Conjunctive query (CQ) answering over knowledge bases is an important reasoning task. However, with expressive ontology languages such as OWL, query answering is computationally very expensive. The PAGOdA system addresses this issue by using a tractable reasoner to compute lower and upper-bound approximations, falling back to a fullyfledged OWL reasoner only when these bounds don't coincide. The effectiveness of this approach critically depends on the quality of the approximations, and in this paper we explore a technique for computing closer approximations via RSA, an ontology language that subsumes all the OWL 2 profiles while still maintaining tractability of standard reasoning tasks. We present a novel approximation of OWL 2 ontologies into RSA, and an algorithm to compute a closer lower bound approximation using the RSA combined approach. We have implemented these algorithms in our prototype and conducted an extensive evaluation thereof.
Conjunctive query (CQ) answering is one of the primary reasoning tasks over knowledge bases for many applications. However, when considering expressive ? This work was supported by the AIDA project (Alan Turing Institute), the SIRIUS Centre for Scalable Data Access (Research Council of Norway, project no.: 237889), Samsung Research UK, Siemens AG, and the EPSRC projects AnaLOG (EP/P025943/1), OASIS (EP/S032347/1) and UK FIRES (EP/S019111/1). 1 Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). description logic languages, query answering is computationally very expensive, even when considering only complexity w.r.t. the size of the data (data complexity ). Fully-fledged reasoners oriented towards CQ answering over unrestricted OWL 2 ontologies exist but, although heavily optimised, they are only effective on small to medium datasets. In order to achieve tractability and scalability for the problem, two main approaches are often used: either the expressive power of the input ontology or the completeness of the computed answers is sacrificed.
Using the first approach, query answering procedures have been developed
for several fragments of OWL 2 for which CQ answering is tractable with respect
to data complexity [
A particularly interesting approach to CQ answering over unrestricted OWL 2
ontologies is adopted by the reasoner PAGOdA [
This work expands on this “pay-as-you-go” technique; it aims to improve the
lower-bound approximation in PAGOdA, tightening the gap between lower and
upper bounds and minimising the use of HermiT. We achieve this by (soundly)
approximating the input ontology into RSA [
Figure 1 summarises the workflow of the system: (i) normalisation and customisable approximation steps approximate an unrestricted OWL 2 ontology to RSA; (ii) the canonical model is then computed for the resulting ontology; (iii) a Approximation to RSA
Canonical model computation 30 25 tecom )(ssdn2105 a co eR se10 5 0 180 160 140 )120 (s LBUMssecodn1680000 0 0 0 0 0 0 0 0 10 20 30 40 50 60 70 80
LUBM size 0 0 0 0 0 0 0 0 10 20 30 40 50 60 70 80
LUBM size Datalog filtering program is derived from the input query and is combined with the canonical model to produce the set of certain answers to the input query over the approximated ontology. Depending on how the approximation is performed, the set of answers returned might have different properties (e.g., the approximation currently provided computes a lower bound of the answers to the query over the original ontology).
It is worth noting that, in this scenario, steps (i),(ii) are query independent, while step (iii) is ontology independent. As such, when multiple queries are submitted, steps (1-2) can be performed “offline” and only the third step needs to be performed for each input query. We took advantage of this and streamlined the execution of the combined approach by factoring out those steps that are query independent to make answering multiple queries over the same knowledge base more efficient.
We have carried out an extensive evaluation to assess the effectiveness of the
system and test the scalability and performance of the different steps in the
execution of the combined approach. In Figure 2, we compare the scalability
of approximation and canonical model computation steps over LUBM [
Q u e r y 1 100 80 60 40 20 0
Q u e r y 2 100 80 60 40 20 0
Q u e r y 3
Reactome2. The two steps are query independent and present a linear growth w.r.t. the dataset size of both knowledge bases.
Another interesting aspect is that most of the time the filtering step takes considerably less time than the canonical model computation. Figure 3 shows the percentage time distribution of three of the tested queries over Reactome. Filtering takes consistently less that 20% of the total execution time, when considering bigger datasets. As mentioned before, we can limit the impact of the canonical model computation by factoring out the task and computing it “offline” whenever we found ourselves in a scenario in which we need to perform query answering over a fixed ontology.
Overall, our experimental results show that the new technique yields significant performance improvements in several important application scenarios and solve some critical problems present in the original PAGOdA implementation. 4
We are already working on additional improvements to the approximation algorithm to RSA; the current visit of the dependency graph to detect the axioms to delete might be improved with different heuristics and might in some cases take into account the input query (deleting axioms that are not necessarily involved in the computation of the answers). A similar approach could be introduced to integrate RSA in the upper-bound of the answers to a query, with the ultimate goal of improving this step in PAGOdA as well.
On a different note, we hope to obtain additional improvements in performance in the current implementation of the RSA combined approach by introducing parallel execution of filtering steps for different input queries, using the named graph functionality provided by RDFox. 2 https://reactome.org/