摘要：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â^Z. Our main result states that all unbounded queries in UCQâ^Z are #P-hard for PQE. As bounded queries in UCQâ^Z are already classified by the dichotomy of Dalvi and Suciu [Dalvi and Suciu, 2012], our results and theirs imply a complete dichotomy on PQE for UCQâ^Z queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQâ^Z 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.
