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: h981728d195610421
Venue: PODS
Year: 2003
Pagerank: 0.00013204612
Overall Rank: 897 | 93.98%
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
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025872962
500	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017280722
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015798582
2,138	Logical Foundations of Peer-To-Peer Data Integration	2004	PODS	8.9737764e-05
2,537	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.328546e-05
2,584	Advanced Processing for Ontological Queries	2010	VLDB	8.2585389e-05
2,613	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2260448e-05
3,503	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2520222e-05
3,614	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1605909e-05
4,868	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.3748367e-05
5,365	Certain Answers Meet Zero-One Laws	2018	PODS	6.1604893e-05
5,392	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	6.1502284e-05
5,740	Relative Information Completeness	2009	PODS	6.011429e-05
6,046	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9052121e-05
6,472	A Deferred Cleansing Method for RFID Data Analytics	2006	VLDB	5.7740555e-05
6,481	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	5.770936e-05
7,001	When is Naive Evaluation Possible?	2013	PODS	5.6250062e-05
7,605	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.485681e-05
7,991	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.4115836e-05
8,062	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.3955302e-05
8,426	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3350162e-05
9,704	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	5.1378347e-05
11,477	Chase Termination Beyond Polynomial Time	2024	PODS	4.9793485e-05
12,201	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9793485e-05
12,701	Certain Answers for XML Queries	2010	PODS	4.9793485e-05
12,783	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9793485e-05
12,900	Incompleteness in Information Integration	2008	VLDB	4.9793485e-05
13,015	Determining Source Contribution in Integration Systems	2005	PODS	4.9793485e-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
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027958527
619	On the Semantics of Updates in Databases	1983	PODS	0.00015518944
2,557	On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals	1992	PODS	8.3008262e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS
2	7,705	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
3	5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
4	8,674	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
5	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
6	12,501	Certain Query Answering in Partially Consistent Databases	2014	VLDB
7	12,695	Completeness of Queries over Incomplete Databases	2011	VLDB
8	2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
9	3,503	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