We present a theoretical basis for supporting subjective and conditional probabilities in
deductive databases. We design a language that allows a user greater expressive power than
classical logic programming. In particular, a user can express the fact that A is possible
(i.e. A has non-zero probability), B is possible, but A and B as a whole is impossible.
A user can also freely specify probability annotations that may contain variables. The focus
of this paper is to study the semantics of programs written in such a language in relation
to probability theory. Our model theory which is founded on the classical one captures the
uncertainty described in a probabilistic program at the level of Herbrand interpretations.
Furthermore, we develop a fixpoint theory and a proof procedure for such programs and
present soundness and completeness results. Finally we characterize the relationships
between probability theory and the fixpoint, model, and proof theory of our programs.