]}-<>()

#  An Experiment on the Connection between the Description Logics’ Family
$\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$> and the Real World

Domenico Cantone<EMAIL_ADDRESS>
Antonio Pisasale<EMAIL_ADDRESS>
###### Abstract

This paper describes the analysis of a selected testbed of Semantic Web
ontologies, by a SPARQL query, which determines those ontologies that can be
related to the description logic $\mathcal{DL}$
<$\mathcal{\forall}_{0}^{\pi}$>, introduced in Cantone _et al._ , [4] and
studied in Longo, [9]. We will see that a reasonable number of them is
expressible within such computationally efficient language. We expect that, in
a long-term view, a temporalization of description logics, and consequently,
of OWL(2), can open new perspectives for the inclusion in this language of a
greater number of ontologies of the testbed and, hopefully, of the “real
world”.

## INTRODUCTION

In the last years, Semantic Web has increasingly expanded its area of
influence. Being an innovative instrument for the retrieval of not expressly
stored information and a way of organizing concepts and relations by their
meaning, it broadens up plenty of horizons for knowledge representation.
Though, only a bunch of experts and researchers know that under a suprisingly
vast dimension of new features there lies a mathematical and logical structure
inside which they fight day by day for the balancing of expressiveness and
efficiency. The _Description Logics_ formalisms, which we will see in Section
1, are the formal bases for the so-called Web 3.0, that should allow one to
automatically infer (and retrieve) new information from _reasoning_ on
“sematicized” knowledge repositories. Some examples of families of logics are
described in the following, together with a short coverage of arguments such
as RDF graphs and OWL.

Section 2 introduces the description logic $\mathcal{DL}$
<$\mathcal{\forall}_{0}^{\pi}$>, showing notable characteristics of expressive
power and polynomial complexity. In the same section, a more detailed
description of the analysis, which may be seen as a conceptual experiment,
follows. Our purpose is to show that a good number of real-world ontologies
may be related to this family of logics. Results are promising enough to spur
us to stay on this path and complement it with studies on temporalization of
Description Logics and, consequently, of Semantic Web (briefly touched in this
report), which we will approach in the near future.

The SPARQL query which was specifically created to assess the membership of
some real-world ontologies to the aforementioned logic is reported in Appendix
A.

##  1 THEORETICAL FUNDAMENTALS

###  1.1 Description Logics

_Description Logics_ (_DL_ s) are a family of formalisms for knowledge
representation, built on logic-based semantics. They are founded on some
fundamental ideas:

  * •

basic syntactic “blocks” are atomic concepts (1-ary predicates), atomic roles
(2-ary predicates) and individuals (costants);

  * •

the expressiveness of a certain language depends on the use of a set of chosen
constructors, that give birth to complex concepts and roles starting from
existing ones;

  * •

by means of classification of concepts, a _subsumption_ hierarchy is
established, which specifies what concept includes or is included by another;

  * •

implied knowledge is automatically obtained through a logic procedure, called
_reasoning_ , essentially based on the application of inference rules to
subsumption between concepts, and an instance definitions between individuals
and the latter.

On the assumption that a Knowledge Representation System (_KR-System_) is to
give an answer to a user query, _reasoning_ algorithms for DLs should be
regarded as decisional procedures which return a positive or negative verdict.
This raises the decision problem for such languages. Furthermore, having an
answer does not always mean getting it in a reasonable lapse of time, and that
compels us to consider also the complexity of algorithms at stake.
Decidability and complexity directly depend on the expressive power of the
description logic we use: whereas very expressive DLs tend to have inference
problems and be computationally _hard_ (or even undecidable), the DLs that are
more efficient in _reasoning_ turn out to be not espressive enough to
represent all concepts and relations in the domain of interest. Research still
going on in the field of DLs just aims at the ability of balancing
expressiveness against efficiency, while not dropping semantic precision that
could make it applicable to real world situations.

A _Description Logics Knowledge Base_ (_DLKB_) is made of two components: TBox
(_Terminological Box_) and ABox (_Assertional Box_). The former contains the
vocabulary, i.e., the definitions of atomic and non-atomic concepts and roles,
called _axioms_ , whereas the latter describes individuals in terms of this
vocabulary, i.e. it includes the declarations, called _assertions_ , of their
instances. By means of the TBox we can name complex descriptions of concepts
and roles. The language for such a naming is what distinguishes one DL from
another and is based on a _model-theoretic_ semantics. Thus statements in TBox
and ABox can be regarded as first-order logic formulas. _Reasoning_ procedures
for the terminological part are used to verify the _satisfiability_ of a
description (i.e., its non-contradictoriness), or whether it may be _subsumed_
by another (i.e., whether the latter is more general than the former), while
those for the assertive part establish whether its set of assertion is
_consistent_ (i.e., it has a model or it entails that a certain individual is
an instance of a given concept). Satisfiability tests for descriptions and
consistency tests for a set of assertion allow one to establish whether the
knowledge base is meaningful or not, whereas subsumption tests allow one to
maintain a hierarchy of concepts _ab universali_ ; finally, instance tests
give one the ability of querying the system against single individuals.

More formally, a generic DL axiom is a formula of one of the following types:

  * •

$C\equiv D$ (equivalence between concepts)

  * •

$C\sqsubseteq D$ (subsumption between concepts)

  * •

$R\equiv S$ (equivalence between roles)

  * •

$R\sqsubseteq S$ (subsumption between roles),111The equivalence and
subsumption between roles may be indicated also by the symbols $=$ and
$\subseteq$, respectively.

where the symbols $C,D$ are names or expressions of complex concepts, which
are formed by 1-ary or 2-ary operations on/between atomic (indicated by $A$ in
the following) or complex concepts, while $R,S$ are names or expressions of
complex roles which are formed by 1-ary or 2-ary operations on/between atomic
(indicated by $P$ in the following) or complex roles.

A generic DL assertion is a formula of one of the following types:

  * •

$C\left(a\right)$ (concept assertion)

  * •

$R\left(a,b\right)$ (role assertion),

where the symbols $a,b$ are names of individuals, for which the concept $C$ or
the role $R$ holds.222A large number of constructs is listed in the table at
the end of this section.

