论文标题
无限概率数据库的元组无关表示
Tuple-Independent Representations of Infinite Probabilistic Databases
论文作者
论文摘要
概率数据库（PDB）是数据库实例的概率空间。它们为处理数据库中的不确定性提供了一个框架，因为数据集成，嘈杂的数据，来自不可靠来源的数据或随机过程。现有的大多数理论文献研究了有限的，元组独立的PDB（TI-PDB），其中元素的发生是独立事件。直到最近，Grohe和Lindner（Pods '19）才引入了超出有限域假设的PDB的独立性假设。在有限的情况下，讨论Ti-PDB的理论属性的主要论点是，它们可用于通过视图来表示任何有限的PDB。一旦元素数量无限，情况就不再如此。在本文中，我们从TI-PDB和相关的块独立脱节PDB方面系统地研究了无限PDB的代表性。 中心问题是哪些无限PDB可以表示为元组独立的PDB的一阶视图。我们为PDB的表示性提供了必要的条件，并就PDB的概率分布提供了足够的标准。有了各种示例，我们探讨了标准的限制。我们表明，一阶性能的条件在表达性方面没有额外的功能。最后，我们讨论了（非）表示性的纯粹逻辑和算术原因之间的关系。
Probabilistic databases (PDBs) are probability spaces over database instances. They provide a framework for handling uncertainty in databases, as occurs due to data integration, noisy data, data from unreliable sources or randomized processes. Most of the existing theory literature investigated finite, tuple-independent PDBs (TI-PDBs) where the occurrences of tuples are independent events. Only recently, Grohe and Lindner (PODS '19) introduced independence assumptions for PDBs beyond the finite domain assumption. In the finite, a major argument for discussing the theoretical properties of TI-PDBs is that they can be used to represent any finite PDB via views. This is no longer the case once the number of tuples is countably infinite. In this paper, we systematically study the representability of infinite PDBs in terms of TI-PDBs and the related block-independent disjoint PDBs. The central question is which infinite PDBs are representable as first-order views over tuple-independent PDBs. We give a necessary condition for the representability of PDBs and provide a sufficient criterion for representability in terms of the probability distribution of a PDB. With various examples, we explore the limits of our criteria. We show that conditioning on first order properties yields no additional power in terms of expressivity. Finally, we discuss the relation between purely logical and arithmetic reasons for (non-)representability.
