A dichotomy in the complexity of counting database repairs

DOI10.1016/J.JCSS.2013.01.011MaRDI QIDQ389240zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• A survey of the data complexity of consistent query answering under key constraints
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• 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 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• First-order query rewriting for inconsistent databases
• On the Structure of Polynomial Time Reducibility
• PP is as Hard as the Polynomial-Time Hierarchy
• Queries and materialized views on probabilistic databases
• Scalar aggregation in inconsistent databases.
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The complexity of computing the permanent

Cited in

(15)

• Counting subset repairs with functional dependencies
• A survey of the data complexity of consistent query answering under key constraints
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• Characterizing and computing causes for query answers in databases from database repairs and repair programs
• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• Consistent query answering for primary keys in Datalog
• Uniform reliability of self-join-free conjunctive queries
• On the complexity of inconsistency measurement
• Inconsistency-tolerant semantics based on (preferred) repairs (invited paper)
• Counting and enumerating preferred database repairs
• The Complexity of Counting Problems Over Incomplete Databases
• Uniform Reliability of Self-Join-Free Conjunctive Queries
• scientific article; zbMATH DE number 7561483 (Why is no real title available?)
• First-order under-approximations of consistent query answers

Describes a project that uses

Uses Software

• MayBMS

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

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