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: 5.9887721e-05
Overall Rank: 5,754 | 61.44%
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,753	Capturing Missing Tuples and Missing Values	2010	PODS	5.9887721e-05
6,166	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.8492355e-05
7,628	On Scale Independence for Querying Big Data	2014	PODS	5.4649494e-05
8,189	Complete Approximations of Incomplete Queries	2013	VLDB	5.3649295e-05
11,644	Enriching Relations with Additional Attributes for ER	2024	VLDB	4.9605343e-05
12,744	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9605343e-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.00049435337
239	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023510465
502	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017239652
878	Queries Independent of Updates	1993	VLDB	0.0001326705
899	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013158587
1,297	Extending Dependencies with Conditions	2007	VLDB	0.00011118907
1,355	Independence of Logic Database Queries and Updates	1990	PODS	0.00010910619
2,055	Views and Queries: Determinacy and Rewriting	2005	PODS	9.1029941e-05
2,166	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9171951e-05
2,740	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0589519e-05
3,820	Closed World Databases Opened Through Null Values	1988	VLDB	6.9820853e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,627	Incomplete Information and Certain Answers in General Data Models	2011	PODS
2	3,817	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
3	4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS
4	899	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
5	6,166	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
6	3,515	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS
7	5,753	Capturing Missing Tuples and Missing Values	2010	PODS
8	12,744	Completeness of Queries over Incomplete Databases	2011	VLDB
9	14,815	Completeness Information and Its Application to Query Processing	1986	VLDB
10	2,740	On The Integrity Of Databases With Incomplete Information	1986	PODS