Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Algebras of ontology alignment relations

Correspondences in ontology alignments relate two ontology entities with a relation. Typical relations are equivalence or subsumption. However, different systems may need different kinds of relations. We propose to use the concepts of algebra of relations in order to express the relations between ontology entities in a general way. We show the benefits in doing so in expressing disjunctive relations, merging alignments in different ways, amalgamating alignments with relations of different granularity, and composing alignments.

Motivations

The heterogeneity of ontologies on the semantic web requires finding the correspondences between them in order to interoperate. The operation of finding correspondences is called ontology matching and its result is a set of correspondences called an alignment [START_REF] Euzenat | Ontology matching[END_REF]. Alignments are used for importing data from one ontology to another or for translating queries.

In general, a correspondence relates an entity, e.g., a class, a property, an instance, of a first ontology to an entity of the second ontology by a specific relation. This relation can be the equivalence or subsumption between these entities or more complex relations, e.g., mereologic relations such as partOf.

Within an alignment, correspondences are interpreted conjunctively, but it may sometimes be necessary to express disjunctions of relations, e.g., when one is only able to establish a subset of the possibly holding relations. Moreover, in the wider context of sharing alignments on the web and composing ontology matchers, it is necessary to manipulate alignments: combining alignments either conjunctively or disjunctively, composing alignments when a direct alignment between two ontologies does not exist or converting alignments using a different set of relations. Current support for alignment is not adapted to this: correspondences are usually expressed with respect to simple relations and the connection between relations is not explicit.

Example 1 (Background). We consider the example of three geographic ontologies designed for statistical purposes. They are loosely built on the Eurostat Nomenclature for Territorial Units for Statistics (or NUTS). We deal with three ontologies adapted to the German (o), English (o ) and French (o ) territory. In order to be able to aggregate information from the German and the British sources, engineers need an alignment between o and o . They will take advantage of alignments provided by various sources.

We propose to solve this problem by expressing alignment relations within the formalism of algebras of relations. At first sight, algebras of relations may seem like just one possible solution to express disjunctions. However, we show that, in addition to allowing disjunctive relations, this formalism provides many advantages in the manipulation of alignments.

We first present in more detail the notion of ontology alignment and relations between ontology entities ( §2), as well as algebra of relations ( §3). We then show how, in addition to expressing disjunction, algebras of relations can support several types of relation aggregation ( §4), alignment composition ( §5), algebraic reasoning on alignments ( §6), and weakening of representations ( §7). We finally show that this kind of relations can still be manipulated coherently with confidence measures ( §8).

Alignments and relations

Alignments express the correspondences between entities belonging to different ontologies (we restrict ourselves to two ontologies here). We provide the definition of the alignment following the work in [START_REF] Euzenat | An API for ontology alignment[END_REF][START_REF] Bouquet | Specification of a common framework for characterizing alignment[END_REF].

Definition 1 (Correspondence). Given two ontologies o and o with associated entity languages Q L and Q L , a set of alignment relations Θ, and a confidence structure over Ξ, a correspondence is a quadruple:

e, e , r, n ,

such that -e ∈ Q L (o) and e ∈ Q L (o ); -r ∈ Θ; -n ∈ Ξ.
The correspondence e, e , r, n asserts that the relation r holds between the ontology entities e and e with confidence n.

The entities can be simply made of all the formulas of the ontology language based on the ontology vocabulary. They can be restricted to particular kinds of formulas from the language, such as atomic formulas, or even to terms of the language, like class expressions. It can also restrict the entities to be only named entities. The entity language can be an extension of the ontology language. For instance, it can be a query language, such as SPARQL [START_REF]SPARQL query language for RDF[END_REF], adding operations for manipulating ontology entities that are not available in the ontology language itself, like concatenating strings or joining relations.

