A Formal Investigation of Mapping Language for Terminological Knowledge

1 Motivation

The benefits of using ontologies as explicit models of the conceptualization underlying information sources has widely been recognized. Meanwhile, a number of logical languages for representing and reasoning about ontologies have been proposed and there are even language standards now that guarantee stability and homogeneity on the language level. At the same time, the need to represent mappings between different ontologies has been recognized as a result of the fact that different ontologies may partially overlap or even represent the same domain from different points of view [Bouquet et al., 2004]. As a result, a number of proposals have been made for extending ontology languages with notions of mappings between different models. Unlike for the case of ontology languages, work on languages to represent ontology mappings has not yet reached a state where a common understanding of the basic principles exists. As a consequence, existing proposals show major differences concerning almost all possible aspects of such languages. This makes it difficult to compare approaches and to make a decision about the usefulness of a particular approach in a given situation.

The purpose of this work is to provide a better understanding of the commonalities and differences of existing proposals for ontology mapping languages. We restrict our attention to logic-based approaches that have been defined as extensions of existing formalisms for representing Terminological Knowledge. In particular, we chose approaches that extend description logics (DL) with notions of mappings between different T-boxes. The rationale for this choice is the fact that DLs are a widely agreed standard for describing terminological knowledge. In particular, DLs have gained a lot of attention as a standardized way of representing ontologies on the Semantic Web [Horrocks et al., 2003].

Approach and Contributions

We encode the different mapping languages in an extended version of distributed first-order logic (DFOL), a logical framework for representing distributed knowledge systems [Ghidini and Serafini, 2000]. DFOL consists of two components: a family of first order theories and a set of axioms describing the relations between these theories. As most proposals for mapping languages are based on a subset of firstorder logic for describing local models and mappings with a particular semantics for the connections between models, these mapping languages can be expressed in distributed first order logic in the following way:

• restrictions on the use of first order sentences for describing domain models
• the form of axioms that can be used for describing relations between domain models
• axioms describing the assumptions that are encoded in the specific semantics of mappings

Encoding the different mapping approaches in first-order logic in this way has several advantages for an analysis and comparison of existing work. In particular it allows us to do a formal analysis and comparison of different approaches in a uniform logical framework. In the course of the investigations, we make the following contributions to the state of the art in distributed knowledge representation and reasoning:

• we show how the DFOL formalism can be used to model relations between heterogeneous domains (Proposition 1)
• we encode existing mapping approaches in a common framework, making them more comparable
• we make hidden assumptions explicit in terms of distributed first order logic axioms
• we provide first results on the relative expressiveness of the approaches and identify shared fragments

The paper is structured as follows. In section 2 we introduce distributed first order logic as a general model for describing distributed knowledge systems. We explain the intuition of the logic and introduce its syntax and semantics. In section 3 we describe how the different mapping approaches can be encoded in distributed first order language. Here we will focus on the representation of mappings and the encoding of hidden assumptions. In section 4 we compare the different approaches based on their encoding in DFOL and discuss issues such as relative expressiveness and compatibility of the different approaches and conclude with a summary of our findings and open questions.

2 Distributed First-Order Logic

This section introduces distributed first order logic as a basis for modeling distributed knowledge bases. More details about the language including a sound and complete calculus can be found in [Ghidini and Serafini, 2005].

Let {Li}i∈I (in the following {Li}) be a family of first order languages with equality defined over a non-empty set I of indexes. Each language Li is the language used by the i-th knowledge base (ontology). The signature of Li is extended with a new set of symbols used to denote objects which are related with other objects in different ontologies. For each variable, and each index j ∈ I with j ̸= i we have two new symbols x→j and xj→, called arrow variables. Terms and formulas of Li, also called i-terms and i-formulas and are defined in the usual way. Quantification on arrow variables is not permitted. The notation φ(x) is used to denote the formula φ and the fact that the free variables of φ are x = {x1, . . . , xn}. In order to distinguish occurrences of terms and formulas in different languages we label themwith their index. The expression i :φ denotes the formula φ of the i-th knowledge base.

