Introduction

The problem of aligning, or matching, ontologies can be essentially broken down into three sub-problems: (1) the problem of discovery, i.e., the problem of finding adequate relationships or mappings between the syntactical material of different ontologies; (2) the problem of representing such possibly rather heterogeneous 'theory connections'; and (3) the problem of computing or constructing a new super-ontology realising the intended integration.

While the first problem can be of an empirical, heuristic or statistical nature, and often requires the intervention of human experts to be adequately solved (see Euzenat and Shvaiko [2007] for a survey), ( 2) and (3) are purely theoretical or logical problems of adequate representation, construction, and computation.

We concentrate on the latter problems and propose a general framework for representing, combining, and computing complex alignments building on the category theoretic notions of diagram and colimit and the theory of institutions. This generalises earlier work of a similar spirit, briefly introduced and discussed in Section 3, most notably the 'semantic integrations' of Schorlemmer and Kalfoglou [2008] (that we call Λ-alignments), and the Vand W-alignments of Zimmermann et al. [2006].

Our approach also gives an elegant and simple solution to the problem of combining alignments, compare Section 3.5, and easily covers and unifies standard alignment problems of identifying symbols from different ontologies or keeping symbols from different ontologies with the same name apart. However, it also covers more elaborate integration scenarios, for instance those based on E-connections or DDLs, where not a simple identity but a more complex relationship between symbols is established-this is presented in Section 6.

Moreover, we briefly discuss how heterogeneous ontology alignments can be represented as diagrams using the heterogeneous specification language Het-Casl, and demonstrate how the tool Hets can be used to compute a colimit ontology of such a diagram, i.e., the required integrated super-ontology of the alignment.

Institutions

The study of modularity principles can be carried out to a quite large extent independently of the details of the underlying logical system that is used. The notion of institution was introduced by Goguen and Burstall in the late 1970s exactly for this purpose (see [Goguen and Burstall, 1992]). Institutions capture in a very abstract and flexible way the notion of a logical system by leaving open the details of signatures, models, sentences (axioms) and satisfaction (of sentences in models).

The only condition governing the behaviour of institutions is the satisfaction condition, stating that truth is invariant under change of notation (or enlargement of context):

M |= Σ σ(ϕ) ⇔ M | σ |= Σ ϕ

Here, σ: Σ −→ Σ is a signature morphism, relating different signatures (or module interfaces), σ(ϕ) is the translation of the Σ-sentence ϕ along σ, and M | σ is the reduction of the Σ -model M to a Σ-model.

The importance of the notion of institutions lies in the fact that a surprisingly large body of logical notions and results can be developed in a way that is completely independent of the specific nature of of the underlying institutionall that is needed is captured by the satisfaction condition. We refer the reader to the literature, see Goguen and Burstall [1992]; Diaconescu [2008], for full formal details.

A theory in an institution is a pair T = (Σ, Γ ) consisting of a signature Sig(T ) = Σ and a set of Σ-sentences Ax(T ) = Γ , the axioms of the theory. If T = (Σ, Γ ) is a theory and Σ (resp. Γ ) a signature (resp. set of sentences), we write Σ T

(resp. Γ T ) shorthand for Σ ⊆ Sig(T ) = Σ (resp. Γ ⊆ Ax(T ) = Γ ).

The models of a theory T are those Sig(T )-models that satisfy all axioms in Ax(T ). Logical consequence is defined as usual: T |= ϕ if all T -models satisfy ϕ. Theory morphisms are signature morphisms that map axioms to logical consequences.

Example 1. First-order Logic. In the institution FOL ms= of many-sorted firstorder logic with equality, signatures are many-sorted first-order signatures, consisting of sorts and typed function and predicate symbols. Signature morphisms map symbols such that typing is preserved. Models are many-sorted first-order structures. Sentences are first-order formulas. Sentence translation means replacement of the translated symbols. Model reduct means reassembling the model's components according to the signature morphism. Satisfaction is the usual satisfaction of a first-order sentence in a first-order structure.

Example 2. Relational Schemes. A signature consists of a set of sorts and a set of relation symbols, where each relation symbol is indexed with a string of sorted field names. Signature morphisms map sorts, relation symbols and field names. A model consists of a carrier set for each sort, and an n-ary relation for each relation symbol with n fields. A model reduction just forgets the parts of a model that are not needed. A sentence is a link (integrity constraint) between two field names of two relation symbols. Sentence translation is just renaming. A link is satisfied in a model if for each element occurring in the source field component of a tuple in the source relation, the same element also occurs in the target field component of a tuple in the target relation.

