A BKB is represented as a directed graph. There are two types of nodes in the graph: I-nodes(instance nodes) and S-nodes(support nodes). The I-nodes represent possible states of a random variable, one I-node per state. The S-nodes represent conditional probabilities. The arcs that connect the S-nodes and I-nodes represent the conditional dependencies between random variables.

Figure 1 is an example of a simple Bayesian Knowledge Base with three random variables, each having two states. Each RV state (represented by a large unfilled circle) is associated with a single I-node. Each support node is represented by a small filled circle. S-nodes connect the I-nodes. A given I-node must have at least one S-node supporting that I-node. An S-node may also have one or more I-nodes in its tail, with directed arcs to the S-node. The set of I-nodes which are members of an S-node's tail are referred to as the S-node's tail condition(TC). I-nodes A=1 and B=1 comprise the tail condition of the S-node Sc1. If an S-node has no tail condition it is a root node; Sa1,Sa2,Sb1 and Sb2 are root nodes.

Figure 1: A simple BKB. We can interpret as If ``A=1'' and ``B=1'' then ``C=1'' with probability P(C=1|A=1,B=1)=0.5

S-nodes contain the conditional probability that the supported I-node will become active when all members of its tail condition are active. An I-node is considered active when one of its supporting S-nodes is active. The random variable C will be in state 1 if RV A is in state 1 and RV B is in state 1 (the tail condition of Sc1 has been met) with probability Sc1 = 0.5.

BKBs and Bayesian networks(BNs) are methods of representing uncertainty in knowledge. BKBs differ from BNs because they do not require full specification of all probabilistic relationships between variables as well as various forms of cyclical knowledge[1, 7, 6] . Specifically, BKBs allow incompleteness in the knowledge they represent because they do not require denotation of random variable relationships which are unknown. The ability to represent incomplete knowledge is only part of the solution. We also need a method to inference over incompleteness.