In recent years, there has been a growing interest in the problem of conjunctive query answering over description logic (DL) ontologies and large scale data sets. This problem is central to many applications, which often involve managing data sets consisting of hundreds of millions, or even billions of data assertions.
Meeting the scalability requirements of such applications is, however, a very
challenging problem. Answering conjunctive queries over ontologies in
expressive DLs is of high computational complexity; in fact, decidability is still an
open problem for SROIQ [
Scalability of query answering can be ensured by restricting the expressive
power of the ontology language to the level that makes reasoning tractable.
This has led to the development of three pro les of OWL 2, namely OWL 2
RL, OWL 2 EL, and OWL 2 QL [
Although allowing for e cient query answering, these lightweight DLs impose
severe restrictions on the expressive power of the ontology language. In order to
provide scalable query answering w.r.t. ontologies that cannot be captured by
such lightweight DLs, Semantic Web researchers have developed reasoners that
can process arbitrary OWL/SROIQ ontologies, but that guarantee
completeness only for ontologies that fall within the fragment de ned by the OWL 2
RL pro le. Given the close connection between OWL 2 RL and datalog, these
reasoners typically implement (deductive) database algorithms based on data
materialisation. Examples of such systems include Jena [
All such materialisation-based reasoners are sound ; that is, the answers they
compute can be seen as a lower bound on the complete set of query answers.
For ontologies outside the OWL 2 RL pro le, however, these reasoners are
incomplete, and hence they are not guaranteed to compute all query answers. A
possible approach to this problem is to investigate the behaviour of the reasoner
on a given query Q and ontology T in an e ort to show that it behaves as
a complete reasoner w.r.t. Q, T and an arbitrary data set [
An alternative approach, which we investigate in this paper, is to devise a scalable procedure for computing complete but possibly unsound query answers. Such answers provide an upper bound to the set of all answers, which can complement the lower bounds e ciently computed by incomplete reasoners. The combined use of such lower and upper bounds has many interesting implications. First, the di erence between the upper and lower bounds can be used as an optimisation for reducing the number of candidate answers; furthermore, it also provides a measure of the degree of incompleteness of a reasoner for a given input; nally, if both bounds match, we can e ciently compute all query answers without relying on potentially very expensive entailment tests.
In order to be useful, upper bounds should clearly be as tight as possible, and should also be e ciently computable. Obtaining such an upper bound is, however, not straightforward. The technique we use is to approximate T to give an ontology T 0 that is strictly \stronger" that T (i.e., T 0 j= T ), and that is within a fragment for which query answers can be e ciently computed.
Knowledge approximation has been extensively studied in the literature,
although mostly in the direction of weakening the ontology/theory [
Our technique exploits recent work on chase termination for existential rules,
which introduces a so called Models-Summarising Acyclicity (MSA) check [
We have implemented our approach, and conducted preliminary experiments
using LUBM [
We assume basic familiarity with the DLs underpinning the ontology language OWL 2 and its pro les. We next introduce datalog ;_ and datalog languages, and de ne the syntax and semantics of conjunctive queries. In our de nitions, we adopt standard rst-order logic notions of variable, constant, term, substitution, atom, formula, and sentence. We assume all formulas to be function-free. We denote with ? the special atom evaluated as false in all interpretations, and we use to denote the special equality predicate in rst-order logic. Finally, we also adopt the standard notions of satis ability, unsatis ability, and entailment. Datalog Languages. A datalog ;_ rule r is a formula of the form (1), where each Bj is an atom di erent from ? whose free variables are contained in x, and { m = 1 and '1(x; y1) = ?, or { m 1 and, for each 1 i m, formula 'i(x; yi) is a conjunction atoms di erent from ? whose free variables are contained in x [ yi.
m
8x:[B1 ^ ::: ^ Bn] ! _ 9yi:'i(x; yi)
i=1
(1)
A rule is safe if each variable in x also occurs in some Bj , and we consider
only safe rules. For brevity, the quanti er 8x is left implicit. The body of r is
the set body(r) = fB1; : : : ; Bng, and the head of r is the formula head(r) =
Wim=1 9yi:'(x; yi). A datalog ;_ rule r is datalog if m = 1 [
A fact is a ground atom, and an instance I is a nite set of facts. We denote with ind(I) the set of all individuals occurring in I.
For a set of datalog rules and I an instance, the saturation of w.r.t. I is the instance I0 consisting of all facts entailed by [ I.
Most DL ontologies can be transformed into a set of datalog ;_ rules and an instance by means of standard transformations. The rules and facts obtained via such transformations involve only unary and binary predicates; thus, we de ne an ABox A as an instance containing only unary and binary atoms. Queries. A conjunctive query (CQ), or simply a query, is a formula Q(x) of the form 9y:'(x; y), where '(x; y) is a conjunction of atoms. A tuple of individuals a is a certain answer to a query Q(x) w.r.t. a set of rst-order sentences F and an instance I if F [ I j= Q(a). The set of answers of Q(x) w.r.t. F and I is denoted as cert(Q; F ; I), where the free variables of Q(x) are omitted for brevity. 3 3.1
Given a TBox T , an ABox A and a query Q, our goal is to compute a (hopefully tight) upper bound to the set cert(Q; T ; A) of answers. We poceed as follows: 1. Transform T into a set T of datalog ;_ rules such that
extension of T . 2. Transform T into a set approx( T ) of datalog rules s.t. approx( T ) j=
3. Transform approx( T ) into an OWL 2 RL TBox T 0 for which we have cert(Q; approx( T ); A) = cert(Q; T 0; A) for every query Q and ABox A. Our transformation depends only on T , and satis es the following property: cert(Q; T ; A) cert(Q; T 0; A) for every query Q and ABox A Given the OWL 2 RL TBox T 0 we can then use T and T 0 with a materialisation based reasoner rl that is sound for OWL 2 and complete for OWL 2 RL (such as OWLim) to respectively compute a lower and an upper bound to query answers for the given Q and A. More precisely, we have: rl(Q; T ; A) cert(Q; T ; A) rl(Q; T 0; A) for every Q and A 3.2
We next describe in detail the transformations in Steps 1-3. As a running example, we use the TBox Tex in Figure 1.
From DL TBoxes to Datalog ;_ Rules. The rst step is to transform the DL TBox T into a set T of datalog ;_ rules such that T is a conservative extension of T . For a wide range of DLs, this can be achieved by rst using the well-known correspondence between DL axioms and rst-order logic formulas and then applying standard structural transformation rules, which may involve introducing new predicates. The transformation of our example Tex into datalog ;_ rules Tex is also shown in Figure 1; here, Tex and Tex are equivalent. From Datalog ;_ to Datalog. Next, we approximate the datalog ;_ rules
T by a datalog program approx( T ) that entails T . Intuitively, this
transformation can be described in two steps:
{ Rewrite each datalog ;_ rule r into a set of datalog rules by transforming
disjunctions in the head of r into conjunctions and splitting the conjunctions
into di erent datalog rules. Such a way to eliminate disjunction in the head
has been used in OWL reasoning with logic program [
RA(x) ! 9y:[works(x; y) ^ Group(y)]
Emp(x) ! 9y:[works(x; y) ^ Org(y)] Student(x) ! Grad(x) _ Undergrad(x)
RA(x) ! works(x; c1) ^ Group(c1) Emp(x) ! works(x; c2) ^ Org(c2)
Student(x) ! Grad(x) ^ Undergrad(x) De nition 1. For each datalog ;_ rule r of the form (1) and each variable yij 2 yi, let cirj be a fresh individual unique for r and yij . Then, approx(r) is the following set of rules, where for each 1 i m, ir is a substitution mapping each variable yij 2 yi to cirj : approx(r) = fB1 ^ ::: ^ Bn ! 'i(x; ir(yi)) j 1 i mg (2) For a set of datalog ;_ rules, approx( ) is the smallest set that contains approx(r) for each rule r 2 .
We next show that approx( T ) entails T . The following proposition
provides su cient and necessary conditions for a datalog ;_ rule to be entailed by
an arbitrary set of rst-order sentences (the proof is rather straightforward and
can be found in [
Proposition 1. Let F be a set of rst-order sentences and r be a datalog ;_ rule of the form (1). Then, for each substitution mapping the free variables of r to distinct individuals not occurring in F or r, we have F j= r if and only if m F [ f (B1); : : : ; (Bn)g j= _ 9yi:'i( (x); yi) i=1 Proposition 1 can be used to show that each datalog ;_ rule r in by approx(r), and hence approx( T ) strengthens T .
Proposition 2. For a set of datalog ;_ rules, we have approx( ) j= .
Proof. It su ces to show that, for each rule r 2 of the form (1) and each ri 2 approx(r), we have ri j= r. Let be a substitution mapping the free variables in r to fresh individuals; by Proposition 1, we have m ri j= r , ri [ f (B1); : : : ; (Bn)g j= _ 9yi:'i( (x); yi) (3) i=1 1 Note that, although approx( Tex ) is strictly speaking not datalog (we have conjunction of atoms in the head), it is trivially equivalent to a set of datalog rules. Since ri and r have the same body atoms, the de nition of ri in (2) implies ri [ f (B1); : : : ; (Bn)g j= 'i( (x); ir(yi)) Since substitution ir maps variables to constants, the following conditions clearly hold by the semantics of rst-order logic: m 'i( (x); ir(yi)) j= 9yi:'i( (x); yi) j= _ 9yi:'i( (x); yi) But then, conditions (3), (4) and (5) immediately imply ri j= r, as required. The fact that approx( ) entails implies that query answers w.r.t. approx( ) are an upper bound to those w.r.t. .
Proposition 3. For each set of datalog ;_ rules , each ABox A and each query Q, we have cert(Q; ; A) cert(Q; approx( ); A).
From Datalog to OWL 2 RL. The last step is to transform approx( T ) into an OWL 2 RL TBox T 0. Although arbitrary datalog rules cannot be transformed into OWL 2 RL, the rules in approx( T ) have been obtained from a DL TBox and are therefore tree-shaped, which makes this transformation possible.
There is, however, a technical consideration related to the fresh skolem constants in approx( T ). In particular, the following rule in our running example (see Figure 2) does not directly correspond to an OWL 2 RL axiom: i=1 (4) (5)
tu (6)
RA(x) ! works(x; c1) ^ Group(c1) This issue can be easily addressed by introducing fresh atomic roles. More precisely, rule (6) can be transformed into the following three OWL 2 RL axioms, where R0 is a fresh atomic role:
RA v 9R0:fc1g > v 8R0:Group
R0 v works 3.3
that we can easily weaken approx( T ) given in De nition 1 such that T is still entailed. In particular, when transforming a disjunctive rule in T into datalog by replacing disjunctions with conjunctions, it su ces to keep only one of the conjuncts. For example, given the transformation Student(x) ! Grad(x) _ Undergrad(x) Student(x) ! Grad(x) ^ Undergrad(x) we can replace in approx( T ) the rule Student(x) ! Grad(x) ^ Undergrad(x) with either Student(x) ! Grad(x), or Student(x) ! Undergrad(x). Any of these choices will lead to a (di erent) upper bound. In practice, one can choose to process any number of such di erent options, or simply devise suitable heuristics to choose the most promising one.
Unsatis ability Issues. For given TBox T and ABox A, it might be the case that approx( T ) [ A is unsatis able, whereas T [ A is satis able. Then, the upper bound we obtain is the trivial one for each query. For example, if we extend Tex in Figure 1 with the axiom Grad u Undergrad v ?, we obtain a rule with ? in the head in T , namely Grad(x) ^ Undergrad(x) ! ?. For Aex = fRA(a)g we then have that Tex [ Aex is satis able, but approx( Tex ) [ Aex is unsatis able; thus, for a given Q, any tuple of individuals of the appropriate arity must be included in the upper bound.
A way to address this issue is to remove from approx( T ) all rules with ? in the head. Although it is then no longer the case that approx( T ) j= T , we can still guarantee completeness provided that T [ A is satis able. Proposition 4. Let be a set of datalog ;_ rules and let 0 the result of removing from approx( ) all rules containing ? in the head. Then, the following condition holds for each ABox A and each query Q: if [ A is satis able, then cert(Q; ; A) cert(Q; 0; A).
In practice, checking the satis ability of T [A, which is equisatis able with T [ A, is easier than (and a prerrequisite for) query answering. Even if satis ability of T [ A cannot be checked in practice using a complete reasoner for a very large A, we can still compute an upper bound \modulo satis ability".
approx( T ) into OWL 2 RL TBox T 0. Note, however, that one could obtain the upper bound directly from approx( T ) by rst computing the saturation A0 of approx( T ) w.r.t. A and then computing cert(Q; ;; A0).
The saturation A0 can be computed in polynomial time [
Our current approach, however, does have some advantages. In particular, one can use the same o -the-shelf RL reasoner (such as OWLim) to compute both the lower and upper bound, which is convenient in practice. Furthermore, as suggested by our experiments, reasoners such as OWLim are quite e cient for large data sets. 4
We have implemented our approach in Java and used the latest version of OWLim-Lite as an OWL 2 RL reasoner. All experiments have been performed on a desktop computer with 4Gb of RAM, of which 3000Mb were assigned as maximum heap size in Java.
In our experiments, we have used LUBM extended with additional
synthetically generated queries. The LUBM ontology contains 93 TBox axioms, out of
which 8 contain existential quanti cation, and 39 are domain and range axioms.
The LUBM ontology, however, does not contain disjunction or negation; thus,
the corresponding issues discussed in Section 3.3 do not apply to our
experiments. To test how tight our upper bounds are for di erent queries, we have
used LUBM(1,0), the smallest data set in the benchmark, since the complete
DL reasoner HermiT can answer all test queries for this data set. LUBM(1,0)
contains data for one university and 14 departments, with a total of 100; 543
ABox assertions about 17; 174 di erent individuals.
Standard Queries. LUBM provides 14 queries. As shown in Table 1, the lower
and upper bounds computed using OWLim coincide, which allows us to conclude
that OWLim is complete for all these queries and the LUBM(1,0) data set.
Hence, in these cases, one wouldn't need to use a complete DL reasoner at all.
Additional Synthetic Queries. We have used a synthetic query generation
tool [
Observe, however, that the lower bound is missing those answers which require taking into account LUBM's axioms with existential quanti ers, for which OWLim is not complete. For example, consider the following query
Q51(x) = 9y:(memberOf(x; y) ^ Group(y)) LUBM's ontology contains all the axioms in Tex, except for the last two axioms in Figure 1; furthermore, LUBM(1,0) contains many instances of RA. Since LUBM's ontology implies that each RA works for (and hence is a member of) some group, all these instances are answers to Q51, which are not computed by OWLim. Additional Query. For all previous test queries, we have obtained a tight upper bound. To show that this is not always the case, we have manually created the additional query given next.
Q(x1; x2) = 9y:works(x1; y) ^ works(x2; y) ^ Group(y) Since this query is not tree-like, it cannot be answered using HermiT. To obtain the complete answers, we have used REQUIEM2 to compute a (complete) UCQ rewriting U of Q w.r.t. LUBM's ontology; then, we used OWLim to compute the answers to U w.r.t. the LUBM(1,0) data. For this query, the lower and upper bounds contained zero and 299; 209 answers, respectively; in contrast, we obtained 547 answers using REQUIEM and hence the upper bound is not tight.
As shown in Figure 2, our transformation implies that all RAs work for the same group (represented by the skolem constant c1); since there are many instances of RA in LUBM(1,0), all pairs of RA instances will be included in the upper bound. Clearly, however, many of these RAs work for di erent groups.
Note, however, that even for this query we managed to reduce the number of candidate answers from 17; 1742 3 108 to 299; 209. 4.2
To test scalability of upper bound computation, we have performed additional experiments using LUBM data sets of increasing size (from 1 to 10 universities). For each data set and each of the 78 synthetic queries, we have computed lower and upper bounds (using OWLim) and the complete answers (using HermiT). The results are summarised in Figure 4.2, where the time refers to the total query answering time for all test queries.
We can observe similar query answering times and scalability behaviour for lower and upper bound computation. Furthermore, we can observe that HermiT's performance is similar to OWLim's for relatively small data sets. HermiT, however, does not scale well for the largest LUBM data sets. In particular, it takes 178s to complete the tests for 9 universities and runs out of memory for 10 universities; in contrast, OWLim computation times increase more regularly. 5
In this paper, we have proposed a novel technique for e ciently computing an upper bound to CQ answers for ontologies given in a expressive DL. Our preliminary experiments on LUBM show that this upper bound might be tight in many cases. Furthermore, we identi ed cases were lower and upper bounds coincide and hence it is not necessary to use a fully- edged DL reasoner such as HermiT to compute query answers (HermiT is able to answer rollable queries).
Our work so far, however, is only very preliminary, and there are plenty of possibilities for future work. We are planning to perform experiments with ontologies involving disjunction and negation, and address the issues discussed in 2 http://www.cs.ox.ac.uk/isg/tools/Requiem/ 1400 1200 1000 800 600 400 200 0 3)0 1 (* s m o i x A f o r e b m u N e h T ) s ( e m i T
Answers by Hermit Lower Bound by OWLim Upper Bound by OWLim
The Size of ABox 0 0 2 4 6 The Number of Universities 8
10 Section 3.3. Furthermore, we will implement a dedicated datalog engine that can compute the saturation in polynomial time for tree-shaped datalog rules; this might allow us to improve performance as well as to simultaneously compute lower and upper bounds. We will also develop techniques for identifying during upper bound computation the fragments of the ABox and TBox that are su cient to determine, using a complete reasoner, which of the answers in the upper bound are actual answers; we expect that these techniques will provide additional room for optimisation. As a result, we can integrate all these techniques in HermiT to optimise query answering.
Acknowledgements. This work was supported by the Royal Society, the EU FP7 project SEALS and the EPSRC projects ConDOR, ExODA, and LogMap.