text: Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing modifications to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.
  @cite_8: It is often desirable to represent in a database, entities whose properties cannot be deterministically classified. The authors develop a data model that includes probabilities associated with the values of the attributes. The notion of missing probabilities is introduced for partially specified probability distributions. This model offers a richer descriptive language allowing the database to more accurately reflect the uncertain real world. Probabilistic analogs to the basic relational operators are defined and their correctness is studied. A set of operators that have no counterpart in conventional relational systems is presented. >
  @cite_29: We study the problem of null values. By this we mean that an attribute is applicable but its value at present is unknown and also that an attribute is applicable but its value is arbitrary. We adopt the view that tuples denote statements of predicate logic about database relations. Then, a null value of the first kind, respectively second kind, corresponds to an existentially quantified variable, respectively universally quantified variable. For instance if r is a database relation without null values and X is a range declaration for r then the tuple (a, ∀,b, ∃) ∈ R is intended to mean “there exists an x ∈ X such that for all y ∈ X: (a,y,b,x) ∈ r”. We extend basic operations of the well-known relational algebra to relations with null values. Using formal notions of correctness and completeness (adapted from predicate logic) we show that our extensions are meaningful and natural. Furthermore we reexamine the generalized join within our framework. Finally we investigate the algebraic structure of the class of relations with null values under a partial ordering which can be interpreted as a kind of logical implication.
  @cite_24: 
  @cite_2: Note: Chapter 6 Reference EPFL-CHAPTER-167070 Record created on 2011-06-22, modified on 2017-05-12
  @cite_16: We discuss, compare and relate some old and some new models for incomplete and probabilistic databases. We characterize the expressive power of c-tables over infinite domains and we introduce a new kind of result, algebraic completion, for studying less expressive models. By viewing probabilistic models as incompleteness models with additional probability information, we define completeness and closure under query languages of general probabilistic database models and we introduce a new such model, probabilistic c-tables, that is shown to be complete and closed under the relational algebra.
  @cite_25: 
  @cite_11: ABSTRACT This paper concerns the semantics of Codd's relational model of data. Formulated are precise conditions that should be satisfied in a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed. These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by using a specified subset Ω of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in Ω are in fact derivable in this system. Two such systems of practical interest are shown. The first, based on the usual Codd's null values, supports projection and selection. The second, based on many different (“marked”) null values or variables allowed to appear in a table, is shown to correctly support projection, positive selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by this system is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. A third system, mainly of theoretical interest, supporting projection, selection, union, join, and renaming, is also discussed. Under a so-called closed world assumption, it can also handle the operator of difference. It is based on a device called a conditional table and is crucial to the proof of the correctness of the second system. All systems considered allow for relational expressions containing arbitrarily many different relation symbols, and no form of the universal relation assumption is required. Categories and Subject Descriptors: H.2.3 [Database Management]: Languages— query languages; H.2.4 [Database Management]: Systems— query processing General Terms: Theory
summary: Because early theoretical work on incomplete data focuses largely on algebras and representation systems (e.g., @cite_29 @cite_11 ), it was only natural to extend this line of thinking to probabilities @cite_8 @cite_25 @cite_2 @cite_16 @cite_24 benjelloun06uldbs . However, this extension is quite difficult since the probabilities in query results must include expressions derived from the confidence values originally embedded in the database. Systems meeting these theoretical conditions must overcome a set of challenges that are often satisfied at the expense of modeling-power or understandability.