Query answering over ontologies is a crucial feature in contexts such as ontology-based data access and semantic information integration. There is considerable research interest in using query rewriting for e cient and scalable query answering: instead of evaluating a given query over the ontology with the (potentially very large) data directly, one rewrites the query with respect to the relevant knowledge in the ontology, and delegates the evaluation of the computed rewriting to a (possibly deductive) database system where the data resides. In this paper we examine the performance and scalability of producing unions of conjunctive queries versus datalog queries as rewritings. We present an empirical comparison between two representative approaches that consider very expressive ontology languages.
The use of ontologies for query answering allows for the extraction of both
explicit and implicit knowledge from the underlying data. Query answering over
ontologies is a crucial problem in contexts such as ontology-based data access
[
The main query language considered in the literature is that of conjunctive
queries (which captures the core of SPARQL queries). In contrast, several
ontology languages of various levels of expressivity have been considered. Query
answering for very expressive languages such as OWL 2 DL is known to be
intractable [
Query answering in QL can be performed via query rewriting in two steps: rst, the query and the terminological part of the ontology (i.e., the schema or TBox) are transformed into a so-called rewriting ; and then the rewriting is evaluated over the assertional part of the ontology (i.e., the data or ABox) only.
2 With respect to data complexity. In this case, the rewriting is an expanded version of the original query in the form of a union of conjunctive queries (UCQ). Therefore, reasoners implementing query rewriting not only avoid keeping potentially very large ABoxes in memory, but may delegate evaluation of the rewriting to o -the-shelf, highly optimized RDBMSs.
Various UCQ-producing rewriting algorithms have been devised for (variants
of) QL [
In this paper, we consider the advantages and disadvantages of producing
DQs over UCQs in terms of scalability of query answering. We begin by
presenting the query rewriting approach in more detail in Section 2. We then present
a general overview of existing approaches (of the two kinds) in Section 3. The
main contribution of the paper is an empirical evaluation in which we compare
the (DQ-producing) approach of Eiter et al. [
In this section, we introduce the notion of query rewriting informally by means of an example; we then discuss the advantages and disadvantages of the approach, and we nish with relevant formal de nitions.
Query rewriting is a technique that can be used to solve the problem of query answering over ontologies|that is, given a conjunctive query and an ontology, composed of a TBox and an ABox, compute the set of certain answers of the query with respect to the ontology. The main idea behind query rewriting is to transform the given query and TBox into an expanded query that can be later evaluated over the ABox only. Intuitively, the expanded query contains all the relevant information captured in the TBox, making the latter unnecessary for query evaluation.
Example 1. Suppose we have an ontology O = hT ; Ai that talks about universities, students, professors, and so on. The TBox T contains the following axioms (shown in Manchester syntax3):
where axiom (1) states that teachers teach at least someone, axiom (2) states that professors are teachers, and axiom (3) states that all tutors are professors.
Suppose that we want to retrieve the list of individuals who teach according
to O using the query Q (shown in datalog syntax [
Q(x)
teaches(x; y)
Before considering the data in A, we can rewrite the query with respect to the TBox|that is, expand Q with the relevant knowledge in T . According to the meaning of axioms (1){(3), we conclude that all teachers, professors, and tutors teach; therefore, we expand Q with:
Q(x) Q(x) Q(y)
Teacher(x) Professor(x) hasTutor(x; y)
We can now evaluate the resulting union of queries (4){(7) over A without further consideration of T .
The query rewriting approach has important advantages over the `direct' query answering approach implemented in reasoners like Pellet,4 HermiT,5 or FaCT++.6 Since the query and the TBox only are considered, reasoners implementing query rewriting need not maintain potentially large ABoxes in memory, a crucial feature for some applications in terms of scalability. Once the query has been rewritten, its evaluation can be delegated to existing highly optimized (deductive) database systems. Moreover, as the rewriting is independent from the ABox, one does not need to recompute it every time the data changes, but only when the TBox does. This is important in many application domains where data tends to change much more often than the schema.
The speci cation of OWL 2 includes the de nition of various fragments or
pro les that have been tailored with speci c use cases in mind. In particular, the
QL pro le was designed so as to bene t from the advantages of query rewriting,
both in terms of scalability and performance. It has been shown that queries
posed over OWL 2 QL TBoxes can be rewritten into unions of conjunctive queries
(UCQs) [
Query rewriting is, alas, not a silver bullet. Depending of the nature of the
expanded query, it might turn out to be too big and/or complex to evaluate e
ciently (or at all). In particular, for instance, the size of a UCQ computed from
a query and an OWL 2 QL TBox has been shown to be worst-case exponential
(with respect to the size of the inputs) [
An alternative approach to query rewriting is a technique based on forward
chaining [
Other alternatives include hybrid approaches where both the query and the ABox are expanded with respect to the TBox. The objective of these approaches is to avoid the potential exponential explosion in the size of the expanded query by using certain types of axiom to expand the ABox, while still retaining a manageable size. Unfortunately, similarly to materialization, these approaches might not be very e cient in scenarios where the data changes frequently.
We nish this section by giving a formal de nition of the various notions
described thus far. We use the well-known notions of constants, variables, function
symbols, terms, and atoms of rst-order logic [
De nition 1. A Horn clause is an expression of the form H B1 ^ ^ Bm, where H is a possibly empty atom and fBig is a set of atoms. The atom H is called the head and the set fBig is called the body. A Horn clause C is safe if all variables occurring in the head also occur in the body.
A datalog program P is a set of function-free, safe Horn clauses. The extensional database (EDB) predicates of P are those that do not occur in the head atom of any Horn clause in P ; all other predicates are called intensional database (IDB) predicates. A datalog query (DQ) Q is a tuple hQP ; P i, where QP is a query predicate and P is a datalog program. Q = hQP ; P i is a union of conjunctive queries (UCQ) if QP is the only IDB predicate in P and the body of each clause in P does not contain QP , and Q is a conjunctive query (CQ) if it is a union of conjunctive queries and P contains exactly one Horn clause.
An ontology O is a tuple hT ; Ai, where T is the terminological box or TBox,
and A is the assertional box or ABox [
Given a conjunctive query Q and a TBox T , a datalog query QT is said to be a rewriting of Q w.r.t. T if and only if ans(Q; T [ A) = ans(QT ; A) for every A. 3
The success of query rewriting depends on algorithms that produce manageable rewritings, both in terms of size and complexity. Since the seminal work of Calvanese et al. on DL-Lite|the Description Logic that provides the logical underpinning for OWL 2 QL|many rewriting algorithms aimed at e cient query answering via query rewriting have been proposed, most of which have been implemented in prototypes or commercial systems.
We limit ourselves to approaches implementing query rewriting as de ned
in De nition 1; that is, approaches where only the query gets expanded and
the ABox is considered to be independent. Materialization-based and hybrid
approaches|such as those by Kontchakov et al. [
Notable approaches include that of Calvanese et al. (PerfectRef) [
Most of the papers cited previously include an empirical evaluation of the approach with respect to others. We have summarized these results in Table 2, which shows the comparison of the approaches with respect to the rewritings size (number of clauses), their structural complexity, the time it takes to compute them, and the time it takes to evaluate them over some ABox. [Clipper Presto], Prexto < [PerfectRef = Requiem = Rapid = Nyaya] Complexity [PerfectRef [Clipper
Requiem Presto]
Prexto
Rapid
Nyaya] < Time
Rapid, Nyaya, [Clipper
Presto] < Requiem < PerfectRef Eval time [Requiem
Clipper
Presto] < PerfectRef Note 1. All these comparison were made over DL-Lite ontologies. The relationship between approaches separated with commas is not discussed in the literature.
The approaches that produce DQs (see Table 1) produce smaller rewritings than their UCQ-producing counterparts, with the exception of Prexto. This is due to the fact that UCQs are larger than semantically equivalent (non UCQ) DQs (conjunctive normal form versus disjunctive normal form). Prexto stands apart because, unlike other UCQ-producing approaches, it implements an optimization that considers the ABox to reduce the size of the rewritings. Regarding complexity, we see that UCQ-producing approaches do better than DQproducing ones. With respect to time, as it is related to size, it is not surprising that producing DQs is faster than producing UCQs; it is important to mention, however, that among those algorithms that produce UCQs, some approaches are much more e cient than others (hours versus seconds). Finally, with respect to evaluation time, we see that Presto outperforms PerfectRef, and, interestingly, that Requiem, Clipper, and Presto perform similarly, in spite of the fact that Requiem's rewritings are larger.
The comparison between Requiem, Clipper, and Presto regarding evaluation times was carried out by evaluating the computed rewritings of each system using DLV.7 Using such a system was necessary as both Presto and Clipper require a deductive database of this type for query evaluation even for DL-Lite ontologies; note, however, that Requiem produces UCQs in this scenario. Therefore, these results suggest that evaluating semantically equivalent UCQs and DQs in DLV takes approximately the same time, so there is no substantial gain in evaluation time by producing (smaller but more complex) DQs versus UCQs. It would be interesting to see, however, whether UCQs can be evaluated more e ciently in an RDBMS or an RDF database.
Another important aspect to consider is the time it takes to compute the rewritings. According to Table 2, both Clipper and Presto outperform Requiem with respect to this metric (in fact, Requiem is outperformed by every algorithm except PerfectRef). It would be interesting to see whether Requiem can be made faster by enhancing it with the various optimization techniques used in the other, more e cient approaches.
In order to address these two questions, we present an empirical evaluation of Clipper and Blackout|an optimized version of Requiem|in Section 5. We chose these two approaches as they are the ones that support the most expressive logic within their respective rewriting type (UCQ vs DQ) categories. The optimizations implemented in Blackout are described in Section 4. 4
In this section we describe Blackout, a highly optimized version of Requiem. Blackout is part of the state-of-the-art triplestore Stardog.8 Besides careful software engineering for e ciency, Blackout improves Requiem with two core optimizations.
First, Blackout implements an eager query containment optimization, as opposed to Requiem's lazy approach that computes query containment as the last step. As observed in most of the papers referenced in Section 3, this is one of Requiem's major drawbacks as the nal containment step could take a very long time. Eager containment prunes redundant queries earlier in the rewriting process; thus, it prevents additional rewritings from being generated from these redundant queries, which themselves would be redundant. Even though this does not ultimately change the number of rewritings, it does signi cantly minimize the time spent on query containment checks. Thus, Blackout does not waste time generating redundant queries that will eventually be pruned, and it reduces the total number of containment checks performed.
Second, Blackout implements an optimization technique known as data
oracle. This optimization is related to the so-called extensional constraints technique
presented in [
The e ectiveness of this optimization lies in the fact that even when a TBox might contain a large number of classes and properties, the assertions in the ABox typically use a much smaller number of classes and properties. This is frequently the case for deep class hierarchies where asserted types use leaf classes of the hierarchy, instead of more general classes higher in the hierarchy. For this reason, querying for a generic class might produce many rewritings because of the class hierarchy, but we might not need to execute all of those rewritings depending on the speci c ABox at hand.
In Section 2 we pointed out that one advantage of the query rewriting approach is that it is independent of the ABox, whereas clearly the data oracle optimization introduces a dependency. This dependency, however, is a very weak one and requires the data oracle to only check the existence of an atom, a class or a property, in the data. Stardog, like other RDF databases, maintains special index structures that make this very e cient. Therefore, the query rewriting component can still be loosely-coupled from the storage system and does not need to maintain special in-memory data structures for this optimization. Moreover, as will be discussed further, the data oracle implementation can be crucial to the success of query rewriting in practice. 5
In this section we present an empirical evaluation of Clipper and Blackout. Our evaluation is based on the LUBM benchmark|a well-known standard that provides customizable data generation capabilities.9 We rst examined the performance of the two approaches with respect to size/complexity of the rewritings, including the time it took to compute them; and then, we looked into how these rewritings perform when evaluated.
All experiments were performed on Ubuntu 3.0.0 with a 3.2Ghz AMD Phenom processor, 8GB of RAM running Java 1:6:033 with 8GB allocated to the JVM for each run. We recorded the average of 10 runs after 5 warmups for each experiment. 5.1
Computing Rewritings The rst part of the evaluation consisted of rewriting the 14 LUBM queries with respect to three TBoxes: TQL, TRL, and TEL, which correspond to QL, RL, and EL versions of the LUBM TBox, respectively. Table 3 summarizes our results. On the left-hand-side, we show the time in milliseconds that each system took to produce the rewritings for the 14 queries, whereas on the right-hand-side we show the number of clauses that each system produced overall.
As can be seen, Blackout is generally slower than Clipper, but it produces smaller rewritings. We believe the rewritings with few clauses produced by Blackout are the result of the data oracle optimization. In order to verify the bene ts of this optimization, we ran Blackout without it and obtained 66 clauses for TQL, 65 clauses for TRL, and 253 clauses for TEL. The most signi cant gain was in query 5 over TEL, in which Blackout produced a rewriting containing 51 clauses, whereas Blackout with no data oracle produced 117. These results suggest that the data oracle optimization, when applicable, may have a big impact.
As can be seen in Table 4, Clipper produced DQs exclusively for all the queries and pro les, whereas Blackout produced UCQs most of the time, even for RL and EL. These results suggest that it is not always necessary to produce DQs as rewritings even for RL or EL ontologies. The type of the rewriting impacts evaluation time as UCQs are structurally less complex than DQs, and might be easier to evaluate, depending on their size. The second part of our evaluation consisted of evaluating the rewritings produced by the two approaches. We used DLV|a state-of-the-art deductive database system (datalog engine) maintained by DLVSYSTEM s.r.l.|to evaluate Clipper and Blackout rewritings, and we used Stardog to evaluate Blackout rewritings only.10 We considered four ABoxes of increasing size: A1, A10, A100, and A1000, which contain approximately 138K, 1.38M, 13.8M, and 138M triples, respectively.11 10 Note that Stardog cannot presently evaluate DQs. 11 Since the current implementation of Clipper does not support data property assertions, we ignored this type of assertion in our tests.
As can be seen, DLV was able to execute Blackout rewritings faster than those of Clipper, which is not surprising as the former are smaller and less complex than the latter. Unfortunately, DLV was unable to execute the rewritings over A100 and A1000 due to lack of memory since it maintains all the clauses in memory. Clearly, in order to be able to evaluate rewritings and queries in general over large ABoxes, we would need a system that makes use of secondary storage. In this section we summarize the results from previous sections with respect to Blackout and Stardog. Table 7 shows the overall performance of Stardog in milliseconds counting the time it took Blackout to compute the rewritings and the time it took Stardog to evaluate them. It also shows the percentage of time that was spent on evaluating the produced rewritings.
Our results show that the larger the ABox, the longer time is spent on evaluating the rewritings. Therefore, we believe it is important to produce the simplest and smallest rewritings possible, even if this means spending a bit more time on the rewriting phase. 6
In this section we present a summary of our results.
DQ-producing approaches, such as Clipper, do not necessarily produce smaller rewritings than UCQ-producing approaches as formerly thought. Taking into consideration the underlying data might result in optimizations, such as the data oracle optimization, that can signi cantly reduce the size of the produced UCQs. This type of optimization should apply to DQs as well; it would be interesting to see to what extent it does and the impact it has.
It is not necessary to produce DQs for RL and EL in many cases. This is important as users can bene t from several of the languages features that are not included in QL without needing a datalog engine for query evaluation. As shown in this paper, the size of UCQs can be reduced and, importantly, UCQs are amenable to straightforward parallel evaluation. Therefore, we believe that one should only have to deal with DQs, and datalog engines, when necessary.
Evaluating the rewritings dominates the overall query answering time at large scales. Therefore, even though it may not be bene cial at small scales, it is worth investing time on optimizing the computation of rewritings in order to produce smaller and simpler rewritings that can be evaluated more e ciently. 7
We are currently working on adding datalog evaluation to Stardog so that it can
correctly evaluate Blackout rewritings even when they are DQs. Our ongoing
implementation is based on the well-known algorithm Query-SubQuery [
Additionally, we plan to work on the parallelization of UCQ evaluation within Stardog. Currently, Stardog executes the results of the query rewriting as a single query; it takes the UCQ produced by Blackout and creates a single query by unioning each of the queries. However, the queries composing the UCQ tend to be relatively small, simple, and easy to evaluate. Crucially, they are also independent: the results of one conjunct are not needed to produce the results of another. This lends itself very nicely to evaluation of each query in parallel, which can be done by taking advantage of existing architecture within Stardog.
We are also working on the implementation of SPARQL 1.1 with Stardog. There are new features in SPARQL 1.1 such as sub-queries and property paths that have an interesting overlap with features provided, or planned, within Stardog and Blackout. First, we will explore what the performance implications are for rewriting sub-queries in SPARQL 1.1, and if there are advantages the QSQ approach can provide during evaluation, or even if rewriting sub-queries is a feasible design. Additionally, with some OWL language features, such as transitivity, now available in SPARQL, we will determine whether Blackout can be used to handle queries utilizing these features. 12 http://www.iris-reasoner.org/