On A Theory of Probabilistic Deductive Databases

Details On A Theory of Probabilistic Deductive Databases On A Theory of Probabilistic Deductive Databases

2003-12-18

arxiv.org/abs/cs/0312043v1

Computer Science

Databases

38 pages, 0 figures

Scientific paper

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, thep oints 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.

Affiliated with

Also associated with

No associations

Rating

On A Theory of Probabilistic Deductive Databases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On A Theory of Probabilistic Deductive Databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On A Theory of Probabilistic Deductive Databases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-198594