Introduction and Problem Description

Ontology matching and alignment based on statistical methods is a relatively developed field, with yearly competitions since 2004 comparing the various strengths and weaknesses of existing algorithms. 5 In this paper, we aim at exploring the degrees to which statistical alignment may lead to inconsistency in the merged ontologies. More precisely, we aim at investigating the effects, both theoretically and practically, of connected alignment, i.e. aligning several ontologies that match (non-trivially) pairwise. Our general approach is to treat large repositories of ontologies (in the order of hundreds of ontologies) as our starting point to perform pairwise matching in order to obtain an interlinked network of ontologies. Formally, such networks are captured by the notion of a hyperontology [6].

Our work in progress is intended to answer questions such as the following:

Assuming pairwise alignments are consistent, how, and when, can we align further ontologies (in various orders) before we drift into inconsistency? In particular, how, and when, can we reduce the question of consistency of aligned ontologies and satisfiability of matched concepts to the consistency of aligned sub-ontologies (i.e. modules generated by the matched sub-signatures)?

We here set up the theoretical background and necessary engineering environment to give meaningful answers to such questions. In our related paper [9], we have studied techniques of information hiding to support the visualisation of the linkage structure and to allow a user to explore the complex networks resulting from pairwise matching on large sets of ontologies. We here focus on the last question mentioned above, namely how to reduce the consistency problem in an aligned network of ontologies to the consistency of merged modules generated by respective alignments, and the corresponding interoperability problem between matching, modularity, and structuring tools. We also study the effects of matching ontologies in different orders by looking at some specific examples.

Synonymy and Alignment as Colimit Computation. An essential part of the matching and alignment process is to relate and identify signature elements from different ontologies (possibly formulated in different ontology languages). Formally, this is captured by the notion of a signature morphism. 6 In the case of OWL ontologies, these are type-preserving symbol mappings of the form σ : Sig(O 1 ) → Sig(O 2 ), i.e. mapping the signature of O 1 (= Sig(O 1 )) to that of O 2 , i.e. concepts to concepts, individuals to individuals, and roles to roles. 7 For a fixed ontology language, a signature morphism straightforwardly induces a sentence translation map.

V-Alignments [13] abstractly capture the alignment process for synonymous signature elements. Given ontologies O 1 and O 2 , an interface

(for O 1 , O 2 ) Σ, σ 1 : Σ −→ Sig(O 1 ), σ 2 : Σ −→ Sig(O 2 )

specifies that (using informal but suggestive notation) concepts σ 1 (c) in O 1 and σ 2 (c) in O 2 are identified for each concept c in Σ, regardless of whether the concepts have the same name or not, and concepts in O 1 \ σ(Σ 1 ) and O 2 \ σ(Σ 2 ) are kept distinct, again regardless of whether they have the same name or not.

The resulting ontology O is not given a priori, but rather it is computed from the aligned ontologies via the interface. This computation is a pushout in the sense of category theory, which in this case is just a disjoint union with identification of specific parts (namely those given through Σ, σ 1 , σ 2 ).

V-alignments can deal with basic alignment problems such as synonymy (identifying different symbols with the same meaning) and homonymy (separating (accidentally) identical symbols with different meaning)-see Fig. 1.

Example 1. In Fig. 1, the interface Σ, σ 1 , σ 2 specifies that the two instances of the concept Woman as well as Person and Human are to be identified. This yields two concepts Woman and Human_Being in the push-out ontology O obtained along the dashed arrows. It also determines that the two instances of Bank are to be understood as homonyms, and thus generates two new distinct concepts.

Notion such as polysemy, however, are typically understood to relate terms that have a different, but related meaning, and can thus not be dealt with by simply identifying symbols or keeping them apart. 8 Similarly, [13] raise the criticism that V-Alignments do not cover the case where a concept Woman in O 1 is aligned with a concept Person in O 2 : here, the merged ontology should turn Woman into a subconcept of Person. Whilst this is not directly possible with pushouts, we are here only interested in matching synonyms across a network of ontologies, and for this purpose, V-alignments (and their compositions) are sufficient. Studying more complex alignment operations we leave for future work. We next turn to the problem of aligning several ontologies at once.

Consistency and Chinese Whispers. The game of Chinese Whispers9 is played as follows: n persons are arranged in a certain (typically circular) order such that for each person P i there is a j such that P i exchanges a message with P j . The point of the game is to observe the distortion of the message as it travels from P 1 along the communication channel. We here are interested in the effects of playing Chinese Whispers with ontologies, where the pairwise matching replaces the transmission of a message, i.e. the messages being exchanged are of the form: "O i and O j agree that concept C of O i is synonymous with concept D of O j ".

