一句话：证明无自连接合取查询的均匀可靠性可多项式求解当且仅当查询是层次的，并推广可靠性二分法。
本文研究元组独立概率数据库中布尔合取查询（CQ）的可靠性问题：每个元组按给定概率独立采样，求查询被满足的概率。对无自连接 CQ，已有二分法表明层次查询多项式可解，非层次查询 #P 难。作者转而考察其均匀情形：所有元组概率均为 1/2，即统计输入数据库中有多少事实子集满足查询。主要结果表明，在常规复杂度假设下，层次性不仅是可处理的充分条件，也是必要条件；非层次查询的均匀可靠性是 #P 难的。进一步，作者把该二分法推广到元组概率仅由其关系决定的一类受限可靠性问题，统一了若干特例。
The reliability of a Boolean Conjunctive Query (CQ) over a tuple-independent probabilistic database is the probability that the CQ is satisfied when the tuples of the database are sampled one by one, independently, with their associated probability. For queries without self-joins (repeated relation symbols), the data complexity of this problem is fully characterized by a known dichotomy: reliability can be computed in polynomial time for hierarchical queries, and is #P-hard for non-hierarchical queries. Inspired by this dichotomy, we investigate a fundamental counting problem for CQs without self-joins: how many sets of facts from the input database satisfy the query? This is equivalent to the uniform case of the query reliability problem, where the probability of every tuple is required to be 1/2. Of course, for hierarchical queries, uniform reliability is solvable in polynomial time, like the reliability problem. We show that being hierarchical is also necessary for this tractability (under conventional complexity assumptions). In fact, we establish a generalization of the dichotomy that covers every restricted case of reliability in which the probabilities of tuples are determined by their relation.
@article{paperbot1645,
title = {Uniform Reliability of Self-Join-Free Conjunctive Queries},
author = {Antoine Amarilli and Benny Kimelfeld},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 4},
year = {2022},
doi = {10.46298/lmcs-18(4:3)2022}
}