Antoine Amarilli ; Benny Kimelfeld - Uniform Reliability of Self-Join-Free Conjunctive Queries

lmcs:10088 - Logical Methods in Computer Science, November 9, 2022, Volume 18, Issue 4 - https://doi.org/10.46298/lmcs-18(4:3)2022
Uniform Reliability of Self-Join-Free Conjunctive QueriesArticle

Authors: Antoine Amarilli ; Benny Kimelfeld

    The reliability of a Boolean Conjunctive Query (CQ) over a tuple-independent probabilistic database is the probability that the CQ is satisfied when the tuples of the database are sampled one by one, independently, with their associated probability. For queries without self-joins (repeated relation symbols), the data complexity of this problem is fully characterized by a known dichotomy: reliability can be computed in polynomial time for hierarchical queries, and is #P-hard for non-hierarchical queries. Inspired by this dichotomy, we investigate a fundamental counting problem for CQs without self-joins: how many sets of facts from the input database satisfy the query? This is equivalent to the uniform case of the query reliability problem, where the probability of every tuple is required to be 1/2. Of course, for hierarchical queries, uniform reliability is solvable in polynomial time, like the reliability problem. We show that being hierarchical is also necessary for this tractability (under conventional complexity assumptions). In fact, we establish a generalization of the dichotomy that covers every restricted case of reliability in which the probabilities of tuples are determined by their relation.


    Volume: Volume 18, Issue 4
    Published on: November 9, 2022
    Accepted on: September 27, 2022
    Submitted on: September 27, 2022
    Keywords: Computer Science - Databases

    Consultation statistics

    This page has been seen 1277 times.
    This article's PDF has been downloaded 282 times.