From a semantical point of view, an _interpretation_ $\mathcal{I}$ is a pair
$(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$, where the non-empty set
$\Delta^{\mathcal{I}}$ represents the domain of the interpretation and the
interpretation function $\cdot^{\mathcal{I}}$ associates a set
$A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$ to every atomic concept $A$ , a
relation
$P^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$ to
every atomic role $P$, and an element $a^{\mathcal{I}}\in\Delta^{\mathcal{I}}$
to every individual $a$. We write:333In the following,
$\mathcal{I}\models\phi$ means “$\mathcal{I}$ satisfies $\phi$, where $\phi$
can be an axiom or an assertion. A syntax/semantical reference for the main
axioms, assertions and property declarations is listed in the table at the end
of this section.

  * •

$\mathcal{I}\models\left(C\equiv D\right)$ iff444“Iff” is short for “if and
only if”. $C^{\mathcal{I}}=D^{\mathcal{I}}$

  * •

$\mathcal{I}\models\left(C\sqsubseteq D\right)$ iff $C^{\mathcal{I}}\subseteq
D^{\mathcal{I}}$

  * •

$\mathcal{I}\models\left(R\equiv S\right)$ iff
$R^{\mathcal{I}}=S^{\mathcal{I}}$

  * •

$\mathcal{I}\models\left(R\sqsubseteq S\right)$ iff $R^{\mathcal{I}}\subseteq
S^{\mathcal{I}}$

  * •

$\mathcal{I}\models C\left(a\right)$ iff $a^{\mathcal{I}}\in C^{\mathcal{I}}$

  * •

$\mathcal{I}\models R\left(a,b\right)$ iff $\left(a,b\right)^{\mathcal{I}}\in
R^{\mathcal{I}}$

Finally, we say that $\mathcal{I}$ is a _model_ for a DLKB $\mathcal{K}$ (and
write $\mathcal{I}\models\mathcal{K}$) if $\mathcal{I}$ satisfies all the
axioms and assertions of $\mathcal{K}$ . The latter is said to be _consistent_
if there exists at least an interpretation satisfying it, and the search of
this interpretation (_consistency problem_) is just the clue to _reasoning._

###  1.2 Families of logics

As already observed, distinct DLs are characterized by the constructs allowed
to form complex concepts and roles starting from atomic ones. The names are
usually specified by a series of alphabet letters and symbols. In the
following, we will not concentrate on formal semantics, but, for the sake of
clarity, we will only hint at the meaning of some constructs.

By way of an example, we briefly describe the $\mathcal{ALC}$ logic
(_Attributive Language with Complements_). Its syntax obeys the following
rules:

$C,D\rightarrow A\ |\ \top\ |\ \bot\ |\ \neg C\ |\ C\sqcap D\ |\ C\sqcup D\ |\
\forall R.C\ |\ \exists R.C\,\,,$

where $\top$ denotes the concept enclosing any other one (_top concept_),
$\bot$ denotes the concept enclosed in any other one (_bottom concept_),
$\neg$ negates a concept; $\sqcup$ represents the union of concepts (notice
the analogy with the corresponding set operators) and $\sqcap$ represents the
intersection of concepts. The last two constructs are called respectively
_universal_ and _existential restriction_ , and are pivotal in research
connected to this report. The concepts that can be built in $\mathcal{ALC}$
are called $\mathcal{ALC}$ -concepts.The axioms __ and assertions that may be
expressed in the $\mathcal{ALC}$ logic are

$C\equiv D,\ \,\ \,\ C\sqsubseteq D,\ \,\ \,\ C\left(a\right),$

which indicate, respectively, equivalence and subsumption (also called _GCI_ ,
_General Concept Inclusion_) between two concepts, and the membership of a
concept. However, _reasoning_ in $\mathcal{ALC}$ has a PSpace-complete
computational complexity.

In addition to those seen above, the most common constructs for concepts which
can be formed in DLs are $\leq 1.R$ (_functional restriction_ , denoted
$\mathcal{F}$ , that is equivalent to $\exists R.\top$), $\leq nR$ and $\geq
nR$ (_numerical restrictions_ , $\mathcal{N}$ , which enclose the functional
one), $\leq nR.C$ and $\geq nR.C$ (_qualified restrictions_ , $\mathcal{Q}$ ,
that include the numerical ones), $\left\\{a\right\\}$ and
$\left\\{a_{1},\ldots,a_{n}\right\\}$ (_nominals_ , $\mathcal{O}$ ), and
$\exists R.\mathit{Self}$ (_self-concept_). Contructs for roles are often
denoted by an operator symbol inside brackets after the name of the logic.
They are $R^{-}$ (inverse role, $\mathcal{I}$), $R\cup S,R\cap S$ and $\neg R$
(role union, intersection and complement, respectively), $R\circ S$ (role
composition, also used in chain), $R^{+}$ and $R^{*}$ (transitive and
reflexive-transitive closure of roles), $\mathit{id}\left(C\right)$(_concept
identity_), and $R_{C|},R_{|D}$ and $R_{C|D}$ (role restrictions). Sometimes,
the symbols $U$ (or _$\nabla$_ ,_universal role_ , defining the role which
encloses any other one) and _$N$ _(or __$\triangle$__ ,_empty role_ , defining
the role enclosed in any other one) are used. Other kinds of axioms which can
be introduced are $R\equiv S$ (equivalence between roles), $R\sqsubseteq S$
(hierarchy between roles, $\mathcal{H}$ , denoted also by $R\subseteq S$), and
the relative assertion $R\left(a,b\right)$ (role instance). The reflexive,
irreflexive, symmetric, antisymmetric, transitive, intransitive, disjunctive
(two roles having no pair of elements in common), functional and inverse
functional properties for roles are denoted by symbols that often differ in
literature, but are never ambiguous, e.g. respectively
$\mathit{Sym}\left(R\right),\mathit{Asym}\left(R\right),\mathit{Refl}\left(R\right),\mathit{Irrefl}\left(R\right),\mathit{Tr}\left(R\right),\mathit{Intr}\left(R\right),\mathit{Disj}\left(R\right),\mathit{Fn}\left(R\right),\mathit{InvFn}\left(R\right)$.
When transitive property is allowed, we use the symbol $\mathcal{S}$ , which
corresponds to $\mathcal{ALC}(^{+})$. Sometimes, even small differences among
logics (e.g., limitation on the use of atomic rather than complex roles on the
right or left part of an assertion) can make a big difference in
expressiveness and complexity. Thus, it is not always easy to concisely denote
DLs, that consequently constitute an ever-open research field.

One or more among the above descripted constructs, axioms and assertions are
present in the families of logics that are the base of languages used in
ontologies. Among these, an important example is the logic
$s\mathcal{ROIQ}_{(D)}$ (in literature always denoted by $\mathcal{SROIQ}(D)$
), at the bottom of the OWL 2 DL profile, which will be discussed in the
following (the letter in parenthesis indicates the use of _concrete domains_ ,
that will not be discussed here). Its syntax is easily inferred from the
symbols, while its complexity is N2ExpTime-hard.555By the symbol $\mathcal{R}$
, we mean that a DL allows complex inclusions of the kind $R\circ S\sqsubseteq
R$ and $R\circ S\sqsubseteq S$.

_Construct_ | _Syntax_ | _Semantics_
---|---|---
top concept | $\top$ | $\top^{\mathcal{I}}=\Delta^{\mathcal{I}}$
bottom concept | $\bot$ | $\bot^{\mathcal{I}}=\emptyset$
concept negation | $\neg C$ | $\left(\neg C\right)^{\mathcal{I}}=\Delta^{\mathcal{I}}\backslash C^{\mathcal{I}}$
concept intersection | $C\sqcap D$ | $\left(C\sqcap D\right)^{\mathcal{I}}=C^{\mathcal{I}}\cap D^{\mathcal{I}}$
concept union | $C\sqcup D$ | $\left(C\sqcup D\right)^{\mathcal{I}}=C^{\mathcal{I}}\cup D^{\mathcal{I}}$
universal restriction | $\forall R.C$ | $\left(\forall R.C\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\left(\forall\left(a,b\right)\in R^{\mathcal{I}}\right)\left(b\in C^{\mathcal{I}}\right)\right\\}$
existential restriction | $\exists R.C$ | $\left(\exists R.C\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\,\exists\left(a,b\right)\in R^{\mathcal{I}}\wedge b\in C^{\mathcal{I}}\right\\}$
numerical restriction |  | $\leq nR$
---
$\geq nR$
| $\left(\leq
nR\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\,\\#\left\\{b\in\Delta^{\mathcal{I}}|\left(a,b\right)\in
R^{\mathcal{I}}\right\\}\leq n\right\\}$
---
$\left(\geq
nR\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\,\\#\left\\{b\in\Delta^{\mathcal{I}}|\left(a,b\right)\in
R^{\mathcal{I}}\\}\right\\}\geq n\right\\}$
qualified restriction |  | $\leq nR.C$
---
$\geq nR$.C
| $\left(\leq
nR.C\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\,\\#\left\\{b\in
C^{\mathcal{I}}|\left(a,b\right)\in R^{\mathcal{I}}\right\\}\leq n\right\\}$
---
$\left(\geq
nR.C\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\,\\#\left\\{b\in
C^{\mathcal{I}}|\left(a,b\right)\in R^{\mathcal{I}}\right\\}\geq n\right\\}$
nominals |  | $\left\\{a\right\\}$
---
$\left\\{a_{1},\ldots,a_{n}\right\\}$
| $\left\\{a\right\\}^{\mathcal{I}}=\left\\{a^{\mathcal{I}}\right\\}$
---
$\left\\{a_{1},\ldots,a_{n}\right\\}^{\mathcal{I}}=\left\\{a_{1}^{\mathcal{I}},\ldots,a_{n}^{\mathcal{I}}\right\\}$
self concept | $\exists R.\mathit{Self}$ | $\left(\exists R.Self\right)^{\mathcal{I}}=\left\\{a\in\Delta^{\mathcal{I}}|\left(a,a\right)\in R^{\mathcal{I}}\right\\}$
universal role |  $U$, $\nabla$ | $U^{\mathcal{I}}=\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$
empty role |  $N$, $\triangle$ | $N^{\mathcal{I}}=\emptyset\times\emptyset$
role inverse | $R^{-}$ | $\left(R^{-}\right)^{\mathcal{I}}=\left\\{\left(a,b\right)|\left(b,a\right)\in R^{\mathcal{I}}\right\\}$
role negation | $\neg R$ | $\left(\neg R\right)^{\mathcal{I}}=\left(\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}\right)\backslash R^{\mathcal{I}}$
role intersection | $R\sqcap S$ | $\left(R\sqcap S\right)^{\mathcal{I}}=R^{\mathcal{I}}\cap S^{\mathcal{I}}$
role union | $R\sqcup S$ | $\left(R\sqcup S\right)^{\mathcal{I}}=R^{\mathcal{I}}\cup S^{\mathcal{I}}$
chaining | $R\circ S$ | $\left(R\circ S\right)^{\mathcal{I}}=R^{\mathcal{I}}\circ S^{\mathcal{I}}$
concept identity | $\mathit{id}\left(C\right)$ | $\left(id\left(C\right)\right)^{\mathcal{I}}=\left\\{\left(a,a\right)|\,a\in C^{\mathcal{I}}\right\\}$
transitive closure | $R^{+}$ | $\left(R^{+}\right)^{\mathcal{I}}=\left(R^{\mathcal{I}}\right)^{+}$
refl-trans closure | $R^{*}$ | $\left(R^{*}\right)^{\mathcal{I}}=\left(R^{+}\right)^{\mathcal{I}}\cup\left(id\left(\top\right)\right)^{\mathcal{I}}$
role restriction |  | $R_{C|}$
---
$R_{|D}$
$R_{C|D}$
| $(R_{C|})^{\mathcal{I}}=\left\\{\left(a,b\right)\in R^{\mathcal{I}}|\,a\in
C^{\mathcal{I}}\right\\}$
---
$(R_{|D})^{\mathcal{I}}=\left\\{\left(a,b\right)\in R^{\mathcal{I}}|\,b\in
D^{\mathcal{I}}\right\\}$
$(R_{C|D})^{\mathcal{I}}=\left\\{\left(a,b\right)\in R^{\mathcal{I}}|\,a\in
C^{\mathcal{I}}\wedge b\in D^{\mathcal{I}}\right\\}$

