W3C currently extends the SPARQL query language with so-called entailment regimes, which define how queries are evaluated using logical entailment relations. We describe a sound and complete algorithm for the OWL Direct Semantics entailment regime. Since OWL's Direct Semantics is based on Description Logics (DLs), this results in an expressive query language for DL knowledge bases. The query language di ers from the commonly studied conjunctive queries in that it only has distinguished variables. Furthermore, variables can occur within complex concepts and can also bind to concept or role names. We provide a prototypical implementation and propose several novel optimization strategies. We evaluate the e ciency of the proposed optimizations and find that for ABox queries our system performs comparably to already deployed systems. For complex queries an improvement of up to three orders of magnitude can be observed.
The SPARQL W3C working group is currently devising version 1.1 of SPARQL, which also includes several entailment regimes. These entailment regimes redefine the semantics of SPARQL queries based on standard semantic web entailment relations such as RDFS or OWL Direct Semantics entailment. This allows for using SPARQL also as a query language over OWL ontologies with query answers also including solutions that are implicit consequences of the queried ontology or knowledge base.
In this paper, we present an implementation and optimization techniques for the SPARQL OWL 2 Direct Semantics entailment regime, which we call SPARQL-OWL for brevity. SPARQL-OWL only allows for distinguished variables (for compatibility with SPARQL 1.0), but it poses significant challenges for implementations, e.g., by allowing variables that bind to concepts or roles and which can even occur within complex concepts. Our implementation supports ontologies (knowledge bases) in OWL 2 DL and is based on the HermiT reasoner.5 Most of the devised optimization techniques are also applicable when using another OWL reasoner. In our algorithm, we extend the techniques used for conjunctive query answering to deal with arbitrary SPARQL-OWL queries and propose a range of novel optimizations in particular for SPARQL-OWL queries that go beyond SPARQL-DL.
Our prototypical system is the first to fully support SPARQL-OWL, and we have performed a preliminary evaluation in order to investigate the feasibility of our algorithm and the e ectiveness of the proposed optimizations. This evaluation suggests that, in the case of standard conjunctive queries, our system performs comparably to existing ones. It also shows that a naive implementation of our algorithm behaves badly for some non-standard queries, but that the proposed optimizations can dramatically improve performance, in some cases by as much as three orders of magnitude.
An extended version of this paper is accepted at ESWC’11 [
In this section we give a brief introduction to the SPARQL-OWL entailment regime and in the next section we describe an algorithm that finds answers to queries under this regime. 2.1
SPARQL is originally an RDF query language and the WHERE clause of a SPARQL
query consists of an RDF graph, where some nodes or edges are replaced by variables.
There is, however, a close relationship between OWL and RDF since OWL ontologies
can be represented as RDF graphs. Furthermore, OWL’s RDF-Based Semantics is a
direct extension of the RDF and RDFS semantics. We focus here, however, on OWL’s
Direct Semantics, which is based on the DL SROIQ [
SELECT ?i FROM <ontologyIRI> WHERE f ?i rdf:type C g
where the triple in the WHERE clause is called a basic graph pattern (BGP) and is
written in Turtle [
OWL DL is a typed language and to map RDF triples into OWL structural objects, one often has to know the type of a term. For example, in order to map the triple p rdfs:subpropertyOf p0 into an OWL structural object, we have to know whether p is an abstract or a concrete role (an object or a data property), in the former case, the mapping results in SubObjectPropertyOf(p p0), whereas in the latter case, we get SubDataPropertyOf(p p0). In DL notation, we get p v p0, but p and p0 would either be abstract or concrete roles. In many cases, the typing information from the queried KB can be used to disambiguate the mapping process. For variables that map to concepts or roles, however, typing information is usually required and has to be added to the BGP. For example, a rdf:type [ rdf:type owl:Restricion ; owl:onProperty ?x ; owl:someValuesFrom ?y ] could be mapped to either (1) or (2).
ClassAsserion(ObjectSomeVauesFrom(?x ?y) a) (1)
ClassAsserion(DataSomeVauesFrom(?x ?y) a) (2)
In such a case, a triple such as ?x rdf:type owl:ObjectProperty can be added to
disambiguate the mapping process. Although the SPARQL specification uses Turtle, other
query syntaxes can also be defined. Pellet accepts, for example, queries where the BGP
is written in Manchester Syntax [
For further details, we refer interested readers to the W3C specification that defines
the mapping between OWL structural objects and RDF graphs [
In the following, we directly write BGPs in DL notation extended to allow for variables in place of concept, role and individual names in axioms. For simplicity, we do not consider concrete roles (data properties) here.
Anonymous individuals in the query are treated as variables whose bindings do not appear in the query’s result sequence. This is motivated by the way SPARQL handles anonymous individuals (known as blank nodes in RDF terminology). This is in contrast to conjunctive queries where they are treated as existential variables. Furthermore, anonymous individuals in the queried KB are treated as (Skolem) constants and can be returned in a query answer. For brevity, we assume here that neither the query nor the queried KB contains anonymous individuals.
Definition 1. Let NC, NR, NI , VC, VR, and VI be countable, infinite, and pairwise disjoint sets of concept names, role names, individual names, concept variables, role variables, and individual variables, respectively. We call S = (NC; NR; NI ; VC; VR; VI ) a signature. A SPARQL-OWL query w.r.t. S consists of axiom templates, which are SROIQ axioms where in place of concept names, one can use names from NC [ VC, in place of role names, one can use names from NR [ VR, and in place of individual names, one can use names form NI [ VI . A SROIQ knowledge base uses only terms from NC; NR, and NI . The restriction of S to terms that occur in a knowledge base K (a query q) is denoted as SK (Sq); we write V(q) to denote the set of all variables in q.
Given a knowledge base K with SK = (NCK ; NK ; NIK ; ;; ;; ;) and a query q over R (NCK ; NRK ; NIK ; VC; VR; VI ), a solution mapping for q over K is a partial function : VC [ VR [ VI ! NCK [ NRK [ NIK such that dom( ) = V(q), (v) 2 NCK for each v 2 VC \ dom( ), (v) 2 NRK for each v 2 VR \ dom( ), and (v) 2 NIK for each v 2 VI \ dom( ), where dom( ) denotes the domain of ; we write (q) to denote the result of replacing each variable v in q with (v).
The evaluation of q over K yields a set of solution mappings with
f j K [ (q) is a SROIQ knowledge base and K j= (q)g
More complex WHERE clauses, which use operators such as UNION for alternative
selection criteria or OPTIONAL to query for optional bindings [
In the remainder, we use K to denote the SROIQ KB obtained from a queried RDF graph, and q for the query obtained from mapping a BGP into axiom templates. We further assume that the signature of K is SK = (NCK ; NRK ; NIK ; ;; ;; ;) and a query uses symbols from (NCK ; NRK ; NIK ; VC; VR; VI ). 3
A straightforward algorithm to realize the entailment regime simply tests, for each possible solution mapping , whether K j= (q). Since only terms that are used in K can occur in the range of solution mappings, there are finitely many mappings to test. In the worst case, however, the number of mappings that have to be tested is still exponential in the number of variables in the query. Such an algorithm is sound and complete if the reasoner used to decide entailment is sound and complete since we check all mappings for variables that can constitute actual solution mappings. 3.1
Optimizations cannot easily be integrated in the above sketched algorithm since it uses the reasoner to check for the entailment of the instantiated query as a whole and, hence, does not take advantage of relations that may exist between axiom templates. For a more optimized evaluation, we evaluate the query axiom template by axiom template. Initially, our solution set contains only the identity mapping, which does not map any variable to a value. We then pick our first axiom template, extend the identity mapping to cover the variables of the chosen axiom template and use the reasoner to check which of the mappings instantiate the axiom template into an entailed axiom. We then pick the next axiom template and again extend the mappings from the previous round to cover all variables and check which of those mappings lead to an entailed axiom. Thus, axiom templates which are very selective and are only satisfied by very few solutions reduce the number of intermediate solutions. Choosing a good execution order, therefore, can significantly a ect the performance.
For example, let q = fC(?x); r(?x ?y)g with r 2 NR; C 2 NC; ?x; ?y 2 VI . The query belongs to the class of conjunctive queries. We assume that the queried KB contains 100 individuals, only 1 of which belongs to the concept C. This C instance has 1 r-successor, while we have overall 200 pairs of individuals related with the role r. If we first evaluate C(?x), we test 100 mappings (since ?x is an individual variable), of which only 1 mapping satisfies the axiom template. We then evaluate r(?x ?y) by extending the mapping with all 100 possible mappings for ?y. Again only 1 mapping yields a solution. For the reverse axiom template order, the first axiom template requires the test of 100 100 mappings. Out of those, 200 remain to be checked for the second axiom template and we perform 10; 200 tests instead of just 200.
The importance of the execution order is well known in relational databases and cost based optimization techniques are used to find good execution orders. Ordering strategies as implemented in databases or triple stores are, however, not directly applicable in our setting. In the presence of expressive schema level axioms, we cannot rely on counting the number of occurrences of triples. We also cannot, in general, precompute all relevant inferences to base our statistics on materialized inferences. Furthermore, we should not only aim at decreasing the number of intermediate results, but also take into account the cost of checking or computing the solutions. This cost can be very significant with OWL reasoning.
For several kinds of axiom templates we can, instead of checking entailment, directly retrieve the solutions from the reasoner. For example, for C(?x), reasoners typically have a method to retrieve concept instances. Although this might internally trigger several tests, most methods of reasoners are highly optimized and avoid as many tests as possible. Furthermore, reasoners typically cache several results such as the computed concept hierarchy and retrieving sub-concepts can then be realized with a cache lookup. Thus, the actual execution cost might vary significantly. Notably, we do not have a straight correlation between the number of results for an axiom template and the actual cost of retrieving the solutions as is typically the case in triple stores or databases. This requires cost models that take into account the cost of the specific reasoning operations (depending on the state of the reasoner) as well as the number of results.
As motivated above, we distinguish between simple and complex axiom templates, where simple axiom templates are those that correspond to dedicated reasoning tasks. Complex axiom templates are, in contrast, evaluated by iterating over the compatible mappings and by checking entailment for each instantiated axiom template. An example of a complex axiom template is (9r:?x)(?y).
Algorithm 1 shows how we evaluate queries. We first explain the general outline of the algorithm and leave the details of the used submethods for the following section. We first simplify axiom templates where possible (rewrite, line 1). Next, the method connectedComponents (line 2) partitions the axiom templates into sets of connected components, i.e., within a component the templates share common variables, whereas between components there are no shared variables. Unconnected components unnecessarily increase the amount of intermediate results and, instead, we can simply combine the results for the components in the end (line 24). For each component, we proceed as described below: we first determine an order (method reorder in line 5). For a simple axiom template, which contains so far unbound variables, we then call a specialized reasoner method to retrieve entailed results (callReasoner in line 10). Otherwise, we check which compatible solutions yield an entailed axiom (lines 11 to 19). The method prune (lines 13 and 17) excludes mappings that cannot lead to entailed axioms. 3.2
Axiom Template Reordering We now explain how we order the axiom templates in the method reorder (line 5). Since complex axiom templates can only be evaluated with costly entailment checks, our aim is to reduce the number of bindings before we check the complex templates. The simple axiom templates are ordered by their cost, which is computed as the weighted sum of the estimated number of required consistency checks and the estimated result size. These estimates are based on statistics provided by the reasoner and this is the only part where our algorithm depends on the specific reasoner that is used. In case the reasoner cannot give estimates, one can still work with statistics computed from explicitly stated information. We do this for some simple templates, e.g., queries for domains and ranges of properties, for which the reasoner does not provide result size estimations. Since the result sizes for complex templates are di cult to estimate using either the reasoner or the explicitly stated information in K , we order complex templates based only on the number of bindings that have to be tested. It is obvious that the reordering of axiom templates does not a ect soundness and completeness of Algorithm 1.
Axiom Template Rewriting Some costly to evaluate axiom templates can be rewritten into axiom templates that can be evaluated more e ciently and yield an equivalent result. Such axiom templates are shown on the left-hand side of Table 1 and their equivalent simplified form is shown on the right-hand side. To understand the intuition behind such transformation, we consider a query with only the axiom template: ?x v 9r:?y u C. Its evaluation requires a quadratic number of consistency checks in the number of concepts (since ?x and ?y are concept variables). The rewriting yields: ?x v C and ?x v 9r:?y. The first axiom template is now evaluated with a cheap cache lookup (assuming that the concept hierarchy has been precomputed). For the second one, we only have to check the usually few resulting bindings for ?x combined with all other concept names for ?y. We apply the rewriting in the method rewrite in line 1 of our algorithm. Soundness and completeness is preserved since instantiated rewritten templates are semantically equivalent to the corresponding instantiated complex ones. Concept and Role Hierarchy Exploitation The number of consistency checks required to evaluate a query can be further reduced by taking the concept and role hierarchies into account. Once the concepts and roles are classified (this can ideally be done before a system accepts queries), the hierarchies are stored in the reasoner’s internal structures. We further use the hierarchies to prune the search space of solutions in the evaluation of certain axiom templates. We illustrate the intuition with an example: Infection v 9hasCausalLinkTo:?x If C is not a solution and B v C holds, then B is also not a solution. Thus, when searching for solutions for ?x, the method removeNext (line 15) chooses the next binding to test by traversing the concept hierarchy topdown. When we find a non-solution C, the subtree rooted in C of the concept hierarchy can safely be pruned, which we do in the method prune in line 17. Queries over knowledge bases with a large number of concepts and a deep concept hierarchy can, therefore, gain the maximum advantage from this optimization. We employ similar optimizations using the role hierarchies. It is obvious that we only prune mappings that cannot constitute actual solution and instance mappings, hence, soundness and completeness of Algorithm 1 is preserved.
Exploiting the Domain and Range Restrictions The implicit domains and ranges of the roles in K (in case the reasoner precomputes and stores them) and/or the explicit ones can be exploited to reduce the number of entailment checks that need to be performed in order to evaluate a query.
Let us assume that K contains > v 8takesCourse:Course, expressing a range restriction, and q contains GraduateStudent v 9takesCourse:?x. In case at least one solution mapping exists for ?x, the concept Course and its super-concepts can immediately be considered solution mappings for ?x. Moreover, if the reasoner precomputes the disjoint concepts, this information can be used to prune the possible concepts for ?x that are disjoint from the concept Course. This is done in the method prune (line 13), which again preserves soundness and completeness. 4
Since SPARQL’s entailment regimes only change the evaluation of BGPs, standard SPARQL algebra processors can be used to combine the intermediate results, e.g., in unions or joins. Furthermore, standard OWL reasoners such as HermiT, Pellet, or FaCT++ can be used to perform the required reasoning tasks. 4.1
In our system, the queried KB is loaded into an OWL reasoner and the reasoner
performs initial tasks such as concept classification before the system accepts queries. We
use the ARQ library7 of the Jena Semantic Web Toolkit for parsing the SPARQL queries
and for the SPARQL algebra operations apart from the BGP evaluation. The BGPs are
mapped to queries (as in Def. 1) and represented in a custom extension of the OWL API
[
We tested our system with the Lehigh University Benchmark (LUBM) [
costly operations such as the realization of the ABox, which computes the types for all individuals, are done in the beginning, depends on the setting and the reasoner. Since realization is relatively quick in HermiT for LUBM (GALEN has no individuals), we also performed this task upfront. The given results are averages from executing each query three times. The ontologies and all code required to perform the experiments are available online.8
We first evaluate the 14 LUBM queries. These queries are simple ones and have variables only in place of individuals and literals. The LUBM ontology contains 43 concepts, 25 abstract roles, and 7 concrete roles. We tested the queries on LUBM(1,0), which contains data for one university starting from index 0, and which contains 16,283 individuals and 8,839 literals. The ontology took 3.8 s to load and 22.7 s for classification and realization. Table 2 shows the execution time for each of the queries. The reordering optimization has the biggest impact on queries 2, 7, 8, and 9. These queries require much more time or are not answered at all within the time limit of 30 min without this optimization (758.9 s, 14.7 s, >30 min, >30 min, respectively).
Conjunctive queries are supported by a range of OWL reasoners. SPARQL-OWL allows, however, the creation of very powerful queries, which are not currently supported by any other system. In the absence of suitable standard benchmarks, we created a custom set of queries as shown in Table 3. Since the complex queries are mostly based on complex schema queries, we switched from the very simple LUBM ontology to the GALEN ontology. GALEN consists of 2,748 concepts and 413 abstract roles. The ontology took 1.6 s to load and 4.8 s to classify (concepts and roles). The execution time for these queries is shown on the right-hand side of Table 2. For each query, we tested
1 Infection v 9hasCausalLinkTo:?x 2 Infection v 9?y:?x 3 ?x v Infection u 9hasCausalAgent:?y 4 NAMEDLigament v NAMEDInternalBodyPart u ?x
?x v 9hasShapeAnalagousTo?y u 9?z:linear 5 ?x v NonNormalCondition ?z v ModifierAttribute Bacterium v 9?z:?w ?y v StatusAttribute ?w v AbstractStatus ?x v 9?y:Status the execution once without optimizations and once for each combination of applicable optimizations from Section 3.
As expected, an increase in the number of variables within an axiom template leads to a significant increase in the query execution time because the number of mappings that have to be checked grows exponentially in the number of variables. This can, in particular, be observed from the di erence in execution time between Query 1 and 2. From Queries 1, 2, and 3 it is evident that the use of the hierarchy exploitation optimization leads to a decrease in execution time of up to two orders of magnitude and, in combination with the query rewriting optimization, we can get an improvement of up to three orders of magnitude as seen in Query 3. Query 4 can only be completed in the given time limit if at least reordering and hierarchy exploitation is enabled. Rewriting splits the first axiom template into the following two simple axiom templates, which are evaluated much more e ciently:
NAMEDLigament v NAMEDInternalBodyPart and NAMEDLigament v ?x After the rewriting, the reordering optimization has an even more pronounced e ect since both rewritten axiom templates can be evaluated with a simple cache lookup. Without reordering, the complex axiom template could be executed before the simple ones, which leads to the inability to answer the query within the time limit of 30 min. Without a good ordering, Query 5 can also not be answered, but the additional use of the class and property hierarchy further improves the execution time by three orders of magnitude.
Although our optimizations can significantly improve the query execution time, the required time can still be quite high. In practice, it is, therefore, advisable to add as many restrictive axiom templates for query variables as possible. For example, the addition of ?y v Shape to Query 4 reduces the runtime from 68.2 s to 1.6 s. 5
We have presented a sound and complete query answering algorithm and novel optimizations for SPARQL’s OWL Direct Semantics entailment regime. Our prototypical query answering system combines existing tools such as ARQ, the OWL API, and the HermiT OWL reasoner. Apart from the query reordering optimization—which uses (reasoner dependent) statistics provided by HermiT—the system is independent of the reasoner used, and could employ any reasoner that supports the OWL API.
We evaluated the algorithm and the proposed optimizations on the LUBM benchmark and on a custom benchmark that contains queries that make use of the very expressive features of the entailment regime. We showed that the optimizations can improve query execution time by up to three orders of magnitude.
Acknowledgements This work was supported by EPSRC in the project HermiT: Reasoning with Large Ontologies. The work has also been supported by the EC Indicate project.