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.00014049364
- Overall Rank
- 1,102 | 92.34%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 25 of 25 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 265 |
A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification |
2005 |
SIGMOD |
0.00029763412 |
| 560 |
Dependencies Revisited for Improving Data Quality |
2008 |
PODS |
0.00020141923 |
| 678 |
ConQuer: Efficient Management of Inconsistent Databases |
2005 |
SIGMOD |
0.00018253213 |
| 1,769 |
Logical Foundations of Peer-To-Peer Data Integration |
2004 |
PODS |
0.00010619921 |
| 2,566 |
Database Repairs and Consistent Query Answering: Origins and Further Developments |
2019 |
PODS |
8.5243847e-05 |
| 2,720 |
A General Datalog-Based Framework for Tractable Query Answering over Ontologies |
2009 |
PODS |
8.2367715e-05 |
| 2,755 |
Advanced Processing for Ontological Queries |
2010 |
VLDB |
8.1690695e-05 |
| 3,324 |
On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information |
2006 |
PODS |
7.2213002e-05 |
| 3,937 |
On Reconciling Data Exchange, Data Integration, and Peer Data Management |
2007 |
PODS |
6.6159574e-05 |
| 4,806 |
Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers |
2019 |
SIGMOD |
5.9092698e-05 |
| 5,460 |
Relative Information Completeness |
2009 |
PODS |
5.4957751e-05 |
| 5,494 |
Incomplete Data: What Went Wrong, and How to Fix It |
2014 |
PODS |
5.4759469e-05 |
| 6,295 |
Your notebook is not crumby enough, REPLace it |
2020 |
CIDR |
5.1249204e-05 |
| 6,419 |
A Deferred Cleansing Method for RFID Data Analytics |
2006 |
VLDB |
5.0690363e-05 |
| 6,858 |
When is Naive Evaluation Possible? |
2013 |
PODS |
4.9060157e-05 |
| 7,393 |
Incomplete Information and Certain Answers in General Data Models |
2011 |
PODS |
4.7428879e-05 |
| 7,405 |
The INFOMIX System for Advanced Integration of Incomplete and Inconsistent Data |
2005 |
SIGMOD |
4.7378885e-05 |
| 7,941 |
Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds |
2021 |
SIGMOD |
4.613363e-05 |
| 8,145 |
Evaluating Top-k Queries with Inconsistency Degrees |
2020 |
VLDB |
4.5761263e-05 |
| 9,377 |
Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning |
2022 |
VLDB |
4.347117e-05 |
| 10,908 |
Chase Termination Beyond Polynomial Time |
2024 |
PODS |
4.1945683e-05 |
| 12,215 |
Certain Answers for XML Queries |
2010 |
PODS |
4.1945683e-05 |
| 12,298 |
XML with Incomplete Information: Models, Properties, and Query Answering |
2009 |
PODS |
4.1945683e-05 |
| 12,416 |
Incompleteness in Information Integration |
2008 |
VLDB |
4.1945683e-05 |
| 12,532 |
Determining Source Contribution in Integration Systems |
2005 |
PODS |
4.1945683e-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