_Table 1.1._ Main constructs for concepts and roles

_Syntax_ | _Semantics_
---|---
$C\equiv D$ | $C^{\mathcal{I}}=D^{\mathcal{I}}$
$C\sqsubseteq D$ | $C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$
| $C\left(a\right)$
---
$\neg C\left(a\right)$
| $a^{\mathcal{I}}\in C^{\mathcal{I}}$
---
$a^{\mathcal{I}}\notin C^{\mathcal{I}}$
$R\equiv S$ | $R^{\mathcal{I}}=S^{\mathcal{I}}$
$R\sqsubseteq S$ | $R^{\mathcal{I}}\subseteq S^{\mathcal{I}}$
| $R\left(a,b\right)$
---
$\neg R\left(a,b\right)$
| $\left(a,b\right)^{\mathcal{I}}\in R^{\mathcal{I}}$
---
$\left(a,b\right)^{\mathcal{I}}\notin R^{\mathcal{I}}$
$R\sqcap S=N$, $\mathit{Disj}\left(R,S\right)$ | $R^{\mathcal{I}}\cap S^{\mathcal{I}}=\emptyset\times\emptyset$
| $\mathit{Refl}\left(R\right)$
---
$\neg\mathit{Refl}\left(R\right)$
| $\left(\forall a\in\Delta^{\mathcal{I}}\right)\left(\left(a,a\right)\in
R^{\mathcal{I}}\right)$
---
$\left(\forall a\in\Delta^{\mathcal{I}}\right)\left(\left(a,a\right)\notin
R^{\mathcal{I}}\right)$
| $\mathit{Sym}\left(R\right)$
---
$\neg\mathit{Sym}\left(R\right)$
| $\left(\forall\left(a,b\right)\in
R^{\mathcal{I}}\right)\left(\left(b,a\right)\in R^{\mathcal{I}}\right)$
---
$\left(\forall\left(a,b\right)\in
R^{\mathcal{I}}\right)\left(\left(b,a\right)\notin R^{\mathcal{I}}\right)$
| $\mathit{Trans}\left(R\right)$
---
$\neg\mathit{Trans}\left(R\right)$
| $\left(\forall\left(a,b\right)\in
R^{\mathcal{I}}\right)\left(\left(b,c\right)\in
R^{\mathcal{I}}\rightarrow\left(a,c\right)\in R^{\mathcal{I}}\right)$
---
$\left(\forall\left(a,b\right)\in
R^{\mathcal{I}}\right)\left(\left(b,c\right)\in
R^{\mathcal{I}}\rightarrow\left(a,c\right)\notin R^{\mathcal{I}}\right)$

_Table 1.2._ Main types of axioms and assertions on concepts and roles666The
use of $\mathit{Trans}\left(R\right)$, $\mathit{Refl}\left(R\right)$, and so
on, looks like adding a new type of axiom. Actually, they must be regarded as
abbreviations of more complex expressions involving equivalence, subsumption
and various constructs which we will not be treated here.

###  1.3 Semantic Web