In some tradition, e.g., schema matching [START_REF] Sheth | Federated database systems for managing distributed, heterogeneous, and autonomous databases[END_REF][START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF], some authors tend to consider that a correspondence like: address = street + " " + number is some kind of ternary complex relation (• = • + " " + •) between three entities address, street and number. In our setting, this is simply a normal correspondence in which the binary relation is equivalence (=) and the ontology entities are address and street+" "+number. This is the main reason why we consider ontology entities, the latter entity is a term built on strings and operations on strings (here concatenation +).

The next important component of the alignment is the relation that holds between the entities. We identify a set of relations Θ that is used for expressing the relations between the entities. Matching algorithms primarily use the equivalence relation (=) meaning that the matched objects are the same or are equivalent if these are formulas. It is possible to use relations from the ontology language within Θ. For instance, using OWL, it is possible to take advantage of the owl:equivalentClass, owl:disjointWith or rdfs:subClassOf relations in order to relate classes of two ontologies. These relations correspond to set-theoretic relations between classes: equivalence (=), disjointness (⊥), less general ( ). They can be used without reference to any ontology language.

For pragmatic reasons, the relationship between two entities is assigned a degree of confidence which can be viewed as a measure of trust in the fact that the correspondence holds -'I trust 70% the fact that the correspondence is correct or reliable' -and can be compared with the certainty measures provided with meteorological forecasts. These values are taken from a bounded ordered set Ξ that we call a confidence structure. We will come back on this in Section 8 and ignore it until then.

Finally, an alignment is defined as a set of correspondences. This definition does not tell how to interpret this set of correspondences. However, it is clear from usage that it has to be interpreted in a conjunctive manner: all the correspondences are asserted to hold when asserting an alignment.

Hence, the problem of expressing disjunctions of correspondences can be raised. This can be because it is necessary to aggregate the result of methods which address the ontology matching problem from different dimensions, this can be because the person or the program generating the alignment is unsure about the exact relation but knows that this relation is constrained to a specific set of alternative relations.

Example 3 (Disjunctive relations). For instance, an engineer may know that a Stadt, i.e., Town, and a Town are similar things but may not know exactly the nature of the overlaps. She can express that they are not disjoint by the disjunction of relations <, >, and =, thus prohibiting ⊥. This can also be because the alignment has been generated by composing two alignments. This operation does not usually return a simple relation but a disjunction of such relations, e.g., if Stadtgebiet, i.e., Urban area, is more general than Ville, i.e., Town, and Ville overlaps Municipality, then Stadtgebiet either is more general or overlaps Municipality, it cannot be disjoint with it. Hence, the result is a disjunction of relations. This is also the case of the ≥ (more-general-or-equal) and ≤ (more-specific-orequal) relations used by some systems. These are typically the disjunction of < and = or > and =. In fact, practice which considers that if both ≤ and ≥ hold (conjunction), then = holds, only reflects the set operation: {<, =} ∩ {>, =} = {=} or the logical interpretation that:

∀a, b, (a < b ∨ a = b) ∧ (a > b ∨ a = b) |= a = b if <, > and = are exclusive
The first goal of this paper is to consider a systematic treatment for disjunctive alignment relations. For that purpose, we use algebra of relations and we show that this has many advantages.

Relation algebra

An algebra of binary relations (hereafter referred to as relation algebra) [START_REF] Tarski | On the calculus of relations[END_REF] is a structure Θ, ∧, ∨, * , 1, 0, 1 , ¬ such that Θ, ∧, ∨, 1, 0 is a Boolean algebra; * is an associative internal composition law with (left and right) unity element 1 , that distributes over ∨; ¬ is an internal involutive unary operator, that distributes over ∨, ∧ and *.

We consider a particular type of relation algebras1 in which Θ is the powerset of a generating set Γ closed under ¬ (hereafter -1 ) and ∧/∨ are set intersection/union (∩/∪). Such an algebra of (binary) relations is defined by 2 Γ , ∩, ∪, •, Γ, ∅, {=}, -1 such that:

