License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2021.17
URN: urn:nbn:de:0030-drops-137252
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13725/
Amarilli, Antoine ;
Kimelfeld, Benny
Uniform Reliability of Self-Join-Free Conjunctive Queries
Abstract
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 in a known dichotomy: reliability can be computed in polynomial time for hierarchical queries, and is #P-hard for non-hierarchical queries. Hierarchical queries also characterize the tractability of queries for other tasks: having read-once lineage formulas, supporting insertion/deletion updates to the database in constant time, and having a tractable computation of tuples' Shapley and Banzhaf values.
In this work, 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 in polynomial time, like the reliability problem. However, it is an open question whether being hierarchical is necessary for the uniform reliability problem to be in polynomial time. In fact, the complexity of the problem has been unknown even for the simplest non-hierarchical CQs without self-joins.
We solve this open question by showing that uniform reliability is #P-complete for every non-hierarchical CQ without self-joins. Hence, we establish that being hierarchical also characterizes the tractability of unweighted counting of the satisfying tuple subsets. We also consider the generalization to query reliability where all tuples of the same relation have the same probability, and give preliminary results on the complexity of this problem.
BibTeX - Entry
@InProceedings{amarilli_et_al:LIPIcs.ICDT.2021.17,
author = {Amarilli, Antoine and Kimelfeld, Benny},
title = {{Uniform Reliability of Self-Join-Free Conjunctive Queries}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {17:1--17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-179-5},
ISSN = {1868-8969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13725},
URN = {urn:nbn:de:0030-drops-137252},
doi = {10.4230/LIPIcs.ICDT.2021.17},
annote = {Keywords: Hierarchical conjunctive queries, query reliability, tuple-independent database, counting problems, #P-hardness}
}
|
Keywords: |
|
Hierarchical conjunctive queries, query reliability, tuple-independent database, counting problems, #P-hardness |
|
Collection: |
|
24th International Conference on Database Theory (ICDT 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
11.03.2021 |
