Interoperability is a strong requirement in open distributed systems and in the Semantic Web. The need for ontology integration is not always completely met by the available ontology matching techniques because, in most cases, the semantics of the compared ontologies is not considered, thus leading to inconsistent mappings. Probabilistic approaches has been proposed to validate mappings and solve the inconsistencies, based on a mapping con dence measure. As probabilistic approaches su er from the lack of well-founded likelihood measures of mapping correctness, we propose a validation approach based on fuzzy interpretation of mappings, which better models the notion of degree of similarity between ontology elements. Moreover, we describe a conict resolution method which computes the minimal sets of con icting mappings and can be the ground of di erent validation strategies.
In the context of the Semantic Web, the available information is organized in
ontologies. Ontologies are controlled vocabularies describing objects and relations
between them in a formal way, and have a grammar for using the vocabulary
terms in order to express something meaningful within a speci ed domain of
interest. However, ontologies themselves can be heterogeneous: given two
ontologies describing a reference domain, the same real entity can be denoted in
the two ontologies with di erent names or it can be de ned in di erent ways (an
entity of one ontology may be the union of two of the entities of the other
ontology) whereas both ontologies may be expressed in di erent languages, though
expressing the same knowledge. In order to achieve the goal of ontology
interoperability, we need to align heterogeneous ontologies by (semi-)automatically
discovering mappings between the elements in two di erent ontologies. Most of
the existing matching techniques do not take into account the semantics of the
compared ontologies, therefore the resulting mappings can not be interpreted as
semantic relations among the ontology elements, which is a necessary condition
to perform integration and, subsequently, query answering over the integrated
schema. Recently, several studies have focused on mapping validation with
respect to the semantics of the ontologies involved and, at the same time, by
maintaining the uncertain nature of mappings. In [
Probabilistic approaches for mapping validation su er of limitations due to
the nature of mappings and the way the probability values are computed. Our
idea is to adopt a completely di erent interpretation in order to be able to
validate mappings even in the absence of a precise semantics and in the presence
of uncertainty. Assuming that an ontology mapping states the generic similarity
of two concepts, we can assert that the objects modeled by the rst concept
can be also modeled by the second concept to a certain degree. In other words,
the individuals of the rst concept belong to the second concept with a
certain degree, which is exactly the semantics of fuzzy membership functions. The
degree of membership is determined by the strength of the similarity relation,
computed by the same matching technique which produced the mapping. By
using the acquired mappings to create fuzzy individual assertions, we provide
a formal interpretation of mappings. Moreover, on the grounds of the Fuzzy
Description Logics theory, we are able to perform reasoning on the integrated
ontologies in order to detect and solve inconsistencies by mapping re nement,
which is another di erence compared to [
Ontology Mappings and Fuzzy Interpretation
In this section, we provide an introduction to a fuzzy extension of Description
Logics (DL) by adding degrees to DL facts; we call this extension f-DL. This
extension is based on Fuzzy Sets and Fuzzy Logic [
As usual fuzzy DLs are de ned by an alphabet of distinct concept names
(class names ) C, role names (property names ) R and individuals I. The set
of roles (properties) is de ned as R [ fR j R 2 Rg, where R represents the
inverse of R. Elementary descriptions are atomic concepts and atomic roles, and
by using concept constructors we can de ne complex concept descriptions. More
precisely, if A; C; D 2 C, R; S 2 R and p 2 N, where A is an atomic concept,
C; D are complex concepts, and S is an atomic role [
C; D ! ? j > j A j C t D j C u D j :C j 8R:C j 9R:C j pS j pS
A fuzzy DL Knowledge Base is a triple = hT ; R; Ai, where T is a TBox, R a RBox and A an ABox. A TBox is a set of concept subsumption axioms of the form, C v D and concept equivalence axioms of the form C D, where C; D are f-SHIN -concepts. An RBox is a set of transitive role axioms of the form Trans(R) and role subsumption axioms of the form R v S, where R; S are fSHIN -roles, while an ABox is a set of fuzzy concept and fuzzy role assertions of the form (a : C)./n and ((a; b) : R)./n, or individual equalities and inequalities of the form a = b or a 6= b, where a; b 2 I, ./ 2 f ; >; ; <g and n 2 [0; 1].
The semantics of f-DL are based on fuzzy interpretations. A fuzzy interpretation I is a pair I = ( I ; I ), where the domain I is, like the crisp case, a non-empty set of objects and I is a fuzzy interpretation function, which maps { an individual name o to an object oI 2 I , { a concept name C to a membership function CI : I ! [0; 1] 1, and { a property name R to a membership function RI : I I ! [0; 1].
Complex f-SHIN -concepts, roles and axioms are interpreted by extending fuzzy interpretation, making use of fuzzy set theoretic operators and notions, like subsethood, from the fuzzy set literature. The complete semantics are presented in Table 1, where sup is the supremum, inf is the in mum, c is a fuzzy complement, t is a fuzzy conjunction (t-norm), u is a fuzzy disjunction (t-conorm) and J is a fuzzy implication.
A fuzzy knowledge base is satis able i there exists a fuzzy interpretation I which satis es all axioms in . Basic inference problems in f-DL are: (i) check if a fuzzy knowledge base is consistent i.e. has a model, (ii) check if D subsumes C w.r.t. , i.e. j= C v D, (iii) check if a is an instance of C to degree ./n, i.e. j= a : C./n, where ./ 2 f ; >; ; <g and (iv) determine the greatest lower bound of a w.r.t. , denoted glb( ; a), where glb( ; a) = supfn j j= a ng. 2.1
In order to achieve ontology interoperability heterogeneous ontologies should be (semi-)automatically aligned. The problem called \Ontology Alignment" or \Ontology Matching" can be described as follows: given two ontologies each describing a set of discrete entities (which can be classes, properties, predicates, etc.), nd the relationships (e.g., equivalence or subsumption) that hold between these entities. In a more formal way we could say that a mapping M is a set of tuples
mi = hCi; Ci0; ni; Rii for i 2 I, where 1 For instance, given an object a 2 I and a class name C, CI (a) gives a degree of con dence (such as 0.8) that the object a belongs to the fuzzy concept C. Bottom Top Intersection Union Complement Existential Restriction Universal Restriction Min Cardinality Restriction
DL Syntax ? > C u D C t D :C 9R:C 8R:C
nR SubClass Equivalent Classes SubRole Class Individual Role Individual Disjoint Classes Transitive Object Property
C v D C D R v S o : C./n (o; o0) : R./n
C v :D
Trans(R) Max Cardinality Restriction nR
( nR)I(a) =
Another way to represent these relations using bridge rules, as used in distributed
description logics [
Ci ! Ci0 : n
Ci v! Ci0 : n
Ci w! Ci0 : n
In order to take into account the uncertain and fuzzy nature of the mappings we de ne a fuzzy mapping as follows.
De nition 1 (Fuzzy Mapping). Given two ontology elements Ci and Ci0, a fuzzy mapping f mi = hCi; Ci0; ni; Rii is a mapping mi, whose value ni denotes the degree that the semantic relation Ri holds between Ci and Ci0, where Ri can be one of equivalence ( ) or subsumption (v, w).
This way the mappings are formalized as fuzzy knowledge. The basic idea behind
the formalization of mappings as fuzzy knowledge is to use the mappings so as to
create fuzzy individual assertions. In order to do that we must provide semantics
for the mappings and to do so we will use the Fuzzy Set Theory [
I j= Ci ! Ci0 : ni () 8b:b 2 CiIc ! Ci0I (b) = ni I j= Ci v! Ci0 : ni () 8b:b 2 CiIc ! Ci0I (b) I j= Ci w! Ci0 : ni () 8b:b 2 CiIc ! Ci0I (b) ni ni
The above de nitions imply a procedure by which we can transfer individuals from the source ontology O to the target ontology O', creating a set of fuzzy assertions AM . This procedure will be described in more detail in the following. 2.2
In this section we provide a short introduction to the Fuzzy Reasoning Engine
FiRE [
Our approach to mapping validation is articulated in four phases 1. Ontology mapping acquisition. In this phase, we acquire mappings produced by using an ontology mapping system; the matching system can rely on syntactic, structural or even semantic matching techniques. 2. Fuzzy interpretation of mappings. In this phase, the acquired mappings are interpreted as fuzzy assertions as presented in Section 2.1. 3. Fuzzy reasoning over mappings. In this phase, the ontology obtained by enriching the second ontology of the mapping with fuzzy individual assertions produced with the help of the mappings is checked for consistency by means of a fuzzy reasoning system. 4. Mapping validation and revision. In this phase, mappings are revised according to the reasoning results; mappings causing inconsistencies within the new ontology are re ned and given a new strength.
In more detail the validation procedure, takes as input a mapping set (M ) together with the respective ontologies (O1 and O2) and creates a new mapping set (M 0), which includes re ned mappings or discarded ones.
The main algorithm is described by Algorithm-1. Firstly, M is ordered by descending order. In this way, we rst consider the stronger mappings for which similarity is higher. Then, the algorithm examines each mapping with the aforementioned order and calculates a strength. If a mapping was re ned Algorithm 1 M 0 := fuzzyValidation( M ) input: a mapping set M , and the mapped ontologies output: a validated mapping set M 0 while the degree of some mapping has changed do sort M w.r.t. the strength ni of each mapping mi = fCi; Ci0; ni; Rig 2 M M 0 := ; for mi 2 M do newStrengthi := computeStrength( mi ) if newStrengthi is di erent than ni then mi := fCi; Ci0; newStrengthi; Rig break end if if newStrength is non zero then
add mi to M 0 end if end for end while return M 0 then the same method is applied again for the old set of mappings plus the new re ned one, since the new degree might cause a new con ict that did not occur before. This is performed iteratively until all the mappings have been used and no inconsistencies occur. The nal set of mappings is saved in M 0.
The method that re nes the degree of a mapping is described by Algorithm2 and proceeds as follows: A new ontology O0 = hT 0; R0; A0i is created, where T 0 = T2, R0 = R2. The ABox of the new ontology is gradually constructed from the ABox of O2 and by using the current mapping in order to transfer individuals from ontology O1. More formally, A0 = A2 [ AM , where AM is de ned as follows: AM = fa : Ci0 fa : Ci0
n j hCi; Ci0; n; vi 2 M; O1 j= Ci(a)g[ fa : Ci0 = n j hCi; Ci0; n; =i 2 M; O1 j= Ci(a)g[
n j hCi; Ci0; n; wi 2 M; O1 j= Ci(a)g.
As it can be noted by the above de nition, both the explicit as well as inferred
assertions are taken into consideration (O1 j= Ci(a)). To do so we make use of a
classic DL reasoner and more precisely in the current setting we have used Pellet
[
Algorithm 2 s := computeStrength( mi ) input: mi := fCi; Ci0; ni; Rig output: the new strength of the mapping for every individual of Ci (Ci(a)) do add a to Ci0 ! Ci0(a) check consistency of O2 if O2 is not consistent then remove all individuals of Ci added to Ci0 s := re neStrength(inconsistencyInfo) else
s := ni end if end for return s
v M obileDevice O2 : P hone v ElectronicDevice
CableP hone v P hone CellularP hone v P hone
CableP hone v :CellularP hone
Example. Consider two simple ontologies, O1 and O2, de ned as follows:
The two ontologies have been compared by adopting the linguistic component of
HMatch 2.0 [
Since the validation process works by translating mappings into fuzzy individual assertions, suppose that each concept of the two ontologies has at least one representative individual. In particular, we assume that mp1 is an instance of the concept M obileP hone and md1 is an instance of the concept M obileDevice. Sorted by the strength, one by one mappings are inserted into the second ontology as fuzzy individual assertions.
Following the example, the rst mapping to be added to O2 is mapping 4, which is translated into the assertion (CellularP hone(mp1), 1.0). Since the rst mapping does not cause an inconsistency, the procedure moves to the subsequent mapping (1), which is converted into (ElectronicDevice(md1), 0.7) and (ElectronicDevice(mp1), 0.7). The latter assertion violates the fuzzy DLs interpretation of subsumption (C v D () CI (a) DI (a)), therefore making the resulting ontology inconsistent. In this case, the solution is to increase the strength of ElectronicDevice(mp1) and ElectronicDevice(md1) to 1 in order to satisfy the semantic constraint ElectronicDeviceI (mp1I ) CellularP honeI (mp1I ). The same situation occurs when the assertions corresponding to mapping 2 are added into O2 and the same re nement is applied to restore consistency. At last, the assertion determined by mapping 3, i.e. (CableP hone(mp1), 0.4), causes an inconsistency because it does not satisfy the semantic constraint CableP honeI (mp1I ) 1 CellularP honeI (mp1I ). Giving priority to the stronger mapping, the latest assertion has to be re ned. Since the resulting strength would be equal to 0, the assertion corresponding to mapping 3 is de nitely dropped, and the mapping is removed as well. The result of the validation process is the following mapping set:
4
The validation process described in the previous section enforces the inconsistency detection and resolution by re ning the strength of the mappings. When a con ict arises, two or more mappings are involved and, to achieve the consistency, at least one of them must be re ned or removed. Generally the choice among the con icting mappings is not trivial because it should be driven by the semantics of the mapped elements. The decision is even a harder task when is performed automatically, therefore requiring e ective heuristics. Moreover, even when the choice is made by a human expert, there can be di erent correct decisions according to di erent criteria that can be adopted.
The proposed validation technique adopts a naive strategy which gives priority to the strongest mapping and forces the last added mapping to be re ned or deleted. This solution has the advantage of being e cient in terms of performances but does not always lead to the expected results. In fact, for instance, one may prefer to preserve the highest number of mappings instead of the strongest ones. The limitation is more evident if we consider mapping deletion as the only possible way to solve inconsistencies. For instance, consider the two ontologies de ned in the example of the previous section and assume to have the same mapping set but with the following strength values:
The con icting subsets of mappings in this con guration are (1,2,3) and (3,4), due to the violation of the fuzzy DLs interpretation of subsumption and negation, respectively. If we apply a restricted version of the validation procedure of Section 3 that allows only the deletion of inconsistent mappings, the inconsistency would be solved by deleting all the mappings except for mapping 3, which is the strongest one. In this case, it is clear that giving priority to the mapping with the highest value could be not always the expected choice.
To provide a better support for the resolution of mapping inconsistencies, we propose a di erent approach, namely the con ict resolution method, based on the complete analysis of the con icts. The underlying idea is to compute a degree of inconsistency of each mapping, i.e. a measure that re ects the number of times in which a mapping is involved in a con ict. To evaluate this degree, we consider the inconsistencies in all the possible mapping con gurations, that are the set P(M ) of all the subsets of the given mapping set, except the empty set and the singleton sets. More formally, given a set of mappings M and the set P(M ) P(M ) n fx 2 P(M ) j x = ; _ jxj = 1g , we de ne the con icting set C(M ) P(M ) as
C(M ) = fc 2 P(M ) j 9 m; m0 2 c such that m and m0 cause an inconsistencyg C(M ) is built by validating each subset si 2 P(M ) through the validation procedure of Section 3. If the resulting set s0i is equal to si then si does not contain any con ict and it is not included into C(M ). Otherwise, if s0i si then a mapping has been removed to solve an inconsistency, therefore si is added into C(M ).
We de ne the minimal con icting set MC(M ) of M as the collection of all minimal subset of mappings which contains a con ict:
MC(M ) = fmc 2 C(M ) j @ mc0 2 C(M ) such that mc0 mcg The degree of inconsistency im of a mapping m 2 M is de ned as follows: im = jfmc 2 MC(M ) j m 2 mcgj The assumption is that the higher is the degree of inconsistency of a mapping, the more bene t we will get by removing it from the mapping set. Therefore, the strategy behind this con ict resolution method is to preserve as much as possible the mappings by detecting and deleting those which participate in the highest number of con icts. After computing the degree of inconsistency, all the mappings are added into the second ontology as fuzzy individual assertions and the resulting ontology is checked for consistency. If an inconsistency is detected, the mapping with the highest degree of inconsistency is removed and the resulting ontology is again checked for consistency. The step is repeated until consistency is achieved.
Let us describe this method with the aforementioned set of mappings that are not correctly validated by the strength-based ordering approach. The computation of the degrees of inconsistency produces the following results: P(M ) = f(1; 2); (1; 3); (1; 4); (2; 3); (2; 4); (3; 4); (1; 2; 3); (1; 2; 4); : : :g C(M ) = f(1; 2); (1; 3); (3; 4); (1; 2; 3); (1; 2; 4); (2; 3; 4); (1; 2; 4); (1; 2; 3; 4)g MC(M ) = f(1; 2); (1; 3)(3; 4)g i1 = jf(1; 2); (1; 3)gj = 2; i2 = jf(1; 2)gj = 1;
All mappings are added into the resulting ontology and, subsequently, mappings 1 and 3 are removed before consistency is restored. Compared with the results of the strength-based ordering approach, this method detected the actual incorrect mapping (3) and produced the con guration with the largest number of mappings. Moreover, in the context of semi-automatic validation tools, the analysis performed with this method can report to the user the actual minimal sets of con icting mappings, in order to better support the decision process. 5
Recent work [
As a possible solution to cope with the uncertainty of automatically
discovered mappings, probabilistic techniques have been developed. The approach
presented in [
To be e ective, probabilistic approaches should be fed with values which
actually state the con dence of the relation, therefore computed on the basis
of well-founded statistical techniques or measures. This turns out to be a
relevant limitation because most of the matchmaking tools do not provide such
a measure but only a value representing the degree of similarity between the
mapped elements. The alternative we propose is to exploit the fuzzy
interpretation to handle the uncertainty of mappings but without relying on the con dence
values. In the ontology matching literature, fuzzy theories have been exploited
mainly with the aim of dealing with uncertainty during the process of
mapping discovery and not for validation. For instance, the method described in [
Regarding con ict resolution strategies, relevant work have been presented
in the eld of ontology repairing in order to provide debugging functionalities
for logically erroneous knowledge bases. In [
Other work in dealing with ontology mapping in the fuzzy context has been
presented in [
In this paper we have discussed the application of the fuzzy DLs theories to the problem of mapping validation as a di erent way of handling mapping uncertainty with respect to probabilistic approaches. As a result, we described a mapping validation algorithm based on fuzzy interpretation of mappings in order to detect inconsistencies. Similarly to previous work on mapping validation, the strategy to solve inconsistencies is a simple strength-based heuristics, i.e. the con icting mapping with the highest strength value is preserved. Although being a fast solution, this naive approach does not lead always to the expected con guration. To cope with possible di erent strategies, we proposed a con ict resolution approach which performs a thorough analysis of all possible inconsistencies and computes the minimal sets of con icting mappings.
The preliminary results show that the con ict resolution method is e ective
and can potentially be applied to any validation semantics (e.g. probabilistic,
fuzzy). Furthermore, other validation strategies can be built on top of it, for
instance a strategy to maximize the number of preserved mappings. Regarding the
complexity, it is obviously dependent on the number of mappings involved and,
without further optimizations, the method is applicable only on relatively small
alignments. Future work will be devoted to the development of optimization
techniques, in particular the goal is to reduce the number of mapping subsets to
be validated during the search for the minimal con icting sets. A possible way
of reducing the search space, and thus the combinatorial space, is to make some
approximations, like the one proposed in [