Copyright c 2013 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. Modularity has been and continues to be one of the central research topics in ontology engineering. The number of ontologies available, as well as their size, is steadily increasing. There is a large variation in subject matter, level of specification and detail, intended purpose and application. Ontologies covering different domains are often developed in a distributed manner; contributions from different sources cover different parts of a single domain. Not only is it difficult to determine and define interrelations between such distributed ontologies, it is also challenging to reconcile ontologies which might be consistent on their own but jointly inconsistent. Further challenges include extracting the relevant parts of an ontology, re-combining independently developed ontologies in order to form new ones, determining the modular structure of an ontology for comprehension, and the use of ontology modules to facilitate incremental reasoning and version control.
Modularity is envisaged to allow mechanisms for easy and flexible reuse, combination, generalization, structuring, maintenance, collaboration, design patterns, and comprehension. This is analogous to the role of modularity in software engineering, where there are well-understood notions of modularity that have led to generally accepted and widely supported mechanisms for the named tasks. In contrast, modularity for ontologies is still an active research field with open questions because existing approaches are heterogeneous and less universally applicable. For ontology engineering, modularity is central not only to reducing the complexity of understanding ontologies, but also to maintaining, querying and reasoning over modules. Distinctions between modules can be drawn on the basis of structural, semantic, or functional aspects, which can also be applied to compositions of ontologies or to indicate links between ontologies.
In particular, reuse and sharing of information and resources across ontologies depend on purpose-specific, logically versatile criteria. Such purposes include “tight” logical integration of different ontologies (wholly or in part), “loose” association and information exchange, the detection of overlapping parts, traversing through different ontologies, alignment of vocabularies, module extraction possibly respecting privacy concerns and hiding of information, etc. Another important aspect of modularity in ontologies is the problem of evaluating the quality of single modules or of the achieved overall modularization of an ontology. Again, such evaluations can be based on various (semantic or syntactic) criteria and employ a variety of statistical/heuristic or logical methods.
Recent research on ontology modularity has produced substantial results and approaches towards foundations of modularity, techniques of modularization and modular developments, distributed and incremental reasoning, as well as the use of modules in different application scenarios, providing a foundation for further research and development. Since the beginning of the WoMO workshop series, there has been growing interest in the modularization of ontologies, modular development of ontologies, and information exchange across different modular ontologies. In real life, however, integration problems are still mostly tackled in an ad-hoc manner, with no clear notion of what to expect from the resulting ontological structure. Those methods are not always efficient, and they often lead to unintended consequences, even if the individual ontologies to be integrated are widely tested and understood.
Topics covered by WoMO include, but are not limited to:
– Kinds of modules and their properties – Modules vs. contexts – Design patterns – Granularity of representation
– Conservativity and syntactic approximations for modules – Modular ontology languages – Reconciling inconsistencies across modules – Formal structuring of modules – Heterogeneity Algorithmic Approaches – Distributed and incremental reasoning – Modularization and module extraction – Sharing, linking, and reuse – Hiding and privacy – Evaluation of modularization approaches – Complexity of reasoning – Implemented systems Application Areas – Modularity in the Semantic Web – Life Sciences – Bio-Ontologies – Natural Language Processing – Ontologies of space and time – Ambient intelligence – Social intelligence – Collaborative ontology development and ontology versioning Previous events. The WoMO 2013 workshop follows a series of successful events that have been an excellent venue for practitioners and researchers to discuss latest work and current problems. It is intended to consolidate cuttingedge approaches that tackle the problem of ontological modularity and bring together researchers from different disciplines who study the problem of modularity in ontologies at a fundamental level, develop design tools for distributed ontology engineering, and apply modularity in different use cases and application scenarios. Previous editions of WoMO are listed below. The links refer to their homepages and proceedings. WoMO 2006. The 1st workshop on modular ontologies, co-located with ISWC 2006, Athens, Georgia, USA. Invited speakers were Alex Borgida (Rutgers) and Frank Wolter (Liverpool). Organizers and program chairs were http://www.cild.iastate.edu/events/womo.html http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-232 WoMO 2007. The 2nd workshop, co-located with K-CAP 2007, Whistler BC, Canada. The invited speaker was Ken Barker (Texas at Austin). http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-315 WoRM 2008. The 3rd workshop in the series, co-located with ESWC 2008, Tenerife, Spain, entitled ‘Ontologies: Reasoning and Modularity’ had a special emphasis on reasoning methods. http://dkm.fbk.eu/worm08 http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-348 WoMO 2010. The 4th workshop in the series, co-located with FOIS 2010, Toronto, Canada. Invited speakers were Simon Colton (London) and Marco Schorlemmer (Barcelona). http://www.informatik.uni-bremen.de/%7Eokutz/womo4 http://www.booksonline.iospress.nl/Content/View.aspx?piid=16268 WoMO 2011. The 5th workshop in the series, co-located with ESSLLI 2011, Ljubljana, Slovenia. Invited speakers were Stefano Borgo (Trento), Stefan Schulz (Graz) and Michael Zakharyaschev (London). http://www.informatik.uni-bremen.de/%7Eokutz/womo5 http://www.booksonline.iospress.nl/Content/View.aspx?piid=20369 WoMO 2012. The 6th workshop in the series, co-located with ICBO/FOIS 2012, Graz, Austria. Invited speakers were Thomas Eiter (Vienna) and Luciano Serafini (Trento). http://www.informatik.uni-bremen.de/∼ts/womo2012/ http://ceur-ws.org/Vol-875/ Organizers of the previous editions and editors of the proceedings were Diego Calvanese (Bozen-Bolzano) – 2008; Bernardo Cuenca Grau (Manchester, Oxford) – 2007, 2008, 2010; Peter Haase (Karlsruhe) – 2006; Jie Bao (Rensselaer) – 2010; Joana Hois (Bremen) – 2010; Vasant Honovar (Iowa State) – 2006, 2007; Oliver Kutz (Manchester, Bremen) – 2006, 2010, 2011; Ulrike Sattler (Manchester) – 2008; Anne Schlicht (Mannheim) – 2007; Thomas Schneider (Bremen) – 2011, 2012; Luciano Serafini (Trento) – 2008; Evren Sirin, (Clark & Parsia LLC, Washington DC) – 2008; York Sure (Karlsruhe) – 2006; Andrei Tamilin (Trento) – 2006, 2008; Michael Wessel (Hamburg) – 2008; Dirk Walther (Madrid) – 2012; Frank Wolter (Liverpool) – 2007, 2008 This volume contains the papers presented at the 7th International Workshop on Modular Ontologies (WoMO 2013) held on September 15, 2013 in Corunna, Spain as a satellite event of the conference LPNMR 2013. We received 9 submissions. Each submission was reviewed by three program committee members. The committee decided to accept five papers for long or short presentations. The program also included two invited talks: – Till Mossakowski (University of Bremen, Germany)
– George Vouros (University of Piraeus, Greece)
Acknowledgments. We would like to thank the PC members and the additional reviewers for their timely reviewing work, our invited speakers for delivering keynote presentations at the workshop, and the authors and participants for contributing to the workshop program. We would also like to thank the organizers of LPNMR 2013 for hosting the WoMO workshop, the IAOA and SINTELNET for their generous financial support, and the EasyChair developers for greatly simplifying the work of the program committee.
September 27, 2013 Manchester, Toronto, Madrid and Dresden Chiara Del Vescovo
Torsten Hahmann
David Pearce
Dirk Walther
Kenneth Baclawski Eva Blomqvist Alex Borgida Stefano Borgo
Northeastern University, Boston, USA Link¨oping University, Sweden Rutgers University, Piscataway, USA Laboratory for Applied Ontology, ISTC-CNR, Trento, Italy University of Leipzig, Germany Raytheon BBN Technologies, Ann Arbor, USA The University of Manchester, UK Technical University of Vienna, Austria The John Paul II Catholic University of Lublin,
Poland Dagmar Gromann Vienna University of Economics and Business,
Austria Michael Gruninger University of Toronto, Canada Torsten Hahmann (co-chair) University of Toronto, Canada Robert Hoehndorf University of Cambridge, UK Dieter Hutter DFKI GmbH, Bremen, Germany Tomi Janhunen Aalto University, Finland Pavel Klinov University of Ulm, Germany Christoph Lange University of Birmingham, UK Thomas Meyer CSIR Meraka Institute, Pretoria, South Afrika Leo Obrst MITRE, McLean, VA, USA David Pearce (co-chair) Universidad Polit´ecnica de Madrid, Spain Marco Schorlemmer IIIA-CSIC, Barcelona, Spain Luciano Serafini Fundazione Bruno Kessler, Trento, Italy Dmitry Tsarkov The University of Manchester, UK Dirk Walther (co-chair) TU Dresden, Germany Konev, Boris Koopmann, Patrick Kutz, Oliver
Lange, Christoph
C G K L M N P R S V Paschke, Adrian Rezaeian, Amin Sch¨afermeier, Ralph Schmidt, Renate Mart´ın-Recuerda, Francisco Mossakowski, Till Naghibzadeh, Mahmoud Vouros, George A.
W Walther, Dirk Wolter, Frank
1 The Distributed Ontology, Modelling and
Specification Language – DOL Till Mossakowski1,2, Oliver Kutz1, Mihai Codescu3, and Christoph Lange4 1 Collaborative Research Centre on Spatial Cognition, University of Bremen 2 DFKI GmbH Bremen 3 University of Erlangen-Nürnberg 4 School of Computer Science, University of Birmingham Abstract. There is a diversity of ontology languages in use, among them OWL, RDF, OBO, Common Logic, and F-logic. Related languages such as UML class diagrams, entity-relationship diagrams and object role modelling provide bridges from ontology modelling to applications, e.g. in software engineering and databases.
Another diversity appears at the level of ontology modularity and relations among ontologies. There is ontology matching and alignment, module extraction, interpolation, ontologies linked by bridges, interpretation and refinement, and combination of ontologies.
The Distributed Ontology, Modelling and Specification Language (DOL) aims at providing a unified meta language for handling this diversity. In particular, DOL provides constructs for (1) “as-is” use of ontologies formulated in a specific ontology language, (2) ontologies formalised in heterogeneous logics, (3) modular ontologies, and (4) links between ontologies. This paper sketches the design of the DOL language. DOL will be submitted as a proposal within the OntoIOp (Ontology Integration and Interoperability) standardisation activity of the Object Management Group (OMG). 1
OWL is a popular language for ontologies.5 Yet, the restriction to a decidable description logic often hinders ontology designers from expressing knowledge that cannot (or can only in quite complicated ways) be expressed in a description logic. A practice to deal with this problem is to intersperse OWL ontologies with first-order axioms, e.g. in the case of bio-ontologies where mereological relations such as parthood are of great importance, though only partly definable in OWL. However, these remain informal annotations to inform the human designer, rather than first-class citizens of the ontology with formal semantics and impact on reasoning. One goal of the Distributed Ontology, Modelling and Specification Language (DOL), discussed in detail in this paper, is therefore to equip such heterogeneous ontologies with a precise semantics and proof theory. 5 We adopt the completely formal position that an ontology is a formal theory in a given ontology language, and that an ontology language is any logical language that some community considers suitable for ontology design.
A variety of languages is used for formalising ontologies. Some of these, such as RDF (mostly used for linked data), OBO and certain6 UML class diagrams, can be seen more or less as fragments and notational variants of OWL, while others, such as F-logic and Common Logic (CL), clearly go beyond the expressiveness of OWL.
We face this diversity not by proposing yet another ontology language that would subsume all the others, but by accepting this pluralism in ontology languages and by formulating means (on a sound and formal semantic basis) to compare and integrate ontologies written in different formalisms. This view is a bit different from that of unifying languages such as OWL and CL, which are meant to be “universal” formalisms (for a certain domain/application field), into which everything else can be mapped and represented. While such “universal” formalisms are clearly important and helpful for reducing the diversity of formalisms, it is still a matter of fact that no single formalism will be the Esperanto that is used by everybody [23]. It is therefore important to both accept the existing diversity of formalisms and to provide means of organising their coexistence in a way that enables formal interoperability among ontologies.
DOL enjoys the following distinctive features:
– modular and distributed ontologies are specially supported,
– ontologies can not only be aligned (as in BioPortal [37] and NeON [
The paper is organised as follows: we first discuss the theoretical foundations of DOL in Section 2, followed by a sketch of the DOL language itself in Section 3. Section 4 briefly discusses the DOL-enabled, web-based ontology repository engine Ontohub, and Section 5 concludes. 2
Foundations of the Distributed Ontology, Modelling
and Specification Language (DOL)
The Distributed Ontology, Modelling and Specification Language (DOL)7 aims
at providing a unified framework for (1) “as-is” use of ontologies formulated in
6 Those avoiding qualified associations (amounting to identification constraints),n-ary
relations (for n > 2) and stereotyping.
7 DOL has formerly been standardised within ISO/TC 37/SC 3. The OntoIOp
(Ontology Integration and Interoperability) activity is now being continued at OMG,
see the project page at http://ontoiop.org.
a specific ontology language, (2) ontologies formalised in heterogeneous logics,
(3) modular ontologies, and (4) links between ontologies. Historically, the design
of DOL has inherited many ideas and features (1) discussed in the Workshop on
Modular Ontologies series [
A distributed ontology in DOL consists of modules formalised in basic ontology languages, such as OWL (based on description logic) or Common Logic (based on first-order logic with some second-order features). These modules are serialised in the existing syntaxes of these languages in order to facilitate reuse of existing ontologies. DOL adds a meta-level on top, which allows for expressing heterogeneous ontologies and links between ontologies.9 Such links include (heterogeneous) imports and alignments, conservative extensions (important for studying ontology modules), and theory interpretations (important for reusing proofs). Thus, DOL gives ontology interoperability a formal grounding and makes heterogeneous ontologies and services based on them amenable to automated verification. The basic syntax and semantics of DOL has been introduced in [35, 34], and the general theory of heterogeneous specifications for ontologies in [22]. DOL uses internationalised resource identifiers (IRIs, the Unicode-aware superset of URIs) for all entities of distributed ontologies to make them referenceable on the Web. 2.1
Foundations
The large variety of logical languages in use can be captured at an abstract
level using the concept of institutions [
Institutions also provide a model theory, which introduces semantics for the language and gives a satisfaction relation between the models and the sentences of a signature. The only restriction imposed is the satisfaction condition, which captures the idea that truth is invariant under change of notation (and enlargement of context) along signature morphisms. This relies on two further components of institutions: the translation of sentences along signature morphisms, and 8 See http://ifipwg13.informatik.uni-bremen.de 9 The languages that we call “basic” ontology languages here are usually limited to one logic and do not provide meta-theoretical constructs. the reduction of models against signature morphisms (generalising the notion of model reduct known from logic).
It is also possible to complement an institution with a proof theory, introducing a derivability relation between sentences, formalised as an entailment system [30]. In particular, this can be done for all logics that have so far been in use in DOL.
Example 1. OWL signatures consist of sets of atomic classes, individuals and properties. OWL signature morphisms map classes to classes, individuals to individuals, and properties to properties. For an OWL signature Σ , sentences are subsumption relations between classes or properties, membership assertions of individuals in classes and pairs of individuals in properties, complex role inclusions, and some more. Sentence translation along a signature morphism simply replaces non-logical symbols with their image along the morphism. The kinds of symbols are class, individual, object property and data property, respectively, and the set of symbols of a signature is the union of its sets of classes, individuals and properties. Models are (unsorted) first-order structures that interpret concepts as unary and properties as binary predicates, and individuals as elements of the universe of the structure, and satisfaction is the standard satisfaction of description logics. This gives us an institution for OWL.
In this framework, a basic ontology O over an institution I is a pair (Σ, E ) where Σ is a signature and E is a set of Σ -sentences. Given a basic ontology O, we denote by Sig(O) the signature of the ontology. An ontology morphism σ : (Σ 1, E1) → (Σ 2, E2) is a signature morphism σ : Σ 1 → Σ 2 such that σ (E1) is a logical consequence of E2.
Several notions of translations between institutions can be introduced. The
most frequently used variant are institution comorphisms [
Figure 1 shows a conceptual hierarchy of mappings.10 Mappings are split
along the following dichotomies:
– translation versus projection: a translation embeds or encodes a logic into
another one, while a projection is a forgetful operation (e.g. the
projection from first-order logic to propositional logic forgets predicates with arity
greater than zero). Technically, the distinction is that between institution
comorphisms and morphisms.
– plain mapping versus simple theoroidal mapping [
Mappings can also be classified according to their accuracy; see [33] for
details. Sublogics are the most accurate mappings: they are syntactic subsets.
Embeddings come close to sublogics, like injective functions come close to subsets. A
mapping can be faithful in the sense that logical consequence (or logical
deduction) is preserved and reflected, that is, inference systems and reasoning engines
for the target logic can be reused for the source logic (along the mapping).
(Weak) exactness is a technical property that guarantees this faithfulness even
in the presences of ontology structuring operations [
A Graph of Logic Translations Figure 2 is a revised and extended version of the graph of logics and translations introduced in [33]. New nodes include UML class diagrams, OWL-Full (i.e. OWL with an RDF semantics instead of description logic semantics), and Common Logic without second-order features (CL− ). We have defined the translations between most of these logics in earlier publications [35, 33]. The definitions of the DOL conformance of some central standard ontology languages and translations among them will be given as annexes to the standard and published in an open registry, which is also the place where the remaining definitions will be maintained (cf. Section 2.3). 2.3
A Registry for Ontology Languages and Mappings Beyond those shown so far, it will be possible to use any (future) language or mapping (in the sense of Section 2.1) with DOL. We host a registry to which EL++ (OWL 2 EL)
DL-LiteR (OWL 2 QL)
DL-RL (OWL 2 RL)
Prop UML-CD Schema.org
DDLOWL ECoOWL
EER
SROIQ (OWL 2 DL) ECoFOL
OWL-Ful
OBOOWL OBO 1.4 F-logic
RDF RDFS FOL= FOLms= HOL subinstitute theoroidal subinstitute simultaneously exact and model-expansive comorphisms model-expansive comorphisms grey: no fixed expressivity green: decidable ontology languages yellow: semi-decidable orange: some second-order constructs red: ful second-order logic the community can contribute descriptions of any languages and mappings11, as well as logics and serialisations (i.e. concrete syntaxes of languages).12 The LoLa (“logics and languages”) ontology formalises these notions [25].LoLa and its main instance, the registry, form themselves a distributed ontology. The registry is written in RDF, LoLa in OWL plus some Common Logic axioms.
Figure 3 shows the top-level classes of LoLa’s OWL module, axiomatising logics, languages, and mappings. Object-level classes (that is, classes providing the vocabulary for expressing distributed ontologies) comprise ontologies, their constituents (namely symbols and sentences), as well as links between ontologies. Mappings are modelled as shown in Figure 1: by a hierarchy of properties corresponding to the different types of edges in Figure 2. The full LoLa ontology is available at http://purl.net/dol/1.0/rdf#. 11 As distributed ontologies refer to languages and mappings by IRIs, third parties may also set up their own, decentral registry extensions. 12 The OWL 2 DL language is, e.g., exactly as expressive as the logic SROIQ(D) [17], and it can be serialised in the text-based Manchester syntax or as XML. 3.1
Motivation Many (domain) ontologies are written in DLs such as SROIQ and its profiles. These logics are characterised by having a rather fine-tuned expressiveness, exhibiting (still) decidable satisfiability problems, whilst being amenable to highly optimised implementations.
However, expressiveness beyond standard DLs is required for many foundational ontologies (as well as bio-medical ontologies), for instance Dolce13, BFO14, or GFO15. Moreover, for practical purposes, these foundational ontologies also come in different versions ranging in expressiveness, typically between OWL (e.g. Dolce Light, BFO-OWL) and first-order (Dolce, GFO) or even second-order logic (BFO-Isabelle).
The relation between such different versions, OWL and first-order, may be recorded in various ways. In some cases it is primarily discussed in the research literature, see Keet’s mereo-topological ontology [18] for an example, or it is described in the OWL ontology within a comment, not carrying formal semantics. Such a comment might only contain an informal explanation of how the OWL approximation was obtained (Dolce Light is an example), but it might also describe a fully formal, axiomatised first-order extension of the OWL ontology.
Consider the BFO-OWL object property temporalPartOf. The OWL axiomatisation states this to be a transitive subproperty of occurrentPartOf, and the inverse of hasTemporalPart.16 This property is, however, annotated in a rich way, containing example usages, a richer first-order axiomatisation of this property with pointers to the corresponding axioms in the first-order version, as well as natural language renderings of these axioms. The logical part of this annotation may be captured in DOL as follows: an OWL ontology first lists the entire OWL axiomatisation of BFO. In a second step, we import this OWL ontology along a translation to Common Logic, and subsequently extend the resulting firstorder version of BFO-OWL with the first-order axioms previously only listed as comments. We obtain a two-level specification of BFO: the original OWL part (supported by OWL reasoners) and the full first-order part in Common Logic (amenable to first-order theorem proving and non-conservatively extending the OWL consequences). 3.2
DOL Syntax and Semantics The DOL language is not “yet another ontology language”, but ameta language for expressing relations between ontologies. Therefore, any ontology written in any conforming ontology language also is a DOL ontology. This has the clear 13 See http://www.loa.istc.cnr.it/DOLCE.html 14 See http://www.ifomis.org/bfo/ 15 See http://www.onto-med.de/ontologies/gfo/ 16 Parthood, typically understood as an anti-symmetric relation in mereology, is the canonical example of a relation that cannot be adequately formalised in OWL; a corresponding comment can be found in many bio-medical ontologies. advantage that users can leave their ontologies as they are when working with DOL.
DOL provides two main abstract syntax categories: 1. Modular and heterogeneous ontologies. Such an ontology is written in a modular way, with the help of structuring operations. The semantics of ontologies is given by a signature and a class of models. In some cases, we can additionally provide a theory-level semantics of ontologies, as a signature and a class of sentences that, if it exists, agrees with the model-level semantics (that is, the model class is equal to the class of models satisfying the theory). We call an ontology flattenable if it has a theory-level semantics and elusive if it only admits a model-level semantics. This can be decided according to the outermost structuring operation on ontologies, as follows: Flattenable ontologies: basic ontologies, extension, union, translation, interpolate/forget, extract, reference, qualification, combination, bridge. Among these operations, interpolate/forget and extract can only be applied to flattenable ontologies.
Elusive ontologies: reduction, minimisation and maximisation.
For detailed definitions of these types of ontologies, see Section 3.3. 2. Distributed ontologies. These consist of of a list of declarations involving (possibly modular and/or heterogeneous) ontologies. These declarations can be ontology definitions (assigning a name to an ontology), interpretations (specifying a logical consequence relationship between ontologies), equivalences of ontologies (specifying that their model classes are in bijective correspondence), module relations (between ontologies and their modules), ontology alignments, and qualifications of the language, logic and/or serialisation. This will be detailed in Section 3.4. 3.3
Modular and Heterogeneous Ontologies A (possibly modular and/or heterogeneous) ontology can be one of the following: (a) a basic ontology O written inline, in a conforming ontology language and serialisation. The semantics is inherited from the ontology language. O can also be an ontology fragment, which means that some of the symbols or axioms may refer to symbols declared outside O (i.e. in an imported ontology). This is mainly used for extensions and equivalences. Here are two sample ontologies in OWL (using Manchester syntax) and Common Logic (using CLIF): Class: Woman EquivalentTo: Person and Female ObjectProperty: hasParent (cl-module PreOrder (forall (x) (le x x)) (forall (x y z) (if (and (le x y) (le y z)) (le x z)))) (b) an ontology qualified with the ontology language that is used to express it (written language l : O, where l identifies a language). Similarly, qualifications can also be by logic (written logic l : O), and/or serialisation (written syntax s : O).17 (c) an IRI reference to an ontology existing on the Web18, possibly abbreviated using prefixes.19 For example: %prefix(
co-ode: <http://owl.cs.manchester.ac.uk/co-ode-files/ontologies/> )% http://owl.cs.manchester.ac.uk/co-ode-files/ontologies/pizza.owl co-ode:pizza.owl (d) an extension of an ontology by new symbols and axioms, written O1 then O2, where O2 is an ontology (fragment) in a conforming ontology language. The resulting signature is that of O1, augmented with the symbols in O2. A model of an extension ontology is a model of this signature, that satisfies the axioms on O2 and is (when appropriately reduced) a model of O1. An extension can optionally be marked as conservative (%mcons or %ccons after the “then”). The semantics is that each O1-model must have at least one expansion to the whole extension O1 then O2 (for %mcons) resp. that each logical consequence of O1 then O2 is already one of O1 if it is over the signature of O1 (for %ccons). In case that O2 does not introduce any new symbols, the keyword %implied can be used instead of %ccons or %mcons; the extension then merely states intended logical consequences. The keyword %def stands for definitional extensions. This is similar to %mcons, but the model expansion must always exist uniquely. The following OWL ontology is an example for the latter:
Class Person
Class Female then %def
Class: Woman EquivalentTo: Person and Female (e) a union of two self-contained ontologies (not fragments), written O1 and O2.
Models of this union are those models that are (perhaps after appropriate reduction) models of both O1 and O2. For example, the class of commutative monoids can be expressed as algebra:Monoid and algebra:Commutative Forming a union of ontologies is a particularly common operation in the RDF logic, where it is known as merging graphs [15, section 0.3]; however, the RDF language provides no explicit syntax for this operation. When multiple RDF ontologies (“graphs”) contain statements about the same symbol (“resource”), i.e., syntactically, triples having the same subject, the effect 17 Some of the following listings omit obvious qualifications for readability. 18 Note that not all ontologies can be downloaded by dereferencing their IRIs. Implementing a catalogue mechanism in DOL-aware applications might remedy this problem. 19 Some of the following listings abbreviate IRIs using prefixes but omit the prefix bindings for readability. is that in the merged graph the resource will have all properties that have previously been stated about it separately. Different kinds of properties, e.g. multilingual labels, geodata, or outgoing links to external graphs, are often maintained in different RDF graphs, which are then merged; consider the following excerpt: { :UniBremen rdfs:label "Université de Brême"@fr . } and { :UniBremen geo:lat "53.108612"^^xsd:float . } and { :UniBremen owl:sameAs20
<http://dbpedia.org/page/University_of_Bremen> . } (f) a translation of an ontology to a different signature (written O with σ , where σ is a signature morphism) or into some ontology language (written O with translation ρ , where ρ is an institution comorphism). For example, we can combine an OWL ontology with a first-order axiom (formulated in Common Logic) as follows: ObjectProperty: isProperPartOf
Characteristics: Asymmetric
SubPropertyOf: isPartOf with translation trans:SROIQtoCL then
(if (and (isProperPartOf x y) (isProperPartOf y z)) (isProperPartOf x z)) Note that OWL can express transitivity, but not together with asymmetry. (g) a reduction of an ontology to a smaller signature Σ is written O reveal Σ .
Alternatively, it can be written O hide Σ , where Σ is the set of symbols to be hidden (i.e. this is equivalent to O reveal Sig(O) \ Σ ). The effect is an existential quantification over all hidden symbols. For example, when specifying a group in sorted first-order logic, using the CASL language, sort Elem ops 0: Elem; __+__: Elem * Elem -> Elem; inv: Elem -> Elem forall x,y,z . 0 + x = x . x + (y + z) = (x + y) + z . x + inv(x) = 0 reveal Elem, 0, __+__ revealing everything except the inverse operation inv results in a specification of the class of all monoids that can be extended with an inverse operation, i.e. the class of all groups with inverse left implicit.
Here is an example of hiding: ontology Pizza = %% a simplified remake of the Pizza ontology [16] Individual: TomatoTopping Individual: MozzarellaTopping DifferentFrom: TomatoTopping ObjectProperty: hasTopping Class: VegetarianTopping
EquivalentTo: { TomatoTopping, MozzarellaTopping, ... } 20 While owl:sameAs is borrowed from the vocabulary of OWL, it is commonly used in the RDF logic to link to resources in external graphs, which should be treated as if their IRI were the same as the subject’s IRI. Class: VegetarianPizza SubClassOf: some hasTopping VegetarianTopping ... end ontology Pizza_hide_VegetarianTopping =
Pizza hide VegetarianTopping end A reduction to a less expressive logic is written O hide along μ , where μ is an institution morphism. This is a common operation in TBox/ABox settings, where an ontology in an expressive language provides the terminology (TBox) used in assertions (ABox) stated in a logic that is less expressive but scales to larger data sets; OWL DL (whose logic is SROIQ) vs. RDF is a typical language combination: ontology TBoxABox =
Pizza hide along trans:SROIQtoRDF then language lang:RDF syntax ser:RDF/Turtle : { :myPizza :hasTopping
[ a :TomatoTopping ], [ a :MozzarellaTopping ] .
} (h) an interpolation of an ontology, either in a subsignature or a sublogic, optionally with respect to a logic L (written O keep in Σ with L, where Σ is a signature or a logic and L is a logic)21. The effect is that sentences not expressible in Σ are weakened or removed, but the resulting theory still has the same L-consequences. The “with L” is optional, it defaults to the logic of O. Technically, this is a uniform interpolant [41, 29]. In case that Σ is a sublogic, this is also called approximation [28]. For example, we can interpolate the first-order DOLCE mereology in OWL:22 DOLCE_Mereology keep in log:OWL Dually, O forget Σ with L interpolates O with the signature Sig(O)\Σ , i.e. Σ specifies the symbols that need to be left out. Cf. the notion of forgetting in [41, 29]. For example,
Pizza forget VegetarianTopping This has a theory-level semantics, i.e. yields a theory in the reduced signature (without VegetarianTopping). By contrast Pizza hide VegetarianTopping has a model-level semantics. (i) a module extracted from an ontology, written O extract c Σ with m. Here, Σ is a restriction signature (which needs to be a subsignature of Sig(O)), c is one of %mcons and %ccons, and m identifies a module extraction method. The extracted module is a subontology of O with signature larger than (or equal to) Σ , such that O is a conservative extension of the extracted module. 21 It is also possible to specify a signature and a logic simultaneously: O keep in Σ, L 1 with L2 22 Interpolants need not always exist, and even if they do, tools might only be able to approximate them. Dually, O remove c Σ with m extracts w.r.t. the signature Sig(O) \ Σ .23 For example, using the syntactic locality-* extraction method [38]: Pizza remove %mcons
VegetarianTopping with <http://example.org/onto/module/syntactic-locality-*> Table 1 illustrates some of the connections between (g)–(i). We have three ways of removing the class VegetarianTopping from the ontology Pizza: (1) using hiding, we keep the model class of Pizza, but just remove the interpretation of VegetarianTopping from each model. Note that the resulting ontology has VegetarianPizza SubClassOf:
Annotations: dol:iri (*) some hasTopping { TomatoTopping, MozzarellaTopping, ... } as a logical consequence. This is also a consequence of the corresponding uniform interpolant
Pizza forget VegetarianTopping which captures the theory of Pizza hide VegetarianTopping. Note that there is a subtle difference between (model-theoretic) hiding and (consequencetheoretic) forgetting: a model satisfying the theory of O hide Σ might itself not be a model of O hide Σ . In examples involving “with L”, the uniform interpolant can be weaker than the hiding, because it is only required to have the same logical consequences in some language L, and a formula like (*) might not be a formula of L. Finally, an extracted module does not contain (*), because it only selects a subontology, and Pizza does not contain (*). Note that while forget/keep and hide/reveal both work w.r.t. smaller signatures and sublogics, remove/extract does not work for sublogics. This is because remove/extract must always respect the conservative extension property, which may not be possible when projecting to a sublogic. And if conservativity cannot be guaranteed, then forget/keep can be used in any case. (j) a combination of ontologies, written combine O1, . . . , On L1, . . . , Lm. Here the Lj are links between ontologies, see below. For disambiguating the symbols in the combined ontology, the individual ontologies can be prefixed with labels, like n : O, which are scoped to the current distributed ontology. The simplest example of a combination is a disjoint union (we here translate OWL ontologies into many-sorted OWL in order to be able to distinguish between different universes of individuals): ontology Publications1 =
Class: Publication Class: Article SubClassOf: Publication
Class: InBook SubClassOf: Publication 23 Note that the resulting module can still contain symbols from Σ , because the resulting signature may be enlarged.
STAR AMEX 7000 6000 5000 y cn4000 e u req3000 F 2000 1000 0
STAR AMEX
Fig. 4. Frequency of module sizes for NCI? (left) and NCI?(≡) (right).
Figure 4 summarises our experimental results for modules extracted for axiom signatures. The figure shows the frequency ofAMEX and STAR-modules of a given size within NCI? and NCI?(≡) for the cases when the modules differ – which is in 13% and 68% of cases, respectively. For NCI?(≡) in the cases in which we find a difference the STAR module is always larger than the corresponding AMEX module with an average difference of 865.6 axioms. For NCI? in a few (87 cases) the STAR modules are smaller than the corresponding AMEX ones by an average difference of 6.9 axioms whereas in the rest of the cases the STAR modules are much larger with an average difference of 1427 axioms. We do not show the results for NCI?(v) since, as explained above for the experiments with random signatures, there is essentially no difference between AMEX and STAR-modules.
These experiments were carried out on a PC with an Intel i5 CPU @ 3.30GHz with 2GB of Java heap space available to the program. For NCI? the average time taken per extraction was just under 3s and the maximum time taken was 15s. Interestingly, in almost all experiments the QBF solver was called just once. Thus, in most cases the modules were computed purely syntactically and the QBF solver simply provided an assurance that the extracted axioms indeed constituted a depleting module. Only in 3% of all experiments the QBF solver identified separability causing axioms. The maximal number of separability causing axioms recorded in any single extraction was 4 and the maximal number of QBF solver calls themselves was 73.
Experiments with full NCI Although AMEX-modules are significantly smaller than
STAR-modules for acyclic TBoxes containing many concept equations, the
applications of AMEX alone are very limited since most ontologies contain additional
axioms such as disjointness axioms, role inclusions, and domain and range restrictions.
To tackle this problem we first observe that, in principle,AMEX can be applied to any
general TBoxes: given such a TBox T , one can split T into two parts T1 and T2, where
T1 is an acyclic ALCQI-TBox (and as large as possible) and T2 := T \ T1. Then
for any signature Σ it follows from the robustness properties [
Theorem 3. Let M ⊆ M0 ⊆ T be TBoxes and Σ a signature such that M0 is a depleting Σ-module of T and M is a depleting Σ-module of M0. Then M is a depleting Σ-module of T .
Since both AMEX and STAR compute depleting Σ-modules, given a signature Σ and ontology T one can extract an AMEX module from the STAR module (and vice versa) and have the guarantee the resulting module is still a depleting Σ-module of T . In this way, one can repeatedly extract from the output of one extraction approach again a module using the other approach until the sequence of modules becomes stable.
The following experiments are based on a naïve implementation of this hybrid approach and extract modules from the full version of NCI. Again we consider random concept signatures with varying amount of role names. The experiments shown in Figure 5 are based on 200 signatures for each concept signature size/role percentage combination and compare the average size of modules extracted using the hybrid approach and using STAR extraction only.
Role% 0% 25% 50% 75% 100% |Σ| traS ttrIaeed iffD% traS ttrIaeed iffD% traS ttrIeaed iffD% traS ttrIaeed iffD% traS ttrIaeed iffD% 100 5385.7 1949.5 176% 9569.8 6177.7 55% 13733.8 10339.0 33% 19486.4 16089.1 21% 23196.6 19810.2 17% 250 7298.6 3268.7 123% 11959.8 7963.9 50% 16072.1 12069.6 33% 20974.9 16978.8 24% 25141.0 21134.7 19% 500 9445.0 4827.6 96% 13165.1 8533.4 54% 16406.7 11767.0 39% 23046.8 18418.3 25% 27331.2 22691.9 20% 750 11070.2 6058.6 74% 15268.3 10235.9 49% 19696.2 14683.3 34% 23705.7 18689.6 27% 28917.3 23903.4 21% 1000 12370.7 7108.5 74% 16434.7 11174.0 47% 21978.6 16737.6 31% 25529.0 20286.5 26% 30218.5 24965.4 21%
For all signatures we found a reduction in the size of the module when iterated with the STAR module on its own being between 17% and 176% larger than the hybrid module.
In Figure 6, we show the results of our experiments for axioms signatures. They are based on 20 000 randomly selected axioms from the full NCI Thesaurus. 13% of such signatures showed a difference from the STAR module. The frequency of module sizes for the cases when the modules differ is given in Figure 6. The average difference in size, for the cases when there is a difference, is 295.2 axioms.
All individual extractions using the hybrid approach saw exactly 2 alternations of the STAR module extraction whereas the AMEX extraction varied between 1 and 2 times. The cases in which the AMEX extraction alternated just once happened much more often as the signature sizes grew and the difference between the respective module sizes became smaller. The additional time taken to extract the hybrid module compared to the STAR extraction alone was at most only 2.2 seconds.
STAR size
Iterated Size
We have presented a new system, AMEX, for depleting module extraction from acyclic
ALCQI-TBoxes. Using the NCI Thesaurus, we have compared the size of
AMEXmodules with the size of >⊥∗-modules computed by the OWL-API library
implementation (referred as STAR-modules) and we have presented a hybrid approach in which
STAR and AMEX-module extraction are used iteratively. The results show that for
TBoxes with many axioms of the form A ≡ C, AMEX-modules can be significantly
smaller than STAR-modules and that an iterative approach can lead to significantly
smaller modules than ‘pure’ STAR-modules. In contrast to [
Francisco Mart´ın-Recuerda1 and Dirk Walther2 1 Universidad Polit´ecnica de Madrid, Spain fmartinrecuerda@fi.upm.es
2 TU Dresden, Germany Center for Advancing Electronics Dresden
dirk.walther@tu-dresden.de Abstract. Atomic decomposition of ontologies has been suggested as a tool to understand the modular structure of ontologies. It consists of a polynomial size representation of potentially exponentially many modules of an ontology. Tractable algorithms for computing the atomic decomposition for locality-based modules have been introduced, albeit leaving room for improvement in terms of running time. In this paper, we consider ontologies formulated in OWL-EL. We introduce a notion of an axiom dependency hypergraph for an ontology, which represents how axioms are included in locality-based modules. We use a standard algorithm from graph theory to compute strongly connected components of the axiom dependency hypergraph and show that such components correspond to atoms of the ontology. An empirical evaluation of the algorithm on large fragments of biomedical ontologies confirms a significant improvement in running time. 1 The atomic decomposition of an ontology provides a compact representation of all possible modules that can be extracted from a given ontology. It represents a significant contribution to a better understanding of the internal structure of the ontology.
In this paper, we introduce a novel representation model of OWL-EL ontologies based on directed hypergraphs that explicitly represent information for syntactic locality and atomic decomposition. We call this model Axiom Dependency Hypergraphs (ADHs). A directed hypergraph is a generalisation of a directed graph in which edges (in this case hyperedges) can connect two nonempty disjoint sets of nodes (or vertices). The nodes in such hypergraphs represent the axioms of an ontology, and hyperedges indicate subset relations between terms ? We thank the reviewers of the workshop WoMO 2013 for their comments. The first author acknowledges the support of the EU project SEALS (FP7-ICT-238975), and the second author the support of the German Research Foundation (DFG) within the Cluster of Excellence ‘Center for Advancing Electronics Dresden’. in axioms. By using standard hyperpath search algorithms it is possible to efficiently extract locality-based modules (in linear time) and to compute the atomic decomposition of the ontology.
The use of hypergraph-based models for locality-based module extraction is
not new [
The paper is organised as follows. In Section 2, we review the main notions on syntactic ⊥-locality, atomic decomposition, and hypergraphs. In Section 3, we introduce axiom dependency hypergraphs and discuss their size, and evaluate the performance of atomic decomposition based on these graphs in Section 4. We conclude this paper in a final section. 2
In this paper, we consider ontologies formulated in the description logic E L,
which allows for conjunction and existential restrictions. Large parts of, e.g.,
biomedical ontologies are expressed in E L. For notions on description logics, we
refer to [
The notion of ⊥-locality depends on whether or not a given signature covers
all symbols occurring on the LHS of a general concept inclusion, or occurring on
the LHS or RHS of a general concept equation. The following proposition makes
that precise.3
1 For sets of axioms with this property the term ‘safety’ is used in the literature [
Axiom β is syntactic ⊥-local wrt. Σ if there are two symbols, one occurring in LHS(β) and one in RHS(β), that are not contained in Σ, i.e., if β satisfies any of the following conditions: – A1 ∈/ Σ and Ai ∈/ Σ, for some i ∈ {2, 3}; or – A1 ∈/ Σ and r1 ∈/ Σ.
Extracting modules based on locality
This is the module extraction algorithm from [
The algorithm takes an ontology O and a signature Σ as input and returns a subset M of O. The computed set M consists of axioms that are not xlocal wrt. Σ ∪ sig(M), or equivalently, O \ M consists of axioms that are local wrt. Σ ∪ sig(M). The algorithm produces a finite sequence M0, . . . , Mn, n ≥ 0, of subsets of the ontology O, where Mn is the ⊥-local module of O wrt. 4 These axioms are of the forms that occur frequently in the biomedical ontology Full-Galen. Σ ∪ sig(Mn) with Σ being the initial signature. This sequence induces a relation on O representing the successive inclusion of the axioms into the module. Later we will represent this relation as hyperedges in an axiom dependency hypergraph. This is illustrated in the following example.
Example 2. The signature increases round-by-round due to axioms that are added to the module (line 5). In fact, the RHSs of the axioms introduce new symbols to the signature. Let αi = Ai v Ai+1, for i ∈ {1, ..., n}. Let O = {α1, ..., αn} and Σ = {A1}. We run the algorithm on the input O and Σ. In the first round of the do-until loop (lines 3-6), the axiom α1 is the only axiom in O that is not ⊥-local wrt. Σ ∪ sig(M0) (line 5), where M0 = ∅ (line 2). So α1 is added to M1. In the second round, ⊥-locality is checked for the extended signature Σ ∪ sig(M1) = {A1, A2}. Axioms α1 and α2 are now non-⊥ local wrt. Σ ∪ sig(M1) and both are added to M2. The algorithm proceeds this way until all axioms of O are added to Mn. As no more axioms are added the algorithm exits the do-until loop (line 6) and returns Mn+1 = O as the ⊥-local module of O wrt. Σ (line 7). The following picture shows the module extraction process as a graph Gmod⊥(O,Σ) = (V, E), where V = {α1, ..., αn} and E = {(αi, Ai+1, αi+1) | i ∈ {1, ..., n − 1}}, and the sequence M0, ..., Mn, Mn+1 produced by the module extraction algorithm. Additionally we indicate with a tilted arrow labelled with A1 to node α1 that the concept name A1 is provided by the initial signature. In this case, α1 is the first axiom to be included by the module extraction algorithm.
M0
A2 - α2
A3 - α3 M1
M2
A4 - ...
M3
An- αn
Mn = Mn+1
Atoms represent sets of highly related axioms in the sense that they always
co-occur in modules. A set a of axioms from an ontology O is an atom of O
if for every module M of O, it holds that a ⊆ M or a ∩ M = ∅. We denote
with AtomsO the set of all atoms of O. The atoms of an ontology partition the
set of its axioms (i.e., each axiom occurs in exactly one atom). A dependency
relation between pairs of atoms can be established: an atom a2 depends on an
atom a1 in an ontology O (written a1 <O a2) if a2 occurs in every module
of O containing a1. For a given ontology, the pair hAtomsO, <Oi consisting of
the set of atoms together with the dependency relation between them is called
Atomic Decomposition.5 It provides a compact representation of all modules of an
ontology as every module is composed of the axioms of certain atoms. Therefore,
the atomic decomposition contributes to a better understanding of the internal
structure of ontologies with possible implications in ontology engineering and
reasoner design. The representation of the modules in terms of atoms and their
5 Here we use atomic decomposition for ⊥-local modules denoted as hAtoms⊥O, <⊥Oi.
interdependencies is of linear size and it can be computed in polynomial time,
whereas there are exponentially many possible modules of an ontology. However,
not all modules of an ontology can be computed from its atomic decomposition.
The atomic decomposition was first introduced in [
Directed hypergraphs
A directed hypergraph [
A node v2 is B-connected 6 (or forward reachable7) from v1 if (i) v2 = v1 (v2 is B-connected from itself), or (ii) there is a hyperedge e such that v2 ∈ H(e) and all the elements of T (e) are B-connected from v1. A B-hyperpath from node v1 to node v2 in a hypergraph H is a minimal (in terms of hyperedges and nodes) subhypergraph of H such that v2 is B-connected to v1.
In a directed hypergraph H, two nodes v1 and v2 are strongly B-connected
if v2 is B-connected to v1 and vice versa. In other words, both nodes, v1 and
v2, are mutually reachable. A strongly B-connected component (SCC) is a set of
nodes from H which are all are mutually reachable [
In the case of directed graph, it is possible to calculate all the strongly
connected components in linear time [
Axiom dependency hypergraphs are a representation model for ontologies based
on directed hypergraphs that explicitly represent information for locality and
atomic decomposition. The nodes in such graphs represent the axioms of an
ontology, and hyperedges indicate subset relationships between terms in axioms
6 There is a similar notion called F-connectivity [
The ⊥-locality signatures ⊥-sig(α) of an axiom α is the set of signatures ⊥-sig(α) = ({sig(LHS(α))} if α is of the form C v D;
{sig(LHS(α)), sig(RHS(α))} if α is of the form C ≡ D.
Intuitively, ⊥-sig(·) is a function assigning to an axiom α the signatures ⊥-sig(α) that are relevant for deciding the ⊥-locality status of α. More precisely, we have that α is not ⊥-local wrt. S, for every S ∈ ⊥-sig(α).
Axiom dependency hypergraphs for EL-ontologies are defined as follows. Definition 1 (Axiom dependency hypergraph for ⊥-locality). Let O be an EL-ontology. The ⊥-locality axiom dependency hypergraph (ADH) HO⊥ for O is defined as HO⊥ = (V, E), where – V = O; and – e = (T (e), H(e)) ∈ E iff the following holds: (i) H(e) = {β}, for some β ∈ V, and (ii) T (e) ⊆ V \ {β} such that |T (e)| is minimal with the property S ⊆ sig(T (e)), for some S ∈ ⊥-sig(β). a Note that the axiom dependency hypergraph for an EL-ontology is defined for the notion of ⊥-locality.9 The nodes are the axioms of the ontology, and the hyperedges are associating axioms α1, . . . , αn with a single axiom β such that one of the ⊥-locality signatures of β is contained in the signature of the axioms αi. The minimality condition states that each of the axioms αi is required and none of them is superfluous for covering some of the ⊥-locality signatures of β.10 Example 3. Let O = {α1, ..., α5}, where α1 := A v B α2 := B u C u D v E α3 := E v A u C u D α4 := A v X α5 := X v A The ADH HO⊥ contains the hyperedges e1 = ({α1, α3}, {α2}), e2 = ({α1}, {α4}), e3 = ({α2}, {α3}), e4 = ({α3}, {α1}), e5 = ({α3}, {α4}), e6 = ({α4}, {α1}), e7 = ({α4}, {α5}), e8 = ({α5}, {α1}) and e9 = ({α5}, {α4}); see Example 4 for a visualisation of the graph. Now obtain O0 by replacing α2 with α20 := B uC uD ≡ E. Then the ADH HO⊥0 contains one additional edge e10 = ({α3}, {α2}).
B-connectivity (forward reachability) in axiom dependency hypergraphs can
be used to specify ⊥-local modules in the corresponding ontology. Denote with
Mod⊥O(α) the ⊥-local module of ontology O wrt. the signature of axiom α.
9 Axiom dependency hypergraphs for the notion of >-locality can be defined in a
similar way.
10 Note that the minimality condition in Def. 1 is to avoid superfluous hyperedges, but
it is not required in terms of correctness.
Proposition 2. Let O be an EL-ontology and α an EL-axiom. Then: Mod⊥O(α) =
{β | α is B-connected to β in HO⊥}. a
Reachability-based modules have been defined in other hypergraph
respresentations of ontologies in [
The set of atoms for an EL-ontology O corresponds to the set of strongly connected components in the axiom dependency hypergraph for O. Let SCCs(HO⊥) be the set of strongly connected components of the hypergraph HO⊥. Proposition 3. Let O be an EL-ontology. Then: Atoms⊥O = SCCs(HO⊥).
The proposition can readily be seen as follows. As a corollary of Proposition 2, mutually reachable axioms are contained in the same modules, which is equivalent to the axioms forming an atom of the ontology. The nodes in a strongly connected component are all mutually reachable. Thus, both notions are equivalent.
The dependencies between atoms for an EL-ontology O (as given by the relation <⊥) correspond to a certain binary relation over the set of strongly con
O nected components of HO⊥, which is defined as follows. For S1, S2 ∈ SCCs(HO⊥), we say that S2 depends on S1 (written S1 →⊥O S2) if there is an hyperedge e = (T (e), H(e)) in HO⊥ such that T (e) ⊆ S1 and H(e) ⊆ S2. Let →⊥O∗ be the reflexive, transitive closure of →⊥O.
Proposition 4. Let O be an EL-ontology. Let a1, a2 ∈ Atoms⊥O and S1, S2 ∈ SCCs(HO⊥) such that a1 = S1 and a2 = S2. Then: a1 <⊥O a2 iff S1→⊥O∗S2. a Example 4. Consider again the ontology O and its axiom dependency hypergraph HO⊥ from Example 3. We obtain the following ⊥-local modules for the axioms:
Mod⊥O(α1) = {α1, α4, α5} Mod⊥O(α2) = {α1, α2, α3, α4, α5} Mod⊥O(α3) = {α1, α2, α3, α4, α5}
Mod⊥O(α4) = {α1, α4, α5} Mod⊥O(α5) = {α1, α4, α5} The resulting atoms in AtomsO are a1 = {α2, α3} and a2 = {α1, α4, α5}, where a1 < a2, i.e., a2 depends on a1. The ADH HO⊥ and the atoms of O can be depicted as follows: α2
? α3 a1 * a2 α1 YHHHHHHHHHHHHHHHHj 6 α5
? - α4 Consider the strongly connected components of HO⊥. Axiom α1 is B-connected with the axioms α4 and α5, α4 is B-connected with α1 and α5, and α5 is Bconnected with α1 and α4. Axiom α2 is B-connected with α3 and vice versa. Axioms α2, α3 are each B-connected with α1, α4 and α5, but not vice versa. Hence, {α1, α2, α4} and {α2, α3} are the strongly connected components of HO⊥. Moreover, we say that the former component depends on the latter as any two axioms contained in them are unilaterally and not mutually B-connected. Note that the atoms a1 and a2 of O and their dependency coincide with the strongly connected components of HO⊥ .
For ontologies consisting of axioms of the form A v C, where A is a concept name, the locality dependencies between axioms can be represented in directed graphs (i.e., hypergraphs in which the tail of any hyperedge contains only one axiom). For such ontologies O, the definition of the axiom dependency hypergraph HO⊥ = (V, E) can be simplified (cf. Def. 1). The condition for a hyperedge e = ({α}, {β}), for α, β ∈ V, to be contained in E is now:
e = ({α}, {β}) ∈ E iff sig(LHS(β)) ⊆ sig(α)
The advantage of this representation is that we can directly use a standard
linear time algorithm for calculating strongly connected components of directed
graphs [
Size of axiom dependency hypergraphs (worst-case) We observe that axiom dependency hypergraphs may be of exponential size. Proposition 5. There exists ontologies O such that the axiom dependency hypergraph HO contains exponentially many hyperedges in the number of axioms of O. a We show the proposition with the following example.
Example 5. Let n, k be two natural numbers with n > 0 and k > 0. Ontology On,k is defined as: On,k = {α := X1u. . .uXn v Y } ∪ {αji := Aij v Xi | i ∈ {1, ..., n}, j ∈ {1, ..., k}} Axiom α is the only axiom in On,k with a complex LHS, which in turn is a conjunction of n many concept names X1, ..., Xn. The axioms αji state that each concept name Xi subsumes k many concept names Ai1, ..., Aik. The corresponding axiom dependency graph HOn,k is the the tuple HOn,k = (V, E), where V = On,k and
E = {({β1, ..., βn}, {α}) | βi ∈ {α1i, ..., αki}, i ∈ {1, ..., n}}. It can readily be seen that HOn,k contains kn many hyperedges, where n, k are each bound by the number of axioms in On,k.
The axiom dependency hypergraph serves as a tool to determine the atoms of an ontology via calculating the strongly connected components of the graph. Example 5 illustrates a problem with the size of the axiom dependency hypergraphs as defined in Def. 1. We note, however, that no hyperedge in HOn,k is needed for the purpose of determining the atoms for On,k. For every axiom β in On,k, the ⊥-local module Mod⊥O(β) is a singleton set consisting of β itself. Consequently, the atoms of On,k are singleton sets as well as are the strongly connected components of HOn,k . Note that we obtain the same strongly connected components after removing every hyperedge from HOn,k . This observation suggests a possible solution to avoid the exponential blow-up problem. The idea is to build the hypergraph using only the “necessary” hyperedges that are required for the computation of the strongly connected components which in turn correspond to atoms. We hypothesize that the hyperedges needed are the ones that preserve the mutual reachability relation between the axioms of the ontology. This means that no more incoming hyperedges are needed per axiom than the total number of axioms in the ontology. We leave a formal treatment of this idea for future work.
Size of axiom dependency hypergraphs for real ontologies Primitive concept inclusions, i.e. axioms of the form A v C, where A is a concept name and C a possibly complex concept, are of prime importance for biomedical ontologies. For instance, the majority of axioms in the biomedical ontologies from the Bioportal in the following table are primitive concept inclusions.11 Ontology
Signature #axioms percentage #axioms #role size A v C of all axioms C ≡ D axioms
in ontology CPO (12/2011) FMA-lite Full-Galen (v1.1) GO v1.1 (1986) NCBI (v1.2) RH-MeSH (08/2012) Snomed CT (2010a) 136 090 306 111 75 168 119 558 24 088 25 563 34 220 61 990 847 796 847 755 286 382 403 210 291 207 227 698 80.61% 99.99% 67.81% 99.99% 100% 100% 78.18% 73 461
0 9 968 0 0 0 63 446 96 3 2 165 5 0 0 12 Most ontologies contain other axioms as well such as concept equations and role axioms.12 The table shows the percentage of axioms of the form A v C to all axioms in each ontology. The ontologies NCBI and RH-Mesh are taxonomies (no logical operators); they consist entirely of axioms of the form A v B, where A, B are concept names. 11 http://bioportal.bioontology.org 12 Other axiom types are not shown here, e.g., disjointness axioms in CPO. Ontology A v C-fragment
Signat.
size
ADH #nodes #edges #SCCs CPO (12/2011) 136 027 306 111 1 474 962 131 482 FMA-lite 75 141 119 558 1 021 863 54 649 Full-Galen (v1.1) 16 412 25 563 179 770 12 502 GO v1.1 (1986) 34 175 61 990 255 215 34 167 NCBI (v1.2) 847 760 847 755 1 695 474 847 755 RH-MeSH (08/2012) 286 380 403 210 1 435 631 286 263
Snomed CT (2010a) 240 021 227 698 556 474 227 698
The difference between the number of SCCs and the number of nodes in the axiom dependency hypergraph can be seen as a measure of cyclicity of the graph.
The following example illustrates the limitations of axiom dependency graphs. Axioms of the form C v D or C ≡ D (i.e. axioms whose ⊥-locality signatures contains more than one symbol) can cause many hyperedges to be included in the axiom dependency hypergraph.
Example 6. Consider this concept equation α from the ontology Full-Galen: Incontinence ≡ Transport u ∃ actsOn.BodySubstance u ∃ hasIntentionality.(Intentionality u ∃ hasAbsoluteState.involuntary) u ∃ hasUniqueAssociatedDisplacement.(Displacement
u ∃ isDisplacementTo.GRAILExteriorOfBody) The axiom dependency hypergraph HF⊥ull-Galen contains up to 9.2 × 1012 many hyperedges of the form e = (T (e), {α}), where T (e) is a set of axioms containing the 12 signature symbols from ⊥-sig(α).13 As indicated in Section 3.1, the number of hyperedges may be reduced while preserving the strongly connected components. The idea is that no more incoming hyperedges are needed per axiom as there are axioms in the ontology. In the case of Full-Galen, we have an upper bound of 37 696 many incoming hyperedges per axiom. In particular, for axiom α from Example 6 we estimate up to 21 095 many hyperedges to preserve the mutual reachability relation involving α. 4
We have implemented a Java program that takes an E L-ontology O (with axioms of the form A v C) as an input and builds the corresponding axiom dependency hypergraph HO⊥. Then it computes the set SCCs(HO⊥) of strongly connected components of HO⊥ and the dependencies between these components. We compare the running times of atomic decomposition using FaCT++ with the times needed by the hypergraph-based approach. The following table lists the results.14 13 The number of hyperedges is merely an estimated upper bound (as it does not take into account the minimality condition in Def. 1). 14 All experiments were performed on an Intel Xeon E5-2640 2.50 GHz with Java version 1.7.0 40 (command line parameters -Xss1G -Xms4G -Xmx8G). We used FaCT++, 64bit, Version 1.6.2 (19 February 2013) and the OWL API version 3.4.4. Ontology fragment with axioms of the form A v C
time FaCT++ time hypergraph-based approach load build comp. comp. total ont. ADH SCC deps.
speedup CPO (12/2011) 1 262.69 s 9.99 s 0.85 s 0.59 s 0.52 s 11.94 s 105.8 FMA-lite 19 991.92 s 9.50 s 0.49 s 6.43 s 0.20 s 16.62 s 1 202.9 Full-Galen (v1.1) 115.77 s 2.87 s 0.09 s 0.20 s 0.05 s 3.21 s 36.1 GO v1.1 (1986) 44.33 s 3.42 s 0.15 s 0.16 s 0.09 s 3.82 s 11.6 NCBI (v1.2) 49 227.86 s 73.72 s 1.42 s 0.87 s 1.19 s 77.22 s 637.5 RH-MeSH (08/2012) 6 921.62 s 15.24 s 1.31 s 0.63 s 0.66 s 17.84 s 388.0 Snomed CT (2010a) 4 538.65 s 14.47 s 0.48 s 0.31 s 0.32 s 15.58 s 291.3 The times for FaCT++ are the total times needed (2nd column), which includes loading the ontology, initialising the reasoner and computing the atoms (but not saving the atoms). For the hypergraph-based approach, we have listed the times needed for the OWL-API to load the ontology and to do some initialisation (3rd column), to build the axiom dependency hypergraph (4th column), to compute the strongly connected components of the graph (5th column), to compute the dependencies between the strongly connected components (6th column) and the total time needed (6th column). The last column shows for each ontology the speedup achieved for atomic decomposition using the hypergraphbased approach compared to FaCT++. On FMA-lite an over 1 000-fold speedup was realised.
FaCT++ improves upon the original algorithm for atomic decomposition [
Modularisation and atomic decomposition has been suggested as a means to understand the internal structure of ontologies. Axiom dependency hypergraphs are an explicit representation of these notions. A module can be extracted from the hypergraph by collecting the nodes reachable from the nodes that are determined by the input signature. Moreover, it is possible to directly apply standard off-the-shelf graph algorithms for computing the atoms of certain E L-ontologies in linear time. For the atomic decomposition of FMA-lite, a staggering 1 000-fold speedup could be achieved compared to the reasoner FaCT++.
The disadvantage of the axiom dependency hypergraphs, as introduced in this paper, is their exponential size in the worst case for general concept inclusions. We have indicated that the blow-up in size can be avoided by omitting hyperedges while still preserving the mutual reachability relation between axioms. In this way, no more than quadratically many hyperedges are required for determining the atoms.
For future work, the idea of avoiding the exponential blow-up of the axiom dependency hypergraphs for general E L-ontologies needs to be formalised, implemented and evaluated. It would also be interesting to extend the current approach to other locality notions such as >- and ⊥>∗-locality and to richer languages such as SROIQ.
Towards a Unified Approach to Modular Ontology Development Using the
Aspect-Oriented Paradigm
Ralph Sch¨afermeier and Adrian Paschke
Freie Universita¨t Berlin, Ko¨nigin-Luise-Str. 24-26, 14195 Berlin, Germany
{schaef,paschke}@inf.fu-berlin.de http://www.corporate-semantic-web.de/ Abstract. In this paper, we describe our ongoing work on the application of the Aspect-Oriented Programming paradigm to the problem of ontology modularization driven by overlapping modularization requirements. We examine commonalities between ontology modules and software aspects and propose an approach to applying the latter to the problem of a priori construction of modular ontologies and a posteriori ontology modularization.
Keywords: ontology modularization, aspect-oriented development,
crosscutting concerns
1
The majority of existing modularization approaches are specialized solutions,
relying on semantic (cf., for example, [
The aspect-oriented programming paradigm allows for the separation of multidimensional requirements into dedicated software code modules (aspects), leading to better code modularity and therefore reusability. Using AOP, modules can be recombined (interwoven) either extensionally, by explicitly marking the points in the code where the execution flow should be diverted to a different module, or intensionally, by specifying a set of properties such code points are expected to have in common.
In this paper, we examine commonalities between ontology modules and
software aspects and describe our ongoing work towards the application of the above
mentioned principles of the AOP paradigm to ontologies. We argue that the
latter enables (a) straightforward development of modular ontologies from scratch,
and (b) flexible a-posteriori modularization, driven by user requirements.
Aspect-oriented software programming (AOP) languages provide syntactic means
for the separation of so called cross-cutting concerns in software code into
dedicated modules. As defined by the ISO/IEC/IEEE standard 42010 of software
architecture1, “concerns are those interests which pertain to the systems
development, its operation or any other aspects that are critical or otherwise important
to one or more stakeholders”. Cross-cutting concerns are concerns which emerge
from requirements on different levels, concern the entire or a significant part
of the system and are thus scattered across the system, diminishing code
locality and hindering system evolution and reusability [
Car
Req. 1: Car components Engine Frame Wheels
Customer
Tax Units sold
Provenance Mulitilingualism Tractable reasoning Req. 2: Tractable reasoning Stakeholder 1: Stakeholder 2:
Engineering Sales Fig. 2: Selection of an ontology module Fig. 1: Cross-cutting concerns by the ex- that satisfies two cross-cutting requireample of a car ontology. Different stake- ments: It should only contain concepts holders are interested in different aspects of the subdomain “car components” of of the core concept (car). The different in- the car domain (“Engineering” aspect, terests (concerns) reflect requirements for- dotted), and it should only contain conmulated by each of the stakeholders. At structs that allow for tractable reasoning the same time, stakeholder-independent re- (“Tractability” aspect, dashed). The requirements cross-cut the ontology. Each of sulting module (grey) only contains those theses requirements has a different dimen- constructs that are concerned by both assion. pects.
In AOP terminology, the encapsulation of a single concern in a dedicated module is referred to as aspect. An aspect consists of two components: the actual implementation of the functionality, referred to as advice, and information about all points in the application’s control flow at which the advice should be executed, referred to as join points. In this manner, we use the notion of aspects in order to relate ontological constructs to different requirements (see Figure 2).
Listing 1.1 shows an example of a concern “authentication” that cross-cuts with the actual business logic of a bank application and leads to tangled code. Listing 1.2 shows how the authentication concern is encapsulated in an aspect “Authentication”. The authentication handling code has been centralized in the advice of the aspect. Listing 1.1: Example of the cross- Listing 1.2: The concern “authenticacutting concern “authentication” af- tion” is encapsulated in an aspect “Aufecting different parts of the code. thentication”. withdraw ( Account a , f l o a t amount ) {
AuthService as = getAuthService ( ) ; i f ( ! as . a u t h e n t i c a t e d ( a . u s e r ) )
as . a u t h e n t i c a t e ( a . u s e r ) ; a . balance −= amount ; } d e p o s i t ( Account a , f l o a t amount ) {
AuthService as = getAuthService ( ) ; i f ( ! as . a u t h e n t i c a t e d ( a . u s e r ) )
as . a u t h e n t i c a t e ( a . u s e r ) ; a . balance +=amount ; } public Aspect A u t h e n t i c a t i o n ( ) {
AuthService as = getAuthService ( ) ; i f ( ! as . a u t h e n t i c a t e d ( a . u s e r ) )
as . a u t h e n t i c a t e ( a . u s e r ) ; } @aspect A u t h e n t i c a t i o n withdraw ( Account a , f l o a t amount ) {
a . balance −= amount ; } @aspect A u t h e n t i c a t i o n d e p o s i t ( Account a , f l o a t amount ) {
a . balance +=amount ; }
Note that this example demonstrates the explicit (extensional) variant of join
points, in the form of tags assigned to each part of the code where an aspect
is applicable. In order to achieve complete detangling of cross-cutting concerns,
AOP introduces two principles: quantification and obliviousness.
2.1 Quantification
AOP allows for an intensional definition of join points by using quantified
statements in the form
∀m(p1, . . . , pn) ∈ M : s(m(p1, . . . , pn)) → (m(p1, . . . , pn) → a(p1, . . . , pn)),
where M is the set of all methods defined within the software product, s
a predicate specifying the join point properties, m(p1, . . . , pn) ∈ M a method
adhering to the signature m(p1, . . . , pn), and a(p1, . . . , pn) the execution of the
advice with all the parameters of each method, respectively [
In the case of the authentication example, an instantiation of this formula would be: ∀m(p1, . . . , pn) ∈ M : sig(m(p1, . . . , pn)) = m(Account acc, f loat amount) → (m(acc, amount) → Authentication(acc, amount)).
In order to select ontology axioms in the same fashion, a means of quantification over such axioms is necessary.
∀ax(p1, . . . pn) ∈ O : s(ax(p1, . . . pn)) → (ax(p1, . . . pn) → a(ax(p1, . . . pn))), with O being an ontology, ax(p1, . . . pn) axioms (in the form of n-ary predicates the domain of which is the union of the vocabulary of the ontology language in question and the vocabulary of the problem domain, such as class, property and individual names), and a(ax(p1, . . . pn)) a function that applies the aspect to ax(p1, . . . pn), whereupon we define the application of an aspect to an axiom as the inclusion of that particular axiom in the module represented by the aspect. In this manner, the aspect “tractability” from the example scenario could be implemented by building a query that selects all axioms which are compatible with the OWL-EL profile.
hasAspect ≡ Car
Aspect ≥ hasWheel
min 4 Wheel
Fig. 3: Extensional join point definition using an OWL annotation.
As mentioned in section 1, join points can also be specified extensionally, for example, by manually annotating axioms which cover a particular aspect with a dedicated OWL Annotation (see Figure 3). This is of particular use for a priori modular ontology development if used, e. g., by an ontology editor with switchable contexts, each context representing an aspect. A user could then extensionally define an aspect-oriented ontology module by switching aspects.
Obliviousness and Harmlessness
The fact that in aspect-oriented software systems control flow is handed over
from the main module to the aspects, making the main module (and any other
modules) unaware of the (quantified or extensionally specified) assertions made
about it by external aspects that might possibly be applied to it, is termed
obliviousness [
Danters et al. allude to the problem that obliviousness is only guaranteed on
a syntactic level while external aspects have in fact the potential to alter the
semantics of the target module, making them potentially dangerous [
While it is obvious that the obliviousness property naturally holds for ontology modules, the harmlessness property does not. Nevertheless, it is agreed upon in the recent literature that it is desirable if an ontology module is uninvasive, i.e., its addition to an ontology has no side effects. Whether uninvasiveness of a module applied by the means of an aspect is a required feature or not depends on the specific use case.
Grau et al. [
Let O1 ⊆ O ontologies, S a signature and L a logic. O is a conservative extension of O1 wrt. L, if for every axiom ax with sig(ax) ⊆ S: O |= ax iff O1 |= ax.
In the same vein, we define a harmless aspect of an ontology O as an aspect that yields the selection of a module O1 that is the conservative extension of O with respect to L.
It has been noted that determining whether a module is a conservative
extension of an ontology is a highly complex problem and even undecidable for
expressive ontologies [
Further work is necessary in order to achieve a functional meta description of ontology axioms for the purpose of pointcut definition. The formalism described in section 2.1 works in terms of meta predicates with the domain consisting of vocabulary of the ontology language, reifing axioms contained in the ontology.
The research question raised in this paper is how the application of the aspect-oriented paradigm affects the quality of ontology modularizations. Our hypothesis is that aspect-oriented ontology development yields useful ontology modules wrt. to cross-cutting modularization requirements, such as dynamic access, understandability, maintenance, and re-use. We expect that the intensional specification of ontology modules with pointcuts adds dynamicity and flexibility to modular development, making it easier to evolve modular ontologies in situations where evolution implies modularization requirement changes.
To evaluate our approach and test our hypothesis, we will apply the approach to different modularization use-cases in the context of ontology development projects. Aspects considered in these use cases will comprise project affiliation, temporal attribution, workflow affiliation, re-use, and module understandability. We then use quality metrics in order to assess the quality of the modularizations gained using our approach and compare it with existing approaches.
This work has been partially supported by the “InnoProfile-Transfer Corporate Smart Content” project funded by the German Federal Ministry of Education and Research (BMBF) and the BMBF Innovation Initiative for the New German L¨ander - Entrepreneurial Regions.
1. Cuenca Grau, B., Parsia, B., Sirin, E.: Combining OWL ontologies using EConnections. Web Semantics: Science, Services and Agents on the World Wide