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.4904942e-05
Overall Rank: 5,466 | 62.02%
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,271	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1273783e-05
7,561	Complete Approximations of Incomplete Queries	2013	VLDB	4.7057229e-05
12,217	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1905499e-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
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028572729
560	Dependencies Revisited for Improving Data Quality	2008	PODS	0.0002012328
620	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00018983367
937	Queries Independent of Updates	1993	VLDB	0.00015194231
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.0001342924
2,039	Views and Queries: Determinacy and Rewriting	2005	PODS	9.7059912e-05
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
2,598	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4660607e-05
2,776	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1371926e-05
2,836	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0466188e-05
3,582	Closed World Databases Opened Through Null Values	1988	VLDB	6.9455143e-05
5,467	Relative Information Completeness	2009	PODS	5.4904942e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,824	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7233576e-05
8,951	Queries with Arithmetic on Incomplete Databases	2020	PODS	4.420578e-05
5,508	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4706858e-05
11,164	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	4.1905499e-05
12,217	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1905499e-05
14,272	Completeness Information and Its Application to Query Processing	1986	VLDB	-
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
2,776	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.1371926e-05
5,467	Relative Information Completeness	2009	PODS	5.4904942e-05
6,271	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1273783e-05