The semantics of DFOL is an extension of Local Models Semantics defined in [Ghidini and Giunchiglia, 2001]. Local models are defined in terms of first order models. To capture the fact that certain predicates are completely known by the i-th sub-system we select a sub-language of Li containing the equality predicate, denoted as Lci , which we call the complete fragment of Li. Complete terms and complete formulas are terms and formula of Lci and vice versa.

Definition 1 (Set of local Models). A set of local models of Li are a set of first order interpretations of Li, on a domain domi, which agree on the interpretation of Lci , the complete fragment of Li.

As noted in [Franconi and Tessaris, 2004] there is a foundational difference between approaches that use epistemic states and approaches that use a classical model theoretic semantics. The two approaches differ as long as there is more than one model m. Using the notion of complete sublanguage Lc, however, we can force that the set of local models is either a singleton or the empty set by enforcing that Lc = L. Under this assumption the two ways of defining the semantics of submodels are equivalent. Using this assumption, we are therefore able to simulate both kinds of semantics in DFOL.

Two or more models can carry information about the same portion of the world. In this case we say that they semantically overlap. Overlapping is unrelated to the fact that the same constant appears in two languages, as from the local semantics we have that the interpretation of a constant c in Li is independent from the interpretation of the very same constant in Lj, with i ̸= j. Overlapping is also unrelated to the intersection between the interpretation domains of two or more contexts. Namely if dom1 ∩ dom2 ̸= ∅ it does not mean that L1 and Lj overlap. Instead, DFOL explicitly represents semantic overlapping via a domain relation.

Definition 2 (Domain relation). A domain relation from domi to domj is a binary relation rij ⊆ domi ×domj.

A domain relation from i to j represents the capability of the j-th sub-system to represent in its domain the domain of the i-th subsystem. A pair 〈d, d′ 〉 being in rij means that, from the point of view of j, d in domi is the representation of d′ in domj. We use the functional notation rij(d) to denote the set {d′ ∈ domj| 〈d, d′ 〉 ∈ rij}. The domain relation rij formalizes j's subjective point of view on the relation between domi and domj and not an absolute objective point of view. Or in other words rij ̸= rji because of the non-symmetrical nature of mappings. Therefore 〈d, d′ 〉 ∈ rij must not be read as if d and d′ were the same object in a domain shared by i and j. This fact would indeed be formalized by some observer which is external (above, meta) to both i and j. Using the notion of domain relation we can define the notion of a model for a set of local models.

Definition 3 (DFOL Model). A DFOL model M is a pair 〈{Mi}, {rij}〉 where, for each i ̸= j ∈ I: Mi is a set of local models for Li, and rij is a domain relation from domi to domj .

We extend the classical notion of assignment (e.g., the one given for first order logic) to deal with arrow variables using domain relations. In particular, an assignment a, provides for each system i, an interpretation for all the variables, and for some (but not necessarily all) arrow variables, as the domain relations might be such that there is no consistent way to assign arrow variables. For instance if ai(x) = d and rij(d) = ∅, then aj cannot assign anything to xi→.

Definition 4 (Assignment). Let M = 〈{Mi}, {rij}〉 be a model for {Li}. An assignment a is a family {ai} of partial functions from the set of variables and arrow variables to domi, such that:

1. ai(x) ∈ domi; 2. ai(xj→) ∈ rji(aj(x)); 3. aj(x) ∈ rij(ai(x→j ));

An assignment a is admissible for a formula i : φ if ai assigns all the arrow variables occurring in φ. Furthermore, a is admissible for a set of formulas Γ if it is admissible for any j : φ ∈ Γ. An assignment a is strictly admissible for a set of formulas Γ if it is admissible for Γ and assigns only the arrow variables that occur in Γ.

Using the notion of an admissible assignment given above, satisfiability in distributed first order logic is defined as follows:

Definition 5 (Satisfiability). Let M = 〈{Mi}, {rij}〉 be a model for {Li}, m ∈ Mi, and a an assignment. An i-formula φ is satisfied by m, w.r.t, a, in symbols m |=D φ[a] if

