=Paper=
{{Paper
|id=None
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-969/proceedings.pdf
|volume=Vol-969
}}
==None==
https://ceur-ws.org/Vol-969/proceedings.pdf
ADVANCES IN ONTOLOGIES
Proceedings of the Eighth Australasian
Ontology Workshop, Sydney, Australia
4 December 2012
Editors
Aurona Gerber
Kerry Taylor
Tommie Meyer
Mehmet Orgun
Preface
The Australasian Ontology Workshop series was initiated in 2005, and AOW
2012 is the eighth in the series. In 2012, AOW was held on the 4th of December
2012 in Sydney, Australia. Like most of the previous events AOW 2012 was held
as a workshop of the Australasian Joint Conference on Artificial Intelligence
celebrating its 25th anniversary as AI2012.
Out of papers submitted, we accepted 5 full papers and 4 short papers on the
basis of three or four reviews submitted by our Program Committee of
international standing. The submissions covered an interesting balance of topics
with papers on fundamental research in ontologies, to ontology applications. We
were pleased to note that we again attracted international authors.
As in previous years, an award of $250 AUD was made available for the best
paper, sponsored this year by CAIR 1 (the Centre for Artificial Intelligence
Research in South Africa). In 2012 the best paper prize was awarded to Giovanni
Casini and Alessandro Mosca for their paper "Defeasible reasoning in ORM2".
AOW 2012 was the last AOW in its current form. From 2013 AOW will be
replaced by the Australasian Semantic Web Conference (ASWC). The 12th
International Semantic Web Conference (ISWC) and the 1st Australasian
Semantic Web Conference (ASWC) will be held 21-25 October 2013 in Sydney,
Australia and from 2014 onwards, ASWC will be a free-standing conference.
Many individuals contributed to this workshop. We thank our contributing authors
and dedicated international Program Committee for their careful reviews in a tight
time frame. We also thank CAIR for sponsoring the memory keys containing the
proceedings. We acknowledge the EasyChair conference management system,
which was used in all stages of the paper submission and review process and
also in the collection of the final camera-ready papers, as well as the Yola web
authoring system for our website available at http://aow2012.yolasite.com. We
hope that you found this eighth Australasian Ontology Workshop to be
informative, thought provoking, and most of all, enjoyable!
Kerry Taylor (CSIRO ICT Centre, Australia) (co-chair)
Aurona J. Gerber (CAIR, South Africa) (co-chair)
Tommie Meyer (CAIR, South Africa) (co-chair)
Mehmet A. Orgun (Macquarie University, Australia) (co-chair)
Organisers of AOW 2012
December 2012
1
http://www.cair.za.net/
Page 1 of 110
Conference Organisation
Programme Chairs
Kerry Taylor (CSIRO ICT Centre, Australia)
Aurona J. Gerber (CAIR – Centre for Artificial Intelligence Research, South Africa)
Tommie Meyer (CAIR – Centre for Artificial Intelligence Research, South Africa)
Mehmet A. Orgun (Macquarie University, Australia)
Programme Committee
Franz Baader TU Dresden
Michael Bain UNSW
Arina Britz Meraka Institute, CSIR
Giovanni Casini CAIR (CSIR and UKZN)
Werner Ceusters SUNY at Buffalo
Michael Compton CSIRO
Oscar Corcho Universidad Politécnica de Madrid
Atilla Elci Süleyman Demirel University
R. Cenk Erdur Ege University
Peter Fox TWC/RPI
Manolis Gergatsoulis Dept. of Archive and Library Science, Ionian University
Tudor Groza School of ITEE, The University of Queensland
Armin Haller Digital Enterprise Research Institute (DERI), National University of Ireland,
Galway
Knut Hinkelmann University of Applied Sciences Northwestern Switzerland FHNW
Bo Hu SAP Research
C. Maria Keet School of Mathematics, Statistics, and Computer Science, University of
KwaZulu-Natal, South Africa
Aneesh Krishna Curtin University, Australia
Kevin Lee National ICT Australia and University of New South Wales
Laurent Lefort CSIRO ICT Centre
Yuan-Fang Li Monash University
Constantine Mantratzis University of Westminster
Deshendran Moodley University of Computer Science
Maurice Pagnucco The University of New South Wales
Jeff Z. Pan University of Aberdeen
Deborah Richards Macquarie University
Rolf Schwitter Macquarie University
Barry Smith SUNY Buffalo
Markus Stumptner University of South Australia
Vijayan Sugumaran School of Business Administration, Oakland University, Rochester, MI
48309, USA
Boontawee Suntisrivaraporn Sirindhorn International Institute of Technology
Sergio Tessaris Free University of Bozen - Bolzano
Nwe Ni Tun Research Fellow
Ivan Varzinczak Centre for AI Research, CSIR Meraka Institute and UKZN
Kewen Wang Griffith University
Levent Yilmaz Auburn University
Antoine Zimmermann École des Mines de Saint-Étienne
Page 2 of 110
AOW 2012 Accepted Papers
Giovanni Casini and Defeasible reasoning in ORM2. p.4
Alessandro Mosca.
Zhe Wang, Kewen OntoMerge: A System for Merging DL-Lite Ontologies. p.16
Wang, Yifan Jin and
Guilin Qi.
Giovanni Casini and Lexichographic Closure for Defeasible Description Logics. p.28
Umberto Straccia.
Riku Nortje, Arina Britz A normal form for hypergraph-based module extraction for p.40
and Tommie Meyer. SROIQ.
Doug Foxvog. Two Case Studies of Ontology Validation. p.52
Artemis Parvizi, Non-Taxonomic Concept Addition to Ontologies. p.64
Roman Belavkin and
Christian Huyck.
Brandon Whitehead Deep Semantics in the Geosciences: semantic building blocks for p.74
and Mark Gahegan. a complete geoscience infrastructure.
Eric Snow, Chadia Assessing Procedural Knowledge in Open-ended Questions p.86
Moghrabi and Philippe through Semantic Web Ontologies.
Fournier-Viger.
Aurona Gerber, Nelia Using Formal Ontologies in the Development of p.98
Lombard and Alta van Countermeasures for Military Aircraft.
der Merwe.
Page 3 of 110
Defeasible reasoning in ORM2
Giovanni Casini1 and Alessandro Mosca2
1
Centre for Artificial Intelligence Research, CSIR Meraka Institute and UKZN, South Africa
Email: GCasini@csir.co.za
2
Free University of Bozen-Bolzano, Faculty of Computer Science, Italy
Email: mosca@inf.unibz.it
Abstract. The Object Role Modeling language (ORM2) is one of the main con-
ceptual modeling languages. Recently, a translation has been proposed of a main
fragment of ORM2 (ORM2zero ) into the description logic ALCQI, allowing the
use of logical instruments in the analysis of ORM schemas. On the other hand, in
many ontological domains there is a need for the formalization of defeasible infor-
mation and of nonmonotonic forms of reasoning. Here we introduce two new con-
straints in ORM2 language, in order to formalize defeasible information into the
schemas, and we explain how to translate such defeasible information in ALCQI.
1 Introduction
ORM2 (‘Object Role Modelling 2’) is a graphical fact-oriented approach for modelling,
transforming, and querying business domain information, which allows for a verbal-
isation in a language readily understandable by non-technical users [1]. ORM2 is at
the core of the OGM standard SBVR language (‘Semantics of Business Vocabulary
and Business Rules’), and of conceptual modelling language for database design in Mi-
crosoft Visual Studio (VS). In particular, the Neumont ORM Architect (NORMA) tool
is an open source plug-in to VS providing the most complete support for the ORM2
notation.
On the other hand, in the more general field of formal ontologies in the last years a
lot of attention has been dedicated to the implementations of forms of defeasible reason-
ing, and various proposals, such as [2,3,4,5,6,7,8], have been made in order to integrate
nonmonotonic reasoning mechanisms into DLs.
In what follows we propose an extension of ORM2 with two new formal constraints,
with the main aim of integrating a form of defeasible reasoning in the ORM2 schemas;
we explain how to translate such enriched ORM2 schemas into ALCQI knowledge
bases and how to use them to check the schema consistency and draw conclusions.
In particular, the paper presents a procedure to implement a particular construction in
nonmonotonic reasoning, i.e. Lehmann and Magidor’s Rational Closure (RC)[9], that is
known for being characterized by good logical properties and for giving back intuitive
results.
2 Fact-oriented modelling in ORM2
‘Fact-oriented modelling’ began in the early Seventies as a conceptual modelling ap-
proach that views the world in terms of simple facts about individuals and the roles they
play [1]. Facts are assertions that are taken to be true in the domain of interest about
Page 4 of 110
Fig. 1. A conceptual schema including an instantiation of most of the ORM2 constraints.
objects playing certain roles (e.g. ‘Alice is enrolled in the Computer Science program’).
In ORM2 one has entities (e.g. a person or a car) and values (e.g. a character string or
a number). Moreover, entities and values are described in terms of the types they belong
to, where a type (e.g. House, Car) is a set of instances. Each entity in the domain of
interest is, therefore, an instance of a particular type. The roles played by the entities
in a given domain are introduced by means of logical predicates, and each predicate
has a given set of roles according to its arity. Each role is connected to exactly one ob-
ject type, indicating that the role is played only by the (possible) instances of that type
((e.g. TYPE(isBy.Student,Student)) - notice that, unlike ER, ORM2 makes no use of
‘attributes’). ORM2 also admits the possibility of making an object type out of a rela-
tionship. Once a relation has been transformed into an object type, this last is called the
objectification of the relation.
According to the ORM2 design procedure, after the specification of the relevant
object types (i.e. entity and value types) and predicates, the static constraints must be
considered. The rest of this section is devoted to an informal introduction of the con-
straint graphical representation, together with their intended semantics. Fig. 1 shows an
example of an ORM2 conceptual schema modelling the ‘academic domain’ (where the
soft rectangles are entity types, the dashed soft rectangles are value types, and the se-
quences of one or more role-boxes are predicates). The example is not complete w.r.t.
the set of all the ORM2 constraints but it aims at giving the feeling of the expressive
power of the language. The following are among the constraints included in the schema
(the syntax we devised for linearizing them is in square brackets):
1. Subtyping (depicted as thick solid and dashed arrows) representing ‘is-a’ re-
lationships among types. A partition, made of a combination of an exclu-
sive constraint (a circled ‘X’ saying that ‘Research&TeachingStaff, Ad-
min, Student are mutually disjoint’), and a total constraint (a circled dot for
‘Research&TeachingStaff, Admin, Student completely cover their common super-
type’). [O-SETTot ({Research&TeachingStaff, Admin, Student},UNI-Personnel)]
2. An internal frequency occurrence saying that if an instance of Research&TeachingStaff
plays the role of being lecturer in the relation isGivenBy, that instance can play the role
at most 4 times [FREQ(isGivenBy.Research&TeachingStaff,(1,4))]. A frequency occur-
rence may span over more than one role, and suitable frequency ranges can be specified. At
2
Page 5 of 110
most one cardinalities (depicted as continuos bars) are special cases of frequency occurrence
called internal uniqueness constraints [e.g. FREQ(hasWeight.Course,(1,1))].
3. An external frequency occurrence applied to the roles played by Student and Course,
meaning that ‘Students are allowed to enrol in the same course at most twice’.
[FREQ(isIn.Course,isBy.Student,(1,2))]
4. An external uniqueness constraint between the role played by Course in isIn and
the role played by Date in wasOn, saying that ‘For each combination of Course
and Date, at most one Enrollment isIn that Course and wasOn that Date’.
[FREQ(isIn.Course,wasOn.Date,(1,1))]
5. A mandatory participation constraints (graphically represented by a dot),
among several other, saying that ‘Each Course isGivenBy at least one in-
stance of the Research&TeachingStaff type’ (combinations of manda-
tory and uniqueness translate into exaclty one cardinality constraints).
[MAND(isGivenBy.Research&TeachingStaff,Research&TeachingStaff)]
6. A disjunctive mandatory participation, called inclusive-or constraint (depicted as
a circled dot), linking the two roles played by the instances of AreaMan-
ager meaning that ‘Each area manager either works in or heads (or both)’.
[MAND({worksIn.AreaManager,heads.AreaManager},AreaManager)]
7. An object cardinality constraint forcing the number of the Admin instances to be less or
equal to 100 (role cardinality constraints, applied to role instances, are also part of ORM2).
[O-CARD(Admin)=(0,100)]
8. An object type value constraint indicating which values are allowed in Credit (role value
constraints can be also expressed to indicate which values are allowed to play a given role).
[V-VAL(Credit)={4,6,8,12}]
9. An exclusion constraint (depicted as circled ‘X’) between the two roles played by the
instances of Student, expressing the fact that no student can play both these roles. Ex-
clusion constraint can also span over arbitrary sequences of roles. The combination of
exclusion and inclusive-or constraints gives rise to exclusive-or constraints meaning that
each instance in the attached entity type plays exactly one of the attached roles. Exclu-
sion constraints, together with subset and equality, are called set-comparison constraints.
[R-SETExc (worksFor.Student,collaborates.Student)]
10. A ring constraint expressing that the relation reportsTo is asymmetric.
[RINGAsym (reportTo.Admin,reportTo.AreaManager)]
A comprehensive list of all the ORM2 constraints, together with their graphical
representation, can be found in [1].
3 The ALCQI encoding of ORM2zero
With the main aim of relying on available tools to reason in an effective way on ORM2
schemas, an encoding in the description logic ALCQI for which tableaux-based rea-
soning algorithms with a tractable computational complexity have been developed [10].
ALCQI corresponds to the basic DL ALC equipped with qualified cardinality restric-
tions and inverse roles, and it is a fragment of the OWL2 web ontology language (a
complete introduction of the syntax and semantics of ALCQI can be found in [11]).
We also introduce in the ALCQI language the expression ‘C ⊃ D’ as an abbreviation
for the expression ‘¬C t D’.
Now, the discrepancy between ORM2 and ALCQI poses two main obstacles that
need to be faced in order to provide the encoding. The first one, caused by the absence of
n-ary relations in ALCQI, is overcome by means of reification: for each relation R of
3
Page 6 of 110
arity n ≥ 2, a new atomic concept AR and n functional roles τ (R.a1 ), . . . , τ (R.an ) are
introduced. The tree-model property of ALCQI guarantees the correctness encoding
w.r.t. the reasoning services over ORM2. Unfortunately, the second obstacle fixes,
once for all, the limits of the encoding: ALCQI does not admit neither arbitrary
set-comparison assertions on relations, nor external uniqueness or uniqueness involving
more than one role, or arbitrary frequency occurrence constraints. In other terms, it can
be proven that ALCQI is strictly contained in ORM2. The analysis of this inclusion
thus led to identification of the fragment called ORM2zero which is maximal with
respect to the expressiveness of ALCQI, and still expressive enough to capture the
most frequent usage patterns of the conceptual modelling community. Let ORM2zero =
{TYPE, FREQ− , MAND, R-SET− , O-SETIsa , O-SETTot , O-SETEx , OBJ} be the
fragment of ORM2 where: (i) FREQ− can only be applied to single roles, and (ii)
R-SET− applies either to entire relations of the same arity or to two single roles. The
encoding of the semantics of ORM2zero shown in table 1 is based on the S ALCQI
signature made of: (i) A set E1 , E2 , . . . , En of concepts for entity types; (ii) a set
V1 , V2 , . . . , Vm of concepts for value types; (iii) a set AR1 , AR2 , . . . , ARk of concepts
for objectified n-ary relations; (iv) a set D1 , D2 , . . . , Dl of concepts for domain
symbols; (v) 1, 2, . . . , nmax + 1 roles. Additional background axioms are needed here
in order to: (i) force the interpretation of the ALCQI knowledge base to be correct
w.r.t. the corresponding ORM2 schema, and (ii) guarantee that that any model of the
resulting ALCQI can be ‘un-reified’ into a model of original ORM2zero schema.
The correctness of the introduced encoding is guaranteed by the following theorem
(whose complete proof is available at [12]):
Theorem 1. Let Σ zero be an ORM2zero conceptual schema and Σ ALCQI the ALCQI
KB constructed as described above. Then an object type O is consistent in Σ zero if and
only if the corresponding concept O is satisfiable w.r.t. Σ ALCQI .
Let us conclude this section with some observation about the complexity of reason-
ing on ORM2 conceptual schemas, and taking into account that all the reasoning tasks
for a conceptual schema can be reduced to object type consistency. Undecidability of the
ORM2 object type consistency problem can be proven by showing that arbitrary com-
binations of subset constraints between n-ary relations and uniqueness constraints over
single roles are allowed [13]. As for ORM2zero , one can conclude that object type consis-
tency is E XP T IME-complete: the upper bound is established by reducing the ORM2zero
problem to concept satisfiability w.r.t. ALCQI KBs (which is known to be E XP T IME-
hard) [14], the lower bound by reducing concept satisfiability w.r.t. ALC KBs (which is
known to be E XP T IME-complete) to object consistency w.r.t. ORM2zero schemas [15].
Therefore, we obtain the following result:
Theorem 2. Reasoning over ORM2zero schemas is E XP T IME-complete.
4 Rational Closure in ALCQI
Now we briefly present the procedure to define the analogous of RC for the DL lan-
guage ALCQI. A more extensive presentation of such a procedure can be found in [4]:
it is defined for ALC, but it can be applied to ALCQI without any modifications. RC
is one of the main construction in the field of nonmonotonic logics, since it has a solid
4
Page 7 of 110
Table 1. ALCQI encoding.
Background domain axioms: Ei v ¬(D1 t · · · t Dl ) for i ∈ {1, . . . , n}
Vi v Dj for i ∈ {1, . . . , m}, and some j with 1 ≤ j ≤ l
Di v ulj=i+1 ¬Dj for i ∈ {1, . . . , l}
> v A>1 t · · · t A>nmax
> v (≤ 1i.>) for i ∈ {1, . . . , nmax }
∀i.⊥ v ∀i + 1.⊥ for i ∈ {1, . . . , nmax }
A>n ≡ ∃1.A>1 u · · · u ∃n.A>1 u ∀n + 1.⊥ for n ∈ {2, . . . , nmax }
AR v A>n for each atomic relation R of arity n
A v A>1 for each atomic concept A
TYPE(R.a, O) ∃τ (R.a)− .AR v O
FREQ− (R.a, hmin, maxi) ∃τ (R.a)− .AR v ≥ min τ (R.a)− .AR u ≤ max τ (R.a)− .AR
MAND({R1 .a1 , . . . , R1 .an , O v ∃τ (R1 .a1 )− .AR1 t · · · t ∃τ (R1 .an )− .AR1 t · · · t
. . . , Rk .a1 , . . . , Rk .am }, O) ∃τ (Rk .a1 )− .ARk t · · · t ∃τ (Rk .am )− .ARk
(A)
R-SET− Sub (A, B) AR v AS (A) A = {R.a , . . . , R.a }, B = {S.b , . . . , S.b }
1 n 1 n
(A)
R-SET− Exc (A, B) AR v A>n u ¬AS
(B)
R-SET− Sub (A, B) ∃τ (R.ai )− .AR v ∃τ (S.bj )− .AS (B) A = {R.a }, B = {S.b }
i j
(B)
R-SET− Exc (A, B) ∃τ (R.ai )− .AR v A>n u ¬∃τ (S.bj ).AS
O-SETIsa ({O1 , . . . , On }, O) O1 t · · · t On v O
O-SETTot ({O1 , . . . , On }, O) O v O1 t · · · t On
O-SETEx ({O1 , . . . , On }, O) O1 t · · · t On v O and Oi v un j=i+1 ¬Oj for each i = 1, . . . , n
OBJ(R, O) O ≡ AR
logical characterization, it generally maintains the same complexity level of the under-
lying monotonic logic, and it does not give back counter-intuitive conclusions; its main
drawback is in its inferential weakness, since there could be desirable conclusions that
we won’t be able to draw (see example 2 below).
As seen above, each ORM2zero schema can be translated into an ALCQI TBox. A
TBox T for ALCQI consists of a finite set of general inclusion axioms (GCIs) of form
C v D, with C and D concepts. Now we introduce also a new form of information,
the defeaible inclusion axioms C < ∼ D, that are read as ‘Typically, an individual falling
under the concept C falls also under the concept D’. We indicate with B the finite set of
such inclusion axioms.
Example 1. Consider a modification of the classical ‘penguin example’, with the concepts
P, B, F, I, F i, W respectively read as ‘penguin’, ‘bird’, ‘flying’, ‘insect’, ‘fish’, and ‘have wings’,
and a role P rey, where a role instantiation (a, b):P rey read as ‘a preys for b’. We can define a
defeasible KB K = hT , Bi with T = {P v B, I v ¬F i} and B = {P ∼ < ¬F , B ∼ < F,
P∼ < ∀P rey.F i, B ∼< ∀P rey.I, B ∼ < W }.
In order to define the rational closure of a knowledge base hT , Bi, we must first of
all transform the knowledge base hT , Bi into a new knowledge base hΦ, ∆i, s.t. while
T and B are sets of inclusion axioms, Φ and ∆ are simply sets of concepts. Then, we
shall use the sets hΦ, ∆i to define a nonmonotonic consequence relation that models the
rational closure. Here we just present the procedure, referring to [4] for a more in-depth
explanation of the various steps.
Transformation of hT , Bi into hΦ, ∆i. Starting with hT , Bi, we apply the following
steps.
5
Page 8 of 110
Step 1. Define the set representing the strict form of the set B, i.e. the set Bv = {C v D |
C ∼ < D ∈ B}, and define a set AB as the set of the antecedents of the conditionals in B,
i.e. AB = {C | C ∼ < D ∈ B}.
Step 2. We determine an exceptionality ranking of the sequents in B using the set of the an-
tecedents AB and the set Bv .
Step 2.1. A concept is considered exceptional in a knowledge base hT , Bi only if it is classi-
cally negated (i.e. we are forced to consider it empty), that is, C is exceptional in hT , Bi
only if
T ∪ Bv |= > v ¬C
where |= is the classical consequence relation associated to ALCQI. If a concept is
considered exceptional in hT , Bi, also all the defeasible inclusion axioms in B that have
such a concept as antecedent are considered exceptional. So, given a knowledge base
hT , Bi we can check which of the concepts in AB are exceptional (we indicate the set
containing them as E(AB )), and consequently which of the axioms in B are exceptional
(the set E(B) = {C ∼ < D | C ∈ E(AB )}).
So, given a knowledge base hT , Bi we can construct iteratively a sequence E0 , E1 , . . . of
subsets of B in the following way:
– E0 = B
– Ei+1 = E(Ei )
Since B is a finite set, the construction will terminate with an empty set (En = ∅ for
some n) or a fixed point of E.
Step 2.2 Using such a sequence, we can define a ranking function r that associates to every
axiom in B a number, representing
its level of exceptionality:
i if C ∼< D ∈ Ei and C ∼ 1 , A>2
f1, f2, f3
Background axioms: > v A>1 t A>2
> v (≤ 1f1.>), > v (≤ 1f2.>)
∀f1.⊥ v ∀f2.⊥, ∀f2.⊥ v ∀f3.⊥
A>2 ≡ ∃f1.A>1 u ∃f2.A>1 u ∀f3.⊥
WorksFor v A>2 , Manages v A>2
Employee v A>1 , Manager v A>1 ,
AreaManager v A>1 , TopManager v A>1
Typing Constraints: WorksFor v ∃f1− .Employee, WorksFor v ∃f2− .Project
Manages v ∃f1− .TopManager, Manages v ∃f2− .Project
Frequency Constraints: ∃f1− .Manages v = 1 f1− .Manages
Mandatory Constraints: Employee v ∃f1− .WorksFor
TopManager v ∃f1− .Manages
Project v ∃f2− .WorksFor
Project v ∃f2− .Manages
Exclusion Constraints: ∃f1− .WorksFor v A>2 u ¬∃f1.Manages
Subtyping Constraints: Manager v Employee u (AreaManager t TopeManager)
AreaManager v ¬TopeManager
a change we obtain a knowledge base as the one above, but with the defeasible inclusion
axiom Employee ∼< ∃f1− .WorksFor instead of the axiom Employee v ∃f1− .WorksFor.
Introducing such constraints, we introduce the forms of defeasible subsumptions
appropriate for modeling nonmonotonic reasoning. In particular:
– A subclass relation, as the ones in example 3, is translated into an inclusion axiom
C v D, and correspondingly we translate the defeasible connection C ; D into a
defeasible inclusion axiom C < ∼ D.
– Analogously, consider the strict form of the example 4. The mandatory participation
of the class B to the role AN is translated into the axiom B v ∃f1− .AN . If we use
the defeasible mandatory participation constraint, we simply translate the structure
using the defeasible inclusion <
∼, obtaining the axiom B < ∼ ∃f1− .AN .
9
Page 12 of 110
Hence, from a ORM graph with defeasible constraints we obtain an ALCQI knowl-
edge base K = hT , Bi, where T is a standard ALCQI Tbox containing concept inclu-
sion axioms C v D, while the set B contains defeasible axioms of the form C < ∼ D.
Once we have our knowledge base K, we apply to it the procedure presented in the
previous section, in order to obtain the rational closure of the knowledge base.
Consistency. In ORM2, and in conceptual modeling languages in general, the notion
of consistency is slightly different from the classical form of logical consistency. That
is, generally from a logical point of view a knowledge base K is considered inconsistent
only if we can classically derive a contradiction from it; in DLs that corresponds to
saying that K |= > v ⊥, i.e. every concept in the knowledge base results empty. Instead,
dealing with conceptual modeling schemas we generally desire that our model satisfies a
stronger form of consistency constraint, that is, we want that none of the classes present
in the schema are forced to be empty.
Definition 2 (Strong consistency). A TBox T is strongly consistent if none of the
atomic concepts present in its axioms are forced to be empty, that is, if T 6|= > v ¬A
for every atomic concept A appearing in the inclusion axioms in T .
As seen above, the introduction of defeasible constraints into ORM2zero allows to
build schemas that in the standard notation would be considered inconsistent, but that,
once introducing the defeasible constraints, allow for an instantiation such that all the
classes result non-empty. Hence it is necessary to redefine the notion of consistency
check in order to deal with such situations.
Such a consistency check is not problematic, since we can rely on the ranking pro-
cedure presented above. Consider a TBox T obtained by an ORM2zero schema, and
indicate with C the set of all the atomic concepts used in T . It is sufficient to check the
exceptionality ranking of all the concepts in C with respect to T : if a concept C has
an exceptionality ranking r(C) = n, with 0 < n < ∞, then it represents an atypical
situation, an exception, but that is compatible with the information conveyed by the de-
feasible inclusion axioms. For example, in the above examples the penguins and the top
managers would be empty classes in the classical formalization, but using the defeasi-
ble approach they result exceptional classes in our schemas, and we can consider them
as non-empty classes while still considering the schema as consistent. The only case
in which a class has to be considered necessarily empty, is when it has ∞ as ranking
value: that means that, despite eliminating all the defeasible connections we can, such
a concept still results empty. Then, the notion of strong consistency for ORM2zero with
defeasible constraints is the following:
Definition 3 (Strong consistency with defeasible constraints). A knowledge base K =
hT , Bi is strongly consistent if none of the atomic concepts present in its axioms are
forced to be empty, that is, if r(A) 6= ∞ for every atomic concept A appearing in the
inclusion axioms in K.
Given a defeasible ORM2zero schema Σ, eliminate from it all the defeasible con-
straints (call Σstrict the resulting schema). From the procedures defined above, it is
immediate to see that if Σstrict is a strongly inconsistent ORM2zero schema, in the ‘clas-
sical’ sense, then Σ is a strongly inconsistent defeasible schema: simply, if the negation
of a concept is forced by the strict part of a schema, it will be necessarily forced at each
ranking level, resulting in a ranking value of ∞.
10
Page 13 of 110
On the other hand, there can be also strongly inconsistent defeasible schemas in
which inconsistency depends not only on the strict part of the schema, but also on the
defeasible part. For example, the schema in figure 4 is inconsistent, since the class A
results to have a ranking value of ∞ (the schema declares that the class A is directly
connected to two incompatible concepts). Now, we can check the results of the defined
procedure in the examples presented.
Example 5. Consider example 3. From the translation of the defeasible form of the schema we
conclude that the axiom Penguin v NonFlyingObject has rank 1, while Bird v WingyObject
and Bird v FlyingObject have rank 0, that means that we end up with two default concepts:
d
– δ0 := {Penguin ⊃ NonFlyingObject, Bird ⊃ WingyObject, Bird ⊃ FlyingObject};
– δ1 := Penguin ⊃ NonFlyingObject
We can derive the same kind of conclusions as in example 2, and again we can see the limits of
the rational closure, since we cannot derive the desirable conclusion that Penguin|∼WingyObject.
Example 6. Consider the knowledge base obtained in the example 4. We have only a defeasible
inclusion axiom Employee ∼ < ∃f1− .WorksFor, and, since Employee does not turn out to be an
exceptional concept, we end up with a single default concept in B:
– δ0 := {Employee ⊃ ∃f1− .WorksFor};
Since TopManager is not consistent with all the strict information contained in the schema
plus δ0 , we cannot associate δ0 to TopManager and, despite we have the information that for
non-exceptional cases an employee works for a project, we are not forced to conclude that for the
exceptional class of the top managers.
6 Conclusions and further work
In this paper we have presented a way to implement a form of defeasible reasoning into
the ORM2 formalism. Exploiting the possibility of encoding ORM2zero , that represents a
big portion of the ORM2 language, into the description logic ALCQI on one hand, and
a procedure appropriate for modeling one of the main forms of nonmonotonic reasoning,
i.e. rational closure, into DLs on the other hand, we have defined two new constraints,
a defeasible subclass relation and a defeasible mandatory participation, that are appro-
priate for modeling defeasible information into ORM2, and that, once translated into
ALCQI, allow for the use of the procedures characterizing rational closure to reason
about the information contained into an ORM2zero schema.
The present proposal deals only with reasoning on the information contained in the
TBox obtained from an ORM2 schema, but, once we have done the rational closure of
Fig. 4. Inconsistent schema.
11
Page 14 of 110
the TBox, we can think also of introducing an ABox, that is, the information about a
particular domain of individuals. A first proposal in such direction is in [4]. Actually we
still lack a complete semantic characterization of rational closure in DLs, but hopefully
we shall obtain soon such a result (a first step in such a direction is in [3]). Another future
step will be the implementation of nonmonotonic forms of reasoning that extend rational
closure, overcoming its inferential limits (see example 2), such as the lexicographic
closure [16] or the defeasible inheritance based approach [5].
References
1. Halpin, T., Morgan, T.: Information Modeling and Relational Databases: From Conceptual
Analysis to Logical Design. 2nd edn. Morgan Kaufmann (2001)
2. Bonatti, P.A., Faella, M., Sauro, L.: Defeasible inclusions in low-complexity dls. J. Artif.
Intell. Res. (JAIR) 42 (2011) 719–764
3. Britz, K., Meyer, T., Varzinczak, I.: Semantic foundation for preferential description logics.
In Wang, D., Reynolds, M., eds.: Proceedings of the 24th Australasian Joint Conference on
Artificial Intelligence. Number 7106 in LNAI, Springer (2011) 491–500
4. Casini, G., Straccia, U.: Rational closure for defeasible description logics. In Janhunen,
T., Niemelä, I., eds.: JELIA. Volume 6341 of Lecture Notes in Computer Science., Springer
(2010) 77–90
5. Casini, G., Straccia, U.: Defeasible inheritance-based description logics. In: IJCAI-11. (2011)
813–818
6. Giordano, L., Olivetti, N., Gliozzi, V., Pozzato, G.L.: Alc + t: a preferential extension of
description logics. Fundam. Inform. 96(3) (2009) 341–372
7. Grimm, S., Hitzler, P.: A preferential tableaux calculus for circumscriptive ALCO. In: RR-
09. Number 5837 in LNCS, Berlin, Heidelberg, Springer-Verlag (2009) 40–54
8. Straccia, U.: Default inheritance reasoning in hybrid kl-one-style logics. IJCAI-93 (1993)
676–681
9. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artif. Intell.
55(1) (1992) 1–60
10. Franconi, E., Mosca, A., Solomakhin, D.: ORM2: formalisation and encoding in OWL2. In:
OTM 2012 Workshops. Volume 7567 of LNCS., Springer (2012) 368–378
11. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F., eds.: The
description logic handbook: theory, implementation, and applications. Cambridge University
Press, New York, NY, USA (2003)
12. Franconi, E., Mosca, A.: The formalisation of ORM2 and its encoding in OWL2. Techni-
cal Report KRDB12-2, KRDB Research Centre, Free University of Bozen-Bolzano (2012)
Available at http://www.inf.unibz.it/krdb/pub/TR/KRDB12-2.pdf.
13. Calvanese, D., De Giacomo, G., Lenzerini, M.: Identification constraints and functional de-
pendencies in description logics. In: Proceedings of the 17th international joint conference
on Artificial intelligence (IJCAI). (2001) 155–160
14. Berardi, D., Cali, A., Calvanese, D., Giacomo, G.D.: Reasoning on UML class diagrams. Art.
Intell. 168 (2003)
15. Artale, A., Calvanese, D., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: Reasoning over
extended ER models. In: Proc. of ER 2007, 26th International Conference on Conceptual
Modeling, Springer (2007) 277–292
16. Lehmann, D.J.: Another perspective on default reasoning. Ann. Math. Artif. Intell. 15(1)
(1995) 61–82
12
Page 15 of 110
OntoMerge: A System for Merging DL-Lite
Ontologies
Zhe Wang1 , Kewen Wang2 , Yifan Jin2 , and Guilin Qi3,4
1
University of Oxford, United Kingdom
2
Griffith University, Australia
3
Southeast University, China
4
State Key Laboratory for Novel Software Technology
Nanjing University, Nanjing, China
Abstract. Merging multi-sourced ontologies in a consistent manner is
an important and challenging research topic. In this paper, we propose
a novel approach for merging DL-LiteN bool ontologies by adapting the
classical model-based belief merging approach, where the minimality of
changes is realised via a semantic notion, model distance. Instead of using
classical DL models, which may be infinite structures in general, we
define our merging operator based on a new semantic characterisation
for DL-Lite. We show that subclass relation w.r.t. the result of merging
can be checked efficiently via a QBF reduction. We present our system
OntoMerge, which effectively answers subclass queries on the resulting
ontology of merging, without first computing the merging results. Our
system can be used for answering subclass queries on multiple ontologies.
1 Introduction
Ontologies are widely used for sharing and reasoning over domain knowledge,
and their underlying formalisms are often description logics (DLs). To effec-
tively answer queries, ontologies from heterogeneous sources and contributed
by various authors are often needed. However, ontologies developed by multiple
authors under different settings may contain overlapping, conflicting and inco-
herent domain knowledge. The ultimate goal of ontology merging is to obtain
a single consistent ontology that preserves as much knowledge as possible from
two or more heterogeneous ontologies. This is in contrast to ontology matching
[5], whose goal is to align entities (with different name) between ontologies, and
which is often a pre-stage of ontology merging.
Existing merging systems often adopt formula-based approaches to deal with
logical inconsistencies [10; 9; 14]. Most of such approaches can be described as
follows: the system first combine the ontologies by taking their union; then, if any
inconsistency is detected (through a standard reasoning), it pinpoints the axioms
which (may) cause inconsistency; and finally, remove certain axioms to retain
consistency. However, such an approach is sometimes unsatisfactory because it
is not fine-grained either in the way it measures the minimality of changes, and
thus it is often unclear how close the result of merging is to the source ontologies
Page 16 of 110
semantically; or in the way it resolve inconsistency. In [12], an attempt is made
to provide some semantic justification for the minimality of changes, however,
the result of merging is still syntax-dependant and is often a set of ontologies.
On the other hand, model-based merging operators have been intensively
studied in propositional logic, which are syntax-independent and usually satisfy
more rationality postulates than formula-based ones. However, a major chal-
lenge in adapting model-based merging techniques to DLs is that DL models
are generally infinite structures and the number of models of a DL ontology is
infinite. Several notions of model distance are defined on classical DL models
for ontology revision [13]. Mathematically, it is possible to define a distance o
classical DL models. Such a distance is computationally limited as it is unclear
how to develop an algorithm for the resulting merging operator. A desirable so-
lution is to define ontology merging operators based on a suitable finite semantic
characterisation instead of classical DL models.
In this paper, we focus on merging ontologies expressed as DL-Lite TBoxes,
which can be also accompanied with the ontology-based data access (OBDA)
framework for data integration [2]. We propose a novel approach for merging
ontologies by adapting a classical model-based belief merging approach, where
the minimality of changes is realised via a semantic notion, model distance.
Instead of using classical DL models, which may be infinite structures in general,
we define our merging operator based on the notion of types. We show that
subclass relation w.r.t. the result of merging can be checked efficiently via a
QBF reduction, which allows us to make use of the off-the-shelf QBF solvers [8].
We present our system OntoMerge, which effectively answers subclass queries
on merging results, without first computing the merging results. Our system can
be used to answer subclass queries on multiple ontologies.
2 A New Semantic Characterisation
In our approach, it is sufficient to consider a finite yet large enough signature.
A signature S is a union of four disjoint finite sets SC , SR , SI and SN , where
SC is the set of atomic concepts, SR is the set of atomic roles, SI is the set of
individual names and SN is the set of natural numbers in S. We assume 1 is
always in SN .
Formally, given a signature S, a DL-LiteN
bool language has the following syntax
[1]:
R ← P | P− S ← P | ¬P
B←>|A| >nR C ← B | ¬C | C1 u C2
where n ∈ SN , A ∈ SC and P ∈ SR . B is called a basic concept and C is called
a general concept. BS denotes the set of basic concepts on S. We write ⊥ for
¬>, ∃R for ≥ 1 R, and C1 t C2 for ¬(¬C1 u ¬C2 ). Let R+ = P , where P ∈ SR ,
whenever R = P or R = P − . A TBox T is a finite set of concept axioms of the
form C1 v C2 , where C1 and C2 are general concepts. An ABox A is a finite set
of membership assertions of the form C(a) or S(a, b), where a, b are individual
names. In this paper, an ontology is represented as a DL TBox.
Page 17 of 110
The classical DL semantics are given by models. A TBox T is consistent
with an ABox A if T ∪ A has at least one model. A concept or role is satisfiable
in T if it has a non-empty interpretation in some model of T . A TBox T is
coherent if all atomic concepts and atomic roles in T are satisfiable. Note that
a coherent TBox must be consistent. TBox T entails an axiom C v D, written
T |= C v D, if all models of T satisfy C v D. Two TBoxes T1 , T2 are equivalent,
written T1 ≡ T2 , if they have the same models.
Now, we introduce a semantic characterisation for DL-Lite TBoxes in terms
of types. A type τ ⊆ BS is a set of basic concepts over S, such that > ∈ τ , and
> n R ∈ τ implies > m R ∈ τ for each pair m, n ∈ SN with m < n and each
(inverse) role R ∈ SR ∪ { P − | P ∈ SR }. Type τ satisfies basic concept B if
B ∈ τ , ¬C if τ does not satisfy C, and C1 u C2 if τ satisfies both C1 and C2 .
Given a TBox T , type τ satisfies T if τ satisfies concept ¬C1 t C2 for each axiom
C1 v C2 in T .
For a TBox T , define TM(T ) to be the maximal set of types satisfying
the following conditions: (1) all the types in TM(T ) satisfy T ; (2) for each
type τ ∈ TM(T ) and each ∃R in τ , there exists a type τ 0 ∈ TM(T ) (possibly
τ 0 = τ ) containing ∃R− . A type τ is called a type model (T-model) of T if
τ ∈ TM(T ). Note that TM(T ) is uniquely defined for each TBox T . Note that
for a coherent TBox T , TM(T ) is exactly the set of all types satisfying T . Let
TM(Π) = TM(T1 ) × · · · × TM(Tn ) for Π = hT1 , . . . , Tn i.
Proposition 1. Given a TBox T , we have the following results:
– T is consistent iff TM(T ) 6= ∅.
– For a general concept C, C is satisfiable wrt T iff there exists a T-model in
TM(T ) satisfying C.
– For two general concepts C, D, T |= C v D iff either TM(T ) = ∅ or all
T-models in TM(T ) satisfy C v D.
– T ≡ T 0 iff TM(T ) = TM(T 0 ), for any TBox T 0 .
Given a type τ , an individual a and an ABox A, we say τ is a type of a
w.r.t. A if there is a model I of A such that τ = {B | aI ∈ B I , B ∈ BS }. For
example, given A = {A(a), ¬B(b), C(c)}, type τ = {A, B} is a type of a, but
not a type of either b or c in A. For convenience, we will say a type of a when
the ABox A is clear from the context. Let TMa (A) be the set of all the types
of a in A if a occurs in A; and otherwise, TMa (A) be the set of all the types.
A set M of T-models satisfies an ABox A if there is a type of a in M , i.e.,
M ∩ TMa (A) 6= ∅, for each individual a in A.
Proposition 2. Given a TBox T and an ABox A, T ∪ A is consistent iff
TM(T ) ∩ TMa (A) 6= ∅ for each a in A.
3 Merging Operator
In this section, we introduce an approach to merging DL-Lite ontologies to obtain
a coherent unified ontology.
Page 18 of 110
An ontology profile is of the form Π = hT1 , . . . , Tn i, where Ti is the ontology
from the source n.o. i (1 ≤ i ≤ n). There are two standard definitions of integrity
constraints (ICs) in the classical belief change literature [3], the consistency-
and entailment-based definitions. We also allow two types of ICs for merging,
namely the consistency constraint (CC), expressed as a set Ac of data, and the
entailment constraint (EC), expressed as a TBox Te . We assume the IC is self-
consistent, that is, Te ∪ Ac is always consistent. For an ontology profile Π, a
CC Ac and a EC Te , an ontology merging operator is a mapping (Π, Te , Ac ) 7→
∇(Π, Te , Ac ), where ∇(Π, Te , Ac ) is a TBox, s.t. ∇(Π, Te , Ac )∪Ac is consistent,
and ∇(Π, Te , Ac ) |= Te .
In classical model-based merging approaches, merging operators are often
defined by certain notions of model distances [11; 6]. We use S4S 0 to denote the
symmetric difference between two sets S and S 0 , i.e., S4S 0 = (S \ S 0 ) ∪ (S 0 \ S).
Given a set S and a tuple S = hS1 , . . . , Sn i of sets, the distance between S and
S is defined to be a tuple d(S, S) = hS4S1 , . . . , S4Sn i. For two n-element dis-
tances d and d0 , d d0 if di ⊆ d0i for each 1 ≤ i ≤ n, where di is the i-th element
in d. Given two sets S and S 0 , define σ(S, S 0 ) = S if S 0 is empty, and otherwise,
σ(S, S 0 ) = { e0 ∈ S | ∃e00 ∈ S 0 s.t. ∀e ∈ S, ∀e0 ∈ S 0 , d(e, e0 ) 6≺ d(e0 , e00 ) }. In [6],
given a collection Ψ = {ϕ1 , . . . , ϕn } of propositional formulas, and some ECs
expressed as a propositional theory µ, the result of merging ϕ1 , . . . , ϕn w.r.t. µ
is the theory whose models are exactly σ(mod(µ), mod(Ψ )), i.e., those models
satisfying µ and having minimal distance to Ψ .
Inspired by classical model-based merging, we introduce a merging opera-
tor in terms of T-models. For an ontology profile Π and an EC Te , we could
define the T-models of the merging to be a subset of TM(Te ) (so that Te is
entailed) consisting of those T-models which have minimal distance to Π, i.e.,
σ(TM(Te ), TM(Π)). However, this straightforward adoption does not take the
CC into consideration, and the merging result obtained in this way may not
be coherent. For example, let T1 = {A v ¬B}, T2 = {> v B}, Te = ∅, and
Ac = {A(a), B(a)}. Then, σ(TM(Te ), TM(hT1 , T2 i)) consists of only one type
{B}. Clearly, the corresponding TBox {A v ⊥, > v B} does not satisfy the CC,
and it is not coherent.
Note that in the above example, once the merging result satisfies the CC, then
it is also coherent, because both concepts A and B are satisfiable. In general,
it is also the case that coherency can be achieved by applying certain CC to
merging. We introduce an auxiliary ABox A† in addition to the initial CC Ac ,
in which each concept and each role is explicitly asserted with a member. That
is, A† = {A(a) | A ∈ SC , a ∈ SI is a fresh individual for A} ∪ {P (b, c) | P ∈
SR , b, c ∈ SI are fresh individuals for P }. As assumed, SI is large enough for
us to take these auxiliary individuals. From the definition of CCs, the merged
TBox T must be consistent with all the assertions in A† , which assures all the
concepts and roles in T to be satisfiable. Based on this observation, we have the
following lemma.
Lemma 1. T is coherent iff T ∪ A† is consistent for any TBox T .
To ensure the coherence of merging, we only need to include A† into the CC.
Page 19 of 110
For the merging to be consistent with the CC Ac , from Proposition 2, the
T-model set M of the merging needs to satisfy Ac . That is, M needs to contain a
type of a for each individual a in Ac . However, σ(TM(Te ), TM(Π)) does not nec-
essarily satisfy this condition, as can be seen from the above example: TMa (Ac )
consists of a single type {A, B} and σ(TM(Te ), TM(Π)) ∩ TMa (Ac ) = ∅. Intu-
itively, for the merging to satisfy the CC, type {A, B} need to be added to the
T-models of merging. In general, the T-models of merging can be obtained by
extending (if necessary) the set σ(TM(Te ), TM(Π)) with at least one type of a
w.r.t. Ac for each individual a in Ac , and if there are multiple such types, choose
those with minimal distances.
Based on the above intuitions, the definition of TBox merging is presented
as follows.
Definition 1. Let Π be an ontology profile, Te be a TBox, and Ac be an ABox.
Denote A∗ = Ac ∪ A† . The result of merging Π w.r.t. the EC Te and the CC
Ac , denoted ∇(Π, Te , Ac ), is defined as follows
TM(∇(Π, Te , Ac )) = σ(TM(Te ), TM(Π))∪
[
σ(TM(Te ) ∩ TMa (A∗ ), TM(Π)).
a occurs in A∗
From the definition, the T-models of the merging are constituted with two parts.
The first part consists of those T-models of Te (for the satisfaction of the EC)
with minimal distances to Π. The second part consists of types of a, for each
individual a in A∗ , which are added to the first part for the satisfaction of the CC.
These types are also required to be T-models of Te and have minimal distances
to Π. It is clear from Proposition 1 that the result of merging is unique up to
TBox equivalence.
4 QBF Reduction
In this section, we consider a standard reasoning problem for ontology merg-
ing, namely the subclass queries: whether or not the result of merging entails a
subclass relation C v D. We present a QBF reduction for this problem, which
allows us to make use of the off-the-shelf QBF solvers [8]. We assume that every
TBox in the ontology profile is coherent, and in this case, the T-models of a
TBox T are exactly those satisfying T .
We achieve the reduction in three steps. Firstly, we introduce a novel proposi-
tional transformation for DL-Lite TBoxes. The transformation is inspired by [1],
which contains a transformation from a DL-Lite TBox into a theory in the one
variable fragment of first order logic. Considering T-models instead of classical
DL models allows us to obtain a simpler transformation to propositional logic
than theirs to first order logic.
Page 20 of 110
Function φ(·) maps a basic concept to a propositional variable, and a general
concept (resp., a TBox axiom) to a propositional formula.
φ(⊥) = ⊥, φ(A) = pA , φ(> n R) = pnR ,
φ(¬C) = ¬φ(C), φ(C1 u C2 ) = φ(C1 ) ∧ φ(C2 ),
φ(C1 v C2 ) = φ(C1 ) → φ(C2 ).
Here, pA and pnR are propositional variables. We use VS to denote the set
of propositional variables corresponding to the basic concepts over S, and we
omit the subscript S in what follows for simplicity. We can see that φ(·) is a
bijective mapping between the set of DL-LiteN bool general concepts and the set of
propositional formulas only referring to symbols in VS and boolean operators ¬,
∧ and →.
Naturally, given the mapping φ(·), an arbitrary propositional model may not
correspond to a type. We define a formula η whose models are exactly the set of
types. Let ^ ^
η= pnR → pmR .
R+ ∈SR m,n∈SN with m and ⊥ as abbreviations for, respectively, A ∨ ¬A and A ∧ ¬A for some A.
The symbols |= and |∼ will indicate, respectively, the classical consequence relation and
a defeasible consequence relation. An element of a consequence relation, Γ |= C or
Γ |∼C, will be called a sequent, and in the case of |∼ it has to be read as ‘If Γ , then
typically C’.
We call conditional knowledge base a pair hT , Bi, where T is a set of strict sequents
C |= D, representing certain knowledge, and B is a set of defeasible sequents C|∼D,
representing default information.
Page 28 of 110
Example 1. The typical ‘penguin’ example can be encoded as 3 : K = hT , Bi with T =
{P |= B} and B = {P |∼¬F, B|∼F }. 2
In what follows we are going to present a slight generalization of Lehmann’s procedure
[18], that is, a non-monotonic reasoning procedure that relies on a decision procedure
for |= only. We then suggest how to transpose such an approach into the framework of
DLs.
In the present section we shall proceed in the following way: first, we define the
notion of rational consequence relation (see e.g. [17]) and we present the notions of ra-
tional and lexicographic closure; then, we describe a procedure to build a lexicographic
closure of a conditional knowledge base.
Rational Consequence Relations. The preferential approach is mainly based the iden-
tification of the structural properties that a well-behaved (both from the intuitive and the
logical point of view) non-monototonic consequence relation should satisfy. Between
the possible interesting options, a particular relevance has been given to the group of
properties characterizing the class of rational consequence relations (see [17]). A con-
sequence relation |∼ is rational iff it satisfies the following properties:
(REF) C|∼C Reflexivity
C|∼D D |= F
C|∼D C ∧ D|∼F (RW) Right Weakening
(CT) Cut (Cumulative Trans.) C|∼F
C|∼F
C|∼F D|∼F
C|∼D C|∼F (OR) Left Disjunction
(CM) Cautious Monotony C ∨ D|∼F
C ∧ D|∼F
C|∼F C 6 |∼¬D
C|∼F |= C ↔ D (RM) Rational Monotony
(LLE) Left Logical Equival. C ∧ D|∼F
D|∼F
We refer the reader to [19] for an insight of the meaning of such rules. (RM) is
generally considered as the strongest form of monotonicity we can use in the character-
ization of a reasoning system in order to formalise a well-behaved form of defeasible
reasoning. The kind of reasoning we want to implement applies at the level of sequents:
let B = {C1 |∼E1 , . . . , Cn |∼En } be a conditional knowledge base; we want the agent
to be able to reason about the defeasible information at its disposal, that is, to be able to
derive new sequents from his conditional base.
Semantically, rational consequence relations can be characterized by means of a par-
ticular kind of possible-worlds model, that is, ranked preferential models, but we shall
not deepen the connection with such a semantical characterization here (see [17]). Ex-
cept for (RM), all the above properties are closure properties, that is, they are preserved
under intersection of the consequence relations, allowing for the definition of a notion
of entailment (see [16]), called preferential closure; on the other hand, (RM) is not pre-
served under intersection, and not every rational consequence relation describes a de-
sirable and intuitive form of reasoning. Two main constructions have been proposed to
define interesting and well-behaved rational consequence relations: the rational closure
in [17], and the lexicographic closure in [18].
Lehmann and Magidor’s rational closure operation behaves in an intuitive way and
it is logically strongly characterized (we refer the reader to [17, 9] for a description of
3
Read B as ‘Bird’, P as ‘Penguin’ and F as ‘Flying’.
Page 29 of 110
rational closure). Notwithstanding, rational closure is considered a too weak form of
reasoning, since often we cannot derive intuitive conclusions from our premises. The
main problem of the rational closure is that if an individual falls under an atypical sub-
class (for example, penguins are an atypical subclass of birds, since they do not fly), we
cannot associate to it any of the typical properties characterizing the superclass.
Example 2. Consider the KB in example 1, and add to the set B the sequent B|∼T
(read T as ‘Has feathers’). Even if it would be desirable to conclude that penguins have
feathers (P |∼T ), in the rational closure it is not possible, since penguins, being atypical
birds, are not allowed to inherit any of the typical properties of birds.
Rational closure fails to respect the presumption of independence ([18], pp.63-64):
even if a class does not satisfy a typical property of a superclass, we should presume
that it behaves in a typical way w.r.t. the other properties, if not forced to conclude
the contrary. In an attempt to overcome such a shortcoming, Lehmann has proposed in
[18] a possible extension of rational closure, in order to preserve the desirable logical
properties of rational closure, but augmenting in an intuitive way its inferential power.
Lexicographic Closure. In this paragraph we are going to present the procedure to
define the lexicographic closure of a conditional knowledge base. Our procedure just
slightly generalizes the one in [18], considering also knowledge bases K = hT , Bi with
a strict part T .
The essence of the procedure to build the lexicographic closure of K consists in
transforming hT , Bi into a KB hΦ, ∆i, where Φ and ∆ are sets containing formulae
instead of sequents; that is, Φ contains what we are informed to be necessarily true,
while ∆ contains the formulae we consider to be typically, but not necessarily true.
Once we have defined the pair hΦ, ∆i, we can easily define from it the lexicographic
closure of K.
So, consider hT , Bi, with B = {C1 |∼E1 , . . . , Cn |∼En }. The steps for the construc-
tion of hΦ, ∆i (obtained by combining the construction in [18] with some results from
[3]) are the following:
Step 1. We transfer the information in T into correspondent |∼-sequents and add it to
B, that is, we move from a characterization hT , Bi to h∅, B 0 i, where B 0 = B ∪
{(C ∧ ¬D)|∼⊥ | C |= D ∈ T }. Intuitively, C |= D is equivalent to saying that its
negation is an absurdity, i.e. (C ∧ ¬D)|∼⊥ (see [3], Section 6.5).
Step 2. We define ∆B0 as the set of the materializations of the sequents in B 0 , i.e. the
material implications corresponding to such sequents: ∆B0 = {C → D | C|∼D ∈
B 0 }. Also, we indicate by AB0 the set of the antecedents of the sequents in B 0 :
AB0 = {C | C|∼D ∈ B 0 }.
Step 3. Now we define an exceptionality ranking of sequents w.r.t. B 0 .
Exceptionality: Lehmann and Magidor call a formula C exceptional for a set of
sequents D iff it is false in all the most typical situations satisfying D (see [17],
Section 2.6); in particular, C is exceptional w.r.t. D if we can derive >|∼¬C from
the preferential closure of D. C|∼D is said to be exceptional for D iff its antecedent
C is exceptional for D. Exceptionality of sequents can be decided based on |= only
(see [17], Corollary 5.22), as C is exceptional for a set of sequents D iff ∆D |= ¬C.
Given a set of sequents D, indicate by E(AD ) the set of the antecedents that result
exceptional w.r.t. D, that is E(AD ) = {C ∈ AD | ∆D |= ¬C}, and with E(D) the
Page 30 of 110
exceptional sequents in D, i.e. E(D) = {C|∼D ∈ D | C ∈ E(AD )}. Obviously,
for every D, E(D) ⊆ D.
Step 3.1. We can construct iteratively a sequence E0 , E1 . . . of subsets of the con-
ditional base B 0 in the following way: E0 = B 0 , Ei+1 = E(Ei ). Since B 0 is a
finite set, the construction will terminate with an empty (En = ∅) or a finite
(En + 1 = En 6= ∅) fixed point of E.
Step 3.2. Using such a sequence, we can define a ranking function r that associates
to every sequent in B 0 a number, representing its level of exceptionality:
i if C|∼D ∈ Ei and C|∼D ∈ / Ei+1
r(C|∼D) =
∞ if C|∼D ∈ Ei for every i .
Step 4. In Step 3, we defined the materialization of B 0 and the rank of every sequent in
it. Now,
Step 4.1. we can determine if B 0 is inconsistent. A conditional base is inconsistent
if in its preferential closure we obtain the sequent >|∼⊥ (from this sequent we
can derive any other sequent using (RW) and (CM)). Given the result in Step
3.1, we can check the consistency of B 0 using ∆B0 : >|∼⊥ is in the preferential
closure of B 0 iff ∆B0 |= ⊥.
Step 4.2. Assuming B 0 is consistent, and given the ranking, we define the back-
ground theory Te of the agent as Te = {> |= ¬C | C|∼D ∈ B 0 and r(C|∼D) =
∞}4 , and a correspondent set of formulae Φ = {¬C | > |= ¬C ∈ Te } (one
may verify that, modulo classical logical equivalence, T ⊆ Te ).
Step 4.3. once we have Te , we can also identify the set of sequents B,
e i.e., the defea-
sible part of the information contained in B : B = {C|∼D ∈ B 0 | r(C|∼D) <
0 e
∞} (one may verify that Be ⊆ B). We indicate the ranking of Be as the highest
ranking value of the conditionals in B, e i.e. r(B)
e = max{r(C|∼D) | C|∼D ∈
B}.
e
Essentially, so far we have moved the non-defeasible knowledge ‘hidden’ in B to T .
Step 5. Now we can define the lexicographic closure of hTe , Bi. e Consider the set of the
materializations of the sequents in B, e ∆ = {C → D | C|∼D ∈ B}, e and assume
that r(B) e = k. ∆k represents the subset of ∆ composed by conditionals of rank k,
i.e. ∆i = {C → D ∈ ∆ | r(C|∼D) = i}. We can associate to every subset D of ∆
a string of natural numbers hn0 , . . . , nk iD , where n0 =| D ∩ ∆k |, and, in general,
ni =| D ∩ ∆k−i |. In this way we obtain a string of numbers expressing how
many materializations of defaults are contained in D for every ranking value. We
can order linearly the tuples hn0 , . . . , nk iD using the classic lexicographic order:
hn0 , . . . , nk i ≥ hm0 , . . . , mk i iff
(i) for every i (0 ≤ i ≤ k), ni ≥ mi , or
(ii) if ni < mi , there is a j s.t. j < i and nj > mj .
4
One may easily verify the correctness of this definition referring to the following results in
[3], Section 7.5.3: Definition 7.5.1, the definition of clash (p.178), Corollary 7.5.7, Definition
7.5.2, and Lemma 7.5.5. It suffices to show that the set of the sequents with ∞ as ranking value
represents the greatest clash of B, which can be proved quite immediately by the definition of
the exceptionality ranking.
Page 31 of 110
This lexicographic order is based on the intuitions that the more conditionals are
satisfied, the better it is, and that more exceptional conditionals have the priority
over less exceptional ones. The linear ordering > between the tuples corresponds to
a modular ordering ≺ between the subsets of ∆:
Seriousness ordering ≺ ([18], Definition 2). Let D and E be subsets of ∆. D is
preferred to (more serious than) E (D ≺ E) iff hn0 , . . . , nk iD > hn0 , . . . , nk iE .
Given a conditional knowledge base hT , Bi (transformed into hΦ, ∆i) and a set of
premises Γ , we indicate by D the set of the preferred subsets of ∆ that are consistent
with the certain information we have at our disposal, that is Φ and Γ :
DΓ = min{D ⊆ ∆ | Γ ∪ Φ ∪ D 6|= ⊥}
≺
l
The consequence relation |∼hT ,Bi , corresponding to the lexicographic closure of
hT , Bi, will be defined as:
l
Γ |∼hT ,Bi E iff Γ ∪ Φ ∪ D |= E for every D ∈ DΓ .
The procedure proposed by Lehmann relies heavily on a proposal by Poole, [20],
but it makes also use of the cardinality and the exceptionality ranking of the sets of
defaults. At the propositional level, the problem of deciding if a sequent C|∼D is in the
lexicographic closure of a conditional base K = hT , Bi is exponential (see [18], p.81).
Example 3. Consider the knowledge base in the example 2: K = hT , Bi with T =
{P |= B} and B = {P |∼¬F, B|∼F, B|∼T }. We define (Step 1) the set B 0 = {P ∧
¬B|∼⊥, P |∼¬F, B|∼F, B|∼T }, and the ranking values obtained from the materializa-
tion of B 0 are r(B|∼F ) = r(B|∼T ) = 0, r(P |∼¬F ) = 1, r(P ∧ ¬B|∼⊥) = ∞ (Steps
2-3) . Hence, we end up with a pair hΦ, ∆i, with Φ = {¬(P ∧ ¬B)}, ∆ = ∆0 ∪ ∆1 ,
∆0 = {B → F, B → T }, and ∆1 = {P → ¬F } (Steps 4-5). We want to check if we
can derive P |∼T , impossible to derive from the rational closure of K. We have to find
which are the most serious subsets of ∆ that are consistent with P and Φ: it turns out
that there is only one, D = {B → T, P → ¬F }, and we have {P } ∪ Φ ∪ D |= T , that
l
is, P |∼hT ,Bi T .
3 Lexicographic Closure in ALC
Now we redefine Lehmann’s procedure for the DL case. We consider a significant DL
representative, namely ALC (see e.g. [1], Chap. 2). ALC corresponds to a fragment
of first order logic, using monadic predicates, called concepts, and diadic ones, called
roles. To ease the reader in taking account of the correspondence between the proce-
dure presented in Section 2 and the proposal in ALC, we are going to use the same
notation for the components playing an analogous role in the two constructions: capital
letters C, D, E, . . . now indicate concepts, instead of propositions, and |= and |∼ to in-
dicate, respectively, the ‘classical’ consequence relation of ALC and a non-monotonic
consequence relation in ALC. We have a finite set of concept names C, a finite set of
role names R and the set L of ALC -concepts is defined inductively as follows: (i)
C ⊂ L; (ii) >, ⊥ ∈ L; (iii) C, D ∈ L ⇒ C u D, C t D, ¬C ∈ L; and (iii)
Page 32 of 110
C ∈ L, R ∈ R ⇒ ∃R.C, ∀R.C ∈ L. Concept C → D is used as a shortcut of
¬C t D. The symbols u and t correspond, respectively, to the conjunction ∧ and the
disjunction ∨ of classical logic. Given a set of individuals O, an assertion is of the form
a:C (C ∈ L) or of the form (a, b):R (R ∈ R), respectively indicating that the individual
a is an instance of concept C, and that the individuals a and b are connected by the role
R. A general inclusion axiom (GCI) is of the form C v D (C, D ∈ L) and indicates
that any instance of C is also an instance of D. We use C = D as a shortcut of the pair
of C v D and D v C.
From a FOL point of view, concepts, roles, assertions and GCIs, may be seen as
formulae obtained by the following transformation
τ (a:C) = τ (a, C)
τ (x, C u D) = τ (x, C) ∧ τ (x, D)
τ ((a, b):R) = R(a, b)
τ (x, C t D) = τ (x, C) ∨ τ (x, D)
τ (C v D) = ∀x.τ (x, C) → τ (x, D)
τ (x, ∃R.C) = ∃y.R(x, y) ∧ τ (y, C)
τ (x, A) = A(x)
τ (x, ∀R.C) = ∀y.R(x, y) → τ (y, C) .
τ (x, ¬C) = ¬τ (x, C)
Now, a classical knowledge base is defined by a pair K = hA, T i, where T is a finite
set of GCIs (a TBox) and A is a finite set of assertions (the ABox), whereas a defeasible
knowledge base is represented by a triple K = hA, T , Bi, where additionally B is a finite
set of defeasible inclusion axioms of the form C @ ∼ D (‘an instance of a concept C is
typically an instance of a concept D’ ), with C, D ∈ L.
Example 4. Consider Example 3. Just add a role P rey in the vocabulary, where a role
instantiation (a, b):P rey is read as ‘a preys on b’, and add also two more concepts,
I (Insect) and F i (Fish). A defeasible KB is K = hA, T , Bi with A = {a:P , b:B,
(a, c):P rey, (b, c):P rey}; T = {P v B, I v ¬F i} and B = {P @ ∼ ¬F , B @
∼ F,
B@ ∼ T, P @ ∼ ∀P rey.F i, B @ ∼ ∀P rey.I}. 2
The particular structure of a defeasible KB allows for the ‘isolation’ of the pair hT , Bi,
that we could call the conceptual system of the agent, from the information about the
individuals (formalised in A) that will play the role of the facts known to be true. In
the next section we are going to work with the information about concepts hT , Bi first,
exploiting the immediate analogy with the homonymous pair of Section 2, then we will
address the case involving individuals as well.
Construction of the Lexicographic Closure. We apply to hT , Bi a procedure analo-
gous to the propositional one, in order to obtain from hT , Bi a pair hΦ, ∆i, where Φ and
∆ are two sets of concepts, the former representing the background knowledge, that is,
concepts necessarily applying to each individual, the latter playing the role of defaults,
that is, concepts that, modulo consistency, apply to each individual. Hence, starting with
hT , Bi, we apply the following steps.
Step 1. Define B 0 = B ∪{C u¬D @ ∼ ⊥ | C v D ∈ T }. Now our agent is characterized
by the pair h∅, B 0 i.
Step 2. Define ∆B0 = {> v C → D | C @ ∼ D ∈ B 0 }, and define a set AB0 as the set
of the antecedents of the conditionals in B 0 , i.e. AB0 = {C | C @
∼ D ∈ B 0 }.
Step 3. We determine the exceptionality ranking of the sequents in B 0 using the set of
the antecedents AB0 and the materializations in ∆B0 , where a concept C is excep-
tional w.r.t. a set of sequents D iff ∆D |= > v ¬C. The steps are the same of the
propositional case (Steps 3.1 – 3.2), we just replace the expression ∆D |= ¬C with
the expression ∆D |= > v ¬C. In this way we define a ranking function r.
Page 33 of 110
Step 4. From ∆B0 and the ranking function r we obtain (i) that (Step 4.1.) we can verify
if the conceptual system of the agent is consistent by checking the consistency of
∆B0 , and (ii) (Steps 4.2.-4.3.) we can define the real background theory and the
defeasible information of the agent, respectively the sets Te and Be as:
∼ D ∈ B 0 and r(C @
Te = {> v ¬C | C @ ∼ D) = ∞}
Be = {C @
∼D|C@ ∼ D ∈ B 0 and r(C|∼D) < ∞} .
From Te and Be we define the correspondent sets of concepts Φ = {¬C | > v ¬C ∈
Te } and ∆ = {C → D | C @ ∼ D ∈ B}.e
Step 5. Now, obtained hΦ, ∆i and the ranking value of the elements of Be and, conse-
quently, of ∆ (assume r(B)
e = k), we can determine the seriousness ordering on the
subsets of ∆. The procedure is the same as for the propositional case, that is, (i)
we associate to every subset D of ∆ a string hn0 , . . . , nk i with ni =| D ∩ ∆k−i |,
and we obtain a lexicographic order ‘>’ between the strings. Then we define the
seriousness ordering ≺ between the subsets of ∆ as
D ≺ E iff hn0 , . . . , nk iD > hn0 , . . . , nk iE
for every pair of subsets D and E of ∆.
Hence, we obtain an analogous of the procedure defined for the propositional case by
substituting the conceptual system hT , Bi with the pair hΦ, ∆i.
Closure Operation over Concepts. Consider the pair hΦ, ∆i. Now we specify the no-
l
tion of lexicographic closure over the concepts, that is, a relation |∼hT ,Bi that tells us
what presumably follows from a finite set of concepts Γ . Again, we define for a set of
premises Γ the set of the most serious subsets of ∆ that are consistent with Γ and Φ.
l l l
DΓ = min{D ⊆ ∆ | 6|= Γu Φu D v ⊥}
≺
Having obtained DΓ , the lexicographic closure is defined as follows:
Γ |∼lhT ,Bi E iff |=
d d d
Γu Φu D v E for every D ∈ DΓ .
We can prove two main properties characterizing the proposition lexicographic closure
l l l
and respected by |∼hT ,Bi : (i) |∼hT ,Bi is a rational consequence relation, and (ii) |∼hT ,Bi
extends the rational closure.
Proposition 1. |∼hTe ,Bi
e is a rational consequence relation validating K = hT , Bi.
Page 34 of 110
This can be shown by noting that the analogous properties of the propositional rational
consequence relation are satisfied, namely:
(REF) C|∼hT ,∆i C
C |∼hT ,∆i E |= C = D C |∼hT ,∆i D |= D v E
(LLE) (RW)
D |∼hT ,∆i E C |∼hT ,∆i E
C u D |∼hT ,∆i E C |∼hT ,∆i D C |∼hT ,∆i E C |∼hT ,∆i D
(CT) (CM)
C |∼hT ,∆i E C u D |∼hT ,∆i E
C |∼hT ,∆i E D |∼hT ,∆i E C |∼hT ,∆i D C 6 |∼hT ,∆i ¬E
(OR) (RM)
C t D |∼hT ,∆i E C u E |∼hT ,∆i D
For the rational closure in ALC, we refer to the construction presented in [9], Section 3.
r
We indicate by |∼hT ,Bi the consequence relation defined there.
r
Proposition 2. The lexicographic closure extends the rational closure, i.e. |∼hT ,Bi ⊆
l
|∼hT ,Bi for every pair hT , Bi.
To prove this it is sufficient to check that, given a set of premises Γ and a pair hΦ, ∆i,
each of the sets in DΓ classically implies the default information that would be associ-
ated to Γ in its rational closure, as defined in [9].
Let us work out the analogue of Example 3 in the DL context.
Example 5. Consider the KB of Example 4 without the ABox. Hence, we start with
K = hT , Bi. Then K is changed into B 0 = {P u¬B @∼ ⊥, IuF i @
∼ ⊥, P @∼ ¬F , B @∼ F,
B @ ∼ T, P @ ∼ ∀P rey.I}. The set of the materializations of B 0 is
∼ ∀P rey.F i, B @
∆B0 = {> v P ∧ ¬B → ⊥, > v I u F i → ⊥, > v P → ¬F, > v B → F, > v B →
T, > v P → ∀P rey.F i, > v B → ∀P rey.I}, with AB0 = {P ∧ ¬B, I u F i, P, B}.
Following the procedure at Step 3, we obtain the ranking values of every inclusion
axiom in B 0 : namely, r(B @
∼ F ) = r(B @∼ T ) = r(B @
∼ ∀P rey.I) = 0; r(P @∼ ¬F ) =
r(P @∼ ∀P rey.F i) = 1 and r(P u ¬B @ ∼ ⊥) = r(I u F i @
∼ ⊥) = ∞. From such a
ranking, we obtain a background theory Φ = {¬(P ∧ ¬B), ¬(I u F i)}, and a default
set ∆ = ∆0 ∪ ∆1 , with
∆0 = {B → F, B → T, B → ∀P rey.I}
∆1 = {P → ¬F, P → ∀P rey.F i} .
l
To check if P |∼hT ,Bi T , we have to find the most serious subsets of ∆ that are consistent
d d
d P and the concepts in Φ (i.e. the most serious subsets D of ∆ s.t. 6|= Γ u Φ u
with
D v ⊥). Turns
d d that there is only one, D = {P → ¬F, P → ∀P rey.F i, B → T },
out
and |= P u Φ u D v T .
It is easy to check that we obtain the analogue sequents as in the propositional case and
avoid the same undesirable ones. Moreover we can derive also sequents connected to the
l l
roles, such as B|∼hT ,Bi ∀P rey.¬F i and P |∼hT ,Bi ∀P rey.¬I. 2
We do not have yet a proper proof, but we conjecture that the decision procedure should
be EXPTIME-complete also in ALC.
Closure Operation over Individuals. Now we will pay attention on how to apply the
lexicographic closure to the ABox. Unfortunately, the application of the lexicographic
Page 35 of 110
closure to the ABox results into a really more complicated procedure than in the case of
rational closure, as presented in the last paragraph of [9], Section 3. Assume that we have
already transformed our conceptual system hT , Bi into a pair hTe , Bi, e and eventually
into a pair hΦ, ∆i. In particular, dealing with the ABox, we assume that we start with
a knowledge base K = hA, Te , ∆i. We would like to infer whether a certain individual
a is presumably an instance of a concept C or not. The basic idea remains to associate
to every individual in A every default information from ∆ that is consistent with our
knowledge base, respecting the seriousness ordering of the subsets of ∆. As we will
see, the major problem to be addressed here is that we cannot obtain anymore a unique
lexicographic extension of the KB.
Example 6. Consider K = hA, ∅, ∆i, with A = {(a, b):R} and ∆ = {A u ∀R.¬A}.
Informally, if we apply the default to a first, we get b:¬A and we cannot apply the default
to b, while if we apply the default to b first, we get b:A and we cannot apply the default
to a. Hence, we may have two extensions. 2
The possibility of multiple extensions is due to the presence of the roles, that allow
the transmission of information from an individual to another; if every individual was
‘isolated’, without role-connections, then the addition of the default information to each
individual would have been a ‘local’ problem, treatable without considering the concepts
associated to the other individuals in the domain, and the extension of the knowledge
base would have been unique. On the other hand, while considering a specific individual,
the presence of the roles forces to consider also the information associated to other
individuals in order to maintain the consistency of the knowledge base, and, as shown
in example 6, the addition of default information to one individual could prevent the
association of default information to another.
We assume that hA, T i is consistent, i.e. hA, T i 6|= a:⊥, for any a. With OA we
indicate the individuals occurring in A. Given K = hA, T , ∆i, we say that a knowledge
base Ke = hA∆ , T i is a default extension of K iff
– K
e is classically consistent and A ⊆ A∆ .
d
– For any a ∈ OA , a:C ∈ A∆ \ A iff C = D for some D ⊂ ∆ s.t. hA∆ ∪
0 0 0
{a:D }, T i |= ⊥ for every D ⊆ ∆, with D ≺ D.
Essentially, we assign to each individual a ∈ OA one of the most serious default sets
that are consistent with the ABox.
Example 7. Referring to Example 6, consider K = hA, ∅, ∆i, with A = {(a, b) : R}
and ∆ = {A u ∀R.¬A, >}. Then we have two default-assumption extensions, namely
K
e 1 = hA ∪ {a:A, a:∀R.¬A}, ∅i and Ke 2 = hA ∪ {b:A, b:∀R.¬A}, ∅i. 2
A procedure to obtain a set As of default extensions is as follows:
(i) fix a linear order s = ha1 , . . . , am i of the individuals in OA , and let A0s = {A}.
Now, for every ai , 1 ≤ i ≤ m, do:
Page 36 of 110
(ii) for every element X of Adi−1
s , find the set all the ≺-minimal default sets {D1 , . . . ,
Dn }, s.t. Dj ⊆ ∆ and X ∪ {ai : Dj } is consistent (1 ≤ j ≤ n);
d
(iii) Define a new set Ais containing all the sets X ∪ {ai : Dj } obtained at the point
(ii).
(iv) Move to the next individual ai+1 .
(v) Once the points (ii)-(iv) have been applied to all the individuals in the sequence
s = ha1 , . . . , am i, set As = Am m
s , where As is the final set obtained at the end of the
procedure.
It can be shown that
Proposition 3. An Abox A0 is a default extension of K = {A, ∆} iff it is in the set As
obtained by some linear ordering s on OA and the above procedure.
For instance, related to Example 7, K
e 1 is obtained from the order ha, bi, while K
e 2 is
obtained from the order hb, ai.
Example 8. Refer to Example 5, and let K = {A, T , ∆}, where A = {a:P , b:B,
(a, c):P rey, (b, c):P rey}, T = {P v B, I v ¬F i}, ∆ = {B → F, B → T, B →
∀P rey.I, P → ¬F, P → ∀P rey.F i}. If we consider an order where a is before b then
we associate D = {B → T, P → ¬F, P → ∀P rey.F i} to a, and consequently c is
presumed to be a fish and we are prevented in the association of B → ∀P rey.I to b. If
we consider b before a, c is not a fish and we cannot apply P → ∀P rey.F i to a. 2
If we fix a priori a linear order s on the individuals, we may define a consequence relation
depending on the default extensions generated from it, i.e. the sets of defaults in As : we
say that a:C is a defeasible consequence of K = hA, T , ∆i w.r.t. s, written K ls a:C,
iff A0 |= a:C for every A ∈ As .
For instance, related to Example 7 and order s1 = ha, bi, we may infer that K ls1 a:A,
while with order s2 = hb, ai, we may infer that K ls2 b:A.
The interesting point of such a consequence relation is that it satisfies the properties
of a rational consequence relation in the following way.
REFDL hA, ∆i s a:C for every a:C ∈ A
hA, ∆i s a:C hA, ∆i s b:D
hA ∪ {b:D}, ∆i s a:C D = E CMDL
hA ∪ {b:D}, ∆i s a:C
LLEDL
hA ∪ {b:E}, ∆i s a:C
hA ∪ {b:D}, ∆i s a:C hA ∪ {b:E}, ∆i s a:C
hA, ∆i s a:C C v D ORDL
hA ∪ {b:D t E}, ∆i s a:C
RWDL
hA, ∆i s a:D
hA, ∆i s a:C hA, ∆i 6 s b:¬D
hA ∪ {b:D}, ∆i s a:C hA, ∆i RMDL
s b:D hA ∪ {b:D}, ∆i s a:C
CTDL
hA, ∆i s a:C
We can show that
Proposition 4. Given K and a linear order s of the individuals in K, the consequence
relation ls satisfies the properties REFDL − RMDL .
Page 37 of 110
4 Conclusions
In this paper we have proposed an extension of a main non-monotonic construction,
the lexicographic closure (see [18]), for the DL ALC. This work carries forward the
approach presented in [9], where the adaptation of the rational closure in ALC is pre-
sented. Here we have first presented the procedure at the propositional level, and then
we have adapted it for ALC, first considering only the conceptual level, the information
contained in the TBox, and then considering also the particular information about the
individuals, the ABox, assuming we are working with unfoldable KB.
It is straightforward to see that, while the procedure defined for the TBox is simple and
well-behaved, the procedure for the ABox is really more complex than the one for the
rational closure presented in [9].
Besides checking the exact costs of these procedures from the computational point of
view and checking for which other DL formalisms we can apply them, we conjecture
that a semantical characterization of the above procedures can be obtained using the kind
of semantical constructions presented in [8].
References
1. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter Patel-
Schneider. The Description Logic Handbook: Theory, Implementation and Applications.
Cambridge University Press, 2003.
2. Franz Baader and Bernhard Hollunder. How to prefer more specific defaults in terminological
default logic. In In Proceedings of the IJCAI, pages 669–674. Morgan Kaufmann Publishers,
1993.
3. Alexander Bochman. A logical theory of nonmonotonic inference and belief change.
Springer-Verlag New York, Inc., New York, NY, USA, 2001.
4. P. Bonatti, C. Lutz, and F. Wolter. The complexity of circumscription in description logic.
Journal of Artificial Intelligence Research, 35:717–773, 2009.
5. Piero A. Bonatti, Marco Faella, and Luigi Sauro. Defeasible inclusions in low-complexity
dls. J. Artif. Intell. Res. (JAIR), 42:719–764, 2011.
6. Piero A. Bonatti, Marco Faella, and Luigi Sauro. On the complexity of el with defeasible
inclusions. In IJCAI-11, pages 762–767. IJCAI/AAAI, 2011.
7. Gerhard Brewka and D Sankt Augustin. The logic of inheritance in frame systems. In IJCAI-
87, pages 483–488. Morgan Kaufmann Publishers, 1987.
8. K. Britz, T. Meyer, and I. Varzinczak. Semantic foundation for preferential description logics.
In D. Wang and M. Reynolds, editors, Proceedings of the 24th Australasian Joint Conference
on Artificial Intelligence, number 7106 in LNAI, pages 491–500. Springer, 2011.
9. Giovanni Casini and Umberto Straccia. Rational closure for defeasible description logics. In
Tomi Janhunen and Ilkka Niemelä, editors, JELIA, volume 6341 of Lecture Notes in Com-
puter Science, pages 77–90. Springer, 2010.
10. Giovanni Casini and Umberto Straccia. Defeasible inheritance-based description logics. In
IJCAI-11, pages 813–818, 2011.
11. Francesco M. Donini, Daniele Nardi, and Riccardo Rosati. Description logics of minimal
knowledge and negation as failure. ACM Trans. Comput. Log., 3(2):177–225, 2002.
12. Dov M. Gabbay, C. J. Hogger, and J. A. Robinson, editors. Handbook of logic in artificial in-
telligence and logic programming (vol. 3): nonmonotonic reasoning and uncertain reasoning.
Oxford University Press, Inc., New York, NY, USA, 1994.
Page 38 of 110
13. Laura Giordano, Valentina Gliozzi, Nicola Olivetti, and Gian Luca Pozzato. Reasoning about
typicality in low complexity dls: The logics el; tmin and dl-litec tmin . In IJCAI, pages 894–
899. IJCAI/AAAI, 2011.
14. Laura Giordano, Nicola Olivetti, Valentina Gliozzi, and Gian Luca Pozzato. Alc + t: a pref-
erential extension of description logics. Fundam. Inform., 96(3):341–372, 2009.
15. S. Grimm and P. Hitzler. A preferential tableaux calculus for circumscriptive ALCO. In
RR-09, number 5837 in LNCS, pages 40–54, Berlin, Heidelberg, 2009. Springer-Verlag.
16. Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferen-
tial models and cumulative logics. Artif. Intell., 44(1-2):167–207, 1990.
17. Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail?
Artif. Intell., 55(1):1–60, 1992.
18. Daniel J. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell.,
15(1):61–82, 1995.
19. David Makinson. General patterns in nonmonotonic reasoning. In Handbook of logic in arti-
ficial intelligence and logic programming: nonmonotonic reasoning and uncertain reasoning,
volume 3, pages 35–110. Oxford University Press, Inc., New York, NY, USA, 1994.
20. David Poole. A logical framework for default reasoning. Artif. Intell., 36(1):27–47, 1988.
21. Joachim Quantz and Veronique Royer. A preference semantics for defaults in terminological
logics. In KR-92, pages 294–305. Morgan Kaufmann, Los Altos, 1992.
22. U. Straccia. Default inheritance reasoning in hybrid kl-one-style logics. IJCAI-93, pages
676–681, 1993.
Page 39 of 110
A normal form for hypergraph-based module
extraction for SROIQ
Riku Nortje, Katarina Britz, and Thomas Meyer
Center for Artificial Intelligence Research, University of KwaZulu-Natal and CSIR
Meraka Institute, South Africa
Email: nortjeriku@gmail.com; {arina.britz;tommie.meyer}@meraka.org.za
Abstract. Modularization is an important part of the modular design
and maintenance of large scale ontologies. Syntactic locality modules,
with their desirable model theoretic properties, play an ever increasing
role in the design of algorithms for modularization, partitioning and rea-
soning tasks such as classification. It has been shown that, for the DL
EL+ , the syntactic locality module extraction problem is equivalent to
the reachability problem for hypergraphs. In this paper we investigate
and introduce a normal form for the DL SROIQ which allows us to map
any SROIQ ontology to an equivalent hypergraph. We then show that
standard hyperpath search algorithms can be used to extract modules
similar to syntactic locality modules for SROIQ ontologies.
1 Introduction
The advent of the semantic web presupposes a significant increase in the size
of ontologies, their distributive nature and the requirement for fast reasoning
algorithms. Modularization techniques not only play an increasingly important
role in the design and maintenance of large-scale distributed ontologies, but also
in the design of algorithms that increase the efficiency of reasoning tasks such
as subsumption testing and classification [11, 1].
Extracting minimal modules is computationally expensive and even undecid-
able for expressive DLs [2, 3]. Therefore, the use of approximation techniques and
heuristics play an important role in the effective design of algorithms. Syntactic
locality [2, 3], because of its excellent model theoretic properties, has become an
ideal heuristic and is widely used in a diverse set of algorithms [11, 1, 4].
Suntisrivaraporn [11] showed that, for the DL EL+ , ⊥-locality module extrac-
tion is equivalent to the reachability problem in directed hypergraphs. Nortjé et
al. [9, 10] extended the reachability problem to include >-locality and introduced
bidirectional reachability modules as a subset of ⊥> modules.
In this paper we introduce a normal form for the DL SROIQ, which allows
us to map any SROIQ ontology to an equivalent syntactic locality preserving
hypergraph. We show that, given this mapping, the extraction of ⊥-locality
modules is equivalent to the extraction of all B-hyperpaths, >-locality is similar
to extracting all F -hyperpaths and ⊥>∗ modules to that of extracting frontier
graphs. These similarities demonstrate a unique relationship between reasoning
Page 40 of 110
tasks, based on syntactic locality, for SROIQ ontologies, and standard well
studied hypergraph algorithms.
2 Preliminaries
2.1 Hypergraphs
Hypergraphs are a generalization of graphs and have been extensively studied
since the 1970s as a powerful tool for modelling many problems in Discrete Math-
ematics. In this paper we adapt the definitions of hypergraphs and hyperpaths
from [8, 12].
A (directed) hypergraph is a pair H = hV, Ei, where V is a finite set of nodes,
E ⊆ 2V × 2V is the set of hyperedges such that for every e = (T (e), H(e)) ∈ E,
T (e) 6= ∅, H(e) 6= ∅, and T (e) ∩ H(e) = ∅. A hypergraph H0 = hV 0 , E 0 i is a
subhypergraph of H if V 0 ⊆ V and E 0 ⊆ E. A hyperedge e is a B-hyperedge
if |H(e)| = 1. A B-hypergraph is a hypergraph such that each hyperedge is a
B-hyperedge. A hyperedge e is an F-hyperedge if |T (e)| = 1. An F-hypergraph is
a hypergraph such that each hyperedge is an F-hyperedge. A BF-hypergraph is
a hypergraph for which every edge is either a B- or an F-hyperedge.
Let e = (T (e), H(e)) be a hyperedge in some directed hypergraph H. Then,
T (e) is known as the tail of e and H(e) is known as the head of e. Given a
directed hypergraph H = (V, E), its symmetric image H is a directed hypergraph
defined as: V(H) = V(H) and E(H) = {(H, T ) | (T, H) ∈ E(H)}. We denote by
BS(v) = {e ∈ E | v ∈ H(e)} and F S(v) = {e ∈ E | v ∈ T (e)} respectively
the backward star and forward star of a node v. Let n and m be the number of
nodesP and hyperedges in a hypergraph H. We define the size of H as size(H) =
|V| + e∈E (|T (e)| + |H(e)|).
Q
A simple path st from s ∈ V(H) to t ∈ V(H) in H is a sequence (v1 , e1 , v2 , e2 ,
..., vk , ek , vk+1 ) consisting of distinct nodes and hyperedges such that s = v1 ,
t = vk+1 and for Q every 1 ≤ i ≤ k, vi ∈ T (ei ) and vi+1 ∈ H(ei ). If in addition
t ∈ T (e1 ) then st is a simple cycle. A simple path is cycle free if it does not
contain any subpath that is a simple cycle.
A node s is B-connected to itself. If there is a hyperedge e such that all nodes
vi ∈ T (e) are B-connected to s, then every vj ∈ H(e) is B-connected to s. A
B-hyperpath from s ∈ V(H) to t ∈ V(H)Q is a minimal subhypergraph of H where
t is B-connected to s. An F-hyperpath st from s ∈ V(H) to t ∈ V(H) in H is
Q
a subhyperpath of H such that st is a B-hyperpath from t to s in H. A BF-
hyperpath from s ∈ V(H) to t ∈ V(H) in H is a minimal (in the inclusion sense)
subhyperpath of H such that it is simultaneously both a B-hyperpath and an F-
hyperpath from s to t in H. We note that every hypergraph H can be transformed
to a BF-hypergraph H0 by replacing each hyperedge e = (T (e), H(e)) with the
two hyperedges e1 = (T (e), {nv }), e2 = ({nv }, H(e)) where nv is a new node.
2
Page 41 of 110
Algorithm 1 (Visiting a hypergraph [8])
Procedure Bvisit(s,H) Procedure Fvisit(t,H)
1 : for each u ∈ V do blabel(u) := f alse; for each u ∈ V do f label(u) := f alse;
2 : for each e ∈ E do T (e) := 0; for each e ∈ E do T (e) := 0;
3 : Q := {s}; blabel(s) := true; Q := {t}; f label(t) := true;
4 : while Q 6= ∅ do while Q 6= ∅ do
5: select and remove u ∈ Q; select and remove u ∈ Q;
6: for each e ∈ F S(u) do for each e ∈ BS(u) do
7: T (e) := T (e) + 1; H(e) := H(e) + 1;
8: if T (e) := |T ail(e)|then if H(e) := |Head(e)|then
9: for each v ∈ Head(e) do for each v ∈ T ail(e) do
10 : if blabel(v) = f alse then if f label(v) = f alse then
11 : blabel(v) = true f label(v) = true
12 : Q := Q ∪ {v} Q := Q ∪ {v}
Given some node s, Algorithm 1 can be used to find all B-connected or F-
connected nodes to s in O(size(H)) time. Here, the set of all B-hyperpaths from
s and F-hyperpaths to t are respectively represented by all those nodes n such
that blabel(n) = true or f label(n) = true, as well as the edges connecting those
nodes.
Fig. 1. Example hypergraph H1
Example 1. In Figure 1 we have H1 = (V1 , E1 ), with V1 = {v1 , ..., v9 } and E1 =
{e1 , e2 , e3 , e4 , e5 , e6 } such that e1 = ({v1 }, {v2 , v3 }), e2 = ({v2 }, {v1 , v5 , v6 }),
e3 = ({v3 , v4 }, {v7 }), e4 = ({v5 , v6 }, {v8 }), e5 = ({v7 }, {v6 , v8 }) and e6 =
({v6 , v8 }, {v9 }). The directed hypergraph G1 with nodes V(G1 ) = {v1 , v2 , v3 , v5 ,
v6 , v8 , v9 } and E(G1 ) = {e1 , e2 , e4 , e6 } is a B-hyperpath from v1 to v9 in H1 . The
hypergraph G2 with V(G2 ) = {v3 , v4 , v6 , v7 , v8 , v9 } and E(G2 ) = {e3 , e5 , e6 } is an
F-hyperpath from v3 to v9 in H1 . The hypergraph G3 with V(G3 ) = {v6 , . . . v9 }
and E(G3 ) = {e5 , e6 } is a BF-hyperpath from v7 to v9 in H1 .
Definition 1. Given a hypergraph H = (V, E), the frontier graph H0 = (V 0 , E 0 , s, t)
of H, such that V 0 ⊆ V, E 0 ⊆ E, s, t ∈ V, is the maximal (in the inclusion sense)
BF -graph in which (1) s and t are the origin and destination nodes, (2) if v ∈ V 0
then v is B-connected to s, and t is F-connected to v in H0 .
3
Page 42 of 110
Algorithm 2 (Frontier graph Extraction Algorithm [8])
Procedure frontier(H, H0 , s, t)
1 : H0 := H; change := true
2 : while change = true do
3 : change = f alse
3 : H0 = Bvisit(s, H0 ); H0 = F visit(t, H0 )
4 : for each v ∈ V 0
5: if blabel(v) = f alse or f label(v) = f alse then
6: change := true
7: V 0 = V 0 − {v}; E 0 = E 0 − F S(v) − BS(v)
8 : if s 6∈ V 0 or t 6∈ V 0 then
9: H0 := ∅; change := f alse;
Algorithm 2 can be used to extract a frontier graph for any source and
destination nodes and runs in O(n size(H)) time.
2.2 The DL SROIQ
In this section we give a brief introduction to the DL SROIQ [5, 7] with its
syntax and semantics listed in Table 1. NC , NR and NI denote disjoint sets
of atomic concept names, atomic roles names and individual names. The set
NR includes the universal role. Well-formed formulas are created by combining
concepts from the table by using the connectives ¬, u, t etc.
Given R1 ◦ . . . ◦ Rn v R, where n > 1 and Ri , R ∈ NR , is a role inclusion
axiom (RIA). A role hierarchy is a finite set of RIAs. Here R1 ◦ . . . ◦ Rn denotes
a composition of roles where R, Ri may also be an inverse role R− . A role R
is simple if it: (1) does not appear on the right-hand side of a RIA; (2) is the
inverse of a simple role; or (3) appears on the right-hand side of a RIA only if the
left-hand side consists entirely of simple roles. Ref (R), Irr(R) and Dis(R, S),
where R, S are roles other than U , are role assertions. A set of role assertions
is simple w.r.t. a role-hierarchy H if each assertion Irr(R) and Dis(R, S) uses
only simple roles w.r.t. H.
A strict partial order ≺ on NR is a regular order if, and only if, for all roles
R and S: S ≺ R iff S − ≺ R. Let ≺ be a regular order on roles. A RIA w v R
is ≺-regular if, and only if, R ∈ NR and w has one of the following forms: (1)
R ◦ R, (2) R− , (3) S1 ◦ . . . ◦ Sn , where each Si ≺ R, (4) R ◦ S1 ◦ . . . ◦ Sn , where
each Si ≺ R and (5) S1 ◦ . . . ◦ Sn ◦ R, where each Si ≺ R. A role hierarchy H is
regular if there exists a regular order ≺ such that each RIA in H is ≺-regular.
An RBox is a finite, regular role hierarchy H together with a finite set of
role assertions simple w.r.t. H. If a1 , . . . , an are in NI , then {a1 , . . . , an } is a
nominal. No is the set of all nominals. The set of SROIQ concept descriptions
is the smallest set such that: (1) ⊥,>, each C ∈ NC , and each o ∈ No is a concept
description. (2) If C is a concept description, then ¬C is a concept description.
(3) If C and D are concept descriptions, R is a role description, S is a simple role
description, and n is a non-negative integer, then the following are all concept
descriptions: (C u D), (C t D), ∃R.C, ∀R.C, 6 nS.C, > nS.C, ∃S.Self .
4
Page 43 of 110
Table 1. Syntax and semantics of SROIQ
Concept Syntax Semantics
atomic concept C ∈ NC C I ⊆ ∆I
individual A ∈ NI aI ∈ ∆I
nominal {a1 , . . . , an }, ai ∈ NI {aI1 , . . . , aIn }
role R ∈ NR R I ⊆ ∆I × ∆I
inverse role R − , R ∈ NR R−I = {(y, x)|(x, y) ∈ RI }
universal role U U I = ∆I × ∆I
role composition R1 ◦ . . . ◦ Rn {(x, z)|(x, y1 ) ∈ R1I ∧ (y1 , y2 ) ∈
R2I ∧ . . . ∧ (yn , z) ∈ Rn+1 I
}
top > >I = ∆I
bottom ⊥ ⊥I = ∅
negation ¬C (¬C) = ∆I \ C I
I
conjunction C1 u C2 (C1 u C2 )I = C1I ∩ C2I
disjunction C1 t C2 (C1 t C2 )I = C1I ∪ C2I
exist restriction ∃R.C {x|(∃y)[(x, y) ∈ RI ∧ y ∈ C I ]}
value restriction ∀R.C {x|(∀y)[(x, y) ∈ RI → y ∈ C I ]}
self restriction ∃R.Self {x|(x, x) ∈ RI }
atmost restriction 6 nR.C {x|#{y|(x, y) ∈ RI ∧ y ∈ C I } 6 n}
atleast restriction > nR.C {x|#{y|(x, y) ∈ RI ∧ y ∈ C I } > n}
Axiom Syntax Semantics
concept inclusion C1 v C2 C1I ⊆ C2I
role inclusion R1 ◦ . . . ◦ Rn v R (R1 ◦ . . . ◦ Rn )I ⊆ RI
reflexivity Ref (R) {(x, x)|x ∈ ∆I } ⊆ RI
irreflexivity Irr(R) {(x, x)|x ∈ ∆I } ∩ RI = ∅
disjointness Dis(R, S) S I ∩ RI = ∅
class assertion C(a) aI ∈ C I
inequality assertion a 6= b aI 6= bI
role assertion R(a, b) (aI , bI ) ∈ RI
negative role assertion ¬R(a, b) (aI , bI ) 6∈ RI
If C and D are concept description then C v D is a general concept inclusion
(GCI) axiom. A TBox is a finite set of GCIs. If C is a concept description,
a, B ∈ NI , R, S ∈ NR with S a simple role description, then C(a), R(a, b),
¬S(a, b), and a 6= b, are individual assertions. An SROIQ ABox is a finite set
of individual assertions. All GCIs, RIAs, role assertions, and individual assertions
are referred to as axioms. A SROIQ-KB base is the union of a TBox, RBox
and ABox.
2.3 Modules
Definition 2. (Module for the arbitrary DL L) Let L be an arbitrary de-
scription language, O an L ontology, and σ a statement formulated in L. Then,
O0 ⊆ O is a module for σ in O (a σ-module in O) whenever: O |= σ if and only
if O0 |= σ. We say that O0 is a module for a signature S in O (an S-module in
O) if, for every L statement σ with Sig(σ) ⊆ S, O0 is a σ-module in O.
5
Page 44 of 110
Definition 2 is sufficiently general so that any subset of an ontology preserving
a statement of interest is considered a module, the entire ontology is therefore
a module in itself. An important property of modules in terms of the modular
reuse of ontologies is safety [2, 3]. Intuitively, a module conforms to a safety
condition whenever an ontology T reuses concepts from an ontology T 0 in such
a way so that it does not change the meaning of any of the concepts in T 0 . This
may be formalized in terms of the notion of conservative extensions:
Definition 3. (Conservative extension [3]) Let T and T1 be two ontologies
such that T1 ⊆ T , and let S be a signature. Then (1) T is an S-conservative
extension of T1 if, for every α with Sig(α) ⊆ S, we have T |= α iff T1 |= α. (2)
T is a conservative extension of T1 if T is an S-conservative extension of T1 for
S = Sig(T1 ).
Definition 4. (Safety [3, 6]) An ontology T is safe for T 0 if T ∪ T 0 is a
conservative extension of T 0 . Further let S be a signature. We say that T is safe
for S if, for every ontology T 0 with Sig(T ) ∩ Sig(T 0 ) ⊆ S, we have that T ∪ T 0
is a conservative extension of T 0 .
Intuitively, given a set of terms, or seed signature, S, a S-module M based
on deductive-conservative extensions is a minimal subset of an ontology O such
that for all axioms α with terms only from S, we have that M |= α if, and only if,
O |= α, i.e., O and M have the same entailments over S. Besides safety, reuse of
modules requires two additional properties namely coverage and independence.
Definition 5. (Module coverage [6]) Let S be a signature and T 0 , T be
ontologies with T 0 ⊆ T such that S ⊆ Sig(T 0 ). Then, T 0 guarantees coverage of
S if T 0 is a module for S in T .
Definition 6. (Module Independence [6]) Given an ontology T and signa-
tures S1 , S2 , we say that T guarantees module independence if, for all T1 with
Sig(T ) ∩ Sig(T1 ) ⊆ S1 , it holds that T ∪ T1 is safe for S2 .
Unfortunately, deciding whether or not a set of axioms is a minimal module
is computationally hard or even impossible for expressive DLs [2, 3]. However,
if the minimality requirement is dropped, good sized approximations can be
defined that are efficiently computable, as in the case of syntactic locality, which
modules are extracted in polynomial time.
Algorithm 3 (Extract a locality module [2])
Procedure extract-module(T , S, x)
Inputs: Tbox T ; signature S; x ∈ ⊥, >; Output x-module M
1 : M := ∅; T 0 = T ;
2 : repeat
3 : change = f alse
4 : for each α ∈ T 0
5: if α not x-local w.r.t. S∪Sig(M) then
6: M = M + {α}
7: T 0 = T 0 \ {α}
8: changed = true
9 : until changed = f alse
6
Page 45 of 110
Definition 7. (Syntactic locality [3]) Let S be a signature and O a SROIQ
ontology. An axiom α is ⊥-local w.r.t. S (>-local w.r.t S) if α ∈ Ax(S), as
defined in the grammar:
⊥-Locality
Ax(S) ::= C ⊥ v C|C v C > |w⊥ v R|Dis(S ⊥ , S)|Dis(S, S ⊥ )
Con (S) ::= A⊥ |¬C > |C ⊥ u C|C u C ⊥ |C1⊥ t C2⊥ |∃R⊥ .C|∃R.C ⊥
⊥
|∃R⊥ .Self | > nR⊥ .C| > nR.C ⊥
Con (S) ::= ¬C ⊥ |C1> u C2> |C > t C|C t C > |∀R.C > | 6 nR.C >
>
|∀R⊥ .C| 6 nR⊥ .C
>-Locality
Ax(S) ::= C ⊥ v C|C v C > |w v R>
Con (S) ::= ¬C > |C ⊥ u C|C u C ⊥ |C1⊥ t C2⊥ |∃R.C ⊥ | > nR.C ⊥
⊥
|∀R> .C ⊥ | 6 nR> .C ⊥
Con (S) ::= A> |¬C ⊥ |C1> u C2> |C > t C|C t C > |∀R.C > |
>
∃R> .C > | > nR> .C > | 6 nR.C > |∀R⊥ .C| 6 nR⊥ .C
In the grammar, we have that A⊥ , A> 6∈ S is an atomic concept, R⊥ , R> (resp.
S ⊥ ,S > ) is either an atomic role (resp. a simple atomic role) not in S or the
inverse of an atomic role (resp. of a simple atomic role) not in S, C is any con-
cept, R is any role, S is any simple role, and C ⊥ ∈ Con⊥ (S), C > ∈ Con> (S).
We also denote by w⊥ a role chain w = R1 ◦ . . . ◦ Rn such that for some i with
1 ≤ i ≤ n, we have that Ri is (possibly inverse of ) an atomic role not in S. An
ontology O is ⊥-local (>-local) w.r.t. S if α is ⊥-local (>-local) w.r.t. S for all
α ∈ O.
Algorithm 3 may be used to extract either >- or ⊥-locality modules. Al-
ternating the algorithm between ⊥- and >-locality module extraction until a
fixed-point is reached results in ⊥>∗ modules.
3 Normal form
In this section we will introduce a normal form for any SROIQ ontology. The
normal form is required to facilitate the conversion process between a SROIQ
ontology and a hypergraph.
Definition 8. Given Bi ∈ NC \ {⊥}, Ci ∈ NC \ {>}, D ∈ {∃R.B, ≥ nR.B,
∃R.Self }, Ri , Si ∈ NR and n > 1, a SROIQ ontology O is in normal form
if every axiom α ∈ O is in one of the following forms:
α1 : B1 u . . . u Bn v C1 t . . . t Cm α2 : ∃R.B1 v C1 t . . . t Cm
α3 : B1 u . . . u Bn v ∃R.Bn+1 α4 : B1 u . . . u Bn v ∃R.Self
α5 : ∃R.Self v C1 t . . . t Cm α6 : > nR.B1 v C1 t . . . t Cm
α7 : B1 u . . . u Bn v> nR.Bn+1 α8 : R1 ◦ . . . ◦ Rn v Rn+1
α9 : D1 v D2
In order to normalize a SROIQ ontology O we repeatedly apply the nor-
malization rules from Table 2. Each application of a rule rewrites an axiom into
an equivalent normal form. Algorithm 4 illustrates the conversion process.
7
Page 46 of 110
Algorithm 4 Given any SROIQ axiom α:
1. Recursively apply rules NR7 - NR11 to eliminate all equivalences, universal
restrictions, atmost restrictions and complex role fillers.
2. Given that α = (αL v αR ), recursively apply the following steps until αL
contains no disjunctions and αR contains no conjunctions:
(a) recursively apply rules NR1, NR3, NR6 to αL ,
(b) recursively apply rules NR2, NR4, NR5 to αR .
3. recursively apply any applicable rules from NR12 through NR21.
Table 2. SROIQ normalization rules
NR1 ¬Ĉ2 v Ĉ1 > v Ĉ1 t Ĉ2
NR2 B̂1 v ¬B̂2 B̂1 u B̂2 v ⊥
NR3 B̂ u D̂ v Ĉ B̂ u A v Ĉ, D̂ v A, A v D̂
NR4 B̂ v Ĉ t D̂ B̂ v Ĉ t A, D̂ v A, A v D̂
NR5 B̂ v Ĉ1 u Ĉ2 B̂ v Ĉ1 , B̂ v Ĉ2
NR6 B̂1 t B̂2 v Ĉ B̂1 v Ĉ, B̂2 v Ĉ
NR7 . . . ∀R.Ĉ . . . . . . ¬∃R.A . . ., A u Ĉ v ⊥, > v A t Ĉ
NR8 . . . ∃R.D̂ . . . . . . ∃R.A . . ., D̂ v A, A v D̂
NR9 . . . > nR.D̂ . . . . . . > nR.A . . ., D̂ v A, A v D̂
NR10 . . . 6 nR.Ĉ . . . . . . ¬(> (n + 1)R.Ĉ) . . .
NR11 B̂ ≡ Ĉ B̂ v Ĉ,Ĉ v B̂
NR12 > 0R.B v Ĉ > v Ĉ
NR13 B̂ v ∃R.⊥ B̂ v ⊥
NR14 B̂ v> nR.⊥ B̂ v ⊥
NR15 B̂ v> 0R.B
NR16 > nR.⊥ v Ĉ
NR17 ∃R.⊥ v Ĉ
NR18 B̂ u ⊥ v Ĉ
NR19 ⊥ v Ĉ
NR20 B̂ v Ĉ t >
NR21 B̂ v >
Above A 6∈ NC , B̂i and Ĉi are possibly complex concept descriptions
and D̂ a complex concept description. R ∈ NR , n > 0. We note that
rules NR18 and NR20 makes use of the commutativity of u and t.
Theorem 1. Algorithm 4 converts any SROIQ ontology O to an ontology O0
in normal form, such that O0 is a conservative extension of O. The algorithm
terminates in linear time and adds at most a linear number of axioms to O.
For every normalized ontology O0 the definition of syntactic locality from
Definition 7 may now be simplified to that of Definition 9. This is possible since
for every axiom α = (αL v αR ) ∈ O0 , ⊥-locality of α is dependent solely on αL
and >-locality is dependent solely on αR .
8
Page 47 of 110
Definition 9. (Normal form syntactic locality) Let S be a signature and O
a normalized SROIQ ontology. Any axiom α is ⊥-local w.r.t. S (>-local w.r.t
S) if α ∈ Ax(S), as defined in the grammar:
⊥-Locality
Ax(S) ::= C ⊥ v C | w⊥ v R | Dis(S ⊥ , S) | Dis(S, S ⊥ )
Con (S) ::= A⊥ | C ⊥ u | C u C ⊥ | ∃R⊥ .C | ∃R.C ⊥ | ∃R⊥ .Self |
⊥
> nR⊥ .C |> nR.C ⊥
>-Locality
Ax(S) ::= C v C > | w v R>
Con (S) ::= A> | C > t C | C t C > |∃R> .C > |> nR> .C > |
>
∃R> .Self
In the grammar, we have that A⊥ , A> 6∈ S is an atomic concept, R⊥ ,R> (resp.
S ⊥ ,S > ) is either an atomic role (resp. a simple atomic role) not in S or the
inverse of an atomic role (resp. of a simple atomic role) not in S, C is any con-
cept, R is any role, S is any simple role, and C ⊥ ∈ Con⊥ (S), C > ∈ Con> (S).
We also denote by w⊥ a role chain w = R1 ◦ . . . ◦ Rn such that for some i with
1 ≤ i ≤ n, we have that Ri is (possibly inverse of ) an atomic role not in S. An
ontology O is ⊥-local(>-local) w.r.t. S if α is ⊥-local(>-local) w.r.t. S for all
α ∈ O.
We note that we may denormalize a normalized ontology if we maintain a
possibly many-to-many mapping from normalized axioms to their original source
axioms. Formally, define a function denorm : Ô → 2O , with O an SROIQ
ontology and Ô its normal form. S
For brevity, we write denorm(Φ), with Φ a set
of normalized axioms, to denote α∈Φ denorm(α).
4 SROIQ hypergraph
Suntisrivaraporn [11] showed that for the DL EL+ , extracting ⊥-locality modules
are equivalent to the reachability problem in directed hypergraphs. This was
extended in [9, 10] to include a reachability algorithm for >-locality modules. In
this section we show that a SROIQ ontology O in normal form can be mapped
to a hypergraph which preserves both ⊥-locality and >-locality.
Definition 10. Let α be a normalized axiom and α⊥ a minimum set of symbols
from Sig(α) required to ensure that α is not ⊥-local, and let H = (V, E) be
a hypergraph. We say that an edge e ∈ E preserves ⊥-locality iff α⊥ = T (e).
Similarly, e ∈ E preserves >-locality whenever α> = H(e).
For each normal form axiom αi in Definition 8 we show that αi may be
mapped to a set of hyperedges, with nodes denoting symbols from Sig(αi ), such
that both ⊥-locality and >-locality are simultaneously preserved.
– Given α1 : B1 u . . . u Bn v C1 t . . . t Cm we map it to the hyperedge
eα1 = ({B1 , . . . , Bn }, {C1 , . . . , Cm }). We transform the hyperedge eα1 to
two new hyperedges eB F
α1 = ({B1 , . . . , Bn }, {H1 }) a B-hyperedge, eα1 =
9
Page 48 of 110
({H1 }, {C1 , . . . , Cm }) an F-hyperedge and with H1 a new node. By defi-
nition each Cj is B-connected to H1 if all Bi are B-connected to H1 . From
Definition 9 we know that this preserves ⊥-locality for α1 since it is ⊥-local,
w.r.t. a signature S, exactly when any of the conjuncts Bi 6∈ S. In other
words it is non ⊥-local exactly when all Bi ∈ S. The same also holds for >-
locality, since eF α1 requires every Ci ∈ α1 to be in S for H1 to be F-connected.
From Definition 9 we see that, w.r.t. a signature S, eF α1 is >-local exactly
when any of the disjuncts Ci 6∈ S.
– Given α2 : ∃R.B1 v C1 t. . .tCm or α6 : > nR.B1 v C1 t. . .tCm we map it
to the two hyperedges eB F
α2/6 = ({B1 , R}, {H2 }), eα2/6 = ({H2 }, {C1 , . . . , Cm })
an F-hyperedge and with H2 a new node. This mapping preserves ⊥-locality
for α2/6 since by Definition 9 it is ⊥-local, w.r.t. a signature S, exactly when
either B1 or R is not in S. The argument for >-locality follows that of α1 .
– Given α3 : B1 u . . . u Bn v ∃R.Bn+1 or α7 : B1 u . . . u Bn v> nR.Bn+1 we
map it to the hyperedges eB F1
α3/7 = ({B1 , B2 , . . . , Bn−1 , Bn }, {H3 }), eα3/7 =
({H3 }, {Bn+1 }), eF α3/7 = ({H3 }, {R}). This mapping preserves ⊥-locality for
2
α3/7 similarly to eB α1 for α1 . From Definition 9 we know that >-locality for
either of these axioms, w.r.t. a signature S, is dependent on neither R nor
Bn+1 being elements of S. Therefore, they are non >-local exactly when
either or both of these are in S. This is represented by the two edges eF 1
α3/7
F2
and eα3/7 for which H3 becomes F-connected exactly when either R or Bn+1
is F-connected.
– Given α4 : B1 u . . . u Bn v ∃R.Self and α5 : ∃R.Self v C1 t . . . t Cm we see
that ∃R.Self is both ⊥ or > local exactly when R 6∈ S. Therefore we map
α4 to the hyperedge eB α4 = ({R}, {C1 , . . . , Cm }), and α5 to the hyperedge
eF
α5 = ({B 1 , . . . , B n }, {R}).
– Given α8 : R1 ◦ . . . ◦ Rn v Rn+1 , we see that α8 is ⊥-local exactly when any
Ri 6∈ S, i ≤ n and is >-local exactly when Rn+1 6∈ S. We therefore map α8
to the hyperedge eB α8 = ({R1 , . . . , Rn }, {Rn+1 }).
– For α9 we have many forms, all variants of those discussed in the pre-
vious mappings. Therefore α9 is mapped to any of the following: eB α9 =
1
({R, B1 }, {H9 }}), eF α9
1
= ({H 9 }, {R}), e F2
α9 = ({H 9 }, {B}), or e 1
α9 = ({R, B 1 },
{R}), or eF α9
1
= ({R 1 }, {R 2 }), e F2
α9 = ({R 1 }, {B}), or e 1
α9 = ({R 1 }, {R 2 }).
Given a SROIQ ontology O in normal form we may now map every axiom
α ∈ O to its equivalent set of hyperedges. For each of these mappings there are
at most three hyperedges introduced, therefore mapping the whole ontology O
to an equivalent hypergraph HO will result in a hypergraph with the number of
edges at most linear in the number of axioms in O. It is easy to show that the
mapping process can be completed in linear time in the number of axioms in O.
We note that, similar to the normalization process, we may maintain a pos-
sibly many-to-many mapping from normalized axioms to their associated hy-
peredges. Formally, define a function deedge : HO → 2O , with O a SROIQ
ontology and HO its hypergraph.
S For brevity, we write deedge(Φ), with Φ a set
of hyperedges, to denote e∈Φ deedge(e).
10
Page 49 of 110
5 Hypergraph module extraction
In this section we show that, given a hypergraph HO for a SROIQ ontology O,
we may extract a frontier graph from HO which is a subset of a ⊥>∗ module. We
show that some of these modules guarantee safety, module coverage and module
independence. The hypergraph algorithms presented require one start node s
and a destination node t. In order to extend these algorithms to work with an
arbitrary signature S, we introduce a new node s with with an edge esi = (s, si )
for each si ∈ S ∪ >, as well as a new node t with an edge eti = (si , t) for each
si ∈ S ∪ ⊥.
Theorem 2. Let O be a SROIQ ontology and HO its associated hypergraph
B
and S a signature. Algorithm 1 - Bvisit extracts a set of B-hyperpaths HO
corresponding to the ⊥-locality module for S in O. Therefore, these modules also
guarantees safety, module coverage and module independence.
Theorem 3. Let O be a SROIQ ontology and HO its associated hypergraph
F
and S a signature. Algorithm 1 - F visit extracts a set of F -hyperpaths HO
corresponding to a subset of the >-locality module for S in O.
Theorem 4. Let O be a SROIQ ontology and HO its associated hypergraph
BF
and S a signature. Algorithm 2 extracts a frontier graph HO corresponding to
∗
a subset of the ⊥> -locality module for S in O.
The module extracted in Theorem 3 is a subset of the >-locality module
for a given seed signature. It is as yet unclear whether or not these modules
provide all the model-theoretic properties associated with >-locality modules.
However, from the previous work done for the DL EL+ [10], it is evident that
these modules preserve all entailments for a given seed signature S. Further, they
also preserve and contain all justifications for any given entailment. Similarly,
the exact module theoretic properties of modules associated with frontier graphs
is something we are currently looking into.
6 Conclusion
We have introduced a normal form for any SROIQ ontology, as well as the
necessary algorithms in order to map any SROIQ ontology to a syntactic local-
ity preserving hypergraph. This mapping process can be accomplished in linear
time in the number of axioms with at most a linear increase in the number of
hyperedges in the hypergraph.
Standard path searching algorithms for hypergraphs may now be used to find:
(1) sets of B-hyperpaths — this is equivalent to finding ⊥-syntactical locality
modules; (2) sets of F -hyperpaths — these are subsets of >-locality modules,
and (3) frontier graphs — these are subsets of ⊥>∗ modules. Whilst the modules
associated with B-hyperpaths share all the module theoretic properties of ⊥-
locality modules, it is unclear at this point which module-theoretic properties
modules associated with F -hyperpaths and frontier graphs possess.
11
Page 50 of 110
The ability to map SROIQ ontologies to hypergraphs, such that hyperedges
preserve syntactic locality conditions, allows us to investigate the relationship
between DL reasoning algorithms and the vast body of standard hypergraph
algorithms in greater depth.
Our primary focus for future research is to investigate and define the module-
theoretic properties of modules associated with F -hyperpaths and frontier graphs
as well as their relative performance with respect to existing locality methods.
Thereafter, we aim to expand our research and investigate other hypergraph
algorithms and how they may be applied to DL reasoning problems.
References
1. Cuenca Grau, B., Halaschek-Wiener, C., Kazakov, Y., Suntisrivaraporn, B.: Incre-
mental classification of description logic ontologies. Tech. rep. (2012)
2. Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Just the right amount:
extracting modules from ontologies. In: Williamson, C., Zurko, M. (eds.) Proceed-
ings of the 16th International Conference on World Wide Web (WWW ’07). pp.
717–726. ACM, New York, NY, USA (2007)
3. Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontolo-
gies: Theory and practice. Journal of Artificial Intelligence Research (JAIR) 31,
273–318 (2008)
4. Del Vescovo, C., Parsia, B., Sattler, U., Schneider, T.: The modular structure of an
ontology: atomic decomposition and module count. In: O. Kutz, T.S. (ed.) Proc.
of WoMO-11. Frontiers in AI and Appl., vol. 230, pp. 25–39. IOS Press (2011)
5. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistable SROIQ. In: Do-
herty, P., Mylopoulos, J., Welty, C. (eds.) Proceedings of the Tenth International
Conference on Princleples of Knowledge Representation and Reasoning. pp. 57–67.
AAAI Press (2006)
6. Jiménez-Ruiz, E., Cuenca Grau, B., Sattler, U., Schneider, T., Berlanga, R.: Safe
and economic re-use of ontologies: A logic-based methodology and tool support.
In: Proceedings of ESWC-08. vol. 5021 of LNCS, pp. 185–199 (2008)
7. Maier, F., Ma, Y., Hitzler, P.: Paraconsistent OWL and related logics. In: Janowicz,
K. (ed.) Semantic Web 2012. pp. 1–33. IOS Press (2012)
8. Nguyen, S., Pretolani, D., Markenzon, L.: On some path problems on oriented
hypergraphs. Theoretical Informatics and Applications 32(1-2-3), 1–20 (1998)
9. Nortjé, R.: Module extraction for inexpressive description logics. Master’s thesis,
University of South Africa (2011)
10. Nortjé, R., Britz, K., Meyer, T.: Bidirectional reachability-based modules. In: Pro-
ceedings of the 2011 International Workshop on Description Logics (DL2011).
CEUR Workshop Proceedings, CEUR-WS (2011), http://ceur-ws.org/
11. Suntisrivaraporn, B.: Polynomial-Time Reasoning Support for Design and Main-
tenance of Large-Scale Biomedical Ontologies. Ph.D. thesis, Technical University
of Dresden (2009)
12. Thakur, M., Tripathi, R.: Complexity of linear connectivity problems in directed
hypergraphs. Linear Connectivity Conference pp. 1–12 (2001)
12
Page 51 of 110
Two Case Studies of Ontology Validation
Doug Foxvog
University of Maryland Baltimore County, Baltimore, MD, USA
doug@foxvog.org
Abstract. As ontologies and ontology repositories have proliferated, the need
for a discipline of ontology validation and quality assurance has grown more
urgent. This report describes two case studies of ontology validation by con-
verting ontologies to a more powerful reasoning language and analyzing them
using logical queries. The lessons learned and directions for continuing work
are discussed.
Keywords: ontology, quality assurance, validation
1 Introduction
In computer science, an ontology is a formalization of the concepts of a specific field,
specifying the types (classes) of things that are dealt with in the field, relations that
may apply among instances of those classes, rules applying to instances of those clas-
ses, and possibly specific instances of those classes. It may define subsumption and
disjointness between classes or relations and may constrain the argument types of
relations. An ontology is not a definition of terms in a natural language, although
many ontologies provide mappings between the terms of the ontology and natural
language terms.
If an ontology accurately constrains the relations and classes of a model of the do-
main with restrictions that prevent assertions that could not be true in the modeled
domain and does so in a logically consistent manner, then it can be used to encode
valid information in the field, conclude additional information that is implied by the
stated information, and detect or block statements that are inconsistent with the do-
main model.
However, an ontology that does not accurately model the domain would allow log-
ically invalid statements to be asserted, prevent true statements from being made, or
both. An ontology may be incorrect not only due to some of its statements being
incorrect, but also due to missing assertions. An ontology that accurately encodes a
domain model and yet is logically invalid indicates that the model itself is invalid.
For these reasons, it is important to validate ontologies before use and whenever they
are modified. Not only can sets of logically inconsistent statements be identified, but
omission of argument constraints and class disjointness assertions can be flagged.
Page 52 of 110
Fig. 1. Class with three disjoint superclasses1
Our method does not cover ways to verify if an ontology corresponds to reality or
to an external model, but deals with design flaws and logical issues that could be ex-
amined with an inference engine. This paper presents the results of validating two
standard ontologies with strong user bases and communities (the Cell Line Ontology
and Plant Ontology described in Section 2) using this technique.
As the ontology language for the selected case studies lacks the reasoning capabili-
ties for logically detecting all the considered types of ontology flaws, we translated
the ontologies into a richer language (CycL [1]) in order to perform the analysis 2.
Some errors are flagged as the translated ontology is being input to the Cyc system,
while others can only be detected by asking the inference engine queries about the
ontology.
2 Source of Ontologies for Validation
The National Center for Biomedical Ontology maintains hundreds of ontologies for
the biomedical field with versions in several formats [2].
We selected as case studies two associated ontologies hosted by the NCBO: the
Cell Line Ontology and the Plant Ontology, downloading them in the OBO format
[3]. The 5 May 2009 version of the Cell Line Ontology [4] included thousands of cell
types including types of animal cells, plant cells, fungal cells, and prokaryotic cells.
1
http://bioportal.bioontology.org/ontologies/39927/?p=terms&conceptid=CL%3A0000522
2
Although CycL is formally an undecidable language, the queries used here (taxonomic, local
closed world, queries ranging over locally defined predicates, etc.) were not. The Cyc infer-
ence engine specifies whether lists of answers provided are known to be complete.
Page 53 of 110
The Plant Ontology [5] covers plant anatomy (including types of plant cells), mor-
phology, growth, and development. The Cell Line Ontology and Plant Ontology had
hundreds of pairs of plant cell concepts, with the same name and same or similar Eng-
lish definition, but different IDs.
Disjointness violations we detected in the Cell Line Ontology (see 3.1) suggested
that at least the one ontology had not been created with automated logical verification
of its statements. We decided to do a more complete analysis of the two ontologies to
determine if there were additional issues.
3 Cell Line Ontology
3.1 Introduction
In the Cell Line Ontology terms for several classes of cells, such as “epidermal cell,”
which are used by botanists and anatomists to refer to cells with similar functions in
both plants and animals, had been created with some plant cell subclasses and other
animal cell subclasses. However, at some point these terms were defined as sub-
classes of animal cell. Without disjointness constraints between plant and animal cell,
this situation was not detected when the statements were made. The term for “spore”
was similarly a subclass of three disjoint classes: “prokaryotic cell,” “plant cell,” and
“fungal cell” (Fig. 1) and “zygote” was a subclass of “animal cell” and “plant cell.”
These disjointness issues, which were detected by Cyc when we attempted to add
disjointness assertions to a translated version of the 2009 Cell Line Ontology, were
corrected with the separation of plant cell types from the Cell Line Ontology in De-
cember 2011 [6].
3.2 Analysis
For a more complete analysis, we downloaded an updated (13/1/2012 09:59) version
of the Cell Line Ontology. This version had obsoleted all plant cell types, referring
the user to the Plant Ontology for such terms, and distinguished prokaryotic spores
from fungal spores. The ontology defines 1928 non-obsoleted cell types, 29 binary
predicates, and 32 (new) disjointness assertions among cell types.
A collection of terms from other ontologies (including PR for protein, UBERON -
cross-species anatomy, NCBI - biological taxa, ChEBI - chemical entities, PATO-
phenotypic qualities) are also included to be specified as arguments to relations re-
stricting the cell type definitions. 4233 such assertions are included in the ontology.
To perform an analysis, the ontology was converted to CycL, loaded into Open-
Cyc [7], and then queries were asked using the OpenCyc interface.
Formal criteria Analysis of the logical constraints for the Cell Line Ontology
showed that the cell types were arranged in a directed acyclic graph rooted on a term
for “cell” and that there were no shared subclasses of any of the defined disjoint pairs
Page 54 of 110
(Table 1, column 1). Cyc was not needed for such a determination – OWL reasoners
can detect intersections of disjoint classes.
Table 1. Queries of Cell Line Ontology
Disjoint classes that have Cell types that develop from Eukaryotic cell types that de-
a common subclass Eukaryotic cells, but are not velop from cell types not
known to be Eukaryotic known to be Eukaryotic
(and (and (and
(ist-Asserted3 (allRelationExists (allRelationExists
CL_Mt ?C1 ?C1
(disjointWith CL_developsFrom CL_developsFrom
?C1 ?C2)) ?C2) ?C2)
(genls ?C0 ?C1) (genls ?C2 (genls ?C1
(genls ?C0 ?C2)) EukayoticCell) EukayoticCell)
(unknownSentence (unknownSentence
(genls ?C1 (genls ?C2
EukayoticCell))) EukayoticCell)))
Answers: 0 Answers: 19 Answers: 22
Informal Criteria – Completeness. Nine of the 29 binary relations had argument
restrictions defined, all of which were to the PATO Ontology’s term for “Quality”
(PATO:00000001). Five of these relations were defined as transitive, two of them
having an identical domain and range defined, and the rest having neither. These
relations were only used in expressing intersection with a property [See Table 2], and
in all cases the classes were consistent with the argument restrictions. The lack of
argument restrictions on most relations is a significant incompleteness.
One of the properties defined for many cell types is that they develop from other
cell types. Logically, cells that develop from types of EukayoticCell4 (or Pro-
karyotic_Cell or Animal_Cell) should themselves be types of Eu-
kayoticCell (or Prokaryotic_Cell or Animal_Cell). The inference en-
gine finds 19 violations of this principle. Similarly, if a subtype of one of these gen-
eral classes of cells is known to develop from another type, it is quite possible that the
second type is also a subtype of the general class. The inference engine finds 22 cases
in which the cell type from which a eukaryotic cell type develops is not known to be a
eukaryotic cell type. Table 1 (columns 2 and 3) provides the queries asked of the
inference engine, their English translations, and the number of answers.
3
The CycL relation ist-Asserted relates a specified context to a specific statement
made in it; the relation genls is the CycL subclass relation; allRelationExists
means that for every instance of a class (first argument) the specified relation (second
arg.) relates it to some instance of another class (third arg.); unknownSentence
means that the statement that is its only argument is neither stated nor derivable
through taxonomic reasoning. Variables in CycL are prefixed by a question mark (“?”).
The relation ist-Asserted can not be expressed in FOL.
4
The Cell Ontology uses IDs such as CL:0000003. For clarity, we use the phrase provided
by the name field to specify each term.
Page 55 of 110
Table 2. Germ line stem cell defined as intersection of germ-line cell and being capable of stem
cell division (OWL format)
:CL_0000014 rdf:type owl:Class ;
owl:equivalentClass
[ rdf:type owl:Class ;
owl:intersectionOf
( :CL_0000039
[ rdf:type owl:Restriction ;
owl:onProperty : capable_of ;
owl:someValuesFrom GO:0017145
]
)
] .
Only 32 disjointness assertions are defined, all of which apply to types of white
blood cells and blood progenitor cells. Cell types near the top of the hierarchy include
cell types by number of nuclei (none, some, one, greater than one) and cell types by
organism type (prokaryotic, eukaryotic, animal, and fungal — plant cells having been
removed from the ontology), which strongly indicated missing partitions and disjoint-
ness assertions (Fig. 2).
Fig. 2. Top Layers of Cell Ontology hierarchy, from
http://proto.informatics.jax.org/prototypes/GOgraphEX/CL_Graphs/CL_0000003.svg
Informal Criteria – Abstraction Level. A brief analysis of the very top levels of the
hierarchy showed that sets of classes were being treated as normal classes, with their
members being labeled as subclasses. The initial partition (as described by textual
descriptions) is Cell_in_Vitro vs. Cell_in_Vivo (renamed Native_Cell)
with almost every other cell type a subclass of Cell_in_Vivo.
An ontologist might prefer to make this distinction orthogonal to other distinctions
(since in vitro cells might reasonably be considered to be muscle/nerve/etc. cells, and
Page 56 of 110
to have a nucleus or not even though they are not in a body). Cell_in_Vivo has
the subclasses Cell_by_Organism and Cell_by_Class. Cell_by_Class
has the subclasses Cell_by_Nuclear_Number, Cell_by_Ploidy, Cell_
by_Lineage, Cell_by_Histology, Cell_by_Function, and Nontermi-
nally_Differentiated_Cell. The textual descriptions of each of the
“Cell_by_X” classes start with “a classification of cells by …,” making it clear that
each are intended to be sets of classes, i.e. metaclasses, since their descriptions are not
generally applicable to the various subclasses of those cell types that are defined as
their direct subclasses. The definitions of these classes are meaningless with respect
to the individual cells that are supposed to be their instances [8].
Some of these sets of cell types seem to naturally be disjoint sets. Under
Cell_by_Organism there is Prokaryotic_Cell and Eukaryotic_Cell
and under Eukaryotic_Cell there is Animal_Cell, Fungal_Cell, and My-
cetozoan_Cell (Plant_Cell has been obsoleted), all of which are cells distin-
guished by the type of organism of which they are a part. Since every organism is
either a prokaryote or a eukaryote, the first division is a partition on Cell although it
has not been so declared in the ontology. The three directly specified subclasses of
Eukaryotic Cell are all disjoint, but this is not stated in the ontology; these
subclasses do not cover all eukaryotic cells, so it is not a partition.
A similar analysis covers Cell_by_Nuclear_Number and Cell_by_
Ploidy, each of which has instances (although defined as subclasses) that partition
Cell. These instances each have very few subclasses even though most cell types
fall under the definition of an instance of each of these metaclasses.
Table 3. Cell Line Ontology Property Issues
Cell types defined as the Cell types defined as the Cell types that have a property
intersection of another cell intersection of a metatype and are not stated as being a
type and having some prop- and having some property subclass of the intersection of a
erty superclass with the property
(and (and (and
(isIntersectionOf (isIntersectionOf (isIntersectionOf
?C ?C1 ?PRED ?V) ?CT ?MCT ?PRED ?C1 ?C0 ?PRED ?V)
(isa ?C1 CellType) ?VALUE) (genls ?C2 ?C0)
(isa ?C CellType)) (genls ?MCT (allRelationExists
CellType) ?C2 ?PRED ?V)
(genls ?CT Cell)) (unknownSentence
(genls ?C2 ?C1)))
Answers: 547 Answers: 10 Answers: 10
Formal criteria – Internal Consistency. Over 4200 cell types in the ontology are
defined as having some property (e.g., haploid, mononucleate, etc.). Over 500 cell
types are defined as being the intersection of a more general cell type and having a
specific property. Ten of the cell types which end up being instances of one of the
metaclasses are also defined as being an intersection of a metaclass and having one of
Page 57 of 110
these properties. However, in the Cell Line Ontology, the more specific cell types
specified as having a property are not always (through the subclass hierarchy) de-
clared to be subclasses of the class which is an intersection of that property and one of
their superclasses. Although many reasoners (including OWL reasoners) can derive
the subclass relationship, BioPortal’s browser for the Cell Type Ontology at the time
of the ontology release did not conclude them.
A query by the inference engine yielded ten such missing subclass relationships,
which makes the ontology internally inconsistent for insufficiently powerful systems
such as the BioPortal ontology browser of January 2011. Table 3 provides queries
asked of the inference engine, their English translations, and the number of answers.
3.3 Resolution
We converted the metaclasses at the top of the ontology to actual metaclasses, con-
verting the subclass assertions of their instances to instantiation assertions. This
meant that those classes which had their subclassOf relationships removed needed
to have new subclassOf relationships asserted if no others existed. Subclass as-
sertions were made from the instances of these metaclasses to Cell, not to Na-
tive_Cell. Prokaryotic_Cell was made a subtype of Anucleate_Cell
and Nucleate_Cell was made a subclass of Eukaryotic_Cell. Other sub-
class assertions are needed at this level; for example, a number of the (now) instances
of Cell_Type_by_Function should be declared to be subclasses of Ani-
mal_Cell or Eukaryotic_Cell, but such work is the responsibility of a devel-
oper or subject matter expert.
Defined subclasses of these now direct instances of the metaclasses were examined
to determine whether they should also be instances of the metaclass and were so as-
serted only if judged appropriate. For example, Cell_By_Nuclear_Number had
Mononucleate_Cell, Binucleate_Cell, and Multinucleate_Cell
added as instances while remaining as subclasses of Nucleate_Cell.
Other former direct subclasses were examined to determine whether they should be
subclasses of direct instances of the metaclass, and not instances themselves. For
example, Cell_by_Nuclear_Number had its instances restricted to Anucle-
ate_Cell, Nucleate_Cell, Mononucleate_Cell, and Multinucleate
Cell, with its other former direct subclasses (Mononuclear_Osteoclast,
Multinuclear_Osteoclast, …) being asserted as subclasses of the appropriate
direct instance as indicated by their comments.
Disjointness statements were made for the instances of the newly restructured met-
aclasses, Cell_by_Organism, Cell_by_Nuclear_Number, and Cell_by_
Ploidy. Cell_by_Organism was made a subclass of Cell_by_Class.
We added rules to the CycL version of the ontology conclude subclass relation-
ships:
A rule was added so that cell types that are defined as developing from eukaryotic
or animal cell types are concluded to also be subclasses of Eukaryotic_Cell
Page 58 of 110
or Animal_Cell, respectively. This resulted in 26 subclass assertions being de-
rived.
A rule was added so that if one class is defined as an intersection of a class and a
property, subclasses of that class that have that property are concluded to be sub-
classes of the intersection class. This resulted in a further ten subclass assertions
being derived.
A rule was added so that if one class is defined as an intersection of a metaclass
and a property, other classes with that property are concluded to be subclasses of
the direct instance of the metaclass. The intersection assertion was changed to be-
ing an intersection of Cell and the property. This resulted in nine subclass asser-
tions being derived.
The Cell Ontology obsoleted the metaclasses in March 2012 [8]. A more recent
OBO Library browser does conclude subclass relationships derived from intersection
definitions.
Other detected problems still need to be resolved. Such work is not the responsi-
bility of a validator, but of a developer or subject matter expert. We recommend that
Cell Line Ontology developers:
Define subclasses of Mononucleate_Cell and other instances of Cell_by
Nuclear_Number so that every cell type that has a restricted nuclear number is
defined as such by the subclass hierarchy.
Define subclasses of Diploid_Cell and other instances of Cell_by_Ploidy
so that every cell type that has a restricted ploidy is defined as such by the subclass
hierarchy.
Define those instances of Cell_by_Function which of necessity are sub-
classes of Animal_Cell or Eukaryotic_Cell as being so. For those in-
stances which are not so restricted, check their direct subclasses to determine
whether they should be subclasses of Animal_Cell or Eukaryotic_Cell.
In cases in which a subclass of Eukaryotic_Cell (or Animal_Cell) is
declared to develop from a cell type that is not such a subclass, the second class
should be examined to determine whether it should be a subclass of Animal_
Cell or Eukaryotic_Cell.
Add many more disjointness assertions among sibling classes, as appropriate.
Define appropriate argument restrictions on the predicates in the ontology.
4 Plant Ontology
4.1 Introduction
The 2 April 2012 version of the Plant Ontology contains 1593 terms, 1181 of which
are types of plant anatomical entity, 272 of which are types of plant structure devel-
opmental stage, eight of which are binary relations, and 132 of which are obsoleted.
37 disjointness assertions among cell types are included. The Plant Ontology includes
Page 59 of 110
64 assertions specifying that one class is an intersection of another class with having a
specific property.
The intersection assertions are accepted as a way of stating subclass relationships
that are to be concluded instead of directly stated. This was done in order to avoid
directly stating “dual parentage” in the ontology [5, p. 4].
4.2 Analysis
To analyze the ontology, it was converted to CycL, loaded into OpenCyc, and queries
were asked using the OpenCyc interface.
Formal criteria – Logical constraints. Analysis of the logical constraints for the
Plant Ontology showed that the classes were arranged in two directed acyclic graphs
rooted on terms for “plant anatomical entity” and “plant structure development stage,”
and that there were no shared subclasses of any of the defined disjoint pairs. There
was no violation of logical constraints.
Formal criteria – Internal Consistency. Over 800 classes in the ontology are de-
fined as having some property. 64 of the classes are defined as being an intersection
of a more general class and having one of these properties. By querying the inference
engine, we found that in 63 cases, the more specific classes are not (directly or indi-
rectly) defined as subclasses of the class-property intersection. Two examples of this
are types of plant cell that have the property of being part of a plant embryo, but are
not known to be subclasses of EmbryonicPlantCell. For systems with limited
reasoning capabilities, these are violations of internal consistency.
Table 3 provides the queries asked of the inference engine, their English transla-
tions, and the number of answers.
Table 2. Plant Ontology Property Issues
Classes which are defined to have some property Plant cell types that are part of plant em-
that are not defined to be subclasses of the inter- bryos, but are not known to be embryonic
section of a superclass with that property plant cells
(and (and
(isIntersectionOf (allRelationExists ?P1
?P1 ?P0 ?PRED ?V) PO_part_of PlantEmbryo)
(allRelationExists ?P2 ?PRED ?V) (genls ?P1 PlantCell)
(genls ?P2 ?P0) (unknownSentence
(unknownSentence (genls ?P1
(genls ?P2 ?P1))) EmbryonicPlantCell)))
Answers: 63 Answers: 2
Informal Criteria – Completeness. Disjointness assertions were missing from the
developmental stage hierarchy and from near the top of the anatomical hierarchy.
None of the binary relations had argument restrictions defined. Three of these rela-
tions were defined as transitive; none as symmetric or reflexive. Only 37 disjointness
assertions are present, all of which are well down in the cell type hierarchy. There are
Page 60 of 110
significant gaps in the ontology in both argument type restrictions and disjointness
assertions.
Informal Criteria – Abstraction Level. Unlike the Cell Line Ontology, the Plant
Ontology had no metaclasses near the top of the hierarchy that were used as sub-
classes.
4.3 Resolution
We added a rule to conclude subclass relationships:
A rule was added so that if one class is defined as an intersection of a class and a
property, subclasses of that class that have that property are concluded to be sub-
classes of the intersection class. This resulted in 63 assertions being derived.
A more recent Plant Ontology browser does conclude subclass relationships derived
from intersection definitions. Much is still missing, e.g., disjointness assertions and
argument type restrictions. Such work is not the responsibility of a validator, but of a
developer or subject matter expert.
We recommend that Plant Ontology developers:
Specify disjointness among sibling classes as appropriate.
Define appropriate argument restrictions on the predicates in the ontology.
Review comments which state that a class has a certain property, and encode those
that are valid and are not already encoded or derivable from properties of super-
classes.
5 Lessons Learned and Conclusion
We analyzed two ontologies that have strong user bases and communities for ensuring
their validity. Significant problems were discovered with each ontology as a result of
verification queries.
We note that public ontologies are not static. Early problems in the class hierarchy
of the Cell Line Ontology, discovered when making high-level disjointness assertions
(e.g., plant vs. animal cell) flagged common subclasses, were corrected before our in-
depth analysis and the Plant Ontology was disconnected from the Cell Type Ontology
in December of 2011. The in-depth analyses of the two ontologies discovered no re-
maining disjointness problems. Only a domain expert can determine whether this is
due to the validity of the current subclass hierarchy or the sparseness of disjointness
assertions.
One of the two ontologies erroneously treated metaclasses as normal subclasses of
the root term. This led to numerous missing subclass assertions (evidently because
the subclass does not fit the definition of the metaclass). These metaclasses have since
been obsoleted. They could be reinstated as metaclasses if they are recognized as
such.
Page 61 of 110
The omission of argument restrictions can be readily determined. The lack of dis-
jointness assertions among sibling classes can also be readily determined, but a sub-
ject matter expert should determine whether such sibling classes are actually disjoint.
Both ontologies had statements that instances of certain classes had certain proper-
ties, and that other classes were the intersection of superclasses with having some
property. Such statements were initially not executable rules in the provided ontology
viewer, so that in both cases subclass assertions that could be concluded based on
these rules were missing. These examples emphasize that ontology evaluation needs
to cover more than just whether the statements in an ontology lead to a logical contra-
diction.
When an ontology includes statements that could be mapped to rules from which
subclass relationships or disjointness between classes can be concluded, an ontology
evaluation step in a sufficiently rich semantic language can draw such conclusions
and check if the conclusions are entailed by the encoded subclass and disjointness
statements. If they are not already present, the concluded statements can then be add-
ed to the ontology.
The presence of metaclasses erroneously defined as normal classes in a subsump-
tion hierarchy cannot be concluded from automatic analysis of the statements in an
ontology. Such problems may be more likely to occur near the root of a subclass
hierarchy and can be manually detected by reading the descriptions of the terms.
Such situations can be resolved by determining which of the defined subclasses of the
metaclass are normal classes and which are metaclasses, converting the normal clas-
ses to be instances instead of subclasses of the metaclass, and adding disjointness
assertions, as appropriate, among them.
It is noteworthy that the problems found in these case studies consisted of system-
atic repetition of narrow categories of errors, rather than many different errors. If one
were to evaluate the ontologies using a checklist of validity criteria or common errors,
they would have gotten few black marks; yet a large proportion of their concepts was
affected. If it can be shown that this pattern is typical, an ontology validation and
correction strategy could be optimized accordingly.
Although a discipline of ontology validation and quality assurance is still evolving,
our experiences so far have been positive and instructive. Potential future work in-
cludes the creation of an updated, comprehensive reference to ontology validity crite-
ria, informed by a survey of previous case studies and the performance of additional
new case studies.
Acknowledgement
This work was funded under NSF award #0934364 to the University of Maryland,
Collaborative Research Establishing a Center for Hybrid Multicore Productivity Re-
search..
Page 62 of 110
References
1. Matuszek, C., Cabral, J., Witbrock, M., DeOliveira, J.: An Introduction to the Syntax and
Content of Cyc. In Proceedings of the 2006 AAAI Spring Symposium on Formalizing and
Compiling Background Knowledge and Its Applications to Knowledge Representation and
Question Answering, Stanford, CA, (2006).
2. OBO Download Matrix, http://www.berkeleybop.org/ontologies .
3. The OBO Flat File Format Specification, version 1.2, http://www.geneontology.org/
GO.format.obo-1_2.shtml .
4. Cell Line Ontology version 1.0, May 2009, http://bioportal.bioontology.org/ontologies/
39927/.
5. L. D. Cooper et al., “The Plant Ontology: Development of a Reference Ontology for all
Plants,” http://icbo.buffalo.edu/F2011/slides/AnatomyWorkshop/ FAOI2011.08.Cooper.
pptx, 2011.
6. Mungall, C.: Cell Ontology 2012-12-13[STET – typo in year] release,
http://sourceforge.net/mailarchive/message.php?msg_id=28544354 , December 15 2011.
7. OpenCyc, http://www.opencyc.org/, 2012.
8. Delete meaningless upper level terms, Cell-Ontology Issues Wiki, http://code.google.com/
p/cell-ontology/issues/detail?id=1 .
Page 63 of 110
Short Paper: Non-Taxonomic Concept Addition
to Ontologies
Artemis Parvizi, Chris Huyck, and Roman Belavkin
Middlesex University
The Borough
London NW4 4RL
Abstract. Concept addition, an ontology evolution’s edit operation,
includes adding taxonomic (hierarchical structure) and non-taxonomic
(concept properties) relations. Generating concept properties requires in-
formation extraction from various sources, such as WordNet. Other than
semantic similarities generated by WordNet, self-information generated
from existing non-taxonomic relations has aided non-taxonomic relation
addition to ontologies. Evaluation is based on using an ontology as gold
standard and detaching and reattaching the nodes. Non-taxonomic re-
lation generation without accessing an enormous amount of information
has proven to be quite difficult; the results displayed in this work are an
indication of this difficulty.
Keywords: Ontology Evolution, Ontology Learning, Non-Taxonomic
Relations, Concept Addition
1 Introduction
Ontology is commonly defined as a formal, explicit specification of a shared
conceptualisation [14], and often has been used for modelling concepts of the
world. Due to the experts’ limitations of producing a complete image of the
world with flexible boundaries for a domain, change is inevitable. Change in
ontologies has some common causes [29]: change in the domain, change in the
shared conceptualisation, or change in the specification. Ontology update has
been a subject of debate for many years, and many methods have been proposed
to address it. Ontology evolution and ontology learning are among these pro-
posed methods. Ontology evolution is “the timely adaptation of an ontology to
the arisen changes and the consistent propagation of these changes to dependent
artefacts” [39], such as systems defined in [5, 30, 22, 40, 13, 4, 42, 19, 21]; ontology
learning involves changing an ontology automatically or semi-automatically by
consulting some structured data sources, such as databases; semi-structured data
sources, such as WordNet, or Cyc; or some unstructured data sources, such as
text documents and web pages [10]. A few examples of ontology learning systems
can be found in [20, 9, 36, 27, 11, 41, 33].
Changing an ontology involves both changing the concepts and the relations.
Ontology relations have been divided into two categories: taxonomic relations
Page 64 of 110
2 The Eighth Australasian Ontology Workshop
such as subClassOf and disjointWith in OWL [2], and non-taxonomic rela-
tions which covers most of the other OWL relations. On one hand, taxonomic
relations provide a structure to ontologies and are crucial. On the other hand,
non-taxonomic relations by presenting meaning add depth to the ontology. Re-
gardless of using the term ontology evolution or ontology learning, commonly,
ontology update involves changing both taxonomic and non-taxonomic relations.
A fundamental design operation for having a successful ontology evolution
application includes concept addition [24, 15]. To address concept addition, two
approaches (Approach I (see Section 4.1) and Approach II (see Section 4.2))
have been introduced in which ontology graphs (see Section 2) and semantic
similarity (see Section 3) have been employed.
2 Ontology Graph
The definition of an ontology in this paper is a set C of concepts and a set of
relations R1 , . . . , Rn , Ri ⊂ C × C. Since multiple relations with different labels
are allowed to exist in ontologies, labelled graphs also known as multigraphs
(G = (V, E1 , . . . , En )) with the set of vertices V ⇐⇒ C and a set of edges
Ei ⇐⇒ Ri are a logical choice of representing them. A graph with the stated
characteristics is called an ontology graph and is able to cover all important
structural OWL ontology features including individuals, classes, relations, ob-
ject properties, datatype properties, and restrictions [23]. The notion of ontology
graph in this work is an extended version represented in [26, 16, 34, 17, 3, 25];
vertices represent concepts, individuals, restrictions, and values, and edges, in-
clude taxonomic OWL relations, such as subClassOf and disjointWith, and
non-taxonomic relations.
3 Semantic Similarity
A successful ontology change application must be able to detect what needs
to be changed, gather sufficient information about the element that needs to
be changed, and finally decide how to implement change. Extracting relevant
and sufficient information is crucial. In this work, WordNet [38] and Wikipedia
as general purpose semi-structured data sources are consulted; they both are
capable of generating semantic similarity distances between concepts. Semantic
similarity between two or more concepts refers to the level of closeness that their
meanings possess, and it is very difficult to acquire. It is common practice to use
ontologies for computing the distance between two concepts and normalising the
final result. In RiTa WordNet [18], the minimum distance between any two senses
for the two words in the WordNet tree is returned and the result is normalised;
if there is a similarity a number is retuned, and 1 if no similarity is found.
This work has generated semantic similarities from Wikipedia as well. Al-
though many have mentioned that Wikipedia is much richer and a far better
source [35, 7, 32, 37], the result acquired from Wikipedia were not as promis-
ing as WordNet. Often semantic Wikipedia APIs only consult the infoboxes for
Page 65 of 110
Non-Taxonomic Concept Addition to Ontologies 3
generating semantic similarity; lack of word sense when extracting concepts is
identified as another shortcoming [37].
4 Methodology
Ontology development is highly dependent on ontology experts, and domain
experts. The perception of an expert about a correct or an incorrect relation
may differ from another expert. This issue has contributed to the complexity of
ontology development and update. Nonetheless, this work proposes that when
adding a non-taxonomic relation, provided that the consistency of the ontol-
ogy holds and the ontological statement is semantically correct, the new state-
ment is as welcomed as any existing statement. For example when given the
three concepts Student, Library, and Group, and the relation memberOf, an
expert might generate Student memberOf some Library, Student memberOf
some Group, or both. Absence of either of these two statements will not make
the ontology incorrect but in certain circumstances it can be claimed that the
ontology is less accurate. The same justification holds when a system is auto-
matically generating non-taxonomic statements.
Commonly when generating non-taxonomic statements, a common approach
is to provide a set of possible properties for each concept, rank them accord-
ing to their frequencies, and finally according to some criteria select the highly
probably one. However, this work does not intend to generate new properties for
concept, but to assign an existing property to an input concept. Non-taxonomic
relations can be classified into two general groups: object properties (intrinsic
and extrinsic), and data-type properties [28]. The aim of this work is to gener-
ate intrinsic properties for a new input concept based on the existing intrinsic
properties. The hypothesis is that siblings of a vertex in an ontology graph often
have the same intrinsic properties assigned to different concepts.
In this work, the complete set of possible answers (Ans list) is generated,
and the existing statements in the ontology (Cur list) are extracted. Ans list is
a combination of an input concept I, the set of vertices V = V1 , V2 , . . . , Vn , the
set of edges E = E1 , E2 , . . . , En , and the set of restrictions. Note that in this
work only the two restrictions some and only are considered. Sample statements
for the following approaches are as follows:
Existing Statement: V1 E1 some V2
Generated Statement: I E1 some V3
4.1 Approach I
The members of list Ans for an input concept I, m vertices, the two restrictions,
and n edges will be 4 × m × n which comparative to list Cur are numerous.
This approach consists of a number of filters to prune Ans list according to Cur
list with the aid of various semantic similarities. To be able to apply semantic
similarities, a random entropy or self-information approach has been selected.
Page 66 of 110
4 The Eighth Australasian Ontology Workshop
Probability of the event of randomly connecting a to b by an Ri relation is defined
by P (e) = P ((a, b) ∈ Ri ). The prior probability therefore being P (e) = k1 , where
k is the number of possible links (a, b) ∈ Ri . Given some semantic similarity
distances (see Section 3) s(a, b) ∈ [0, 1], the posterior probability of a connection
assuming a dependency between e and s(a, b) is:
P (e | s(a, b)) 6= P (e)
Since s(a, b) is a similarity distance (taking values in [0, 1] with 0 correspond-
ing to the most similar), it can be assumed that the posterior probability of
connection monotonically depends (∝) on 1 − s(a, b):
P (e | s(a, b)) ∝ 1 − s(a, b)
The monotonicity for two events e1 = (a, b) and e2 = (a, c) means the following:
s(a, b) ≥ s(a, c) ⇐⇒ 1 − s(a, b) ≤ 1 − s(a, c)
=⇒ P (e1 | s(a, b)) ≤ P (e2 | s(a, c))
The probability can be used to compute self-information as follows [6]:
h(a, b) = − log(P (e | s(a, b)))
≈ − log(1 − s(a, b))) (1)
The first filter is called hierarchy filtering; it is based on the patterns of the
siblings of the input concept. A sibling is referred to a concept with a disjoint-
With relation. This work focuses on non-taxonomic patterns. For the input con-
cept I, assuming that one of the statements in Ans is IE1 onlyV1 , the patterns
would be IE1 only and E1 onlyV1 . This approach only makes use of the forward
patterns which in this example is E1 onlyV1 . Any member of the Ans list which
does not contain the same pattern as one of the members of Cur list will be ex-
cluded from Ans. Also, if the input concept I and the first concept of a member
of Cur list do not have the same parent, the statement will be excluded from
Ans. Presuming both the pattern and the parent is matched, when the success
rate of comparing the generated statement with all the members of Cur list is
more than 50%, the statement will still remain in Ans, otherwise dropped. At
this stage, only the statements with the patterns similar to the existing non-
taxonomic statements remain.
From this point onwards, Equation 1 will aid the pruning process. For the
second filter Q1 = h(I, E1 ), Q2 = h(V3 , E1 ), Q3 = h(V2 , E1 ), and Q4 = h(V1 , E1 )
are generated. The goal of this filter is to investigate Q1 + Q2 ≤ Q3 + Q4 ∈ [0.1];
if in more than half the occurrences this function holds, then the generated
statement will be accepted; otherwise rejected. The aim is for the self-information
of the generated statement to be less than or equal to the self-information of the
current statements.
For the third filter Q5 = h(I, V1 ) and Q6 = h(V2 , V3 ) are calculated. This
filter will examine that in more than half the occurrences Q5 ≤ Q6 ∈ [0, 1] holds.
Page 67 of 110
Non-Taxonomic Concept Addition to Ontologies 5
The forth filter will generate Q7 = h(I, V2 ) and Q8 = h(V1 , V3 ); the relation
Q7 ≤ Q8 ∈ [0, 1] must hold in more than half the occurrences for the generated
statement to be accepted.
The last filter will generate the self-information among all the members of
the generated and the current statement:
Qi = h(Statement f rom Ans list, Statement f rom Cur list)
The result generated by Qi are sorted and the k most similar statements
selected. Tables 1 and 2 display the results when k = 2.
4.2 Approach II
The members of the Ans list have to be pruned according to the members of Cur
list. A comparison between all the members of both lists is made. Providing that
a statement from one of lists has the same relation and restriction (for example
EK Some or EK Only) as the other list, the occurring pattern and its frequency
is recorded. The list containing the patterns P at will be sorted ascending with
regard to the frequencies, and the top half selected. Those statements in Ans
which do not contain these patterns will be omitted from the final answer pool.
The statement V1 E1 some V2 contains two patterns; (1) E1 some V2 and (2) V1
E1 some.
The aim of this step is to prune Ans list according to the patterns in Cur
list; there is a trade off to this filter, some semantically correct statements will
not be validated due to the low or lack of frequencies.
Hierarchy filtering as discussed in approach (I) will filter the remaining mem-
bers of the Ans list. When the siblings of the input concept contain a non-
taxonomic relation which have occurred in more than 50% of the cases and
this taxonomic relation is among the remaining members of the Ans list, this
statement will be accepted, otherwise rejected from Ans list.
4.3 Transitive Reduction
Both of the introduced approaches have the potential of producing transitive
relations, which from the consistency point of view have to be eliminated. Inher-
itance through the hierarchy has to be modelled in an ontology graph. Transitive
reduction on directed graphs is the answer to this problem. Presuming there is
the possibility of representing information in the directed graph G with fewer
arcs than the current amount, then that is the solution [1]. Graph G0 will be the
transitive reduction of G if it satisfies the following conditions:
1. A direct path between v and u in G0 exists, if a direct path between v and
u in G exists.
2. There is no graph with fewer arcs than G0 satisfying the above condition.
Page 68 of 110
6 The Eighth Australasian Ontology Workshop
For approach (II), since all the remaining members of the Ans list are se-
lected, transitive reduction is applied after the last step. However, approach (I)
is more complicated due to selecting the top k generated relations. Transitive
reduction can be applied before or after the top k selection, which this work
has adopted the latter. Regardless of the approach, in situations in which a
child inherits a property and the algorithm identifies this transitive property,
the property is dropped.
4.4 Evaluation
This work has adopted an evaluation mechanism based on precision and recall
measurements [8, 12]. The strategy is to select a well-structured ontology and
after converting it into an ontology graph, detach the vertices one by one; the
system will attempt to reattach the vertex to the graph optimally with the
original relations and at the original location [31]. A comparison between the
number of removed edges in the original ontology graph (O) and the modified
graph (O0 ) is made. Assuming concepts c1 and c2 and relation Rk are present
in O0 , the hypothesis is to examine O and determine whether c1 and c2 are
related by Rk or not. Accepting the hypothesis indicates that O contains an
edge corresponding to c1 Rk c2 ; rejecting is when there is no such edge in O. The
overall count of correct edges in O0 relative to the numbers of all edges in O0
or O respectively will produce precision and recall. F-measure is a more just
measurement since precision and recall are distributed evenly.
|E ∩ E 0 | |E ∩ E 0 |
P (E 0 , E) = R(E 0 , E) =
|E 0 | |E|
P (E 0 , E)R(E 0 , E)
F (E 0 , E) = 2 ×
P (E 0 , E) + R(E 0 , E)
Other than studying the effect of a single concept addition, the effect of
adding a sequence of concepts also has to be studied. The order in which concepts
a and b are added to the system has an effect on the non-taxonomic relations
generated; generally, the semantic richness of the ontology is affected by the
existing concepts and relations. This work has studied the effect of adding two
(p = 2) and ten (p = 10) concepts to the ontology graph. Due to all the input
concepts being known, the average of all the possible orders have been displayed.
Approaches (I) clearly has better results than approaches (II) excluding one
exception. The more frequent a pattern, the higher the probability of it being
selected; also, the closer the pattern in the hierarchy, the greater the likelihood
of it being the final answer. The major difference between the two approaches
other than the F-measure is in the number of statements being selected as the
final answer. In the approach (I), the number of statements selected has a limit;
as a result, fewer unmatched statements are selected. However, approach (II)
has no limit on the number of generated statement, but at the same time more
unmatched statements are in the final answer pool. The reason this paper is
using the expression unmatched instead of incorrect is that studying the final
Page 69 of 110
Non-Taxonomic Concept Addition to Ontologies 7
Table 1. The experimental results of non-taxonomic learning for approach (I). The
results are displayed in percentage.
p=1 p=2 p=10
Precision Recall F-measure Precision Recall F-measure Precision Recall F-measure
Pizza 0 0 unknown 0 0 unknown 0 0 unknown
Travel 25.0 50.0 33.33 25.0 50.0 33.33 25.0 50.0 33.33
Amino Acid 31.11 11.20 16.47 31.11 11.20 16.47 33.33 12.00 17.64
Career 20.00 26.66 22.85 20.00 26.66 22.85 15.00 20.00 17.14
Human and Pets 16.66 17.39 17.02 16.66 17.39 17.02 14.28 16.66 15.38
Movie 23.52 11.32 15.28 20.00 9.43 12.82 17.5 7.27 10.29
OBOE 0 0 unknown 0 0 unknown 0 0 unknown
University 19.56 14.51 16.66 19.56 14.51 16.66 11.36 8.06 9.43
Vehicle 14.28 18.18 16.0 14.28 18.18 16.0 23.07 27.27 25.0
Table 2. The experimental results of non-taxonomic learning for approach (II). The
results are displayed in percentage.
p=1 p=2 p=10
Precision Recall F-measure Precision Recall F-measure Precision Recall F-measure
Pizza 18.76 71.71 29.69 18.76 71.71 29.69 15.84 52.25 24.31
Travel 46.15 42.85 44.44 46.15 42.85 44.44 56.25 32.14 40.90
Amino Acid 52.50 63.00 57. 27 52.50 63.00 57. 27 59.42 41.0 48.52
Career 50 50 50 50 50 50 37.5 25.0 30.00
Human and Pets 52.77 39.58 45.23 52.77 39.58 45.23 57.57 39.58 46.91
Movie 45.16 70.0 54.90 48.83 70 57.53 49.33 61.66 54.81
OBOE 0 0 unknown 0 0 unknown 0 0 unknown
University 20.40 28.57 23.80 20.40 28.57 23.80 25.00 28. 57 26.66
Vehicle 0 0 unknown 0 0 unknown 0 0 unknown
results has shown that more than 50% of the unmatched statements are actually
semantically and logically accurate, although, not present in the original answer
pool. Nevertheless, Table (1) and 2 only display the result of correctly matched
edges to the original graph.
5 Conclusion and Future Work
One ontology evolution operation is concept addition, which implies adding a
concept by taxonomic and non-taxonomic relations. Commonly for changing an
ontology some external information is required. In this work WordNet as an ex-
ternal source for generating similarities between concepts and relations has been
Page 70 of 110
8 The Eighth Australasian Ontology Workshop
selected. The semantic similarities generated by WordNet, self-information pro-
duced from patterns within ontologies, and the hierarchical structure of ontolo-
gies are the basis of approaches introduced in this paper. The focus is on intrinsic
properties; presuming that intrinsic properties already exist, the assumption is
that an input concept is more likely to have the same intrinsic properties as its
siblings. Evaluation is based on calculating the precision and recall of detaching
a node from an ontology and attempting to reattach it. The results displayed in
this paper are based on this evaluation technique. Due to the poor F-measures
generated by the introduced approaches, an investigation into the cause of this
poor performance revealed that more than 50% of the statements that were con-
sidered incorrect are actually semantically accurate. These results if generated
by an ontology expert, could easily be regarded as correct.
The next step for this research is to generate more complex non-taxonomic
relations, such as statements including conjunction and disjunction. Throughout
the development of this work, the need for a ternary and a quaternary comparison
has been visible. Such a comparison is essential for generating more meaningful
ontology statements. Another future direction is to develop a source capable of
ternary and quaternary comparison.
References
1. A V Aho, M R Garey, and J D Ullman. The transitive reduction of a directed
graph. SIAM Journal on Computing, 1(2):131–137, 1972.
2. H. Peter Alesso and Craig F. Smith. Thinking on the Web: Berners-Lee, Godel
and Turing. Wiley-Interscience, New York, NY, USA, 2008.
3. Christoph Böhm, Philip Groth, and Ulf Leser. Graph-based ontology construction
from heterogenous evidences. In International Semantic Web Conference, pages
81–96, 2009.
4. Silvana Castano, Irma Sofia Espinosa Peraldi, Alfio Ferrara, Vangelis Karkaletsis,
Atila Kaya, Ralf Moeller, Stefano Montanelli, Georgios Petasis, and Michael Wes-
sel. Multimedia interpretation for dynamic ontology evolution. Journal of Logic
and Computation, 19(5):859–897, October 2009.
5. Fabio Ciravegna, Alexiei Dingli, David Guthrie, and Yorick Wilks. Integrating in-
formation to bootstrap information extraction from web sites. In IJCAI’03 Work-
shop on Intelligent Information Integration, pages 9–14, 2003.
6. Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-
Interscience, New York, NY, USA, 1991.
7. Gerard de Melo and Gerhard Weikum. Menta: inducing multilingual taxonomies
from wikipedia. In Proceedings of the 19th ACM international conference on Infor-
mation and knowledge management, CIKM ’10, pages 1099–1108, New York, NY,
USA, 2010. ACM.
8. K. Dellschaft and S. Staab. On how to perform a gold standard based evalua-
tion of ontology learning. In Proceedings of the 5th International Semantic Web
Conference (ISWC), 2006.
9. Takahira Yamaguchi Dept and Takahira Yamaguchi. Acquiring conceptual rela-
tionships from domain-specific texts. In Proceedings of the Second Workshop on
Ontology Learning OL’2001, pages 0–2, 2001.
Page 71 of 110
Non-Taxonomic Concept Addition to Ontologies 9
10. Lucas Drumond and Rosario Girardi. A survey of ontology learning procedures. In
Frederico Luiz Gonçalves de Freitas, Heiner Stuckenschmidt, Helena Sofia Pinto,
Andreia Malucelli, and Óscar Corcho, editors, WONTO, volume 427 of CEUR
Workshop Proceedings. CEUR-WS.org, 2008.
11. E. Drymonas, K. Zervanou, and E. Petrakis. Unsupervised ontology acquisition
from plain texts: the ontogain system. In Proceedings of the 15th International
Conference on Applications of Natural Language to Information Systems (NLDB),
Wales, UK, 2010.
12. Jérôme Euzenat. Semantic precision and recall for ontology alignment evaluation.
In Proceedings of the 20th international joint conference on Artifical intelligence,
pages 348–353, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
13. Ademir Roberto Freddo and Cesar Augusto Tacla. Integrating social web with
semantic web - ontology learning and ontology evolution from folksonomies. In
KEOD, pages 247–253, 2009.
14. T Gruber. A translation approach to portable ontology specifications. Knowledge
Acquisition, 5(2):199–220, 1993.
15. Mark Hall. Ontology integration and evolution. SE Data and Knowledge Engi-
neering, 10, May 2004.
16. J. Hartmann, P. Spyns, A. Giboin, D. Maynard, R. Cuel, M. C. Suarez-
Figueroa, and Y. Sure. D1.2.3 methods for ontology evaluation. Techni-
cal report, Knowledge Web Consortium, 2005. Version 1.3.1, Available at:
http://knowledgeweb.semanticweb.org/, Downloaded 2005-05-10.
17. Matthew Horridge, Holger Knublauch, Alan Rector, Robert Stevens, and Chris
Wroe. A Practical Guide To Building OWL Ontologies Using Prot eg e 4 and
CO-ODE Tools. The University Of Manchester, 1.2 edition, March 2009.
18. Daniel C. Howe. Rita: creativity support for computational literature. In Proceed-
ing of the seventh ACM conference on Creativity and cognition, pages 205–210,
New York, NY, USA, 2009. ACM.
19. Pieter De Leenheer. On Community-based Ontology Evolution. PhD thesis, Vrije
Universiteit Brussel, Brussels, Belgium., 2009.
20. A. Maedche and S. Staab. Mining non-taxonomic conceptual relations from text.
In Proceedings of the 12th European Knowledge Acquisition Workshop (EKAW),
Juan-les-Pins, France, 2000.
21. Yuxin Mao. A semantic-based genetic algorithm for sub-ontology evolution. In-
formation Technology Journal, 9:609–620, 2010.
22. Diana Maynard, Diana Maynard, Wim Peters, and Marta” Sabou. Change man-
agement for metadata evolution. International Workshop on Ontology Dynamics
(IWOD) at European Semantic Web Conference, 2007.
23. D.L. McGuinness and F. van Harmelen. OWL web ontology language overview.
World Wide Web Consortium, Feb 2004.
24. Mohamed Mhiri and Faı̈ez Gargouri. Using ontologies to resolve semantic conflicts
in information systems design. In Proceedings of The first International Conference
on ICT and Accessibility, Hammamet, Tunisia, April 2007. The first International
Conference on ICT and Accessibility.
25. Victoria Nebot and Rafael Berlanga. Efficient retrieval of ontology fragments using
an interval labeling scheme. Information Sciences, 179(24):4151 – 4173, 2009.
26. Chokri Ben Necib and Johann Christoph Freytag. Using ontologies for database
query reformulation. In ADBIS (Local Proceedings), 2004.
27. Mathias Niepert, Cameron Buckner, and Colin Allen. A dynamic ontology for a
dynamic reference work. In Proceedings of the 7th ACM/IEEE-CS joint conference
on Digital libraries, JCDL ’07, pages 288–297, New York, NY, USA, 2007. ACM.
Page 72 of 110
10 The Eighth Australasian Ontology Workshop
28. Natalya Noy and Deborah L. McGuinness. Ontology development 101: A guide
to creating your first ontology. Technical Report KSL-01-05, Stanford Knowledge
Systems Laboratory, March 2001.
29. Natalya F. Noy and Mark A. Musen. Ontology versioning in an ontology man-
agement framework. Intelligent Systems, IEEE [see also IEEE Intelligent Systems
and Their Applications], 19(4):6–13, 2004.
30. Philip O’Brien and Syed Sibte Raza Abidi. Modeling intelligent ontology evolu-
tion using biological evolutionary processes. In IEEE International Conference on
Engineering of Intelligent Systems, pages 1–6, 2006.
31. Georgios Petasis, Vangelis Karkaletsis, Georgios Paliouras, Anastasia Krithara,
and Elias Zavitsanos. Ontology Population and Enrichment: State of the Art,
volume 6050 of Lecture Notes in Computer Science, pages 134–166. Springer Berlin
Heidelberg, 2011.
32. Simone Paolo Ponzetto and Roberto Navigli. Large-scale taxonomy mapping for
restructuring and integrating wikipedia. In Proceedings of the 21st international
jont conference on Artifical intelligence, IJCAI’09, pages 2083–2088, San Francisco,
CA, USA, 2009. Morgan Kaufmann Publishers Inc.
33. Janardhana Punuru and Jianhua Chen. Learning non-taxonomical semantic rela-
tions from domain texts. Journal of Intelligent Information Systems, pages 1–17,
2011. 10.1007/s10844-011-0149-4.
34. Sang Keun Rhee, Jihye Lee, and Myon-Woong Park. Ontology-based semantic
relevance measure. In Proceedings of the The First International Workshop on
Semantic Web and Web 2.0 in Architectural, Product and Engineering Design,
2007.
35. Navigli Roberto, Velardi Paola, and Faralli Stefano. A graph-based algorithm for
inducing lexical taxonomies from scratch. In Toby Walsh, editor, Proceedings of the
22nd International Joint Conference on Artificial Intelligence, Spain, July 2011.
IJCAI/AAAI.
36. David Sánchez and Antonio Moreno. Discovering non-taxonomic relations from
the web. In 7th International Conference on Intelligent Data Engineering and
Automated Learning. LNCS 4224, pages 629–636, 2006.
37. Rion Snow, Daniel Jurafsky, and Andrew Y. Ng. Semantic taxonomy induction
from heterogenous evidence. In Proceedings of the 21st International Conference
on Computational Linguistics and the 44th annual meeting of the Association for
Computational Linguistics, ACL-44, pages 801–808, Stroudsburg, PA, USA, 2006.
Association for Computational Linguistics.
38. Michael M. Stark and Richard F. Riesenfeld. Wordnet: An electronic lexical
database. In Proceedings of 11th Eurographics Workshop on Rendering. MIT Press,
1998.
39. Ljiljana Stojanovic. Methods and Tools for Ontology Evolution. PhD thesis, Uni-
versity of Karlsruhe, Germany, 2004.
40. Carlo Torniai, Jelena Jovanovic, Scott Bateman, Dragan Gasevic, and Marek
Hatala. Leveraging folksonomies for ontology evolution in e-learning environments.
In ICSC, pages 206–213, 2008.
41. C. Trabelsi, A. Ben Jrad, and S. Ben Yahia. Bridging folksonomies and do-
main ontologies: Getting out non-taxonomic relations. In Data Mining Workshops
(ICDMW), 2010 IEEE International Conference on, pages 369 –379, dec. 2010.
42. P. Wongthongtham, N. Kasisopha, and S. Komchaliaw. Community-oriented soft-
ware engineering ontology evolution. Internet Technology and Secured Transac-
tions, 2009. ICITST 2009. International Conference for, pages 1–4, November
2009.
Page 73 of 110
Short Paper:
Deep Semantics in the Geosciences: semantic building
blocks for a complete geoscience infrastructure
1,2 1
Brandon Whitehead, Mark Gahegan
1
Centre for eResearch
2
Institute of Earth Science and Engineering
The University of Auckland, Private Bag 92019, Auckland, New Zealand
{b.whitehead, m.gahegan}@auckland.ac.nz
Abstract. In the geosciences, the semantic models, or ontologies, available are
typically narrowly focused structures fit for single purpose use. In this paper
we discuss why this might be, with the conclusion that it is not sufficient to use
semantics simply to provide categorical labels for instances—because of the
interpretive and uncertain nature of geoscience, researchers need to understand
how a conclusion has been reached in order to have any confidence in adopting
it. Thus ontologies must address the epistemological questions of how (and
possibly why) something is ‘known’. We provide a longer justification for this
argument, make a case for capturing and representing these deep semantics,
provide examples in specific geoscience domains and briefly touch on a
visualisation program called Alfred that we have developed to allow
researchers to explore the different facets of ontology that can support them
applying value judgements to the interpretation of geological entities.
Keywords: geoscience, deep semantics, ontology-based information retrieval
1 Introduction
From deep drilling programs and large-scale seismic surveys to satellite imagery and
field excursions, geoscience observations have traditionally been expensive to
capture. As such, many disciplines related to the geosciences have relied heavily on
inferential methods, probability, and—most importantly—individual experience to
help construct a continuous (or, more complete) description of what lies between two
data values [1]. In recent years the technology behind environmental sensors and
other data collection methods and systems have enabled a boom of sorts in the
collection of raw, discrete and continuous geoscience data. As a consequence, the
operational paradigm of many conventional geoscience domains, once considered
data poor, now have more data than can be used efficiently, or even effectively. For
example, according to Crompton [2], Chevron Energy Technology Corporation had
over 6000 Terabytes of data, and derived products such as reports, and is rapidly
expanding. This data deluge [3], while significant in its affect on capturing
information related to complex earth science processes, has become a Pyrrhic victory
for geoscientists from a computational perspective.
Page 74 of 110
The digital or electronic facilitation of science, also known as eScience [4] or
eResearch, coupled with the science of data [5] is fast becoming an indispensable
aspect of the process of Earth science [6–8]. There are exemplar projects such as
OneGelogy1, which translates (interoperates) regional geologic maps in an effort to
create a single map of the world at 1:1 million scale; as well as the Geosciences
Network2 (GEON) which houses a vast array of datasets, workflows, and tools for
shared or online data manipulation and characterisation. Further, the National
Science Foundation (in the U.S.A.) has funded EarthCube3 which seeks to meld the
perspectives of geoscientists and cyberscientists to create a framework for locating
and interoperating disparate, heterogeneous information about the entire Earth as a
comprehensive system. The major contributions that eScience can make is by
providing ways to communicate the semantics, context, capabilities and provenance
of the datasets, workflows, information and tools in order for researchers to have a
firm understanding of the artefacts they are using, and how they are using them.
In this paper, we illustrate how multiple, multi-faceted semantic models are
coordinated under the linked data paradigm to better reflect how geoscience
researchers situate concepts with their own knowledge structures in an effort to
contextualise observations, phenomena and processes. We look to expose which
semantic, or ontological, commitments are needed to glean how science artefacts
relate to researchers, methods and products (as data, or via theory) in order to transfer
what is known about a place, and how it is known, as a useful analog for geoscience
discovery. We use an interactive computational environment, known as Alfred, to
view disparate ontologies that carry pieces of this ‘knowledge soup’ [9] as facets, and
expose the relationships for discovery of new knowledge.
2 Geoscience Background
The geosciences are far from exact; the earth as a living laboratory provides plenty of
challenges, not least to the task of representing and communicating semantics. While
geoscientists are remarkable in their ability to utilise disparate knowledge in
mathematics, physics, chemistry and biology to create meaning from observed
phenomena, their theories are bound by the inherent problems associated with scale
and place, cause and process, and system response [10]. The Earth’s phenomena are
complex, they often exhibit statistically unique signatures with several stable states
while mechanical, chemical and biologic processes work in tandem, or
asynchronously. Due to these often contradictory complications it has also been
suggested that the Earth sciences exemplify a "case study to understand the nature and
limits of human reasoning, scientific or otherwise" [11]. Adding to the complexity,
“Geologists reason via all manner of maps, outcrop interpretation, stratigraphic
1
http://www.onegeology.org/
2
http://www.geongrid.org
3
http://earthcube.ning.com/
Page 75 of 110
relationships, and hypothetical inferences as to causation” [12] and they do this
simultaneously across geographic and temporal scales.
In order to discern the categories and components of the Earth as a system, the
geoscientist requires a trained eye, what anthropologists call “professional vision”
[13], which often necessitates years of experience and mentoring. This contextualised
view of the world uses a long view of time, and becomes adept at distinguishing
infrequent catastrophic events from those more frequent via the feedback loops
between processes and components [13]. However, these feedback loops are often not
well understood due to the fragmented nature of geoscience observation and data.
This has required the geoscience community of practice to develop the means by
which their observations are understood. Most notably, instead of constructing a
specific research question and testing it, geoscientists often use the method of
‘multiple working hypotheses’ [14] and work toward reducing what is not known,
instead of working towards some axiomatic truth. Indeed, the ability to abstract earth
processes to a rational metaphoric justification could be considered an art form.
As such, geology is often referred to as an interpretive science [15]; where empirical
evidence is not possible, a story often emerges. Interpreting meaning in the
geosciences revolves heavily around the inherent allusion in hypothesis, methods,
models, motivations, and often more importantly, experience. Understanding the
knowledge any researcher creates requires understanding that person’s research
methods and the rationale behind their decision processes, which requires the ability
for knowledge components to change roles as one tries to demystify the scale in
context and perceptions from which they are constrained. Often, what is determined
to be a result is steeped in probability as a function of a desired resource. To date, the
research and research tools used throughout geoscience domains are largely
situational; capturing tightly coupled observations and computations which become
disjointed when the view, filter, or purpose is altered, even slightly, to that which is
more representative of an earth system science.
3 Semantic Modelling in the Geosciences
As the previous section suggests, the semantic nature of geoscientific ideas, concepts,
models, and knowledge is steeped in experiential subjectivity and often characterised
by what can or cannot be directly observed, directly or indirectly inferred, and, in
many cases, the goals of the research. As the Semantic Web [16] has gained traction
and support, a subset of Earth science researchers have been intrigued by the
possibility of standards, formal structure, and, ultimately, ontologies in geoscience
domains, mainly because, as Sinha et al., have stated, “From a scientific perspective,
making knowledge explicit and computable should sharpen scientific arguments and
reveal gaps and weaknesses in logic, as well as to serve as a computable reflection of
the state of current shared understanding” [17].
Page 76 of 110
As evidenced by the dearth of semantic models, or ontologies, in the earth sciences
[18], the often-conflicting ideals and knowledge schemas are proving to be significant
hurdles for ontological engineers. Most of the semantic models in Earth science
communities would be considered weak [19], lightweight (sometimes referred to as
‘informal’) [20, 21] or implicit [22]. These include taxonomies, or controlled
vocabularies—like the American Geophysical Union’s (AGU) index of terms,4
glossaries [23], thesauri [24], or a typical data base schema. Conversely, semantic
models created with the aspiration of eventuating to strong, heavyweight or formal
ontologies are limited. In cases where published formal domain ontologies do exist
[25], they are often not openly available within the community.
One openly available ontology of note is the upper-level ontology SWEET: Semantic
Web for Earth and Environmental Terminology [26]. This formal ontology was
created to tag the huge repositories of satellite imagery created and housed by NASA.
As a result, the concepts used in SWEET are very high level and the granularity of the
ontology is, in most cases, not detailed enough to differentiate between the thousands
of resources an active research geoscientist might find useful,
There is a middle ground between the two ends of the semantic spectrum, in the form
of Mark-up Languages, which is quite promising. In the geosciences, two exemplar
Mark-up Languages do exist; the Geography Mark-up Language (GML) [27], and
Geoscience Mark-up Language (GeoSciML) [28]. The two languages were created to
serve mainly as a translation schema for data sharing and interoperability, and do
provide a level of formalisation and weakly typed relationship structure.
4 A Case for Deep Semantics
In this research we use the relative lack of formalised structures in the geosciences as
an opportunity to start from scratch and take a slightly different approach to
ontological engineering in the domain. We try get away from the highly restrictive,
monolithic, overarching structures and focus on a more complete picture of the
relational patterns of geoscientific artefacts. To summarise Gahegan et al., [29]: we
are looking to expose the ‘web of multi-faceted interactions’ between observations,
theory, data, motivations, methods, tools, places and people. To focus the modelling
effort, we asked the following questions: How is something known? Which entities
support a research artefact? Who has been publishing about a topic, concept, place,
research method or data product? What was the inference path a geoscientist traveled
from a piece of evidence to an interpretation?
As these questions might suggest, a deep semantic support structure should provide a
conceptual richness that permeates the depth of a specialised set of concepts and
provide a mechanism for defining how an artefact came to be represented. A deep
semantic structure should provide enough specificity in the concepts and relations that
4
http://www.agu.org/pubs/authors/manuscript_tools/journals/index_terms/
Page 77 of 110
the terms can be used to differentiate complex but real situations via the written
materials describing these situations, not simply how it was labelled, or tagged, by the
creator, librarian or data curator. Exposing this story behind the data, or, more
formally, the epistemological connections, deep semantics works towards
constraining the conceptual uncertainty of the procedural knowledge by explicitly
representing and exposing the semantics of research artefacts as the scientist has
orientated them for his/her evidence, and thus, the resultant interpretation. This
effectively frees the research scientist to focus on the declarative knowledge
supporting the probabilities in the numerical components.
The ability to locate resources has become increasingly important as data storage
continues to increase. What carries a heavier weight is the ability to locate a data
product at the time it is most useful, by being able to distinguish a resource’s when
and where relatively rapidly. With a deep semantic view, we are able to begin
pursuing the why and how of the conceptual structures that support geoscientific
knowledge and discovery. In the information sciences this is often referred to as
precision and recall. Deep semantics adds epistemological underpinnings and a level
of context to precision and recall while adding facets to the constraint and delineation
mechanisms.
5 Ontology Inception and Use
Building the relationship structures, as described in this section, of the disparate parts
of geoscience research artefacts creates a contextualised, and in this case visual,
representation of the network of ontological components that support a concept. We
treat every ontological component as linked data supported by domain specific
terminological ontologies [30]. We use the full version of the Web Ontology
Language (OWL Full) to promote emergent constraints via relationships when
possible. OWL Full was chosen due to its compatibility with other modeling
approaches, most notably Resource Description Framework (RDF), as well as
reducing the restrictions on class definitions. The latter is necessary in the Earth
sciences as it is quite common to find a concept, or identifier, that is a class name as
well as an instance. In addition, given the nature of geoscience knowledge, it should
not be logically impossible to arrive at a conclusion that is not yet known to the
system through the ontological framework. We felt this fits more in line with the
process of Earth science, which relies quite heavily on reducing what is not known
rather than enforced, top-down, logical constraints depicting what is known
axiomatically. It is this connected interworking of heterogeneous semantic models
ranging from weak to strong, lightweight to heavyweight, and informal to formal
which join together as linked data, that we have come to refer to as deep semantics.
The remainder of this section describes how each individual ontology was
constructed.
5.1 Basin and Reservoir ontology
Page 78 of 110
We endeavoured to create a framework for formal geoscience knowledge as it applies
to sedimentary basins and reservoirs in the energy and petroleum industry under the
aegis of recognised industry Subject Matter Experts (SMEs). The SMEs participated
in knowledge acquisition exercises [31] orchestrated to discuss fundamental concepts
and their meanings as interpreted and explained through their formal and experiential
mastery. As concepts emerged, they were explicitly described, often through
diagrams and examples, to the satisfaction of the other participants. Prior to each
workshop, a set of concepts had been extracted from a survey of applicable literature
in the domain to serve as exemplars for the types of concepts found in research
artefacts that differentiate and describe specific geoscience situations and models.
These concepts were periodically re-introduced to the SMEs to ensure structure that
was being created had semantically tenable end-points. This process allowed
interrelationships between fundamental and domain-level concepts to be exposed and
characterised. As the exercise progressed, clusters of concept and relationship types
became apparent. The open nature of the knowledge acquisition exercise allowed the
participants to navigate through the conceptual neighbourhood that they had created.
As such, there are areas of the concept space that are defined more rigorously than
others.
The workshops culminated two ontological frameworks: a Basin ontology [32, 33]
and a Reservoir ontology. The Basin ontology focuses on concepts corresponding to
basin characterisation. The core concepts are related to properties and other classes
through select earth processes (e.g., the Basin class is related to the Strata class via a
tectonic processes, such as subsidence). The Reservoir ontology was created quite
similarly as the Basin ontology, with the exception being that the contributing SMEs
were well versed in petroleum reservoir characterisation and modeling instead of
basin characterisation.
The Basin and Reservoir ontologies have been created to interoperate with each other
to coordinate the delineation of scale dependent ambiguities in research artefacts. To
further promote semantic interoperability, both of these ontologies have natural
contact points for semantic correlation with upper-level earth science ontologies in
the public-domain, such as SWEET, as well as with other domain-specific ontologies
from hydrocarbon exploration and production, to hydrologic and paleoclimate
modeling, should they become available.
5.2 Agent and Resource ontology
Two of the more important facets of this research are the actual research artefacts and
the researchers, or creators, of those artefacts. Fortunately, librarians have already
spent a significant amount of time developing a standard for metadata that captures
the types of information that we wanted to capture from resources. We used the
Agent profile from the Dublin Core Metadata Initiative5 (DCMI) to describe authors,
contributors, software, companies, and research groups. There are other types of
agents, of course, and DCMI is set up to handle these distinctions, but for our
5
http://dublincore.org/
Page 79 of 110
purposes a subset was all that was required. The Resource profile from DCMI is used
to describe any artefact produced by research. This can include publications,
abstracts, presentations, and data products. Again, the schema for the DCMI
framework allows for a plethora of types, but a subset was all that was required here.
5.3 Task ontology
The Task ontology was constructed to provide a framework for actions that are
completed during research. These include observations, methods and processes like
data collection, data manipulation, statistical methods, etc. Items in the Task
ontology link to Resources as outputs and inputs, and to Agents as creators,
contributors, reviewers, etc. The concepts in this specification are often chained
together to create large structures, and are helpful in delimiting clusters of
information. The Task ontology was created by, first, describing a small set of
exemplar concepts that related strongly to key components of the semantic models
described in the previous two sections. Once the initial concepts were introduced, the
structure was extended by defining known superclasses and subclasses, and then
supplanting those core concepts with text mining utilising basic natural language
processing principles.
5.4 Oilfield Glossary and World Oil and Gas Atlas ontology
The Schlumberger Oilfield Glossary6 is a fantastic on-line resource covering an
expansive number of topics. The Oilfield Glossary ontology was constructed from
harvesting the information hosted on this web site. Due to research limitations, it was
more beneficial to create a local copy of this data and convert that to a series of triples
than to develop a script to query the site interactively. During the data conversion, all
partial relationships within the structure, and the links to the corresponding web page
were preserved.
The World Oil and Gas ontology was created by manually entering information
provided in the summaries, graphs, and tabular data, as depicted in the World Oil and
Gas Atlas [34], into an electronic format. Once in an electronic format, a script was
generated to alter the format, along with a little manual editing, to OWL.
6 Early Results: Powder River Basin Use Case
This use case illustrates how research artefacts associated with the Powder River
Basin, located in the central part of the U.S.A., can be visualised and navigated via a
knowledge computation platform referred to here as Alfred. This platform allows for
navigating and manipulating disparate multifaceted structures in one graph space.
The user loads an ontology into the system, which is then represented as a facet. Any
facet can be docked to any length of the graph border. Through docking a facet (up to
four), Alfred provides a space for the user to follow their interests in their linked data
exploration.
6
http://www.glossary.oilfield.slb.com/
Page 80 of 110
We proceed from the perspective of a research scientist with an interest in the Powder
River Basin. The user enters “Powder River” into Alfred’s the search field. The
resulting graph, shown in Figure 1, shows two concepts matching the search term
within a neighbourhood of related concepts. One of the Powder River concepts
(highlighted with a yellow outer ring) is symbolised using a gold circle coupled with a
black ‘basin’ object from a scalable vector graphic (SVG). The edge pointing to the
yellow circle labeled Basin, denotes it is an instance of the Basin class (yellow disc)
from the Basin ontology. The other symbol labeled Powder River is a grey triangle
which signifies it as a member of the World Oil and Gas ontology (in the structure,
these two concepts are in fact connected via an owl:sameAs relation, but this type of
relation has been suppressed in the current view for readability). Three conference
abstracts, symbolised by a red circle, with an SVG in the shape of a book, relate via a
references edge to the Powder River concepts, as well as a few concepts symbolised
by black diamonds, which are delineating concepts from the Oilfield Glossary
ontology.
Fig. 1. Local graph neighbourhood of the concept representing the Powder River Basin. The
current view shows three published artefacts, how the concept Powder River is linked in the
hierarchy (it is an instance of Basin) as well as a few terms from the Oilfield Glossary.
At this stage, the user has a few options. The user can select something from the
graph, adjust the filter settings to increase the type and/or level of information
displayed in the graph, or start a new search. To continue with the example in the use
case, we assume the users interest has been piqued by one of the research artefacts
Page 81 of 110
sharing a relationship with the Powder River Basin concept. If the user were
interested in seismic reflection data, they might select the artefact purporting to deal
with complex seismic reflection attributes (red disc with book SVG, lower left) via a
double click.
Upon this click action, the graph re-centres itself using the user selected node as the
central concept, as depicted in Figure 2. This selection reveals a deeper structure
associated with that particular artefact. In this view, the creator of the artefact,
symbolised by a dark green circle surrounding a SVG of a person, has emerged along
with several concepts found in the Oilfield Glossary. The relationship to the Powder
River and Basin concepts have persisted to the new concept layout (lower middle of
Fig. 2). Several concepts from the Task ontology (blue circles) have emerged,
potentially signifying relationships to the data (seismic data) as well as concepts
related to analysis mechanisms (phase coherence) associated with this particular
research artefact. This view also provides the user with contextually similar research
artefacts by displaying the research outputs that share a relation with other concepts in
the known ontologies.
Fig. 2. Local graph neighborhood of a research artefact related to the Powder River Basin.
The current view shows the artefacts creator, as well as other concepts from the semantic
structures known to the system.
In the example depicted in Figure 2, three research artefacts appear to share several
relationships (mostly a reference edge) with concepts found in the Oilfield Glossary,
as well as the Tasks ontology. This clustering suggests there are other research
Page 82 of 110
products that have utilised the same, or similar, methods and data that were used in
the research artefact of interest. This is worth mentioning here as the related data,
tasks, and concepts allow the user to explore and glean the concepts and structures
that support a research artefact. The ability to navigate, what has become, the
epistemological lineage of a research artefact cultivates a formal representation of the
symbiotic components of geoscience research products and geoscience knowledge.
Fig. 3. A local graph neighbourhood shown with a web page that is marked up with red text
using the concepts from the ontologies loaded into the system. The user can go back and forth
between graph space and the web page in order to better refine the context and scope of
research artefacts and web enabled content.
At this final stage of the use case, we illustrate how the conceptual neighbourhood of
the graph can synchronise with other web enable components, in this case browser
content. As portrayed in Figure 3, a user can open a web page and search for known
semantic components on that page. When the search has completed, all known
concepts are now displayed with red text within the browser. Further, by hovering
over any syntactic component on the corresponding web page (in this instance, it is
the mobile version of the Wikipedia page for the Powder River Basin) the user is
presented with a pop-up dialogue populated by the referring ontology. If a term is
situated in multiple ontologies, each one will be listed in the pop up, with the text
providing a live link back to the graph space. In this way, a user could bring their
conceptual neighbourhood with them as they peruse web content and use the
highlighted text references to help filter for relevance. This has proved to be
Page 83 of 110
particularly helpful with the increasing number of peer reviewed publications
available in a web friendly format.
The Powder River Basin use case illustrates how deep semantics can benefit
geoscientists by providing a mechanism to visualise and explore the components that
comprise a knowledge construct. When a geologist purports to know how to
characterise a particular basin, other geologists and engineers naturally want to know
what data and analysis methods were used to support that interpretation. How was
the stratigraphy interpreted? What was the timing of the tectonic events? What is the
burial history? Deep semantics allows other geoscientists to explore these supporting
entities and the decisions that were made along the path to any particular explication.
7 Concluding Remarks
Geoscience ontologies are typically quite lightweight, or implicit, and are engineered
for one specific purpose. As such, the semantic structures in the geosciences fail to
capture the complexities and intricacies inherent in the domain knowledge.
Ontologies like SWEET are a great start at a general upper level structure for
geoscience domains, but other than providing a label for instances, these structures
are far removed from capturing the level of detail necessary to empower domain
scientists, or knowledge engineers, with useful components for day-to-day
meaningful research activities. In this paper we illustrate how a deep semantic
structure serves to differentiate research products by capturing epistemological
commitments of geoscience research artefacts using ontologies throughout the
spectrum of formalisation. This deep semantic structure provides the conceptual
backbone for geoscientific search, discovery and enquiry.
Acknowledgments. The authors would like to thank Dr. Will Smart and Sina
Masoud-Ansari, at the University of Auckland’s Centre for eResearch, for their
contributions to the Alfred framework used to illustrate the use case in this paper.
The authors would also like to acknowledge the generous support of the New Zealand
International Doctoral Research Scholarship (NZIDRS), which helped make this
research possible.
8 References
1. Brodaric, B., Gahegan, M.: Experiments to Examine the Situated Nature of Geoscientific Concepts.
Spatial Cognition and Computation. 7, 61–95 (2007).
2. Crompton, J.: Putting the FOCUS on Data. W3C Workshop on Semantic Web in Oil & Gas Industry. ,
Houston, USA (2008).
3. Bell, G., Hey, T., Szalay, A.: Beyond the Data Deluge. Science. 323, 1297–1298 (2009).
4. Hey, T., Trefethen, A.E.: Cyberinfrastructure for e-Science. Science. 308, 817–821 (2005).
5. Hey, T., Tansley, S., Tolle, K. eds: The Fourth Paradigm: Data-intensive scientific discovery.
Microsoft Research, Redmond, Washington (2009).
6. Sinha, A.K. ed: Geoinformatics: Data to Knowledge. Geological Society of America (2006).
Page 84 of 110
7. Sinha, A.K., Arctur, D., Jackson, I., Gundersen, L. eds: Societal Challenges and Geoinformatics.
Geological Society of America, Boulder, CO (2011).
8. Keller, G.R., Baru, C. eds: Geoinformatics: Cyberinfrastructure for the Solid Earth Sciences.
Cambridge University Press, Cambridge, UK (2011).
9. Sowa, J.F.: Crystallizing Theories out of Knowledge Soup. In: Ras, Z.W. and Zemankova, M. (eds.)
Intelligent Systems: State of the Art and Future Directions. pp. 456–487. Ellis Horwood, New York
(1990).
10. Schumm, S.A.: To Interpret the Earth: ten ways to be wrong. Cambridge University Press, Cambridge,
UK (1991).
11. Raab, T., Frodeman, R.: What is it like to be a geologist? A phenomenology of geology and its
epistemological implications. Philosophy and Geography. 5, 69–81 (2002).
12. Baker, V.R.: Geosemiosis. GSA Bulletin. 111, 633–645 (1999).
13. Kastens, K., Manduca, C.A., Cervato, C., Frodeman, R., Goodwin, C., Liben, L.S., Mogk, D.W.,
Spangler, T.C., Stillings, N.A., Titus, S.: How Geoscientists Think and Learn. Eos. Trans. AGU. 90,
265–266 (2009).
14. Chamberlin, T.C.: The Method of Multiple Working Hypotheses. Science. 148, 754–759 (1899).
15. Frodeman, R.: Geological reasoning: Geology as an interpretive and historical science. GSA Bulletin.
107, 960–968 (1995).
16. Berners-Lee, T., Hendler, J., Lassila, O.: The Semantic Web. Scientific American. 284, 34–43 (2001).
17. Sinha, A.K., Ludäscher, B., Brodaric, B., Baru, C., Seber, D., Snoke, A., Barnes, C.: GEON:
Developing the Cyberinfrastructure for the Earth Sciences. (2003).
18. Babaie, H.A.: Ontological relations and spatial reasoning in earth science ontologies. In: Sinha, A.K.,
Arctur, D., Jackson, I., and Gundersen, L. (eds.) Societal Challenges and Geoinformatics. pp. 13–27.
Geological Society of America, Boulder, CO (2011).
19. Obrst, L.: Ontologies for semantically interoperable systems. Proceedings of the twelfth international
conference on Information and knowledge management. pp. 366–369. ACM, New Orleans, LA (2003).
20. Sowa, J.F.: Future Directions for Semantic Systems. In: Tolk, A. and Jain, L.C. (eds.) Intelligence-
Based Systems Engineering. pp. 23–47. Springer-Verlag Berlin (2011).
21. Giunchiglia, F., Zaihrayeu, I.: Lightweight Ontologies. In: Liu, L. and Özsu, M.T. (eds.) Encyclopedia
of Database Systems. pp. 1613–1619. Springer, US (2009).
22. Sheth, A., Ramakrishnan, C., Thomas, C.: Semantics for the Semantic Web: The Implicit, the Formal
and the Powerful. International Journal on Semantic Web & Information Systems. 1, 1–18 (2005).
23. Neuendorf, K.K.E., Mehl, Jr., J.P., Jackson, J.A.: Glossary of Geology. American Geosciences
Institute (2011).
24. Deliiska, B.: Thesaurus and domain ontology of geoinformatics. Transactions in GIS. 11, 637–651
(2007).
25. Zhong, J., Aydina, A., McGuinness, D.L.: Ontology of fractures. Journal of Structural Geology. 31,
251–259 (2009).
26. Raskin, R.G., Pan, M.J.: Knowledge Representation in the Semantic Web for Earth and Environmental
Terminology (SWEET). Computers & Geosciences. 31, 1119–1125 (2005).
27. Lake, R., Burggraf, D.S., Trnini!, M., Rae, L.: Geography Mark-Up Language (GML). John Wiley &
Sons, Ltd, West Sussex, England (2004).
28. Sen, M., Duffy, T.: GeoSciML: Development of a generic Geoscience Markup Language. Computers
& Geosciences. 31, 1095–1103 (2005).
29. Gahegan, M., Luo, J., Weaver, S.D., Pike, W., Banchuen, T.: Connecting GEON: Making sense of the
myriad resources, researchers and concepts that comprise a geoscience cyberinfrastructure. Computers
& Geosciences. 35, 836–854 (2009).
30. Sowa, J.F.: Knowledge Representation: Logical, Philosophical, and Computational Foundations.
Course Technology Cengage Learning, Boston, MA (2000).
31. Ribes, D., Bowker, G.: Between meaning and machine: Learning to represent the knowledge of
communities. Information and Organization. 19, 199–217 (2009).
32. Whitehead, B., Gahegan, M., Everett, M., Hills, S., Brodaric, B.: Fostering the exchange of geoscience
resources for knowledge exploration and discovery. Proceedings of eResearch Australasia Conference.
p. 2p. , Gold Coast, Australia (2010).
33. Everett, M., Hills, S., Gahegan, M., Whitehead, B., Brodaric, B.: Improving Semantic Interoperability
through the Development of a Reusable E&P Earth Science Ontology. American Association of
Petroleum Geologists (AAPG) Annual Convention and Exhibition. , Houston, USA (2011).
34. Guoyo, L.: World Atlas of Oil and Gas Basins. WIley-Blackwell, Hoboken, NJ, USA (2010).
Page 85 of 110
Short Paper: Assessing Procedural Knowledge in Open-
ended Questions through Semantic Web Ontologies
Eric Snow, Chadia Moghrabi and Philippe Fournier-Viger
Département d’informatique, Université de Moncton, Moncton, Canada
{eric.snow,chadia.moghrabi,philippe.fournier-viger}@umoncton.ca
Abstract. This paper presents a novel approach for automatically grading stu-
dents’ answers to open-ended questions. It is inspired by the OeLE method,
which uses ontologies and Semantic Web technologies to represent course ma-
terial. The main difference in our approach is that we add a new category of
concepts, named functional concepts, which allow specifying an ordering rela-
tion between concepts. This modification allows assessing procedural
knowledge in students’ answers by grading the ordering of these concepts. We
present an example for grading answers in a course about computer algorithms,
and report the corresponding results.
Keywords: E-Learning, Computer-Assisted Assessment (CAA), Ontology,
Semantic Web, Procedural Knowledge.
1 Introduction
Assessing the students’ learning in an e-learning environment often relies on multiple
choice or fill-in-the-blank questions, which only trigger the lowest level (Knowledge)
of Bloom’s taxonomy [1] of knowledge acquisition. As we shall see in Section 2,
several attempts have been made to incorporate open-ended questions in online as-
sessment, which would possibly trigger the higher levels of Bloom’s taxonomy (Syn-
thesis and Evaluation) in the students’ learning.
However, grading open-ended questions by hand can be time-consuming. To build
an e-learning environment that can automatically grade free-text answers, a variety of
techniques have been used, such as Information Extraction (IE) [4-5], Natural Lan-
guage Processing (NLP) [6-11], or statistical techniques [13-15].
Our approach resembles that of the OeLE system [2]. This system also uses NLP to
assess the level of understanding of the students. Course material is represented in an
ontology and encoded in the Web Ontology Language (OWL). The use of Semantic
Web technologies allows the sharing and reusing of course ontologies, thus potential-
ly reducing the time spent designing the ontologies. This allows for a deeper under-
standing of the text than more superficial statistical techniques. Automatic assessment
is much faster, and hopefully done more objectively, than manual scoring. The OeLE
system has been used in two online courses, Design and Evaluation of Didactic Me-
dia, and Multimedia Systems and Graphical Interaction.
Page 86 of 110
OeLE successfully assesses the semantic content of the students’ answers if the an-
swers contain static expressions of facts about didactic media or multimedia systems.
However, when applying it to the assessment of a computer algorithms course, we
observed that the ordering of the elements in students’ answers is not taken into ac-
count. It is crucial that this ordering be considered because to describe how an algo-
rithm works, certain concepts should be stated in a specific order. In this paper, we
address this challenge by proposing a new approach in which we introduce the idea of
functional concepts. The course ontology then incorporates ordering information
about a subset of these functional concepts. The assessment process is modified to
take into account the ordering of these concepts in the students’ answers and adjust
their grade accordingly. The novelty of our work is in applying a hybrid approach
combining the OeLE system with functional concepts to assess students’ answers in
domains using highly procedural knowledge.
Section 2 of this paper is a review of other automatic free-text assessment systems.
We only focus here on short-answer assessment systems where reference texts are
tailored to the course material, although some other systems have also been developed
for essay scoring, where more general texts about a topic are used for training. Sec-
tion 3 presents the general methodology, followed by our preliminary results in Sec-
tion 4. We conclude the paper in Section 5 with some future work which we are in-
vestigating.
2 Related Work
This section presents previous and ongoing research in automatic short-answer as-
sessment. A good review of many of these systems can be found in [3]. Although
these systems do not take advantage of Semantic Web ontologies, they contain none-
theless functionalities and techniques useful to our system.
Some systems compare students’ answers to the ideal answer supplied by the
teacher. For instance, Automated Text Marker [4] uses a pattern-matching technique.
It has been tested in courses on Prolog programming, psychology and biology. Au-
tomark [5] uses IE techniques to grade students’ answers by comparing them to a
mark scheme template provided by the teacher. It achieved 94.7% agreement with
human grading for six of the seven science-related questions asked on a test exam.
Some systems require teachers to provide training sets of marked student answers.
For example, Auto-marking [6] uses NLP and pattern-matching techniques to com-
pare students’ answers to a training set of marked student answers. This system ob-
tained 88% of exact agreement with human grading in a biology course. Bayesian
Essay Test Scoring System (BETSY) [7] uses naive Bayes classifiers to search for
specific features in students’ answers. In a biology course, it achieved up to 80% ac-
curacy. CarmelTC [8] uses syntactic analysis and naive Bayes classifiers to analyze
essay answers. On an experiment with 126 physics essays, it obtained 90% precision
and 80% recall. The Paperless-School Marking Engine (PS-ME) [9] is commercially
available and requires a training set of marked answers. The system uses NLP to
grade the students’ answers in addition to implementing Bloom’s taxonomy heuris-
Page 87 of 110
tics. However, the exact implementation is not disclosed. C-rater [10] uses a set of
marked training essays to determine the students’ answers grade using NLP. In a
large-scale experiment of 170,000 answers to reading comprehension and algebra
questions, it achieved 85% accuracy. In [11], a combination of NLP and Support Vec-
tor Machines is used to classify answers into two classes (above/below 6 points out of
10). It obtains an average of 65% precision rate (the only reported metric).
The MultiNet Working Bench system [12] uses a graphical tool to represent the
students’ knowledge visually. It compares the semantic network extracted from the
student answer to that submitted by the teacher. Verified parts of the network are
displayed in green, while wrong or unverified parts (not supported by logic inference)
are displayed in red.
Other systems rely on Latent Semantic Analysis (LSA). For example, Research
Methods Tutor [13] uses LSA to compare the students’ answers to a set of expected
answers. If the student answers incorrectly, the system guides the student into obtain-
ing the right answer. The Willow system [14] requires several unmarked reference
answers for each question. It also uses LSA to evaluate students’ answers written in
English or Spanish. In a computer science course, it achieved on average 0.54 correla-
tion with the teacher’s grading. A system currently in use at the University of Witwa-
tersrand [15] uses LSA and clustering techniques. It achieves between 0.80 and 0.95
correlation with the teacher’s grading.
3 Methodology
In this section, we briefly present the work on OeLE [2] and how we have adapted it
and expanded on it in our system. Our focus has been on grading students’ answers to
questions in a computer algorithms course taught in French.
3.1 Natural Language Processing
For each of the online exam’s questions in OeLE [2], the ideal answer provided by the
teacher and the students’ answers are processed similarly. The GATE software per-
forms most of the NLP tasks, and the Protégé software is used to build the course
ontology and encode it in OWL. While OeLE is written in Java and uses the Jena
framework to process the encoded ontology, our system is done in PHP and we de-
veloped our own ontology-processing code. It is important to note that OeLE and our
system use OWL for knowledge representation, but do not utilize its inference ser-
vices. In this paper, we use the same terminology as [2]. We refer to OWL classes as
concepts, to object properties as relations, and to data properties as attributes. Also,
entity is used as a generic term for concept, relation, or attribute, while property is
used for relation or attribute.
The NLP consists of three phases: Preparation, Search, and Set in a context. The
Preparation phase consists of spell-checking, sentence detection, tokenization and
POS tagging. In the Search phase, the linguistic expressions are detected and matched
against the course ontology. Finally, the Set in a context phase associates the attrib-
Page 88 of 110
utes and values to their respective concept, and also identifies which concepts partici-
pate in a relation.
In OeLE, the texts are annotated semiautomatically, meaning that the teacher only
needs to manually annotate the fragments unknown to the system or incorrectly
tagged. In our system, the natural language processing is done manually for the mo-
ment, as GATE does not sufficiently support French (out-of-the-box) for our purpos-
es. Performing automatic French annotation is planned as a future work.
As an example, we use an actual question from a computer algorithms course given
at our university: “Describe Depth-First Search (DFS)”. Table 1 shows the annotation
set (at the end of the NLP phase) of the partial student’s answer: “Depth-First Search
(DFS) is an exhaustive algorithm that explores a graph...” The ideal answer supplied
by the teacher is similarly annotated; however, for every annotated entity, a numerical
value ought to be supplied specifying the relative importance of that entity within the
question.
Table 1. Example annotated answer of a student to describe DFS.
Category Description
Concept DepthFirstSearch
Concept Algorithm
Concept Graph
Attribute Exhaustive
Relation IsA
Relation Explores
3.2 Conceptual Grading
The grading stage consists of calculating the semantic distance between the annota-
tion sets (obtained in Section 3.1) of each student’s answer and that of the teacher’s
ideal answer, with respect to the course ontology. Because of space limitations, we
cannot give detailed calculations for the example. The reader is advised to see the full
explanation in the original publication [2], or an easy-to-follow example in [16].
The formulas used in [2] for calculating the semantic distances are given below. In
every function, teacher-provided constants allow for certain elements to be weighted
more or less heavily according to their importance. The best combination of these
constants is problem-dependent and should be discovered empirically. The “linguistic
distance” between the textual representation of the entities in the student and teacher’s
answer is also taken into account. All functions return values in the [0,1] interval.
Concept similarity. To calculate the concept similarity (CS) between concepts and
, the following function is used:
( ) ( ) ( ) ( ) (1)
The constants , , indicate the relative importance of the corresponding
elements. Also, and .
Page 89 of 110
The concept proximity (CP) is calculated using the taxonomy formed in the ontol-
ogy by the class hierarchy defined in OWL. Note that the relation is explicitly
added to the course ontology (with the class as domain and the subclass as image)
where rdfs:subClassOf is used:
If the concepts and have no taxonomic parent (other than the root), this value
is zero, otherwise it is defined as such:
| ( )|
( ) | |
(2)
where | ( )| is the number of concepts separating and through the
shortest common path through the taxonomic tree, and | | is the total number
of concepts in the ontology. A shorter path thus indicates a stronger similarity be-
tween the two concepts.
The properties similarity (PS) calculates the similarity between the set of properties
associated with and . The properties of a concept c are the union of the set of
attributes that have c as domain, and the set of relations that have c as domain or im-
age.
Lastly, ( ) uses the Levenshtein distance between the string representation
of concepts and , written below, and is defined as follows:
( ) (3)
Attribute similarity. The attribute similarity between two attributes and of two
concepts is calculated by a similar function:
( ) ( )
( ) ( ) (4)
Here also, the non-negative constants , , must add up to 1. The function
returns the (most specific) concept which is in the domain of a. The function
( ) is defined as such:
| |
( ) | {| |}|
(5)
that is, the similarity of their value sets. The function returns the image of
the attribute a.
Relation similarity. The relation similarity between two relations and is calcu-
lated in a similar manner:
Page 90 of 110
( ) ( )
( ) ( ) (6)
It is required that the sum of the non-negative constants , be 1. The function
returns the most specific concept in the domain of r, while returns
the most specific concept in the image of r. The concept similarity is calculated twice,
to compare the domains of the relations and (obtained by ) and the
images of the relations (obtained by ), respectively.
Global evaluation. In order to accomplish the evaluation of a question, each of the
concepts of the student’s answer is associated with the closest concept of the ideal
answer, given that each concept can only be used once. The similarity between each
pair of concepts is then calculated and is multiplied by the relative numerical value of
the concept in the ideal answer. The similarity is then added to the final grade. The
same process is repeated for relations and attributes.
3.3 Procedural Knowledge Grading
Our system uses the same grading algorithm as OeLE [2]. The students’ answers are
compared to the teacher’s ideal answer. The grades are calculated based on the most
similar entity in the expected answer. In OeLE, the order of the entities is not factored
in the grade and any permutation of the linguistic expressions of the student’s answer
yields the same grade.
However, this is not appropriate for assessing procedural knowledge in our system.
If the above method is applied to evaluate text describing procedural knowledge such
as algorithms-related answers, the grade calculation ought to take into account the
relative order of a subset of concepts expressing procedural knowledge.
Functional concepts. In order to address this issue, we propose to add functional
concepts to the course ontology. A functional concept represents a global procedure, a
sequence of sub-procedures or individual steps to accomplish a given task.
Let us consider the following example algorithm, DepthFirstSearch, given in
pseudocode:
procedure DepthFirstSearch
VisitRoot
VisitFirstChildNode
VisitOtherSiblings
end
procedure VisitRoot [...]
procedure VisitFirstChildNode [...]
procedure VisitOtherSiblings [...]
Page 91 of 110
For every procedure or sub-procedure, we create a corresponding functional con-
cept: DepthFirstSearch, VisitRoot, VisitFirstChildNode, and VisitOtherSiblings. The
last three sub-procedures could in turn be further decomposed.
The functional concepts allow for a high-level description of the algorithm and
mask implementation details, which would be difficult to express in the ontology
using relations or attributes. Further decomposition of VisitRoot into individual steps
could be stated in any of the following ways:
DepthFirstSearch Root [using relation ]
VisitRoot Root [same relation with a more specific concept]
Root.visited=true [the value of the attribute becomes true]
Representing functional concepts in OWL. Relationships between functions are
defined as meta-functions in [17]. These meta-functions are implemented in our sys-
tem as relations between two functional concepts. In this example, two instances of
the relation are needed. One instance is needed between Visit-
FirstChildNode and VisitRoot, because the root has to be visited first, and another
between VisitOtherSiblings and VisitFirstChildNode, because the first child node
should be visited first. Similarly, three instances of the relation are
used between VisitRoot and each of the remaining functional concepts.
The same idea is found in [18], where the relation preceded_by is defined similarly
to and can be used to order any pair of classes P and P1. In other
words, P preceded_by P1 is defined as “Every P is such that there is some earlier P1”.
This relation is defined as transitive, and is neither symmetric, reflexive nor antisym-
metric.
In [19], an irreflexive and transitive relation precedes is used when “the sequence
of the related events is of utmost importance for the correct interpretation”. This paper
also defines the inverse relation follows.
Similarly, the working draft: “Time Ontology in OWL” [20] of the World Wide
Web Consortium (W3C) states that: “There is a before relation on temporal entities,
which gives directionality to time. If a temporal entity T 1 is before another temporal
entity T2, then the end of T1 is before the beginning of T 2.” This relation is part of the
time namespace.
In our implementation, the functional concepts and the relation
are defined as such in OWL:
Page 92 of 110
Note that the relation is implied by the class hierarchy rooted at
the concept FunctionalConcept, just as the relation is implied by the class
hierarchy in OeLE.
For every algorithm, a separate (meta) ontology lists the required orderings specific
to that algorithm. Although there exists many algorithms for graph exploration, we
only need to define the functional concepts once in the course ontology, and their
ordering can then be declared in a separate ontology. For instance, the Breadth-
FirstSearch algorithm can be defined with the same functional concepts as above,
only ordered differently.
For DepthFirstSearch, the meta-ontology is as follows:
VisitFirstChildNode VisitRoot
VisitOtherSiblings VisitFirstChildNode
Note that the following relation is also inferred by the transitive property:
VisitOtherSiblings VisitRoot
Grading with functional concepts. In our approach, the question evaluation process
remains mostly unchanged. No special treatment is given to the functional concept
class hierarchy rooted at the concept FunctionalConcept, even though its implied
relation is , rather than the relation implied for the other
concepts. This takes into account function nesting and composition, while allowing
calculating the proximity of the functional concepts.
However, the global evaluation of a student answer R takes into account the algo-
rithm-specific orderings of the meta-ontology. The new evaluation function is given
below:
( ) (7)
The final grade (FG) for the student answer R is proportional to the global evalua-
tion of the answer, , obtained from Section 3.2. Here, is a constant in the
interval [0,1] allowing the teacher to adjust the relative importance of the correct or-
dering of concepts in the global evaluation. The ordering factor of the answer, ,
is defined as follows:
(8)
| |
where represents the number of functional concepts having the right order-
ing in the student answer R, and | | the number of functional concepts or-
derings in the meta-ontology.
Page 93 of 110
It should be noted that if functional concepts in the student’s answer are ordered
with the opposite relation (that is, ), the evaluation algorithm inverts
the relation between the functional concepts.
Also, the individual student grades are affected by the number of defined order-
ings. If there are only a few orderings, as demonstrated below, students are strongly
penalized for every mistake. This is also the case with the concept proximity defined
in Formula 2, where the number of concepts in the ontology affects students' grades.
However, we can assume that the course ontology is fixed during evaluation, and that
the students' grades are therefore affected similarly (in a linear fashion).
4 Working Example and Results
Using Depth-First Search as an example, we can quantify the effect of the new evalu-
ation function on a student’s answer. To simplify, we omit the conceptual grading of
the answer and concentrate on the functional grading. Since the same entities are pre-
sent in both the student and teacher’s answers, the conceptual grade is 100%. The
ideal functional answer could be as follows: “Depth-First Search first visits the root
[of a graph], then [recursively] visits its first child node before visiting its other sib-
lings.” Table 2 shows the produced functional concepts.
Table 2. Example annotation of ideal answer to describe DFS (using only functional concepts).
Category Description
(Functional) Concept DepthFirstSearch
(Functional) Concept VisitRoot
(Functional) Concept VisitFirstChildNode
(Functional) Concept VisitOtherSiblings
Any permutation of this ideal answer taken as input by the original approach would
yield a grade of 100%. Now, consider the following student’s answer: “Depth-First
Search visits the root [of a graph], then [recursively] visits its first child node after
visiting its other siblings.” Here, “after” inverts the ordering of the two last concepts
(highlighted in bold below), yielding the following answer:
Table 3. Example annotation of student’s answer for DFS (using only functional concepts).
Category Description
(Functional) Concept DepthFirstSearch
(Functional) Concept VisitRoot
(Functional) Concept VisitOtherSiblings
(Functional) Concept VisitFirstChildNode
The student gave here the incorrect ordering:
VisitFirstChildNode VisitOtherSiblings
Page 94 of 110
However, these two student orderings are correct:
VisitFirstChildNode VisitRoot [inferred]
VisitOtherSiblings VisitRoot
As stated above, the conceptual grading of this answer, as performed by OeLE, is
100%. By using the new evaluation function (Formula 7), the final grade (FG) be-
comes:
( ) (9)
where the global evaluation (GE) is 100%, the ordering factor (DF) is 66.67%, and
the constant is given a value of 1.0. Considering that the ideal answer to this algo-
rithm contains only three orderings for pairs of functional concepts (one is inferred)
and that a third is out of order, this low grade seems acceptable, or at least a reasona-
ble improvement over the former grade of 100% that would have been attributed had
we only used the conceptual grading system.
5 Conclusion and Future Work
The work presented in this paper adapts the OeLE system to include procedural
knowledge. The example was taken from an algorithms course given at Université de
Moncton. This approach could be used in other domains where procedural knowledge
is central to processing the text. For example, [18] and [19] apply similar methods to
biomedical ontologies.
The approach put forth in this paper introduces functional concepts to represent
procedural knowledge in ontologies. The class hierarchy of functional concepts is
considered as a series of instances of the relation instead of .
For every computer algorithm (or procedure, for other domains), a series of instances
of the relation specify an ordering for pairs of functional concepts.
In this paper, the texts were annotated manually. We are considering annotating the
French texts semiautomatically as future work. The detection of the orderings (detect-
ing keywords such as “first”, “before”, “after” in the example of Section 4) could also
be performed automatically.
In the case where the student answer uses the opposite ordering relation (), the relation between the functional concepts is inverted prior to evalu-
ation. Some more complex answers could require more inversions, for example if the
student wrote “X and Y should be done after Z”.
Future work could also consider flow control structures, such as loops or branches,
although the textual representation of those structures without proper indentation or
braces could be ambiguous. For example, the VisitOtherSiblings functional concept
can be decomposed into the following loop: (for every other sibling, VisitNode).
Another idea that could be explored would be to add the notion of recursive proce-
dures, such as Depth-First Search. VisitFirstChildNode and (every VisitNode of) Visi-
tOtherSiblings should include recursive calls. As an ideal answer, the teacher could
Page 95 of 110
give either: DFS.isRecursive=true, or VisitFirstChildNode.isRecursive=true and Visi-
tOtherSiblings.isRecursive=true. Depending on the ideal answer given and their own
answer, students could be unjustly penalized.
References
1. Bloom, B.S.: Taxonomy of Educational Objectives, Handbook 1: The Cognitive Domain.
David McKay Co Inc., New York (1956)
2. Castellanos-Nieves, D., Fernández-Breis, J.T., Valencia-García, R., Martínez-Béjar, R.,
Iniesta-Moreno, M.: Semantic web technologies for supporting learning assessment.
Information Sciences 181(9), 1517-1537 (2011)
3. Pérez-Marín, D., Pascual-Nieto, I., Rodríguez, P.: Computer-assisted assessment of free-
text answers. The Knowledge Engineering Review 24(4), 353-374 (2009)
4. Callear, D., Jerrams-Smith, J., Soh, V.: CAA of short non-MCQ answers. In: Proceedings
of the 5th International CAA Conference, Loughborough, UK (2001)
5. Jordan, S., Mitchell, T.: e-Assessment for learning? The potential of short-answer free-text
questions with tailored feedback. British Journal of Educational Technology 40(2), 371-
385 (2009)
6. Sukkarieh, J., Pulman, S., Raikes, N.: Auto-marking: using computational linguistics to
score short, free text responses. In: Proceedings of the 29th IAEA Conference,
Philadelphia, USA (2003)
7. Rudner, L. & Liang, T.: Automated essay scoring using Bayes’ theorem. In: Proceedings
of the Annual Meeting of the National Council on Measurement in Education, New
Orleans, LA (2002)
8. Rosé, C., Roque, A., Bhembe, D., VanLehn, K.: A hybrid text classification approach for
analysis of student essays. In: Proceedings of the HLT-NAACL Workshop on Educational
Applications of NLP, Edmonton, Canada (2003)
9. Mason, O., Grove-Stephenson, I.: Automated free text marking with paperless school. In:
Proceedings of the 6th International CAA Conference, Loughborough, UK (2002)
10. Burstein, J., Leacock, C., Swartz, R.: Automated evaluation of essays and short answers.
In: Proceedings of the 5th International CAA Conference, Loughborough, UK (2001)
11. Hou, W.-J., Tsao, J.-H., Li, S.-Y., Chen, L.: Automatic Assessment of Students’ Free-Text
Answers with Support Vector Machines. LNCS 6096, 235-243 (2010)
12. Lutticke, R.: Graphic and NLP Based Assessment of Knowledge about Semantic
Networks. In: Proceedings of the Artificial Intelligence in Education conference, IOS Press
(2005)
13. Wiemer-Hastings, P., Allbritton, D., Arnott, E.: RMT: A dialog-based research methods
tutor with or without a head. In: Proceedings of the 7th International Conference on
Intelligent Tutoring Systems, Springer-Verlag, Berlin (2004)
14. Pérez-Marín, D., Alfonseca, E., Rodríguez, P., Pascual-Nieto, I.: Willow: Automatic and
adaptive assessment of students free-text answers. In: Proceedings of the 22nd
International Conference of the Spanish Society for the Natural Language Processing
(SEPLN), Zaragoza, Spain (2006)
15. Klein, R., Kyrilov, A., Tokman, M.: Automated Assessment of Short Free-Text Responses
in Computer Science using Latent Semantic Analysis. In: ITiCSE ‘11 Proceedings of the
16th annual joint conference on Innovation and technology in computer science education,
New York, USA, pp. 158-162 (2011)
Page 96 of 110
16. Fernández-Breis, J.T., Valencia-García, R., Cañavate- Cañavate, D., Vivancos-Vicente,
P.J., Castellanos-Nieves, D. OeLE: Applying ontologies to support the evaluation of open
questions-based tests. In: Proceedings of the KCAP’05 WORKSHOP. SW-EL’05:
Aplications of Semantic Web Technologies for E-Learning (in conjunction with 3rd
International Conference on Knowledge Capture (KCAP’05)), Banff, Canada (2005)
17. Aroyo, L., Dicheva, D.: Courseware authoring tasks ontology. In: Proceedings of the
International Conference on Computers in Education, pp. 1319-1320. (2002)
18. Smith, B., Ceusters W., Klagges, B., Köhler, J., et al.: Relations in biomedical ontologies.
Genome Biology 6(R46) (2005)
19. Schulz, S., Markó, K., Suntisrivaraporn, B. Formal representation of complex SNOMED
CT expressions. BMC Medical Informatics and Decision Making 8(1) (2008)
20. World Wide Web Consortium (W3C), http://www.w3.org/TR/2006/WD-owl-time-
20060927/, last accessed 2012-11-21.
Page 97 of 110
Short paper: Using Formal Ontologies in the
Development of Countermeasures for Military
Aircraft
Nelia Lombard1,2 , Aurona Gerber2,3 , and Alta van der Merwe3
1
DPSS, CSIR
nlombard@csir.co.za
http://www.csir.co.za
2
CAIR - Centre for AI Research
Meraka CSIR and Univerity of Kwazulu-Natal
http://www.cair.za.net/
3
Department of Informatics
University of Pretoria, Pretoria
http://www.up.ac.za/
South-Africa
Abstract. This paper describes the development of an ontology for use
in a military simulation system. Within the military, aircraft represent
a significant investment and these valuable assets need to be protected
against various threats. An example of such a threat is shoulder-launched
missiles. Such missiles are portable, easy to use and unfortunately, rela-
tively easy to acquire. In order to counter missile attacks, countermea-
sures are deployed on the aircraft. Such countermeasures are developed,
evaluated and deployed with the assistance of modelling and simulation
systems. One such system is the Optronic Scene Simulator, an engineer-
ing tool that is able to model and evaluate countermeasures in such a way
that the results could be used to make recommendations for successful
deployment and use.
The use of formal ontologies is no longer a foreign concept in the support
of information systems. To assist with the simulations performed in the
Optronic Scene Simulator, an ontology, Simtology, was developed. Sim-
tology supports the system in various ways such as providing a shared
vocabulary, improving the understanding of the concepts in the environ-
ment and adding value by providing functionality that improves integra-
tion between system components.
Keywords: Ontology, Countermeasure, Simulation, Design Research
1 Introduction
Military forces consider aircraft as important and expensive assets often repre-
senting huge investments. The protection of these assets is considered to be a
priority by most countries. Protection is needed from various threats and one of
Page 98 of 110
2 Lombard, Gerber and van der Merwe
these threats are attacks through enemy missiles such as surface-to-air missiles,
which are relatively cheap and easy to operate, and in addition, widely avail-
able in current and old war-zone areas [1]. These surface-to-air missiles are often
complex and they are continually being updated to withstand aircraft counter-
measures. In addition, missile systems differ from one another and the need to
understand how each type of missile reacts in an aircraft engagement is crucial in
the development of aircraft protection countermeasures[1]. The development of
these countermeasures is often not possible in real-life situations, and modelling
and simulation are therefore necessary for the development of aircraft protection
countermeasures. Figure 1 illustrates a military aircraft ejecting a flare, which
is a specific type of countermeasure used to protect against missile attacks.
Fig. 1. Countermeasures are implemented on aircraft to protect against missile attacks.
Aircraft Ejecting Countermeasures Flares (www.aerospaceweb.org)
Simulation systems model real-world objects and simulate them in an arti-
ficial world [2]. One such a simulation system is the Optronic Scene Simulator
(OSSIM), which has an application called the Countermeasure Simulation Sys-
tem (CmSim). CmSim uses models of real world objects such as the aircraft
and the missile, and simulates different scenarios to evaluate the behaviour of
these models under different circumstances [2]. Often these evaluations require
substantial computing power and it is not uncommon to wait a few hours for
simulation results.
At present, various problems are experienced when constructing the input
models for CmSim simulations. Because models are used as input into CmSim
simulations, it is necessary to ensure that these models are adequate and accurate
for useful simulations. The input model is adequate when it captures sufficient
input variables and context, and a model is accurate when it correctly captures
the input variables and relations. It is for example possible to create input mod-
els that are syntactically correct, but the interaction between the models are not
correctly set up in the simulation and therefore the results have no correlation
with the real world. In addition, different users with various roles work with the
system and it is necessary to acquire a common understanding and vocabulary
for the constructs of the models and their characteristics. Furthermore, the cre-
Page 99 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 3
ation of reference models for reuse across the user base would ensure better use
of resources and time.
When investigating possible technologies that support modelling within in-
formation systems, ontologies and ontology technologies feature extensively. One
of the original definitions for the term ontology is that by Gruber who defined an
ontology as a formalisation of a shared conceptualisation [3]. A formal concep-
tualisation is a representation in a formal language of the concepts in a specific
domain representing a part of the world. Formal ontologies are therefore on-
tologies constructed using a formal representation language such as Description
Logics (DL) [4]4 . Ontology is also used as a technical term denoting an artefact
that is designed for the specific purpose of modelling knowledge about some
domain of interest. Typically a domain ontology provides a shared and common
understanding of the knowledge in the chosen domain [5]. Given the character-
istics and purpose of ontologies, we decided to investigate the use of an ontology
to address the identified needs when constructing CmSim Models.
The remainder of this paper is structured as follow: Section 2 provides some
background of the simulation environment and why it was necessary to build
an ontology, as well as some background on ontologies. Section 3 discusses the
development and nature of Simtology. Sections 4 and 5 discuss the contribution
and conclude the paper in addition to discussing future work, as well as possible
extensions to the ontology.
2 Background
One of the largest investments in the military of a country is aircraft. Aircraft
is the target of unfriendly forces in order to weaken the military forces of a
country. These attacks include attacks executed by shoulder-launched missiles,
which are portable, easy to use and relatively easy to acquire. In order to counter
these missile attacks, the military deploy various kinds of countermeasures on
aircraft, and these countermeasures are developed, evaluated and deployed with
the assistance of modelling and simulation systems such as the Optronic Scene
Simulator (OSSIM).
2.1 The Simulation System Environment
CmSim is a software application that is part of the broader Optronic System
Simulation (OSSIM) system [2]. OSSIM is an engineering tool used to model and
evaluate the imaging and dynamic performance of electro-optical systems under
diverse environmental conditions. OSSIM are typically used for the following
applications:
– Development of optronic systems
– Mission preparation
4
For the remainder of this paper we mean formal ontology when we use the term
ontology
Page 100 of 110
4 Lombard, Gerber and van der Merwe
– Real-time rendering of infra-red and visible scenes
CmSim is specifically designed to do countermeasure evaluation for the pro-
tection of military aircraft. Models of the aircraft, the missile, the countermea-
sure and the environment are used to construct a scenario that simulates what
will happen in the real world [2]. The models are used as input into CmSim, and
it is necessary to carefully construct these models to get accurate simulations
results. The generation of simulation results are complex and time consuming,
and when inaccurate or faulty input models are used, valuable time is lost.
In order to construct better input models, it is necessary to improve the
understanding of the simulation and the meaning of concepts in the simulation
environment. Users of models often does not know what models exist already, to
what level the models were constructed, and the scenarios that might be possible
in the simulation, and knowledge is not shared between different role-players.
The simulation practitioner setting up the simulation scenario might not have
specialist knowledge of how the models interact, and can set up scenarios that
are syntactically correct but do not correlate with the real world scenario. There
is therefore a need to capture the specialised knowledge in reference models that
could be used before the scenario is fed to the simulation. Figure 2 depicts the
different role-players that could be involved in the simulation environment.
Fig. 2. Different Role-players Involved in a Simulation Environment
In order to address the above mentioned needs, we initiated a project based
following the guidelines of design science research (DSR) [6]. DSR provides a
research method for research that is concerned with the design of an artefact
that solves an identified problem. The creation of an ontology based application
was identified as a possible solution to the needs articulated when constructing
OSSIM simulation models. DSR will be described further in Section 3.1. The
next sections briefly introduce background on ontologies in computing.
Page 101 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 5
2.2 Ontologies and Ontology Tools
The origins of the term ontology could be traced to the philosophers of the
ancient world who analysed objects in the world and study their existence [3].
Modern ontologies use the principles of the ontology of early philosophers [7].
Ontologies formally describe concepts, so it is often used to capture knowledge of
a specific domain. The role of ontologies in a specific domain are thus generally
defined by [5] as to:
– Provide people and agents in a domain with a shared, common understanding
of the information in the domain;
– Enable reuse of domain knowledge;
– Explicitly publish domain assumptions;
– Provide a way to separate domain knowledge from operational knowledge;
and
– Setting a platform for analysis of the domain knowledge.
From the characteristics listed above it is possible to argue that an ontology
may be a solution to the problems experienced in OSSIM simulations. Formal
ontologies are represented in a specific formal knowledge representation language
[4]. For building and maintaining Simtology, we adopted Protégé 4 constructing
an OWL ontology. [8, 9]. Protégé is widely used and support for the use of the
editor and the development of ontologies are readily available [10–12]. Protégé
bundles reasoners such as Fact++ and Pellet with the environment [9, 13] and
we used these reasoners to test for consistency or to compute consequences over
the knowledge base during the development of Simtology [14].
2.3 Ontology Use in Modelling, Simulation and Military Systems
Within computing, modelling and simulation are used to build a representation
of the real world and simulate the behaviour of objects presented in the models
[2]. A simulation system is a specific application that uses a model as input
and execute a computer program that determines consequences and resulting
scenario information about the system being investigated [15].
Military systems and the knowledge captured therein are complex and of-
ten consist of layered information from different sources. To support this view,
Clausewitz, in his book, On War, wrote about military information as follow
[16]:
’...three quarters of the information upon which all actions in War are
based on are lying in a fog of uncertainty...’
’...in war more than any other subject we must begin by looking at the
nature of the whole; for here more than elsewhere the part and the whole
must always be thought of together...’
Furthermore, Mandrick discussed the use of ontologies to model information
in the military environment. According to Mandrick, ontologies in the military
Page 102 of 110
6 Lombard, Gerber and van der Merwe
must adhere to the same requirements as ontologies in other domains, as de-
scribed in Section 2.2. Important aspects to highlight is the ability of the ontology
to provide a common vocabulary between planners, operators and commanders
in the different military communities [16].
At present the adoption of ontologies in the military domain is primarily for
support of command and control in the battlefield, as well as the management of
assets and the sharing of knowledge[11, 17]. We also find ontologies where there is
a need to integrate different data sources and the communication between these
data sources [18, 19]. Although ontologies are used in the military modelling
and simulation domain, examples are sparse and at present do not support the
construction of input models for systems such as OSSIM. It could be argued that
Simtology will therefore present a unique contribution to military information
management.
3 Simtology
The development of Simtology was in response to the identified needs when
using the Optronic Scene Simulator (OSSIM) [2] to develop countermeasures for
missile attacks on aircraft as discussed in Section 2.1.
3.1 The Design and Development Process
The research design adopted for the development of Simtology, was Design Re-
search (DSR). DSR is a research methodology for the design and construction
of computing artefacts through the use of rigour (the use of fundamental knowl-
edge) and relevance (basing the development of the artefact on real needs) [6, 20].
In this project, the artefact is Simtology, the fundamental knowledge is obtained
from ontology knowledge, and the need is the construction of models for the OS-
SIM simulation environment. A DSR execution method that was proposed by
Vaishnavi et al.[21] is depicted on the left in Figure 3. This method was adopted
for this research project, and the development of Simtology is discussed further
according to the steps in Figure 3.
3.2 Awareness and Suggestion
The first steps in the design research process is awareness of the problem and
proposing possible suggestions for a solution. The following list summaries the
issues and needs in the simulation system as discussed in Section 2.1 that created
awareness of the problem:
– Different role-players: There are developers, model builders and users in-
volved in the system. Inconsistencies in the terminology used between dif-
ferent users often led to frustration and wrong use of concepts. There is lack
of a common vocabulary that is shared by everyone involved in building and
using the system.
Page 103 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 7
– Model complexity: One of the main characteristics is the ability of the system
to execute models at different levels of detail. This poses a problem to users,
when to know at which level of detail a model is implemented at.
– Reference models: Specific users that only interact with the system at a
certain level, need more technical insight into model detail to know what is
available in the system. This means that reference models are required that
can define domain-specific concepts to these users.
– Model Interaction: A simulation consists of a scenario that is built up from
interacting models. The models interact using a set of rules but there is cur-
rently no rules that verify model behaviour when a scenario are constructed.
Previous research efforts in the simulation environment attempted to address
the the need for a standard notation for documentation of the simulation models.
This proved to be problematic and one of the suggestions for further research was
to investigate the use ontologies in the simulation environment. The suggestion
according to the DSR process is therefore that a formal ontology is created to
address the above mentioned needs for the simulation environment.
Fig. 3. The Design Research Process on the left, and the Adaptive Methodology Pro-
cess on the right
3.3 Development
The ontology was build using the approach followed by the researchers who
develop the Adaptive Methodology [22], and was chosen for its lightweight, in-
cremental approach. Figure 3 depicts the development process steps as well as
the alignment with the design process.
Page 104 of 110
8 Lombard, Gerber and van der Merwe
– Scope and Purpose: The first step is to scope the purpose and the ex-
tent of the ontology. In the case of a domain ontology, the concepts of the
domain must be included. It is not necessary to include all the concepts of
the domain. The level of detail will be determined by the purpose of the
ontology.
– The Use of Existing Structures: There are several documents, structures
and sources available in the OSSIM simulation environment available to use
in order to gather information to develop the ontology and to, for example,
make a list of the concepts in the simulation. Modelling reports, installation
guides, white papers and technical documentation, as well as the source
code of the system and the documented test point configurations were used
as input into the ontology development process.
– The Prototype: The prototype structure is the first version of the ontology
that is operational. The prototype for the simulation environment contains
only a selected set of components from the domain. The concepts are on a
high level and the nested structures of complex concepts were not included
in the prototype. The prototype was developed in Protégé and is illustrated
in Figure 4 on the left.
The prototype is a proof-of-concept and in this project it played an impor-
tant role to demonstrate the feasibility of the suggested solution. The pro-
totype ontology supported the role of an ontology in the simulation system
environment, and supported an ontology as a solution to a shared, common
vocabulary. The tools also provided graphical views of the concepts defined
in the ontology.
– Development of the Working Ontology: During this phase the proto-
type ontology was expanded by adding concepts from the domain not previ-
ously included in the ontology, as well as developing new functionality. The
working ontology contains a full set of domain concepts that describe the
simulation models and model properties and is called Simtology. The next
section describes Simtology in more detail, as well as how Simtology is used
in CmSim.
3.4 Description of Simtology
To do a simulation in CmSim, a scenario must be set up to act as input to
the simulation. The scenario consists of various configuration files but the main
file is the scenario file itself, which contains links to all other files necessary to
describe a scenario and the components in it. Although the prototype already
contained enough information to set up basic scenarios, Simtology contains all
the concepts in the domain of CmSim.
The first task was thus to expand the prototype to present not only the
basic objects, but all the possible objects in the CmSim domain. The classes
and properties were expanded. The following list describes the concepts and
properties defined in Simtology.
– Concepts: In Simtology, an example of a concept representing all the indi-
vidual aircrafts modelled in the simulation environment, is Aircraft. Figure
Page 105 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 9
Fig. 4. Concepts from the prototype ontology on the left, and concepts in the final
version of Simtology on the right
4 depicts an extract of the top-level concepts defined in Simtology, where the
concepts were selected to present those in a simulation scenario. The main
concepts in Simtology are the Moving, Observer and Scenario concepts. The
choice of concepts relied heavily on the structure of the simulation configu-
ration files. Therefore objects of type Moving have specific behaviour in the
simulation and belong together in a concept.
– Individuals: Individuals are asserted to be instances of specific concepts.
Specific scenarios can be build by choosing individuals from the ontology
and thus creating an individual scenario.
ScenarioC130 is an individual of the Scenario concept that uses a specific
type of aircraft.
– Object Properties: Object properties are used to link individuals to each
other. In Simtology, a scenario must have a clock object, so having a clock
object is an object property of the scenario concept. The name of the prop-
erty is “hasClock“ and links an individual of class Clock to an individual
from class Scenario.
In Simtology the main object properties belong to a scenario. The following
properties are sufficient to denote a valid scenario that can run in a simula-
tion: ScenarioC130 hasClock Clock10ms
ScenarioC130 hasTerrain TerrainBeachFynbos
ScenarioC130 hasMoving C130Flying120knots
ScenarioC130 hasObserver SAMTypeA
ScenarioC130 hasAtmosphere MidLatitudeSummer
Page 106 of 110
10 Lombard, Gerber and van der Merwe
– Data Properties: Data properties were added to Simtology to add data to
individuals. Examples of data properties are geometric locations of moving
objects, or data belonging to the class Clock, as depicted below:
Clock10ms hasInterval 10ms and Clock10ms hasStopTime 10sec
Functionality: A scenario can be complex and rules were built in to ensure that
a valid scenario is constructed, for instance only certain types of flares can be
used as a valid countermeasure on a specific aircraft. After building the scenario
in the ontology, the scenario can be processed by a reasoner. The reasoners are
used to compute the inferred ontology class hierarchy and to do consistency
checking after a scenario is created.
Additional functionalities were developed for use with Simtology such as the
integration of the ontology with the graphical user interface (GUI) used to set
up the simulation. The ontology is used to populate the elements in the inter-
face, resulting in several advantages such as that only one source of simulation
information has to be maintained, as well as that the ontology can be used to
change the language displayed in the GUI .
Functionalities were also developed to write out scenarios created in the
ontology to files that can act as input to the simulation. This made it possible
that a scenario can first be checked for logical correctness before it is run in
the simulation. Modelling errors not handled by the simulation software are
handled early in the simulation process by using the reasoning technology in the
ontology. By having a scenario defined in the ontology, it is possible to export a
high-level description of a scenario and its components to be used for reporting
and documentation of simulation studies.
Testing of Simtology Testing the ontology was an important step towards
creating a useful Simtology. When an ontology is small with a few concepts, it
is easier to identify modelling problems but when there are large numbers of
concepts with complex relationships, it is important to test the ontology regu-
larly in order to avoid inconsistencies immediately and eliminate rework. During
ontology verification the focus was mainly to ensure that the ontology was built
correctly and that the ontology concepts match the domain it represents. The
test phase of the ontology is part of the adaptive methodology process and this
phase complements the evaluation phase of the design research process.
4 Evaluation
In Section 3.2, the simulation system environment was discussed. In order to
evaluate the use of Simtology in the simulation system and the contribution it
has for the improvement of the environment, the issues mentioned in Section
3.2 are used as evaluation criteria. The identified issues are 1) different users; 2)
model complexity; 3) reference models; and 4) model interaction. When evalu-
ated against the identified issues, Simtology provided the necessary solutions.
Page 107 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 11
– Different users: Simtology provided a common, shared ’language’ to as-
sist with eliminating ambiguities and the inconsistent use of terminology by
the different users of the system. The feedback by all concerned users was
positive. An example of how Simtology assisted with regards to a common
understanding is in the use of ambiguous terms. Some terms in the simulation
had different meanings depending on the user using it and the application
it was used for. An example of such a term is countermeasure, which was
vague and previously many different types of countermeasures existed. In
Simtology the concept Countermeasure was defined in such a way that it
can be used as an explanatory tool to illustrate the different countermeasures
available in the simulation as well as the use of each countermeasure.
The Protégé editor allows for several ways to communicate the ontology, for
example a graphical display of the concepts and the relations in the ontology
A visual display of the different components in the simulation leads to better
communication between all the people involved.
– Model complexity: Simtology formally defined the concepts, properties
and individuals necessary for the construction of input models. When a user
uses Simtology to construct her input model, the appropriate level of detail
and complexity of the input models are specified.
– Reference models: Simtology provides a reference model for all the dif-
ferent users of the system to create their specific input models from. After
introducing Simtology, very few problems were experienced by users when
constructing simulation models because Simtology acted as a reference model
informed their specific model design.
– Model Interaction: A simulation consists of a scenario that is build up
from interacting models. Simtology provides a common shared language to
be used in the simulation environment for both users and when interacting
with other applications. The definitions of concepts in the system are kept
in Simtology and made available to applications in the environment such as
the Graphical User Interface.
As a final evaluation, the guidelines proposed by Hevner et al. [6] for a design
research artefact were used to evaluate and present the research process
followed to develop Simtology. This discussion is outside the scope of this
paper but it was demonstrated that the construction of Simtology followed
the proposed guidelines.
5 Conclusion and Future Work
The outcome of the research project was Simtology, a domain ontology for the
simulation environment that contains the model information for simulation sce-
narios. An added benefit was that the process to analyse the contents of the
simulation environment to construct the ontology clarified the knowledge in the
domain.
During the construction of Simtology, the following observations were made:
Page 108 of 110
12 Lombard, Gerber and van der Merwe
– With regards to modelling, it is important to distinguish part-of from subclass-
of. An aircraft body is part of an aircraft, not part of a specific type of
aircraft.
– It is important to correctly model roles. Modelling a missile as an observer
in the simulation means that it can never be used in the simulation as an
object of type moving. In Simtology, a missile can therefore never be used in
a different role.
– Another important modelling decision has to do with the modelling of indi-
viduals vs. concepts. This decision has an impact on how the ontology could
ultimately be used. The choice between concept and individual is often con-
textual and application-dependent but it needs to be evaluated in one of the
development cycles.
– The development and use of the ontology should be an iterative process. As
new functionality is added, it must be tested, used and evaluated. Exist-
ing functionality is maintained by making changes where necessary. Proper
version control is therefore also necessary when constructing ontologies.
Several advantages of having an ontology in the simulation environment
emerged after the ontology was created. The ontology can, for instance, be used
in training exercises to show aircraft personnel the technical detail of the coun-
termeasures deployed on the aircraft. Furthermore, the simulation environment
is always expanding and improving through the addition of new models, the ad-
dition of new properties to existing entities in the system or through the addition
of new functionality to entities. Future versions of the ontology need to incor-
porate these changes and there should therefore always be future expansions to
the Simtology ontology. Furthermore, Simtology should ideally be expanded to
not only include concepts in CmSim, but also in the Optronic Scene Simulator.
One of the planned functions to be developed is to reverse engineer previously
run simulations and add the scenario descriptions of those simulations to the
ontology.
References
1. Birchenall, R.P., Richardson, M.A., Butters, B., Walmsley, R.: Modelling an in-
frared man portable air defence system. Infrared Physics & Technology (July 2010)
2. Willers, C., Willers, M.: Ossim: Optronics scene simulator white paper. Technical
report, Council for Scientific and Industrial Research (2011)
3. Gruber, T.R.: A translation approach to portable ontology specifications. Knowl-
edge Acquisition 5(2) (1993) 199–220
4. Baader, F., Horrocks, I., Sattler, U.: Description logics as ontology languages for
the semantic web. In Hutter, D., Stephan, W., eds.: Mechanizing Mathematical
Reasoning: Essays in Honor of Jörg H. Siekmann on the Occasion of His 60th
Birthday. Volume 2605 of Lecture Notes in Artificial Intelligence. Springer-Verlag
(2005) 228–248
5. Noy, N.F., McGuiness, D.L.: Ontology development 101: A guide to creating your
first ontology. Technical report, Stanford Knowledge Systems Laboratory (2001)
Page 109 of 110
Ontology Use in the Development of Military Aircraft Countermeasures 13
6. Hevner, A.R., March, S.T., Park, J., Ram, S.: Design Science in Information
Systems Research. MIS Quarterly 28(1) (2004) 75–105
7. Guarino, N.: Formal ontology and information systems. In Guarino, N., ed.:
Proceedings of the First International Conference on Formal Ontologies in Infor-
mation Systems (FOIS-98), June 6-8, 1998, Trento, Italy, IOS Press, Amsterdam,
The Netherlands (1998) 3–15
8. OWL: Owl2 web ontology language. Available at http://www.w3.org/TR/owl2-
overview. [1 April 2011]
9. Protege: The protege ontology editor. Available at http://protege.stanford.edu.
[13 April 2011]
10. Gáevic, D., Djuric, D., Devedı́c, V.: Model Driven Engineering and Ontology
Development. 2. edn. Springer, Berlin (2009)
11. Schlenoff, C., Washington, R., Barbera, T.: An intelligent ground vehicle ontology
to enable multi-agent system integration. In: Integration of Knowledge Intensive
Multi-Agent Systems. (2005) 169–174
12. Nagle, J.A., Richmond, P.W., Blais, C.L., Goerger, N.C., Kewley, R.H., Burk, R.K.:
Using an ontology for entity situational awareness in a simple scenario. The Journal
of Defense Modeling and Simulation: Applications, Methodology, Technology 5(2)
(2008) 139–158
13. Tsarkov, D., Horrocks, I.: FaCT++ description logic reasoner: System description.
In: Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2006). Volume
4130 of Lecture Notes in Artificial Intelligence., Springer (2006) 292–297
14. Bock, J., Haase, P., Ji, Q., Volz, R.: Benchmarking OWL Reasoners. CEUR
Workshop Proceedings (June 2008)
15. Benjamin, P., Patki, M., Mayer, R.: Using ontologies for simulation modeling.
In: Proceedings of the 38th conference on Winter simulation. WSC ’06, Winter
Simulation Conference (2006) 1151–1159
16. Mandrick, L.B.: Military ontology. http://militaryontology.com/
17. Valente, A., Holmes, D., Alvidrez, F.C.: Using a military information ontology to
build semantic architecture models for airspace systems. In: Aerospace Conference,
2005 IEEE. (March 2005) 1–7
18. Winklerova, Z.: Ontological approach to the representation of military knowledge.
Technical report, Military Academy in Brno, Command and Staff Faculty, Czech
Republic (2003)
19. Smart, P.R., Russell, A., Shadbolt, N.R., Shraefel, M.C., Carr, L.A.: Aktivesa.
Comput. J. 50 (November 2007) 703–716
20. Hevner, A., Chatterjee, S. In: Evaluation. Volume 22 of Integrated Series in Infor-
mation Systems. Springer US (2010) 109–120
21. Vaishnavi, V., Kuechler, W.: Design research in information systems. Available at
http://desrist.org/design-research-in-information-systems/ Last Updated 16 Au-
gust 2009 (January 2004)
22. Bergman, M.: A new methodology for building lightweight, domain ontologies.
Available at http://www.mkbergman.com/908/a-new-methodology-for-building-
lightweight-domain-ontologies/ (2010)
Page 110 of 110