Back to papers
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
- 1298
- Venue
- PODS
- Year
- 2003
- Pagerank
- 0.00014037952
- Overall Rank
- 1,101 | 92.35%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 25 of 25 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 268 |
A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification |
2005 |
SIGMOD |
0.00029739054 |
| 560 |
Dependencies Revisited for Improving Data Quality |
2008 |
PODS |
0.0002012328 |
| 677 |
ConQuer: Efficient Management of Inconsistent Databases |
2005 |
SIGMOD |
0.00018250681 |
| 1,767 |
Logical Foundations of Peer-To-Peer Data Integration |
2004 |
PODS |
0.00010609587 |
| 2,574 |
Database Repairs and Consistent Query Answering: Origins and Further Developments |
2019 |
PODS |
8.5126812e-05 |
| 2,723 |
A General Datalog-Based Framework for Tractable Query Answering over Ontologies |
2009 |
PODS |
8.2314732e-05 |
| 2,763 |
Advanced Processing for Ontological Queries |
2010 |
VLDB |
8.1614123e-05 |
| 3,325 |
On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information |
2006 |
PODS |
7.2149375e-05 |
| 3,940 |
On Reconciling Data Exchange, Data Integration, and Peer Data Management |
2007 |
PODS |
6.6096825e-05 |
| 4,809 |
Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers |
2019 |
SIGMOD |
5.9035874e-05 |
| 5,467 |
Relative Information Completeness |
2009 |
PODS |
5.4904942e-05 |
| 5,508 |
Incomplete Data: What Went Wrong, and How to Fix It |
2014 |
PODS |
5.4706858e-05 |
| 6,295 |
Your notebook is not crumby enough, REPLace it |
2020 |
CIDR |
5.1200006e-05 |
| 6,414 |
A Deferred Cleansing Method for RFID Data Analytics |
2006 |
VLDB |
5.0648604e-05 |
| 6,857 |
When is Naive Evaluation Possible? |
2013 |
PODS |
4.9013761e-05 |
| 7,391 |
Incomplete Information and Certain Answers in General Data Models |
2011 |
PODS |
4.7383385e-05 |
| 7,405 |
The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data |
2005 |
SIGMOD |
4.7333266e-05 |
| 7,944 |
Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds |
2021 |
SIGMOD |
4.6089395e-05 |
| 8,148 |
Evaluating Top-k Queries with Inconsistency Degrees |
2020 |
VLDB |
4.5717374e-05 |
| 9,385 |
Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning |
2022 |
VLDB |
4.342951e-05 |
| 10,912 |
Chase Termination Beyond Polynomial Time |
2024 |
PODS |
4.1905499e-05 |
| 12,223 |
Certain Answers for XML Queries |
2010 |
PODS |
4.1905499e-05 |
| 12,306 |
XML with Incomplete Information: Models, Properties, and Query Answering |
2009 |
PODS |
4.1905499e-05 |
| 12,425 |
Incompleteness in Information Integration |
2008 |
VLDB |
4.1905499e-05 |
| 12,541 |
Determining Source Contribution in Integration Systems |
2005 |
PODS |
4.1905499e-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.
Semantically Similar Papers