论文标题
无限制封闭图形查询的均匀可靠性
Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries
论文作者
论文摘要
我们研究了一个固定的查询可靠性问题，该问题询问固定的布尔查询Q，给定实例i，i的子介绍满足了Q。同等地，这是对元素不依赖于元素的概率数据库的布尔查询评估的限制案例，所有事实必须具有所有事实，所有事实都必须具有可能性1/2。我们专注于图形特征，以及在同态下关闭的查询。我们表明，对于任何无限制的查询，即不等于连接性查询的结合，统一的可靠性问题是＃p-hard。这重新接收了S-T连接性的硬度，例如，它计算了输入图的多少个子图在源和水槽之间具有路径。 这种新的硬度导致统一的可靠性增强了我们早期的硬度导致对无限同构封闭的查询（ICDT'20）的概率查询评估。的确，我们早期使用的证据具有概率1的至关重要的事实，因此不适用于未加权案例。本文提供的新证明避免了这一点。它使用我们的最新硬度结果，对无自结合的非层次结合查询的统一可靠性（ICDT'21）以及新技术。
We study the uniform query reliability problem, which asks, for a fixed Boolean query Q, given an instance I, how many subinstances of I satisfy Q. Equivalently, this is a restricted case of Boolean query evaluation on tuple-independent probabilistic databases where all facts must have probability 1/2. We focus on graph signatures, and on queries closed under homomorphisms. We show that for any such query that is unbounded, i.e., not equivalent to a union of conjunctive queries, the uniform reliability problem is #P-hard. This recaptures the hardness, e.g., of s-t connectedness, which counts how many subgraphs of an input graph have a path between a source and a sink. This new hardness result on uniform reliability strengthens our earlier hardness result on probabilistic query evaluation for unbounded homomorphism-closed queries (ICDT'20). Indeed, our earlier proof crucially used facts with probability 1, so it did not apply to the unweighted case. The new proof presented in this paper avoids this; it uses our recent hardness result on uniform reliability for non-hierarchical conjunctive queries without self-joins (ICDT'21), along with new techniques.