1. M |= i :P(x→j ) → j :Q(x) iff For all d ∈ ||P||i and for all d′ ∈ rij(d), d′ ∈ ||Q||j
2. M |= i :P(x) → j :Q(xi→) iff For all d ∈ ||P||i there is a d′ ∈ rij(d), s.t., d′ ∈ ||Q||j
3. M |= j :Q(xi→) → i :P(x) iff For all d ∈ ||Q||j and for all d′ with d ∈ rij(d′ ), d′ ∈ ||P||i
4. M |= j :Q(x) → i :P(x→j ) iff For all d ∈ ||Q||i there is a d′ with d ∈ rij(d′ ), s.t., d′ ∈ ||P||i

Figure 1: Implicit Quantification of Arrow Variables in Interpretation Constraints

1. a is admissible for i :φ and
2. m |= φ[ai], according to the definition of satisfiability for first order logic.

Mappings between different knowledge bases are formalized in DFOL by a new form of constraints that involves more than one knowledge base. These formulas that will be the basis for describing different mapping approaches are called interpretation constraints and are defined as follows:

Definition 6 (Interpretation constraint). An interpretation constraint from i1, . . . , in to i with ik ̸= i for 1 ≤ k ≤ n is an expression of the form

The interpretation constraint (1) can be considered as an axiom that restricts the set of possible DFOL models to those which satisfy it. Therefore we need to define when a DFOL model satisfies an interpretation constraint.

Definition 7 (Satisfiability of interpretation constraints). A model M satisfies the interpretation constraint (1), in symbols M |= i1 : φ1, . . . , in : φn → i : φ if for any assignment a strictly admissible for {i1 :φ1, . . . , in :φn}, ifM |= ik :φk[a] for 1 ≤ k ≤ n, then a can be extended to an assignment a′ admissible for i :φ and such that M |= i :φ[a′ ].

Notice that, depending on whether an arrow variable x→ occurs on the left or on the right side of the constraint, x→ has a universal or an existential reading. Figure 1 summarizes the different possible readings that will reoccur later. Notationally, for any predicate P, ||P||i = ⋂m∈Mi m(P), where m(P) is the interpretation of P in m.

By means of interpretation constraints on equality, we can formalize possible relations between heterogeneous domains.

1 Since it will be clear from the context, in the remainder we will use the classical satisfiability symbol |= instead of |=D and we will write m |= φ[a] to mean that an i-formula φ is satisfied by m. In writing m |= φ[a] we always mean that a is admissible for i : φ (in addition to the fact that m classically satisfies φ under the assignment a)

Proposition 1. Let Mbe a DFOL model and i ̸= j ∈ I.

1. M |= Fij iff rij is a partial function.
2. M |= INVij iff rij is the inverse of rji.
3. M |= ODij if rij(= r-1 ji ) is an isomorphism between a subset of domi and a subset of domj. I.e., domi and domj (isomorphically) overlap.
4. M |= EDij iff rij(= r-1 ji ) is an isomorphism between domi and a subset of domj. I.e., domi is (isomorphically) embedded in domj
5. M |= IDij iff rij(= r-1 ji ) is an isomorphism between domi and domj. I.e., domi is isomorphic to domj.
6. M |= RD, if for every constant c of Li and Lj, if c is interpreted in d for all m ∈ Mi then c is interpreted in rij(d) for all models of m ∈ Mj, and vice-versa. I.e., the constant c is rigidly interpreted by i and j in two corresponding objects.
7. Finally M |= IPij iff Mi = ∅ implies that Mj = ∅. I.e., inconsistency propagates from i to j.

3 ModelingMapping Languages in DFOL

Formalisms for mapping languages are based on four main parameters: local languages and local semantics used to specify the local knowledge, and mapping languages and semantics for mappings, used to specify the semantic relations between the local knowledge. In this section we focus on the second pairs and as far as local languages and local semantics it is enough to notice that

Local languages In all approaches local knowledge is expressed by a suitable fragment of first order languages.

