Identifying the Extent of Completeness of Query Answers over Partially Complete Databases

Summary: Proposes completeness patterns as table-level selections to denote complete parts of databases. Adapts relational algebra to infer query-answer completeness; proves soundness; extends to instance-aware patterns; shows scalable real-data evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5077
Venue: SIGMOD
Year: 2015
Pagerank: 5.1273783e-05
Overall Rank: 6,271 | 56.42%
DOI: 10.1145/2723372.2750544

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,914	CYADB: A Database that Covers Your Ask	2018	VLDB	4.8878659e-05
6,943	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	4.8876509e-05
9,321	READY: Completeness is in the Eye of the Beholder	2017	CIDR	4.3517399e-05
11,524	Wikinegata: a Knowledge Base with Interesting Negative Statements	2021	VLDB	4.1905499e-05
11,556	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
823	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00016225326
879	Don’t be SCAREd: Use SCalable Automatic REpairing with Maximal Likelihood and Bounded Changes	2013	SIGMOD	0.00015649604
933	Flexible Database Generators	2005	VLDB	0.00015220613
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
3,054	Partial Results in Database Systems	2014	SIGMOD	7.6478475e-05
4,789	Consistency in a Stream Warehouse	2011	CIDR	5.9144227e-05
5,466	Capturing Missing Tuples and Missing Values	2010	PODS	5.4904942e-05
5,467	Relative Information Completeness	2009	PODS	5.4904942e-05
5,508	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4706858e-05
8,790	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	4.4464049e-05
12,185	Bistro Data Feed Management System	2011	SIGMOD	4.1905499e-05
12,217	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,561	Complete Approximations of Incomplete Queries	2013	VLDB	4.7057229e-05
8,802	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4428211e-05
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952
5,466	Capturing Missing Tuples and Missing Values	2010	PODS	5.4904942e-05
3,683	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.84255e-05
7,391	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7383385e-05
5,508	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4706858e-05
14,272	Completeness Information and Its Application to Query Processing	1986	VLDB	-
12,217	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1905499e-05
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05