Independence allows us to use the following standard identities:

P(A ∧ B) = P(A) × P(B)
$$\begin{array}{c}{{P(A\lor B)=1-(1-P(A))(1-P(B))}}\\ {{P(\forall x:\varphi(x))=\prod_{x}P(\varphi(x))}}\\ {{P(\exists x:\varphi(x))=1-\prod_{x}(1-P(\varphi(x)))}}\\ {{\mathbb{E}(\#x:\varphi(x))=\sum_{x}P(\varphi(x))}}\end{array}$$
$$\left(\begin{array}{c c c}{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\end{array}\right)$$
Then, a rule ϕ =⇒ ψ is translated as a probability assignment P(ψ**) :=** P(ϕ)
and ϕ **is recursively decomposed using these identities. Following the example**
of Equation (3), we derive the value of Pr2(x ≡ x
′
**) in Equation (4) as follows:**

$$\prod_{r,y}(1)$$
$=\;\frac{1}{2}$  . 
$$\begin{array}{r l}{\prod_{r\mid}}\\ {\prod_{r\mid}}\end{array}$$

1 − P(∃r, y r(*x, y*) ∧ (∀y
′
r(x
′
, y′) ⇒ y 6≡ y
′
) ∧ fun(r**) is high)**
=Qr,y(1 − P(r(*x, y*)) ×Qy
′ (1 − P(r(x
′
, y′) ∧ y ≡ y
′
) × fun(r**)) (13)**
=Qr(x,y)
(1 − fun(r)Qr(x′,y′)
(1 − P(y ≡ y
′
))).

since r(*x, y***) and** r(x
′
, y′**) are crisp, non-probabilistic facts.**
Similarly, when we need to estimate a number such as "\#x : ϕ(x**)", we**
compute E(\#x : ϕ(x**)) using the aforementioned identities.**

## C Equivalence Of Sets

We compare two instances for equivalence by comparing every **statement about**
the first instance with every statement about the second instance (if they have the same relation). This entails a quadratic number of comparisons. For example, if an actor x acted in the movies y1, y2, y3**, and an actor** x
′ **acted in**
the movies y
′

1
, y
′

2
, y
′

3
, then we will compare every statement actedIn(*x, y*i**) with**
every statement *actedIn*(x
′
, y′j
). Alternatively, one could think of the target values as a set and of the relation as a function, as in actedIn(x, {y1, y2, y3})
and *actedIn*(x
′
, {y
′

1
, y′2
, y′3
}**). Then, one would have to compare only two sets**
instead of a quadratic number of statements. However, all elements of one set are potentially equivalent to all elements of the other set. **Thus, one would still** need a quadratic number of comparisons.

One could generalize a set equivalence measure (such as the Jaccard index) to sets with probabilistic equivalences. However, one would still need to take into account the functionality of the relations: If two people share an e-mail address
(high inverse functionality), they are almost certainly equivalent. By contrast, if two people share the city they live in, they are not necessarily equivalent. To unify two instances, it is sufficient that they share the value **of one highly inverse**
functional relation. Conversely, if two people have a different birth date, they are certainly different. By contrast, if they like two different books, they could still be equivalent (and like both books). Our model takes this into account. Thus, our formulas can be seen as a comparison measure for sets with **probabilistic** equivalences, which takes into account the functionalities.