| Summary: | Conjunctive query (CQ) answering is one of the primary reasoning tasks over knowledge bases (KBs). However, when considering expressive description logics (DLs), 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 (Web Ontology Language). 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 the RSA (role safety acyclic) ontology language; (ii) ACQuA, a reference implementation of the proposed hybrid architecture combining RSAComb, PAGOdA (Zhou, Cuenca Grau, Nenov, et al. 2015), and HermiT (Glimm, Horrocks, Motik, et al. 2014) 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 showed how ACQuA can reliably match PAGOdA’s performance and further limit its performance issues, especially when the latter extensively relies on the underlying fully-fledged reasoner.
|
|---|