Ontology alignments

Semantic interoperability can be grounded in ontology reconciliation. Integrating heterogeneous resources of the web requires finding agreement between the ontologies involved. We are interested in expressing these agreements (or disagreement) in relation with the ontology matching problem. We express them through an alignment: a set of relationships, e.g., equivalence or subsumption, between ontology entities.

We have contributed to the definition of alignments and their semantics and we are still working towards deeper expressivity and flexibility of ontology alignments. We also develop supporting software.

Framework and surveying

In the context of the Knowledge web network of excellence, we are developing activities for structuring the research on ontology alignment at the European level. These activities have helped shaping the European research community on the topics of ontology alignment and matching.

This has led to numerous activities and results, including:

• The definition of a general framework for ontology matching [Bouquet 2004a] characterizing the alignment process and the semantics of its output. This framework has been further developed on our side by providing the basis for the Alignment format (see below) and investigating the categorical characterization of matching and merging as well as the composition of alignments.
• A survey of existing alignment techniques and systems [Euzenat 2004g]. In part from this effort we developed a tutorial presented at the European Semantic Web Conference 2005 and a survey paper organising the algorithms in the field [Shvaiko 2005a].
• Finally, with Pavel Shvaiko we produced a reference book on the topic of Ontology matching [Euzenat 2007b]. We also maintain the ontologymatching.org web site.

A large part of the work described in this section were related to the activities of the Heterogeneity work package (2.2) of the Knowledge web network of excellence.

Alignment languages, format and API

We provided a general model for ontology alignment (the result of the mapping task [Euzenat 2003i, Bouquet 2004a]).

An alignment between two ontologies o and o' is a set of correspondences ⟨e, e', r, n⟩ in which

• e∈o and e'∈o' are the entities between which a relation is asserted by the correspondence, e.g., formulas, terms, classes, individuals;
• r is the relation asserted to hold between e and e'. This relation can be any relation applying to these entities, e.g., equivalence, subsumption.
• n is a degree of confidence in this particular correspondence (which will be omitted here).

Most matching algorithms provide correspondences between named entities, more rarely between compound terms. The relationships are generally the equivalence between these entities. Some systems are able to provide subsumption relations as well as other relations in the support language (like incompatibility or instanciation). Confidence measures are usually given a value between 0 and 1 and are used for expressing preferences between two correspondences.

This format designed by Exmo is used in the Alignment API [Euzenat 2004f] which provides a common ground for implementing and comparing alignment algorithms and is used in ontology benchmarking. It is widely adopted.

In order to offer a declarative format which is both expressive and independent from concrete ontology languages we developed the Expressive Alignment Language [Euzenat 2007e]. The high expressivity of the language allows the expression of complex alignments even if the ontology languages are not themselves expressive. The language independence guarantees that we can define expressive alignments between any languages and provides a declarative definition of the alignments which will be usable in various manners (ontology merging, data translation, etc.).

We defined for this language an abstract syntax (used for describing the semantics), an exchange syntax (in RDF/XML) and a more readable surface syntax. We provided a model theoretic semantics for the language which rely upon the semantics of aligned ontologies while remaining independent from their details. We also provided support for this language by combining and extending the API for the Alignment Mapping Language developed at Innsbruck and our own Alignment API.

This work has been carried out in cooperation with Innsbruck Universität (François Scharffe) in the context of the Knowledge web project.

Semantics of alignments and distributed systems

So far, alignments have been given semantics only related to a precise logical framework (e.g., first-order logic). In the continuation of our work on categorical definition of alignment (see below), we aimed at an alignment semantics independent from the ontology semantics.

For that purpose, we have defined a parameterised family of model-theoretic semantics for alignments and knowledge-based distributed systems. This semantics is parameterised by the interpretation of the set of relation, it uses and rely transparently on the semantics of the ontologies (which is only supposed to define the consequence relation ⊨). This means that the models, i.e., satisfying interpretations, of an alignment or a distributed system are defined in function of the models of the local ontologies, even when different ontologies are written in different languages.

Given the semantics of the two ontologies provided by their consequence relation, we define an interpretation of the two ontologies as a triple made of an interpretation for each ontology and an equalising function (γ) which maps the domain of each of the models to a common domain on which the relations are interpreted. Such a triple ⟨m, m', γ⟩ is a model of the aligned ontologies o and o' if and only if, for each correspondence ⟨e, e', r ⟩ ∈ A of the alignment, then m⊨o, m'⊨o' and ⟨γ(m(e)), γ(m'(e'))⟩∈r^γ.

This definition is extended to distributed system, for which a model is a tuple of local models and an equalising function, such that each alignment is valid for the models and the equalising function involved in the tuple. In such a system, alignments play the role of model filters which select the local models which are compatible with all alignments.

We have investigated three different variations of this semantics, offering different levels of integration and supporting different paradigms. The three types of semantics use different techniques to obtain commensurate interpretation of formulas: either by constraining interpretations on a common domain, mapping the domains to a common domain or relating the entities of each pairs of domains. We studied the semantic properties of ontology alignment composition according to these three variants [Zimmermann 2006b]. It appears that only the first two types of distributed semantics are sound with respect to alignment composition, while the last one, which corresponds to the paradigm of Distributed First Order Logics (DFOL), Distributed Description Logics (DDL) and C-OWL, is not.

This work is now used in designing ontology modules. It is also used for defining precisely semantic extensions of precision and recall.

With modular ontologies, knowledge is expressed in interlinked chunks rather than large monolitic ontologies. Ontologies can be assembled from ontology modules like programme modules in software engineering.

We have designed a model of modules which combines an interface and an ontology implementation, in which a module can import other modules through alignments with their interface [Bezerra 2008a, Zimmermann 2008c]. This is a very natural approach since alignments can be used to adjust the components in the ontologies. We have provided a semantics for such modules which is a combination of ontology semantics and our own alignment semantics.

The work on modules is carried out in cooperation with Frederico Freitas within the OntoCompo project and in the framework of the NeOn project.

Towards an alignment algebra

Concrete categories of ontologies exist in the literature, but fail to express complex alignments, e.g. alignments expressing subsumption relation between concepts of two ontologies. To solve this problem, we investigated two approaches: defining more complex categories or improving the structure of our categorical alignments. On the one hand, more complex categories enhance the expressivity of the alignments, but the categories miss some interesting properties such as the existence of the merge for any V-alignment and pair of ontologies. On the other hand, simpler categories, such as the category of theories and theory morphisms in institution theory, can describe complex alignments if the alignment structure is more elaborate. In collaboration with the University of Karlsruhe (Markus Krötzsch and Pascal Hitzler), we introduced W-alignments: a structure having an additional ontology containing bridge axioms relating to o and o' by two V-alignments [Hitzler 2005a, Zimmermann 2006a]. This raises the expressivity of alignments while keeping desirable properties of the category. However, the resulting algebra is less natural (composition is not associative).

In order to deal with uncertainty in relations between ontology entities, we have proposed to use algebra of binary relations instead of the generally used ad hoc relations. We have shown that algebras of binary relations are a natural way to represent disjunction of relations, to agregate matcher results, and to compute composition and granularity change [Euzenat 2008e].

In addition, once we are able to ascribe a semantics to alignments [Zimmermann 2008c], it is possible to carry out approximate reasoning that does not involve ontologies but alignments alone. This can be exploited for evaluating alignments [David 2008b] or for checking consistency or preprocessing a distributed set of alignments through the computation of its compositional, symmetric and union closure. Algebra of relations are then instrumental for computing composition of alignments.