=Paper=
{{Paper
|id=Vol-232/paper-6
|storemode=property
|title=Semantic Import: An Approach for Partial Ontology Reuse
|pdfUrl=https://ceur-ws.org/Vol-232/paper6.pdf
|volume=Vol-232
|dblpUrl=https://dblp.org/rec/conf/semweb/PanSZ06
}}
==Semantic Import: An Approach for Partial Ontology Reuse==
https://ceur-ws.org/Vol-232/paper6.pdf
Semantic Import: An Approach for Partial
Ontology Reuse (∗)
Jeff Z. Pan1 , Luciano Serafini2 and Yuting Zhao2
1
University of Aberdeen, UK
jpan@csd.abdn.ac.uk
2
ITC-IRST, Povo 38100 Trento, Italy
{yzhao,serafini}@itc.it
Abstract. As more and more applications use ontology to represent se-
mantic information, how to support ontology reuse is becoming more
and more important. In the OWL Web Ontology Language, the main
primitive for ontology reuse is owl:imports. However, this “copy-and-
paste” approach suffers a number of problems. In this paper, we propose
a new import primitive, called semantic import, to facilitate partial on-
tology reuse. The main contributions of this paper include the semantics
of semantic import and reasoning support for TBox reasoning in sim-
ple ontology spaces, where an ontology semantically imports vocabulary
from another ontology. The semantic import approach provides a brand
new way for partial ontology reuse.
1 Introduction
Ontologies [17] play an important role in the Semantic Web [2]. The advent of
the connectivity and the Web makes an increasing number of ontologies widely
available for reuse. As more and more applications use ontology to represent
semantic information, how to support ontology reuse [18] is becoming more and
more important. In this paper, we assume that ontologies are all written in a
standard ontology language, such as the W3C recommendation OWL Web On-
tology Language [12], and do not consider the translation of ontological axioms
from one ontology language to another.
The basic primitive for in the OWL Web ontology language to support reuse
is owl:imports [12], which allows one to “copy-and-paste” an ontology into an-
other one. We call this operation syntactic import, to stress the fact the operation
is defined on the set of axioms of an ontology, rather than the knowledge encoded
in the ontology itself. The “copy-and-paste” approach provides only limited sup-
port for partial ontology reuse, which means importing only a (small) part of the
knowledge encoded in an ontology, while ignoring the rest. We illustrate this
issue with the following example.
(∗)
Thanks to Prof. Fausto Giunchiglia for the discussions on this topic, he has partic-
ipated to write previous versions of this paper. This work is supported by the FP6
Network of Excellence EU project Knowledge Web (IST-2004-507842).
2 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
Example 1. Suppose that we want to build our own ontology for people trans-
portation, let us say W ppl , by reusing other ontology present on the Web, e.g.
SUMO [9]. In our ontology, one can use cars and horses as transportation devices;
therefore, we would like to impose the following axioms:
sumo:Horse v sumo:TransportationDevice (1)
sumo:Car v sumo:TransportationDevice (2)
Furthermore, we would like to reuse some knowledge which is explicitly stated
in or entailed by SUMO:
sumo:Car v ∃sumo:capability.(sumo:Transportation) (3)
There are three approaches to reaching the partial ontology reuse through
syntactic imports: (i) simply import the whole SUMO ontology into W ppl , and
only use some of the axioms, ignoring the others; (ii) only “copy-and-paste” a
subset of the SUMO axioms into W ppl ; (iii) divide the SUMO ontology into dif-
ferent modules, based on some criteria, and import only the interesting module.
All these approaches present some problems, as discussed below.
For (i), when importing the whole ontology and only using some of its axioms
the following drawback can raise. Firstly, inconsistency can easily be reached
by importing those conflicting axioms from the source ontology. Secondly, there
exist partial disagreements in certain axioms; e.g., we might agree that Horses are
quadrupeds and mammals, but we do not agree that they are not transportation
devices. Thirdly, scalability could become a problem. This means that intention
of reusing only a few objects and/or classes in a source ontology would end up
importing the whole ontology.
For (ii), in order to import a subset of the axioms, users have to be carefully
identify which set of axioms encodes the knowledge he wants to import; other-
wise, it will cause information lost. Sometimes, the structure of the ontology is
such that this is not possible. For example, given an ontology containing the ax-
ioms A v B and B v C, a user wants to import only A v C without committing
on B.
Approach (iii) actually is most promising. The main difficulty of (iii) is that
the modularisation of an ontology is far from easily customisable and generalis-
able to any ontology. A recent approach in this line is the work by Cuenca-Grau
et al. [5], which provides the theory and an algorithm for the modularisation of
a wide class of ontologies, called safe ontologies.
The main contributions of this paper are as follows. Firstly, it proposes se-
mantic imports, a new mechanism of partial ontology reuse. One distinguished
feature of this new partial reuse mechanism is to allow users to semantically
reuse vocabulary (classes, properties or individuals), while current approaches
allow to reuse axioms. Moreover, semantic imports provide a flexible way to
partially reuse ontologies, by allowing users (in their target ontologies) to agree
or disagree with some subsumption relationships in a distant ontology. More
specifically, in our mechanism all subsumption relations among the semantically
Semantic Import: An Approach for Partial Ontology Reuse 3
imported named classes in the distant ontology are transferred to the target on-
tology. Secondly, the paper address some logical properties and algorithm of a
reasoning problem for a special case in our framework, i.e., semantic imports
in simple ontology spaces, where an ontology semantically imports vocabulary
from another ontology. Based on the notion of local/non-local classes first pro-
posed by Cuenca-Grau et al. [5] (we call them positive/negative classes), several
categories of subsumption relations among class descriptions over the semanti-
cally imported vocabulary can be transferred from a distant ontology to a target
ontology in simple ontology spaces. Furthermore, it presents a distributed tab-
leaux algorithm to compute class satisfiability in simple ontology spaces, in the
presence of semantic import of ALC ontologies.
2 Ontologies with Imports
An OWL [12] ontology, as defined by the W3C standard, consists of a set of
axioms, including class axioms, property axioms and individual axioms.1 The
reader is referred to [12] for details of syntax and semantic of OWL. An OWL
ontology can import (other) OWL ontologies, with the help of imports annota-
tions similar to the following.
Annotation(imports )
Annotation(imports )
These imports annotations include all the axioms in the two source ontologies
into the target ontology.
We extend the notion of ontology by allowing the semantic import of classes,
properties, and individuals from source ontologies. To simplify the presentation,
in this paper we only consider the abstract domain and leave the discussion of
the datatype domain [10] as our future work.
Definition 1 (Ontology). An ontology is a tuple W i = hi, Mi , Si , Oi i, where
1. i is the identifier of the ontology W i ,
2. Mi (called the syntactic import box) is the set of ontology identifiers which
are syntactically imported by W i (by the primitive owl:imports),
3. Si (called the semantic import box) is a set of classes, properties and/or in-
dividuals symbols which are semantically imported by W i (by the new prim-
itive owlx:semanticImports).
4. Oi (called the axiom box) contains a set of class, property and individual
axioms.
Example 2. W ppl = hppl, Mppl , Sppl , Oppl i is an ontology, where Mppl = ∅
(no syntatic imports), Sppl = {sumo:Car, sumo:Horse, sumo:Transportation,sumo:
TransportationDevice ,sumo:capability} (W ppl semantically imports the classes
sumo:Car, sumo:Horse, sumo:Transportation and sumo:TransportationDevice, the
1
Individual axioms are also called facts.
4 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
property sumo:capability). Furthermore, Oppl contains the axioms:
sumo:Horse v ∃sumo:capability.(sumo:Transportation)(4)
∃sumo:capability.(sumo:Transportation) v sumo:TransportationDevice (5)
ppl:BelgianDraftHorse v sumo:Horses (6)
ppl:Ferrari v sumo:Car (7)
They state that horses can be used for transportation (4), that those can be used
for transportation are transportation devices (5), that Belgian Draft horses are
horses (6), and that Ferrari is a type of car (7), which do not hold in SUMO.
Intuitively the fact that W ppl semantically imports sumo:Car means that W ppl
“demands” the semantics of sumo:Car from SUMO. In other words, an object of
the domain of W ppl cannot be a sumo:Car if it is not a sumo:Car in the domain
of the SUMO ontology.
It is worth noting that, in the formal definition, a semantic import box is
described as a set of classes, properties, and/or individuals. While in practice,
this box can be specified either by explicitly listing its components, or, in a
more intensional way, by, e.g., including all the sub-classes or all the individuals
of some given classes. From the theoretical perspective this is clearly irrelevant,
while it is very relevant from the usability point of view.
We end this section by clarifying the expected effects of semantic imports,
which are all satisfied by the semantics of semantic imports to be provided in
the next section (we assume that 1:A, 1:B, 1:R, 1:o, 1:o2 ∈ S2 ): (i) Propagation
of class hierarchy: if W 1 entails 1:A v1:B, then W 2 entails 1:A v1:B. (ii)
Propagation of disjoint classes: if W 1 entails 1:A v¬ 1:B, then W 2 entails 1:A
v¬ 1:B. (iii) Property Closure: all the 1:R-successors and 1:R-predecessor of
1:o1 are also imported. (iv) Propagation of (in)equality objects: if W 1 entails
1:o1 ≈ 1:o2 (1:o1 6= 1:o2), then W 2 entails 1:o1 ≈ 1:o2 (1:o1 6= 1:o2).
3 Ontology Spaces
In order to give a formal semantics to semantic imports, we briefly introduce
some basic notions.
Definition 2 (Local language). Given an ontology W i , a local class w.r.t.
W i is a class name in Oi associated with the identifier i. Local properties and
local individuals are defined analogously. The set of local classes, local properties
and local individuals of W i are denoted by Ci , Ri and Ii . The local language
of W i , i.e., Li , is the union of them.
For example, the local language of W ppl is Lppl , which contains the two
classes ppl:BelgianDraftHorse and ppl:Ferrari.
Now we introduce the concept of ontology spaces, in which we consider not
only a single ontology but a set of ontologies. As described in the last section,
OWL imports annotations do not guarantee the existence of imported ontologies.
Semantic Import: An Approach for Partial Ontology Reuse 5
Similarly, the occurrence of an URIrefs in an axiom does not impose requirement
of the existence of an ontological resource associated with such a URIref. For
instance, the existence of the axiom car:Car v abc:ExpensiveGood in the ontol-
ogy W car does not guarantee the existence of the ontology W abc ; furthermore,
even if W abc does exist, this axiom does not guarantee that abc:ExpensiveGood
is in Labc . When we consider an ontology space, we impose these requirements.
Definition 3 (Ontology space). Let I be a set of ontology identifiers and
j ∈ I an ontology identifier. An ontology space on I is a family of ontologies
S = {W i }i∈I such that (i) for each W i = hi, Mi , Si , Oi i, Mi ⊆ I, (ii) for
each j:x occurring in Oi , j:x ∈ Si , and (iii) for each j:x ∈ Si , j:x appears in
Oj , where j ∈ I and j 6= i.
Note that, given an ontology space {W i }i∈I , the above definition requires
that: (i) all the imported ontologies of each ontology exist and are in {W i }i∈I ,
and (ii) non-local classes, properties and individuals of each ontology in {W i }i∈I
should be introduced by some ontologies in {W i }i∈I . For example, S = hW sumo , W ppl i
is an ontology space, where W ppl is defined in Example 2 and W sumo = hsumo, Msumo ,
Ssumo , Osumo i with Msumo = ∅, Ssumo = ∅, (no ontology imports and no semantic
import) and with Osumo equal to the set of axioms contained in SUMO.
Based on an ontology space, we introduce the concept of import closure and
foreign languages. Intuitively speaking, an import closure of an ontology W i is
the set of axioms considering its syntactic imports, while the foreign language
of W i is the set of names of classes, properties and individuals in an ontology
space that are not in its local language.
Definition 4 (Import closure). Given an ontology space S = {W i }i∈I , the
import closure of an ontology W i w.r.t. S, written as OiS , is a set of class,
property, and individual axioms recursively defined as follows:
1. Oi ⊆ OiS ;
2. if j ∈ Mi then OjS ⊆ OiS ;
3. nothing else is in OiS .
Definition 5 (Foreign language). Given an ontology space S = {W i }i∈I , the
foreign language of W i w.r.t. S, written as FSi , is the set of classes, properties
and individuals of the form j:x (j 6= i) which occur in Si or in OiS .
Intuitively, the semantic for an ontology space is a family of interpretations
one for each ontology, such that the axioms of the import closure of each on-
tology are satisfied, and there is an agreement between the interpretations on
the semantics of semantically imported symbols, which will be formally defined
below. It should be noted that the interpretation domains of the family of inter-
pretations could be disjoint or overlapping with each other.
Definition 6 (Interpretation of an ontology space). Let S = {W i }i∈I be
an ontology space on I. An interpretation of S is a family I = {Ii }i∈I , where
each Ii , called the local interpretation of W i , is an interpretation (including
hole interpretations) of the local and foreign language of W i , such that
6 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
1. Ii |= OiS ;
2. if j:C is a class name in Si , then (j:C)Ii = (j:C)Ij ∩ ∆Ii ;
3. if j:a is an individual name in Si , then (j:a)Ii = (j:a)Ij ;
4. if j:R is a property name in Si , then
forward closure for all d ∈ ∆Ii ∩ ∆Ij , for all d0 ∈ ∆Ij , hd, d0 i ∈ (j:R)Ii
iff hd, d0 i ∈ (j:R)Ij ;
backward closure for all d ∈ ∆Ii ∩ ∆Ij , for all d0 ∈ ∆Ij , hd0 , di ∈ (j:R)Ii
iff hd0 , di ∈ (j:R)Ij .
Example 3. The interpretation I = {Isumo , Ippl } described in Table 1 is an in-
terpretation of S = hW sumo , W ppl i.
symbol Isumo Ippl
> {c, f, h, k, d, t, . . . } {c, f, h, v, d, t}
sumo:Car {c, f } {c, f }
sumo:Horse {h, k} {h}
sumo:TransportationDevice {c, f, d} {c, f, h, v}
sumo:Transportation ½ {t} ¾ ½ {t} ¾
hc, ti, hh, ti hc, ti, hh, ti
sumo:capability
hf, ti, hd, ti hf, ti, hd, ti
ppl:BelgianDraftHorse undef {h}
ppl:Ferrari undef {f }
sumo:OrganicObject {h, k} undef
sumo:Artifact {c, f, d} undef
... ... undef
Table 1. An interpretation for the ontology space hW sumo , W ppl i
It is worth noting the following points: (i) In a local interpretation of W ppl ,
only symbols in local and foreign languages are considered. That is why local
interpretations of W ppl , such as Ippl above, do not have to provide an inter-
pretation mapping for symbols (such as sumo:OrganicObject and sumo:Artifact)
that are not in the local or foreign languages of W ppl . (ii) Due to the backward
closure, hd, ti is in (sumo:capability)Ippl .
Definition 7 (Logical consequence). Let S = {W i }i∈I be an ontology space
on I. An OWL DL axiom α is a logical consequence of S in W j , written S |=j α,
iff, for every interpretation I = {Ij }j∈I of S, Ij |= α.
4 Reasoning in Simple Ontology Spaces
Note that the framework proposed in the previous sections is very general; e.g.,
there can be an arbitrary (finite) number of ontologies in an ontology space and
any ontology involved can semantically vocabulary from any other ontologies in
the ontology space. As a first step, in the rest of this paper we only consider a
Semantic Import: An Approach for Partial Ontology Reuse 7
special kind of ontology spaces, called simple ontology spaces. Informally speak-
ing, a simple ontology space consists of a pair of ontologies W i and W j , where
there is no syntactic imports, and W j semantically imports some vocabulary
from W i , and W i does not (semantically) import anything.
Definition 8. A simple ontology space is of the form S = hW j , W i i, where
Mj = Mi = ∅ (no syntactic imports) and Sj = ∅.
What is the effect on the logical consequence of semantic import? And how
such effect can be computed? In what follows, we will answer these questions by
characterizing the effect of class constructors on transferring knowledge (in the
form of class subsumptions) from a distant ontology to a target ontology. Let us
illustrate our characterization by revisiting our example about hW sumo , W ppl i.
Example 4. In our example, the subsumption (3) is propagated from W sumo
to W ppl . Intuitively this is because W ppl semantically agrees with W sumo on
the meanings of all the terms of this subsumption. Instead, the subsumption
sumo:Horses v ¬sumo:TransportationDevice which holds in W sumo , does not hold
in W ppl because W ppl disagrees with W sumo on the meaning of sumo:Transport-
ationDevice (see the different interpretations in table 1).
Generalizing the previous example, one might falsely infer that, if the ontol-
ogy W i semantically imports a set of symbols Si from the ontology W j , then
all the class subsumptions in the language of Sj that hold in W j are propagated
to W i . This is true with an exception, due to the effect of coverage axioms. Let
us explain this point with an example.
Example 5 (Closure Axioms are not Propagated). 2 Suppose that the ontology
W xyz contains the axiom
¬xyz:Fast v xyz:Slow. (8)
Such an axioms partitions the domain of W xyz into two sets, the fast objects and
the slow objects. Even if W ppl semantically imports all vocabulary from W xyz ,
axiom (8) is not propagated form W xyz to W ppl . The reason is that the domain
of ontology W ppl might contain objects which are not in the domain of W xyz ,
and these objects could be neither fast nor slow.
4.1 Characterizing Logical Consequence in Simple Ontology Spaces
In Sections 2 and 3, we mainly considered subsumption relations among seman-
tically imported named classes. Now we introduce related class descriptions.
Definition 9 (Semantically imported classes descriptions). The seman-
tically imported class descriptions, or simply semantically imported classes, of
an ontology W i are SHOIN -class descriptions that can be constructed from
classes, properties and individuals contained in Si . We say that W i semanti-
cally imports a description X from W j if X is constructed by the local language
of W j .
2
B. Cuenca-Grau presented this example at the DL-2006 workshop.
8 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
Definition 10. Given S an semantic import box, we say that a class description
C (property description R) is S-related if all the vocabulary in C (R, respectively)
are in S.
For example, given the semantic box Sppl = {sumo:Car, sumo:Horse, sumo:Trans-
portation, sumo:TransportationDevice (see Example 2), sumo:Car, sumo:capability,
and ∃(sumo:capability).(sumo:Transportation) are Sppl -related.
On the base of the intuition given in the example presented at the beginning
of Section 4, in the following we will provide a precise class characterization on
which subsumptions propagate as a consequence of semantic imports in simple
ontology spaces. Formally speaking, we accomplish this by using the notion of
local/non-local classes first proposed by Cuenca-Grau et al. [5]. In this paper,
we call them positive/negative classes.
Definition 11 (Polarity). The polarity of a semantically imported SHOIN -
classes is defined as follows (let A and B be classes, a an individual and R an
object property): any atomic class is positive, ⊥ is positive, > is negative, {a} is
positive, A u B is positive if either A or B are positive, A t B is positive if both
A and B are positive, ¬A is positive iff A is negative, ∃R.A is positive, ∀R.A is
negative, (≥ 0)R is negative, (≥ n)R with n ≥ 1 is positive, (≤ n)R is negative,
every class which is not positive is negative.
Property 1. For every positive concept semantically imported from W j , C Ii =
C Ij ∩ ∆Ii . For every negative concept semantically imported from W j , C Ii =
(C Ij ∩ ∆Ii ) ∪ ∆Ii −Ij (where ∆Ii −Ij is a shortcut of ∆Ii \ ∆Ij ).
The Property 1 is the same as the property of local/non-local classes pre-
sented in the proof of Theorem 1 of [5], in which the authors have proved: (1)
for each local (positive) class description C, C Ii = C Ij , and (2) for each non-
local (negative) class description C, C Ii = C Ij ∪ ∆Ii −Ij . Note that the property
from [5] is based on a different kind of cross-domain semantics, namely domain
expansion3 , rather than that of semantic imports presented in Definition 6. It
should be pointed out that, in order to maintain properties like Property 1, the
kind of cross-domain semantics should be carefully selected. For example, if we
replace the semantics of semantically imported properties (defined in Definition
6) with RIi = RIj ∩ (∆Ii × ∆Ii ) (as in C-OWL [3]), the Property 1 no longer
holds.
Based on the notion of positive/negative (i.e. local/non-local) classes and the
above property, the following Definition 12, Theorem 1 and 2 and can be seen
as counterparts (under the semantics of semantic imports) of the Theorem 2 of
[5], which identifies safe axioms, i.e. the kind of axioms that are satisfies by any
domain expansions of their interpretations.
3
According to [5], a domain expansion Ii of an interpretation Ij is an interpretation
such that: (1) ∆Ii = ∆Ij ∪ Φ, with Φ a non-empty set disjoint with ∆Ij , (2) AIi =
AIj for each class name, and (3) RIi = RIj for each property name.
Semantic Import: An Approach for Partial Ontology Reuse 9
Definition 12. Let S = hW j , W i i be a simple ontology space. The subsump-
tions transfer from W j to W i , written as Sji (W j ), is the set of subsumption
statements of the form X v Y , where X and Y are Si -related class descrip-
tions, W j |= X v Y and, either X is positive or Y is negative.
Intuitively, the subsumption transfer from W i to W j is the set of all the pos-
sible subsumptions in W i that are semantically propagated in W j . The following
theorem shows that the subsumption transfer defined above can be used for a
sound and complete characterization of logical consequences in simple ontology
spaces.
Theorem 1 (Soundness). Let S = hW j , W i i be a simple ontology space. If
X and Y are Si -related class descriptions, then
W i ∪ Sji (W j ) |= X v Y =⇒ S |=i X v Y.
Theorem 2 (Completeness). Let S = hW j , W i i be a simple ontology space.
If X and Y are Si -related class descriptions, then
W i ∪ Sji (W j ) |= X v Y ⇐= S |=i X v Y.
Proof. Suppose that Oi ∪ Sji (W j ) 6|= X v Y and let us build a model for S
such that S 6|=i X v Y . If Oi ∪ Sji (W j ) 6|= X v Y then let Ii be a model of
Oi ∪ Sji (W j ) such that X Ii 6⊆ Y Ii .
Suppose that Oj is unsatisfiable, then for all concept C ∈ Si , Oj |= C v ⊥;
for all nominal {x} ∈ Si i, Oj |= {x} v ⊥; for all role R ∈ Si , Oj |= > v
∀R.⊥. In all the cases we have that the corresponding subsumptions belongs to
Sji (Oj ). The fact that Ii |= Sji (Oj ), implies that Si does not contains nominals
(otherwise Ii |= {x} v ⊥, which is not possible), and for all C and R in Si ,
they are interpreted by Ii in the empty set. This implies that the interpretation
hIj , Ii i with Ij being a hole interpretation, satisfies S.
Now let us consider the case were Oj is consistent. Let ∆∗ ⊆ ∆Ii be the set
¯
¯ x ∈ B Ii for some B ∈ Si or
¯
¯
Ii ¯ x = {a}
Ii
for some a ∈ Si or
x∈∆ ¯ Ii
¯ hx, yi ∈ RI for some y and R ∈ Si or
¯ hy, xi ∈ R i for some y and R ∈ Si
If ∆∗ = ∅ then, the interpretation hIj , Ii i where Ii is the hole interpretation is a
model of S which does not satisfy X v Y . Suppose, therefore that ∆∗ contains
at least an element x0 .
Let W ∗i be obtained by extending the semantic import Si of W i with the set
of constants in ∆∗ (we can suppose with no loss of generality that ∆∗ is disjoint
from the language of W i ), and with a new role R0 . a new nominal {x0 }. Let Ii∗
∗ I∗
be the extension of Ii such that xIi = x for all x ∈ ∆∗ and x0 i be any value in
∆∗ . Clearly Ii∗ is an interpretation of W ∗i that satisfies Oi∗ = Oi .
Let W ∗j be obtained by extending Oj of W j , with the following set of axioms.
We denote the resulting set with Oj∗ .
10 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
1. {x0 } v ∃R0 {x} for all x ∈ ∆∗
2. {x} v ¬ {y} for every x 6= y ∈ ∆∗ .
3. {x} v B, if B ∈ Si and x ∈ B Ii ;
4. {x} v ∃R. {y}, if R ∈ Si and hx, yi ∈ RIi .
Consider the ontology space S∗ = hW ∗j , W ∗i i, If Oj∗ is consistent, then there is
∗
an interpretation Ij∗ for Oj∗ in which xIj = x. Let Ij be the restriction of Ij∗ on
the language of W i , then by construction hIj , Ii i is an interpretation for S.
If Oj∗ is inconsistent, then, since Oj is consistent, there is a finite subset Oj0
of the axioms 1–4 added to Oj that make it inconsistent. Let C ∗ be the concept
t X u ¬Y.
XvY ∈Oj0
We have that Oj ∪ C ∗ v ⊥ is inconsistent. This implies that
Oj |= {x0 } v ∃R0 C ∗ .
Notice that both {x0 } and ∃R0 C ∗ are positive classes, which implies that {x0 } v
∃R0 C ∗ belongs to Sij (W i ) which generates a contradiction.
4.2 Distributed Tableaux for Simple Ontology Spaces
In this section, we consider ontologies represented as ALC [13] TBoxes (which
consists of only class axioms) and describe a distributed tableaux algorithm to
compute concept consistency in simple ontology spaces.
Tableaux algorithms (first by [14]) are very useful to solve class satisfiability
problem. They test the satisfiability of a class E 4 by trying to construct an
interpretation for E, which is represented by a completion tree T : nodes in T
represent individuals in the model; each node y is labeled with L(y) and each
edge hy, zi is labeled with L(hy, zi). A tableaux algorithm starts from an labelled
initial tree (usually simply a root node), and is expanded by repeatedly applying
the completion rules. The algorithm terminates either when T is complete (no
further completion rules can be applied) or when an obvious contradiction, or
clash, has been revealed.
Formally, a completion tree is a tuple T = hx, N, E, Li, where x is the root
of T , N and E are the sets of nodes and edges, respectively, of T , and L a
function that maps each node y (each edge hy, zi) in T to its label L(y) (L(hy, zi),
respectively). Let T be a completion tree, S a semantic import box. We say that
a completion tree T is S-related if there exist some S-related class or property
descriptions in the labels of all edges and all non-leaf nodes of T . In what follows,
we define the main operation on completion trees we need in our algorithm.
Definition 13 (Projection of Completion Tree). Let S be a semantic im-
port box and T an S-related clash-free completion tree with root x0 . The projec-
tion of T w.r.t. S, denoted as πS (T ), is a completion tree which
4
Here we assume E is in negation normal form; i.e., negation is only applied to class
names.
Semantic Import: An Approach for Partial Ontology Reuse 11
1. has the same root x0 ,
2. contains the exact set of nodes and edges as T , and
3. for each label L(x0 ) (L(hx0 , y 0 i)) of a node x (an edge hx0 , y 0 i, respectively) is
the subset of the label L(x) (L(hx, yi), respectively) of the corresponding node
x (edge hx, yi, respectively). If all the S-related class descriptions in L(x) is
negative, L(x0 ) = ∅; otherwise, L(x0 ) contains all the S-related class descrip-
tions in L(x) . L(hx0 , y 0 i) contains all the S-related property descriptions in
L(hx, yi).
According to Theorem 1 and 2, we do not project any S-related class descriptions
in L(x) to L(x0 ) if all the S-related class descriptions in L(x) are negative.
For a simple ontology space S = hW j , W i i, the procedure S-Tab(i, E) verifies
the satisfiability of an ALC class description E in ontology W i . The procedure
Tab(Ox , T ) is a (local) tableaux algorithm to expand T w.r.t. a local ontology
Ox . Tab(Ox , T ) has two distinguished features that we need: (i) it takes not only
a single node but an arbitrary initial completion tree (see line 8 in Algorithm
1), (ii) the algorithm can cache reasoning states (see line 11 in Algorithm 1).
Algorithm 1: S-Tab(i, E)
1: let T :=Tab(Oi , hx0 , {x0 }, ∅, {L(x0 ) = {E}}i) //local expansion w.r.t. Oi
2: repeat
3: if T has a clash then
4: return unsatisfiable
5: end if
6: let T1 , . . . , Tn be the maximal Si -related sub-trees of T with roots x1 , ..., xn ,
repectively
7: T10 := πSi (T1 ), . . . , Tn0 := πSi (Tn ) //sub-trees projection
8: T10 := Tab(Oj , T10 ), . . . , Tn0 := Tab(Oj , Tn0 ) //local expansion w.r.t. Oj
9: if any of T10 , . . . , Tn0 has a clash then
10: if T is backtrackable then
11: T :=Tab(Oi , T , backtrack) //backtrack and expand
12: else
13: return unsatisfiable
14: end if
15: else
16: return satisfiable
17: end if
18: until false
The algorithm needs some explanation and clarification. T is initialised with
a root x0 with L(x0 ) = {E}, and is expanded by local completion rules w.r.t. Oi
(line 1). As T might not be Si -related, maximal Si -related sub-trees then should
be projected and expanded by local completion rules w.r.t. Oj (lines 6-8). If any
of the projected sub-tree has a clash, T needs to be backtracked, expanded and
start the checking all over again. In what follows, let us use a simple example to
illustrate its main idea of the algorithm.
Example 6. Given the following ontology space S = hW j , W i i, where W j and
W i are defined as follows: W j = hj, Mj = ∅, Sj = ∅, Oj = {j:A v ∀j:R.(j:C),
12 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
j:C v j:B}i and W i = hi, Mi = ∅, Si = {j:A, j:B, j:R}, Oi = ∅i. We want to
check the satisfiability of the following class j:A u ∃j:R.(¬j:B) in W i w.r.t. S.
We use Tab(Oi , hx0 , {x0 }, ∅, {L(x0 ) = {j:A u ∃j:R.(¬j:B)}}i) to build a
clash-free completed completion tree T . It is obvious that T is Si -related, so
there is only one maximal Si -related sub-tree of T , which is itself. Therefore, T 0
consists of two connected nodes x00 and x01 , where x00 is labelled with L(x00 ) =
{j:A u ∃j:R.(¬j:B), j:A, ∃j:R.(¬j:B)}, x01 is labelled with L(x01 ) = {¬j:B} and
the edge hx00 , x01 i is labelled with L(hx00 , x01 i) = j:R. Then we expand T 0 with
mega-constraints:5 we first expand L(x00 ) as {j:Au∃j:R.(¬j:B), j:A, ∃j:R.(¬j:B),
¬j:A t ∀1:R.(j:C), ¬j:C t j:B}; for the disjunction ¬j:A t ∀j:R.(j:C) in L(x00 ),
we have to choose ∀j:R.(j:C) since j:A ∈ L(x00 ); then we expand L(x01 ) and add
C in it, so L(x01 ) = {¬j:B, ¬j:A t ∀j:R.(j:C), ¬j:C t j:B, C}; obviously there
is a clash in L(x01 ) because ¬j:C t j:B, j:C and ¬j:B are in L(x01 ). Hence, T 0
and T are not complete and j:A u ∃j:R.(¬j:B) is unsatisfiable in W i w.r.t. S.
To prove the algorithm correct, we need to show that: (1) The algorithm
always terminates. (2) The algorithm returns unsatisfiable iff S 6|=i E. (3) The
algorithm returns satisfiable iff S |=i E.
Due to limited space, we only provide a brief discussion. For (1), observe that
Algorithm 1 does not change T at all and simply invokes backtrack when there
exists an external clash. Algorithm 1 terminates because Tab(O, E) terminates.
For (2), observe that S 6|=i E either because Oi 6|= E (this would be detected
by lines 1-3) or there exists some X v Y ∈ Sji s.t. ¬X t Y is disjoint with a
Si -related sub-class of E (this would be detected by lines 7-9). For (3), it can be
shown that we can construct an interpretation of E whenever we have a complete
T , and vice versa.
5 Related Work
Ontology reuse has been an important topic [19, 18, 8]. Uschold et al [18] conclude
that reusing an ontology requires significant effort on considering the context and
intended usage of both the source and target ontologies as well as the specific
task of the target application. This is consistent with our observation that users
need to be able to customise their partial reuse of ontologies.
The semantic for ontology import is an evolution of the semantics C-OWL
language [3]. The main difference concerns the interpretation of foreign rela-
tions. In C-OWL (i:R)Ij = (i:R)Ii ∩ ∆Ij × ∆Ij while in semantic import we
imposed the forward and backtrack closure. This update was necessary to allow
the propagation of properties on relations.
Our approach is also related to existing work on reasoning with distributed
Description Logics [15] and distributed First Order Logics [6]. In particular it is
still an open question if semantic imports can be obtained by suitably mapping
a concept (role or individual) on its native ontology with the occurrence of the
5
In Tab(Oj , T 0 ), meta-constraints M (T 0 ) = {A1 , . . . , An } is merged into the label of
each node in T 0 , where Ai = ¬Ci t Di for each Ci v Di in T 0 (1 ≤ i ≤ n).
Semantic Import: An Approach for Partial Ontology Reuse 13
concept in the importer ontology. The conjecture is that semantically importing
≡
i:C into the ontology W j corresponds to adding the mappings i:C −→ j:C,
≡
¬i:C −→ ¬j:C. 6 .
Ontology modularisation [16, 4, 11, 5, 1] is an active topic in the field of ontol-
ogy reuse. StuckenSchmidt and Klein [16] propose a structure-based approach for
partitioning large class hierarchies. Cuenca-Grau et al. [4] present a partitioning
algorithm, based on e-connections [7]. The partitioning of an ontology is auto-
matic, although the modularisation is not always possible. Later, Cuenca-Grau
et al. [5] propose the notion of safe ontologies, which are ontologies that can be
modularised. The idea of safe ontologies is based on the notion of local/non-local
classes (which we call positive/negative classes); see Section 4.1 for more details.
Besides using different kind of cross-domain semantics, the main differences be-
tween our approach and Cuenca-Grau et al.’s approach include: (1) the reusable
units in our approach are some vocabulary (such as classes or properties) rather
than axioms; (2) our approach allows users to agree or disagree with some sub-
sumption relations in distant ontologies, while modules of ontologies are required
to preserve subsumptions among named classes; (3) unlike the modularisation
operator, the semantic imports operator can be used between any two ontologies
in an ontology space.
6 Discussion
How to support ontology reuse is becoming more and more important. While the
“copy-and-paste” approach suffers a number of problems, this paper proposes a
new import primitive, called semantic import, to facilitate partial ontology reuse.
In this paper, we have identified four semantic requirements for semantic import:
propagation of class hierarchy, disjoint classes, property closure and (in)equality
objects. Secondly, we have investigated the logical properties of semantic imports
in simple ontology spaces. Based on the notion of positive/negative classes first
proposed by Cuenca-Grau et al. [5], several categories of subsumption relations
(knowledge) class descriptions over the agreed vocabulary have been shown to
be transferrable form distant ontologies to the target ontology. Finally, we have
presented a distributed algorithm for TBox reasoning of semantic import of ALC
ontologies in simple ontology spaces.
An important “side effect” of introducing semantic import into ontology lan-
guages such as OWL DL is to open a door to support the intended usage of URI
references, i.e. identifying resources. In OWL DL, the same individual URIref
can be interpreted as different objects in different ontologies, where URI refer-
ences are not really playing a role on identifying resources. In the presence of
semantic import, however, the semantic of ontology space guarantees that an
semantically imported individual is interpreted as the same object in multiple
ontologies. This suggests that semantic import could play a very fundamental
role in Web ontologies under the unique identification assumption.
6
Thanks to Andrei Tamilin for this intuition
14 Jeff Z. Pan, Luciano Serafini and Yuting Zhao
As for future work, we would like to further investigate logical consequence
of more complex ontology spaces and distributed tableaux algorithms for more
expressive ontology languages, such as OWL DL.
References
1. J. Bao, D. Caragea, and V. Honavar. A Distributed Tableau Algorithm for Package-
based Description Logics. In Proc. of the Second International Workshop on Con-
text Representation and Reasoning, 2006.
2. T. Berners-lee. Semantic Web Road Map. W3C Design Issues. URLhttp://www.
w3.org/DesignIssues/Semantic.html, Oct. 1998.
3. P. Bouquet, F. Giunchiglia, F. van Harmelen, L. Serafini, and H. Stuckenschmidt.
C-owl – contextualizing ontologies. In Proc. of the 2nd International Semantic
Web Conference, pages 164–179, 2003.
4. B. Cuenca-Grau, B. Parsia, E. Sirin, and A. Kalyanpur. Modularizing OWL On-
tologies. In Proc. of the KCAP-2005 Workshop on Ontology Management.
5. B. Cuenca-Grau, B. Parsia, E. Sirin, and A. Kalyanpur. Modularity and Web
Ontologies. In KR2006, 2006.
6. C. Ghidini and L. Serafini. Distributed First Order Logics. In Frontiers of Com-
bining Systems 2, Studies in Logic and Computation, 2000.
7. O. Kutz, C. Lutz, F. Wolter, and M. Zakharyaschev. E-connections of description
logics. In Proc. of DL-2003, pages 178–187, 2003.
8. A. Maedche, B. Motik, L. Stojanovic, R. Studer, and R. Volz. An infrastructure
for searching, reusing and evolving distributed ontologies. In Prof. of WWW2003,
pages 439–448.
9. SUMO ontology. http://ontology.teknowledge.com/, 2005.
10. J. Z. Pan and I. Horrocks. OWL-Eu: Adding Customised Datatypes into OWL.
In Proc. of Second European Semantic Web Conference (ESWC 2005), 2005. Its
revised and extended version is accepted in Journal of Web Semantics, 4(1).
11. E. B. Paslaru, M. Mochol, and R. Tolksdorf. Case Studies on Ontology Reuse. In
Proc. of the 5th Int. Conf. on Knowledge Management, 2005.
12. P. F. Patel-Schneider, P. Hayes, and I. Horrocks. OWL Web Ontology Language
Semantics and Abstract Syntax. Technical report, W3C, Feb. 2004. W3C Recom-
mendation, URL http://www.w3.org/TR/2004/REC-owl-semantics-20040210/.
13. K. Schild. A correspondence theory for terminological logics: Preliminary report.
In Int. Joint Conf. on Artificial Intelligence, pages 466–471, 1991.
14. M. Schmidt-Schauß and G. Smolka. Attributive concept descriptions with comple-
ments. Artificial Intelligence, 48:1–26, 1991.
15. L. Serafini, A. Borgida, and A. Tamilin. Aspects of Distributed and Modular
Ontology Reasoning. In Int. Joint Conf. on Artificial Intelligence, pages 570–575,
2005.
16. H. Stuckenschmidt and M. Klein. Structure-based partitioning of large concept
hierarchies. In Proc. of Int. Semantic Web Conf., 2004.
17. M. Uschold and M. Gruninger. Ontologies: Principles, Methods and Applications.
The Knowledge Engineering Review, 1996.
18. M. Uschold, M. Healy, K. Williamson, P. Clark, and S. Woods. Ontology reuse
and application. In Proc of the Int Conf on FOIS’98.
19. M. Uschold and M. King. Towards a methodology for building ontologies. In Proc.
of the IJCAI95, Workshop on Basic Ontological Issues in Knowledge Sharing, 1995.