The so-called Web 2.0 describes the current model of information search. The
difference with Web 1.0 is represented by the change in the origin of this
information (from below−users−rather than from above−webmasters). Yet, a
paradigm change in its fundamental structure has not occured, as the creator
of Web, Tim Berners-Lee, wished instead. Indeed, contents are still
exclusively made up of pages connected by links, whose nontrivial words,
together with metadata, are indexed by search engines, by means of which a
correspondence between those and the one inserted by users can be found. In
this way, notwithstanding the high efficiency and precision of the algorithms
involved, such engines constitute a “stupid” example of _information_
_retrieval_ , where the matching between terms, even if advanced, weighs more
than their meaning.

The change brought by the so-called Semantic Web (_SW_ or Web 3.0) addresses
the main issue that in the Web, as we know it, most of the contents are
structured in order to be read by humans, rather than investigated by programs
in an automatic way. A computer can jump from page to page by following links,
but it does not make any assumption on the semantics of their contents. SW is
an extension of “previous” Web that allows one to assign a meaning to
information and provides machines with the ability to elaborate and
“understand” what in the past they could only show. For all this to work,
computers should be able to access well-structured information schemas and
apply inference rules to permit automatic reasoning, in order to delocalize
knowledge representation and spread it over the Net. The languages these rules
apply should be expressive enough to make the Web capable of “reasoning” in a
versatile and widespread way. That is made possibile by tools such as
_eXstensible Markup Language_ (_XML_), _Resource Description Framework_
(_RDF_) and the ontologies described by the _Ontology Web Language_ (_OWL_).

###  1.4 RDF graphs

RDF is a model for representation of information on the Web. The basic idea is
that every resource (concept, class, property, object, value, etc.) can be
univocally described in terms of simple or identified-by-value properties. All
this permits to schematize an RDF model by means of an oriented graph, whose
nodes represent primitive objects and whose edges denote properties. The
limited vocabulary of RDF is extended by _RDFS_ (_RDF Schema_), which allows
one to define classes and properties in a more powerful way. E.g., it is
possibile to define a property as a relation by indicating its domain and/or
range, or say what class is a subclass of another.

From a data structure point of view, an RDF graph may be seen as a set of
triples of type (subject predicate object). For each triple, subject and
object are two nodes connected by an edge that represents a predicate; thus,
the subject of a triple may be the object of another and viceversa. Each of
these nodes may be identified by a URI/IRI, and so it can represent a
resource, or it may be simply a “connector” (in this case, it is called a
_blank node_ , _bnode_ , or _anonymous node_). If an object is not a subject
of another triple, it may also be a _literal_ , i.e., a datum representing a
value in a certain domain.

On the representation side, W3C suggests five types of _serialization_ s for
an RDF graph, the most used of which are RDF/XML (XML language is used) and
Turtle (descriptions through lists of triples).777The _serialization_ of an
object is the process which allows one to represent it in an accessible way,
in our case a text file. XML is used because of its precise representation of
data. Thus, they can be shared, by means of RDF, among various Web
applications while preserving their original meaning.

###  1.5 Ontologies

OWL ontologies extend RDFS vocabulary further.888Computer science ambitiously
draw on the philosophical term _ontology_ to show that the OWL language can
describe the world starting from its ultimate constituents and from relations
among them. If RDFS guarantees generality and precision in constructing
knowledge representation, with OWL we reach such an expressiveness that we can
“argue” about described information and “extract” more, through _reasoning_.
It provides powerful tools to define classes (that represent concepts),
properties (relations among classes) and individuals (their instances), and
gives the chance to combine them in logic constraints by means of which
necessity and/or sufficiency may be expressed.

Upon a W3C _recommendation_ , OWL is made up of three sublanguages with
increasing expressiveness: OWL Lite, OWL DL and OWL Full. The first two have
an almost total correspondence between two peculiar DLs (resp._
$\mathcal{SHIF}_{(D)}$_and _ $\mathcal{SHOIN}_{(D)}$_).999OWL-Lite and OWL-DL
provide the possibility of defining _annotation_ s, which correspondent DLs do
not do. In any case, annotations affect neither _reasoning_ , nor complexity,
nor decidability. For the sake of precision, OWL-Lite is considered a
“syntactic subset” of OWL-DL. The last one uses the same subset of OWL DL
constructs, but allows them to be unconstrained, according to RDF style. Due
to the lack of restrictions on transitive property and to the possibility of
handling concepts as individuals (_metamodeling_), OWL Full turns out to be
undecidable and thus, for the correspondence between that and any of the
aforesaid DLs, OWL DL is the most expressive decidable sublanguage of
OWL.101010Obviously, nothing excludes there is another decidable and more
expressive−but not studied yet−sublanguage.

OWL 2 extends OWL by enhancing its features and expressiveness. Apart from a
limited number of cases, OWL 2 is perfectly “backward compatible” with the old
OWL (which we call OWL 1 to differentiate it from the OWL 2), i.e., all the
ontologies of the latter keep the same semantics as that they had before, even
if “fed” to a _reasoner_ for OWL 2. Concisely, OWL 2 introduces a
simplification into the writing of the most common _statements_ , it permits
_metamodeling_ , together with some new constructs which increase its
expressiveness, and it extends support to data types.

As for sublanguages, in OWL 2 we can deal with OWL 2 Full and OWL 2 DL. As
mentioned before, the latter corresponds to the _$s\mathcal{ROIQ}_{(D)}$ _
logic. Though the former may be syntactically seen as the union of the latter
with RDFS, it is semantically compatible with OWL 2 DL (insofar as its
semantics allows one to draw all the inferences that can be drawn by using the
semantics of OWL 2 DL). Similarly to the analogue sublanguage OWL 1 Full, OWL
2 finds application in the modelling of concepts where _reasoning_ is not
required. A new feature of OWL 2 is the use of _profiles_ (i.e., fragments of
language) OWL 2 EL, OWL 2 QL and OWL 2 RL:111111In this way, OWL 1 Lite, OWL 1
DL and OWL 2 DL may be considered profiles of OWL 2. the first is useful for
applications involving ontologies that contain a great number of classes
and/or properties; the second aims at those applications with large volumes of
instances, where answering the queries is of primary importance (from which
the name QL, _Query Language_); the last profile is useful in applications not
requiring the sacrifice of too much expressiveness to efficiency. We will not
delve into the structural characteristics of these profiles. Here, we only say
that they are grounded on very different DLs, each of them fit for the
specific purpose they are designed for.

###  1.6 Syntactical correspondence of OWL(2) with DLs

As to its practical representation, an ontology is a RDF/XML-structured text
file, but, for our goals, it will be more useful to think to it in terms of an
RDF graph and, thus, of triples. Table 1.3 describes the correspondence
between the most common constructs of DLs and such triples (or a single
resource, where applicable), which use RDF(S) syntax together with that of
OWL(2). It also contains the names given by OWL to the fundamental concepts
and roles of DLs. It is interesting to notice how a DL construct often
corresponds to more triples, which sometimes makes interpretation quite hard.
The symbols _:x and _list in the Table 1.3 indicate respectively a _blank
node_ and a _list_ (a structure we will not deal with), whereas the prefixes
before the elements of triples represent standard W3C _namespaces_ , which
serve as abbreviations for the URIs they refer to.121212The correspondences
between namespaces and prefixes are:  rdf: http://www.w3.org/1999/02/22-rdf-
syntax-ns# rdfs: http://www.w3.org/2000/01/rdf-schema# owl:
http://www.w3.org/2002/07/owl# xsd: http://www.w3.org/2001/XMLSchema#

