Lower and Upper Bounds for SPARQL Queries over OWL Ontologies

Introduction

The recent standardization of the SPARQL 1.1 Entailment Regimes [ 2 ], which extend the SPARQL Query Language [ 3 ] with the capability of querying also for implicit knowledge makes the need for an e cient evaluation of complex queries over OWL ontologies urgent. We present an approach for optimizing the evaluation of SPARQL queries over OWL ontologies using SPARQL’s OWL Direct Semantics entailment regime. Such queries consist of axiom templates, i.e., Description Logic (DL) axioms with variables in place of concept, role and individual names. Answers to such queries are mappings of query (concept, role or individual) variables to corresponding (concept, role or individual) names that instantiate the axiom templates to axioms entailed by the queried knowledge base (KB).

Since computing query answers over an expressive KB is computationally very costly, approximation techniques have been proposed that use a weakened version of the KB to compute a lower bound (yields sound but potentially incomplete results) and a strengthened version to compute an upper bound (yields complete but potentially unsound results) for the results [ 9, 7, 8 ]. Another well-known technique is to compute the bounds from a complete and clash-free tableau generated by a DL reasoner [ 4, 5 ]. Deterministically derived facts are used as lower bound, while also non-deterministically derived ones are considered for the upper bound. Answers in the “gap”, i.e., potential answers in the upper but not the lower bound, usually have to be checked individually by performing a consistency check with a fully fledged OWL 2 DL reasoner.

While we also use bounds, we allow for much more expressive queries than related approaches. To optimize the evaluation of possible query answers in the gap, we present a query extension approach that uses the TBox of the queried KB to extend the query with additional parts. We show that the resulting query is equivalent to the original one and we use the additional parts that are simple to evaluate for restricting the bounds of subqueries of the initial query. In an empirical evaluation we show that the proposed query extension approach can lead to a significant decrease in the query execution time of up to four orders of magnitude. More details about our method as well as more evaluation results can be found in the extended version of our paper [ 1 ]. We will show the intuition of the proposed query extension method through an example. Let K be a KB, A; B; C be concept names, r a role name, a; b; c; d individual names, x an individual variable, Y a concept variable and

T = f B v A t C; 9r:B v Cg A = fA(a); B(b); r(a; b); A(d)g

q = fA(x); 9r:Y(x); Y v Bg Note that the only answer for q over K is the mapping f j (x) = a; (Y) = Bg.

First we compute bounds for axiom templates of q over K . Since fA(a); A(d)g K we have K j= A(a) and K j= A(d). That is, we can find the lower bound L = f j (x) 2 fa; dgg for the query fA(x)g over K without performing any tests. To find an upper bound for fA(x)g, we can use a model I of K . It is easy to check that K has a model I = ( I; I) with I = fd1; d2; d3; d4g, aI = d1, bI = d2, cI = d3, dI = d4, AI = fd1; d2; d4g, BI = fd2g, CI = fd1g and rI = fhd1; d2ig. Note that I 6j= A(c). Thus, from this model alone one can conclude that K 6j= A(c) and hence that the set U = f j (x) 2 fa; b; dgg provides an upper bound for the query fA(x)g over K . Although the model I can be similarly used for finding an upper bound for complex templates, such as f9r:Y(x)g, in general it can only be found by iterating over all possible mappings for x and Y and checking which instances of this template are entailed by the model. Therefore, in practice, one does not compute the bounds for complex templates. The bounds for the query fY v Bg can be computed by classifying the KB and retrieving subsumption relationships for B. Since for classification one usually needs to consider just the (relatively small) TBox T , the bounds for this query can be computed exactly, i.e., in our example we have L = U = f j (Y) 2 f?; Bgg.

