In this paper, we propose a general model of schema matching based on the following ideas: on the one hand, a schema is viewed as a context (namely as a partial and approximate representation of the world from an agent's perspective); on the other hand, a schema cannot be assigned any arbitrary interpretation, as the meaning of the expressions used to label nodes (and possibly arcs) may be constrained by shared social conventions or agreements expressed in some lexical or domain ontologies. Accordingly, the proposed schema matching method can be viewed as an attempt of coordinating intrinsically context-dependent representations by exploiting socially negotiated constraints on the acceptable intepretations of the labels as codi ed in shared artifacts like lexicons or ontologies.
In the literature, we nd many di erent approaches to the problem of schema matching, and each of them re ects a theoretical view on what a schema is (a graph, a linguistic structure, a data model, . . . ). In this paper, we propose a general model based on the following ideas: on the one hand, a schema can be viewed as a context in the sense de ned in [?] (a partial and approximate representation of the world from an agent's perspective); on the other hand, a schema cannot be assigned any arbitrary interpretation, as the meaning of the expressions used to label nodes (and possibly arcs) may be constrained by shared social conventions or agreements expressed in some lexical or domain ontologies. Accordingly, a schema matching method can be viewed as an attempt of coordinating intrinsically context-dependent representations by exploiting socially negotiated constraints on the acceptable intepretations of the labels as codi ed in shared artifacts like lexicons or ontologies.
Our claim is that this type of approach may also provide a general view on the relation between contexts and ontologies. The idea is the following: contexts are representations which encode an agent's point of view; to be shared or communicated, these representations need to be linguistically expressed; however, this linguistic representation cannot be arbitrary, otherwise agents would never succeed in cokmmunication; lexical and domain ontologies are the rei cation ? Part of the material for this paper was developed in collaboration with Stefano
Zanobini as part of his PhD work. of partial and evolving agreements achieved in a linguistic or in other types of communities on the use of terms used for communication (perhaps in limited domains).
The paper is structured as follows. First, we present the intuitions underlying our approach. Then we show how these intuitions are captured in a formal model. Finally we argue that this model can also be used to explan what other approaches to schema matching do. 2
Let us start with a few general de nitions.
De nition 1 (Schema). Let Lext be a set of labels. A schema S is a 4-tuple hN; E; labN ; labEi, where hN; Ei is a graph, labN : N ! Lext is a function that associates each node with a label in Lext, and labE : E ! LNL is a function that associates each edge to a label in Lext [ ;.
In this de nition, Lext is the language used to externalize a schema outside an agent's mind (e.g. for publishing the schema and sharing it with other agents). In many real situations, it may be a subset of some natural language. For example, in most web directories, the communication language is basically the portion of English which is needed to label the directory categories, and the sign > to denote the sub-category relation (e.g. Music > Baroque > Europe is a subcategory of Music > Baroque)
Now we need to capture the intuition that an agent a may associate a set of
objects to a schema element e based on her understanding of the meaning of e,
and that di erent agents may have a di erent understanding of e. Let a1 and
a2 be two agents and Lext a suitable communication language. We now
introduce the notion of a representation language for an agent, namely the internal
(mental?) language which represents agents know about their environment. Let
Li be the representation language of the agent ai (where i = 1; 2), W a set of
worlds, and C a set of contexts of use. Intuitively, W is the set of all possible
interpretations of Lj , and C represents a collection of distinct contexts of use
of expressions belonging to Lext (C is necessary to model the fact that many
communication languages, including natural languages, are polysemous, namely
the same word may have a di erent meaning in di erent contexts of use). We do
not make any special assumption on Lext and Lj ; the only important
requirement is that they are distinct { and possibly di erent { languages. For the sake
of this paper, we will assume that the representation languages are some sort of
Description Logic (DL) language (see [
The connection between schema elements and data happens in two steps: in the rst, we take the speci cation of a schema element e in Lext and build the representation of its meaning in Lj (given a context of use c); in the second, we provide an interpretation function from the resulting expression of Lj into a set of objects in the domain of W .
The rst step is formalized by the following translation function. De nition 2 (Translation function). Let Lj be a representation language, Lext a communication language and c a context in C. The translation function Tcj : Lext ! Lj is the function which associates an expression of Lj to an expression of Lext when used in c.
We notice that the translation function is indexed with an agent's name, as it re ects the way such an agent assign a (subjective) meaning to the (public) expressions of a communication language. In the following, we will use the notation T j to denote the family of functions fTcj j c 2 Cg.
The second step is formalized by the following projection function. De nition 3 (Projection function). Let Lj be a representation language and w 2 W . The projection function P wj : Lj ! 2w is a function which, for any possible world w, associates an extension to any term of Lj .
In the following, we will use the notation P j to denote the family of functions fP wj j w 2 W g.
To model the fact that agents may have domain knowledge about the concepts which they associates to schema elements, we introduce the notion of an agent's ontology, expressed as a set of axioms in the agent's representation language: Oj = fti v tk j ti; tk 2 Lj g1.
Finally, an agent aj which uses Lext as a communication language is de ned as follows: De nition 4 (Agent). An agent ajLext = T j ; Pj; Lj ; Oj is a quadruple, where T j is a family of translation functions, P j is a family of projection functions, Lj is the agent's representation language, Oj is the agent's knowledge, and the following holds: 8w 2 W ti v tk 2 Oj ) P wj(ti)
P wj(tk)
Now we have all the necessary building blocks for de ning the formal object of schema matching in this model. 3
The main idea of our model is that in no real world sitation one can guarantee
that two agents share meanings just because they share a communication
language. Indeed, the notion of shared meaning is not available (meaning is always
mediated through concepts, and therefore partially private). Therefore, to model
schema matching, we need to introduce a notion of agreement which does not
1 For the sake of simplicity, we assume that the agent knowledge can be represented
as a set of entailment axioms between concepts. Notice that this formalization of the
knowledge basis is not a novelty, but it is the standard one used in Description Logics
[
P w1(Tc1(t1)) R P w2(Tc2(t2))
Imagine, for example, that R is an equivalence relation and t1 = t2 = 'cat'; then the de nition above says that two agents are coordinated with respect to the use of the word `cat' (in English) in a context of use c if, for any world w 2 W , they associate to it the set of objects belonging to the domain of w (via translation and projection).
In what follows, we will use the notation coord(a1; a2; t1; t2; R; c) to denote that the agents a1 and a2 are semantically coordinated on t1, t2 with respect to R in the context c.
We now introduce a syntactic notion of mapping across schemas: De nition 6 (Mapping). Let S1 = N1; E1; lab1N ; lab1E and S2 = N2; E2; lab2N ; lab2E be two schemas and < = fr1; : : : ; rng be a set of binary relations which may hold between elements of the two schemas. A mapping MS1P !S2P is a set of mapping elements hn1; n2; rii, where n1 2 N1, n2 2 N2, and r 2 <.
We say that a mapping element m = hn1; n2; R; qi is correct if the two agents a1 and a2 are semantically coordinated with respect to n1, n2 and R, in a context c:
schemas S1 and S2. MS1!S2 is correct if and only if, for any mapping element m = hn1; n2; ri 2 MS1!S2 , it holds that:
coord(a1; a2; n1; n2; r; c)
To illustrate the generality of the model, consider the two following cases. In
the rst, we imagine that a1 and a2 are the same agent; in this case, semantic
2 Compatibility here refers to a precise formal notion which was de ned in [
Many theoretical results can be used to prove that semantic coordination (and therefore the correctness of a mapping) can't be directly checked, as it would require knowledge on what any agent really means by a word in a context, and this would be equivalent to look into an agent's mind. However, in this section we show that the condition of semantic coordination can be (and actually is) approximated by three types of default rules which are used by agents to \jump to the conclusion" that semantic coordination holds. 4.1
The rst type of default rule has to do with the used of a communication language Lext in a community of agents. The idea is the following. Take any two expressions t1 and t2 of Lext, and a family R+ of relations which connect some syntactic features of any two expressions of Lext (e.g. string identity, substring, permutations of strings, and so on). Now suppose that we have a \table" associating the elements of R+ with a family of set{theoretic relations R. The syntactic default rule (SDR) says that, whenever r+ 2 R+ holds between t1 and t2, then r 2 R holds between the meaning of t1 and t2.
De nition 8 (Syntactic Default Rule). Let let a1 and a2 be two agents, t1 and t2 be two expressions of the language Lext, r+ a relation between expressions of Lext, and r the set-theoretical relation which corresponds to the syntactic relation r+. Then: if t1 r+ t2
in a context c then coord(a1; a2; t1; t2; r; c)
As an example, let t1 be the phrase `black and white images', t2 be the word `images' and r+ a relation holding two strings when one contains the other. Imagine that this relation is associated with set inclusion ( ). Then one would be allowed to conjecture that an agent a1 using the expressions `black and white images' is semantically coordinated with an agent a2 using the expression `images' with respect to set inclusion.
We should recognize that this default rule is extremely powerful and widely used even in human communication, in particular in the special case of a single term (we typically assume that, unless there is any evidence to the contrary, what other people mean by a word t is what we mean by the same word in a given context). The intuitive correctness and the completeness of this default rule essentially depends on the fact that a syntactical relation r+ be an appropriate representation of a set{theoretical relation r, and vice{versa, that a set{theoretical relation r is appropriately represented by some syntactical relation r+. But, in general, polysemy does not allow to guarantee the correctned and completeness of this rule even in the trivial case when t1 = t2; and the existence of synonyms makes it quite hard to ensure completeness. 4.2
The second type of default rules says that agents tend to induce that they are semantically coordinated with other agents from a very small number of cases in which the agreed with another agent upon the use of a word. For example, from the fact that they agreed upon a few examples of objects called \laptops", they tend to induce a much stronger form of coordination on the meaning of the word \laptop". Formally, this pragmatic default rule can be expressed as follows:
of the language Lext, W a set of worlds, c 2 C a context of use and r a set{ theoretical relation. Furthermore, let wA 2 W be a nite world. Then: if Pw1A (Tc1(t1)) R P w2A (Tc2(t2)) then coord(a1; a2; t1; t2; r; c) For exmaple, if t1 = t2 = t and R is the equality symbol (`='), then the pragmatic default rule says that the restricted notion of semantic coordination can be inferred when two agents associate the same subset of the current world to t.
Pragmatic default rules are a very strong form of induction from the particular to the universal, and it is well-known that this not a valid pattern of reasoning. Indeed, if the positive examples are taken from a very small domain, then the two agents may happen to induce their coordination on equivalence simply because they never hit a negative example (lack of correctness); or vice versa they may fail to recognize their coordination simply because they could not nd any positive example (lack of completeness). 4.3
Finally, we discuss a third type of default rule, which can be stated as follows: if Tci(t1) r Tcj (t2); then 8w 2 W
P wi(Tci(t1)) r P wj(Tcj (t2)) where r would be any relation between concepts.
However, there are two major problems with this de nition: { rst of all, the premise of the rule does not make sense, as we do not know how to check in practice whether Tci(t1) R Tcj (t2) holds or not, as the two concepts belong to di erent (and semantically autonomous) representation languages; { second, it not clear how to determine a relation between concepts. Indeed, the syntactic and pragmatic default rule are based on conditions (relation between strings, and relations between sets of objects) which can be externally veri ed. But how do we check whether the concept of \cat" is subsumed by the concept of \mammal"?
A possible way out for the second issue may be that agents infer that such a relation holds (or does not hold) from what they know about the two concepts. This, of course, introduces an essential directionality in this rule, as it may be that two agents have di erent knowledge about the two concepts to be compared. So we need two distinct checks: and
if Oi j= Tci(t1) R Tcj (t2) then 8w 2 W
P wi(Tci(t1)) R P wj(Tcj (t2)) if Oj j= Tci(t1) R Tcj (t2) then 8w 2 W
P wi(Tci(t1)) R P wj(Tcj (t2))
Suppose we accept this asymmetry. How can we address the rst problem?
Senses and Dictionaries Here is where we introduce the notion of socially
negotiated meanings. Indeed, most communication languages (for example,
natural languages) provide dictionaries which list all accepted senses of a word
(WordNet [
However, we believe that dictionaries are crucial tools for communication languages, and indeed a linguistic community can be de ned as a group of speakers which agree on a common dictionary. Let us show how this idea can be used to de ne a surrogate of a conceptual default rule.
Lext, W a set of worlds, and c 2 C a context of use. Furthermore, let a1Lext and aLext be to agents of the same linguistic community. Then: 1
if SRc1(t) = SRc2(t) then coord(a1; a2; t; t; ; c) where SRci(t) is a function that, given a context c and a term t 2 Lext, returns a suitable sense for t from a dictionary (notice that this function is again parametric on agents).
Such default rules overcomes the rst issue of an the ideal conceptual default rule, i.e. comparing terms from di erent representation languages. Indeed, it is a veri able condition whether two agents refer to the same dictionary sense of a word in a given context of use. However, as it is, it can only be used to infer the restricted form of semantic coordination, as it applies only to a single term t of Lext. The general default rule should say that two agents a1 and a2 are semantically coordinated with respect to two expressions t1 and t2 of the communication language Lext, and with respect to a relation r, when the dictionary senses individuated by the sense retrieval function are r {related, where r is a relation between senses corresponding to the relation r between concepts. As we said at the beginning of this section, the relation r can be determined only with respect to an agent's knowledge about the relation between concepts corresponding to senses. To capture this aspect, we need to make a further assumption, namely that there is a mapping from the concepts is an agent's ontology Oj and dictionary senses. For example, if a1's ontology O1 contains the axiom `cat v animal' (where cat and animal are expressions of L1), then [O1] contains the axiom `sg v sh', where sg is the dictionary sense `feline mammal' associated to the word `cat' and sh is the dictionary sense `a living organism' associated to the word `animal'3. Now, we can introduce an extended lexical default rule.
De nition 11 (Lexical Default Rule Extended). Let t1 and t2 be two expressions of the language Lext, W a set of worlds, c 2 C a context of use and r a set{theoretical relation. Furthermore, let a1 and a1 be two agents belonging to the same linguistic community. Then: and
if [O1] j= SRc1(t1) r SRc2(t2) then coord(a1; a2; t1; t2; r; c)
w:r:t: [O1]
if [O2] j= SRc1(t1) r SRc2(t2)
then coord(a2; a1; t1; t2; r; c)
w:r:t: [O2]
3 The problem of lexicalizing the ontologies with respect to some dictionary is not
completely new. In computer science area, a lot of studies are dedicated to this
problem. Among them, in our opinion the most relevant approaches are described in
[
Essentially, this rule says that, if the sets of senses associated to two expressions t1 and t2 by the agents a1 and a2 are in some relation r with respect to the (lexicalized) knowledge of the agent ai (for i = 1; 2), then they are semantically coordinated with respect to t1, t2 and r. An example will better clarify the situation. Suppose t1 is `images of cats', and t2 is `images of animals'. Furthermore, imagine that the senses that a1 associates to t1 are hsq; sw; sei (SRc1(t1) = hsq; sw; sei), and that the senses that a2 associates to t2 are hsq; sw; sri (SRc2(t2) = hsq; sw; sri), where sq = `a visual representation', sw = `concerning', se = `feline mammal' and sr = `a living organism'. Imagine now that the (lexicalized) ontology [O1] contains the following two axioms: (i) `for each pair of concepts c; d, if c v d, then `a visual representation' `concerning' c is less general than `a visual representation' `concerning' d; (ii) `feline mammal' v `a living organism'. In this case, we can deduce that hsq; sw; sei `less general than' hsq; sw; sei, and, by applying the default rule, that the two agents are coordinated with respect to the relation `less general than' ( ). The same considerations can be done if we take into account the agent knowledge [O2] of the other agent.
As we announced at the beginning of the section, the extended lexical default
rule introduces a form of directionality in the notion of semantic coordination,
as the computation of the relation r between (lexicalized) concepts relies on an
agent's knowledge about them, and such knowledge may lack, or be di erent in
two di erent agents. However, as it was proved in [
The correctness and completeness of the lexical default essentially depends on the condition that two agents use the same function to associate dictionary senses to concepts in their internal representation and vice versa. Clearly, this condition cannot be guaranteed, as we can always conceive a situation where two agents point to the same dictionary sense sk for a term t, but then their internal representation of sk is di erent. However, this type of rule makes an essential use of socially negotiated tools, which provide a powerful extension to purely syntactic or pragmatic methods. 5
The model we propose leds to two general results. The rst is negative, as it
says that the condition required to prove that a mapping is correct (even in the
weak sense of semantic coordination) can never be formally proved. The second,
however, is that all the proposed matching methods can be classi ed into three
broad families, one for each default rule4:
4 Wever, see [
Syntactic methods: methods which try to determine a mapping by a purely
syntactic analysis of the linguistic expressions occurring in di erent schemas,
namely by comparing the properties of the strings that are used to label
nodes, and reasoning on their arrangement into a schema. Examples can be
found in [
The three types of methods have their own pros and cons. For example, syntactic methods are highly e ective, as they exploit and reuse very e cient techniques from graph matching; however, their meaningfulness is quite low, as they take into account a very super cial level of meaning which disregards potential ambiguities and cannot capture semantic relations between concepts which are not re ected in the pure syntax (for example, the relation between \cats" and \mammals"). Pragmatic methods are extremely meaningful (if two schemas were used to classify the same data set, and if the data set was representative of the domain of discourse, then the outcome of pragmatic methods would be always correct { independently from the analysis of labels and from the arrangement of nodes); however, the necessary preconditions (same data set and appropriate coverage) are extremely hard to match, and in practice we can never know when they are matched (we can only rely on statistical methods). Finally, conceptual methods { like pragmatic methods { have the advantage of being independent from the syntactical structure of the schemas, as in principle they can nd the correct relation between two schema elements even if labels are (syntactically) very di erent and nodes are arranged in di erent orders (when such an order is inessential from a semantic point of view). In addition, like syntactic methods, they have the advantage of being independent from the data contained into the schema elements. However, conceptual methods may fail in two crucial steps. First of all, the function which returns a sense for a word in a context of use is quite complex, and inherits most well-known issues related to word sense disambiguation in NLP. Second, an agent might lack part of the relevant knowledge to compute a mapping between two concepts. However, we should add that these methods are the only ones which are semantically incremental: one can always know why a mapping was not found (or why a wrong match was computed) and x the problem is a general way (and not, for example, by tuning some parameters, which may have bad e ects on the performance on di erent schemas).
Probaby to overcome some of these limitations, most actual methods are indeed hybrid, as they use techniques which are based on more than one default rule (for example, syntactic methods use lexical information from thesauri, and some conceptual methods use string matching techniques for improving the quality of their results).