We describe PAGOdA: a highly optimised `pay-as-you-go' reasoning system that
supports conjunctive query (CQ) answering with respect to an arbitrary OWL 2
ontology and an RDF dataset. PAGOdA uses a novel hybrid approach to query
answering that combines a datalog reasoner (currently RDFox [
This approach has proved to be very e ective in practice: in our tests of more than 2,000 queries over ve ontologies, none of which is contained within any of the OWL pro les, more than 99% of queries were fully answered without resorting to the fully- edged reasoner. Moreover, even when the fully- edged reasoner was used, the above mentioned optimisations were highly e ective: the size of the dataset was typically reduced by an order magnitude, and often by several orders of magnitude, and it seldom required more than a single test to resolve the status of all potential answer tuples. Taken together, our experiments demonstrate that PAGOdA can provide an e cient CQ answering service in real-world scenarios requiring both expressive ontologies and datasets containing hundreds of millions of facts.
The basic approach in PAGOdA has been described in [
PAGOdA is written in Java and it is available under an academic license.3 As well as RDFox and HermiT, PAGOdA also exploits the combined approach for CQ r implemented in KARMA.4 The architecture of PAGOdA answering in E LHO? is depicted in Figure 1.
PAGOdA accepts as input arbitrary OWL 2 DL ontologies, datasets in Turtle format and CQs in SPARQL. Queries can be interpreted under ground or certain answer semantics. In the former case, PAGOdA is sound and complete. In the latter case, however, PAGOdA is ultimately limited by the capabilities of HermiT, which can only check entailment of ground or DL concept queries; hence, PAGOdA can guarantee completeness only if the lower and upper bounds match, or if the query can be transformed into a DL concept query via rolling-up.5 Otherwise, PAGOdA returns a sound (but possibly incomplete) set of answers, along with a bound on the incompleteness of the computed answer set.
PAGOdA uses four instances of RDFox: one for the lower bound, one for each upper bound materialisation (c-chase and c-chasef ), and one for subset extraction. Furthermore, it uses two instances of HermiT (one in each of the summary lter and dependency graph components).
The process of fully answering a query can be divided into several steps. Here, we distinguish between query independent steps and query dependent ones. As we can see in Figure 1, the `loading ontology' and `materialisation' steps are query independent. Therefore, both of them are counted as pre-processing steps. `Computing query bounds', `extracting subset' and `full reasoning' are query dependent, and are called query processing steps.
Loading ontology and data. PAGOdA uses the OWL API to parse the input
ontology O. The dataset D is given separately in Turtle format. The normaliser
then transforms the ontology into a set of rules corresponding to the axioms in
O. PAGOdA's normaliser is an extension of HermiT's clausi cation component
[
After normalisation, the ontology is checked to determine if it is inside OWL
r ); if so, then RDFox (resp. KARMA) is already sound and
2 RL (resp. E LHO?
complete, and PAGOdA simply processes O, D and subsequent queries using the
relevant component. Otherwise, PAGOdA uses a variant of shifting |a
polynomial program transformation commonly used in Answer Set Programming [
Materialisation. There are three components involved in this step, namely lower bound, c-chase and c-chasef . Each of these takes as input and D, and each computes a materialisation (shown in Figure 1 as ellipses). The lower bound 3 http://www.cs.ox.ac.uk/isg/tools/PAGOdA/ 4 http://www.cs.ox.ac.uk/isg/tools/KARMA/. 5 PAGOdA implements an extension of the well-known rolling-up technique. Full reasoning Extracting subsets Computing query bounds Materialisation
Loading ontology & data Lq
cert(q,O ∪ D) heuristic planner
HermiT q,Gq tracking encoder Σ,q,Gq track(Σ,q,Gq)
Lq FsoundAnswers(q,Σ ∪ D) M2L
q lower store
KARMA
RDFox endormophism checker
G0 ⊆ Gq summary filter
HermiT q,Gq
Kq subset extractor
RDFox of D
D certU2(q,Σ ∪ D) M2U
q Gq D c-chase
RDFox certU3(q,Σ ∪ D) M3U
q c-chasef *
RDFox Σ shift profile checker normaliser
HermiT clausifier
O
component rst uses RDFox to compute a materialisation of D using the
datalog subset of ; it then uses the materialised dataset as input to KARMA,
which computes the materialisation M2L using the E LHOr? subset of . The
c-chase and c-chasef components compute the M2U and M3U upper bound
materialisations using chase-like procedures [
If ? is derived while computing M2L, then the input ontology and dataset is unsatis able, and PAGOdA simply reports this and terminates. If ? is derived while computing M3U , then the computation is aborted and M3U is no longer used. If ? is derived while computing M2U , then PAGOdA checks the satis ability of [D (using the optimised query answering procedure described below). If [D is unsatis able, then PAGOdA reports this and terminates; otherwise the input ontology and dataset is satis able, and PAGOdA is able to answer queries. Computing query bounds. Given a query q, PAGOdA uses the M2L lower bound materialisation to compute the lower bound answer Lq, exploiting the ltration procedure in KARMA to eliminate spurious answer tuples (shown as ]facts a circle with an `F' in it in Figure 1). If ? was not derived when computing the M3U materialisation, then the upper bound answer U q is the intersection of the query answers w.r.t. M3U and M2U ; otherwise U q is computed using only M2U . Extracting subsets. If Lq = U q, then PAGOdA simply returns Lq; otherwise it must determine the status of the tuples in the `gap' Gq = U q n Lq. To do this, PAGOdA extracts subsets of and D that are su cient to check the entailment of each such tuple. First, the tracking encoder component is used to compute a datalog program that tracks rule applications that led to the derivation of the tuples in Gq. This program is then added to the rules and data in the c-chase component, and RDFox is used to extend the c-chase materialisation accordingly. The freshly derived facts (over the tracking predicates introduced by the tracking encoder) are then passed to the subset extractor component, which identi es the relevant facts and rules in and D.
Full reasoning. PAGOdA uses HermiT to verify answers in Gq. As HermiT
only accepts queries given either as facts or DL concepts, we have implemented
an extension of the rolling-up technique to internalise CQs as ontology axioms
[
We have evaluated PAGOdA on a range of realistic and benchmark ontologies, datasets and queries. Experiments were conducted on a 32 core 2.60GHz Intel Xeon E5-2670 with 250GB of RAM, and running Fedora 20.6 Further details, including detailed comparison with other systems, additional experiments, and results on other ontologies are given in our technical report.
Table 1 summarises our test data. LUBM and UOBM are widely-used
benchmarks [
We tested the scalability of PAGOdA on LUBM, UOBM and the ontologies from the EBI platform. For LUBM we used datasets of increasing size with a step of n = 100. For UOBM we also used increasingly large datasets with step n = 100 and we also considered a smaller step of n = 5 for hard queries. Finally, in the case of EBI's datasets, we computed subsets of the data of increasing sizes from 1% of the original dataset up to 100% in steps of 10%. For each test ontology we measured pre-processing time and query processing time as described in Section 2. We organise the test queries into three groups: G1: queries for which the lower and upper bounds coincide; G2: queries with a non-empty gap, but for which summarisation is able to lter out all remaining candidate answers; and G3: queries where the fully- edged reasoner is called over an ontology subset on at least one of the test datasets. A timeout of 2:5h was set for each individual query and 5h for all queries.
Our results are summarised in Figure 2. For each ontology, we plot time against the size of the input dataset, and for query processing we distinguish di erent groups of queries as discussed above. PAGOdA behaves relatively uniformly for queries in G1 and G2, so we plot only the average time per query for these groups. In contrast, PAGOdA's behaviour for queries in G3 is quite variable, so we plot the time for each individual query.
LUBM(n) All LUBM queries belongs to either G1 or G3 with the latter group containing two queries. The average query processing time for queries in G1 never exceeds 13s; for the two queries in G3 (Q32 and Q34), this reaches 8; 000s for LUBM(800), most of which is accounted for by HermiT.
UOBM(n) As with LUBM, most test queries were contained in G1, and their processing times never exceeded 8 seconds. We found one query in G2, and PAGOdA took 569s to answer this query for UOBM(500). UOBM's randomised data generation led to the highly variable behaviour of Q18: it was in G3 for UOBM(1) UOBM(10) and UOBM(50), causing PAGOdA to time out in the last case; it was in G2 for UOBM(40); and it was in G1 in all other cases. ChEMBL All test queries were contained in G1, and average processing time was less than 0:5s in all cases. Thus, we have not depicted the scalability of query processing for ChEMBL in Figure 2.
Reactome Groups G2 and G3 each contained one query, with all the remaining queries belonging to G1. Query processing time for queries in G1 never exceeded 10 seconds; for G2 processing time appeared to grow linearly in the size of datasets, and average time never exceeded 10 seconds; the G3 query (Q65) is 7 http://www.ebi.ac.uk/rdf/platform (a) LUBM pre-processing (b) LUBM query processing (c) UOBM pre-processing s 2.5 saTdnhndoo 1 sce 2 su1.5 0.5 0 0
G1(18) G2(1) Q18 much more challenging, but it could still be answered in less than 900 seconds, even for the largest dataset.
Uniprot In contrast to the other cases, Uniprot as a whole is unsatis able; however, our sampling technique can produce a satis able subset up to 40%. For larger subsets, pre-processing times drop abruptly as unsatis ability can be e ciently detected in the lower bound. Query processing times were only considered for satis able samples. There were no queries in G3, and only four in G2, all of which were e ciently handled. 4
We have described PAGOdA: a highly scalable and robust query answering system for OWL 2 DL ontologies. Our experiments using the realistic ontologies and datasets in the EBI linked data platform have shown that PAGOdA is capable of fully answering queries over highly complex and expressive ontologies and realistic datasets containing hundreds of millions of facts|something that is far beyond the capabilities of state-of-the-art ontology reasoners. Acknowledgements. This work has been supported by the Royal Society under a Royal Society Research Fellowship, by the EPSRC projects MaSI3, Score! and DBOnto, and by the EU FP7 project Optique.