###  1.7 SPARQL

One of the most widespread languages for querying against ontologies is
_SPARQL_ _(_ recursive acronym for _SPARQL Protocol And RDF Query Language_).
Although it has lots of analogies with SQL, most of which syntactical, it is
equipped with a fundamentally different semantics. As query languages for
databases essentially work on tables and handle logic conditions to select the
rows of these tables that satisfy them, the WHERE clause in SPARQL finds
matches between the triples of the query and those of the ontology indicated
in the FROM clause. The logic assessments are relegated to the FILTER
operator, which possesses a big expressive power, thanks to its several
functions, but is rarely used due to the loss of efficiency that its presence
may cause.131313Depending on implementation, the FROM clause may be implied
because software loads in memory the ontology model separately. The SELECT
clause is very similar to that of SQL. It accepts  DISTINCT as a keyword and
the classical aggregation operators (COUNT, SUM, MIN, AVG  and MAX), while the
GROUP BY and HAVING clauses are often used (another similarity) to refine the
selection. The involved variables are preceded by the symbol ’?’, whereas
constants do not have a particular syntax, even if they generally coincide
with URI/IRIs of resources present in the ontology one is handling.

Analyzing in finer detail the WHERE clause, one can say that the triples to
match __ are enclosed in a block between braces and separated by a dot, which
implies their intersection. Inside these braces, more sub-blocks may be found,
which are useful in making the union (UNION operator) and the difference
(MINUS operator) between sets. The matching is valid if the variables having
the same names in the clause have the same values in the ontology. There exist
some useful shortenings, such as the use of semicolon or colon in place of
dot, which act respectively in the following way:

?s ?p1 ?o1 ; ?p2 ?o2 . shortens ?s ?p1 ?o1 . ?s ?p2 ?o2 .

?s ?p ?o1 , ?o2 . shortens ?s ?p ?o1 . ?s ?p ?o2 .

In addition to selection, one can also have the DESCRIBE, ASK  and CONSTRUCT
query types, which we will not review here. The employment of the PREFIX
clauses, that precede the real query and indicate the abbreviations for
namespaces used inside of it, is quite peculiar.

_DL construct_ | _RDF(S)/OWL(2) resource/triple(s)_
---|---
$\top$ | owl:Thing
$\bot$ | owl:Nothing
$C\sqsubseteq D$ | ($C$ rdfs:subClassOf $D$)
$C\equiv D$ | ($C$ owl:equivalentClass $D$)
$C\sqsubseteq\neg D$ opp. $C\sqcap D\sqsubseteq\bot$ | ($C$ owl:disjointWith $D$)
$C_{1}\sqcap C_{2}\sqcap\ldots\sqcap C_{n}$ | (_:x owl:intersectionOf _list$\left(C_{1},C_{2},\ldots,C_{n}\right)$)
$C_{1}\sqcup C_{2}\sqcup\ldots\sqcup C_{n}$ | (_:x owl:unionOf _list$\left(C_{1},C_{2},\ldots,C_{n}\right)$)
$\neg C$ | (_:x owl:complementOf $C$)
$\left\\{a_{1},a_{2},\ldots,a_{n}\right\\}$ | (_:x owl:oneOf _list$\left(a_{1},a_{2},\ldots,a_{n}\right)$)
$\exists R.C$ |  | (_:x owl:someValuesFrom $C$) (_:x owl:onProperty $R$)
---
$\forall R.C$ |  | (_:x owl:allValuesFrom $C$) (_:x owl:onProperty $R$)
---
$\exists R.\left\\{a\right\\}$ |  | (_:x owl:hasValue $a$) (_:x owl:onProperty $R$)
---
$\leq nR$ |  | (_:x owl:minCardinality $n$) (_:x owl:onProperty $R$)
---
$\geq nR$ |  | (_:x owl:maxCardinality $n$) (_:x owl:onProperty $R$)
---
$\leq nR\,\sqcap\geq nR$ |  | (_:x owl:cardinality $n$) (_:x owl:onProperty $R$)
---
$\leq nR.C$ |  | (_:x owl:minQualifiedCardinality $n$)
---
(_:x owl:onClass $C$) (_:x owl:onProperty $R$)
$\geq nR.C$ |  | (_:x owl:maxQualifiedCardinality $n$)
---
(_:x owl:onClass $C$) (_:x owl:onProperty $R$)
$\leq nR.C\,\sqcap\geq nR.C$ |  | (_:x owl:qualifiedCardinality $n$)
---
(_:x owl:onClass $C$) (_:x owl:onProperty $R$)
$\exists R.Self$ |  | (_:x owl:hasSelf _true_) (_:x owl:onProperty $R$)
---
$C\left(a\right)$ | ($a$ rdf:type $C$)
$\left\\{a_{i}\right\\}\equiv\left\\{a_{j}\right\\}$ | ($a_{i}$ owl:sameAs $a_{j}$)
$\left\\{a_{i}\right\\}\sqsubseteq\neg\left\\{a_{j}\right\\}$ | ($a_{i}$ owl:differentFrom $a_{j}$)
$U$ opp. ▽ | owl:topObjectProperty
$N$ opp. △ | owl:bottomObjectProperty
$R\sqsubseteq S$ | ($R$ owl:subPropertyOf $S$)
$R\equiv S$ | ($R$ owl:equivalentProperty $S$)
$R\sqcap S\sqsubseteq N$ | ($R$ owl:PropertyDisjointWith $S$)
$R^{-}$ | (_:x owl:inverseOf $R$)
$R_{1}\circ R_{2}\circ\ldots\circ R_{n}\sqsubseteq R$ | ($R$ owl:propertyChainAxiom _list$\left(R_{1},R_{2},\ldots,R_{n}\right)$)
$\mathit{Refl}\left(R\right)$ | ($R$ rdf:type owl:ReflexiveProperty)
$\mathit{Irrefl}\left(R\right)$ | ($R$ rdf:type owl:IrreflexiveProperty)
$\mathit{Sym}\left(R\right)$ | ($R$ rdf:type owl:SymmetricProperty)
$\mathit{Asym}\left(R\right)$ | ($R$ rdf:type owl:AsymmetricProperty)
$\mathit{Trans}\left(R\right)$ | ($R$ rdf:type owl:TransitiveProperty)
$\mathit{Fn}\left(R\right)$ | ($R$ rdf:type owl:FunctionalProperty)
$\mathit{InvFn}\left(R\right)$ | ($R$ rdf:type owl:InverseFunctionalProperty)
$R\left(a,b\right)$ | ($a$_property_name_ $b$)
$\neg R\left(a,b\right)$ |  | (_:x rdf:type owl:NegativePropertyAssertion)
---
(_:x owl:sourceIndividual $a$)
(_:x owl:assertionProperty $R$)
(_:x owl:targetIndividual $b$)

_Table 1.3._ Correspondences between DLs and SW

##  2 ANALYSIS AND RESULTS

###  2.1 The family $\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$>

Description Logics derived from decidable fragments of set theory, generally
denoted by the notation $\mathcal{DL}$ <language_name>, are having
considerable importance.

