Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?

DOI10.1145/2699912zbMath1354.68072OpenAlexW2164496990MaRDI QIDQ2946755

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

constraint satisfaction problemdichotomyinconsistent databasesconsistent query answering

Mathematics Subject Classification ID

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

Related Items (1)

Consistent query answering for primary keys in Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• On the data complexity of consistent query answering
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• Minimal-change integrity maintenance using tuple deletions
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Proof Procedure for Data Dependencies
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Answer sets for consistent query answering in inconsistent databases
• Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?
• The complexity of satisfiability problems

This page was built for publication: Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?