Title

Bag Relational Algebra with Grouping and Aggregation over C-Tables with Linear Conditions

Document Type

Article

Publication Date

2011

Publication Source

International Journal on Advances in Intelligent Systems

Volume

4

Issue

3&4

Inclusive pages

258-272

Publisher

The International Academy, Research and Industry Association (IARIA)

ISBN/ISSN

19422679

Abstract

We introduce bag relational algebra with grouping and aggregation over a particular representation of incomplete information called c-tables, which was first introduced by Grahne in 1984. In order for this algebra to be closed and “welldefined”, we adopt the closed world assumption as described by Reiter in 1978 and extend the tuple and table conditions to linear ones. We explore the problem of rewriting and simplifying this novel type of c-tables, show how to perform equivalence test for c-tables, and argue why it is difficult to create a canonical form for c-tables. We present certain answer semantics for a full-blown relational algebra with grouping and aggregation and accordingly present algorithms for executing the different relational algebra operators over our representation of incomplete information. The algorithms run in polynomial time relative to the size of the precise information, which makes them a candidate for implementation as part of a DBMS engine that supports storage and retrieval of incomplete information.

Disciplines

Computer Sciences

This document is currently not available here.

  Contact Author

Share

COinS