Example 3. Description Logics. Signatures of the description logic ALC consist of a set B of atomic concepts and a set R of roles, while signature morphisms provide respective mappings. Models are single-sorted first-order structures that interpret concepts as unary and roles as binary predicates. Sentences are subsumption relations C 1 C 2 between concepts, where concepts follow the grammar

C ::= B | | ⊥ | C 1 C 2 | C 1 C 2 | ¬C | ∀R.C | ∃R.C

Sentence translation and reduct is defined similarly as in FOL = . Satisfaction is the standard satisfaction of description logics. ALC ms is the many-sorted variant of ALC. The description logic EL restricts ALC as follows:

C ::= B | | C 1 C 2 | ∃R.C. SHOIN

Alignments as Diagrams

Λ-Alignments

In the approach of Schorlemmer and Kalfoglou [2008], two ontologies O 1 and O 2 are aligned by mapping them into a common reference ontology O as follows: theories O 1 and O 2 are said to be semantically integrated with respect to a theory O if (1) there exist theory interpretations α Theory interpretations α 1 , α 2 can be given as follows:

1 : O 1 −→ O, α 2 : O 2 −→ O; (2) there exist structure reducts β 1 : Mod(O 1 ) −→ Mod(O), β 2 : Mod(O 2 ) −→ Mod(O); and (3) O is consistent. O O1 α1 - O2 α 2α1(person(p, n)) = Researcher (p) ∧ String(n) ∧ Name(p, n) α1(author of(p, a)) = Researcher (p) ∧ Article(a) ∧ Author (a, p) ∧ ∧∃j.(Journal (j ) ∧ Has Article(j , a)) α2(Article(x)) = Publication(x )

We will reformulate this example as a (general) heterogeneous alignment in Section 4.

We see the following problems with this approach3 -Allowing for arbitrary sentence maps α i is too liberal: for example, α i could map every sentence to true. 4 It makes more sense to use signature morphisms and their induced sentence translation maps instead. This approach is less flexible in one aspect: with the approach of Schorlemmer and Kalfoglou [2008], e.g. in first-order logic, a predicate symbol p may be mapped to a formula ϕ. However, this is usually better captured by allowing for derived signature morphisms (see Sannella and Burstall [1983]), which here are just signature morphisms into a conservative extension (e.g. an extension by the definition p(x) ⇔ ϕ). -More importantly, perhaps, there may be no suitable common reference ontology at hand. Rather, the common super-ontology should be constructed via a union of O 1 and O 2 , identifying certain concepts, while keeping others distinct. This leads to V-Alignments, discussed in the next section.

V-Alignments

Zimmermann et al. [2006] address the problem of alignment without a common reference ontology. 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 common 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 thus 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 Figure 2. Example 6. In Figure 2, 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.

However, notion such as polysemy 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. We will come back to this when discussing E-connections as alignments in Section 5. Similarly, Zimmermann et al. [2006] themselves 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 resulting ontology should turn Woman into a subconcept of Person. This is not directly possible with the pushout approach.

W-Alignments

In order to solve this problem of V-Alignments, Zimmermann et al. [2006] introduce W-Alignments. They consist of two V-Alignments, using an intermediate bridge ontology B. The latter can be used to specify subconcept relationships like Woman Person as mentioned above.

{Woman} {Woman Person} {Person} O1 B O2 Σ1 - Σ2 - = {Woman} = {Person}

Fig. 3. W-alignment: integration through bridge ontology Zimmermann et al. [2006] list the behaviour of compositions as a weak point of this approach. However, we see as the main weak point the rather loose coupling of O 1 and O 2 ; indeed, the bridge ontology is something like a super-ontology of a sub-ontology and hence can be anything.

M-Alignments

Given two ontologies O 1 and O 2 , let us assume that we want to align them using an interface Σ. We assume that O 1 and O 2 are extensions (typically conservative extensions) of O 1 and O 2 , respectively, taking into account the possible requirements to (1) define new symbols (in order to emulate a derived theory morphism), and (2) introduce new subconcept relationships, such as Woman Person, as discussed above. We thus arrive at the concept of M-alignment: E-connections as a kind of extended (and heterogeneous) M-alignment will be discussed in Section 5. Compare also Example 8 below.

