Conjunctive query answering over unrestricted OWL 2 ontologies

Tracking #: 3206-4420

This paper is currently under review
Authors: 
Federico Igne
Stefano Germano
Ian Horrocks

Responsible editor: 
Guilin Qi

Submission type: 
Full Paper
Abstract: 
Conjunctive query (CQ) answering is one of the primary reasoning tasks over knowledge bases (KBs). However, when considering expressive description logics, query answering can be computationally very expensive; reasoners for CQ answering, although heavily optimized, often sacrifice expressive power of the input ontology or completeness of the computed answers in order to achieve tractability and scalability for the problem. In this work, we present a hybrid query answering architecture that combines black-box services to provide a CQ answering service for OWL. Specifically, it combines scalable CQ answering services for tractable languages with a CQ answering service for a more expressive language approaching the full OWL 2. If the query can be fully answered by one of the tractable services, then that service is used. Otherwise, the tractable services are used to compute lower and upper bound approximations, taking the union of the lower bounds and the intersection of the upper bounds. If the bounds do not coincide, then the "gap" answers are checked using the "full" service. These techniques led to the development of two new systems: (i) RSAComb an efficient implementation of a new tractable answering service for RSA, and (ii) ACQuA, a reference implementation of the proposed hybrid architecture combining RSAComb, PAGOdA, and HermiT to provide a CQ answering service for OWL. Our extensive evaluation shows how the additional computational cost introduced by reasoning over a more expressive language like RSA can still provide a significant improvement compared to relying on a fully-fledged reasoner. Additionally, we show how ACQuA can reliably match the performance of PAGOdA, a state of the art CQ answering system that uses a similar approach, and can significantly improve performance when PAGOdA extensively relies on the underlying fully-fledged reasoner.
Full PDF Version: 
Tags: 
Under Review