Why is it hard to obtain a dichotomy for consistent query answering?

DOI10.1145/2699912MaRDI QIDQ2946755zbMATH OpenOpenAlexFDO

Authors Gaëlle Fontaine

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2699912

zbMATH Keywords

consistent query answeringconstraint satisfaction problemdichotomyinconsistent databases

Mathematics Subject Classification ID

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

Recommendations

• Why is it hard to obtain a dichotomy for consistent query answering?
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• Consistent query answering for primary keys in Datalog
• Complexity of repair checking and consistent query answering
• On the data complexity of consistent query answering over graph databases

Cites work

• A dichotomy in the complexity of consistent query answering for queries with two atoms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Proof Procedure for Data Dependencies
• Answer sets for consistent query answering in inconsistent databases
• Closure properties of constraints
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 1953133 (Why is no real title available?)
• Minimal-change integrity maintenance using tuple deletions
• On the data complexity of consistent query answering
• On the Structure of Polynomial Time Reducibility
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Why is it hard to obtain a dichotomy for consistent query answering?

Cited in

(3)

• Consistent query answering for primary keys in Datalog
• Why is it hard to obtain a dichotomy for consistent query answering?
• A dichotomy in the complexity of consistent query answering for queries with two atoms

This page was built for publication: Why is it hard to obtain a dichotomy for consistent query answering?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946755)