一句话：证明概率图上同态封闭查询求值存在多项式时间与#P-hard之间的完整数据复杂度二分。
论文研究二阶签名上的元组独立概率数据库，即概率图上的查询求值，关注在同态下封闭的查询类，等价于合取查询的无限并。核心结果为：该类中所有无界查询的概率查询求值问题都是 #P-hard；有界查询等价于合取查询的有限并，已由 Dalvi 与 Suciu（2012）的二分法定理分类。两者结合给出概率图上同态封闭查询求值的完整数据复杂度二分：多项式时间或 #P-hard。该结果覆盖二阶签名上合取查询无限并的多个片段，如无否定（析取）Datalog、正则路径查询和一大类本体介导查询，也适用于事实概率仅为 0、0.5 或 1 的广义模型计数。证明通过归约自正分区 2-DNF 公式的赋值计数，或归约自无向图源到目标可靠性问题，具体取决于查询最小模型的性质。
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.
@article{paperbot1751,
title = {The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs},
author = {Antoine Amarilli and İsmail İlkan Ceylan},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:2)2022}
}