Ontologies are increasingly used to provide structure and enhance access to large datasets. In such applications the ontology can be seen as a TBox, and the dataset as an ABox, with the key reasoning problem being conjunctive query (CQ) answering. Unfortunately, for OWL 2 this problem is known to be of high worst case complexity, even when complexity is measured with respect to the size of the data, and in realistic settings datasets may be very large. One way to address this issue is to restrict the ontology to a fragment with better computational properties, and this is the motivation behind the OWL 2 pro les. Another approach is to optimise reasoning for arbitrary OWL 2 ontologies. This latter approach has proved very successful for TBox reasoning, with systems such as Konclude, HermiT, Pellet and Racer being widely used to reason over large-scale ontologies. Up to now, however, reasoning with large ABoxes has, in practice, largely been restricted to the OWL 2 pro les. In this paper we describe PAGOdA: a highly optimised reasoning system that supports CQ answering with respect to an arbitrary OWL 2 ontology and an RDF dataset (roughly equivalent to a SROIQ TBox and ABox). It uses a novel approach to query answering that combines a datalog (or OWL 2 RL) reasoner (currently RDFox [11]) with a fully- edged OWL 2 reasoner (currently HermiT [5]) to provide scalable performance while still guaranteeing sound and complete answers.1 PAGOdA delegates the bulk of the computational workload to the datalog reasoner, with the extent to which the fully- edged reasoner is needed depending on interactions between the ontology, the dataset and the query. This approach is `pay-as-you-go' in the sense that query answering is fully delegated to the datalog reasoner whenever the input ontology is expressed in any of the OWL 2 pro es; furthermore, even when using an out-of-pro le ontology, queries can often be fully answered using only the datalog reasoner; and even when the fully- edged reasoner is required, PAGOdA employs a range of optimisations, including relevant subset extraction, summarisation and dependency analysis, to reduce the number and size of the relevant reasoning problems. This approach has proved to be very e ective in practice: in our tests of more than 4,000 queries over 8 ontologies, none of which is contained within any of the OWL pro les, more than 99% of queries were fully answered without
1 In practice we are limited by the capabilities of OWL 2 reasoners, which typically restrict the structure of the ontology and/or query in order to ensure decidability (which is open for CQ answering over unrestricted OWL 2 ontologies). 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 conjunctive query answering service in real-world scenarios requiring both expressive ontologies and datasets containing hundreds of millions of facts.
The basic approach implemented in PAGOdA has been described in [13{15], and full details about the algorithms currently implemented can be found in a an accompanying technical report.2 Here, we provide an overview of the system and summarise the results of an extensive evaluation. 2
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 r implemented in KARMA.4 ELHO?
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 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.
The architecture of PAGOdA is depicted in Figure 1. We could, in principle, use any materialisation-based datalog reasoner that supports CQ evaluation and the incremental addition of facts, and any fully- edged OWL 2 DL reasoner that supports fact entailment.
PAGOdA uses four instances of RDFox (one in each of the lower and upper bound and subset extractor components) and 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.
We next describe each component, following the process ow of PAGOdA. 2 http://www.cs.ox.ac.uk/isg/tools/PAGOdA/pagoda-tr.pdf 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 rollig-up technique.
Lq
cert(q,O ∪ D) heuristic planner
HermiT q,Gq tracking encoder Σ,q,Gq
track(Σ,q,Gq)
Lq soundAnswers(q,Σ ∪ D) F 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
Full reasoning Extracting subsets Computing query bounds Materialisation
Loading ontology & data
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
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 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
the standard rolling-up technique to transform CQs into concepts [
LUBM(n) UOBM(n)
FLY
NPD DBPedia+ ChEMBL Reactome Uniprot ]axioms ]rules ]9-rules ]_-rules We have evaluated our 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. All test ontologies, queries, and results are available online.6
LUBM and UOBM are widely-used reasoning benchmarks [
FLY is an ontology used in the Virtual Fly Brain tool.7 Although the dataset
is small, the ontology is rich in existentially quanti ed rules, which makes query
answering challenging. We tested 6 CQs provided by the ontology developers.
NPD FactPages is an ontology describing petroleum activities in the
Norwegian continental shelf. The ontology comes with a dataset containing 3.8 million
facts. We tested all atomic queries over the signature of the ontology.
DBPedia contains information about Wikipedia entries. Although the dataset
is rather large, the ontology axioms are simple and can be captured by OWL 2
RL. To provide a more challenging test, we have used LogMap [
ChEMBL, Reactome, and Uniprot are ontologies that are available from
the European Bioinformatics Institute (EBI) linked data platform.8 They are
6 http://www.cs.ox.ac.uk/isg/tools/PAGOdA/2015/jair/
7 http://www.virtual ybrain.org/site/vfb site/overview.htm
8 http://www.ebi.ac.uk/rdf/platform
rich in both existential and disjunctive rules, and the datasets are large. In
order to test scalability, we computed subsets of the data using a data sampling
algorithm based on random walks [
In this test we used LUBM(1) and UOBM(1), 1% of the dataset for ChEMBL and UniProt, and 10% for Reactome; these are already hard for some systems, but can be processed by most. We rolled up all 6 queries into concepts wherever possible to get LUBM rolledUp, UOBM rolledUp and FLY rolledUp. Since the answers to the FLY queries under SPARQL semantics are all empty, we only present results for FLY rolledUp. We set timeouts of 20min for each individual query, and 5h for all the queries over a given ontology.
In Figure 2, each bar represents the performance of a particular reasoner w.r.t. a given ontology and set of test queries. We use green to indicate the percentage of queries for which the reasoner computed all the correct answers, where correctness was determined by majority voting, and blue (resp. purple) to indicate the percentage of queries for which the reasoner was incomplete (resp. unsound). Red, orange and grey indicate, respectively, the percentage of queries for which the reasoner reported an exception during execution, did not accept the input query, or exceeded the timeout. PAGOdA is not represented in the gure as it was able to correctly compute all answers for every query and test ontology within the given timeouts.
Figure 3 summarises the performance of each system relative to PAGOdA, but in this case we considered only those queries for which the relevant system yields an answer (even if unsound and/or incomplete). This is not ideal, but we chose to consider all such queries (rather than only the queries for which the relevant system yields the correct answer) because (i) the resulting time measurement is obviously closer to the time that would be required to correctly answer all queries; and (ii) correctness is only relative as we do not have a gold standard. For each ontology and reasoner, the corresponding bar shows t2=t1 (on a logarithmic scale), where t1 (resp. t2) is the total time required by PAGOdA (resp. the compared system) to compute the answers to the queries under consideration; a missing bar indicates that the comparison system failed to answer any queries within the given timeout. Please note that two di erent bars for the same ontology are not comparable as they may refer to di erent sets of queries, so each bar needs to be considered in isolation.
TrOWL is faster than PAGOdA on LUBM rolledUp, UOBM rolledUp and FLY rolledUp, but it is incomplete for 7 out of 14 LUBM queries and 3 out of 4 UOBM queries. For ChEMBL, TrOWL exceeds the timeout while performing the satis ability check. For the remaining ontologies, PAGOdA is more e cient in spite of the fact that TrOWL is incomplete for some queries, and even unsound for several UniProt queries.
Pellet times out for the FLY ontology, but it succeeds in computing all answers in the remaining cases. We can observe, however, that in all cases Pellet is significantly slower than PAGOdA, sometimes by more than two orders of magnitude. HermiT can only answer queries with one distinguished variable, so we could not evaluate binary queries. HermiT exceeds the timeout in many cases, and in the tests where it succeeds, it is signi cantly slower than PAGOdA. Hydrowl is based on a theoretically sound and complete algorithm, but it was found to be incomplete in some of our tests. It also exceeded the timeout for three of the ontologies, ran out of memory for another two of the ontologies, and reported an exception for ChEMBL 1%. In the remaining cases, it was signi cantly slower than PAGOdA. (b) LUBM query processing
G1(18)
G2(1) Q18 s 2.5 d n o sce 2 sdn su1.5 a o h T 1 0.5 0 0 1 100 200 300 400 500 100 200 300 400 500 (c) UOBM pre-processing
(d) UOBM query processing Scalability Tests 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%. In each case we used the test queries described in Section 3.1. 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. We set a timeout of 2:5h for each individual query and 5h for all queries.
We also tested Pellet (the only other system found to be sound and complete for our tests) on Reactome, the only case were Pellet managed to process at least two datasets.
Our results are summarised in Figures 4 and 5. 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.
s 12 d n o sce10 sd san 8 u o h T 6 4 2 s 14 d cno12 se sd 10 e r ndu 8 H6 4 2 s 2.0 d ceno ss 1.5 d san u ho1.0 T 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.
Total L1 + U1 L2 + U1 L2 + U2 L2 + U2j3 35 20 6 478 1247 1896 26 4 0 442 1240 1883 33 4 5 442 1241 1883 33 12 5 442 1241 1883 33 16 5 473 1246 1896 Table 2: ]Queries answered by di erent bounds 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 much more challenging, but it could still be answered in less than 900 seconds, even for the largest dataset.
On Reactome, Pellet is able to process the samples of size 10%; 20% and 30%, with pre-processing times comparable to PAGOdA. Average query-processing times for queries in G1 and G2 are slightly higher than those of PAGOdA, but times for query Q65 were signi cantly higher. This was due to PAGOdA's subset extraction technique, which is able to keep the input to the fully- edged reasoner small, even for the largest datasets.
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.
E ectiveness of Di erent Techniques We have evaluated the e ectiveness of the various reasoning techniques implemented in PAGOdA by comparing the numbers of test queries that can be fully answered using the relevant technique. Query bounds Table 2 illustrates the e ectiveness of di erent combinations of upper and lower bounds in terms of the number of queries for which the bounds coincided for each test ontology and its smallest test datasets. In the table, we refer to the lower bound computed w.r.t. the datalog subset of the input knowledge base as L1 and to the combined lower bound computed by PAGOdA as L2. Similarly, we refer the naive upper bound computed using a datalog over-approximation of as U1; the upper bound computed w.r.t. M2U and M3U as U2 and U3; and the combined upper bound as U2j3.
It can be seen that L1 and U1 su ce to answer most of the queries in many test ontologies. L2 was very e ective in the case of FLY, where the basic bounds did not match for any query, and also useful for LUBM, yielding matching bounds for 7 more queries. U2, was especially e ective for UOBM and Reactome, where many existentially quanti ed rules were already satis ed by the lower bound materialisation. Finally, the re ned treatment of disjunctive rules in U2j3 was instrumental in obtaining additional matching bounds for non-Horn ontologies. Subset extraction Table 3 shows, for each dataset, the maximum percentage of facts and rules that are included in the relevant subset over all test queries with non-matching bounds. We can observe that subset extraction is e ective in all cases in terms of both facts and rules.
Summarisation and Dependencies The e ectiveness of these techniques was measured by the number of `hard' calls to HermiT that were required to fully answer each query, where a call is considered hard if the knowledge base passed to HermiT is not a summary. The rst row of Table 4 shows the number of gap answers for each query where the L2 and U2j3 bounds don't match. Without optimisation, we would have to call HermiT this number of times to fully answer each query. Row 2 (resp. row 3) shows the number of hard calls to HermiT after applying summarisation (resp. summarisation plus dependency analysis). 4
The reasoning techniques we have proposed here are very general and are applicable to a wide range of knowledge representation languages. Our main goal in practice, however, has been to realise our approach in a highly scalable and robust query answering system for OWL 2 DL ontologies, which we have called PAGOdA. Our extensive evaluation has not only con rmed the feasibility of our approach in practice, but also that our system PAGOdA signi cantly ourperforms state-of-the art reasoning systems in terms of both robustness and scalability. In particular, our experiments using the ontologies 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.
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. 13. Zhou, Y., Nenov, Y., Cuenca Grau, B., Horrocks, I.: Complete query answering over horn ontologies using a triple store. In: The Semantic Web - ISWC 2013 12th International Semantic Web Conference, Sydney, NSW, Australia, October 21-25, 2013, Proceedings, Part I. Lecture Notes in Computer Science, vol. 8218, pp. 720{736. Springer (2013) 14. Zhou, Y., Nenov, Y., Cuenca Grau, B., Horrocks, I.: Pay-as-you-go ontology query answering using a datalog reasoner. In: Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014. CEUR Workshop Proceedings, vol. 1193, pp. 352{364. CEUR-WS.org (2014) 15. Zhou, Y., Nenov, Y., Cuenca Grau, B., Horrocks, I.: Pay-as-you-go OWL query answering using a triple store. In: Proceedings of the Twenty-Eighth AAAI Conference on Arti cial Intelligence (2014), http://www.aaai.org/ocs/index.php/ AAAI/AAAI14/paper/view/8232