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

DOI10.1016/J.IPL.2011.10.018MaRDI QIDQ763497zbMATH OpenOpenAlexFDO

Authors 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

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

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• Answer sets for consistent query answering in inconsistent databases
• Complexity of automaton identification from given data
• First-order query rewriting for inconsistent databases
• Minimal-change integrity maintenance using tuple deletions
• On maximal independent sets of vertices in claw-free graphs
• On the Structure of Polynomial Time Reducibility
• Scalar aggregation in inconsistent databases.

Cited in

(8)

• The 1-Versus-2 Queries Problem Revisited
• scientific article; zbMATH DE number 7561466 (Why is no real title available?)
• On the data complexity of consistent query answering
• Why is it hard to obtain a dichotomy for 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
• A dichotomy in the complexity of counting database repairs
• Taming primary key violations to query large inconsistent data via ASP

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)