TY - GEN
T1 - A dichotomy for homomorphism-closed queries on probabilistic graphs
AU - Amarilli, Antoine
AU - Ceylan, İsmail İlkan
N1 - Publisher Copyright:
© Antoine Amarilli and İsmail İlkan Ceylan; licensed under Creative Commons License CC-BY 23rd International Conference on Database Theory (ICDT 2020).
PY - 2020/3/1
Y1 - 2020/3/1
N2 - We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu [17], our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.
AB - We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu [17], our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.
KW - #P-hardness
KW - Homomorphism-closed queries
KW - Recursive queries
KW - Tuple-independent database
U2 - 10.4230/LIPIcs.ICDT.2020.5
DO - 10.4230/LIPIcs.ICDT.2020.5
M3 - Conference contribution
AN - SCOPUS:85082120619
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 23rd International Conference on Database Theory, ICDT 2020
A2 - Lutz, Carsten
A2 - Jung, Jean Christoph
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 23rd International Conference on Database Theory, ICDT 2020
Y2 - 30 March 2020 through 2 April 2020
ER -