probability P(x ≡ x
′
) to be large if r **is highly inverse functional, and if there**
are y ≡ y
′ with r(*x, y*), r(x
′
, y′) (if, say, x and x
′
**share an e-mail address). This**
can be written pseudo-formally as:
∃r, y, y′: r(*x, y*) ∧ r(x
′
, y′) ∧ y ≡ y
′ ∧ fun−1(r**) is high =**⇒ x ≡ x
′

We transform this logical rule into a probability assignment for x ≡ x
′
**, assuming**

independence and using the formalization described in Appendix B, obtaining thus:
$$P_{1}(x\equiv x^{\prime}):=1-\prod_{r(x,y),r(x^{\prime},y^{\prime})}(1-f u n^{-1}(r)\times P(y\equiv y^{\prime}))$$
**)) (2)**
In other words, as soon as there is one relation r with fun−1(r**) = 1 and with**
r(*x, y*), r(x
′
, y′**), and** P(y ≡ y
′
**) = 1, it follows that** P1(x ≡ x
′
**) = 1. We discuss**
a design alternative in Appendix C.

Note that the probability of x ≡ x
′ **depends recursively on the probabilities of**
other equivalences. These other equivalences may hold either between instances or between literals. We discuss the probability of equivalence between two literals in Section 5. Obviously, we set P(x ≡ x**) := 1 for all literals and**
instances x.

Equation (2) considers only positive evidence for an equality. To consider also evidence against an equality, we can use the following modification. We want the probability P(x ≡ x
′
**) to be small, if there is a highly functional**
relation r with r(*x, y***) and if** y 6≡ y
′
**for all** y
′ **with** r(x
′
, y′**). Pseudo-formally,**
this can be written as
∃r, y : r(*x, y*) ∧ (∀y
′
: r(x
′
, y′) ⇒ y 6≡ y
′
) ∧ fun(r) is high =⇒ x 6≡ x. (3)
This can be modeled as

$$P_{2}(x\equiv x^{\prime}):=\prod_{r(x,y)}\left(1-f u n(r)\prod_{r(x^{\prime},y^{\prime})}(1-P(y\equiv y^{\prime}))\right)$$

As soon as there is one relation r with fun(r) = 1 and with r(*x, y*), r(x
′
, y′),
and P(y ≡ y
′
**) = 0, it follows that** P2(x ≡ x
′
**) = 0. We combine these two**
desiderata by multiplying the two probability estimates:

$$\left({4}\right)$$

P3(x ≡ x
′
**) :=** P1(x ≡ x
′
) × P2(x ≡ x
′
**) (5)**
In the experiments, we found that Equation (2) suffices in practice. However, we discuss scenarios where Equation (5) can be useful in Section 6.

## 4.2 Subrelations

The formulas we have just established estimate the equivalence between two entities that reside in two different ontologies, if there is a relation r **that is**
common to the ontologies. It is also a goal to discover whether a relation r of one ontology is equivalent to a relation r
′ **of another ontology. More generally,**
we would like to find out whether r **is a sub-relation of** r
′
**, written** r ⊆ r
′
.

Intuitively, the probability P(r ⊆ r
′
**) is proportional to the number of pairs in** r that are also pairs in r
′
:

$$P(r\subseteq r^{\prime}):={\frac{\#x,y:r(x,y)\wedge r^{\prime}(x,y)}{\#x,y:r(x,y)}}$$
$$(6)$$

′
#x, y : r(*x, y*)(6)