A dichotomy in the complexity of consistent query answering for queries with two atoms

DOI10.1016/J.IPL.2011.10.018zbMath1233.68133OpenAlexW1994353670MaRDI QIDQ763497

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

zbMATH Keywords

databasesconsistent query answeringdatabase repairskey constraints

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

On the data complexity of consistent query answering ⋮ On the data complexity of consistent query answering over graph databases ⋮ A dichotomy in the complexity of counting database repairs ⋮ Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering? ⋮ Taming primary key violations to query large inconsistent data via ASP ⋮ Unnamed Item

Cites Work

• Unnamed Item
• First-order query rewriting for inconsistent databases
• On maximal independent sets of vertices in claw-free graphs
• Scalar aggregation in inconsistent databases.
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• Minimal-change integrity maintenance using tuple deletions
• On the Structure of Polynomial Time Reducibility
• Complexity of automaton identification from given data
• Answer sets for consistent query answering in inconsistent databases

This page was built for publication: A dichotomy in the complexity of consistent query answering for queries with two atoms