{Woman, Person, River Bank, Financial Bank} O {Woman Person} {Person, Bank} O 1 - O 2 O1 - Σ - O2 ≺ {Woman, Bank} = {Person} ≺ {Person, Bank}

General Alignments and Their Combination

Zimmermann et al. [2006] note that the composition (or better: combination) of W-alignments via pushouts resp. colimits leads to the unpleasant phenomenon that the bridge ontology of the resulting W-alignment includes the whole of one of the aligned ontologies. We think that this problem arises because colimits are used for the wrong purpose: they should be used for the computation of an integrated overall ontology, but not for the combination of alignments. Instead, the complete diagram structure of the alignments should be kept intact. This means that combination generally changes shapes of diagrams, and we hence need to generalise the notion of a (diagrammatic) alignment.

The notion of diagram is formalised in category theory. It generalises the different shapes of alignments that we have seen so far. Diagrams map an index category (via a functor) to a given category of interest. They can be thought of as graphs in the category. For details, see Adámek et al. [1990].

Definition 7. A general alignment of ontologies is a diagram of theories such that the nodes are subdivided into ontology nodes and interface nodes. Now, combination of alignments is basically union of the diagrams. Further details may be found in Kutz and Mossakowski [2007], where also the problem of proof-theoretic and model-theoretic conservativity in diagrams is studied, a problem area that is extremely important when considering ontologies as 'modules' of other ontologies, cf. Lutz et al. [2007]; Cuenca Grau et al. [2008].

Heterogeneous Alignments

As Schorlemmer and Kalfoglou [2008] argue convincingly, since ontologies are being written in many different formalisms, like relation schemata, description logics, first-order logic, and modal (first-order) logics, alignments of ontologies need to be constructed across different institutions.

Heterogeneous specification is based on some graph of logics and logic translations, formalised as institutions and so-called institution comorphisms, see Goguen and Roşu [2002]. The latter are again governed by the satisfaction condition, this time expressing that truth is invariant also under change of notation across different logical formalisms:

M |= J Φ(Σ) α Σ (ϕ) ⇔ β Σ (M ) |= I Σ ϕ.

Here, Φ(Σ) is the translation of signature Σ from institution I to institution J, α Σ (ϕ) is the translation of the Σ-sentence ϕ to a Φ(Σ)-sentence, and β Σ (M ) is the translation (or perhaps: reduction) of the Φ(Σ)-model M to a Σ-model.

The so-called Grothendieck institution is a technical device for giving a semantics to heterogeneous theories involving several institution [see Diaconescu, 2002;Mossakowski, 2002]. The Grothendieck institution is basically a flattening, or disjoint union, of the logic graph. A signature in the Grothendieck institution consists of a pair (L, Σ) where L is a logic (institution) and Σ is a signature in Biblio RS in DL states that the ontology satisfies the relational scheme axioms (referential integrity constraints). Of course, this is not possible literally, but rather the ontology is mapped to first-order logic (CASL) and then extended definitionally to Biblio DL with a definition of the database tables in terms of the ontology classes and properties (compare the specification above after %def). Also, Biblio RS is translated to first-order logic, yielding Biblio RS , and so the view shown in Fig. 5 as a dotted line expresses a theory morphism from Biblio RS to Biblio DL . The involved signature and theory morphisms live in the Grothendieck institution. Thus, we can avoid the use of arbitrary maps α i as in Schorlemmer and Kalfoglou [2008] and instead rely entirely on (Grothendieck) signature morphisms.

In fact, note that the above view is not provable. However, it becomes provable if an inverse of the role hasArticle is introduced and used to restrict the class Article.

E-Connections as Heterogeneous Alignments

In this section, we show how the integration of ontologies via 'modular languages' can be conceived of as specific alignments. We concentrate on E-connections, but note here that DDLs [Borgida and Serafini, 2003] can be treated in exactly the same way [Kutz et al., 2004].

Originally conceived as a versatile and computationally well-behaved technique for combining logics [Kutz et al., 2004], E-connections have also been adopted as a framework for the integration of ontologies in the Semantic Web [Cuenca- Grau et al., 2006]. The general idea behind this combination method is that the interpretation domains of the connected logics are interpreted by disjoint (or sorted) vocabulary and interconnected by means of link relations. The language of the E-connection is then the union of the original languages enriched with operators capable of talking about the link relations.

