On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases

Summary: Characterizes decidability and complexity of consistent query answering under key and inclusion dependencies for soundness/completeness variants, proving general undecidability. Identifies a maximal class of inclusion dependencies that with keys yields decidable query answering, with direct implications for data integration. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1297
Venue: PODS
Year: 2003
Pagerank: 0.00013481551
Overall Rank: 874 | 94.01%
DOI: 10.1145/773153.773179

Incoming Non-self Citations Over Time

Authors

1. Andrea Calì (Sapienza University)
2. Domenico Lembo (Sapienza University)
3. Riccardo Rosati (Sapienza University)

BibTeX Citation

@inproceedings{cali_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases}},
        url = {https://dl.acm.org/doi/10.1145/773153.773179},
        doi = {10.1145/773153.773179},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Calì, Andrea and Lembo, Domenico and Rosati, Riccardo},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00026231189
494	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017526549
586	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00016124396
2,100	Logical Foundations of Peer-To-Peer Data Integration	2004	PODS	9.1675595e-05
2,481	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.5196153e-05
2,544	Advanced Processing for Ontological Queries	2010	VLDB	8.4444438e-05
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.4181806e-05
3,546	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.3244507e-05
4,811	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.4983069e-05
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05
5,271	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	6.2907571e-05
5,617	Relative Information Completeness	2009	PODS	6.1493013e-05
5,931	Your notebook is not crumby enough, REPLace it	2020	CIDR	6.0369708e-05
6,343	A Deferred Cleansing Method for RFID Data Analytics	2006	VLDB	5.9063839e-05
6,359	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	5.9019991e-05
6,852	When is Naive Evaluation Possible?	2013	PODS	5.7540317e-05
7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.61159e-05
7,830	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.5357919e-05
8,133	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.4813895e-05
8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.4574671e-05
9,522	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	5.2557598e-05
11,129	Chase Termination Beyond Polynomial Time	2024	PODS	5.093636e-05
11,901	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	5.093636e-05
12,410	Certain Answers for XML Queries	2010	PODS	5.093636e-05
12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	5.093636e-05
12,610	Incompleteness in Information Integration	2008	VLDB	5.093636e-05
12,725	Determining Source Contribution in Integration Systems	2005	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
602	On the Semantics of Updates in Databases	1983	PODS	0.00015856828
2,506	On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals	1992	PODS	8.4897076e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS
2	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
3	5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
4	8,506	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
5	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
6	12,210	Certain Query Answering in Partially Consistent Databases	2014	VLDB
7	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
8	2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
9	3,433	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS
10	33	Consistent Query Answers in Inconsistent Databases	1999	PODS