Amarilli, Antoine ;
Kimelfeld, Benny
Uniform Reliability of SelfJoinFree Conjunctive Queries
Abstract
The reliability of a Boolean Conjunctive Query (CQ) over a tupleindependent 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 selfjoins (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 #Phard for nonhierarchical queries. Hierarchical queries also characterize the tractability of queries for other tasks: having readonce 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 selfjoins: 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 nonhierarchical CQs without selfjoins.
We solve this open question by showing that uniform reliability is #Pcomplete for every nonhierarchical CQ without selfjoins. 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 SelfJoinFree Conjunctive Queries}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {17:117:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771795},
ISSN = {18688969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13725},
URN = {urn:nbn:de:0030drops137252},
doi = {10.4230/LIPIcs.ICDT.2021.17},
annote = {Keywords: Hierarchical conjunctive queries, query reliability, tupleindependent database, counting problems, #Phardness}
}
11.03.2021
Keywords: 

Hierarchical conjunctive queries, query reliability, tupleindependent database, counting problems, #Phardness 
Seminar: 

24th International Conference on Database Theory (ICDT 2021)

Issue date: 

2021 
Date of publication: 

11.03.2021 