algorithm to non-exclusive observations O such that E O P ( O ) ≥ 1 where the uniqueness condition is seemingly destroyed.

Let us see the MAR condition in action with a simple example. Imagine we walk along a road in front of a lawn. We occasionally observe their state such as "the road is dry but the lawn is wet". Assume that the lawn is watered by a sprinkler running probabilistically.

The program DBr1 = Rr1 U Fr1 in Figure 2 describes a sequential process which outputs an observation observed(road(x),lawn(y)) ("the road is x and the lawn is y") where x, y E { vet, dry}.

{ observed(road(X),lawn(Y)):-

$\pm\epsilon$
Rrr l

$$\begin{array}{r c l c r c l}{{F_{\mathbf{r1}}}}&{{=}}&{{}}&{{\{}\;\;\;\mathrm{msw}}}\end{array}$$

msssssse
( A = yes, X = vet, Y = vet
; A = no,  msw(sprinkler,once,B),
( B = on, X = dry, Y = vet
; B = off, X = dry, Y = dry ) ).

n
{ msw(rain,once,yes), msw(rain,once,no),
msw(sprinkler,once,on), msw(sprinkler,once,off) }

## Figure 2: Db ±1

The basic distribution over F x 1 is specified like P F x ( · ) in Subsection 4.1, so we omit it.

msw(rain,once,A) in the program determines whether it rains (A = yes) or not (A = no), whereas msw(sprinkler,once,B) determines whether the sprinkler works fine (B = on)
or not (B = off).  Since for each sampled values of A = a (a E {yes,no}) and B = b
(b E {on, off}), there uniquely exists an observation observed(road(x),lawn(y)) (x,yE
{vet, dry}), there is a many-to-one mapping χ : χ(a,b) = ⟨ x, y ⟩ . In other words, we can apply the EM algorithm to the observations observed(road(x),lawn(y)) (x,y E
{vet, dry}). What would happen if we observe exclusively either a state of the road or that of the lawn? Logically, this means we observe 3yobserved(road(x),lawn(y)) or 3x observed(road(x),lawn(y)). Apparently the uniqueness condition is not met, because 3y observed(road(wet),lawn(y)) and 3x observed(road(x),lawn(wet)) are compatible (they are true when it rains). Despite the non-exclusiveness of the observations, we can still apply the EM algorithm to them under the MAR condition, which in this case translates into that we observe either the lawn or the road randomly regardless of their state.

We now briefly check other conditions. Basically they can be relaxed at the cost of increased computation. Without the exclusiveness condition for instance, we would need an addition al process of transforming the support set ψ DB ( G ) for a goal G into a set of exclusive explanations. For instance, if G has explanations {msw(a,n,v), msw(b,m,w)}, we have to transform it into {msw(a,n,v), -msw(a,n,v) A msw(b,m,w)} and so on 23 Clearly, this transformation is exponential in the number of msw atoms and efficiency concern leads to assuming the exclusiveness condition.

The finite support condition is in practice equivalent to the condition that the SLD tree for ← G is finite. So relaxing this condition might induce infinite computation.