Paper Info
Title
On a theory of probabilistic deductive databases
Abstract
We propose a framework for modeling uncertainty where both belief and doubt can be given independent, first-class status. We adopt probability theory as the mathematical formalism for manipulating uncertainty. An agent can express the uncertainty in her knowledge about a piece of information in the form of a confidence level, consisting of a pair of intervals of probability, one for each of her belief and doubt. The space of confidence levels naturally leads to the notion of a trilattice, similar in spirit to Fitting's bilattices. Intuitively, the points in such a trilattice can be ordered according to truth, information, or precision. We develop a framework for probabilistic deductive databases by associating confidence levels with the facts and rules of a classical deductive database. While the trilattice structure offers a variety of choices for defining the semantics of probabilistic deductive databases, our choice of semantics is based on the truth-ordering, which we find to be closest to the classical framework for deductive databases. In addition to proposing a declarative semantics based on valuations and an equivalent semantics based on fixpoint theory, we also propose a proof procedure and prove it sound and complete. We show that while classical Datalog query programs have a polynomial time data complexity, certain query programs in the probabilistic deductive database framework do not even terminate on some input databases. We identify a large natural class of query programs of practical interest in our framework, and show that programs in this class possess polynomial time data complexity, i.e. not only do they terminate on every input database, they are guaranteed to do so in a number of steps polynomial in the input database size.
Year
Venue
Keywords
2003
Theory and Practice of Logic Programming
deductive databases,confidence level,classical framework,polynomial time data complexity,classical deductive database,probabilistic deductive database framework,input database,probabilistic deductive databases,declarative semantics,equivalent semantics,probability theory,polynomial time
DocType
Volume
Citations 
Journal
cs.DB/0312
38
PageRank 
References 
Authors
1.53
28
2
Name
Order
Citations
PageRank
Laks V. S. Lakshmanan16216696.78
Fereidoon Sadri2846283.70