=Paper=
{{Paper
|id=None
|storemode=property
|title=Local Safety of an Ontology
|pdfUrl=https://ceur-ws.org/Vol-584/paper4.pdf
|volume=Vol-584
|dblpUrl=https://dblp.org/rec/conf/itat/HomolaS09
}}
==Local Safety of an Ontology==
https://ceur-ws.org/Vol-584/paper4.pdf
Local safety of an ontology?
Lukáš Homoľa1 and Július Štuller2
1
Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University
lukashomola@hotmail.com
2
Institute of Computer Science, Academy of Sciences of the Czech Republic
stuller@cs.cas.cz
Abstract. The ability to import ontologies safely, that is, expertise/authority and cooperates with other teams
without changing the original meaning of their terms, has to relate the part it is working on with other parts.
been identified as crucial for the collaborative development Performing an upgrade of even only one such a com-
and the reuse of (OWL) ontologies. ponent ontology may require the participation of all
In this paper, we propose the notion of local safety of an on- the teams as different component ontologies are, when
tology and we identify scenarios in which this notion may
combined together, interrelated, depend on and affect
be useful in guiding the development of an ontology that is
to import other ontologies safely.
one another (changing one component ontology may
thus necessitate changes to the others and might re-
quire teams to reconcile their changes).
1 Introduction By reusing an ontology we mean using it as an
input to develop a new ontology. In such a process,
Defined as explicit specifications of conceptualizations
significant parts of the reused ontology are often ex-
of a domain of knowledge (or of a discourse) [1], ontolo-
tracted, refined, extended or otherwise adapted and
gies are (virtually) always manifestations of a shared
then combined with other ontologies to form the final
understanding of a domain. They typically take the
assembly.
form of a formal (e.g., logical) theory that fixes the
One of the prerequisites for efficient collaborative
vocabulary of a domain and, through constraining pos-
ontology construction and maintenance is the ability
sible interpretations and well-formed use of the vocab-
to combine ontologies in a controlled way. The interac-
ulary terms, provides meaning for the vocabulary.
tion among component ontologies should be controlled
Ontologies have been advocated as a tool to sup-
and well-understood in order to reduce the communi-
port human communication, knowledge sharing and
cation that is needed among different teams and to
reuse, and interoperability between distributed sys-
avoid expensive reconciliation processes. Ideally, con-
tems. As such, ontologies have a range of applica-
trolled interaction should allow different teams to de-
tions in fields like knowledge management, informa-
velop, test and upgrade their ontologies independently,
tion retrieval and integration, cooperative information
to replace a component ontology or extend an ontology
systems, bioinformatics, medicine, linguistics, e-com-
with minimal side effects. The issue is also vital for on-
merce, etc. Today, they are perhaps best known as the
tology reuse, especially in the case when the reused on-
key technology of the Semantic Web vision.
tology, rather than being adapted and used as a draft
The construction of a typical ontology is a collab-
to develop an ontology component, is linked to and
orative process that involves direct cooperation among
remains under the control of its original developers,
multiple individuals or groups of ontology engineers
who may perform changes to it autonomously.
and domain experts (sometimes from different do-
mains of expertise and different organizations) and/or
indirect cooperation through the reuse of previously
published, autonomously developed ontologies. 2 Problem definition
Most often, each team participating in the develop-
ment of an ontology focuses on a part of it (a “compo- The Web Ontology Language (OWL) [2], a widely ac-
nent ontology”) that pertains to the team’s domain of cepted W3C recommendation for creating and sharing
? ontologies on the Web, provides only very limited sup-
The work was supported by the project No. 1M0554
“Advanced Remedial Processes and Technologies” of the
port for combining ontologies.
Ministry of Education, Youth and Sports of the Czech OWL adopts an importing mechanism, imple-
3
Republic and partly by the Institutional Research Plan mented by the owl:imports construct, which allows
AV0Z10300504 “Computer Science for the Information one to include in an OWL ontology all the statements
Society: Models, Algorithms, Applications”. The first
3
author also acknowledges the financial support of the http://www.w3.org/2002/07/owl#imports, to be pre-
Department of Mathematics at his institution. cise
24 Lukáš Homoľa, Július Štuller
contained in some other OWL ontology. In the import- built using concept and role constructors. We assume
ing ontology, there is no logical difference between the the sets C, R and I of (respectively) atomic concepts,
statements that are imported and the proper ones. atomic roles and individuals to be countably infinite
A number of recent papers by Grau et al. [3–7] and mutually disjoint and to be fixed for every DL.
stressed the particular relevance of the ability to im- An ontology O formalized in a DL takes the form of
port OWL ontologies “safely”, that is, in such a way a finite set of terminological and role axioms, which
that the imported terms (the terms of the imported are used to suitably organize and interrelate multiple
ontologies) preserve their original meaning (the mean- concept and role descriptions. DLs are distinguished
ing these terms have in the imported ontologies) in the by constructors and/or types of axioms they provide.
importing ontology. This ability is applicable in typi- We will use the term L-axiom (L-ontology) to empha-
cal scenarios of OWL ontology development such as in size we are talking about an axiom (an ontology) in
the following one (see the above-mentioned works by the DL L.
Grau et al. for a motivating example): In the abstract notation we will use the letters A, B
to denote atomic concepts, r, s to denote atomic roles,
– an ontology engineer distinguishes between the so-
and a, b for individuals (all the letters possibly with
called external terms and the so-called local terms
a subscript). The letters C, D will be used to denote
of the ontology O he or she is developing;
a concept (atomic or complex), R, S to denote a role,
– the local terms are those whose meaning is as-
and α, β to denote an axiom.
sumed to be fully described in the ontology O it-
self, possibly with the help of the remaining, ex- As the minimal DLs of practical interest are usu-
ternal terms; ally considered the DLs EL and AL, which both are
– the meaning of the external terms is assumed to fragments of the smallest propositionally closed DL
be only partially described in the ontology O – in ALC. In ALC, concepts are composed inductively ac-
terms of their use in the description of the local cording to the following syntax rule:
terms – and to be further described in some other
C, D → A (atomic concept) |
ontologies (preexistent or concurrently developed)
that are to be imported into O; ⊥ (bottom concept) | > (top concept) |
– the use of the external terms in the statements of ¬C (concept negation) |
the ontology O is expected not to alter the original C u D (conjunction) | C t D (disjunction) |
meaning these terms have in the ontologies to be
∃R.C (existential restriction) |
imported.
∀R.C (value restriction).
In the paper, we continue in the study, initiated
by Grau at al., of the methodology for OWL ontology Valid constructs for EL are: ⊥, C u D and ∃R.C.
development in the scenario given above. We propose In AL, the syntax of complex concepts is the follow-
the notion of local safety of an ontology and discuss ing: ⊥, >, ¬A (atomic concept negation), C uD, ∃R.>
under which conditions and how this notion can be (limited existential restriction), and ∀R.C.
used to guide the development of OWL ontologies. DLs EL, AL and ALC provide no role constructors.
The listed ALC constructors are not all indepen-
3 Preliminaries dent (> = ¬⊥, C t D = ¬(¬C u ¬D), ∀R.C =
¬(∃R.¬C)). In fact, ALC can be obtained from both
In this section we introduce description logics (DLs) [8], EL and AL by adding the concept negation construc-
a family of logic-based knowledge representation for- tor.
malisms, which underly modern ontology languages A terminological axiom in EL, AL and ALC is an
such as OWL. OWL consists of three (sub)languages expression of the following forms: A ≡ C (concept de-
of increasing expressive power, two of which, namely finition), A v C (concept specialization) or C v D
OWL Lite and OWL DL, roughly correspond to the (general concept inclusion, GCI). The abbreviation of
DLs SHIF and SHOIN , respectively. the form C ≡ D (concepts equality) stands for the two
DLs view the world as being populated by ob- GCIs C v D and D v C. EL, AL and ALC provide
jects and allow one to represent the relevant notions of no role axioms.
the domain of interest in terms of concepts, roles and S is an extension of ALC in which an atomic role
(possibly) individuals, representing sets of elements, can be declared transitive using the role axiom of the
binary relationships between elements and single el- form Trans(r).
ements, respectively. Starting from atomic concepts, Further extensions of DLs are indicated by ap-
atomic roles and individuals, which are denoted sim- pending letters to the DL’s name. Advanced concept
ply by a name, complex concepts and complex roles are constructors include number restrictions of the form
Local safety of an ontology 25
≥ nR (indicated by appending the letter N ), quali- O |= C v D, and satisfiability of concept C in the
fied number restrictions ≥ nR.C (appending Q) and case O 6|= C v ⊥.
nominals {a} (appending O). In the case of num-
Interpretations I and J are isomorphic (written
ber restrictions and qualified number restrictions, the
I ∼= J ) iff there is a bijection µ : ∆I → ∆J such
dual constructors ≤ nR and ≤ nR.C are introduced
that for every x, y ∈ ∆I , A ∈ C, r ∈ R, a ∈ I the
as abbreviations for ¬(≥ n + 1R) and ¬(≥ n + 1R.C),
following holds: x ∈ AI iff µ(x) ∈ AJ , (x, y) ∈ rI iff
respectively. Nominals allows to construct a concept
(µ(x), µ(y)) ∈ rJ , x = aI iff µ(x) = aJ . Isomorphic
representing a singleton set containing one individ-
interpretations are semantically indistinguishable (in
ual. Enumeration {a1 , . . . , an } is an abbreviation for
particular, they satisfy the same axioms).
{a1 } t . . . t {an }.
Yet other extensions include role constructors, of A signature S is a finite subset of C∪R∪I. Two in-
which the inverse role constructor r− (appending I) terpretations I and J coincide on a signature S (writ-
is the most prominent one. Another important type of ten I|S = J |S ) iff ∆I = ∆J and X I = X J holds for
role axioms is the role inclusion R v S (appending H). all X ∈ S.
These extensions can be used in different combina-
We say that I has been obtained from J through
tions, for example ALN is an extension of AL with
a domain expansion with the set ∆ (such I will by
number restrictions, and SHOIN is the DL that uses
denoted by J∪∆ ) iff ∆ is a non-empty set disjoint
5 of the constructors we have presented.
with ∆J , ∆I = ∆J ∪ ∆, and X I = X J holds for all
The semantics of DLs is defined via interpretations. X ∈ C ∪ R ∪ I. Note that J∪∆ and J only differ in
An interpretation I is a pair I = (∆I , .I ), where ∆I that the domain of J is a proper subset of the domain
is a non-empty set, called the domain of the inter- of J∪∆ (with ∆ being the set of additional domain
pretation, and .I is the interpretation function, which elements).
maps atomic concepts to subsets of ∆I , atomic roles to
binary relations over ∆I and individuals to elements A DL L is said to have the finite model property
of ∆I . The interpretation function extends to complex (FMP) iff every consistent L-ontology admits a model
concepts as follows: that is finite (i.e., with a finite domain). One of the
most prominent DLs that exhibit the FMP is SHOQ,
⊥I = ∅, >I = ∆I , while SHIN is an example of a DL that lacks the
(C u D)I = C I ∩ DI , (C t D)I = C I ∪ DI , FMP. For a DL L with the FMP, L-ontology O and
L-axiom α the following holds: O |= α iff I |= α for
(¬C)I = ∆I − C I ,
all finite models I |= O.
(∀R.C)I = {x ∈ ∆I ; ∀y ((x, y) ∈ RI → y ∈ C I )},
We say that an interpretation K is a disjoint union
(∃R.C)I = {x ∈ ∆I ; ∃y ((x, y) ∈ RI ∧ y ∈ C I )},
of interpretations I and J (written K = I ] J ) iff
(≥ nR)I = {x ∈ ∆I ; |{y ∈ ∆I ; (x, y) ∈ RI }| ≥ n}, there exist some interpretations Ĩ and J˜ satisfying
˜
(≥ nR.C)I = {x ∈ ∆I ; Ĩ ∼
= I, J˜ ∼= J and ∆Ĩ ∩ ∆J = ∅ for which the fol-
˜ ˜
|{y ∈ ∆I ; (x, y) ∈ RI ∧ y ∈ C I }| ≥ n}, lowing holds: ∆K = ∆Ĩ ∪ ∆J , X K = X Ĩ ∪ X J for all
{a} = {aI },
I X ∈ C ∪ R and aK = aĨ for all a ∈ I. Intuitively, the
interpretation K for which K = I ] J holds is com-
(r− )I = {(x, y); (y, x) ∈ rI }.
posed of two unrelated parts one being isomorphic
to I and the other to J . Disjoint union of a set of
The semantics of terminological axioms is defined in
interpretations is defined analogously.
terms of a satisfaction relation |=, which relates inter-
pretations to the terminological axioms they satisfy. A DL L is said to have the disjoint union model
It is defined as follows: I |= C v D iff C I ⊆ DI , property (DUMP) iff the set of models of arbitrary
I |= R v S iff RI ⊆ S I , I |= C(a) iff aI ∈ C I , L-ontology is closed under disjoint unions.
I |= R(a, b) iff (aI , bI ) ∈ RI , I |= Trans(r) iff the
relation rI is transitive. Interpretations satisfying an A prominent example of a DL that enjoys the
axiom are said to be its models. DUMP is SHIQ. DLs that support nominals do not
have this property.
An interpretation I is a model of an ontology O
(written I |= O) iff I |= α for all α ∈ O. An ontology In the subsequent sections, will use C(α) to denote
is said to be consistent if it has at least one model and the set of all atomic concepts that occur in the axiom α
is said to be inconsistent otherwise. (the sets R(α) and I(α) are defined analogously). We
An ontology O entails an axiom α (written O |= α) will use Sig(α) as a shorthand
S for C(α) ∪ R(α) ∪ I(α).
iff all models of O satisfy α, especially we will speak C(O) will stand for α∈O C(α) (the sets R(O), I(O)
about subsumption between C and D in the case of and Sig(O) are defined analogously).
26 Lukáš Homoľa, Július Štuller
4 Related work As Grau et al. showed, even the problem of check-
ing whether an ontology consisting of a single ALC ax-
In the papers by Grau et al. [3–7], safety of ontology iom is safe for a signature w.r.t. ALCO is undecidable.
import is formulated using the notion of conservative It is not yet known whether the safety for a signature
extension, in the context of ontologies first used in [9] is decidable for weaker DLs, such as EL, or for more
and recently further studied in [10, 11]. expressive DLs. Grau et al. proposed several safety
classes of ontologies, parametrized by a signature S
Definition 1 (Conservative extension). Let L be and representing sufficient conditions for safety for S,
a DL, O1 and O2 two ontologies such that O1 ⊆ O2 . that are decidable and can be checked syntactically in
We say that O2 is a deductive conservative ex- polynomial time.
tension of O1 w.r.t. L, if for every L-axiom α with Several extensions to OWL have been proposed
Sig(α) ⊆ Sig(O1 ), we have O2 |= α iff O1 |= α. to better support collaborative ontology develop-
An ontology O into which an ontology O0 can be safely ment and ontology reuse, including P-OWL [13],
imported is said to be safe for O0 . C-OWL [14], the extension based on E-connec-
tions [15] and the extension based on the so-called
Definition 2 (Safety for an ontology). Let L be semantic import [16]. All such extension are, however,
a DL, O and O0 two ontologies. still subjects of research and are not included in the
We say that O is safe for O0 w.r.t. L, if O ∪ O0 is current candidate recommendation for OWL 2 [17], an
a conservative extension of O0 w.r.t. L. ongoing extension to and revision of OWL.
Ghilardi at al. [12] studied novel DL reasoning services
aimed at supporting developers in customizing their 5 Local safety of an ontology
ontology to be safe for a particular ontology.
As regards the scenario we are concerned with,
The notion of safety for a signature, along with the
Grau et al. [3–7] argues that in practice it is often
corresponding safety classes, facilitates the construc-
convenient, or even necessary, for the developers of an
tion of an ontology that is safe for any ontology (in
ontology O to abstract from particular ontologies that
a given DL) with which it shares only some pre-
are to be imported into it and focus instead only on O
arranged set of terms.
and on its external terms:
In the scenario we are interested in here, however,
– ontologies to be imported might not be available an ontology engineer does not always need to have
during the development of O (as it is in the case the ontology O safe for every possible ontology (every
when these ontologies are developed concurrently possible set of axioms in a certain DL), but often only
with O); needs to have it safe for a certain, conveniently cho-
– the developers of O are usually not willing to com- sen class of candidate ontologies. This is the case, for
mit to particular versions of the ontologies they instance, when the scenario applies to collaborative
intend to import (the development of a typical on- ontology development and O is considered as a compo-
tology is a never-finished process); nent ontology for a larger ontology developed distribu-
– at a later time, the developers might find ontolo- tively as a set of ontologies importing one another. The
gies other than those initially considered more development of component ontologies in such a case is
suitable for providing the meaning of the external typically coordinated to some extent (e.g., some prin-
terms of O. ciples on which individual component ontologies will
be build are resolved beforehand and made explicit)
Grau et al. proposed the following condition to be used and the developers can make assumptions about some
to guide the development of an ontology O in such qualities and characteristics of the ontologies they im-
cases. port (as well as about the way these ontologies may
further evolve).
Definition 3 (Safety for a signature). Let L be
a DL, O an ontology and S a signature.
We say that O is safe for S w.r.t. L, if for every 5.1 Local ontologies
L-ontology O0 such that Sig(O) ∩ Sig(O0 ) ⊆ S, O is
safe for O0 w.r.t. L. Ontologies, like other engineering artifacts, are de-
signed. When we choose how to represent something
Once an ontology O is safe for the signature S (which in an ontology4 , we are making design decisions. The
is presumably the set of its external terms) w.r.t. L,
one can safely import into O any ontology O0 written 4 “There is no one correct way to model a domain – there
in L and sharing only terms from S with O. are always viable alternatives.” [18]
Local safety of an ontology 27
best solution to ontology design depends on a num- Intuitively, an ontology restricts the meaning of the
ber of factors, of which the most important include top concept if it introduces its vocabulary in such
the intended use of an ontology, and the anticipated a way that the vocabulary can only be further spe-
extensions and refinements to it. cialized but not otherwise monotonically extended. In
Generally accepted and widely cited are the five de- the case of domain, task and application ontologies
sign criteria Gruber [19] proposed for ontologies whose at least, such an ontology can be considered badly-
purpose is knowledge sharing and interoperation designed:
among programs. They include the following criterion:
– it can not be, without previous modification, ex-
An ontology should offer a conceptual founda-
tended to cover a broader subject area than it al-
tion for a range of anticipated tasks, and the
ready does,
representation should be crafted so that one
– it is unsuitable for importing into any ontology
can extend and specialize the ontology
that touches, even marginally, a subject area dis-
monotonically. Especially, one should be able
joint with that already covered by it.
to define new terms for special uses based on
the existing vocabulary, in a way that does not As regards top-level ontologies, we studied the Basic
require the revision of the existing definitions. Formal Ontology5 and also the design of several other
To facilitate the design, deployment and reuse of on- top-level ontologies [22], and came to the conclusion
tologies, Guarino [20] suggested the development of that even in this case the developers prefer not to re-
different kinds of ontologies with different levels of gen- strict the meaning of the top concept. The only excep-
erality and dependence on a particular domain, task tion we found is the top-level ontology6 proposed by
or point of view, namely top-level ontologies, domain John Sowa.
and task ontologies and application ontologies. Terms The notion of restricting the meaning of the top
of ontologies on a lower level are, in some sense, held concept is closely related to the notion of localness of
to be specializations of terms of ontologies on a level an ontology studied (also under the name safety of an
above. Top-level ontologies, which describe concepts ontology) by Grau et al. [23–26].
independent of a particular problem or domain (such
Definition 5 (Localness). An ontology O is local if
as space, time, object, event, action, etc.) are meant
the set of its models is closed under domain expansion
to be unifying for a large group of ontologies on lower
(i.e., if I |= O implies I∪∆ |= O for every interpreta-
levels.
tion I and every non-empty set ∆ disjoint with ∆I ).
Swartout et al. [21] proposed a number of desider-
ata aimed primarily at domain, task and application In [23], a syntactic characterization of localness for
ontologies. They include the two following: SHOIQ ontologies is given, which allows one to check
An ontology should be extensible. [. . . ] Exten- localness of an SHOIQ ontology in polynomial time.
sion should be possible both at a low level, by We used this characterization7 to show that SHOIQ
adding domain-specific subconcepts, or at high ontologies restricting the meaning of the top concept
level by adding intermediate or upper level con- are exactly those that are not local.
cepts that cover new areas. Proposition 1. A SHOIQ ontology restricts the
Ontologies should not be “stovepipes.” The de- meaning of the top concept iff it is not local.
risive term “stovepipe system” is used to de-
Grau et al. [25] also reported testing over 700 ontolo-
scribe a system that may be vertically inte-
gies available on the Web for localness and finding
grated but cannot be integrated horizontally
more than 99% of them local. However, we could not
with other systems.
trace any further details on their experimental results.
Here we propose a notion of restricting the mean-
ing of the top concept, which, as we believe, provide
a partial characterization of ontologies violating the 5.2 Local safety
aforementioned criteria. Regarding the development of an ontology in our sce-
Definition 4 (Restricting the meaning of the nario, the considerations above suggest that it is often
top concept). We say that the ontology O restricts possible to consider only local ontologies as the candi-
the meaning of the top concept, if there are atomic con- dates for importing.
cepts A1 , . . . , An , atomic roles r1 , . . . , rm , s1 , . . . , sk 5
and individuals a1 , . . . , al in Sig(O) such that: http://www.ifomis.org/bfo
6
http://www.jfsowa.com/ontology/toplevel.htm
O |= > v A1 t . . . t An t ∃r1 .> t . . . t ∃rm .> t 7
Relevant points of the characterization are reproduced
t ∃s−1 .> t . . . t ∃s −
k .> t {a1 , . . . , a l }. at the beginning of the Appendix.
28 Lukáš Homoľa, Július Štuller
Definition 6 (Local safety for a signature). Let Proposition 5. Let S be a signature such that S ⊆ C,
L be a DL, S a signature and O an ontology. O a SHIQ ontology and a an individual. Assume that
We say that O is locally safe for S w.r.t. L, if for there exists a subset S̃ ⊆ S such that the ontology
every local L-ontology O0 with Sig(O) ∩ Sig(O0 ) ⊆ S,
O is safe for O0 w.r.t. L. O ∪ {A ≡ {a}}A∈S̃ ∪ {A ≡ ⊥}A∈S−S̃
The following proposition provides sufficient condition is inconsistent.
for local safety w.r.t. SHOIQ. Then O is not locally safe for S w.r.t. ALO (ELO).
Proposition 2. Let S be a signature and O an ontol-
ogy such that for every interpretation J there exists Corollary 1. Let S be a signature such that S ⊆ C,
a model I of O such that O a SHIQ ontology.
Then O is locally safe for S w.r.t. SHOQ iff O is
– ∆I = ∆J ∪ ∆ for some ∆, ∆ ∩ ∆J = ∅, locally safe for S w.r.t. ALO (ELO).
I J
– X = X for all X ∈ S.
Then O is locally safe for S w.r.t. SHOIQ. Corollary 2. Let L be a DL that is in between ALO
(ELO) and SHOQ.
The following example demonstrates that, in compar- The problem of deciding whether a SHIQ ontol-
ison with safety condition proposed by Grau et al., ogy is locally safe for a signature S, S ⊆ C, w.r.t. L
the condition of local safety is less restrictive and may is reducible to the problem of checking consistency of
allow for a more convenient use of the external terms. a finite set of SHOIQ ontologies, and thus decidable.
Example 1. Let us consider building an OWL ontol-
ogy intended to provide a reference terminology for the Corollary 3. Let O be a SHIQ ontology locally safe
0
annotation of films. Let us assume we intend to safely for S ⊆ C w.r.t. SHOQ, O a local SHOQ ontology
0 0
import into our ontology O some well-designed (and such that Sig(O)∩Sig(O ) ⊆ S. Then O∪O is locally
0
thus local) ontology that defines the categorization of safe for S \ Sig(O ) w.r.t. SHOQ.
films by genre. Suppose that the atomic concept Film
is expected to be the only term our ontology will share
6 Conclusion and outlook
with the imported ontology. Whereas the ontology
O = {Director v ¬Film, Film v ∃hasDirector.Director} This paper contributes to the framework for ontology
development presented by Grau et al. We proposed
is not safe for {Film} even w.r.t. AL (take the non-
the notion of local safety of an ontology and showed
local ontology O0 = {> v Film} as a counterexample),
its applicability in the development of real-world on-
it is, according to Proposition 2, locally safe for {Film}
tologies. We showed that local safety for a signature
w.r.t. SHOIQ.
consisting solely of atomic concepts is decidable for an
When we are concerned with local safety w.r.t. SHOQ interesting group of description logics.
(which has the FMP) we can use the following suffi- For the future work, we would like to study de-
cient condition. cidability and computational properties of (sufficient
Proposition 3. Let S be a signature and O an on- conditions for) local safety for a signature that con-
tology such that for every finite interpretation J there tains atomic roles as well. The results obtained in the
exists a model I of O such that paper are also directly applicable to the problem of ex-
tracting reusable ontology parts, or ontology modules,
– ∆I = ∆J ∪ ∆ for some ∆, ∆ ∩ ∆J = ∅, as conceived by Grau et al. in the cited works.
– X I = X J for all X ∈ S.
Then O is locally safe for S w.r.t. SHOQ.
References
The two following propositions give a recipe for de-
ciding local safety of an ontology written in SHIQ 1. T.R. Gruber: A translation approach to portable ontol-
(which has the DUMP) w.r.t. SHOQ in the case when ogy specifications. Knowledge Acquisition, 5, 2, 1993,
all external terms are atomic concepts. 199–220.
Proposition 4. Let S be a signature such that S ⊆ C, 2. P. Patel-Schneider, P. Hayes, and I. Horrocks: OWL
Web Ontology Language: Semantics and Abstract Syn-
O a SHIQ ontology and a an individual. Assume that
tax. W3C recommendation, W3C, 2004. Available at
for every subset S̃ ⊆ S the ontology http://www.w3.org/TR/owl-semantics/.
O ∪ {A ≡ {a}}A∈S̃ ∪ {A ≡ ⊥}A∈S−S̃ 3. B.C. Grau, I. Horrocks, Y. Kazakov, and U. Sattler:
Ontology Reuse: Better Safe than Sorry. In Descrip-
is consistent. tion Logics, Bozen/Bolzano University Press, 2007,
Then O is locally safe for S w.r.t. SHOQ. 41–52.
Local safety of an ontology 29
4. B.C. Grau, I. Horrocks, Y. Kazakov, and U. Sattler: Technical report, Stanford Knowledge Systems Labo-
Just the right amount: extracting modules from ontolo- ratory, 2001. Available at http://protege.stanford.
gies. In Proc. of the 16th Int. World Wide Web Conf., edu/publications/ontology development/
2007, 717–727. ontology101-noy-mcguinness.html.
5. B.C. Grau, I. Horrocks, Y. Kazakov, and U. Sattler: 19. T.R. Gruber: Toward principles for the design of on-
A logical framework for modularity of ontologies. In tologies used for knowledge sharing . Int. Journal of
Proc. of the 20th Int. Joint Conf. on Artificial Intelli- Human-Computer Studies, 43, 5-6, 1995, 907–928.
gence, 2007. 20. N. Guarino: Formal ontology and information systems.
6. B.C. Grau, I. Horrocks, Y. Kazakov, and U. Sattler: In N. Guarino, editor, Proc. of the 1st Int. Conf. on
Modular reuse of ontologies: theory and practice. Jour- Formal Ontologies in Information Systems, IOS Press,
nal of Artificial Intelligence Research, 31, 2008, 273– 1998, 3–15.
318. 21. B. Swartout, R. Patil, K. Knight, and T. Russ: Toward
7. E. Jimenez-Ruiz, B.C. Grau, T. Schneider, U. Sattler, distributed use of large-scale ontologies. In Proc. of
and R. Berlanga: Safe and economic re-use of on- the 10th Knowledge Acquisition for Knowledge-Based
tologies: a logic-based methodology and tool support. Systems Workshop, 1996.
In Proc. of the 5th European Semantic Web Conf., 22. N.F. Noy and C.D. Hafner: The state of the art in
Springer LNCS, 2008. ontology design: A survey and comparative review. AI
8. F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, Magazine, 18, 1997, 53–74.
and P.F. Patel-Schneider, editors: The Description 23. B.C. Grau, B. Parsia, E. Sirin, and A. Kalyanpur:
Logic Handbook: Theory, Implementation, and Appli- Modularity and web ontologies. In P. Doherty, J. My-
cations. Cambridge University Press, 2003. lopoulos, and C. A. Welty, editors, Proc. the 20th Int.
9. G. Antoniou and A. Kehagas: A note on the the refine- Conf. on Principles of Knowledge Representation and
ment of ontologies. Int. Journal of Intelligent Systems, Reasoning, AAAI Press, 2006, 198–209.
15, 7, 2000, 623–632. 24. B.C. Grau, B. Parsia, E. Sirin, and A. Kalyanpur:
10. C. Lutz and F. Wolter: Conservative extensions in Automatic partitioning of OWL ontologies using E-
the lightweight description logic EL. In Proc. of the connections. In Proc. of the 18th Int. Workshop on
21th Conf. on Automated Deduction, Springer-Verlag, Description Logics, 2005.
2007, volume 4603, 84–99. 25. B.C. Grau, I. Horrocks, O. Kutz, and U. Sattler: Will
11. C. Lutz, D. Walther, and F. Wolter: Conservative ex- my ontologies fit together? In Proc. of the 19th Int.
tensions in expressive description logics. In M. Veloso, Workshop on Description Logics, 2006.
editor, Proc. of the 20th Int. Joint Conf. on Artificial 26. B.C. Grau and O. Kutz: Modular ontology languages
Intelligence, AAAI Press, 2007, 453–458. revisited. In Workshop on Semantic Web for Collab-
12. S. Ghilardi, C. Lutz, and F. Wolter: Did I damage orative Knowledge Acquisition at the 20th Int. Joint
my ontology? A case for conservative extensions in de- Conf. on Artificial Intelligence, 2007.
scription logics. In P. Doherty, J. Mylopoulos, and
C. Welty, editors, Proc. of the 10th Int. Conf. on Prin-
ciples of Knowledge Representation and Reasoning, 7 Appendix
AAAI Press, 2006, 187–197.
13. J. Bao and V. Honavar: Ontology language extensions
As shown in [23]:
to support localized semantics, modular reasoning, and
collaborative ontology design and ontology reuse. Tech- – for each SHOIQ concept C, one of the following
nical report, Iowa State University, 2004. holds:
14. P. Bouquet, F. Giunchiglia, F. van Harmelen, L. Ser-
• C I∪∆ = C I for all I and ∆, ∆ ∩ ∆I = ∅ (such
afini, and H. Stuckenschmidt: C-OWL: Contextualiz-
C is said to be local );
ing Ontologies. In Proc. of the Second Int. Semantic
Web Conf., Springer, 2003, 164–179. • C I∪∆ = C I ∪ ∆ for all I and ∆, ∆ ∩ ∆I = ∅
15. B.C. Grau, B. Parsia, and E. Sirin: Combining OWL (C is non-local ).
ontologies using E-Connections. Web Semantics: Sci- – If R is a SHOIQ role, then RI∪∆ = RI for all I
ence, Services and Agents on the World Wide Web, 4, and ∆, ∆ ∩ ∆I = ∅.
1, 2006, 40–59. – A SHOIQ ontology is not local iff it explicitly
16. J.Z. Pan, L. Serafini, and Y. Zhao: Semantic import: contain a GCI D v C such that C is local and D
an approach for partial ontology reuse. In P. Haase, is non-local.
V. Honavar, O. Kutz, Y. Sure, and A. Tamilin, editors,
Proc. of the 1st Int. Workshop on Modular Ontologies,
volume 232, CEUR-WS.org, 2006. Lemma 1 (Auxiliary). Let α be a SHOIQ axiom,
17. M. Boris, B.C. Grau, I. Horrocks, Z. Wu, A. Fokoue, I an interpretation and ∆ a set disjoint with ∆I .
and C. Lutz: OWL 2 Web Ontology Language: Pro- Then I 6|= α implies I∪∆ 6|= α.
files. W3C draft, W3C, 2009. Available at http://
www.w3.org/TR/2009/CR-owl2-profiles-20090611/. Proof. Suppose that I 6|= α.
18. N.F. Noy and D.L. Mcguinness: Ontology develop- If α is of the form C v D that means C I 6⊆ DI (?). For
ment 101: a guide to creating your first ontology. C, D local, we have C I∪∆ = C I and DI∪∆ = DI . By
30 Lukáš Homoľa, Július Štuller
(?), we get C I∪∆ 6⊆ DI∪∆ . For C local, D non-local, and symbols not occurring in Sig(O) ∩ Sig(O0 ) can be
we have C I∪∆ = C I and DI∪∆ = DI ∪ ∆. By (?) and interpreted arbitrarily.
by the fact that ∆ ∩ C I = ∅ (because ∆ ∩ ∆I = ∅), First, because I |= O and K|Sig(O) = I|Sig(O) ,
we get C I∪∆ 6⊆ DI∪∆ . For C non-local, D local, we K |= O holds. Second, because J |= O0 and O0 is local,
have C I∪∆ = C I ∪ ∆ and DI∪∆ = DI . By (?), we we have J∪∆ |= O0 and consequently, since K|Sig(O0 ) =
get C I∪∆ 6⊆ DI∪∆ . For C, D are non-local, we have J∪∆ |Sig(O0 ) , K |= O0 . Therefore K |= O ∪ O0 .
C I∪∆ = C I ∪ ∆ and DI∪∆ = DI ∪ ∆. By (?) and Since J 6|= α, we have, using Lemma 1, that
by the fact that ∆ ∩ C I = ∅, ∆ ∩ DI = ∅ (because J∪∆ 6|= α. Furthermore, since K|Sig(O0 ) = J∪∆ |Sig(O0 )
∆ ∩ ∆I = ∅), we get C I∪∆ 6⊆ DI∪∆ . For each of the and Sig(α) ⊆ Sig(O0 ), K 6|= α.
four possible cases we showed that I∪∆ 6|= C v D. We showed there exists a model of O ∪ O0 that is
The remaining types of SHOIQ axioms (C ≡ D, not a model of α, which yields a contradiction with
Trans(r), R v S) can be treated in the same way. u t the assumption (∗). u
t
Proof (of Proposition 3.). Same proof as of Proposi-
Proof (of Proposition 1.). The proposition is obviously
tion 2 goes through - we only need to replace the sen-
true for inconsistent ontologies.
tence labeled with (¦) with the following: Because (?)
Assume that a consistent ontology O restricts the
and because SHOQ has the FMP, there exists a finite
meaning of the top concept. Then, by Definition 4,
model J of O0 such that J 6|= α. u
t
O |= > v C for some C of the form A1 t . . . t An t
∃r1 .>t. . .t∃rm .>t ∃s− −
1 .>t. . .t∃sk .>t{a1 , . . . , al }. Proof (of Proposition 4.). Let J be a finite interpre-
Take any model I of O and any x ∈ / ∆I . As >I∪{x} = tation.
I I∪{x} I
∆ ∪ {x} and C = ∆ , I∪{x} 6|= > v C, and thus Let us associate with every x ∈ ∆J (∆J is finite)
I is not a model of O. This shows O is not local. an unique ax ∈ I, ax ∈/ Sig(O) (i.e., different elements
Assume a consistent SHOIQ ontology O does not are associated with different individuals). For every
restrict the meaning of the top concept. Then, by Def- x ∈ ∆J , let us set Sx = {A ∈ S; x ∈ AJ }.
inition 4, O 6|= > v C for C of the form A1 t . . . t An t The conditions of the proposition imply that for
∃r1 .>t. . .t∃rm .>t ∃r1− .>t. . .t∃rm −
.>t{a1 , . . . , al }, every x ∈ ∆J there exists a model Ix of
where A1 , . . . , An , r1 , . . . , rm and a1 , . . . , al are
all atomic concepts, atomic roles and individ- O ∪ {A ≡ {ax }}A∈Sx ∪ {A ≡ ⊥}A∈S−Sx .
uals in Sig(O). Since O 6|= > v C, there exists U
Pick some interpretation Ĩ such that Ĩ = x∈∆J Ix
a model I of O such that I 6|= > v C. Pick any such
and some interpretation I isomorphic with Ĩ such that
model I. Since I 6|= > v C, there exists an object
x ∈ ∆I such that x do not participate in the in- ax I = x for all x ∈ ∆J (to get such interpretation I it
terpretation X I of any atomic concept, atomic role is enough to “rename” finitely many elements in ∆Ĩ ).
and individual X in Sig(O). Observe that: for all lo- Since Ix |= O for all x ∈ ∆J , O is a SHIQ on-
cal SHOIQ concepts C1 composed of the symbols tology, SHIQ has the DUMP, ∆J is finite, we have
from Sig(O), x ∈ / C1I holds; for all non-local SHOIQ Ĩ |= O and consequently, since I ∼ = Ĩ, I |= O (?).
concepts C2 composed of the symbols from Sig(O), As ax I = x for all x ∈ ∆J , we have ∆J ⊆ ∆I (∗).
x ∈ C2I holds. Therefore, O does not contain a GCI It is easy to see that for A ∈ S and x ∈ ∆J the
of the form C2 v C1 (otherwise I were not its model) following holds: AIx = {ax Ix } if x ∈ AJ ; AIx = ∅ if
S
and thus is local. x∈ / AJ . Thus, for A ∈ S S
u
t we have AĨ = S x∈AJ {ax }
Ĩ
I I
and, consequently, A = x∈AJ {ax } = x∈AJ {x},
I J
Proof (of Proposition 2.). Let O be an arbitrary local and thus A = A (¦).
0
SHOIQ ontology with Sig(O) ∩ Sig(O0 ) ⊆ S. We We showed that, for any finite interpretation J ,
0
need to show that O ∪ O is a conservative extension there exists an interpretation I satisfying (?, ∗, ¦). Us-
0
of O w.r.t. SHOIQ. ing Proposition 3 we have that O is locally safe for S
Assume (for contradiction) that there exists w.r.t. SHOQ. u
t
0
a SHOIQ axiom α with Sig(α) ⊆ Sig(O ) for which Proof (of Proposition 5.). Consider an ALO (ELO)
both O0 6|= α (?) and O ∪ O0 |= α (∗) hold. ontology O0 = {A ≡ {a}}A∈S̃ ∪ {A ≡ ⊥}A∈S−S̃ ,
By (?), there is a model J of O0 such that J 6|= α. (¦) which evidently is local, satisfies Sig(O) ∩ Sig(O0 ) ⊆
The conditions of the proposition imply the exis- S and is consistent (O0 6|= > v ⊥). The conditions
tence of a model I of O such that ∆I = ∆J ∪ ∆, ∆ ∩ of the proposition say that the ontology O ∪ O0 is
∆J = ∅ and X I = X J for all X ∈ S. Pick any inter- inconsistent (O ∪ O0 |= > v ⊥). We showed that
pretation K satisfying: ∆K = ∆I , X K = X I for all X ∈ there exists a local ALO (ELO) ontology O0 satisfying
Sig(O), X K = X J for all X ∈ Sig(O0 ). Such an inter- Sig(O) ∩ Sig(O0 ) ⊆ S for which O is not safe. u
t
pretation exists as X I = X J for X ∈ Sig(O)∩Sig(O0 ),