PAGOdA: Pay−as−you−go ABox Reasoning
Yujiao Zhou, Bernardo Cuenca Grau, Yavor Nenov, Ian Horrocks · Description Logics · 2015
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 profiles. 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 profiles. 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-fledged OWL 2 reasoner (currently HermiT [5]) to provide scalable performance while still guaranteeing sound and complete answers. PAGOdA delegates the bulk of the computational workload to the datalog reasoner, with the extent to which the fully-fledged 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 profies; furthermore, even when using an out-of-profile ontology, queries can often be fully answered using only the datalog reasoner; and even when the fully-fledged 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 effective in practice: in our tests of more than 4,000 queries over 8 ontologies, none of which is contained within any of the OWL profiles, more than 99% of queries were fully answered without