U3. Then we visit X's children, Vi and V2. For a topmost node U3 in the original graph, we add clause (26).

$$t b n\left(U_{1}\right)\ :-\ \ m s w\left(p a r(\ 'U_{1}\ ,\ \Box\ ),o n c e,U_{1}\right),\,c a l l_{U_{1}}X\left(U_{1}\right)\ .$$
$$(\,24\,)$$
call_U_1_X(U_1) := val_U_2(U_2), call_X_U_2(U_2), val_U_3(U_3), call_X_U_3(U_3), msw(par('X',[U_1,U_2,U_3]),once,X), call_X_V_1(X), call_X_V_2(X).  
$$\left(25\right)$$
$$\tt{c a l l\_}X_{\_}U_{3}(U_{3})\quad:-\quad\tt{m s w}\left(p a r(\,'U_{3}\,',\,\Box\,)\,\,,o n c e\,,U_{3}\right)\,.$$
$$\left(26\right)$$

Let DB Gr be the final program containing clauses like (24), (25) and (26). Apparently DB G r can be constructed in time linear in the number of nodes in the network. Also note that successive unfolding (Tamaki & Sato, 1984) of atoms of the form call_...( ) in the clause bodies that starts from (24) yields a program DBC similar to the one in Figure 13 which contains msw atoms but no call_...( )'s. As DB Gr and DB'c define the same distribution, 58 it can be proved from Proposition 5.5 that P G ( u ) = P DB c ( bn( u )) =
PDB cr (tbn(u)) holds (details omitted). By the way, in Figure 15 we assume the construction starts from the topmost node U 1 where the evidence u is given, but this is not necessary. Suppose we change to start from the inner node X. In that case, we replace clause (24)
with call_X_U1(U1) :- msw(par('U1',[]),once,U1) just like (26). At the same time we replace the head of clause (25) with tbn() and add a goal call_X_U1(u) to the body and so on. For the changed program DB" Gr, it is rather straightforward to prove that Ppp"~r(tbn()) = PG(u) holds. It is true that the construction of the tabled program DB G - shown here is very crude and there is a lot of room for optimization, but it suffices to show that a parameterized logic program for a singly connected Bayesian network runs in O( | V |) time where V is the set of nodes.

To estimate time complexity of OLDT search w.r.t. DB Gr , we declare tbn and every predicate of the form call_..(~) as table predicate and verify the five conditions on the applicability of the graphical EM algorithm (details omitted). We now estimate the time complexity of OLDT search for the goal ← tbn(u) w.r.t. DB GT.59 We notice that calls occur according to the pre-order scan (parents - the node - children) of the tree G r , and calls to call Y_X() occur val (Y) times. Each call to call Y_X( ) invokes calls to the rest of nodes, X's parents and X's children in the graph G' except the caller node, with diffrent set of variable instantiations, but from the second call on, every call only refers to solutions stored in the solution table in O (1) time. Thus, the number of added computation steps in