The family of logics underlying this class of ontologies, object of research
this project is based on, is focused on the fragment
$\mathcal{\forall}_{0}^{\pi}$ , which has a good expressiveness w.r.t.
knowledge representation in real-world applications. The interest aroused by
that is related to NP-completeness of its decision procedure in some cases of
practical relevance. $\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$>-concepts
and $\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$>-roles are formed according
to the syntax141414The symbol $\text{sym}\left(R\right)$ denotes symmetric
closure of $R$.

$\displaystyle C,D$ $\displaystyle\rightarrow$ $\displaystyle A\ |\ \top\ |\
\bot\ |\ \neg C\ |\ C\sqcap D\ |\ C\sqcup D\ |\ \left\\{a\right\\}\ |\ \exists
R.Self\ |\ \exists R.\left\\{a\right\\}$ $\displaystyle R,S$
$\displaystyle\rightarrow$ $\displaystyle P\ |\ U\ |\ R^{-}\ |\ \neg R\ |\
R\sqcap S\ |\ R\sqcup S\ |\ R_{C|}\ |\ R_{|D}\ |\ R_{C|D}\ |\
id\left(C\right)\ |\ \text{{\text{sym}}}\left(R\right)\,,$

while a $\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$>-KB is made of axioms
and assertions of the following kind:

$\begin{array}[]{c}C\equiv D\ \,\ \,\ C\sqsubseteq D\ \,\ \,\
C\sqsubseteq\forall R.D\ \,\ \,\ \exists R.C\sqsubseteq D\ \,\ \,\
C\left(a\right)\ \,\ \,\ R\left(a,b\right)\\\ R\equiv S\ \,\ \,\ R\sqsubseteq
S\ \,\ \,\ R\circ R^{\prime}\sqsubseteq S\ \,\ \,\ Trans\left(R\right)\ \,\
\,\ Refl\left(R\right)\ \,\ \,\ Asym\left(R\right)\ \,\ \,\ Fn\left(R\right)\
\,\ \,\ InvFn\left(R\right)\,.\end{array}$

We may notice that universal restriction is allowed only in the right part of
a subsumption, whereas existential restriction can appear only in the left
part. In addition, neither numerical, nor qualified restrictions are allowed.

###  2.2 Description of the experiment

Our analysis is aimed at selecting ontologies corresponding to the
$\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$> family, in order to use them as
a base of study for this family of logics in real-world applications. To do
that, it is necessary to query against as many as possible publicly available
ontologies in a quick and efficient way. The use of queries in SPARQL
conveniently lends itself to the purpose. The management is provided by
dOWLphin, a Java library specifically created in order to easily load the
ontologies and prepare the queries. The underlying library is Jena, one of the
most common collections of API for the Semantic Web, that is very handy
because it can directly deal with triples. As a _front-end_ GUI, the program
QuAny was used, which was born inside the experiment too and allows one to
query against local and remote ontologies, and save on disk the corresponding
results, for future verification.

###  2.3 Results and future objectives

The query was employed to test a significant number of ontologies of
BioPortal, the web portal of the National Center for Biomedical Ontology. This
choice was not random, but motivated mainly by two reasons: the first concerns
the large amount of ontologies present on the portal, coming from repositories
of biomedical resources spread all over the world; the second is relative to
the connection that these ontologies have with the real world in general, and
with human life and medicine in particular, which are fields offering several
matters for reflection on how widely knowledge of so important themes may be
schematized and represented, and, most of all, on the role _reasoning_ may
have in automatically inferring new information.

Around 30% of the ontologies resulted member of the language $\mathcal{DL}$
<$\mathcal{\forall}_{0}^{\pi}$>, which brings good hopes for reasoning on
them, given that−we remind−w.r.t. computational complexity we are in the NP-
completeness realm. Concerning the remaining 70%, efficient algorithms for
conversion will have to be considered and semantic tests will have to be done,
as previously happened for the $\mathcal{DL}$ <$\mathsf{MLSS}_{2,m}^{\times}$
> language (cfr. Cantone _et al._ , [3]).

In Appendix B, a table shows which ontologies were recognized as members of
the language $\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$>.

> ## References

  * Baader & Nutt, [2003] Franz Baader, Werner Nutt, _The Description Logic Handbook: Theory, Implementation, and Applications - 2: Basic Description Logics_ , Cambridge University Press, 2003

  * Berners-Lee _et al._ , [2001] Tim Berners-Lee, James Hendler, Ora Lassila, _Il Web Semantico_ in _Le Scienze \- 393_ (Italian translation of _The Semantic Web_ in _Scientific American_), 2001
  * Cantone _et al._ , [2010] Domenico Cantone, Cristiano Longo, Antonio Pisasale, _Comparing Description Logics with Multi-Level Syllogistics: the Description Logic $\mathcal{DL}$ <$\mathsf{MLSS}_{2,m}^{\times}$ >_ in _6th Workshop on Semantic Web Applications and Perspectives_ , University of Bozen/Bolzano, 2010
  * Cantone _et al._ , [2011] Domenico Cantone, Cristiano Longo, Marianna Nicolosi Asmundo, _A Decidable Quantified Fragment of Set Theory Involving Ordered Pairs with Applications to Description Logics_ in _Computer Science Logic (CSL’11) - 25th International Workshop/20th Annual Conference of the EACSL_ , 2011
  * DuCharme, [2011] Bob DuCharme, _Learning SPARQL_ , O’Reilly, 2011
  * Hitzler _et al._ , [2009] Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph, _Foundations of Semantic Web Technologies_ , Chapman & Hall, 2009
  * Horrocks & Patel-Schneider, [2004] Ian Horrocks, Peter F. Patel-Schneider, _Reducing OWL entailment to description logic satisfiability_ in _Journal of Web Semantics_ , Elsevier, 2004
  * Klyne & Carroll, [2004] Graham Klyne, Jeremy J. Carroll, _Resource Description Framework (RDF): Concepts and Abstract Syntax_ on _< http://www.w3.org/TR/rdf-concepts>_, W3C, 2004
  * Longo, [2012] Cristiano Longo, _Set Theory for Knowledge Representation_ , Ph.D. Thesis, University of Catania, 2012
  * Manola & Miller, [2004] Frank Manola, Eric Miller, _RDF Primer_ su _< http://www.w3.org/TR/2004/REC-rdf-primer-20040210_>, W3C, 2004
  * Motik _et al._ , [2009] Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, Zhe Wu, Achille Fokoue, Carsten Lutz, _OWL 2 Web Ontology Language Profiles_ on <_http://www.w3.org/TR/owl2-profiles_ >, W3C, 2009
  * Nardi & Brachman, [2003] Daniele Nardi, Ronald J. Brachman, _The Description Logic Handbook: Theory, Implementation, and Applications - 1: An Introduction to Description Logics_ , Cambridge University Press, 2003
  * Pan & Horrocks, [2007] Jeff Z. Pan, Ian Horrocks, _RDFS(FA): Connecting RDF(S) and OWL DL_ in _IEEE Transaction on Knowledge and Data Engineering - 19.2_ , 2007
  * Pisasale, [2012] Antonio Pisasale, _Web Semantico e Rappresentazione della Conoscenza_ , University of Catania, 2012
  * Zolin, [2010] Evgeny Zolin, _Complexity of reasoning in Description Logics_ on _< http://www.cs.man.ac.uk/~ezolin/dl/>_, 2010

