Traditional database theory splits the world into two extremes. Under the Closed-World Assumption (CWA), any piece of information not explicitly present in the database is assumed to be false. Under the Open-World Assumption (OWA), anything missing is simply treated as unknown.
Real-world data management systems—such as decentralized web directories, crowdsourced knowledge bases, or integrated corporate data warehouses—exist in a messy middle ground. They are rarely perfectly complete, yet they are not entirely empty either. To bridge this gap, database researchers have developed a formal framework to reason about data completeness, allowing systems to provide reliable, exhaustive query answers even when the underlying data sources are partially populated.
The Spectrum of Data Completeness
To handle partially populated databases, Werner Nutt et al. formalize the Partial Closed-World Assumption (PCWA) in Databases under the Partial Closed-world Assumption: A Survey. Instead of treating the entire database as completely known or completely unknown, the PCWA allows administrators to specify exactly which slices of the data are exhaustive.
These guarantees are typically declared using Table-Completeness Statements (TCSs). As explained by Julien Corman et al. in Complete Approximations of Incomplete Queries, TCSs act as metadata that precisely define the conditions under which specific database segments match the real world. For example, a database might be incomplete overall but possess a TCS guaranteeing that its records for "all capital cities in Europe" are fully exhaustive.
Alternatively, systems can flip this perspective. Ognjen Savković et al. introduce a Completeness-as-Default (CAD) model in Turning The Partial-Closed World Assumption Upside Down. Under CAD, data is assumed to be perfect by default, except for specific, flagged regions that are known to be "sketchy" or patchy.
Completeness Entailment: Can We Trust the Query?
Given a set of completeness statements, the core challenge is completeness entailment: determining whether a complex user query is guaranteed to return a fully exhaustive result.
The intuition behind solving this problem relies on a clever reduction. Werner Nutt et al. demonstrate in Completeness of Queries over Incomplete Databases that reasoning about completeness entailment can be reduced to the classic database problem of query containment. If the logical scope of a user's query is entirely contained within the subsets of the data verified as complete by the TCSs, the query result is guaranteed to be exhaustive (Werner Nutt et al. in Completeness Statements about RDF Data Sources and Their Use for Query Answering).
User Query Scope: [------- European Capitals -------]
Verified Complete Data: [---------- All European Cities ----------]
Result: ENTAILED (The query scope is fully contained in the complete data)
While early methods relied strictly on schema-level metadata, Radityo Eko Prasojo et al. show in Enabling Fine-grained RDF Data Completeness Assessment that incorporating the actual data instances allows for much more precise, fine-grained completeness verification.
Query Approximations: Navigating the Gaps
What happens when a query cannot be proven complete? Running an analytical query over a partially complete database risks producing skewed or misleading results, which can severely compromise data-driven decision-making (Ognjen Savkovic et al. in Towards Approximating Incomplete Queries over Partially Complete Databases (Extended Abstract)).
To mitigate this, researchers developed query approximations. Instead of failing or returning untrustworthy data, the system automatically generates two alternative queries to bound the truth:
- Below (More Specific) Approximations: The system specializes the user's query, narrowing its scope so that it only accesses data segments guaranteed to be complete. This ensures that every returned answer is perfectly reliable, acting as a safe lower bound (Ognjen Savković et al. in Complete Approximations of Incomplete Queries).
- Above (More General) Approximations: The system generalizes the query to provide an upper bound or superset of the ideal result, ensuring no potentially valid information is missed.
By presenting these dual bounds, users can immediately see what information might be lost due to data incompleteness and understand how to safely reformulate their queries.
The Computational Reality of Certain Answers
The theoretical gold standard for querying incomplete data is computing certain answers—the set of tuples that would appear in the query result across every single possible valid completion of the database. However, this is notoriously expensive.
Marco Console et al. explore this in On Querying Incomplete Information in Databases under Bag Semantics, revealing that under realistic bag semantics (where duplicate rows matter, as in SQL), finding the maximum occurrences of certain answers becomes computationally intractable.
To bypass this complexity, Leonid Libkin provides a breakthrough insight in How to Define Certain Answers: for queries that are generic and preserve informativeness, certain answers can be obtained by evaluating the query directly on the incomplete database. This allows standard, highly optimized query engines to produce theoretically sound results without the massive computational overhead typically associated with certain answer semantics.
Handling Incompleteness in Web and Graph Environments
The challenge of data incompleteness becomes even more acute in autonomous web databases and graph-structured data (like RDF or XML), where data entry is highly decentralized and inconsistent.
In autonomous web databases, Garrett Wolf et al. develop the QPIAD framework in Query Processing over Incomplete Autonomous Databases. Instead of relying strictly on exact matches, they mine attribute correlations from small data samples to rewrite queries, uncovering highly relevant "possible answers" that traditional engines would ignore. Yi Chen extends this in QUIC: A System for Handling Imprecision & Incompleteness in Autonomous Databases (Demo) by using a decision-theoretic model to rank and explain these partial matches.
For graph data, structural constraints dictate tractability. Pablo Barcelo et al. show in On Incomplete XML Documents with Integrity Constraints that verifying whether an incomplete XML document can satisfy integrity constraints exhibits a sharp dichotomy between polynomial-time and NP-complete cases. To maintain efficiency during complex graph pattern matching, the authors identify structural "sweet spots" like bounded interfaces in Efficient Evaluation of Well-designed Pattern Trees (Extended Abstract).
Finally, when dealing with aggregate queries over decentralized graph data, Dilshod Ibragimov et al. demonstrate in Optimizing Aggregate SPARQL Queries Using Materialized RDF Views how completeness metadata can be baked directly into query rewriting mechanisms. This prevents incorrect aggregations under the open-world assumption by ensuring that precomputed views are only utilized if they possess the necessary mappings to accurately answer the query. Similarly, Andreas Harth et al. explore in On Completeness Classes for Query Evaluation on Linked Data how leveraging authoritative sources can provide formal completeness classes for decentralized web data.
Key Foundational Work
Query Optimization Using Local Completeness (1997) — contributed 1 concept elements to this direction.
Automatically Inferring Database Schemas (1985) — contributed 1 concept elements to this direction.