-Γ is a set of jointly exhaustive and pairwise disjoint (JEPD) relations between two entities. This means that, in any situation, the actual relation between two objects is one and only one of these relations. Sets of relations allow to express uncertainty: the full Γ set is the "I do not know" relation since it is satisfied by any pair of entities; -∩ and ∪ are set operations used to meet and join two sets of base relations, hence if xry or xr y, then xr ∪ r y; -• is the composition operator such that if xry and y r z, then x r • r z; "=" is such that ∀r ∈ Γ, (r• =) = (= •r) = r; --1 is the converse operator, i.e., such that ∀e, e ∈ Γ, ere ⇔ e r -1 e.

These operations are applied to sets of base relations by distributing them on each element, e.g., R • R = r∈R,r ∈R r • r .

A typical example of such an algebra is the Allen algebra of temporal interval relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. Here, we will consider, as an example, a simpler algebra, called A5, isomorphic to that applying to sets in which the base (JEPD) relations between two sets are equivalent (=), includes (>), is-included-in (<), overlaps ( ) and disjoint (⊥). In this algebra, all base relations but < and > are there own converse while > -1 =< and < -1 =>.

The complete set of 2 5 -1 = 31 valid relations that can be made out of these 5 base relations is depicted in Figure 1. Among these relations, Γ means "I do not know" as it contains all the base relations. = is equivalent to {<, >, , ⊥}, ≤ is equivalent to {=, <}, ≥ to {=, >}, < > to {<, >, } and ⊥ to {=, <, >, }. The composition table is given in Table 1.

Relation algebras can still be used when the ontology entities are formulas (or queries) and the base relations are logical connectives between formulas (⇒, ≡). Indeed, it is sufficient to split the disjunctive relations into a disjunction of formulas: φ{⇒, ≡}ψ would be equivalent to φ ≡ ψ ∨ φ ⇒ ψ (these relations are not exclusive anymore).

Aggregating matcher results

The set Θ is closed for ∨, ∧ and ¬. This means that any combination of these operations yields an element of Θ. This is very powerful if one wants to combine relations, e.g., for combining correspondences and alignments.

When matching methods bring new evidences for a correspondence from a different perspective, they are though of as bringing new arguments in favor of a correspondence. Hence, its results must be aggregated with union (R∪R ). When the matching methods, instead, are competing algorithms providing all the possible base relations, i.e., providing arguments against the non selected correspondences, then intersection (R ∩ R ) should be used. Because, we now have two distinguished operations, they can be used together in the same application.

These operations can be used for describing two cases of matching process: an expanding matching process which starts with the empty relation (∅) between each pair of entities and which finds evidences for more base relations between these entities aggregating them with ∪ and a contracting process which starts with Γ between each pair of entities and which discards support for some base relations between entities aggregating the result with ∩. In the first case, the more matching methods are used, the less precise the alignment becomes: this can be balanced by confidence measures as we will see below. In the second case, the more methods are used, the more precise the alignment becomes.

These operations on Θ are used in correspondence aggregation: an alignment is interpreted as all the correspondences it contains hold, and a distributed system is interpreted as all alignments hold. Hence, the disjunctive aggregation of alignments is based on the combination of their set of correspondences with the union of relations; the conjunctive aggregation of alignments is based on the combination of their set of correspondences with the intersection of relations. Hence, we define a normalisation operation Ā, which implements the conjunctive interpretation of alignments. It provides exactly one correspondence per pair of entities and makes explicit all the relations between entities in A:

A 0 = { e, e , Γ |e ∈ Q L (o), e ∈ Q L (o )} Ā = { e, e
, ∩ e,e ,r ∈A∪A 0 r } It is then easy to define intersection: Algebras of relations are useful because they can account for these two behaviours. However, there are other benefits brought by algebra of relations.

