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: 1480
Venue: PODS
Year: 2009
Pagerank: 6.1493013e-05
Overall Rank: 5,617 | 61.47%
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,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	6.0050351e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
8,007	Complete Approximations of Incomplete Queries	2013	VLDB	5.5077375e-05
11,262	Enriching Relations with Additional Attributes for ER	2024	VLDB	5.093636e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-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.00049907763
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
494	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017526549
853	Queries Independent of Updates	1993	VLDB	0.00013587101
874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013481551
1,277	Extending Dependencies with Conditions	2007	VLDB	0.00011368191
1,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
1,991	Views and Queries: Determinacy and Rewriting	2005	PODS	9.344653e-05
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.2736086e-05
3,733	Closed World Databases Opened Through Null Values	1988	VLDB	7.1653591e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS
2	3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
3	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
4	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
5	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
6	3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS
7	5,616	Capturing Missing Tuples and Missing Values	2010	PODS
8	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
9	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB
10	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS