Tuple-Independent Representations of Infinite Probabilistic Databases

ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), vol. 51, pp. 1–401

Abstract

Infinite probabilistic databases (PDBs) are a framework of probability distributions over infinitely many different database instances. We systematically study the representability problem for such PDBs by means of tuple-independence and first-order views. Although first-order views over tuple-independent PDBs are not a complete representation system for infinite PDBs, they form a fairly robust class: Adding first-order constraints does not give them additional expressive power, and they cover many relevant special cases such as block-independent disjoint PDBs, and PDBs of bounded instance size. We identify criteria for representability (or non-representability) in this class and explore their limits. In addition, we study the expressive power of fragments of first-order logic over tuple-independent PDBs. In general, for infinite PDBs, the landscape of relative expressive power for various classes of views over PDBs with independence assumptions is much more complex than in the finite setting.

Authors 4

1. Nofar Carmeli

   Centre National de la Recherche Scientifique · Institut national de recherche en sciences et technologies du numérique · Technion – Israel Institute of Technology · Université de Montpellier · Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

   Affiliation as printed

   Technion - Israel Institute of Technology, Haifa, Israel

   Inria, LIRMM, University of Montpellier, CNRS, Montpellier, France

   Technion-Israel Institute of Technology

2. Martin Grohe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Peter Lindner Aachen Logic and Theory of Discrete Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

   Logic and Theory of Discrete Systems, RWTH Aachen University, Aachen, Germany

4. Christoph Standke Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany