10.46298/lmcs-18(1:2)2022
https://lmcs.episciences.org/7065
Amarilli, Antoine
Antoine
Amarilli
Ceylan, İsmail İlkan
İsmail İlkan
Ceylan
The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
We study the problem of query evaluation on probabilistic graphs, namely,
tuple-independent probabilistic databases over signatures of arity two. We
focus on the class of queries closed under homomorphisms, or, equivalently, the
infinite unions of conjunctive queries. Our main result states that the
probabilistic query evaluation problem is #P-hard for all unbounded queries
from this class. As bounded queries from this class are equivalent to a union
of conjunctive queries, they are already classified by the dichotomy of Dalvi
and Suciu (2012). Hence, our result and theirs imply a complete data complexity
dichotomy, between polynomial time and #P-hardness, on evaluating
homomorphism-closed queries over probabilistic graphs. This dichotomy covers in
particular all fragments of infinite unions of conjunctive queries over
arity-two signatures, such as negation-free (disjunctive) Datalog, regular path
queries, and a large class of ontology-mediated queries. The dichotomy also
applies to a restricted case of probabilistic query evaluation called
generalized model counting, where fact probabilities must be 0, 0.5, or 1. We
show the main result by reducing from the problem of counting the valuations of
positive partitioned 2-DNF formulae, or from the source-to-target reliability
problem in an undirected graph, depending on properties of minimal models for
the query.
episciences.org
Computer Science - Databases
Computer Science - Computational Complexity
Computer Science - Data Structures and Algorithms
Attribution 4.0 International (CC BY 4.0)
2021-11-01
2022-01-07
2022-01-07
eng
journal article
arXiv:1910.02048
10.48550/arXiv.1910.02048
1860-5974
https://lmcs.episciences.org/7065/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 18, Issue 1
Researchers
Students