Relative Information Completeness

Summary: Defines "partially closed" databases via containment constraints q(D)⊆p(Dm) w.r.t. master data Dm to formalize relative information completeness and subsume integrity constraints. Gives decision procedures and tight complexity for (i) checking D's completeness for Q and (ii) existence of a relatively complete D, with CQ-specific characterizations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h6591c2989e9f016f
Venue: PODS
Year: 2009
Pagerank: 6.011429e-05
Overall Rank: 5,740 | 61.41%
DOI: 10.1145/1559795.1559811

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (AT&T; University of Edinburgh)
2. Floris Geerts (University of Edinburgh)

BibTeX Citation

@inproceedings{fan_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Relative Information Completeness}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559811},
        doi = {10.1145/1559795.1559811},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Geerts, Floris},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,739	Capturing Missing Tuples and Missing Values	2010	PODS	6.011429e-05
6,146	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.8712024e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
8,168	Complete Approximations of Incomplete Queries	2013	VLDB	5.3847972e-05
11,590	Enriching Relations with Additional Attributes for ER	2024	VLDB	4.9793485e-05
12,695	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
500	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017280722
875	Queries Independent of Updates	1993	VLDB	0.00013316445
897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013204612
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011156154
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010951176
2,044	Views and Queries: Determinacy and Rewriting	2005	PODS	9.137464e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0893712e-05
3,813	Closed World Databases Opened Through Null Values	1988	VLDB	7.0084288e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,605	Incomplete Information and Certain Answers in General Data Models	2011	PODS
2	3,807	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
3	4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS
4	897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
5	6,146	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
6	3,503	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS
7	5,739	Capturing Missing Tuples and Missing Values	2010	PODS
8	12,695	Completeness of Queries over Incomplete Databases	2011	VLDB
9	14,770	Completeness Information and Its Application to Query Processing	1986	VLDB
10	2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS