Projects per year
Abstract / Description of output
This article investigates the question of whether a partially closed database has complete information to answer a query. In practice an enterprise often maintains master data D_{m}, a closedworld database. We say that a database D is partially closed if it satisfies a set V of containment constraints of the form q(D) ⊆ p(D_{m}), where q is a query in a language L_{C} and p is a projection query. The part of D not constrained by (D_{m}, V) is open, from which some tuples may be missing. The database D is said to be complete for a query Q relative to (D_{m}, V) if for all partially closed extensions D' of D, Q(D') = Q(D), i.e., adding tuples to D either violates some constraints in V or does not change the answer to Q.
We first show that the proposed model can also capture the consistency of data, in addition to its relative completeness. Indeed, integrity constraints studied for data consistency can be expressed as containment constraints. We then study two problems. One is to decide, given D_{m}, V, a query Q in a language L_{Q}, and a partially closed database D, whether D is complete for Q relative to (D_{m}, V). The other is to determine, given D_{m}, V and Q, whether there exists a partially closed database that is complete for Q relative to (Dm, V). We establish matching lower and upper bounds on these problems for a variety of languages L_{Q} and L_{C}. We also provide characterizations for a database to be relatively complete, and for a query to allow a relatively complete database, when L_{Q} and L_{C} are conjunctive queries.
Original language  English 

Article number  27 
Pages (fromto)  144 
Number of pages  44 
Journal  ACM Transactions on Database Systems 
Volume  35 
Issue number  4 
DOIs  
Publication status  Published  Nov 2010 
Keywords / Materials (for Nontextual outputs)
 Incomplete information
 complexity
 master data management
 partially closed databases
 relative completeness
Fingerprint
Dive into the research topics of 'Relative information completeness'. Together they form a unique fingerprint.Projects
 1 Finished

Heterogeneous and Permanent data
Buneman, P., Fan, W., Libkin, L. & Viglas, S.
1/03/08 → 29/02/12
Project: Research