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.0085833e-05
Overall Rank: 5,741 | 61.42%
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,740	Capturing Missing Tuples and Missing Values	2010	PODS	6.0085833e-05
6,148	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.8684233e-05
7,612	On Scale Independence for Querying Big Data	2014	PODS	5.4829143e-05
8,174	Complete Approximations of Incomplete Queries	2013	VLDB	5.3822481e-05
11,596	Enriching Relations with Additional Attributes for ER	2024	VLDB	4.9769913e-05
12,701	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9769913e-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.00049326063
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023580688
501	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017273167
875	Queries Independent of Updates	1993	VLDB	0.0001331025
897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013198452
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011150915
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010946011
2,046	Views and Queries: Determinacy and Rewriting	2005	PODS	9.1331561e-05
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0855936e-05
3,815	Closed World Databases Opened Through Null Values	1988	VLDB	7.0051309e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,611	Incomplete Information and Certain Answers in General Data Models	2011	PODS
2	3,808	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
3	4,594	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,148	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,740	Capturing Missing Tuples and Missing Values	2010	PODS
8	12,701	Completeness of Queries over Incomplete Databases	2011	VLDB
9	14,775	Completeness Information and Its Application to Query Processing	1986	VLDB
10	2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS