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: 5076
Venue: SIGMOD
Year: 2015
Pagerank: 5.1323078e-05
Overall Rank: 6,273 | 56.37%
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,912	CYADB: A Database that Covers Your Ask	2018	VLDB	4.8925595e-05
6,941	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	4.8924e-05
9,316	READY: Completeness is in the Eye of the Beholder	2017	CIDR	4.3559005e-05
11,520	Wikinegata: a Knowledge Base with Interesting Negative Statements	2021	VLDB	4.1945683e-05
11,552	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.1945683e-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
827	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD	0.00016220185
881	Don’t be SCAREd: Use SCalable Automatic REpairing with Maximal Likelihood and Bounded Changes	2013	SIGMOD	0.00015661103
934	Flexible Database Generators	2005	VLDB	0.00015227409
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
3,051	Partial Results in Database Systems	2014	SIGMOD	7.6512591e-05
4,788	Consistency in a Stream Warehouse	2011	CIDR	5.9200462e-05
5,459	Capturing Missing Tuples and Missing Values	2010	PODS	5.4957751e-05
5,460	Relative Information Completeness	2009	PODS	5.4957751e-05
5,494	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4759469e-05
8,792	Database Optimization for the Cloud: Where Costs, Partial Results, and Consumer Choice Meet	2015	CIDR	4.4506724e-05
12,177	Bistro Data Feed Management System	2011	SIGMOD	4.1945683e-05
12,209	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,560	Complete Approximations of Incomplete Queries	2013	VLDB	4.7102455e-05
8,803	Coping with Incomplete Data: Recent Advances	2020	PODS	4.4470842e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
5,459	Capturing Missing Tuples and Missing Values	2010	PODS	5.4957751e-05
3,681	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.8492288e-05
7,393	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7428879e-05
5,494	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	5.4759469e-05
14,258	Completeness Information and Its Application to Query Processing	1986	VLDB	-
12,209	Completeness of Queries over Incomplete Databases	2011	VLDB	4.1945683e-05
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05