- For arbitrary factorizations and their order to compute a marginal distribution, there exists a tabled program that accomplishes the same computation in the specified way.

- When the graph is singly connected and evidence e is given, there exists a tabled program DBGr such that OLDT time for ← bn(e) is O(|V|), and hence the time complexity per iteration of the graphical EM algorithm is O( | V | ) as well.
Let G be a Bayesian network defining a joint distribution PG ( x 1 , . . , x N ) and { PG ( X i =
xi | Π i = u i ) | 1 ≤ i ≤ N, xi E val(Xi), ui E val(Πi)} the conditional probabilities associated with G where val ( X i ) is the set of X i 's possible values and val ( Π i ) denotes the set of possible values of the parent nodes Π i as a random vector, respectively. We construct a parameterized logic program that defines the same distribution P G ( x 1 , . . , x N ). Our program DB G = F G ∪ R G is shown in Figure 13.

$F_{G}\ =\ \{\texttt{msw}(\texttt{par}(i,\texttt{u}_{i}),\texttt{once},x_{i})\ \ \ |\ 1\leq i\leq N,\texttt{u}_{i}\in val(\texttt{II}_{i}),\,x_{i}\in val(X_{i})\ \}$  $R_{G}\ =\ \{\texttt{bn}(\texttt{X}_{1},\ldots,\texttt{X}_{N}):-\bigwedge_{i=1}^{N}\texttt{msw}(\texttt{par}(i,\texttt{II}_{i}),\texttt{once},\texttt{X}_{i})\,.\ \}$
Figure 13: Bayesian network program DBG
FG is comprised of msw atoms of the form msw(par(i,u,),once,x,) whose probability is exactly the conditional probability PG(Xi = xi | Πj = ui). When Xi has no parents, ui is the empty list []. R G is a singleton, containing only one clause whose body is a conjunction of msw atoms which corresponds to the product of conditional probabilities. Note that we intentionally identify random variables X 1 , . . , X N with logical variables X 1 , . . , X N for convenience.

Proposition 5.5 DB G denotes the same distributions as G.

(Proof) Let ( x 1 , . . , x N ) be a realization of the random vector ( X 1 , . . , X N ). It holds by construction that

$$P_{DB_{G}}(\texttt{bn}\,(x_{1},\ldots,x_{N})\,)=\prod_{h=1}^{N}P_{\texttt{nm}}(\texttt{msw}\,(\texttt{par}\,(i,\texttt{u}_{i})\,,\texttt{once},x_{i})\,)$$ $$=\prod_{h=1}^{N}P_{G}(X_{i}\,=\,x_{i}\,\mid\,\Pi_{i}\,=\,\texttt{u}_{i}\,)$$ $$=P_{G}(x_{1},\ldots,x_{N}\,).\hskip28.452756ptQ.E.D.$$

In the case of G 1 in Figure 12, the program becomes 57

bn(A,B,C,D,E,F):-msw()msw()msw()msw()
$$\begin{array}{l}{{\tt m s w\,(p a r\,(\ ^{\prime}A\ ^{\prime}\ ,\ []\ )\ ,o n c e\ ,A\ )\ ,}}\\ {{\tt m s w\,(p a r\,(\ ^{\prime}C\ ^{\prime}\ ,\ [A]\ )\ ,o n c e\ ,C\ )\ ,}}\\ {{\tt m s w\,(p a r\,(\ ^{\prime}E\ ^{\prime}\ ,\ [D]\ )\ ,o n c e\ ,E\ )\ ,}}\end{array}$$
msw(par('B',[]),once,B), msw(par('D',[A,B]),once,D),
msw(par('F',[D]),once,F).

57. 'A', 'B', . . are Prolog constants used in place of integers.