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.00013198452
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.00025861123
501	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017273167
595	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00015791577
2,140	Logical Foundations of Peer-To-Peer Data Integration	2004	PODS	8.9696138e-05
2,538	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.3246034e-05
2,585	Advanced Processing for Ontological Queries	2010	VLDB	8.2546449e-05
2,614	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2221507e-05
3,503	On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information	2006	PODS	7.2485903e-05
3,614	On Reconciling Data Exchange, Data Integration, and Peer Data Management	2007	PODS	7.1572016e-05
4,870	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.3718189e-05
5,370	Certain Answers Meet Zero-One Laws	2018	PODS	6.157573e-05
5,398	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	6.1473171e-05
5,741	Relative Information Completeness	2009	PODS	6.0085833e-05
6,048	Your notebook is not crumby enough, REPLace it	2020	CIDR	5.9024167e-05
6,474	A Deferred Cleansing Method for RFID Data Analytics	2006	VLDB	5.7713221e-05
6,483	The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data	2005	SIGMOD	5.7682067e-05
7,002	When is Naive Evaluation Possible?	2013	PODS	5.6223434e-05
7,611	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.4830842e-05
7,996	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS	5.4090218e-05
8,068	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.392976e-05
8,435	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD	5.3324907e-05
9,709	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	5.1354025e-05
11,483	Chase Termination Beyond Polynomial Time	2024	PODS	4.9769913e-05
12,207	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9769913e-05
12,707	Certain Answers for XML Queries	2010	PODS	4.9769913e-05
12,789	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	4.9769913e-05
12,906	Incompleteness in Information Integration	2008	VLDB	4.9769913e-05
13,021	Determining Source Contribution in Integration Systems	2005	PODS	4.9769913e-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.00055018384
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049326063
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.0002972645
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027945388
619	On the Semantics of Updates in Databases	1983	PODS	0.00015511647
2,557	On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals	1992	PODS	8.2969024e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS
2	7,711	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,682	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
5	1,737	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
6	12,507	Certain Query Answering in Partially Consistent Databases	2014	VLDB
7	12,701	Completeness of Queries over Incomplete Databases	2011	VLDB
8	2,158	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