Function **FindMatch(**Os, ci)

1 Find the class ct **which is equivalent to** ci in Os; 2 if ct is not found in Os **then**
3 **Report Mismatch at** ci; 4 **exit;**
5 end 6 **return** ci;

## 4.2 Working Example

We present a working example to describe how the algorithm works. Consider the protocol shown in Figure 1. We elaborate the steps of applying Algorithm 1 with respect **to the fragments of the client**
and server ontologies shown in Figure 3 and Figure 4 respectively. These fragments are taken from the benchmark provided by [10]. The benchmark has one reference ontology and four other real ontologies and the domain of these ontologies is bibliographic references. We have used the reference ontology as the server ontology and another real ontology named INRIA as the client ontology. We have used a pictorial representation which is similar to entity-relationship diagram to show the fragments of the ontologies. The classes are represented by the rounded rectangles and the ovals represent the properties of a particular class. The class hierarchy is shown using arrows, that is a sub class is connected to its super class by an arrow which is directed towards the sub class. The **properties that belong to a** particular class are connected to the rounded rectangle corresponding to that class through a line. Step-1: While applying Algorithm 1 to the server ontology, the individual class 'Manual' **is searched**
and since the search is successful, it is checked that the attributes that are associated with class 'Manual' **in the query in the protocol are actually answerable by the server and this check turns**
out to be successful for the ontologies that are presented here.

Step-2: The next query uses the class 'Book'**. Algorithm 1 performs the consistency checking in the**
way that is similar to the previous query and the check is successful.

Step-3: The third query uses a specialization sequence 'Book.Proceedings'**. Algorithm 1 searches for**
the 'Book' class in the server ontology and then checks whether 'Proceedings' is a sub class of **'Book'** in the server ontology. Algorithm 1 reports a failure since in the server ontology **'Proceedings'** is not a sub class of **'Book'**.

## 4.3 Proof Of Correctness

Theorem 1. **[Soundness] The mismatches returned by Algorithm 1 are correct.**
Proof. **Algorithm 1 reports mismatch in three cases. We observe each of the cases as follows.**
Mismatch in individual class: If Algorithm 1 does not find a matching class c **which is used in a**
query, a conflict is reported. Since the class is not recognized by the server, it is not possible for the server to answer the query. Therefore the outcome of the algorithm is correct.

Mismatch in specialization sequence: Consider a specialization sequence σ = hc1.c2. **· · ·** .cki in a query q on which Algorithm 1 returns a mismatch. We prove the correctness **of the consistency** checking by induction on the length k of σ.

Basis(k = 1): **In this case there is only one class in the specialization sequence and this case falls**
under the case of mismatch in individual classes.

Inductive Step: **Suppose Algorithm 1 returns the mismatch correctly for specialization sequences**
having length k. We prove that Algorithm 1 reports the conflicts correctly for the **specialization** sequences having length k **+ 1. There can be two possible cases.**
34