Trees { i.e., the type of data structure known under this name { are central to many aspects of knowledge organization. We investigate some central design choices concerning the ontological modeling of such trees. In particular, we consider the limits of what is expressible in the Web Ontology Language, and provide a reusable ontology design pattern for trees.
Trees are fundamental data structures for knowledge organization. They make their appearance in the form of taxonomies, meronomies, decision trees, branching processes, etc. As such they are fundamental for ontological knowledge representation.
At the same time, however, it is not possible to fully characterize trees in the Web Ontology Language (OWL) [13,14] (see Section 3). It is thus an important research question how to represent trees in ontology modeling, and to understand the pros and cons of di erent ways to do it.
We need to realize, of course, that trees in ontology modeling often serve a di erent purpose than in programming. Operations on trees important in programming include, for example, adding or deleting items or pruning of whole sections; i.e., some of the important operations do actually change the tree. For ontology modeling purposes, in contrast, it is more appropriate to think of a tree as static and as something which is being queried. Typical queries would be to identify roots or leaves, common ancestors, or descendants.
However, despite the importance of trees for knowledge organization, there is currently no corresponding ontology design pattern available on ontologydesignpatterns.org. In this paper, we will provide such a pattern, and will also discuss di erent design choices as well as their respective advantages and disadvantages.
The rest of the paper is structured as follows. In Section 2 we present a particularly interesting use case which has informed our work, namely the use of ontology modeling for evolutionary or phylogenetic trees. In Section 3 we discuss the fundamental shortcomings of the Web Ontology Language (OWL) regarding the modeling of trees.4 In Section 4 we present a basic ontology design pattern 4 The pattern is available from
Submissions:Tree_Pattern
http://ontologydesignpatterns.org/wiki/ for the modeling of trees. In Section 5 we discuss the special case of n-bounded trees (e.g., with n = 2 for binary trees). In Section 6 we conclude. 2
One of the central tenets following from the theory of organismal evolution is
that all life is related through descent with modi cation [
A phylogenetic tree represents important evolutionary hypotheses about
shared history. For example, two OTUs A and B are more closely related to
each other than to OTU C if A and B share a more recent common ancestor
than they do with C. The subtree descending from a node forms a clade, clades
which share a parent are called sister clades. One of the major objects of
comparative phylogenetics is to identify the properties and processes (organismal
traits, geographic range, tempo and mode of evolution, etc) by which one clade
di ers from others, in particular its sisters, and how these properties change
along lines of descent in the tree [
Operations (1) and (4) correspond to two principle ways in which the
semantics of clade concepts can be de ned on a tree [
It is worth noting that spurred in part by the exponentially increasing amount
of data available for phylogenetic reconstruction, very large trees encompassing
up to tens of thousands of taxa have recently become available [
In order to investigate to what degree tree-based properties can be expressed using common KR formalisms, we rst need to formally de ne what structures we denote by the notion \tree".
De nition 1. A rooted directed branching tree (short: tree) is de ned as a directed graph T = (V; E) where V is a set called vertices or nodes and E V V is the set of edges, satisfying the following properties: 1. There is exactly one node r 2 V called root, which has no incoming edges, i.e., E \ (V frg) = ;. 2. Every node v 2 V n frg that is not the root has exactly one incoming edge, i.e., there exists exactly one v0 2 V such that (v0; v) 2 E. We then call v0 the parent of v and v the child of v0. 3. Every node v 2 V can be reached from the root traversing edges, i.e., there is a number n 0 and a sequence (v)i2f0;:::;ng such that r = v0, v = vn, and for all i 2 f0; : : : ; n 1g we have (vi; vi+1) 2 E. A node without children will be called leaf node. A binary tree is a tree where every node that is not a leaf has exactly two children. An n-ary tree is a tree where every node that is not a leaf has exactly n children. An n-bounded tree is a tree where every node has at most n children. A tree is nite if V is nite.
When modeling trees using some logic-based KR language, we would like to achieve that we can create a knowledge base which has exactly all ( nite) trees as its models (possibly using additional auxiliary vocabulary), in other words, we would like to characterize or axiomatize the class of all ( nite) trees.
Unfortunately, it is not too hard to show that this is not possible by any
KR formalism that is expressible in rst order predicate logic (FOL). A very
helpful tool for showing this is the well-known compactness theorem of
rstorder logic[
Theorem 1 (Compactness of FOL). A set if and only if every nite subset of is. of FOL sentences is satis able
We now use this theorem to show our negative result.
Proposition 1. Let be a FOL sentence (using the binary predicate \edge") such that every nite tree T = (V; E) corresponds to some model I of , i.e., (V; E) = ( I ; edgeI ). Then, also has a model which does not correspond to any ( nite or in nite) tree.
Proof. Consider the following sequence ('i)i2N of FOL sentences (where a is a fresh constant): '1 := 9x1:edge(x1; a) '2 := 9x19x2:edge(x2; x1) ^ edge(x1; a) '3 := 9x19x29x3:edge(x3; x2) ^ edge(x2; x1) ^ edge(x1; a) . . .
In words, 'k expresses that the node a has an incoming edge-path of length k. Now let := f g [ f'k j k 2 Ng. Obviously, every nite subset of is satis able (intuitively, just pick an arbitrary large nite tree and then pick a such that it is \deep enough" in the tree). Then, by compactness of FOL, itself must be satis able. However, in a model I of the element aI cannot be reachable from the root, since then it would have an incoming edge-path of maximal length which cannot be the case by construction of . Hence I cannot correspond to a tree. By construction, I is also a model of . tu
This result shows, that trees ( nite or in nite) are not fully axiomatizable in FOL and any attempt to do so will only be approximate (although practically useful).
On the other hand, trees are axiomatizable when we extend FOL (or just DLs for that matter) by a transitive closure operator for binary predicates. Assume that, for every binary predicate (or in DL terms: role) p, we allow for a binary predicate/role name p+ and de ne its semantics such that (p+)I is the transitive closure of pI . Then the conditions of De nition 1 can be expressed using the following axioms:
frootg v :9edge :> :frootg v =1 edge :> :frootg v 9(edge )+:frootg > v :9edge:> t =2 edge:> To axiomatize the class of binary trees, the following axiom can be added: In order to impose niteness, one can axiomatize (as an auxiliary additional structure) a nite linear order with a starting element and an ending element and the successor role:
fstartg v :9succ :> :fstartg v =1 succ :> :fstartg v 9(succ )+:fstartg (5) (6) (7)
fendg v :9succ:> :fendg v =1 succ:> :fendg v 9(succ)+:fendg
Transitive closures, of course, are not part of the OWL speci cation [13],
i.e., this characterization cannot be used when modeling in the Web Ontology
Language. Description logics featuring regular expressions over roles have,
however, been considered since the early days of DL research [
The repository of ontology design patterns on ontologydesignpatterns.org does not contain any pattern for trees. There is also none for graphs which could have been used to specialize a trees pattern. The repository contains a pattern for lists, though,5 and a list pattern could be generalizable to a tree pattern.
The schema diagram for this list pattern is depicted in Figure 1. It reuses the sequence pattern6 which seems to be the relevant part for our purposes. We depict the sequence pattern schema diagram in Figure 2 and all non-tautological axioms are given in Figure 3.7 The axiomatization appears to be rather minimalistic, e.g., \follows" should be transitive over \directlyFollows", and for a sequence we should also use cardinality restrictions to limit the number of followers and predecessors. We will return to this later on.
The list pattern just cited provides basic building blocks for a simple tree
pattern. However, we opt to change the names of the properties: It seems to be
5 http://ontologydesignpatterns.org/wiki/Submissions:List
6 http://ontologydesignpatterns.org/wiki/Submissions:Sequence
7 Generated with the OWLAPI LATEX renderer [
Before proceeding with the tree pattern, we present a set of competency questions [17] which seem representative to us and include operationes raised as important in Section 2: 1. Determine the root. 2. Determine all ancestors of a given node. 3. Determine all leaves. 4. Determine all descendants of a given node. 5. Determine all descendants of a given node which are leaves. 6. Given two nodes, determine whether one is a descendant of the other. 7. Given two nodes, determine all commmon ancestors. 8. Given two nodes, determine the latest common ancestor. 9. Given two nodes x and y, determine the earliest ancestor of x which is not an ancestor of y.
We next give our proposal for a simple tree pattern. Afterwards we will discuss our design choices. The schema diagram is given in Figure 4. However, directlyFollows v follows directlyFollows
directlyPrecedes directlyPrecedes v precedes precedes
follows TransitiveProperty(follows)
TransitiveProperty(precedes) the axiomatization is really much more important; it can be found in Figure 6. Note that some additional desired axioms, such as hasParent v hasAncestor and transitivity of hasAncestor can be inferred from the ones stated.
Before we proceed, let us rst make a concrete example how this pattern informs the graph structure of the ABox. Given a tree such as d b a e c f we encode it using the ABox from Figure 5; note that we omit redundant statements which can be inferred from the axioms.
The axioms from Figure 6 should be self-explanatory. Axiom (16) uses a datatype facet. The complete set of axioms is not in OWL DL because axioms (32) and (33) declare irre exivity for non-simple roles. If it is desireable to stay within OWL DL, these axioms could be omitted.
Our pattern and axiomatization include some terms which may appear to be redundant. Indeed, we could have omitted the use of hasParent and hasAncestor as these are simply inverses of hasChild and hasDescendant, respectively. Other aspects, however, are not redundant.
The property hasOutDegree may appear to be redundant, as it captures the
number of children of a node. However, it is not redundant as far as the OWL
model is concerned, because the underlying open world assumption makes it
impossible to count the number of children. This could of course be addressed
using a (local) closed world extension of OWL, such as in [
The case of the hasSibling property is more intricate. Again it would naively appear as if it were redundant. However, we have not been able yet to axiomatize it in the general case; for special cases where it is possible see Section 5. A naive attempt by means of a rule8
hasParent(x; y) ^ hasChild(y; z) ! hasSibling(x; z) 8 This rule can be converted into OWL DL using roli cation, see [18].
RootNode v TreeNode TreeNode v 8hasOutDegree:xsd:positiveInteger TreeNode v =1hasOutDegree:xsd:positiveInteger LeafNode TreeNode u 8hasOutDegree:f0^^xsd:positiveIntegerg TreeNode u 8hasOutDegree:fx^^xsd:positiveInteger j 1 is insu cient because for addressing some competency questions we require irre exivity of hasSibling, while the rule above renders hasSibling to be non-simple, which is not allowed together with irre exivity in OWL DL.
Let us return to the competency questions listed earlier; it turns out we can address them all even when omitting the irre exivity axioms for hasDescendant and hasAncestor, such that our model stays within OWL DL. Questions 1 and 3 can be addressed using the RootNode and LeafNode classes. Questions 2 and 4 are straightforward, as is question 5 using the LeafNode class. Question 6 can be solved with two queries using the hasDescendant property.
The remaining questions are more intricate. Given two nodes x and y, Question 7 can be addressed via
Question 8 seems to require use of the hasSibling property. For readability we rst give the solution as rst-order predicate logic formula: hasChild(z; w) ^ (w = x _ hasDescendant(w; x)) ^ hasSibling(w; v) ^ (v = y _ hasDescendant(v; y)): Conversion of this into OWL following the approach laid out in [18] results in the class description
u (9hasSibling:(fyg t 9hasDescendant:fyg)): In a similar fashion, Question 9 can be addressed using the class description (fxg t 9hasDescendant:fxg) u (9hasSibling:(fyg t 9hasDescendant:fyg)): Note that irre exivity of hasSibling is required for the class descriptions just given. Or to be more precise, what is required is that there is no node z in the tree for which hasSibling(z; z) is declared or can be inferred; note that this is in fact a weaker requirement than what we get by declaring irre exivity. As a consequence, the irre exivity declaration for hasSibling can actually be omitted from the axiomatization without impact on the just given solution to Question 9; however we prefer to keep the irre exivity declaration in the axiomatization as it disambiguates the model [12]. As mentioned earlier, we have not been able to nd a solution to infer the (irre exive) hasSibling relationship in the general case using OWL axioms, thus we require it as a primitive. We will revisit this in the next section, though.
Let us nally use our tree pattern to recover a list pattern based on it. The schema diagram can be found in Figure 7. We keep only one property, hasNext, which corresponds to hasChild, and hasSuccessor, which corresponds to hasDescendant. The root becomes the rst list item, the leaves become the last list item. The outdegree is always 1 unless it's the last list item, so we also omit this information. The corresponding axiomatization, as derived from the hasNext hasSuccessor v hasSuccessor
Irre exive(hasSuccessor) tree axiomatization above, can be found in Figure 8. As before, Axiom (46) causes the pattern to fall outside OWL DL, and if this is undesirable, this axiom should be omitted. 5
In this section, we look at n-bounded trees as a special case, and present a set of OWL axioms that can be employed to model these.
De nition 2. A rooted directed branching n-bounded tree (short: n-bounded tree) is a tree T = (V; E) where every node has at most n outgoing edges; i.e., for every v 2 V , jE \ (fvg V )j n.
In the previous section, we have discussed why we needed to include an explicit hasSibling relation in our model, namely because we were unable to axiomatically de ne it in OWL. If we know that the trees under consideration are n-bounded, though, we can in fact infer the hasSibling relation. n-BoundedTreeNode v TreeNode n-BoundedTreeNode v 8hasAncestor:n-BoundedTreeNode n-BoundedTreeNode v 8hasDescendant:n-BoundedTreeNode n-BoundedTreeNode v Child1 t : : : t Childn fn-BoundedTreeNode v
To this end, we introduce a set of additional axioms (see Figure 9) that, if combined with the axioms from Figure 6 can be used to axiomatize the structure of an n-bounded tree. Key to this are axioms (50) and (51), which together limit the number of children per node to a maximum of n.
Note that, if these axioms are considered, we can indeed automatically infer the hasSibling relationship: Having an upper bound on the number of children per node, we can use a nite set of concept names Childi to di erentiate the children of any given node in the tree. Note how, due to (50) and (51), every n-ary tree node is typed by one and only one class Childi. Moreover, axioms in (52) enforce that at most one child of every node is in the class Childi for every i = 1; : : : ; n. Using axioms in (54), we automatically infer that each child of every node is connected to itself via some property Ri for some i = 1; : : : ; n. Using axiom (55), we can infer the hasSibling relation.
Note, though, that hasSibling is non-simple, i.e. the declaration of irre exivity for hasSibling from Figure 6 violates regularity. If the ontology shall fall within OWL DL, the irre exivity axiom should be removed.
Note also, that the approach just spelled out may not be practical for large n, as the number of models to be checked, e.g. by a tableaux-based reasoner, will increase exponentially with n due to the disjunction in (50). 6
We have presented a general ontology design pattern for trees together with an axiomatization which makes it possible to answer non-trivial competency questions as they arise in practice. We have also presented a list pattern derived from this tree pattern. We have furthermore discussed limitations of OWL for the modeling of trees, and have provided an alternative axiomatization for the more speci c case that the tree is known to be n-bounded.
Of course, our approach is still rather straightforward and there exist cases where our model will not su ce. For example, in the application domain discussed in Section 2, it is often desirable to attach additional information to parent-child relationships (i.e., edges), e.g. temporal information. This cannot be done in our current model but would require a rei cation of the edges using established techniques, and of course this change may a ect the treatment of our competency questions. This remains to be investigated.
Acknowledgements. Pascal Hitzler and Hilmar Lapp acknowledge support by the National Science Foundation (NSF) under awards 1440202 \Earthcube Building Blocks: Collaborative Proposal: GeoLink { Leveraging Semantics and Linked Data for Data Sharing and Discovery in the Geosciences", and DBI-1458484 \An Ontology-Based System for Querying Life in a Post-Taxonomic Age", respectively. 11. Hinchli , C.E., Smith, S.A., Allman, J.F., Burleigh, J.G., Chaudhary, R., Coghill, L.M., Crandall, K.A., Deng, J., Drew, B.T., Gazis, R., Gude, K., Hibbett, D.S., Katz, L.A., Laughinghouse, 4th, H.D., McTavish, E.J., Midford, P.E., Owen, C.L., Ree, R.H., Rees, J.A., Soltis, D.E., Williams, T., Cranston, K.A.: Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc. Natl. Acad. Sci. U. S. A. 112(41), 12764{12769 (13 Oct 2015), http://dx.doi.org/10.1073/pnas. 1423041112 12. Hitzler, P., Krisnadhi, A.: On the roles of logical axiomatizations for ontologies. In: Hitzler, P., Gangemi, A., Janowicz, K., Krisnadhi, A., Presutti, V. (eds.) Ontology Engineering with Ontology Design Patterns { Foundations and Applications, Studies on the Semantic Web, vol. 25, pp. 73{80. IOS Press (2016) 13. Hitzler, P., Krotzsch, M., Parsia, B., Patel-Schneider, P.F., Rudolph, S. (eds.): OWL 2 Web Ontology Language Primer (Second Edition). W3C Recommendation (11 December 2012), http://www.w3.org/TR/owl2-primer/ 14. Hitzler, P., Krotzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies.
CRC Press/Chapman & Hall (2010) 15. Huelsenbeck, J.P., Bollback, J.P., Levine, A.M.: Inferring the root of a phylogenetic tree. Syst. Biol. 51(1), 32{43 (Feb 2002), http://dx.doi.org/10.1080/ 106351502753475862 16. Jarvis, E.D., Mirarab, S., Aberer, A.J., Li, B., Houde, P., Li, C., Ho, S.Y.W., Faircloth, B.C., Nabholz, B., Howard, J.T., Suh, A., Weber, C.C., da Fonseca, R.R., Li, J., Zhang, F., Li, H., Zhou, L., Narula, N., Liu, L., Ganapathy, G., Boussau, B., Bayzid, M.S., Zavidovych, V., Subramanian, S., Gabaldon, T., Capella-Gutierrez, S., Huerta-Cepas, J., Rekepalli, B., Munch, K., Schierup, M., Lindow, B., Warren, W.C., Ray, D., Green, R.E., Bruford, M.W., Zhan, X., Dixon, A., Li, S., Li, N., Huang, Y., Derryberry, E.P., Bertelsen, M.F., Sheldon, F.H., Brum eld, R.T., Mello, C.V., Lovell, P.V., Wirthlin, M., Schneider, M.P.C., Prosdocimi, F., Samaniego, J.A., Vargas Velazquez, A.M., Alfaro-Nun~ez, A., Campos, P.F., Petersen, B., Sicheritz-Ponten, T., Pas, A., Bailey, T., Sco eld, P., Bunce, M., Lambert, D.M., Zhou, Q., Perelman, P., Driskell, A.C., Shapiro, B., Xiong, Z., Zeng, Y., Liu, S., Li, Z., Liu, B., Wu, K., Xiao, J., Yinqi, X., Zheng, Q., Zhang, Y., Yang, H., Wang, J., Smeds, L., Rheindt, F.E., Braun, M., Fjeldsa, J., Orlando, L., Barker, F.K., J nsson, K.A., Johnson, W., Koep i, K.P., O'Brien, S., Haussler, D., Ryder, O.A., Rahbek, C., Willerslev, E., Graves, G.R., Glenn, T.C., McCormack, J., Burt, D., Ellegren, H., Alstrom, P., Edwards, S.V., Stamatakis, A., Mindell, D.P., Cracraft, J., Braun, E.L., Warnow, T., Jun, W., Gilbert, M.T.P., Zhang, G.: Wholegenome analyses resolve early branches in the tree of life of modern birds. Science 346(6215), 1320{1331 (12 Dec 2014), http://dx.doi.org/10.1126/science.1253451 17. Krisnadhi, A., Hitzler, P.: Modeling with ontology design patterns: Chess games as a worked example. In: Hitzler, P., Gangemi, A., Janowicz, K., Krisnadhi, A., Presutti, V. (eds.) Ontology Engineering with Ontology Design Patterns: Foundations and Applications, Studies on the Semantic Web, vol. 25, pp. 3{22. IOS Press, Amsterdam (2016) 18. Krisnadhi, A., Maier, F., Hitzler, P.: OWL and rules. In: Polleres, A., d'Amato, C., Arenas, M., Handschuh, S., Kroner, P., Ossowski, S., Patel-Schneider, P.F. (eds.) Reasoning Web. Semantic Technologies for the Web of Data { 7th International Summer School 2011, Galway, Ireland, August 23-27, 2011, Tutorial Lectures. Lecture Notes in Computer Science, vol. 6848, pp. 382{415. Springer (2011) 19. Maddison, W.P., Donoghue, M.J., Maddison, D.R.: Outgroup analysis and parsimony. Syst. Biol. 33(1), 83{103 (1 Mar 1984), https://academic.oup.com/