We make the following idealisations concerning 'matching' a) we assume that in pairwise matching the order does not matter, i.e. matching O 1 with O 2 yields the same colimit ontology (i.e. alignment) as matching O 2 with O 1 10 ; b) matching algorithms are 'not transitive', i.e., matching O 1 , O 2 and O 2 , O 3 and computing the colimit yields, in general, a different result than matching and aligning O 1 , O 3 , 11 c) we assume that we do not match ontologies with themselves. 12 matching pairs. Playing chinese whispers on R with k ≤ N players now means to pick a connected subgraph of the hyperontology graph (to ensure that each ontology 'talks' to at least one other), which we call a matching configuration . Note that, by assumption, matching configurations contain no loops (i.e. reflexive vertices), are undirected (because of the assumed symmetry of the matching results), and contain at most one edge between two vertices. Therefore, matching configurations are connected simple graphs. For what kinds (or shapes) of matching configurations and exchanged matching results does the consistency of the input ontologies propagate to the merge (colimit) of the matching configuration?

k = 3 k = 2

We will give some partial answers to this problem in Sec. 2 by showing that the consistency of an aligned matching configuration is reducible to the consistency of the alignment of 'reasonably' large modules talking only about the matched signatures. In Sec. 3, we will discuss in detail an alignment of three ontologies involving the Dolce ontology, with pairwise consistent alignments, but an overall inconsistent one. Moreover, in Sec. 4, we will describe how the results of a matcher comparing ontologies O 1 and O 2 (and giving rise to a V-alignment) can be rewritten into a structured ontology for further processing with our tool Hets introduced below, and describe the workflow employing standard ontology matching and reasoning tools. Finally, Sec. 5 describes related and future work.

In the following, we will make precise what we mean by a module and define the notion of conservativity. We start with some auxiliary notions. Let Σ be a signature containing concept names and roles. Let Sen(Σ) be the set of sentences formulated using the symbols in Σ in some language. An ontology O in signature Σ is then simply a subset of Sen(Σ). The sentences of course depend on the language the ontologies under consideration are formulated in, e.g. OWL or some fragment thereof.

We continue with introducing a general notion of a module in the sense that a module of an ontology is not restricted to be a subset of the ontology. It is crucial, however, that the module says everything (expressible in its signature) that is said by the ontology itself (i.e. the ontology is required to be a conservative extension of the module)-see Fig. 3 .

subset of axioms translation along signature morphism

σ : T 1 −→ T 2 T T 1 T 2

Fig. 3. Modules as subsets vs. modules as image under translation.

Definition 1. A theory morphism σ : O 1 −→ O 2 is consequence-theoretically con- servative, if O 2 does not entail anything new w.r.t. O 1 , formally, O 2 |= σ(ϕ) implies O 1 |= ϕ. Moreover, σ : O 1 −→ O 2 is model-theoretically conservative, if any O 1 -model M 1 has a σ-expansion to O 2 , i.e. a O 2 -model M 2 with M 2 | σ = M 1 .

Here, |= as usual denotes logical consequence, whereas _| σ denotes model reduct for a signature morphism σ :

Σ 1 → Σ 2 , i.e. for a Σ 2 -model M 2 , M 2 | σ is a Σ 1 -

model that interprets a symbol by first translating it along σ and then interpreting it using M 2 .

It is easy to show that conservative theory morphisms compose. Moreover, the notion of model-theoretic conservativity is stronger than consequence-theoretic conservativity. To be precise, the former implies the latter, but not vice versa [7]. The two notions coincide if we define consequence-theoretic conservativity using Σ-theories that contain consequences φ ∈ Sen(Σ) formulated in second-order logic.

The computational complexity of deciding conservativity appears to be rather daunting even if the ontologies are formulated in weak logics. For instance, for ontologies formulated in the light-weight Description Logic EL, deciding consequence-theoretic conservativity is ExpTime-complete, and model-theoretic conservativity is undecidable. The former problem also becomes undecidable when adding nominals to ALCIQ, for which it is still 2-ExpTime-complete [8]. This suggests that, for practical purposes and applications, we often have to live with approximations of these notions, more precisely with sufficient (syntactic) conditions for conservativity that allow to construct non-minimal modules. Indeed, the notion of an ontology module of an ontology O has been defined as any "subontology O such that O is a conservative extension of O " [1]. For a Σ-module generator Π, the set

Π( O, Σ ) is called a Σ-module for O. Π( O, Σ ) is called Σ-covering for O if: O is a model-theoretic Σ-conservative extension of Π( O, Σ ).

The idea to use (conservative) module generators is to massively reduce the size of a colimit ontology to a merge of modules generated by the matched signatures and preserving the semantics completely. This means that we can check the satisfiability of our matched concepts (and the consistency of the overall merged ontology) already in a rather small fragment of the overall ontology. Indeed, it is not hard to construct (or find) cases where ontologies have a moderate semantic overlap, but where the overall merge will be very hard to process by current tools.

