=Paper=
{{Paper
|id=Vol-2043/paper-01
|storemode=property
|title=On the Ontological Modeling of Trees
|pdfUrl=https://ceur-ws.org/Vol-2043/paper-01.pdf
|volume=Vol-2043
|authors=David Carral,Pascal Hitzler,Hilmar Lapp,Sebastian Rudolph
|dblpUrl=https://dblp.org/rec/conf/semweb/CarralHLR17
}}
==On the Ontological Modeling of Trees==
https://ceur-ws.org/Vol-2043/paper-01.pdf
On the Ontological Modeling of Trees
David Carral1 , Pascal Hitzler2 , Hilmar Lapp3 , and Sebastian Rudolph1
1
TU Dresden, Germany
2
Data Semantics (DaSe) Laboratory, Wright State University, OH, USA
3
Center for Genomic and Computational Biology, Duke University, Durham, NC,
USA
Abstract. Trees – i.e., the type of data structure known under this
name – are central to many aspects of knowledge organization. We in-
vestigate 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.
1 Introduction
Trees are fundamental data structures for knowledge organization. They make
their appearance in the form of taxonomies, meronomies, decision trees, branch-
ing processes, etc. As such they are fundamental for ontological knowledge rep-
resentation.
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 different ways to do it.
We need to realize, of course, that trees in ontology modeling often serve a
different purpose than in programming. Operations on trees important in pro-
gramming 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 ontologydesign-
patterns.org. In this paper, we will provide such a pattern, and will also discuss
different 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 http://ontologydesignpatterns.org/wiki/
Submissions:Tree_Pattern
2 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
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 Phylogenetic Trees
One of the central tenets following from the theory of organismal evolution is
that all life is related through descent with modification [4]. That is, populations
of a biological species can over time diverge enough, due to natural selection,
adaptation, genetic drift, and other forces acting differentially on different popu-
lations, that they form new species, some of which persist and go on themselves
to split, giving rise to new species, and so forth. Speciation through diversifica-
tion can sometimes be driven by new ecologic opportunities, for example when
new habitats are being colonized, a process often referred to as adaptive radiation
[27,28]. One of the most prominent research objectives in evolutionary science
is to reconstruct, using genetic and organismal trait data, the evolutionary his-
tory of different organisms, species, or life forms; i.e., to reconstruct the lines of
shared descent by which organisms are connected [9,30]. Such a reconstruction
is represented in the form of a phylogenetic tree, in which the leaves are often
called operational taxonomic units (OTUs) and represent the sampled entities,
and internal nodes represent ancestral entities, such as ancestral populations
from which descendent ones diverged. Phylogenetic reconstruction results in un-
rooted trees; the root is normally not known (and cannot normally be sampled),
but reasonably accurate mechanisms for inducing a root exist [15,19] (for exam-
ple, by including in the reconstruction analysis a group of species – a so-called
“outgroup” – that are already known to fall outside of the ingroup for which
evolutionary patterns are being studied).
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 com-
parative phylogenetics is to identify the properties and processes (organismal
traits, geographic range, tempo and mode of evolution, etc) by which one clade
differs from others, in particular its sisters, and how these properties change
along lines of descent in the tree [8,22]. This gives rise to a number of impor-
tant queries when mapping data onto phylogenetic trees for (or as a result of)
analysis. Particularly ubiquitous operations on trees include the following: (1)
finding the most recent common ancestor of a given number of nodes (usually
leaf nodes); (2) enumerating the leaf nodes, or all nodes descending from a given
(internal) node; (3) enumerating the sequence of ancestors of a node to the root;
and (4) identifying the last ancestor of a node A from which another node B is
not also descended. We will come back to these and other operations as part of
the competency questions for our modeling in Section 4.
Operations (1) and (4) correspond to two principle ways in which the seman-
tics of clade concepts can be defined on a tree [23], whether using a concrete
On the Ontologial Modeling of Trees 3
instantiation of a tree, or a hypothetical one. In the field of phylogenetic tax-
onomy [24], a clade concept defined by the most recent common ancestor of a
set of (usually leaf) nodes includes the common ancestor and is referred to as a
node-based definition. In contrast, a branch-based definition circumscribes the
clade as the last ancestor of a (usually leaf) node that excludes (i.e., does not
have as a descendant) another node (also usually a leaf node). The semantics
of a clade concept defined in this way is such that the branch subtending from
the ancestor node to its parent is included (hence the name branch-based). To
understand this, remember that a phylogenetic tree is a model of evolutionary
lines of descent reconstructed from sampled data. In reality, there may be lines
of descent which were not observed (sampled), for example because all organ-
isms from those lines are now extinct, but which, had they been observed, would
originate from the subtending branch and which would therefore still be included
in the clade because they would branch off after the lineage to be excluded.
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 [10,6,7,29,16],
culminating in the initial publication of the synthesized Open Tree of Life with
about 2 million tips [11]. Such encompassing trees open up unprecedented oppor-
tunities for comparative phylogenetic research. However, this also means that our
knowledge about the evolution of life is changing at increasing pace and breadth,
which makes it necessary to efficiently map clade definitions from one tree to
another, or from one revision of the Open Tree of Life to a future one. A recent
initiative, termed “phyloreferencing” (http://phyloref.org) aims to accomplish
this by using machine reasoning over ontological representations of the seman-
tics of both clade definitions and phylogenetic trees [3,21,25]. In the rest of this
paper, we abstract from the specific use case and look at the task of ontological
modeling of trees in general.
3 Fundamental Limitations Regarding Tree Modeling
In order to investigate to what degree tree-based properties can be expressed
using common KR formalisms, we first need to formally define what structures
we denote by the notion “tree”.
Definition 1. A rooted directed branching tree (short: tree) is defined 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 ∈ V called root, which has no incoming edges,
i.e., E ∩ (V × {r}) = ∅.
2. Every node v ∈ V \ {r} that is not the root has exactly one incoming edge,
i.e., there exists exactly one v 0 ∈ V such that (v 0 , v) ∈ E. We then call v 0
the parent of v and v the child of v 0 .
3. Every node v ∈ V can be reached from the root traversing edges, i.e., there
is a number n ≥ 0 and a sequence (v)i∈{0,...,n} such that r = v0 , v = vn , and
for all i ∈ {0, . . . , n − 1} we have (vi , vi+1 ) ∈ E.
4 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
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 finite if V is finite.
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 (finite) trees
as its models (possibly using additional auxiliary vocabulary), in other words,
we would like to characterize or axiomatize the class of all (finite) trees.
Unfortunately, it is not too hard to show that this is not possible by any
KR formalism that is expressible in first order predicate logic (FOL). A very
helpful tool for showing this is the well-known compactness theorem of first-
order logic[5].
Theorem 1 (Compactness of FOL). A set Φ of FOL sentences is satisfiable
if and only if every finite subset of Φ is.
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 finite 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 (finite or infinite) tree.
Proof. Consider the following sequence (ϕi )i∈N of FOL sentences (where a is a
fresh constant):
ϕ1 := ∃x1 .edge(x1 , a)
ϕ2 := ∃x1 ∃x2 .edge(x2 , x1 ) ∧ edge(x1 , a)
ϕ3 := ∃x1 ∃x2 ∃x3 .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 Φ := {ψ} ∪ {ϕk | k ∈ N}. Obviously, every finite subset of Φ is
satisfiable (intuitively, just pick an arbitrary large finite tree and then pick a
such that it is “deep enough” in the tree). Then, by compactness of FOL, Φ
itself must be satisfiable. 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 ψ. t
u
This result shows, that trees (finite or infinite) 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 define its semantics such that (p+ )I is the
On the Ontologial Modeling of Trees 5
transitive closure of pI . Then the conditions of Definition 1 can be expressed
using the following axioms:
{root} v ¬∃edge− .> (1)
−
¬{root} v =1 edge .> (2)
− +
¬{root} v ∃(edge ) .{root} (3)
To axiomatize the class of binary trees, the following axiom can be added:
> v ¬∃edge.> t =2 edge.> (4)
In order to impose finiteness, one can axiomatize (as an auxiliary additional
structure) a finite linear order with a starting element and an ending element
and the successor role:
{start} v ¬∃succ− .> (5) {end} v ¬∃succ.> (8)
−
¬{start} v =1 succ .> (6) ¬{end} v =1 succ.> (9)
− + +
¬{start} v ∃(succ ) .{start} (7) ¬{end} v ∃(succ) .{end} (10)
Transitive closures, of course, are not part of the OWL specification [13],
i.e., this characterization cannot be used when modeling in the Web Ontology
Language. Description logics featuring regular expressions over roles have, how-
ever, been considered since the early days of DL research [1] and decision and
query answering procedures have been described for very expressive DLs with
that feature [2].
4 A Simple Tree Pattern
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 mini-
malistic, e.g., “follows” should be transitive over “directlyFollows”, and for a
sequence we should also use cardinality restrictions to limit the number of fol-
lowers 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 [26].
6 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
Fig. 1. List pattern schema diagram from ontologydesignpatterns.org
more appropriate to use “hasChild” and “hasDescendant” rather than “direct-
lyPrecedes” and “precedes”, and to use “hasParent” and “hasAncestor” rather
than “directlyFollows” and “follows.”
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,
On the Ontologial Modeling of Trees 7
Fig. 2. Sequence pattern schema diagram from ontologydesignpatterns.org
directlyFollows v follows
directlyFollows ≡ directlyPrecedes−
directlyPrecedes v precedes
precedes ≡ follows−
TransitiveProperty(follows)
TransitiveProperty(precedes)
Fig. 3. Axioms for the sequence pattern from Figure 2. We omitted axioms that were
tautologies.
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 first make a concrete example how this pattern
informs the graph structure of the ABox. Given a tree such as
a
b c
d e f
we encode it using the ABox from Figure 5; note that we omit redundant state-
ments 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 irreflexivity for non-simple roles. If it is desireable to stay
within OWL DL, these axioms could be omitted.
8 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
Fig. 4. Schema diagram for the simple tree pattern. Unlabelled arrows are subclass
relationships.
RootNode(a) LeafNode(d) LeafNode(e)
LeafNode(f ) TreeNode(b) TreeNode(c)
hasChild(a, b) hasChild(a, c) hasChild(b, d)
hasChild(b, e) hasChild(c, f ) hasSibling(b, c)
hasSibling(d, e) hasOutDegree(a, 2) hasOutDegree(b, 2)
hasOutDegree(c, 1) hasOutDegree(d, 0) hasOutDegree(e, 0)
hasOutDegree(f, 0)
Fig. 5. Example ABox for a tree.
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 [20], however the
current standard does not support this. For the same reason, membership in the
classes RootNode and LeafNode cannot be inferred.
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 rolification, see [18].
On the Ontologial Modeling of Trees 9
LeafNode v TreeNode (11)
RootNode v TreeNode (12)
TreeNode v ∀hasOutDegree.xsd:positiveInteger (13)
TreeNode v =1hasOutDegree.xsd:positiveInteger (14)
LeafNode ≡ TreeNode u
∀hasOutDegree.{0∧∧ xsd:positiveInteger} (15)
TreeNode u ¬LeafNode ≡ TreeNode u
∀hasOutDegree.{x∧∧ xsd:positiveInteger | 1 ≤ x}
(16)
hasChild ≡ hasParent− (17)
−
hasDescendant ≡ hasAncestor (18)
hasChild v hasDescendant (19)
hasDescendant ◦ hasDescendant v hasDescendant (20)
TreeNode v ∀hasChild.TreeNode (21)
TreeNode u ¬LeafNode ≡ TreeNode u ∃hasChild.TreeNode (22)
TreeNode v ∀hasDescendant.TreeNode (23)
TreeNode v ∀hasParent.TreeNode (24)
TreeNode v ∀hasSibling.TreeNode (25)
TreeNode u ¬RootNode ≡ TreeNode u =1hasParent.> (26)
TreeNode v ∀hasAncestor.TreeNode (27)
RootNode ≡ TreeNode u ¬∃hasParent.> (28)
LeafNode ≡ TreeNode u ¬∃hasChild.> (29)
Irreflexive(hasChild) (30)
Irreflexive(hasParent) (31)
Irreflexive(hasDescendant) (32)
Irreflexive(hasAncestor) (33)
−
hasSibling ≡ hasSibling (34)
Irreflexive(hasSibling) (35)
Fig. 6. Axioms for the tree pattern from Figure 4.
10 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
is insufficient because for addressing some competency questions we require ir-
reflexivity of hasSibling, while the rule above renders hasSibling to be non-simple,
which is not allowed together with irreflexivity in OWL DL.
Let us return to the competency questions listed earlier; it turns out we can
address them all even when omitting the irreflexivity 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, Ques-
tion 7 can be addressed via
∃hasDescendant.{x} u ∃hasDescendant.{y}.
Question 8 seems to require use of the hasSibling property. For readability we
first give the solution as first-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
∃hasChild.(({x} t ∃hasDescendant.{x})
u (∃hasSibling.({y} t ∃hasDescendant.{y})).
In a similar fashion, Question 9 can be addressed using the class description
({x} t ∃hasDescendant.{x}) u (∃hasSibling.({y} t ∃hasDescendant.{y})).
Note that irreflexivity 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 irreflexivity. As a
consequence, the irreflexivity 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 irreflexivity declaration in the axiomatization as
it disambiguates the model [12]. As mentioned earlier, we have not been able
to find a solution to infer the (irreflexive) 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 finally 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 first 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
On the Ontologial Modeling of Trees 11
Fig. 7. Schema diagram for the simple list pattern, derived from the tree pattern.
FirstListItem v ListItem (36)
LastListItem v ListItem (37)
ListItem v ∀hasNext.ListItem (38)
ListItem v ∀hasNext− .ListItem (39)
ListItem u ¬LastListItem ≡ ListItem u =1hasNext.ListItem (40)
ListItem u ¬FirstListItem ≡ ListItem u =1hasNext− .ListItem (41)
−
FirstListItem ≡ ListItem u ¬∃hasNext .> (42)
LastListItem ≡ ListItem u ¬∃hasNext.> (43)
hasNext v hasSuccessor (44)
hasNext ◦ hasSuccessor v hasSuccessor (45)
Irreflexive(hasSuccessor) (46)
Fig. 8. Axioms for the lists pattern from Figure 7.
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 Trees With Bounded Arity
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.
Definition 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 ∈ V , |E ∩ ({v} × V )| ≤ 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 define it in OWL. If we know that the trees under consideration
are n-bounded, though, we can in fact infer the hasSibling relation.
12 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
n-BoundedTreeNode v TreeNode (47)
n-BoundedTreeNode v ∀hasAncestor.n-BoundedTreeNode (48)
n-BoundedTreeNode v ∀hasDescendant.n-BoundedTreeNode (49)
n-BoundedTreeNode v Child1 t . . . t Childn (50)
{Childi u Childj v ⊥ | 1 ≤ i < j ≤ n} (51)
{n-BoundedTreeNode v ≤1hasChild.Childi | 1 ≤ i ≤ n} (52)
n-BoundedTreeNode v ≤nhasChild.n-BoundedTreeNode (53)
{Childi v ∃Ri .Self | 1 ≤ i ≤ n} (54)
{Ri ◦ hasParent ◦ hasChild ◦ Rj v hasSibling | 1 ≤ i < j ≤ n} (55)
Fig. 9. Axioms for the n-bounded Tree Pattern: These need to be added to the axioms
from Figure 6
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 finite set of concept names Childi to differentiate 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 irreflexivity
for hasSibling from Figure 6 violates regularity. If the ontology shall fall within
OWL DL, the irreflexivity 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 Conclusions
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 specific case that the tree is known to be n-bounded.
On the Ontologial Modeling of Trees 13
Of course, our approach is still rather straightforward and there exist cases
where our model will not suffice. For example, in the application domain dis-
cussed 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 reification of the edges using
established techniques, and of course this change may affect 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”, re-
spectively.
References
1. Baader, F.: Augmenting concept languages by transitive closure of roles: An
alternative to terminological cycles. In: Mylopoulos, J., Reiter, R. (eds.) Pro-
ceedings of the 12th International Joint Conference on Artificial Intelligence.
Sydney, Australia, August 24-30, 1991. pp. 446–451. Morgan Kaufmann (1991),
http://ijcai.org/Proceedings/91-1/Papers/069.pdf
2. Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive descrip-
tion logics with nominals. In: Boutilier, C. (ed.) IJCAI 2009, Proceedings of the
21st International Joint Conference on Artificial Intelligence, Pasadena, Califor-
nia, USA, July 11-17, 2009. pp. 714–720 (2009), http://ijcai.org/Proceedings/09/
Papers/124.pdf
3. Cellinese, N., Lapp, H.: An Ontology-Based system for querying life in a Post-
Taxonomic age (2015), https://figshare.com/articles/An Ontology Based System
for Querying Life in a Post Taxonomic Age/1401984
4. Darwin, C.: On the Origin of Species. John Murray, London, 6 edn. (1859)
5. Dawson Jr., J.W.: The compactness of first-order logic:from Gdel to Lindstrm.
History and Philosophy of Logic 14(1), 15–37 (1993)
6. Driskell, A.C., Ané, C., Burleigh, J.G., McMahon, M.M., O’meara, B.C., Sander-
son, M.J.: Prospects for building the tree of life from large sequence databases.
Science 306(5699), 1172–1174 (12 Nov 2004), http://dx.doi.org/10.1126/science.
1102036
7. Dunn, C.W., Hejnol, A., Matus, D.Q., Pang, K., Browne, W.E., Smith, S.A.,
Seaver, E., Rouse, G.W., Obst, M., Edgecombe, G.D., Sørensen, M.V., Had-
dock, S.H.D., Schmidt-Rhaesa, A., Okusu, A., Kristensen, R.M., Wheeler, W.C.,
Martindale, M.Q., Giribet, G.: Broad phylogenomic sampling improves resolu-
tion of the animal tree of life. Nature 452(7188), 745–749 (Apr 2008), http:
//dx.doi.org/10.1038/nature06614
8. Felsenstein, J.: Phylogenies and the comparative method. Am. Nat. 125(1), 1–15
(1985), http://www.jstor.org/stable/10.2307/2461605
9. Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, 2 edn. (4 Sep 2003)
10. Goloboff, P., Catalano, S., Mirande, J., Szumik, C., Arias, J., Källersjö, M., Farris,
J.: Phylogenetic analysis of 73 060 taxa corroborates major eukaryotic groups.
Cladistics 25(3), 211 (2009), http://dx.doi.org/10.1111/j.1096-0031.2009.00255.x
14 David Carral, Pascal Hitzler, Hilmar Lapp, Sebastian Rudolph
11. Hinchliff, 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.) Ontol-
ogy Engineering with Ontology Design Patterns – Foundations and Applications,
Studies on the Semantic Web, vol. 25, pp. 73–80. IOS Press (2016)
13. Hitzler, P., Krötzsch, 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., Krötzsch, 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 phy-
logenetic 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., Fair-
cloth, 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., Gabaldón, T., Capella-Gutiérrez,
S., Huerta-Cepas, J., Rekepalli, B., Munch, K., Schierup, M., Lindow, B., War-
ren, 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., Brumfield,
R.T., Mello, C.V., Lovell, P.V., Wirthlin, M., Schneider, M.P.C., Prosdocimi, F.,
Samaniego, J.A., Vargas Velazquez, A.M., Alfaro-Núñez, A., Campos, P.F., Pe-
tersen, B., Sicheritz-Ponten, T., Pas, A., Bailey, T., Scofield, P., Bunce, M., Lam-
bert, 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., Koepfli, K.P., O’Brien, S., Haussler, D., Ry-
der, O.A., Rahbek, C., Willerslev, E., Graves, G.R., Glenn, T.C., McCormack, J.,
Burt, D., Ellegren, H., Alström, P., Edwards, S.V., Stamatakis, A., Mindell, D.P.,
Cracraft, J., Braun, E.L., Warnow, T., Jun, W., Gilbert, M.T.P., Zhang, G.: Whole-
genome 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: Founda-
tions 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. Lec-
ture 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/
On the Ontologial Modeling of Trees 15
sysbio/article-abstract/33/1/83/1669598/Outgroup-Analysis-and-Parsimony?
redirectedFrom=fulltext
20. Martı́nez, D.C., Janowicz, K., Hitzler, P.: A logical geo-ontology design pattern
for quantifying over types. In: Cruz, I.F., Knoblock, C.A., Kröger, P., Tanin, E.,
Widmayer, P. (eds.) SIGSPATIAL 2012 International Conference on Advances
in Geographic Information Systems (formerly known as GIS), SIGSPATIAL’12,
Redondo Beach, CA, USA, November 7-9, 2012. pp. 239–248. ACM (2012)
21. Michael Keesey, T.: A mathematical approach to defining clade names, with po-
tential applications to computer storage and processing. Zool. Scr. 36(6), 607–621
(Nov 2007), http://dx.doi.org/10.1111/j.1463-6409.2007.00302.x
22. O’Meara, B.C.: Evolutionary inferences from phylogenies: A review of methods.
Annu. Rev. Ecol. Evol. Syst. 43(1), 267–85 (Nov 2011), http://dx.doi.org/10.1146/
annurev-ecolsys-110411-160331
23. de Queiroz, K., Gauthier, J.: Phylogeny as a central principle in tax-
onomy: Phylogenetic definitions of taxon names. Syst. Biol. 39(4), 307–
322 (1 Dec 1990), https://academic.oup.com/sysbio/article-abstract/39/4/307/
1646987/Phylogeny-as-a-Central-Principle-in-Taxonomy
24. de Queiroz, K., Gauthier, J.: Phylogenetic taxonomy. Annu. Rev. Ecol. Syst. 23(1),
449–480 (1 Nov 1992), https://doi.org/10.1146/annurev.es.23.110192.002313
25. Sereno, P.C.: The logical basis of phylogenetic taxonomy. Syst. Biol. 54(4), 595–619
(Aug 2005), http://dx.doi.org/10.1080/106351591007453
26. Shimizu, C., Hitzler, P., Horridge, M.: Rendering OWL in description logic syntax.
In: Proceedings of the ESWC 2017 Poster and Demo Session (2017), to appear
27. Simpson, G.G.: Tempo and Mode in Evolution. Columbia University Press, New
York (1949)
28. Simpson, G.G.: The Major Features of Evolution. Columbia University Press, New
York (1953)
29. Smith, S.A., Beaulieu, J.M., Donoghue, M.J.: Mega-phylogeny approach for com-
parative biology: an alternative to supertree and supermatrix approaches. BMC
Evol. Biol. 9, 37 (11 Feb 2009), http://dx.doi.org/10.1186/1471-2148-9-37
30. Swofford, D.L., Olsen, G.J., Waddell, P.J., Hillis, D.M.: Phylogenetic inference.
In: Hillis, D.M., Moritz, C., Mable, B.K. (eds.) Molecular systematics, pp. 407–
514. Sinauer Associates, Inc., 2 edn. (1996), http://www.citeulike.org/group/1390/
article/768694