##  Appendix A ANALYSIS OF THE SPARQL QUERY

> As we are going to see in the implementation, to write declaratively what an
> algorithm could do through a list of well-constructed statements is not an
> immediate operation to undertake. The final query is the result of various
> logical lines of argument concerning the conversion from $\mathcal{DL}$
> <$\mathcal{\forall}_{0}^{\pi}$>-constructs into those of RDF(S)/OWL(2),
> opportunely applied to some test ontologies.

From Table 1.3, one infers that, for the ontology under examination to be
considered part of the family of logics seen before, the allowed elements of
RDF(S)/OWL(2) are the following:

  * •

class or property definition (rdf:type)

  * •

top concept (owl:Thing)

  * •

bottom concept (owl:Nothing)

  * •

concept negation (owl:complementOf)

  * •

intersection and union of concepts (resp. owl:intersectionOf and owl:unionOf)

  * •

singleton (owl:oneOf)

  * •

self concept (owl:hasSelf)

  * •

value restriction (owl:hasValue)

  * •

universal role (owl:topObjectProperty)

  * •

role inverse (owl:inverseOf)

  * •

intersection and union of roles (not present in OWL 2)151515Obviously, we may
ignore the constructs not present in OWL 2, since they cannot be a cause of
rejection of the ontology.

  * •

role restrictions (not present in OWL 2)

  * •

identity concept (not present in OWL 2)

  * •

symmetric closure (it can be emulated by means of union and inverse of roles)

  * •

equivalence axiom between concepts (owl:equivalentClass)

  * •

subsumption axiom between concepts (rdfs:subClassOf)

  * •

exiistential restriction (owl:someValuesFrom) only in the left part of a
subsumption

  * •

universal restriction (owl:allValuesFrom) only in the right part of a
subsumption

  * •

minimal numerical restriction (owl:minCardinality) with cardinality not
greater than 1, only in the left part of a subsumption

  * •

declaration of concept membership (rdf:type)

  * •

declaration of role membership

  * •

equivalece between roles (owl:equivalentProperty)

  * •

inclusion between roles (owl:subPropertyOf)

  * •

role chaining (owl:PropertyChainAxiom)

  * •

transitive property (owl:TransitiveProperty)

  * •

reflexive property (owl:ReflexiveProperty)

  * •

asymmetric property (owl:AsymmetricProperty)

We have to add to these all the ones that can be deduced from a combination of
them, such as

  * •

disjunction between concepts (owl:disjointWith, owl:members)

  * •

union of disjoint concepts (owl:disjointUnionOf)

  * •

equivalence and non-equivalence between individuals (resp. owl:sameAs and
owl:differentFrom)

  * •

empty role (owl:bottomObjectProperty)

  * •

role domain (rdfs:domain, some cases excluded)161616Role domain corresponds to
the DLs’ axiom $\exists R.\top\sqsubseteq C$, so it is necessary to verify
that $C$ is satisfactorily expressed by the language.

  * •

role range (rdfs:range)

  * •

disjunction of properties (owl:propertyDisjointWith, owl:members)

  * •

irreflexive property (owl:IrreflexiveProperty)

  * •

symmetric property (owl:SymmetricProperty)

  * •

direct and inverse functional property (resp. owl:FunctionalProperty,
owl:InverseFunctionalProperty)

  * •

declaration of role non-membership (owl:NegativePropertyAssertion)

Consequently, the constructs which cause the rejection of an ontology are:

  * •

existential restriction not in the left part of a subsumption

  * •

universal restriction not in the right part of a subsumption

  * •

minimal numerical restriction with cardinality greater than 1 or not in the
left part of a subsumption

  * •

qualified numerical restrictions (owl:[max|min]QualifiedCardinality,
owl:qualifiedCardinality)

  * •

maximum and exact unqualified numerical restrictions (resp.
owl:maxCardinality, owl:cardinality)

  * •

some cases of domain declaration171717Cf. footnote 16.

  * •

datatype (rdfs:Datatype, owl:DatatypeProperty)

In order to create the query, we must consider that the language
$\mathcal{DL}$ <$\mathcal{\forall}_{0}^{\pi}$> is very expressive and provides
constructs and axioms which range over several elements of RDF(S)/OWL(2).
Thus, to abbreviate the task of enumerating them, the criterion of selecting
the triples not related to the language was adopted. Consequently, the result
of the query will contain at least a triple if the examined ontology is to be
rejected. There are as many clauses as the elements to consider, connected by
the UNION operator; thus, if at least a match is found, a non empty result
will be obtained, i.e., the analyzed ontology will not be a member of the
language.

Now, let us analyze the correctness of the query in detail (the relative row
number is indicated in brackets, when necessary).

  * •

The first clause (lines 7-19) includes the triples corresponding to
existential restrictions (line 8). Yet, not all of them contribute to the
rejection of the ontology, but only those which are not in the left part of a
subsumption. Thus, in line 10 we force their exclusion, provided that any is
found. If this is not the case, we find a match, according to line 8;
otherwise, we must control that neither of the following cases occurs (lines
11-17):181818The second-level MINUS operator could be optimized by including
the various triples contained in its clauses after line 8; nonetheless, we
must not forget that the _matching_ of triples is a notoriusly not very much
efficient operation: the choice of double-nesting concurs to avoid that SPARQL
engine performs useless searches when no subsumption in line 10 is found.

    * –

the anonymous node corresponding to a restriction is in the right part of any
triple (line 12): that allows one to include all the axioms with the
restriction and the various operators (e.g., union, intersection, complement,
etc.) which work on lists and single classes in the right part;

    * –

the above-mentioned node is in the left part of a triple corresponding to an
axiom (lines 13-16): that allows one to include single and multiple
equivalences and disjunctions.

  * •

The second clause (lines 19-33) includes the triples corresponding to
universal restrictions (line 20). When a triple of this kind is found, in
order for a _matching_ to be valid, it is also necessary to check that at
least either of the following cases occurs (lines 22-31):

    * –

the anonymous node corresponding to a restriction is in the right part of a
triple (line 23), but this triple is not a subsumption (line 24), nor that
node is the domain of a property (line 25);

    * –

the above-mentioned node is in the left part of a triple (line 27), but it is
not part of the definition of the restriction itself (lines 28-30) (otherwise,
an ever-false condition would be represented): that is to control that the
restriction is neither in the left part of an axiom, nor in the left part of
some class construct.

  * •

The third clause (lines 33-46) includes the triples corresponding to an
operator of minimal cardinality (line 34). Here we proceed (line 36 and lines
39-43) as in the first clause, with the difference (line 37) that the
cardinality value must be not greater than 1 too.191919Footnote 18 holds also
for the nested MINUSes.

  * •

The remaining clauses (lines 47-51) check for _datatype_ (lines 47 and 48),
qualified cardinality (line 49: the onClass property is peculiar to this kind
of restriction), exact and maximum cardinality (lines 50 and 51) triples.

  * •

For the purpose of accelerating the execution, the use of the LIMIT operator
(line 52) reduces the size of results to only one element, which is enough to
reject the ontology.

⬇

1PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>

2PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

3PREFIX owl: <http://www.w3.org/2002/07/owl#>

4

5SELECT *