Before coming to our central theoretical result, we need some preparatory notions. A logic is semi-exact, if it has the amalgamation property for pushout diagrams.

Note that colimits of theories can be easily defined in terms of signature colimits and unions of (translated) axioms; the amalgamation property then carries over from signature colimits to theory colimits (see [11], 4.4.17). We formulate the next results in their full generality to cover also ontology languages other than DLs. But note that they apply in particular to all usual DLs as these are semi-exact and moreover have an initial signature (i.e. a signature with a unique signature morphism into any signature) [5]. We next generalise this result to the case of arbitrary matching configurations.

Theorem 2 (Combination of multiple modules). Assume a semi-exact logic with an initial signature. Consider a family of ontologies (O i ) i∈I indexed by a finite non-empty set I and a simple graph G ⊆ I × I, such that for (i, j) ∈ G, O i and O j are interfaced by

O i θ i,j Σ i,j θ j,i -O j Define Σ i := j∈I\{i} θ i,j (Σ i,j )(1)

and σ i :

Σ i → Π(O i , Σ i ) the module in O i for Σ i . Let σ i,j : Σ i,j → Π(O i , Σ i

) be the restriction of θ i,j , namely θ i,j : Σ i,j → Σ i composed with σ i . 13 Assume that O (resp. O) is obtained by the colimit of the diagram of all σ i,j (resp. all σ i,j composed with the inclusion of

Π(O i , Σ i ) into O i ). Then O is a model-theoretic conservative extension of O. In particular, O is satisfiable iff O is.

Proof. Note that the diagrams for obtaining O resp. O can be turned into connected diagrams by adding the inclusions of the empty signature into all involved theories (the colimit does not change by this addition). The rationale is that this ensures in OWL that all compatible model families are built over the same universe of individuals. More formally, by Prop. 4.4.15 of [11], in any semi-exact logic with an initial signature, all finite non-empty connected diagrams enjoy the amalgamation property. With this, the proof is a straightforward generalisation of the proof of Thm. 1.

Note that Thm. 1 does not hold for consequence-theoretic conservativity. Consider the following example, adapted from [7] Let Σ be {IntroTCS, has_subject}. Then assuming a consequence-theoretically conservative (minimal) module generator,

Π(O 1 , Σ) = Π(O 2 , Σ) = O is IntroTCS ∃has_subject.

But this is consistent, while O 1 ∪ O 2 is not (assuming IntroTCS is also instantiated).

Worked Out Example

The following worked out example serves two purposes: it should illustrate the last theorem on combination of multiple modules, and it should demonstrate its practical impact.

Our ontology repository ORATE 14 contains among others three ontologies, namely: SpatialRelations, ExtendedDnS, and FunctionalParticipation. Let us denote them by O 1 , O 2 , and O 3 resp., to be notationally conform with Theorem 2 above. We combine them in different ways and show how consistency issues of the combined ontologies can already be answered in the combination of modules. Automated matching resulted in the concept identifications listed in the two tables below.

θ 21 = {endurant → physical-endurant, participant → paticipant-place-of, place-of → situation-place-of}.

The second an interface Σ 23 , θ 23 , θ 32 with Σ 23 = {endurant, physical-object, region}, θ 23 = {endurant → non-physical-endurant, physical-object → agentive-physical-object, region → space-region}, and θ 32 = id.

From Σ 12 and Σ 23 , the Σ i 's can be determined: The signatures Σ i , for i = 1, 2, 3, together with corresponding ontologies O i are sent to the module generator that gives us for each ontology the corresponding module M i := Π(O i , Σ i ). Finally, from the signatures Σ i and the signature morphisms θ ij , the colimit (i.e. the alignment) M of the modules M 1 , M 2 , and M 3 is obtained. Similarly, the aligned ontology M can be determined from the three ontologies O 1 , O 2 , and O 3 . A practical result of this alignment can be a check of the merged module M for consistency. As we would expect, the merge of the concept "physical-endurant", "endurant", and "non-physical-endurant" into a single concept makes it unsatisfiable-this result can be automatically verified by a prover. Since we know that Õ must be a conservative extension of M , it is in fact not necessary to build Õ and check its consistency: this information can already be inferred from M . To repair the detected inconsistency of M , we can abandon either M 1 or M 3 from the alignment process. In both cases, M 1 aligned with M 2 only, or M 3 aligned with M 2 only, the resulting merged module turns out to be consistent, and we know by conservativity that the corresponding ontologies would be consistent, too.

Σ 1 = θ 12 Σ 12 = {physical-endurant}, Σ 2 = θ 12 Σ 12 ∪ θ 23 Σ 23 = {endurant}, and Σ 2 = θ 23 Σ 32 = {non-physical-endurant}.

An Interoperability Workflow and Prototypical Implementation