Our query extension method uses additionally the notion of a subquery bound,which provides a range for those answers of a subquery (subset of templates) of q that are su cient to evaluate q. The intuition of our method is that subquery bounds can be improved using bounds of other subqueries of this query. Thus, if a query q can be extended to an equivalent query q [ q0, the number of reasoner calls performed for evaluating q can be reduced using q0. The proposed algorithm can be summarized as follows: First, we replace every (concept, role, individual) variable in q with a fresh distinct (concept, role, individual) name. For our example, consider a mapping such that (x) = ax, (Y) = AY with ax an individual and AY a concept name. Then we materialize and classify K plus (q), where (q) denotes the result of replacing each variable x in q with (x), i.e., we compute all concept assertions A(a), role assertions r(a; b), and subsumptions A v B with atomic concepts and roles entailed by K [ (q). Afterwards, we replace names back with their corresponding variables in the extended KB. In our example T [ (q) = fB v A t C; 9r:B v C; A(ax); 9r:AY (ax); AY v Bg j= C(ax). Thus, for q0 = fC(x)g, we have K [ (q) j= C(ax) = (q0), and it holds that the query q has the same answers for K as the extended query q [ q0 = fA(x); 9r:Y(x); Y v B; C(x)g. In the end, we compute query bounds for the templates in q0 and use them to improve the subquery bounds for templates in q. Using again the model I for K , since I j= C(a), but I 6j= C(b), I 6j= C(c) and I 6j= C(d), we can derive the upper bound U = f j (x) = ag for the query fC(x)g. Using this upper bound, it is now possible to reduce the upper bound for the subquery fA(x)g of q to U. Since U is a subset of the lower bound for fA(x)g (computed in the beginning of the section), this subquery can be evaluated without performing any further entailment tests. The new upper bound U can also be used to further reduce the upper bound for the subquery f9r:Y(x)g of q to f j (x) = a; (Y) 2 f?; Bgg. After this reduction, this subquery can be evaluated using just two entailment tests.

Evaluation

The proposed method has been implemented and evaluated over a set of well-known benchmark ontologies and relevant datasets and for several forms of queries. Although it can be used, in general, for improving the performance of most query answering systems based on query bounds, here the evaluation is based on the system described in Kollia et al. [ 5 ], which, to the best of our knowledge, is the only system that supports the evaluation of complex queries over OWL 2 DL ontologies under the OWL Direct Semantics entailment regime of SPARQL 1.1. In our implemented method (referred to as evalExt) we improve the subquery bounds computed in evalStatic [ 5 ] using the method described in the previous section. Afterwards, we perform the ordering and evaluation methods of Kollia et al. using the improved subquery bounds.

In Table 1 we show the results of the evaluation on the University Ontology Benchmark (UOBM) [ 6 ] using a range of custom queries since the queries provided for UOBM are only simple conjunctive instance queries. Column 1 shows the query qi and extension templates qi0 (1 i 6), columns 2 and 3 show the query answering times and the number of performed entailment checks for evalStatic, respectively, and columns 4 and 5 show the respective numbers for evalExt. In all queries the time spent for query extension is negligible compared to the time spent for query evaluation. We observe that for all queries, additional extension templates were derived, which have significantly better query bounds than the complex templates of the queries. This directly translates to a significantly lower number of entailment checks for evalExt and, hence, a reduction in execution times. The reduction in query answering times is up to four orders of magnitude.

References

1. Glimm , B. , Kazakov , Y. , Kollia , I. , Stamou , G.: Lower and upper bounds for SPARQL queries over OWL ontologies . In: Proceedings of the 29th Conference on Artificial Intelligence (AAAI'15) ( 2015 )

2. Glimm , B. , Ogbuji , C. (eds.): SPARQL 1.1 Entailment Regimes . W3C Recommendation ( 2013 ), available at http://www.w3.org/TR/sparql11-entailment/

3. Harris , S. , Seaborne , A . (eds.) : SPARQL 1 .1 Query Language. W3C Recommendation ( 2013 ), available at http://www.w3.org/TR/sparql11-query/

4. Kollia , I. , Glimm , B. : Cost based query ordering over OWL ontologies . In: Proceedings of the 11th International Semantic Web Conference (ISWC 2012). Lecture Notes in Computer Science , vol. 7649 , pp. 231 - 246 . Springer ( 2012 )

5. Kollia , I. , Glimm , B. : Optimizing SPARQL Query Answering over OWL Ontologies . Journal of Artificial Intelligence Research 48 , 253 - 303 ( 2013 )

6. Ma , L. , Yang , Y. , Qiu , Z. , Xie , G. , Pan , Y. , Liu , S. : Towards a complete OWL ontology benchmark . In: The Semantic Web: Research and Applications , pp. 125 - 139 . Lecture Notes in Computer Science, Springer ( 2006 )

7. Pan , J.Z. , Thomas , E. , Zhao , Y. : Completeness guaranteed approximation for OWL-DL query answering . In: Proceedings of the 22nd International Workshop on Description Logics (DL'09) . CEUR Workshop Proceedings , vol. 477 . CEUR-WS.org ( 2009 ), http://dblp. uni-trier.de/db/conf/dlog/dlog2009.html#PanTZ09

8. Ren , Y. , Pan , J.Z. , Zhao , Y. : Soundness preserving approximation for TBox reasoning . In: Proceedings of the 25th National Conference on Artificial Intelligence (AAAI'10) . AAAI Press ( 2010 )

9. Zhou , Y. , Nenov , Y. , Grau , B.C. , Horrocks , I. : Pay-as-you-go OWL query answering using a triple store . In: Proceedings of the 28th Conference on Artificial Intelligence (AAAI'14) . pp. 1142 - 1148 ( 2014 )