Overview - Probabilistic Databases - page 14

1. OVERVIEW
Around the same time, ProbView, a system by Lakshmanan et al. [ 1997 ], took a different approach
by relaxing the probabilistic semantics in order to ensure efficient query evaluation; the idea of
relaxing the probabilistic semantics can also be found in [ Dey and Sarkar , 1996 ].
The possible worlds model for logics of knowledge and belief was originally proposed by
Hintikka [ 1962 ], and it is now most commonly formulated in a normal modal logic using the
techniques developed by Kripke [ 1963 ]. It is used extensively in logics of knowledge [ Fagin et al. ,
1995 ].
1.4.0.2 Incomplete Databases
Much more work has been done on databases that have a notion of uncertainty but not probability.
Uncertainty in the form of NULL values is part of the SQL standard and supported by most database
management systems. In an even stronger form of labeled nulls that represent uncertain values that
have identity and can be joined on, they were already part of Codd's original definition of the relational
model. The seminal research work on databases with uncertainty is by Imieli nski and Lipski [ 1984 ]
who introduced the notion of conditional tables and strong representation systems, which will both
be discussed in more detail in this topic. The expressiveness of various uncertainty models and the
complexity of query evaluation has been studied in a sequence of works, e.g., [ Abiteboul et al. , 1991 ,
Grahne , 1984 , 1991 , Libkin and Wong , 1996 , Olteanu et al. , 2008 ]. A recent paper [ Koch , 2008b ]
shows that a natural query algebra for uncertain databases, whose probabilistic extension can also
be observed as the core of the query languages of the Trio and MayBMS systems, has exactly the
expressive power of second-order logic. This is a somewhat reassuring fact, because second-order
logic extends first-order-logic, the foundation of relational database languages, by precisely the power
to “guess relations” and thus reason about possible worlds and what-if scenarios, which is the essence
of uncertain database queries.
1.4.0.3 Probabilistic Graphical Models
As explained earlier, this topic is not about probabilistic graphical models but instead focuses on the
database approach to managing probabilistic databases, yet GMs do inform the research in proba-
bilistic databases significantly. There is a vast amount of research on inference in graphical models by
a variety of communities, including researchers in Artificial Intelligence, (bio)statistics, information
theory, and others [ Aji and McEliece , 2000 ]; in fact, the volume of work on graphical models sig-
nificantly exceeds that of research on probabilistic databases. We refer the reader to several topics by
Pearl [ 1989 ], Gilks et al. [ 1995 ], Jordan [ 1998 ], Darwiche [ 2009 ], and Koller and Friedman [ 2009 ].
The connection between probabilistic databases and graphical models was first described and studied
by Sen and Deshpande [ 2007 ]. The concurrent work by Antova et al. [ 2007c ] uses a model of prob-
abilistic databases that can be at once seen as flat Bayesian Networks and as a product decomposition
of a universal relation representation [ Ullman , 1990 ] of the set of possible worlds representing the
probability space.