Ontology mapping negotiation aims to achieve consensus among real-world entities about the process of transforming information between different models (ontologies). This paper describes a novel approach for ontology mapping negotiation, in which agents representing the real-world entities are able to achieve consensus among agents, about the mapping rules defined between two different ontologies. The proposed approach is based on utility functions that evaluate the confidence in a certain mapping rule. According to the confidence value, the mapping rule is accepted, rejected or negotiated. Since the negotiation process requires relaxation of the confidence value, a metautility function is applied, evaluating the effort made in relaxing (increasing) the confidence value, so that the mapping rule might be accepted. This convergence value is further applied by each agent in the evaluation of the global agreement.
The ontology mapping process aims to define a mapping
between a source and target ontology ( M: Os → Ot ). This
mapping is composed of a set of semantic bridges
(mapping rules) and their inter-relations. In our particular case,
the mapping and its semantic bridges are defined and
respect the SBO - Semantic Bridging Ontology [
Copyright 2005
Lift & Normalization
s
t
n
i
a
r
t
s
n
o
C
&
e
g
d
e
l
w
o
n
K
n
i
a
m
o
D
e
c
a
f
r
e
t
n
I
r
e
s
U
l
a
c
i
h
p
a
r
G
However, the semantic bridges resulting from these phases
represent the perspective of an agent on the semantic
relations defined between the entities of two ontologies. Due to
the intrinsic subjective nature of the ontologies, different
agents might have (and usually do have) different
perspectives on the same mapping scenario. This leads to conflicts
when interoperability occurs between such agents. A
consensus building mechanism is required to overcome these
conflicts. This mechanism corresponds to the Cooperative
Consensus Building module of MAFRA [
The user-based process is naturally applied in offline semantic bridging scenarios, i.e. when the semantic bridging phase is carried out and proofed by human domain experts, prior to any data exchange phase. Yet, in scenarios where online semantic bridging is required, an automatic consensus building mechanism is necessary, in order to supply the necessary consensus and speed up the interoperability process. Applications in context of the semantic web, information retrieval, web services, e-commerce and e-business, are application scenarios where ontology mapping and online semantic bridging are highly recommended. This paper addresses the problem of the automatic consensus building among two agents about an ontology mapping. The proposed mechanism, named ontology mapping negotiation, is based on the relaxation of the agents’ goals. The rest of this paper runs as follows: the next section presents the state of the art on the subject and related fields. The third section defines and constraints the ontology mapping negotiation problem according to the characterization of other types of negotiation. The fourth section takes into account the general notion of negotiation and introduces the conceptual approach to the problem. The fifth section describes the so called service-oriented architecture, envisaged as potential approach to the problem, namely the semantic bridging competencies already developed. The sixth and seventh sections describe the proposed solution. Finally, the conclusions section gives an overview of the proposed solution and emphasizes the major contributions of the paper.
Basically there is no research on the topic of ontology mapping negotiation. Instead, long run research exists in the general topic of negotiation, but it is fundamentally concerned with electronic commerce and resource allocation, which is poorly related to this problem. Some ontologybased negotiation research is running [2;3], but this is related to the application of ontologies in the traditional research areas of resource allocation or e-commerce. Supporting this premise, it has be noticed that in two of the most specific and relevant research events in the subject, MCN’2004 (Meaning Coordination and Negotiation Workshop at ISWC-2004) and MeaN’2002 (Meaning Negotiation Workshop at AAAI-02), while many research papers on ontology coordination (mapping) have been presented, none has been presented about ontology negotiation. While resource allocation and e-commerce research field may contribute to the negotiation of ontology mappings, no research exists about the specific characteristics of the negotiation of ontology mappings. In particular, it is necessary to determine and characterize the variables of the negotiation [4;5]: • Number and type of the negotiation entities. • Object of the negotiation (single/multi-object, uniqueness, granularity). • Domain of the negotiation (single/multi-attribute). • Characteristics and constraints of the negotiation process (visibility, honesty, mechanisms, information, strategy).
The definition and characterization of the negotiation context is the subject of the next section.
DEFINITION OF THE PROBLEM Any negotiation process aims to achieve a consensus that, explicitly or implicitly, corresponds to a commonly agreed contract between two entities.
While the contract is the goal of the negotiation, its content is subject to change during the negotiation and, in the end, it might not be the best possible contract for any of the agents. I.e., the optimal contract, defined by each of the agents, might not be achieved. Besides, it is good enough and advantageous to both agents so that it can be accepted by them. However, the optimal contract is a function that might not be explicitly or implicit defined by any of the agents. This is normally the case in ontology mapping, especially due to: • The differences between both ontologies. • The subjective nature of both ontologies. • The goal and requirements of the interoperability. In the context of this project, the real-world agents are represented by artificial agents that act on behalf of the realword agents during the negotiation. Considering that the real world agents (and therefore the artificial agents too) most probably have different perspectives on the ontology mapping scenario, one of the major questions is how to supply to the (artificial) agents the capability to converge on a consensus.
As in any negotiation process, the ontology mapping negotiation problem is mainly characterized by the type of object to negotiate. According to the developed semantic bridging phase [6;7], several types of objects might be considered: • The mapping ( M ), when the whole specification is subject of negotiation. • The semantic bridges, when each of the semantic bridges composing the mapping are subject of negotiation. • Parameters of the semantic bridges (e.g. the set of related entities).
However the more elements are subject of negotiation, the longer and more difficult it is to achieve a consensus among agents. Notice that a coarse grained negotiation (upon the mapping) is very fast, but a consensus is very hard to achieve, due to the lack of relaxation parameters. On the other hand, a fine grained negotiation (on the semantic bridges parameters) is easier to achieve, but it might be too long and therefore unfeasible.
Another important dimension to consider is the value associated to the object of negotiation. In the ontology mapping negotiation scenario, the value of the object is a function relating to the: • Correctness of the object, either the correction of the mapping, of the semantic bridges or of their parameters. • Pertinence of the object in respect to its envisaged application.
Other dimensions are also relevant for the negotiation process, but in order to reduce the negotiation space, the following constraints have been decided and stated: • The negotiation always occurs between two honest, non-bluffing agents. • The ontology mapping to agree on is unidirectional, which means that for a bi-directional conversation, two ontology mapping negotiation processes are required. • The negotiation objects are the semantic bridges only. It means that no internal parameter of the semantic bridge is independently negotiable.
The proposed negotiation process bases on the idea that each entity is able to derive the correct semantic bridges and decide which semantic bridges are required in order to interoperate with the other entity.
The suggested approach aims to further exploit the
multidimensional service-oriented architecture adopted in the
semi-automatic semantic bridging process described and
introduced in [
As referred previously, one of the major problems faced in negotiation scenarios relates to the difficulty in determining and supplying convergence mechanisms to the agents. In that respect, it is important to analyse the notion of negotiation.
Negotiation suggests the need for relaxation of the goals to be achieved by one (or both) of the intervenients in the negotiation, so that both achieve an acceptable contract, and an as good as possible one.
This introduces two distinct concepts: • The goals of the negotiation (the features of the contract to achieve). • The possibilities of relaxing the goals.
Mathematically, these concepts might be represented respectively as: • A utility function ( u ), representing the overall goal of the negotiation of the semantic bridge, in which each parameter of the function is a sub-goal of the negotiation:
u(p1 , p2 ,..., pn ) •
A meta-utility function ( U ) of the parameters of the utility function, defining the conditions in which the parameters may vary:
U(p1 , p2 ,..., pn ) Since the parameters of the utility function are the basic concept of this approach, it is fundamental to identify the possible elements that might play this role in the ontology mapping negotiation process.
It is our conviction that this role might be played by the same parameters that contribute to determine the correctness and completeness of the semantic bridges in the semantic bridging phase.
SERVICE-ORIENTED ARCHITECTURE In scope of the semantic bridging phase, this role is played by the Matches, which are the outcome of the similarity measurement phase. Matches represent the confidence that specific and specialized algorithms, called Matchers (e.g. Resnik, H-Match, MOMIS), have concerning the semantic similarity of two entities (one from the source ontology and the other from the target ontology). A match corresponds therefore to the following tuple: match := (Es , Et , Matcher, Confidence) : Es ∈ Os , Et ∈ Ot The se matches are then grouped together by Services into semantic bridges. Since each semantic bridge associates one single
Service that determines most of the characteristics of the semantic bridge, Services are perceived as the decision makers of the semantic bridging phase. Among others, Services define: • The matchers whose matches are considered for evaluation of the Service confidence in the semantic bridge. • The matches threshold ( tmatch ), below which the • • matches are not considered.
The confidence evaluation function ( u ) that evaluates the Service confidence in the semantic bridge ( csb ). The Service confidence threshold ( tr ), below which the semantic bridge is rejected.
Extrapolating this approach to other phases of the ontology
mapping process, the service-oriented architecture gives
rise to the so called multi-dimensional service-oriented
architecture [
a iu sn rb ra ttA T
SERVICE-ORIENTED NEGOTIATION The confidence evaluation function introduced above, generically referred to as utility function ( u ) plays a major role in the negotiation process. In fact, the proposed negotiation process suggests applying the confidence evaluation function as the utility function introduced in the hypothesis. Reusing the utility function reduces the efforts of Services parameterization and customization, two very human demanding tasks. However, it is our proposal to distinguish the semantic bridging from the negotiation phase, i.e. both phases occur consecutively. First, each agent performs its own semantic bridging process, generating a valid and meaningful mapping. After that, the set of semantic bridges composing the mapping are subject to negotiation between both agents.
The confidence value evaluated for each semantic bridge ( csb ) is then used as the negotiation value of the semantic bridge, corresponding to the agent confidence in proposing the semantic bridge to the other agent.
Several situations might occur when negotiating a specific semantic bridge: • Both agents propose the semantic bridge. • Only one of the agents proposes the semantic bridge.
In case last situation occurs, one of two situations occurs: • The other agent relaxes the confidence value and accepts the semantic bridge. • The other agent cannot relax the confidence value and rejects the semantic bridge.
In case last situation occurs, one of two situations occurs: • The agent proposing the semantic bridge cannot accept the rejection. In this case, the proposed semantic bridge is considered mandatory. • The agent proposing the semantic bridge can accept the rejection.
Since the goal of the process is to negotiate, it is important to provide the mechanisms so that the agents are able to propose, reject and revise their perspective on the semantic bridges. In fact, throughout the negotiation, it is important that agents relax their sub-goals in favour of a larger and wider goal. In this sense, the agent should not decide a piori on the acceptance/rejection of the semantic bridge. Instead, it should admit that certain semantic bridges are neither accepted nor rejected: they are negotiable. Consequently, it is necessary to define confidence categories, so that the agent can judge the semantic bridge pertinence to the mapping and to the interoperability. As a consequence, the rejection threshold borderline ( tr ) is insufficient and should be replaced by a multi-threshold approach: rejected not negotiable negotiable proposed mandatory
Mandatory threshold ( tm ) that determines the utility function value above which it is fundamental that the semantic bridge is accepted by the other agent. • Proposition threshold ( t p ), above which the semantic bridge is proposed to the other agent.
Negotiation threshold ( tn ), above which the semantic bridge is negotiable.
Therefore, five distinct categories of semantic bridges are defined according to the confidence value and the previously identified thresholds (Figure 3): • Rejected semantic bridges are those that csb < tr . Rejected semantic bridges are not even proposed to the user.
Non-negotiable semantic bridges are those that tr ≤ csb < tn . These semantic bridges are proposed to the user but unless he/she changes explicitly its category, they are not negotiated.
Negotiable semantic bridges ( SBn ) are those that tn ≤ csb < t p . It means that the agent confidence in the semantic bridge is sufficient to consider relaxing csb , but not enough to propose it to the other entity. In successful relaxing cases, the semantic bridge might be accepted. • Proposed semantic bridges ( SB p ) are those that tp ≤ csb < tm . It means the agent is confident enough upon the semantic bridge so that it proposes it to the other agent.
Mandatory semantic bridges ( SBm ) are those that csb ≥ tm . The agent is so confident of the pertinence and correctness of this semantic bridge, that the semantic bridge may not be rejected by the other agent.
It is therefore necessary to provide the mechanisms, so that the agent is able to revise its perception of the negotiable semantic bridges. These mechanisms should be embodied in the meta-utility function, as defined in the hypothesis, but not yet contemplated in the applied service-oriented approach of the semantic bridging phase.
The meta-utility function ( U ) is responsible for the definition of: • The parameters variation possibilities. • The priorities over parameters variation. tr confidence value tn tp tm
The conditions under which the variation may take place.
Through these elements, an updated confidence value is evaluated ( csub ) for the negotiable semantic bridges that were proposed by the other agent. If csub ≥ ta , the negotiable semantic bridge is categorized as tentatively agreed ( SBt ). Tentatively agreed semantic bridges are subject of a definitive decision phase.
Since the meta-utility function determines priorities and conditions for the variation of the parameters, it is possible that, for some variations, csub < ta . It is therefore necessary to iterate across the different variation possibilities, following the defined priorities and conditions. In case it is impossible to evaluate csub ≥ ta , the semantic bridge is not recategorized and is therefore rejected.
The effort made by the agent to re-categorize a semantic bridge to SBt varies according to the priorities conditions and values of the parameters. The meta-utility function is also responsible for the evaluation of this effort, named convergence effort ( esb ). This convergence effort value is further applied in the definitive agreement phase, as described in the next section.
The negotiation process described in this section exploits the service-oriented elements introduced in previous sections. The main idea behind the proposed negotiation process is that each agent must maximize the number of proposed semantic bridges ( SB p ) that are agreed to by the other agent.
The negotiation runs in two consecutive phases (Figure 4). The first one intends to build a consensus on mandatory semantic bridges ( SBm ). The second intends to build a consensus on the proposed semantic bridges ( SB p ). In the first phase, each agent proposes every sbm ∈ SBm to the other agent. If one sbm is not accepted by the other agent, the negotiation is closed without a consensus. In the second phase, each agent proposes every sb p ∈ SB p (not yet negotiated) to the other agent. Three situations may occur: SBm sb9 SB p sb1 sb6
sb2 SBn sb3
SBr sb7 sb4
sb2 sb1 sb8 sb7 SBn sb3 SBr sb6 sb4 sb9 sb5 SB p
1. The semantic bridge is also proposed by the other agent, thus categorized as agreed semantic bridge ( SBa ). This situation is represented in Figure 4 by the sb2 semantic bridge. 2. The semantic bridge is rejected by the other agent, and is therefore rejected ( sb6 ). 3. The semantic bridge is negotiable by the other agent, therefore categorized as tentatively agreed ( SBt ). This is the case of sb1 and sb7 semantic bridges.
When both entities categorize certain semantic bridge as negotiable, it is suggested that they forward the decision on a potential agreement to the user ( sb3 semantic bridge). The semantic bridges included in the third situation are subject to a definitive agreement phase in order to ensure that the proposed agreement is advantageous for both agents. The problem consists in deciding if the achieved agreement is globally advantageous (mapping granularity) and not only locally advantageous (semantic bridge granularity).
The problem arises due to the convergence efforts made during the negotiation process. For every sb ∈ SBn recategorized as SBt a convergence effort has been evaluated by the meta-utility function ( esb ). Convergence efforts should be considered inconvenient to the agent and treated as a loss. Instead, the agreement upon the same semantic bridge provided some profit for the agent when it is recategorized. This profit is denoted by the confidence value ( csb ). In that sense, the balance between profits and losses is a function such:
balance = ∑ csb −∑ esb : sb ∈ SBt Depending on the balance value the entity decides to agree on the negotiation agreement or to propose a revision of the mapping.
The balance value ultimately depends on the evaluation of the convergence effort made by the meta-utility function. In its simplest evaluation form, the convergence effort may u correspond to the difference between csb and csb (i.e. esb = csub − csb ).
However, the convergence effort should not be a linear measure between these two values. In fact, the linear difu ference between csb and csb it is typically too small in comparison to the values of csb . As a consequence, the balance value would be constantly positive.
A potential solution is the evaluation of the convergence effort using an exponential function defined under the parameters variation of the meta-utility function. Such exponential function would be helpful in taking into account the distinct efforts made in varying the different parameters in the meta-utility function. Instead, the difficulties in configuring and customizing the meta-utility function would be a considerable inconvenient.
The Multi-dimensional Service-Oriented Architecture advocates that ontology mapping system capabilities and its supported semantic relations are ultimately dependent on the type of transformations allowed/available in the system. Services represent the transformation capabilities in SBO, in semantic bridging and in the execution system, but the proposed architecture suggests that their capabilities should be expanded to support the requirements of other phases of the process. Services embody useful and eventually fundamental competencies for distinct phases of the process, which were originally an exclusive competence of the domain expert. Yet, instead of a monolithic structure representing such knowledge, multiple independent and dynamically evolving modules are used. However, these modules, instead of adopting a task-oriented structure, are orthogonal to multiple phases of the ontology mapping process, providing different functionalities depending on the requesting phase.
The service-oriented negotiation process introduced in this paper exploits such architecture. Services are empowered with competencies to negotiate the agreement on semantic bridges previously generated by the same Services. Services are able to revise their perspectives on the previously categorized semantic bridges, providing therefore the ability to relax their requirements in order to agree on a semantic bridge.
Consequently, it is our conviction that this paper will contribute with a set of novelties to the ontology engineering research area: • The conceptualization of the ontology mapping negotiation problem based on the utility and meta-utility functions. • The identification of matches as parameters of these functions. • The service-oriented negotiation process based on the categorization of semantic bridges.
While the negotiation process is relatively simple and the utility functions have already been developed from the semantic bridging process, the major effort consists in configuring and customizing the meta-utility function. Nevertheless, tests are being carried out in parallel with customization, so that effective results are expected in the near future.
This work is partially supported by the Portuguese MCTFCT project SANSKI (POCTI/2001/GES/41830). Many thanks to Paulo Sousa for the fruitful discussions we had about negotiation. Thanks to Ana Barata for her revisions of this text.