A ∧ A = { e, e ,

Composing alignments

Another way of reusing alignments is to deduce new alignments from existing ones. One way to do so, is to compose alignments. If there exists an alignment between ontology o and ontology o , and another alignment between o and a third ontology o , we would like to find which correspondences hold between o and o . The operation that returns this set of correspondences is called composition.

Alignment composition has already considered [START_REF] Zimmermann | Formalizing ontology alignment and its operations with category theory[END_REF] with the idea that, in an open system like the Alignment API, the rules for composing alignment relations, e.g., instanceOf • subClassOf = instanceOf, should be given by a composition table. Composition tables come directly from algebra of relations and they naturaly extend from base relations to disjunctions of base relations.

Alignment composition can thus be reduced to combining correspondences with regard to their relations and the structure of related entities and computing the confidence degree of the result. The composition table between the base relations of A5 is given in Table 1.

= > < ⊥ = = > < ⊥ > > > ><= > > ⊥ < < Γ < < ⊥ ⊥ > ⊥ < Γ > ⊥ ⊥ ⊥ ⊥ < ⊥ < ⊥ Γ Table 1. Composition table for the A5 relation algebra.
The composition of two alignments A and A is defined by:

A • A = { e, e ,
A 3 = A 1 • A 2 .
because {>} • { } => • = {<, }.
The result provided by the table in this case is a disjunction of relations because it is not possible to obtain more precise information from the alignments alone.

Very often the composition of two base relations is not a base relation but a disjunction of relations. Hence, if we were not dealing with sets of base relations, it would not be possible to represent the composition of two alignments by an alignment. Moreover, defining composition by an algebra of relations automatically satisfies all the constraints on the categorical characterisation of alignments defined in [START_REF] Zimmermann | Formalizing ontology alignment and its operations with category theory[END_REF]: it must be associative and have an identity element. This is true from the definition of algebra of relations.

6 Algebraic reasoning with alignments α-consequences are correspondences which are entailed by two aligned ontologies [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF]; they can be extended as the correspondences entailed by a system of many ontologies and many alignments between them. [START_REF] Zimmermann | Sémantique des connaissances distribuées[END_REF] introduced the notion of quasi-consequences as the set of formulas entailed by a set of alignments alone (without considering ontologies). This notion can be straightforwardly extended to correspondences as quasiα-consequences: the correspondences which are entailed by the set of alignments, when considering the ontologies as void of axioms. Quasi-α-consequences are also α-consequences.

Reasoning on alignments aims at using existing alignments in order to deduce more and more complete alignments. Such a reasoning procedure can be considered, for soundness and completeness, with respect to α-consequences.

Algebraic reasoning (using combination of composition, converse, and intersection) can be used as a practical and efficient way to reason with alignments. The algebraic closure of a set of alignments S is the set of normalised alignments, containing S, closed under composition, converse and intersection.

This procedure is correct (the algebraic operations can be transformed into their logical equivalent). However, since it does not consider ontologies, it can only deduce quasi-α-consequences. We have no guarantee that it is complete even for finding quasiα-consequences.

However, this can already be used for two purposes: (1) improving the existing alignments by deducing new correspondences coming either from the alignment itself or from other alignments, and (2) checking the consistency of a set of alignments (or one alignment). Indeed, if we can deduce x{}y, e.g., because x{<}y and x{>}y for two competing matchers, since the intersection is empty we know that the alignment itself is inconsistent. This kind of reasoning can be more complex, involving several alignments as well as composition operations, i.e., checking a whole distributed system. Then, the set of alignments as a whole would be inconsistent, hence the distributed system would have no model.

Example 6 (Algebraic reasoning). The simplest instance of an inconsistent alignment is to have two contradictory statements like Konstruktion{⊥}Town and Konstruktion{< }Town in the same alignment. The conjunction of these two relations, obtained by normalisation, is empty. Such an inconsistent alignment can also be obtained by combining consistent alignments. For instance, aggregating conjunctively alignments A 3 and A 4 of Example 4, will generate the inconsistent Stadtgebiet {} Municipality correspondence.

Algebraic reasoning allows to expand alignments. For instance, Stadt{>}Town, Stadtgebiet{<}Town, Stadtgebiet{⊥}Municipality entails Stadt{>, , ⊥}Municipality. Computing the compositional closure of this alignment will find this correspondence.

Moreover, if the initial alignment also contain Stadt{=, <}Municipality, the compositional closure will bring the inconsistence to light. Once again, it is possible to use disjunctive relations to better evaluate alignments. Indeed, the problem is that if a matcher returns a correspondence between two entities with relation ≤ while the expected (and exact) relation was <, then the use of syntactic precision and recall measures would count this relation as incorrect. Hence, if the expected alignment was made of this correspondence alone, both precision and recall would be 0. This is unfair because it cannot be said that this correspondence is both incorrect and incomplete. In fact, it is incomplete, because it does not provide the exact relation, but not incorrect, because the relation is more general than the correct one.

This is indeed what happens with semantic precision and recall [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF]: since the relation {<, =}, which is the disjunction of < and =, can be deduced from {<} alone, it would count as correct for semantic precision and still as incorrect for semantic recall because {<, =} does not entail {<}.

We could introduce an algebraic precision and recall for evaluating ontology alignments as an intermediary step between classic precision and recall and semantic precision and recall. It would simply use the inclusion between the relations as suggested above instead of the entailment between correspondences of [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF] and would be far easier to compute. The resulting measure would be a relaxation of precision and recall in the sense of [START_REF] Ehrig | Relaxed precision and recall for ontology matching[END_REF].

Algebra granularity

In order to investigate granularity within algebras of relations, we introduced the notion of weakening [START_REF] Euzenat | Granularity in relational formalisms with application to time and space representation[END_REF]. Weakening an algebra of relations simply consists of grouping together several base relations and taking the result as the base relations of the, less precise, weaker algebra.

In fact, taking any maximal antichain2 that preserves converse in the lattice of Figure 1 yields a base for an algebra of relations. Other constraints can be put on weakening, such as requiring that they preserve a neighbourhood structure. Neighbourhood structures for algebras of relations have been introduced in [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF]. They are based on a connectivity relation between relations that is used for defining neighbourhood. This connectivity relation can be based on different properties of the domain the relations apply to. We have shown that granularity operators, at least in time and space algebras, can be automatically built on such neighbourhoods [START_REF] Euzenat | Granularity in relational formalisms with application to time and space representation[END_REF].

In terms of alignment, the interesting aspect of this weakening operation is that it helps considering that alignments using different sets of relations are compatible and can still be used together. Coming back to the example of set-relations, there can be systems that provides only the = base relation leaving implicitly all the others as Γ , there are other systems like the one considered previously which consider =, <, >, and ⊥. The set of base relations is different and thus it is not easy to combine two such alignments. However, if we consider that the first one is a weakening of the second one (grouping <, >, and ⊥ into =), then it is possible to import one alignment into another formalism and vice-versa (at the expense of completeness when we export to the weaker algebra).

Example 7 (Algebra granularity). Different sources of alignments may provide alignments with different kinds of relations between objects. For instance, the following A 7 alignment (left-hand side) is expressed in the simple {⊥, ⊥} algebra, i.e., identifying only incompatible elements.

Stadt{ ⊥}Town

Stadt{ ⊥}Town

Stadtgebiet{⊥}Municipality Stadtgebiet{⊥, ⊥}Municipality

Thanks to the use of compatible algebras, A 7 can be expressed in the more expressive algebra. In fact, the alignment A 4 of Example 4 is the transcription of A 7 in the A5 algebra. On the other hand, it is possible to degrade an alignment into the coarser algebra at the expense of The alignment on the right-hand side is the result of converting the alignment A 5 of Example 4 to the {⊥, ⊥} algebra.

Figure 2 shows the "interesting" weakened algebras of relations from the initial algebra. It features the {=, =} algebra but also shows that the usually considered {=, ≤ , ≥, ⊥} is not a correct base for such an algebra because it is neither jointly exhaustive (≤ and = can occur at the same time), nor pairwise disjoint ( is missing).

Compatibility with confidence measures

Most matchers assign confidences to the correspondences they produce. They express to what extent they trust the correspondence. This confidence is expressed in a confidence structure:

Definition 3 (Confidence structure). A confidence structure is an ordered set of degrees Ξ, ≤ for which there exists a greatest element and a smallest element ⊥.

The usage of confidence degrees is that the higher the degree with regard to ≤, the most likely the relation holds. This means that a particular confidence degree entails all the inferior confidence degrees.

With algebras of relations, the confidence assigned to a relation applies to the disjunction as a whole. Hence, when a confidence is assigned of some relation, this confidence can be assigned to all its supersets, but not to its subsets. The larger the relation, the stronger the confidence can be: typically, Γ should be given full confidence ( ) and ∅ the lowest one (⊥).

A correspondence e, e , r, n entails another correspondence e, e , r , n if and only if r ⊆ r and n ≥ n . The normalisation operation will then only retain maximal elements for the induced order:

A 0 = { e, e , Γ, |e ∈ Q L (o), e ∈ Q L (o )} Ā = max ⊆,≥ A ∪ A 0 A -1 = { e , e, r -1 , n | e, e , r, n ∈ Ā}
The previous definition of Ā satisfies this definition, either with ⊆ as an order or with as the only confidence grade. The most widely used structure is based on the real number unit interval [0 1], but some systems simply use the boolean lattice. It is convenient to interpret the greatest element as the boolean true and the smallest element as the boolean false. Some other possible structures are fuzzy degrees, probabilities or other lattices. [START_REF] Gal | A framework for modeling and evaluating automatic semantic reconciliation[END_REF] has investigated the structure of fuzzy confidence relations. Below, we simply consider the unit interval with the usual arithmetic operations.

Example 8 (Normalisation with confidences). For instance, Stadt{<} .8 Town, Stadt{<, =} .9 Town is a normalised alignment (if it is added StadtΓ Town), which is interpreted (still conjunctively) as: I am confident with .8 that Stadt is strictly subsumed by Town, and confident with .9 that Stadt subsumed or equivalent to Town. If the confidences were stripped down, this conjunctive statement would be reduced to Stadt{<}Town. This corresponds to having the confidences set to 1. Similarly, the alignment:

Stadt{<} .9 Town, Stadt{<, =} .8 Town is not minimal and can be reduced to Stadt{<} .9 Town. This is because {<} ⊆ {<, =} and .9 ≥ .8, hence Stadt{<} .9 Town entails Stadt{<, =} .8 Town.

Designing operators for merging two alignments with disjunctive relations and confidence, is more open than considering the disjunctive relations alone. The implementation of the aggregation operators can differ as well as the measure for aggregating confidence. Instead of applying a union or intersection, each pair of entities will be assigned for each disjunction of relation (returned by a matcher) a confidence measure which will result in the aggregation of the confidence of all other matchers. There are many different ways to aggregate matcher results depending on confidence [START_REF] Euzenat | Ontology matching[END_REF]:

-Triangular norms (min, weighted products) are useful for selecting only the best results in case of competing alignments;

-Multidimentional distances (Euclidean distance, weighted sum) are useful for taking into account all dimensions in case of complementary alignments; -Fuzzy aggregation (min, weighted average) is useful for aggregating competing algorithms and averaging their results; -Other specific measures, e.g., ordered weighted average, may also be used.

The natural aggregation measure is the conjunctive one induced by the normalisation procedure:

A ∧ A = Ā ∪ Ā However, other aggregation operations can be designed from a confidence aggregation function f and a relation combination × as:

A × f A = { e, e , r × r , f (n, n ) | e, e , r, n ∈ Ā, e, e , r , n ∈ Ā }
The × operation be, for instance, ∩, ∪ or id (which applies only if both sets of relations are equal). We have presented it with two alignments, but this extends straightforwardly to n alignments. Which cannot be reduced.

Ideally, we would like that these aggregation functions preserve the opportunity given in Section 4 to have different operations usable in different situations.

This works well for min and weighted product functions together with intersection.

Property 1 (Reduction to intersection). The (normalised) weighted products and min functions, if applied to correspondences with confidences in {0, 1} with ∩ computes ∩.

This works well for intersection because the methods used have 0 as an absorbing element. Since the other operations do not have a (upper) absorbing element, the confidence that they return are not necessary equal to 1 (or ).

Property 2 (Reduction to union). The weighted sum, Euclidean distance and other instance of the Minlowski distance, if applied to correspondences with confidences in {0, 1} and ∪ computes ∪. However, the confidence value assigned to the resulting correspondences may not be .

Related work

There are very few papers about alignment relations in the literature. [START_REF] Bennacer | Formalizing mappings for OWL spatiotemporal ontologies[END_REF] uses a spatial relation algebra for the purpose of expressing correspondences between spatio-temporal ontologies. However, the relations are only used in the ontology language and the alignment relations are still the classical = and ≤ relations. [START_REF] Sotnykova | Semantic mappings in description logics for spatio-temporal database schema integration[END_REF] went one step further by explicitly considering a set of base relations similar to A5, but they do not consider using disjunction of relations as alignment relations (hence most of what is in this paper does not apply).

In database schema matching, the notion of mapping composition is prominent and has been thoroughly investigated [START_REF] Madhavan | Composing mappings among data sources[END_REF]. The problem there is to design a composition operator that guarantee that the successive application of two mappings yields the same results as the application of their composition [START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF]. The approach is relatively different since relations in this context are always subsumption and their applications involve manipulating the ontology language instead of the alignment language (here the alignment relations). It is even shown that in general the result of composition may require a stronger language than the alignment language (hence the actual result of the composition is not an alignment). The approach taken with composition in algebra of relations is weaker -results are always in the alignment language -but is not complete.

[17] suggests to transform the XML schema matching problem into a constraint optimisation problem. Constraint optimisation problems are constraint satisfaction problems whose solutions maximise a quantity. Though the authors do not consider algebras of relations, this work suggests to use them, since Allen's constraint propagation algorithm [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] is an instance of a constraint propagation algorithm (which can be generalised as arc-consistency).

Conclusions

Starting from the need to express disjunctions of relations between ontology entities, we have introduced algebras of relations as a tool for expressing alignment relations. We have shown that this tool can easily express the most common relations used in ontology matching. However, algebras of relations are very flexible tools and new ones can be created for specific applications, e.g., mixing set and mereological relations.

What makes algebras of relations particularly attractive, besides expressing disjunctions is their ability to support genuinely other needed operations, and, in particular:

-conjunction and disjunction operators can be used as a more flexible means of combining alignments; -composition had already been identified as the perfect tool for composing alignments: disjunction in alignments enables the expression of composition results as alignments; -it can also be used for reasoning directly at the algebraic level and detecting valid consequences and constraints on alignments, before even considering the deeper (onto)logical level; -weakening algebras can be used for combining alignments expressed in different (but compatible) algebras of relations.

This paper is a theoretical paper. We have no experimental setting to demonstrate the superiority of the approach over an eventual previous one. However, we claim that it conveniently demonstrate the benefits brought by the use of algebra of relations within ontology alignments. Algebra of relations is a well-studied domain and the fact that it can apply straight away to ontology alignment is very precious in a context when we want to freely share alignments and combine matching methods on the web.

No implementation is available yet: the full support for algebra of relations remains to be implemented in our Alignment API [START_REF] Euzenat | An API for ontology alignment[END_REF]. Implemented operations would effectively compute composition so as to be able to provide new alignments to clients.

ΓFig. 1 .

 1 Fig. 1. The lattice of 31 disjunctive relations in A5.

8 = A 4 ∨ A 6 :

 846 r ∩ r | e, e , r ∈ Ā, e, e , r ∈ Ā } as well as additional operators such as disjunction and converse of alignments: A ∨ A = { e, e , r ∪ r | e, e , r ∈ Ā, e, e , r ∈ Ā } A -1 = { e , e, r -1 | e, e , r ∈ Ā} Within this paper, alignments are always presented in a reduced way, i.e., without trivial e, e , Γ correspondences added by normalisation. Example 4 (Alignment aggregation). Consider two alignments A 3 and A 5 , resulting from two different matchers which match ontologies using different features for ruling out correspondences (A 3 is on the left, A 5 on the right): Konstruktion{⊥}Municipality Stadt{<}Town Stadtgebiet{>, }Municipality Stadtgebiet{⊥, }Municipality Since these matchers provide competing alignments between ontology o and o , their result can be aggregated conjunctively. The result A 6 = A 3 ∧ A 5 , is given below as the left-hand side alignment: Konstruktion{⊥}Municipality Stadt{<}Town Stadt{=, <, >, }Town Stadtgebiet{ }Municipality Stadtgebiet{⊥}Municipality This alignment is aggregated with the right-hand side alignment A 4 . Since they provide evidence for alignments from different perspective, they are aggregated disjunctively, yielding A Stadt{=, <, >, }Town Stadtgebiet{ , ⊥}Municipality

  r • r | e, e , r ∈ A, e , e , r ∈ A } One can compose an alignment with itself (self-composition) through: A 2 = A • A -1 • A. This operation may provide new correspondences. Example 5 (Composing alignments). The alignment A 3 of Example 4, is the result of the composition of alignments A 1 and A 2 of Example 2:

