Skip to Main content Skip to Navigation
Journal articles

The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs

Abstract : 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.
Complete list of metadata

https://hal.telecom-paris.fr/hal-03712200
Contributor : Antoine Amarilli Connect in order to contact the contributor
Submitted on : Saturday, July 2, 2022 - 4:41:47 PM
Last modification on : Friday, August 5, 2022 - 11:35:58 AM

Links full text

Identifiers

  • HAL Id : hal-03712200, version 1
  • ARXIV : 1910.02048

Collections

Citation

Antoine Amarilli, İsmail İlkan Ceylan. The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022. ⟨hal-03712200⟩

Share

Metrics

Record views

19