This paper introduces a description logic query language for retrieving A-box individuals that satisfy specific conditions. The language is substantially more expressive than traditional concept-based retrieval languages oeffred by previous description logic reasoning systems. The new language is implemented in the Racer system. We demonstrate the applicability of nRQL (new Racer Query Language) to OWL semantic web repositories and evaluate the performance of the current state of the art query answering engines for description logics using the Lehigh University Benchmark (LUBM).
The semantic web is aimed at providing machine “understandable” meta data
information for web resources. The most prominent semantic web meta data
markup language is OWL/RDF. Its design is heavily influenced by description
logics (DLs) [
In this paper we show how Racer’s new A-box query language nRQL(new Racer query language) can be used to provide access to extensionally speciefid information in A-boxes. We demonstrate the applicability of nRQL (pronounce: nercle) to OWL semantic web repositories and evaluate the performance of the current state of the art query answering engines for description logics using the Lehigh University Benchmark (LUBM).
The language nRQL augments and extends Racer’s functional API for querying a knowledge base (a knowledge base, KB for short, is simply a T-box/A-box tuple (T , A). For instance, Racer provides a query function for retrieving all individuals mentioned in an A-box that are instances of a given query concept. Let us consider the A-box {has child(alice, betty), has child(alice, charles)}. If we are interested in finding individuals for which it can be proven that a child exists, in the Racer system, the function concept instances can be used. However, if we would like to find all tuples of individuals x and y such that a common parent exists, currently, it is not possible to directly express this in sound and complete DL systems such as, for instance, Racer.
The paper is structured as follows: rfist we introduce the new Racer query
language. Basic knowledge in description logics is necessary to understand the
introduction to nRQL. We discuss and demonstrate the utility of nRQL with
examples. We then demonstrate the feasibility of the approach by benchmarking
the performance of Racer + nRQL using the so-called Lehigh University
Benchmark (LUBM) [
Racer supports the DL ALCQHIR+ (D− ) with, for instance, algebraic constraints (concrete domains) such as linear inequations for the reals and equations for strings. In the following we describe the syntax and semantics of nRQL. We start with some auxiliary denfiitions: Definition 1 (Individuals, Variables, Object Names). Let I and V be two disjoint sets of individuals and variables, respectively. The set O =def V ∪ I is the set of object names. We denote variables with letters x, y, . . .; individuals are named i, j, . . .; and object names with a, b, . . ..
Query atoms are the basic syntax expressions of nRQL: Definition 2 (Query Atoms). Let a, b ∈ O; C be an ALCQHIR+ (D− ) concept expression, R a nRQL role expression (a nRQL role expression is either a ALCQHIR+ (D− ) role expression, or a negated ALCQHIR+ (D− ) role expression); P one of the concrete domain expressions offered by Racer; and f, g be so-called attributes (whose range is defined to be one of the available concrete domains offered by Racer). Then, the set of nRQL atoms is given as follows: – Unary concept query atoms: C(a) – Binary role query atoms: R(a, b) – Binary constraint query atoms: P (f (a), g(b)) – Binary same-as atoms: same as(a, i) – Unary has-known-successor atoms: has known successor(a, R) – Negated atoms: If A is a nRQL atom, then so is \(A), a so-called negation as failure atom or simply negated atom. nRQL also offers various syntactic abbreviations (“macros”) to facilitate query formulation. For example, it is possible to use role chains followed by an attribute within binary constraint query atoms: the atom ((λ (age1, age2).(age1 + 70) < age2)(age(has child(x)), age(has f ather(has f ather(x))))) retrieves all individuals x having a child being at least 70 years younger than its grand grandfather. This given atom is just an abbreviation for the complex conjunction has child(x, y)∧ has f ather(x, z)∧ has f ather(z, u)∧ ((λ (age1, age2).(age1 + 70) < age2)(age(y), age(u))).
Definition 3 (nRQL Queries). A nRQL Query has a head and a body. Query bodies are defined inductively as follows: – Each nRQL atom A is a body; and – If b1 . . . bn are bodies, then the following are also bodies: • b1 ∧ · · · ∧ bn, b1 ∨ · · · ∨
bn, \(bi) We use the syntax body(a1, . . . , an) to indicate that a1, . . . , an are all the object names (ai ∈ O) mentioned in body. A nRQL Query is then an expression of the form ans(ai1 , . . . , aim ) ← body(a1, . . . , an), The expression ans(ai1 , . . . , aim ) is also called the head, and (i1, . . . , im) is an index vector with ij ∈ 1 . . . n. A conjunctive nRQL query is a query which does not contain any ∨ and \ operators.
The predicate ans should be understood as a keyword. Note that, similar to other logical languages, it is also possible to use individuals as “constants” in the head of queries.
Before we consider atoms with variables, we denfie truth of ground query atoms.
Definition 4 (Ground Query Atoms). A ground query atom is a query atom that does not contain any variables. A positive ground query atom is a ground query atom that is not negated.
To define truth of ground query atoms, we will need the standard notion of logical implication or logical entailment. Assuming that inds(A) returns the set of all individuals mentioned in A-box A we first start with positive atoms. Definition 5 (Entailment of Positive Ground Query Atoms). Let K = (T , A) be an ALCQHIR+ (D− ) knowledge base.
A positive ground query atom A is logically entailed (or implied) by K iff every model I of K is also a model of A. In this case we write K |= A. Moreover, if I is a model of K (A) we write I |= K (I |= A). We therefore have to specify when I |= A holds. In the following, if the atom A contains individuals i, j, it will always be the case that i, j ∈ inds(A). From this it follows that iI ∈ Δ I and jI ∈ Δ I , for any I = (Δ I , · I ) with I |= K: – If A = C(i), then I |= A iff iI ∈ CI . – If A = R(i, j), then I |= A iff (iI , jI ) ∈ RI . – If A = P (f (i), g(j)), then I |= A iff (f I (iI ), gI (jI )) ∈ P I . – If A = same as(i, i), then I |= A. – If A = same as(i, j), then I 6|= A. – If A = has known successor(i, R), then I |= A iff for some j ∈ inds(A):
I |= R(i, j).
It is important to note that the properties of roles and concepts referred to in the query atoms are denfied in the knowledge base K. For example, if the role has descendant has been declared as transitive in K, then has descendant is transitive in the queries as well, since in models of K has descendantI = (has descendantI )+ must hold. If has f ather is declared as a feature (a functional role), then it is treated as a feature in queries as well.
Also note that same as(i, j) is basically a syntactical notion. Suppose that in some models (Δ I , · I ), iI = jI holds. Thus, i and j are basically different names for the same domain individual in these models. Even if iI = jI in all models, still A 6|= same as(i, j) holds. Also note that the unique name assumption for A-box individuals is no longer enforced in Racer 1.8. A corresponding atom same domain individual(i, j) will be added to a future nRQL version.
Now that we have denfied truth of of positive ground query atoms, we can denfie truth of arbitrary ground query atoms: Definition 6 (Truth of Ground Query Atoms). Let A be a ground query atom. Let K = (T , A) be a knowledge base (T-box/A-box tuple). A ground atom A is either TRUE in K (we write K |=NF A) or FALSE in K (we write K 6|=NF A). The relationship |=NF resp. trueness of ground query atoms is inductively defined as follows: – If A is positive (does not contain “\”): K |=NF A iff K |= A – Otherwise: K |=NF \(A) iff K 6|=NF A It is important to note that for each query body or atom q, q is TRUE iff \(q) is FALSE, and vice versa. Note that this does not hold for the usual entailment relationship. For example, consider the A-box {woman(betty)}. Given K =def (∅, A), woman(betty) is TRUE, and mother(betty) is FALSE, since we cannot prove that betty is a mother. Thus, \(mother(betty)) is TRUE. In contrast, ¬mother(betty) is obviously FALSE. Moreover, (mother t ¬mother)(betty) = >(betty) is not the same as (mother(betty)) ∨ (¬mother(betty)).
In order to check whether K |=NF A, we can use the basic consistency checking and A-box retrieval methods offered by Racer. The symbol “ |=NF ” shall remind the reader of the employed “Negation as Failure” semantics (i.e., suppose A is positive, then K |=NF \(A) iff K 6|= A, which means \(A) is TRUE in K, see below for examples).
The truth definition of ground atoms can be extended to complex ground query bodies in the obvious way (i.e., K |=NF b1 ∧ · · · ∧ bn iff ∀bi : K |=NF bi, and analogously for ∨ and \).
Having defined truth of ground query atoms and bodies, we can specify the semantics of queries which are not ground, but rfist we need one more piece of notation. The rationale behind the next denfiition is best understood with an example: consider the query ans(betty) ← woman(betty). The answer to this query should either be ∅ (in case K 6|= woman(betty)), or {(betty)} (in case K |= woman(betty)). A reasonable statement is that ans(betty) ← \ (woman(betty)) should be the complement query of ans(betty) ← woman(betty). Thus, ans(betty) ← \ (woman(betty)) should therefore return the set { (i) | i ∈ inds(A) } if K 6|= woman(betty)) and { (i) | i ∈ inds(A) } \ {betty} if K |= woman(betty). Thus, within \(woman(betty)), betty behaves in fact like a variable. To capture this behavior, we replace the individuals in the atoms with representative variables and use same as statements as follows: Definition 7 ( α -Substitution). Let A be an atom that contains at most one “\” (note that A = \(\(A))). Denote the set of mentioned individuals in A as inds(A). Then, α (A) is defined as follows:
\(A[0i← xi,j← xj]) ∨ \(same as(xi, i)) ∨ \(same as(xj , j)). – If inds(A) = ∅, then α (A) =def A. – If A is positive and inds(A) = {i, j} (possibly i = j), then α (A) =def
A[i← xi,j← xj] ∧ same as(xi, i) ∧ same as(xj , j).
– If A = \(A0) is negative and inds(A) = {i, j} (possibly i = j), then α (A) =def Note that A[i← xi,j← xj] means “substitute i with xi, and j with xj ”. For example, α (R(i, j)) = R(xi, xj ) ∧ same as(xi, i) ∧ same as(xj , j), but α (\(R(i, j))) = \(R(xi, xj )) ∨ \(same as(xi, i)) ∨ \(same as(xj , j)). We extend the definition of α to query bodies in the obvious way. However, we need to bring the bodies into negation normal form (NNF) first, such that “ \” appears only in front of atoms. This is simply done by applying DeMorgan’s Law to the query body (from the given semantics it follows that \(A ∧ B) ≡ \ (A) ∨ \(B), \(A ∨ B) ≡ \ (A) ∧ \(B), \(\(A)) ≡ A). The semantics of a nRQL query can now be paraphrased as follows: Definition 8 (Semantics of a Query). Let ans(ai1 , . . . , aim ) ← body(a1, . . . , an) be a nRQL query q such that body is in NNF. Let β (ai) =def xai if ai ∈ I, and ai otherwise; i.e., if ai is an individual we replace it with its representative unique variable which we denote by xai . Let K be the knowledge base to be queried, and A be its A-box. The answer set of the query q is then the following set of tuples: { (ji1 , . . . , jim ) | ∃j1, . . . , jn ∈ inds(A), ∀m, n, m 6= n : jm 6= jn,
K |=NF α (body)[β (a1)← j1,...,β (an)← jn] }
Finally, we state that {()} =def TRUE and {} =def FALSE.
Note that we assume the unique name assumption (UNA) for the variables here.
However, the implemented query processing engine also offers non-UNA variables
(prefixed with $). For reasons of brevity we decided not to include them in the
formal definitions in this paper. There are various other features in nRQL (which
is still under development) which have been left out here. Please refer to [
Example Session In the following we discuss standard query patterns and discuss the expressivity of nRQL. As a running example we use the following simple knowledge base.
T-box: has child v has descendant
. inv has child = inv(has child) has f ather v inv has child has mother v inv has child
man v person woman v person brother v man
. parent = person u (∃has child.person) mother =. woman u parent
. grandmother = motheru ∃has child.∃has child.person
Role Declarations: transitive(has descendant) attribute(age, integer) f eature(has f ather) f eature(has mother) A-box: woman(alice), woman(betty), brother(charles), (≤ 1has sibling)(charles), has sister(eve, doris), has child(alice, betty), has child(alice, charles), has child(betty, doris), has child(betty, eve), has sibling(charles, betty), has sister(doris, eve) For example, ans(x) ← grandmother(x) asks for all instances of type grandmother from the current A-box to be bound to the variable x. The answer is {(alice)}. If we query with ans(x) ← (¬grandmother)(x) we get {(charles)}, since Charles is known to be a man. Due to the open world semantics, the other women in the A-box (Eve, Doris, Betty) might be grandmothers as well, and we just don’t know. Consequently, ans(x) ← \ (grandmother(x)) yields {(doris)(eve)(charles)(betty)}, due to the negation as failure semantics. This is the complement of the first query.
If we just want to know if there are any known grandmothers at all in the current A-box, we can simply query with ans() ← grandmother(x), and Racer replies TRUE.
As specified, it is possible to use A-box individuals within queries: ans() ← woman(betty) yields TRUE. Consequently, for ans() ← man(betty) the answer is FALSE. If A-box individuals (here betty) are used within a query head, they are listed in the bindings as well: ans(betty) ← woman(betty) yields {(betty)}. However, for ans(betty) ← man(betty) the answer is again FALSE.
To give an example of a binary role query atom, consider ans(mother, child) ← has child(mother, child) which yields the answer set {(betty, doris)(betty, eve) (alice, betty)(alice, charles)}. If we want to know who is not a child of whom, we use ans(x, y) ← \ (has child(x, y)) and get the complement of the previous query (minus tuples excluded due to the UNA for variables). If we are just interested in the children of Betty, we ask Racer with ans(child of betty) ← has child(betty, child of betty) and get {(doris), (eve)}.
To give an example of a binary constraint query atom, consider ans(x) ← > (has f ather ◦ has mother ◦ age(x), has mother ◦ has f ather ◦ age(x)), which asks for persons whose father’s mother is older than their mother’s father.
Suppose we want to know for which individuals we have explicitly modeled children in the A-box. For this purpose, the query ans(x) ← has know successor(has child, x) can be used. Note that the main reason for having atoms of this type is related to negation: suppose we want to retrieve the A-box individuals which do not have a child. The query ans(x) ← \ (has child(x, y)) cannot be used, since first the complement of has child(x, y) is computed, and then the projection to x is carried out. Thus, ans(x) ← \ (has known successor(x, has child)) must be used. We already noted that this query is not equivalent to ans(x) ← \(∃has child.>(x)).
To illustrate the problem, suppose we want to query for mothers not having any explicitly modeled children in the A-box. Obviously, these mothers cannot be retrieved with ans(x) ← \ (∃has child.>(x)), since motherhood implies having a child. But this child need not be explicitly modeled in the A-box. Therefore, the query ans(x) ← mother(x) ∧ \(has known successor(x, has child)) must be used. The syntax ans(x) ← mother(x) ∧ has child(x, NIL) is also understood by Racer.
To give an example of a more complex conjunctive query, suppose we are interested in all mothers of male persons: ans(x, y) ← mother(x) ∧ man(y) ∧ has child(x, y). Racer replies: {(alice, charles)}. Due to the UNA for variables, the query ans(x, y) ← man(x) ∧ man(y) returns ∅, since Charles is the only man. The same applies to ans(x) ← man(x) ∧ man(charles), since x has to be bound to a man different from Charles.
We ask the reader to refer to the Racer manual [
The so-called Lehigh University Benchmark (LUBM, [
In [
For our benchmark, we used a LUBM repository comprising 1 university with 14 departments. We then ran the 13 queries on repositories of increasing size (on a P4 2.8 GHz 1 GB RAM machine running Linux) starting from a university with 1 department, and adding departments one by one to the repository. The answer time of each query is measured 10 times on repositories of increasing size, and the average answer time is recorded.
We ran the benchmark with three different settings: in setting 1, the A-box is not realized before queries are answered which means that the set of concept names an individual is an instance of is not computed before querying starts. In setting 2, the A-box is first realized. Setting 3 refers to a new incremental two-phase tuple-at-a-time query processing mode in Racer 1.8 (see below for an explanation). The A-box sizes, loading and realization time are also given in Figure 2.
With the current Racer version (1.8) it is not yet possible to load a whole university from the LUBM due to the initial A-box consistency test which has to be performed before query answering starts; we therefore had to stop at 5 departments.
From Figure 2 (note the logarithmic scale), we can observe the following: in setting 1, queries 1, 3, 7, 10 and 13 can be answered within fractions of a second, even if 5 departments are loaded. These queries as well as queries 4 and 5 show constant runtime behavior. This is not surprising, since they refer to individuals from the A-box, and are therefore very specicfi. For the queries 2, 8, 9, 11 and 12 an exponential increase in answering time is suggested. However, only queries 8, 9 and 12 need more than 55 seconds when 5 departments are loaded. These are the hard ones in setting 1. Query 12 needs even 2912 seconds.
In setting 2, with a realized A-box, the situation changes: query 12 can now be answered in 12 seconds! Queries 1, 3, 4, 5, 7, 10 and 13 still show constant behavior and run only slightly faster. It is also suggested that the exponential increase for queries 2, 8 and 9 is somehow slightly alleviated (more sampling points are needed in order to be more concise about this). However, only query 12 really benetfis from setting 2. The overall execution times for the other queries are only slightly faster.
The analysis suggests that using a realized A-box can alleviate an exponential increase in query answering time. However, prior realization only pays off when queries are posed that need deep reasoning capabilities for being answered 0.1 0.5 3 2 1 0
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12
Q13 Runtime Performance of LUBM Queries 1-13 (Set ing 1, Logarithmic Scale, Unrealized ABox)
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 10 s conde 1 S 0.1
Runtime Performance of LUBM Queries 1-13 (Set ing 2, Logarithmic Scale, Realized ABox)
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Q11
Q12
Q13
completely. Note that DLDB could not answer query 12. A-box realization times
increase quite drastically, as Figure 2 shows. Queries 8 and 9 are hard in both
settings. Query 12 becomes much easier in setting 2. Query 8 and 9 are also
among the hardest queries for DLDB [
Let us now discuss setting 3. Since version 1.8, Racer supports incremental query answering. Thus, rather than retrieving the whole solution set in a single step (set-at-a-time approach), client applications can load elements from the solution set in a way that proceeds tuple by tuple (tuple-at-a-time iterator approach). Additionally, Racer 1.8 can be congfiured in such a way that nRQL queries are answered with optimized algorithms known from relational databases. Thus, similar to DLDB, Racer treats an A-box as a database and rewrites queries in order to support T-box information for information retrieval. In addition to DLDB, Racer also supports inverse roles in this process. In Figure 2 setting 3 the times for retrieving all tuples that are also found by DLDB (plus some more due to inverse roles) are indicated. Racer 1.8 supports a query function that indicates when the last of these “cheap” answers is returned. After this point, Racer switches to full A-box mode and retrieves the remaining tuples. However, much more computational resources are required (see the discussion above). It is up to the application to decide if it is worth the effort. Figure 2 setting 3 indicates that Racer 1.8 provides comparable performance for similar services as offered by hybrid systems such as DLDB, but offers complete reasoning if required.
For querying OWL semantic web repositories, the query language OWL-QL has
been proposed [
In this paper we have presented the Racer + nRQL semantic web repository, as well as some preliminary benchmarking results.