Obtaining Complete Answers from Incomplete Databases

Summary: A sound-and-complete framework reduces query-answer completeness over partially known relations to query independence from updates. It yields polynomial-time decisions for conjunctive comparison updates, checks completeness in the current instance, and extends to partially incorrect databases. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8552
Venue: VLDB
Year: 1996
Pagerank: 9.1434045e-05
Overall Rank: 2,117 | 85.48%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (AT&T)

BibTeX Citation

@article{levy_vldb96,
        title = {{Obtaining Complete Answers from Incomplete Databases}},
        author = {Levy, Alon Y.},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {402},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
917	Data Integration: The Teenage Years	2006	VLDB	0.00013224381
3,377	Expiring Data in a Warehouse	1998	VLDB	7.4598611e-05
4,944	Hybrid Querying Over Relational Databases and Large Language Models	2025	CIDR	6.432467e-05
5,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
5,617	Relative Information Completeness	2009	PODS	6.1493013e-05
6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	6.0050351e-05
6,278	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.9287393e-05
7,556	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.5997742e-05
8,007	Complete Approximations of Incomplete Queries	2013	VLDB	5.5077375e-05
8,547	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.4119882e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-05
12,940	Fast High-Dimensional Data Search in Incomplete Databases	1998	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00032192665
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015560958
853	Queries Independent of Updates	1993	VLDB	0.00013587101
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
1,388	SIMS: Retrieving and Integrating Information From Multiple Sources	1993	SIGMOD	0.0001094675
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,993	Normalizing Incomplete Databases	1995	PODS
2	2,934	Data Exchange and Incomplete Information	2006	PODS
3	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
4	14,459	Completeness Information and Its Application to Query Processing	1986	VLDB
5	5,271	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS
6	8,007	Complete Approximations of Incomplete Queries	2013	VLDB
7	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
8	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
9	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
10	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD