Typically, probabilistic databases (PDBs) are probability distributions over the subsets of a finite set of facts. However, many practical implementations of relational databases use a bag semantics that allows multiple copies of a fact. As facts may appear arbitrarily often, extending PDBs to a bag semantics naturally leads to infinite PDBs, the mathematical framework of which as only been introduced recently by Grohe and Lindner (PODS 2019, ICDT 2020). In this paper, we study the problem of query evaluation over PDBs with bag semantics (bag PDBs). We focus on tuple-independent bag PDBs, which means that the multiplicities of different facts are independent. In the set-based setting, the complexity of probabilistic query evaluation is well-understood for unions of conjunctive queries (UCQs): it is either in polynomial time, or #P-hard (Dalvi and Suciu, JACM 2012). The setting with bag semantics differs substantially. As PDBs are no longer finite, we need feasible representations. Moreover, the answer to a Boolean query is a probability distribution over numbers, rather than a single probability. This yields different reasonable definitions of the query evaluation problem. First, we discuss computing the expectation and variance of query answers. Surprisingly, under mild assumptions on the representation, both problems are solvable in polynomial time for all UCQs. Second, we investigate the problem of computing the probability that the answer is at most k, where k is a parameter. While key arguments from prior work do not carry over to our setting, we show that the original dichotomy for Boolean self-join free CQs persists for most representations. Still, there are representation systems where the problem is always solvable in polynomial time.
翻译:通常情况下, 概率数据库( PDBB) 是一组有限事实的子集的概率分布。 但是, 许多关联数据库的实际实施都使用包装的语义学, 允许多个事实的复制。 由于事实的出现经常是任意的, 将 PDB 扩展为包装的语义学, 自然导致无限的 PDB, 其数学框架( 刚由 Grohe 和 Lindner ( PODS 2019, ICDT 2020) 引入 。 在本文中, 我们用包装语义( bag PDBs) 来研究 PDB 的查询评估问题。 但是, 我们用袋式语义解答问题( bag PBag PDBs ) 。 我们的语义学参数不是持续的时间, 不同事实的多变异性分析评估的复杂性在时间里, 我们的概率分析中, 我们的概率分析总是会持续到不同的时间。 我们的概率分析是时间, 我们的概率分析总是会持续到不同的计算。