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