Uniform Reliability of Self-Join-Free Conjunctive Queries

DOI10.46298/LMCS-18(4:3)2022MaRDI QIDQ5060188zbMATH OpenOpenAlexFDO

Authors Antoine Amarilli, Benny Kimelfeld

Publication date 9 January 2023

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.07093v9

zbMATH Keywords

counting problems\#P-hardnesshierarchical conjunctive queriesquery reliabilitytuple-independent database

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• The dichotomy of probabilistic inference for unions of conjunctive queries
• A dichotomy in the complexity of counting database repairs
• Consistent query answering for self-join-free conjunctive queries under primary key constraints
• Dichotomies for Queries with Negation in Probabilistic Databases
• The Complexity of Counting Problems Over Incomplete Databases

Cites work

• scientific article; zbMATH DE number 7471691 (Why is no real title available?)
• A dichotomy in the complexity of counting database repairs
• Mathematical Properties of the Banzhaf Power Index
• On the history of the kronecker product
• Stochastic Games
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Shapley Value of Tuples in Query Answering.
• The complexity of the counting constraint satisfaction problem
• The dichotomy of probabilistic inference for unions of conjunctive queries

Cited in

(2)

• Approximating queries on probabilistic graphs
• Conjunctive queries on probabilistic graphs: the limits of approximability

This page was built for publication: Uniform Reliability of Self-Join-Free Conjunctive Queries

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