Local semantics with the notable exception of [Franconi and Tessaris, 2004], where authors propose an epistemic approach to information integration, all the other formalisms for ontology mapping assume that each local knowledge is interpreted in a (partial) state of the world and not into an epistemic state. This formally corresponds to the fact that each local knowledge base is associated with at most one FOL interpretation.

The first assumption is naturally captured in DFOL, by simply considering Li to be an adequately restricted FOL language. Concerning the local semantics, in DFOL models each Li is associated with a set of interpretations. To simulate the single local model assumption, in DFOL it is enough to declare each Li to be a complete language. This implies that all the m ∈ Mi have to agree on the interpretation of Li-symbols.

Notationally, φ, ψ, . . . will be used to denote both DL expressions and FOL open formulas. If φ is a DL concept, φ(x) (or φ(x1, . . . , xn)) will denote the corresponding translation of φ in FOL as described in [Borgida, 1996]. If φ is a role R then φ(x, y) denotes its translation P(x, y), and if φ is a constant c, then φ(x) denote its translation x = c. Finally we use x to denote a set x1, . . . , xn of variables.

3.1 Distributed Description Logics/C-OWL

The approach presented in [Borgida and Serafini, 2003] extends DL with a local model semantics similar to the one introduced above and so-called bridge rules to define semantic relations between different T-Boxes. A distributed interpretation for DDL on a family of DL languages {Li}, is a family {Ii} of interpretations, one for each Li plus a family {rij}i̸=j∈I of domain relations. While the original proposal only considered subsumption between concept expressions, the model was extended to a set of five semantic relations discussed below. The semantics of the five semantic relations defined in C-OWL is the following:

Definition 8 ([Bouquet et al., 2004]). Let φ and ψ be either concepts, or individuals, or roles of the descriptive languages Li and Lj respectively 2 .

1. I |= i :φ ⊑ -→ j :ψ if rij(φIi ) ⊆ ψIj ;
2. I |= i :φ ⊒ -→ j :ψ if rij(φIi ) ⊇ ψIj ;
3. I |= i :φ ≡ -→ j :ψ if rij(φIi ) = ψIj ;
4. I |= i :φ ⊥ -→ j :ψ if rij(φIi ) ∩ ψIj = ∅;
5. I |= i :φ ∗ -→ j :ψ if rij(φIi ) ∩ ψIj ̸= ∅;

An interpretation for a context space is a model for it if all the bridge rules are satisfied.

From the above satisfiability condition one can see that the mapping i :φ ≡ -→ j :ψ is equivalent to the conjunction of the mappings i : φ ⊑ -→ j : ψ and i : φ ⊒ -→ j : ψ. The mapping i : φ ⊥ -→ j : ψ is equivalent to i : φ ⊑ -→ j : ¬ψ. And finally the mapping i : φ ∗ -→ j : ψ is the negation of the mapping i : φ ⊑ -→ j : ψ. For the translation we will therefore consider only the primitive mappings. As the underlying notion of a model is the same as for DFOL, we can directly try to translate bridge rules into interpretation constraints. In particular, there are no additional assumptions about the nature of the domains that have to be modeled. The translation is the following:

We see that a bridge rule basically corresponds to the interpretation a) and d) in Figure 1. The different semantic relations correspond to the usual readings of implications. Finally negative information about mappings (i.e., i : φ ̸ ⊑ -→ j : ψ is not representable by means of DFOL interpretation constraints.

2 In this definition, to be more homogeneous, we consider the interpretations of individuals to be sets containing a single object rather than the object itself.

3.2 Ontology Integration Framework (OIS)

Calvanese and colleagues in [Calvanese et al., 2002b] propose a framework for mappings between ontologies that generalizes existing work on view-based schema integration [Ullman, 1997] and subsumes other approaches on connecting DL models with rules. In particular, they distinguish global centric, local centric and the combined approach. These approaches differ in the types of expressions connected by mappings. With respect to the semantics of mappings, they do not differ and we therefore treat them as one.

OIS assumes the existence of a global model g into which all local models s are mapped. On the semantic level, the domains of the local models are assumed to be embedded in a global domain. Further, in OIS constants are assumed to rigidly designate the same objects across domain. Finally, global inconsistency is assumed, in the sense that the inconsistency of a local knowledge base makes the whole system inconsistent. As shown in Proposition 1, we can capture these assumptions by the set of interpretation constraints EDsg, RDsg, and IPsg, where s is the index of any source ontology and g the index of the global ontology.

According to these assumptions mappings are described in terms of correspondences between a local and the global model. The interpretation of these correspondences are defined as follows:

Definition 9 ([Calvanese et al., 2002b]). Correspondences between source ontologies and global ontology are of the following four forms

1. I satisfies 〈φ, ψ, sound〉 w.r.t. the local interpretation D, if all the tuples satisfying ψ in D satisfy φ in I
2. 〈φ, ψ, complete〉 w.r.t. the local interpretation D, if no tuple other than those satisfying ψ in D satisfies φ in I,
3. 〈φ, ψ, exact〉 w.r.t. the local interpretation D, if the set of tuples that satisfies ψ in D is exactly the set of tuples satisfying φ in I.

From the above semantic conditions, 〈φ, ψ, exact〉 is equivalent to the conjunction of 〈φ, ψ, sound〉 and 〈φ, ψ, complete〉. It's therefore enough to provide the translation of the first two correspondences. The definitions 1 and 2 above can directly be expressed into interpretation constraints (compare Figure 1) resulting in the following translation:

The translation shows that there is a fundamental difference in the way mappings are interpreted in C-OWL and in OIS. While C-OWL mappings correspond to a universally quantified reading (Figure 1 a), OIS mappings have an existentially quantified readings (Figure 1 b/d). We will come back to this difference later.

3.3 DL for Information Integration (DLII)

A slightly different approach to the integration of different DL models is described in [Calvanese et al., 2002a]. This approach assumes a partial overlap between the domains of the models Mi and Mj , rather than a complete embedding of them in a global domain. This is captured by the interpretation constraint ODij. The other assumptions (rigid designators and global inconsistency) are the same as for OIS.

An interpretation I associates to each Mi a domain ∆i. These different models are connected by interschema assertions. Satisfiability of interschema assertions is defined as follows 3

Definition 10 (Satisfiability of interschema assertions). If I is an interpretation for Mi and Mj we say that I satisfies the interschema assertion

As before ≡est and ≡int are definable as conjunctions of ⊑est and ⊑int, so we can ignore them for the DFOL translation. Furthermore, a distinction is made between extensional and intentional interpretation of interschema assertions, which leads to different translations into DFOL.

While the extensional interpretation corresponds to the semantics of mappings in OIS, the intentional interpretation corresponds to the semantics of mappings in C-OWL. Thus using the distinction made in this approach we get an explanation of different conceptualizations underlying the semantics of C-OWL and OIS that use an extensional and an intentional interpretation, respectively.

3.4 ϵ-connections

A different approach for defining relations between DL knowledge bases has emerged from the investigation of socalled ϵ-connections between abstract description systems [Kutz et al., 2004]. Originally intended to extend the decidability of DL models by partitioning them into a set of models that use a weaker logic, the approach has recently been proposed as a framework for defining mappings between ontologies [Grau et al., 2004].

In the ϵ-connections framework, for every pair of ontologies ij there is a set ϵij of links, which represents binary relations between the domain of the i-th ontology and the domain of the j-th ontology. Links from i to j can be used to define i-concepts, in a way that is analogous to how roles are used to define concepts. In the following table we report the syntax and the semantics of i-concept definitions based on links. (E denotes a link from i to j and C denotes a concept in j. The only assumption about the relation between domains is global inconsistency, see above).

3 To simplify the definition we introduce the notation ⊤Inij = ⊤Ini ∩⊤Inj for any n ≥ 1. Notice that ⊤Inij = ∆ni ∩∆nj .

In DFOL we have only one single relation from i to j, while in ϵ-connection there are many possible relations. However, we can use a similar trick as used in [Borgida and Serafini, 2003] to map relations to interschema relations: each of the relations in ϵij acts as a rij. To represent ϵconnections it is therefore enough to label each arrow variable with the proper link name. The arrow variable xOwn -→j is read as the arrow variable x→i where rij is intended to be the interpretation of Ownij. With this syntactic extension of DFOL, concept definitions based on links (denoted as E) can be codified in DFOL as follows:

We see that like OIS, links in the ϵ-connections framework have an extensional interpretation. The fact, that the framework distinguishes between different types of domain relations, however, makes it different from all other approaches.

Another difference to the previous approaches is that new links can be defined on the basis of existing links, similar to complex roles in DL. Syntax and semantics for link constructors is defined in the usual way: (E-)I = (EI )-1 (Inverse), (E ⊓F)I = EI ∩F I (Conjunction), (E ⊔F)I = EI ∪F I (Disjunction), and (¬E)I = (∆i × ∆j) \ EI (Complement). Notice that, by means of inverse links we can define mappings of the b and d type. E.g., the ϵ-connection statement φ ⊑ ∃E-ψ corresponds to the DFOL bridge rule φ(x) : i → ψxi→j : which is of type b). Similarly the ϵconnection φ ⊑ ∀E-ψ corresponds to a mapping of type d).

