Ontologies are increasingly used in systems where performance is an important requirement. While there is a lot of work on reasoning performance-altering structures in ontologies, how these structures appear in Ontology Design Patterns (ODPs) is as of yet relatively unknown. This paper surveys existing literature on performance indicators in ontologies applicable to ODPs, and studies how those indicators are expressed in patterns published on two well known ODP portals. Based on this, it proposes recommendations and design principles for the development of new ODPs.
The Semantic Web is built upon, and depends on, the use of OWL DL ontologies.
The adoption rate of such ontologies among practitioners is as of yet limited.
Ontology Design Patterns (hereafter ODPs) attempt to simplify ontology
development for everyday users, by packaging recurring ontology problems, along
with recommended solutions, as recipes or small reusable building blocks [
However, less e ort has been spent on studying the e ects of ODP design on
reasoning performance over resulting ontologies. Certain structures occurring in
Ontology Design Patterns for meronomy modelling have been shown to impact
reasoning performance [
While obtaining a better understanding of performance-altering structures in ODPs is an important goal in itself, if the work is to provide practical recommendations on the use of published ODPs, one needs also study how the developed performance indicators appear in those ODPs commonly used by the community. With this in mind, the following research questions were selected for study: 1. Which existing performance indicators from literature known to a ect the performance of reasoning with ontologies are also applicable to ODPs? 2. How do these performance indicators vary across published ODPs? 3. Which recommendations on reasoning-e cient ODP design can be made, based on the answers to the above two questions? 2
In order to answer the research questions, a two-step approach was employed. To begin with, a literature study on existing ontology performance indicators that are reusable in describing Ontology Design Patterns was performed, the results of which answer the rst research question. Thereafter, the distribution of these indicators over published Ontology Design Patterns from two ODP portals was studied, in order to answer the second question. In the end, recommendations for ODP developers based on the ndings of both these steps were developed.
In the literature study, publications at the main tracks and the associated workshops of four high-impact conferences dealing with formal knowledge modelling, from 2005 to 2012, were studied. The conferences in question were the International and Extended Semantic Web Conferences (ISWC and ESWC), the International Conference on Knowledge Capture (K-CAP), and the International Conference on Knowledge Engineering and Knowledge Management (EKAW).
All papers matching the above criteria were downloaded, and their abstracts studied. Abstracts mentioning metrics, indicators, language expressivity e ects, classi cation performance improvements or performance analyses (in total, 16 papers) were selected for thorough reading. Of these, eight were found to identify performance-altering structures likely to exist or be relevant in Ontology Design Patterns. These papers and their contributions are discussed in Section 3.1.
The second research question concerned the study of how performance-altering indicators varied among the patterns available in the pattern repositories used by the community. To this end, the reusable OWL building blocks of the patterns from two well known ODP repositories, http://ontologydesignpatterns.org and http://odps.sourceforge.net, were downloaded and studied. A modular expandable tool for measuring ontology or ODP metrics was developed2 specifically for this purpose. The Java-based tool parses an input ontology (or in this case, ODP module) and based on which metric measurement plugins are located in the tool's classpath, measures di erent aspects of said ontology. It generates as output CSV data suitable for post-processing in a spreadsheet or statistics tool. Plugins for all of the performance related indicators under study (with two exceptions, detailed in Section 3.2) were developed for this tool, and it was then executed over the downloaded pattern set.
In analysing the data from the execution of the indicator measurements, a simple four step process was repeated for each indicator under study: 1. Sort all ODPs by the studied indicator. 2. Observe correlation e ects against other indicators. Can any direct or inverse correlations be observed for whole or part of the set of patterns? 3. Observe distribution of values. Do the indicator values for the di erent patterns vary widely or not? Is the distribution even or clustered? 4. For any interesting observation made above, attempt to nd an underlying reason or explanation for the observation, grounded in the OWL ontology language and established ODP usage or ontology engineering methods.
In performing the above analysis, some interesting correlations were discovered and studied, as shown in Section 3.2. In some cases, an explanation for the correlations based on the structure of the OWL language and the constructs within it could also be generated. 3
The below two sections summarise the key ndings of the literature study and the subsequent indicator variance study. 3.1
In the studied papers, three main types of indicators and corresponding e ects could be identi ed, namely expressivity pro le indicators (i.e., indicators related to pro les or constraints of ontology language structures available for use), inheritance hierarchy structural indicators (i.e., indicators related to the structure of the subsumption tree), and axiom usage indicators (i.e., general indicators related to the logical axioms employed in an ontology). Each of these categories and the indicators found to be associated with them are discussed in the following subsections.
Pro le indicators Urbani et al. discuss the issue of scaling out description
logic reasoning on parallel computing clusters using the MapReduce framework.
They show in [
In [
Developing an ontology that lies solely within OWL Horst or one of the OWL 2 pro les, requires that no axioms exist in the ontology that lies outside of the target language restriction. Therefore, it is obviously important that ODP users be aware of the language pro le of the patterns that they consider for reuse. Consequently, the pro le indicators are highly relevant when describing ODP performance characteristics.
Structural indicators Kang et al. [
In [
The structure of the subsumption hierarchy (both depth-wise and in terms of tree impurity/tangledness) is often a ected by extensive pattern use. Given that a common pattern usage method involves importing and subclassing a reference building block, and given that patterns often build upon and re ne one another such that this usage method is repeated, extensive pattern usage may quickly lead to an increased ontology depth or tangledness.
Axiomatic indicators The majority of performance-a ecting indicators
discussed in the studied literature concerns the use of particular types of axioms or
structures in an ontology. Two papers in particular contribute to this knowledge,
namely Goncalves et al. [
Goncalves et al. [
As mentioned above, Kang et al. [
Summary The performance-altering indicators found via the literature study, and further examined in the following section, are summarised in Table 1.
Indicator Source
Average class in-degree [
Tree impurity / Tangledness [
The results of the study of indicator variance are detailed below, with the
exception of a few indicators that were not included, namely cyclomatic complexity,
and the set of OWL pro le adherence indicators. It proved practically infeasible
to develop software for reliably measuring the former, and rather than make
assertions based on possibly inexact data, it has been left out of this analysis.
The latter set of indicators has as mentioned above been discussed extensively
in Horridge et al.[
Average class in-degree The values for the average class in-degree indicator vary between 0.75 and 8, with a median value of 2.39 and an average value of 2.6. The distribution of indicator values over the whole pattern set is shown in Figure 1. The large majority of patterns (93 %) have a class in-degree of less than four, whereas a small group of patterns di er quite signi cantly and have an average value of around six.
Comparing some of the patterns exhibiting high and low values for the average class in-degree indicator, it was observed that they tended to di er in terms of the number of object properties contained within the patterns. The patterns exhibiting a high level of class in-degree seemed to contain a larger number of object properties than those patterns displaying a low level of this indicator. To 35 30 o6 25 a r ss 20 lc/a try15 e p o r p tc 10 e j b O 5 0 1 11 21
31 41 51 61 Ontology Design Pa9ern instances 71 81 9 8 7 6 5 4 1 0
ee 3 rg e d -‐ n 2 is sa l C Object property count (moving average, N=3) Class in-‐ degree test whether this held for the entirety of the pattern set, the object property counts were mapped against the values of the class in-degree indicator. Such a mapping should if the observation holds indicate the existence of an correlation between the two mapped indicator value series. The results, as shown in Figure 1, while not indicating a correlation of the indicators across the entire studied pattern set, does indeed indicate that the patterns towards the high end of the spectrum in terms of class in-degree also often contain a higher number of object properties than the patterns with a lower class in-degree.
A possible explanation for this observation is the use of domain and range de nitions on many object properties in patterns with high average class indegree. It is considered good practice to establish such de nitions for properties one adds to an ontology. However, each domain or range de nition gives rise to one incoming RDF edge to the class in question, raising the average class in-degree indicator. Based on this observation, a recommendation to the e ect of limiting the number of domain and range de nitions used in performancedependent ontologies can be made. However, there is likely to also be other as yet unknown causes beside domain and range de nitions that that give rise to high average class in-degrees, for which reason ODP users and developers are recommended to limit the use of structures that needlessly raise class in-degree. Average class out-degree The values for the average class out-degree indicator vary between 1 and 3.83, with a median value of 2.75 and an average of 2.64. The distribution of indicator values over the whole pattern set is shown in Figure 2. The reason why all patterns exhibit a value of at least one is simply that all de ned classes by de nition have at least one outgoing subClassOf edge to another class.
In studying some patterns displaying low or high values, it was observed that the patterns displaying a higher value seem to be patterns in which class 35 30 t 25 n u o c ss 20 lscau om15 y n o n A10 5 4,5 4 3,5 3 2,5 2 ee r g e 1,5 -‐ d t uo 1 lssa
C 0,5 restrictions are used extensively. Such restrictions are written as a class being asserted to be either a subclass of or equivalent to a restriction axiom, which would explain this observation { each subClassOf or equivalentClass axiom adds an outgoing edge, increasing the value of the indicator. To test whether this explanation is supported by further evidence, the number of anonymous class de nitions (i.e., restrictions) were plotted against the value of the class outdegree indicator. The results are presented in Figure 2 which indicates a possible, if slight, correlation between class out-degree and anonymous class count.
Since the presence of class restrictions can, in the author's experience, help guide novice users understand the purpose of classes in an ontology or ODP, this unexpected performance-related e ect of using such restrictions is of particular interest. Also, given the variation of this indicator's values over the studied set of published ODPs, a recommendation as to limiting its use in performance-critical ontology applications is made.
Depth of inheritance Due to the di culty of measuring the inferred indicators across the transitive import closure graph of an ODP using the tools and APIs available at the time of writing, the values below were only calculated over the asserted depths of patterns, excluding imports. Moreover, as even this is quite a di cult task (due to di erent practices on how subclass relations to the top-level owl:Thing class are expressed), certain simpli cations had to be made. These simpli cations include the assumption of a subclass relation to Thing if no other superclass is asserted within the particular OWL le.
The subsumption hierarchy depth of the patterns varies from 0 to 5.3, with a median value of 1.5 and an average value of 1.7. In other words, most of the patterns are not very deep. At the bottom end of this distribution is a fairly large group (38 of 103 patterns) that have a depth of one or less. This particularly shallow group appears to consist of two types of patterns. The rst type consist of simpler domain speci c vocabularies that do not employ much expressive logics, but rather act as schemas for simple datatypes that may be reused. Examples include patterns for species habitats, invoices, etc. The second type consist of very general patterns that de ne abstract or intangible phenomena without going into speci c details. Examples include patterns modelling phenomena like participation and situation. A large part of the latter group seems to result from refactoring of top-level ontologies like DOLCE, whereas many of the patterns in the former group seem to be developed for more concrete and applied purposes. The patterns from the http://odp.sourceforge.net repository are generally deeper (with an average depth of 3.29) than those from the http://ontologydesignpatterns.org portal. However, the latter patterns generally contain more example classes that would likely be removed before instantiation in real cases, reducing this di erence.
While ontology depth is associated with poor performance as discussed by
LePendu et al. [
Existential quanti cation count About half the patterns, 51 of 103,
contain no explicit existential quanti cation axioms. If cardinality restrictions are
rewritten into semantically equivalent existential restrictions as suggested in [
However, in studying the patterns that contained a higher number of existential quanti cation axioms (i.e., three or more, as seen in 29 of the patterns), it was observed that these axioms were sometimes used in seemingly unneeded ways. For instance, subclasses restating such axioms as were already asserted on their superclasses, and existential quanti cation used to assert the coexistence of two individuals where it seems one individual might well exist on its own. These observed suboptimal uses of computationally expensive existential quanti cation axioms motivates a recommendation on limiting their use { if pattern users wish to add such axioms to restrict their model, the recommended axioms can instead be included in pattern documentation.
General concept inclusion count GCIs were not displayed by any of the studied ODPs. The author believes that this is because such constructs are generally not well supported by ontology engineering tools such as Protege or TopBraid Composer. The lack of any patterns displaying values for this indicator implies that the performance e ects of the use of this type of structure in ODPs is negligible in practice. All the same, a recommendation can be made to the e ect of limiting the use of these structures when developing new patterns. Tree Impurity / Tangledness Due to the mentioned inconsistencies in how subclass relations to the owl:Thing concept are modelled, the tree impurity indicator is di cult to measure in a reliable manner. However, as mentioned, this indicator measures the same underlying structure as the tangledness indicator, i.e., how far an ontology inheritance hierarchy deviates from being a tree with one parent class per subclass. Therefore, observations regarding tangledness variation in the dataset should carry over to the tree impurity indicator also. Of the 103 studied patterns, only three display any degree of directly asserted tangledness at all. In all three of these cases, the number of multi-parent classes in the pattern was one. It appears that the use of asserted multiple inheritance in ODPs is rare. However, it should be noted that the number of inferred multi-parent classes may be signi cantly greater than this number. While inferred tangledness has for technical reasons been infeasible to measure in this study, its e ect on the performance of reasoning may be considerable. 4
{ When developing patterns, don't overspecify. While an ODP creator's understanding of a domain may warrant adding domain and range restrictions to properties, or to implement some existential or cardinality restriction (because that is how the real world concept being modelled actually works), doing so will possibly have detrimental performance e ects. Ensure that requirements on the ODP are made explicit, and implement only such axioms as are required to ful ll those requirements. Do not aim for further completeness for the sake of neatness. { If the reusable OWL building block associated with a certain ODP does not display suitable reasoning characteristics, i.e., if it is overspeci ed, has a needlessly deep subsumption hierarchy, or is outside of a computationfriendly OWL 2 pro le, don't be afraid to rewrite it. Many patterns encode a good practical solution to some modelling problem, which may be reused even if the associated OWL le is not directly suitable for one's purpose. { The problem/solution mapping presented by a pattern may be more reusable than the OWL le building block provided with the pattern, as suggested above. Therefore, when when publishing a new Ontology Design Pattern, ensure su cient documentation exists on the pattern's requirements, the problem that it solves, and how it solves that problem, such that users actually can reengineer the pattern if needed. Presently several published ODPs are only partially described, e.g., in the NeOn ODP portal 3. In this paper we have studied which published indicators of reasoning performance for ontologies that carry over to Ontology Design Patterns, and how those indicators are expressed in the ODPs published in two well-known pattern portals on the web. The results indicate that certain structures occurring in published ODPs can give rise to unfavourable performance when reasoning over ontologies built using these ODPs. Recommendations and design principles have been presented regarding trade-o s and prioritisations that ODP users and developers may need to make in employing or constructing Ontology Design Patterns for usage in systems where performance e ciency is of importance.