The Component Tools

We implemented a workflow for aligning arbitrary matching configurations taking advantage of several third-party tools. We here briefly introduce these tools and describe in the subsequent subsection their interoperation. Our ontologies to be matched and aligned are taken from our ontology repository ORATE which is being developed and maintained within the EU-project OASIS15 . The software is based on BioPortal [10]. As matching system we use Falcon [3] which matches OWL ontologies by means of linguistic and structural analysis. Falcon can be comfortably used in a batch mode and thus makes it suitable for a pipe workflow. For module extraction as well as consistency checks we use Pellet [12] which in particular makes use of the OWL-API 16 . Finally, we use Hets 17 for the computation of colimits (i.e. alignments). Hets is a parsing, static analysis and proof management tool incorporating various provers and different specification languages, thus providing a tool for heterogeneous specifications.

Workflow Description

Our workflow of multiple ontology alignment consists of two phases: 1) the preprocessing of the whole repository (ORATE) to a complete list of pairwise matching records Fig. 5. Pseudo code of the workflow for multiple ontology alignment Fig. 5 shows the whole workflow in pseudo code. We are going to explain it now line by line. Procedure preprocess_repository takes each pair of ontologies (o1,o2) and applies the procedure match_ontologies to it, i.e., it matches pairwise all ontologies from the repository. The output of match_ontologies is a matching_record: the matching system Falcon computes the mapping between the two ontologies o1 and o2. From the mapping the concepts cs1 (cs2) belonging to ontology o1 (o2) are extracted. Based on the concepts cs1 (cs2), the interface signature s12 is built and the corresponding signature morphisms sm1 and sm2 to the ontologies o1 and o2. The two ontologies, the interface signature, and the two signature morphisms form the matching_record. This record can be viewed as a link between two ontologies. We call this network whose nodes are ontologies and whose edges are the matching records hyperontology graph. Although all ontologies are matched pairwise, the graph is not complete, i.e., some pairs of ontologies (in practice even the majority) are not linked, namely when the matching system cannot find any mappings.

Once the hyperontology graph of the ontology repository is computed we can choose an arbitrary subgraph of it to compute the colimit of modules implicitly given in this subgraph. For that the procedure compute_module_graph takes the hyperontology subgraph and basically replaces its ontologies by modules extracted from them. More precisely, for each ontology (=node) it collects all interfaces (=in_edges) connected to this node and computes (according to Equation 1 in Thm. 2) a signature (sig) that is finally used to compute the module. Practically, this last step is delegated to Pellet (OWL-API).

Aligning modules implicitly given in a hyperontology subgraph (cf. align_modules procedure) comprises the following steps: we first transform the graph with the just mentioned procedure compute_module_graph to the module_graph. From the module graph we extract all signatures (=interfaces) and signature morphisms (views) to the modules. From the modules, the interfaces, and the views we compose a specification document (spec) that can be understood by Hets. Finally, Hets computes the colimit (alignment) of this spec.

Related Work and an Outlook

Matching and revision in networks of ontologies seems to be a rather unexplored topic. Although only studying pairs of ontologies, the most closely related work in spirit appears to be [4], where a semi-automatic procedure is presented for the integration of ontologies that involves revision of mappings. This approach is implemented as the Protégé 4 plugin ContentMap. Here, a selected ontology matcher is used to compute mappings between the signatures of two ontologies chosen for integration, the mappings are explicitly internalised as axioms in an OWL-2 ontology, and the result of the integration is then taken to be the (disjoint) union of the original ontologies together with the mapping axioms. The integration is assumed to be successful if a user does not identify unintended logical consequences. This decision is guided by justifications (explanations for entailment) that can automatically be computed, e.g., by ContentMap and the confidence values created by the matcher for the mapping axioms. To eliminate the unintended consequences, a repair plan is created describing which axioms from the original ontologies or the mapping should be removed. It should be noted that such a plan does not always exist and that a desired integration may require the iteration of these steps.

The main differences to our approach are a) we support heterogeneity of ontology languages, b) we do not internalise the mappings but make explicit the structure of the alignment graph, c) we generically support arbitrary matching configurations and use category-theoretic techniques to compute the merged ontologies without duplicating matched signature items. Apart from these differences, the necessity for debugging and revising matchings also applies to our approach, and the proposed techniques can be made fruitful also in this setting.

We could here only scratch the surface of the area of problems related to matching in networks of ontologies. We have laid out the necessary engineering infrastructure to combine matching, structuring, and reasoning tools, and obtained some theoretical results concerning the reduction of consistency checks to merged modules.

However, a lot of open questions remain. For instance, internalising mappings can be extended to internalising the confidence values of mappings building on similarity-based E-connections [2]. Moreover, a full statistical analysis of major ontologies and repositories remains to be done to understand the impact of iterated matching on consistency.