Capturing Missing Tuples and Missing Values

Summary: Introduce c-instances—conditional tables constrained by master data—to model partially closed databases with both missing tuples and missing values, and define three semantics for query completeness under different value-instantiation regimes. Study four problems (completeness checking, existence, minimal-size completeness, bounded-size existence) and establish matching upper and lower complexity bounds across several query languages for each completeness model. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1516
Venue: PODS
Year: 2010
Pagerank: 6.1493013e-05
Overall Rank: 5,616 | 61.48%
DOI: 10.1145/1807085.1807109

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Harbin Engineering University; University of Edinburgh)
2. Floris Geerts (University of Edinburgh)

BibTeX Citation

@inproceedings{fan_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Capturing Missing Tuples and Missing Values}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807109},
        doi = {10.1145/1807085.1807109},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Geerts, Floris},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	6.0050351e-05
8,007	Complete Approximations of Incomplete Queries	2013	VLDB	5.5077375e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
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
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
853	Queries Independent of Updates	1993	VLDB	0.00013587101
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,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-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
5,617	Relative Information Completeness	2009	PODS	6.1493013e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
2	9,225	Queries with Arithmetic on Incomplete Databases	2020	PODS
3	5,271	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS
4	11,367	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS
5	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
6	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB
7	2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
8	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
9	5,617	Relative Information Completeness	2009	PODS
10	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD