  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.
