PAGOdA: Pay-as-you-go ontology query answering using a datalog reasoner - Zhou, Y (2015)
Answering conjunctive queries over ontology-enriched datasets is a core reasoning task for many applications of semantic technologies. Conjunctive query answering is, however, computationally very expensive, which has led to the development of query answering procedures that sacrifice either the expressive power of ontology languages, or the completeness of query answers in order to improve scalability. This thesis describes a hybrid approach to query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable "pay-as-you-go" performance. The key feature of this hybrid approach is that it delegates the bulk of the computation to the datalog reasoner and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. Although the main goal of this thesis is to efficiently answer queries over OWL 2 ontologies, the technical results are more general and the approach is applicable to first-order knowledge representation languages that can be captured by rules allowing for existential quantification and disjunction in the head; the only assumption is the availability of a datalog reasoner and a fully-fledged reasoner for the language of interest, both of which are used as "black boxes". All techniques proposed in this thesis are implemented in the PAGOdA system, which combines the datalog reasoner RDFox and the OWL 2 reasoner HermiT. An extensive evaluation shows that PAGOdA succeeds in providing scalable pay-as-you-go query answering for a wide range of OWL 2 ontologies, datasets and queries.