As the distinctions between different types of links is only made on the model theoretic level, it is not possible to model Boolean combinations of links. Inverse links, however, can be represented by the following axiom:

Finally the inclusion axioms between links, i.e., axioms of the form E ⊑ F where E and F are homogeneous links, i.e., links of the same ϵij , can be translated in DFOL as follows:

We can say that the ϵ-connections framework significantly differs from the other approaches in terms of the possibilities to define and combine mappings of different types.

4 Discussion and Conclusions

The encoding of different mapping approaches in a common framework has two immediate advantages. The first one is the ability to reason across the different frameworks. This can be done on the basis of the DFOL translation of the different approaches using the sound and complete calculus for DFOL [Ghidini and Serafini, 2000]. As there are not always complete translations, this approach does not cover all aspects of the different approaches, but as shown above, we can capture most aspects. There are only two aspects which cannot be represented in DFOL, namely "nonmappings" (i :φ ∗ -→ j :ψ in C-OWL, φ ̸⊑int ψ etc. in DLII) and "complex mappings" such as complex links in ϵ-connection. The second benefit is the possibility to compare the expressiveness of the approaches. We have several dimensions along which the framework can differ:

• Arity of mapped items 4 C-OWL allows only to align constants, concepts and roles (2-arity relations), ϵconnections allow to align only 1-arity items, i.e., concepts, while DLII and OIS allow to integrate n-arity items.

Positive/negative mappings Most approaches state positive facts about mapping, e.g that two elements are equivalent. The DLII and C-OWL frameworks also allow to state that two elements do not map (φ ̸≡ ψ).

• Domain relations The approaches make different assumptions about the nature of the domain. While C-OWL and ϵ-connections do not assume any relation between the domains, DLII assumes overlapping domains and OIS assumes local domains that are embedded in a global domain.
• Multiple mappings Only the ϵ-connection approach supports the definition of different types of mappings between ontologies that partition the inter-domain relations.

Local inconsistency Some approaches provide a consistent semantics also in the case in which some of the ontologies or mappings are inconsistent.

We summarize the comparison in the following table.

We conclude that existing approaches make choices along a number of dimensions. These choices are obviously influenced by the intended use. Approaches intended for database integration for example will support the mapping of nary items that correspond to tuples in the relational model. Despite this fact, almost no work has been done on charting the landscape of choices to be made when designing a mapping approach, and for adapting the approach to the requirements of an application. The work reported in this paper provides the basis for this kind of work by identifying the possible choices on a formal level. An important topic of future work is to identify possible combinations of features for mapping languages on a formal level in order to get a more complete picture of the design space of mapping languages.

4 Due to limited space we did not discuss the encoding of mapped items in this paper