A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs
A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs
复制标题
DOI：
10.4230/lipics.icdt.2020.5
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Antoine Amarilli;I. Ceylan
中科院分区：
文献类型：
--
作者：
Antoine Amarilli;I. Ceylan
我们研究了关于概率图的概率查询评估（PQE）的问题，即元素独立的概率数据库（TIDS）在Arity二的签名上。我们的重点是在同态下关闭的查询类别，或等效地，无限的联合查询工会表示UCQ^\ Infty。我们的主要结果指出，UCQ^\ Infty中的所有无界查询都是PQE的＃P-HARD。由于UCQ^\ Infty中的有限查询已经被Dalvi和Suciu的二分法分类[16]，因此我们的结果及其结果暗示着对ucq^\ for Arity-Two签名的UCQ^\ infty查询的完整二分法。该二分法尤其涵盖了UCQ^\ Infty中的所有片段，例如无否（析取）数据元，常规路径查询以及有关Arity-Two签名的大量本体论介导的查询。通过从计算一些查询的阳性分区2-DNF公式（＃pp2dnf）的价值来显示我们的结果，或从无向图（＃U-ST-CON）中的源到目标可靠性问题来显示。 ，取决于最小模型的属性。
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^\infty . Our main result states that all unbounded queries in UCQ^\infty are #P-hard for PQE. As bounded queries in UCQ^\infty are already classified by the dichotomy of Dalvi and Suciu [16], our results and theirs imply a complete dichotomy on PQE for UCQ^\infty queries over arity-two signatures. This dichotomy covers in particular all fragments in UCQ^\infty 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.