A dichotomy in the complexity of counting database repairs

DOI10.1016/j.jcss.2013.01.011zbMath1408.68048OpenAlexW2103775650MaRDI QIDQ389240

Dany Maslowski, Jef Wijsen

Publication date: 20 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2013.01.011

zbMATH Keywords

conjunctive queriesprobabilistic databasesconsistent query answeringprimary key

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Related Items (7)

Uniform Reliability of Self-Join-Free Conjunctive Queries ⋮ Counting and enumerating preferred database repairs ⋮ Counting subset repairs with functional dependencies ⋮ First-order under-approximations of consistent query answers ⋮ Unnamed Item ⋮ Consistent query answering for primary keys in Datalog ⋮ On the complexity of inconsistency measurement

Uses Software

• MayBMS

Cites Work

• Unnamed Item
• Unnamed Item
• Queries and materialized views on probabilistic databases
• The complexity of computing the permanent
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• First-order query rewriting for inconsistent databases
• Scalar aggregation in inconsistent databases.
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• PP is as Hard as the Polynomial-Time Hierarchy
• On the Structure of Polynomial Time Reducibility

This page was built for publication: A dichotomy in the complexity of counting database repairs