Normalizing incomplete databases

Databases are often incomplete because of the presence of disjunctive information, due to conflicts, partial knowledge and other reasons. Queries against such databases often ask questions about various possibilities encoded by the stored data, rather than the stored data itself. Normalization, which is a mechanism for asking such queries, was presented in [LW93a]; however, it had exponential space complexity. The main goal of this paper is to develop a general theory of answering queries against incomplete databases with disjunctive information, and use it to design practical algorithms for query evaluation. We define the semantics of such databases and prove normalization theorems for setand bag-based complex objects. These theorems provide us with programming primitives that one needs in order to obtain the list of all possibilities encoded by a complex object with disjunctions. We study two ways of making query evaluation faster and more space efficient. Partial normalization allows us to disregard some of the disjunctions if they do not affect a given query. We also design a new normalization algorithm that produces objects represented by an incomplete database one-by-one, rather than all at once. It has linear space complexity and allows us to speed up many classes of queries. Algorithms presented in this paper have been implemented in existing dbpl. We present experimental results that demonstrate substantial improvement over standard algorithms, both in space and time.