6WHERE {

7 {

8 ?left owl:someValuesFrom ?class .

9 MINUS {

10 ?left rdfs:subClassOf ?right .

11 MINUS {

12 { ?s ?p ?left . } UNION

13 { ?left owl:equivalentClass ?right . } UNION

14 { ?left owl:disjointWith ?right . } UNION

15 { ?left owl:members ?right . } UNION

16 { ?left owl:disjointUnionOf ?right . }

17 }

18 }

19 } UNION {

20 ?restr owl:allValuesFrom ?class .

21 {

22 {

23 ?x ?prop ?restr .

24 MINUS { ?x rdfs:subClassOf ?restr . }

25 MINUS { ?x rdfs:domain ?restr . }

26 } UNION {

27 ?restr ?prop ?x .

28 MINUS { ?restr rdf:type ?x . }

29 MINUS { ?restr owl:onProperty ?x . }

30 MINUS { ?restr owl:allValuesFrom ?x . }

31 }

32 }

33 } UNION {

34 ?left owl:minCardinality ?num .

35 MINUS {

36 ?left rdfs:subClassOf ?right .

37 FILTER (?num<=1) .

38 MINUS {

39 { ?s ?p ?left . } UNION

40 { ?left owl:equivalentClass ?right . } UNION

41 { ?left owl:disjointWith ?right . } UNION

42 { ?left owl:members ?right . } UNION

43 { ?left owl:disjointUnionOf ?right . }

44 }

45 }

46 } UNION

47 { ?s ?p owl:DatatypeProperty . } UNION

48 { ?s ?p rdfs:Datatype . } UNION

49 { ?s owl:onClass ?o . } UNION

50 { ?s owl:cardinality ?o . } UNION

51 { ?s owl:maxCardinality ?o . }

52} LIMIT 1

> ##  Appendix B TEST AGAINST BIOPORTAL ONTOLOGIES

The SPARQL query was tested against the ontologies of BioPortal, available at
the link http://rest.bioontology.org/bioportal/virtual/download/ID?apikey=KEY.
The API KEY is an identifier for the registered users. The following table
associates the ID of the previous URL to the symbolic name of the
corrispondent ontology and highlights the ones which belong to the language.

_ID_ | _Name_ | _Res_ | _ID_ | _Name_ | _Res_ | _ID_ | _Name_ | _Res_
---|---|---|---|---|---|---|---|---
1033 | NMR Metabolomics Investig. | Y | 1362 | Hymenoptera Anatomy | N | 1552 | Reprod. Trait and Phenotype | Y

1039

& Proteomics Data N 1369 PhysicalFields Y 1560 Cognitive Paradigm N 1052
Proteins N 1381 NIF Dysfunction Y 1565 Medical Social Entities Y 1054 Amino-
acid N 1393 Information Artifacts N 1567 Pharmacovigilance Y 1056 Basic
Vertebrate Anatomy N 1394 Syndromic Surveillance N 1569 Host Pathogen
Interactions N 1058 SNP N 1398 Language Disorder in Autism Y 1570 Traditional
Med. Constitution Y 1059 Computer-based Patient Record N 1399 Pilot Ontology N
1571 Traditional Med. Other Factors Y 1060 Epoch Clinical Trial N 1401 Nursing
Practice N 1572 Trad. Med. Signs and Symptoms Y 1061 Pharmacogenomics N 1402
NIF Cell N 1573 Traditional Med. Meridian Y 1068 Subcellular Anatomy N 1406
LinkingKing2PEP N 1576 FDA Med. Devices N 1082 Gene Regulation (GRO) N 1407
Description of Dynamics N 1578 HOM-Helixhauser Scores N 1083 NanoParticles N
1409 PKO Re Y 1580 Adverse Event Reporting N 1084 NIFSTD Y 1410 Kinetic
Simulation Algorithm N 1581 Health Indicators N 1086 Disease Genetic
Investigation N 1411 Functioning, Disability and Health N 1582 CAO N 1087
Geographical Regions Y 1413 Software N 1588 General Purpose Datatypes N 1088
MaHCO N 1414 General Medical Science Y 1596 HOM_MDCs-DRGS N 1089 BIRNLex N
1415 CTCAE N 1613 Bone Dysplasia N 1092 Infectious Diseases N 1417 Influenza N
1615 Chemogenomics N 1100 Genetic Intervals N 1418 TOK N 1616 Phylogenetics Y
1104 Biomedical Resource N 1438 Breast tissue cell lines N 1625 HOM-ICD9PCS N
1106 Gene Regulation (BOOTStrep) N 1439 General Formal (GFO) N 1627 HOMERUN
Metadata N 1116 Bleeding History Phenotype N 1440 General Formal (GFO-Bio) N
1629 HOM-UCARE Demographics N 1122 Skin Physiology N 1444 Chemical Information
N 1631 HOM-Harvard N 1123 Biomedical Investigations N 1461 Translational
Medicine N 1633 Cognitive Alias N 1126 Family Health History N 1484 External
Causes of Injuries N 1638 Data Mining Y 1128 Comparative Data Analysis N 1487
Body System Y 1639 Epilepsy N 1130 Cancer Research and Mgmt N 1488 SysMO-JERM
N 1640 Pediatric Terminology N 1131 MGED N 1489 Adverse Events N 1641 HOM-
ICD9CM-ECODES N 1134 BioTop N 1494 Tissue Microarray N 1642 HOM-DXPROCS MDCDRG
N 1136 Experimental Factors Y 1497 PMA 2010 N 1643 HOM-ICD9_PROCS OSHPD N 1141
Physics for Biology N 1500 RNA N 1648 HOM-DATASOURCE OSHPD N 1142 Cardiac
Electrophysiology Y 1501 Neomark Oral Cancer-based N 1650 Units Y 1146
Electrocardiography N 1505 MicroRNA Target Prediction N 1652 HOM-OSHPD Use
cases N 1149 Dermatology Lexicon N 1515 Interaction Network Y 1653 HOM-PROCS2
OSHPD N 1172 Vaccines N 1521 Neural Motor Recovery Y 1658 Hewan Invertebrata N
1183 Lipids N 1522 BioPAX N 1665 Student Health Record N 1190 Parasite
LifeCycle N 1523 OBOE-SBC N 1666 Emotion N 1192 Proteomics Pipeline
Infrastructures N 1524 OBOE N 1667 HOM-DATASOURCE OSHPDSC N 1237 Situation-
based Access Control N 1530 Animal natural history N 1668 HOM-OSHPD-SC N 1247
GeoSpecies N 1532 SemanticScience Y 1671 Quantitative Imaging Biomarkers N
1249 Smoking Behavior Risk N 1533 BioAssay N 1672 DIKB-Evidence N 1290 ABA
Adult Mouse Brain Y 1534 Apollo-akesios Y 1676 Randomized Controlled Trials N
1304 Breast Cancer Grading N 1537 Brucellosis N 1686 Neomark Oral Cancer Y
1314 Cell Line (2) N 1538 Roles Y 1696 Synapses Y 1321 Neural ElectroMagnetic
Ontology N 1540 Drug Discovery Investigations N 3002 Mental Functioning Y 1332
Basic Formal Ontology Y 1541 Cell Line (MCCL 2) N 1335 Parasite Experiments N
1550 PHARE N