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: 1517
Venue: PODS
Year: 2010
Pagerank: 5.4957751e-05
Overall Rank: 5,459 | 62.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan
2. Floris Geerts

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,273	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1323078e-05
7,560	Complete Approximations of Incomplete Queries	2013	VLDB	4.7102455e-05
12,209	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1945683e-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
48	Data Integration: A Theoretical Perspective	2002	PODS	0.00069720859
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00020141923
621	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00019005115
938	Queries Independent of Updates	1993	VLDB	0.00015197786
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.00013441514
2,034	Views and Queries: Determinacy and Rewriting	2005	PODS	9.7156155e-05
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
2,594	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.474176e-05
2,769	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1450304e-05
2,830	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.054172e-05
3,576	Closed World Databases Opened Through Null Values	1988	VLDB	6.9506798e-05
5,460	Relative Information Completeness	2009	PODS	5.4957751e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,818	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7300958e-05
8,947	Queries with Arithmetic on Incomplete Databases	2020	PODS	4.4248197e-05
5,494	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4759469e-05
11,161	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	4.1945683e-05
12,209	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1945683e-05
14,258	Completeness Information and Its Application to Query Processing	1986	VLDB	-
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
2,769	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1450304e-05
5,460	Relative Information Completeness	2009	PODS	5.4957751e-05
6,273	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1323078e-05