This corresponds to some form of a domain-restricted unique **name assumption.**
Therefore, our algorithm considers only equivalence between entities from different ontologies. Strictly speaking, the functionality of a relation (Equation (1))
depends recursively on the equivalence of instances. If, e.g., every citizen lives in two countries, then the functionality of *livesIn* is 12
. If our algorithm unifies the two countries, then the functionality of *livesIn* **jumps to 1. However, since**
we assume that there are no equivalent entities within one ontology, we compute the functionalities of the relations within each ontology upfront.

We implemented a fixpoint computation for Equations (9) and (10). First, we compute the probabilities of equivalences of instances. **Then, we compute**
the probabilities for sub-relationships. These two steps are iterated until convergence. In a last step, the equivalences between classes are computed by Equation
(12) from the final assignment. To bootstrap the algorithm in **the very first step,**
we set P(r ⊆ r
′
) = θ for all pairs of relations *r, r*′ **of different ontologies. We**
chose θ = 0.**10. The second round uses the computed values for** P(r ⊆ r
′
**) and**
no longer θ**. We have not yet succeeded in proving a theoretical condition under**
which the iteration of Equations (9) and (10) reaches a fixpoint. In practice, we iterate until the entity pairs under the maximal assignments change no more
(which is what we call convergence). In our experiments, this state was always reached after a few iterations. We note that one could always **enforce convergence of such iterations by introducing a progressively increasing dampening**
factor. Our model changes the probabilities of two resources being equal - but never the probability that a certain statement holds. All statements in both ontologies remain valid. This is possible because an RDFS ontology cannot be made inconsistent by equating resources, but this would not **be the case any** more for richer ontology languages.

## 5.2 Optimization

The equivalence of instances (Equation (10)) can be computed in different ways.

In the most naive setting, the equivalence is computed for each pair of instances.

This would result in a runtime of O(n 2m), where n **is the number of instances**
and m **is the average number of statements in which an instance occurs (a typical**
value for m **is 20). This implementation took weeks to run one iteration.** We overcame this difficulty as follows.

First, we optimize the computation of Equation (10). For each instance x in the first ontology, we traverse all statements r(*x, y***) in which this instance**
appears as first argument. (Remember that we assume that the ontology contains all inverse statements as well.) For each statement r(*x, y***), we consider**
the second argument y**, and all instances** y
′
**that the second argument is known**
to be equal to ({y
′
: P(y ≡ y
′
) > 0}**). For each of these equivalent instances**
y
′
**, we consider again all statements** r(x
′
, y′) and update the equality of x and x
′
. This results in a runtime of O(nm2e), where e **is the average number of**
equivalent instances per instance (typically around 10). Equations (9) and (12) are optimized in a similar fashion.

Generally speaking, our model distinguishes *true* **equivalences (**P(x ≡ x
′
) >
0) from *false* **equivalences (**P(x ≡ x
′
) = 0) and *unknown* **equivalences (**P(x ≡ x
′
)
not yet computed). Unknown quantities are simply omitted in **the sums and** products of the equations. Interestingly, most equations contain a probability P(x ≡ x
′
**) only in the form** Q(1 − P(x ≡ x
′
**)). This means that the formula**