E-connections, just as DLs themselves, offer an appealing compromise between expressive power and computational complexity: although powerful enough to express many interesting concepts, the coupling between the combined logics is sufficiently loose for proving general results about the transfer of decidability: if the connected logics are decidable, then their connection will also be decidable. We here introduce E-connections only by way of an informal but suggestive example, for full details refer to [Kutz et al., 2004].

Given interpretations W i = (W i , . Wi ), i ∈ {1, 2}, of S i , a model of the E-connection C E (S 1 , S 2 ), where E = {E}, is a structure of the form

M = W 1 , W 2 , E M , where E M ⊆ W 1 × W 2 .

The extension C M ⊆ W i of an i-concept C is defined by simultaneous induction. For concept names C of S i , we put C M = C Wi ; the inductive steps for the Booleans and function symbols of S i are standard; finally,

( E j 1 C) M = {x ∈ W 1 | ∃y ∈ C M (x, y) ∈ E M j }, ( E j 2 D) M = {x ∈ W 2 | ∃y ∈ D M (y, x) ∈ E M j }.

Example As should be clear from the discussion so far, E-connections can essentially be considered as many-sorted heterogeneous theories: component ontologies can be formulated in different logics, but have to be build from many-sorted vocabulary, and link relations are interpreted as relations connecting the sorts of the component logics (compare Baader and Ghilardi [2007] who note that this is an instance of a more general co-comma construction). The main difference between DDLs and various E-connections now lies in the expressivity of the 'link language' L connecting the different ontologies. While the link language of DDL is a certain sub-Boolean fragment of many sorted ALC, the basic link language of E-connections is ALCI ms .5 Such many-sorted theories can easily be represented in a diagram as shown in Figure 6, showing an extension of an M-alignment.

Computation of Alignments

The Heterogeneous Tool Set Hets [Mossakowski et al., 2007a,b] provides analysis and reasoning tools for the specification language HetCasl, a heterogeneous extension of Casl supporting a wide variety of logics [CoFI (The Common Framework Initiative), 2004; Bidoit and Mosses, 2004]. In particular, OWL-DL (with SHOIN and its sublogics EL and ALC, also supporting Manchester syntax), relational schemes, as well as FOL ms and QS5 (using syntax of the Casl language). See the extended example in Sect. 4 for the look-and-feel of HetCasl specifications. Heterogeneous theories grouped inside a library of specifications are represented in Hets as graphs which can be displayed in a GUI window. Thus, by specifying ontologies and the mappings between them in a HetCasl library, we can visualise the diagram of the ontology alignment. Figure 7 shows the diagrams of a Vand a W-alignment obtained with Hets.

Hets also offers an algorithmic method for computing colimits of theories in various logics, based on an implementation for computing colimits of arbitrary sets, which is further applied to sets of signature symbols, like sorts, operation and predicate symbols (the latter two divided according to profiles). As a general strategy, names are kept identical to their original as far as possible (see the example below). If this is not possible, the common origin of symbols is indicated by a (shared) number appended to their name.

Example 10. Considering the V-alignment introduced in Example 6, Figure 8 presents the Hets concept graphs of the theories combining it, as well as the one of the push-out ontology obtained with Hets (the top one). The construction of colimits for heterogeneous diagrams is considerably more difficult. We refer the reader to Mossakowski [2006]; Codescu and Mossakowski [2008] for a detailed analysis of sufficient conditions for obtaining colimits of heterogeneous theories, and for a discussion of weaker notions that are useful in cases where heterogeneous colimits do not exist.

Discussion and Outlook

We have introduced an abstract framework of general alignments that remedies shortcomings of similar frameworks that have been discussed in the literature. The framework allows for a systematic and conceptual analysis of approaches that were previously considered rather disparate. More importantly, it makes possible generic algorithms for heterogeneous alignment problems, as have been implemented in the Heterogeneous Tool Set.

An essential prerequisite for the representation of alignments as diagrams is of course the discovery of alignment mappings of various kinds. While this was not the subject of this paper, we work on integrating a tool for finding theory morphisms into the Heterogeneous Tool Set. This tool, together with other known alignment tools, could then be used as a basis for finding alignment diagrams.