Problem of Incomplete Information in Relational Databases

摘要

The basic semantic assumption is that an incomplete database is a set of complete databases (relations). The author shows that there are twotural lattice structures on the set of all sets of relations. There are several candidate tools for storing and manipulating databases with incomplete information. The author focuses on generalizations of relations. These generalizations, called tables allow variables representing unknown values as entries, as well as entries constraining the variables. The author defines four increasingly (syntactically) stricter classes of tables and the author studies their abilities to serve as a basis for implementing incomplete databases and the operations on them. It turns out that the new class of Horn tables is the most significant from a practical point of view. In this class of tables the author is able to efficiently evaluate positive existential queries and in some cases least fixpoint (recursive) queries. In Horn tables the author can also efficiently incorporate the information contained in one join dependency and a set of equality generating dependencies, as well as hold the result of a subclass of the update operations.