A dichotomy in the complexity of consistent query answering for queries with two atoms
From MaRDI portal
Publication:763497
DOI10.1016/J.IPL.2011.10.018zbMATH Open1233.68133OpenAlexW1994353670MaRDI QIDQ763497FDOQ763497
Phokion G. Kolaitis, Enela Pema
Publication date: 9 March 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.10.018
Recommendations
- Why is it hard to obtain a dichotomy for consistent query answering?
- Why is it hard to obtain a dichotomy for consistent query answering?
- A dichotomy in the complexity of counting database repairs
- Consistent query answering for primary keys in Datalog
- The dichotomy of probabilistic inference for unions of conjunctive queries
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)
Cites Work
- Title not available (Why is that?)
- On the Structure of Polynomial Time Reducibility
- A remark on the complexity of consistent conjunctive query answering under primary key violations
- Minimal-change integrity maintenance using tuple deletions
- Answer sets for consistent query answering in inconsistent databases
- First-order query rewriting for inconsistent databases
- On maximal independent sets of vertices in claw-free graphs
- Complexity of automaton identification from given data
- Scalar aggregation in inconsistent databases.
Cited In (7)
- Title not available (Why is that?)
- On the data complexity of consistent query answering
- Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?
- On the data complexity of consistent query answering over graph databases
- Taming primary key violations to query large inconsistent data via ASP
- A dichotomy in the complexity of counting database repairs
- The 1-Versus-2 Queries Problem Revisited
This page was built for publication: A dichotomy in the complexity of consistent query answering for queries with two atoms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q763497)