Fig. 2 .

 2 Fig. 2. The reasonable weakenings of A5 ( ⊥ = {<, >, =, } and < >= {<, >, }).

Example 9 (

 9 Aggregation with confidence). Consider two alignments A 9 and A 10 containing the following correspondences (A 9 is on the left, A 10 on the right): Stadt{=, <} .5 Town Stadt{=} 1.0 Town Stadt{=, ⊥} .2 Town Stadtgebiet{⊥} .1 Municipality Stadtgebiet{⊥, } .2 Municipality Applying ∩ min (A 9 , A 10 ) yields, once normalised, the following correspondences: Stadt{=} 1. Town Stadtgebiet{⊥, } .2 Municipality Stadtgebiet{⊥} .1 Municipality The same operation with ∪ and weighted sum (weight being 1/3 and 2/3), would yield: Stadt{<, =} .83 Town Stadt{⊥, =} .4 Town Stadtgebiet{⊥, } .16 Municipality

  Definition 2 (Alignment). Given two ontologies o and o , an alignment is made up of a set of correspondences between pairs of entities belonging to Q L (o) and Q L (o ) respectively. Stadtgebiet, i.e., a Urban area, is more general than a Ville, i.e., a Town. A 2 expresses that a Commune is more general or equivalent to a Municipality and Ville overlaps withMunicipality, i.e., that both concepts have common instances but none is more general than the other.

	Example 2 (Alignment). Consider two alignments A 1 and A 2 , relating respectively the
	German to the French ontology and the French ontology to the British one, containing
	the following correspondences (A 1 is on the left, A 2 on the right):
	Konstruktion⊥Commune	Commune ≥ Municipality
	Stadtgebiet > Ville	Ville Municipality
	This means that A 1 considers that a Konstruction, i.e., a Building, is disjoint from a
	Commune, i.e., a Ward, and a

  The first simple application of Table 1 occurs when composing Konstruktion {⊥} Commune and Commune {>, =} Municipality, then it can be deduced that Konstruktion {⊥} Municipality because {⊥} • {>, =} = (⊥• >) ∪ (⊥• =) = {⊥}. Things can be more complex, when composing Stadtgebiet {>} Ville and Ville { } Municipality, then Table 1 allows to deduce that Stadtgebiet {>, } Municipality

[START_REF] Ligozat | What is a qualitative calculus? a general framework[END_REF] shows that a weaker structure than algebras of relations, non associative, can be used in most of the purposes of qualitative calculi. However, we will need associativity later.

An antichain is a set of relations such that no one is comparable to the other.

Acknowledgements

This work started from a discussion with José Ángel Ramos and Asunción Gómez Pérez at Universidad Politécnica de Madrid. José Ángel provided further comments on the previous version of this paper. It also received comments from Jérôme David and Pavel Shvaiko.