Conjunctive query answering over unrestricted OWL 2 ontologies

Tracking #: 3382-4596

Federico Igne
Stefano Germano
Ian Horrocks

Responsible editor: 
Guilin Qi

Submission type: 
Full Paper
Conjunctive Query (CQ) answering is a primary reasoning task over knowledge bases. 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 various 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 OWL2. If the query can be fully answered by one of the tractable services, then that service is used, to ensure maximum performance. Otherwise, the tractable services are used to compute lower and upper bound approximations. The union of the lower bounds and the intersection of the upper bounds are then compared. 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 (role safety acyclic); (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: 


Solicited Reviews:
Click to Expand/Collapse
Review #1
By Xiaowang Zhang submitted on 15/Mar/2023
Major Revision
Review Comment:

This paper presents a hybrid query-answering architecture that combines various services to provide a CQ answering service for OWL. This paper is well-written and well-motivated.
Here are some minor suggestions as follows:
1. In the related work section, a lot of content that needs to be paid attention to is introduced. It is better if the relevant content mentioned in this section can also be suggested in the main text.
2. On the question of interpretability, the answer on page 2 proposes that there is a black box in the framework used in this paper, that is, the process is not interpretable, but the author thinks that the result is interpretable, so the method is interpretable. Shouldn't the process not interpretable mean that the method is not interpretable?
3. Further experiments related to RSAComb and PAGOdA can be carried out. The differences and connections between the two need to be more clearly demonstrated.
4.A more detailed explanation should be provided for OOR batch part. If it is not statistically significant due to the large amount of data and too many types of ontologies, is it possible to take part of it for display and explanation.
5. Is it possible to study more deeply the possible errors in PAGOdA based on what is mentioned in this paper, rather than just using it as a black box?
6. The query size involved in this paper is relatively small, and it is desirable to supplement the relevant data with a slightly larger query size under the premise of ensuring the number of queries.

Review #2
Anonymous submitted on 19/Mar/2023
Review Comment:

The paper presents a hybrid approach for conjunctive query answering over general OWL 2 ontologies. The paper's major contributions are 1) a new and optimised implementation RSAComb of the combined QA approach in RSA, and 2) a hybrid system ACQuA combining RSAComb, PAGOdA, and the OWL 2 reasoner HermiT.

I found the contributions original and significant, and worth publishing at SWJ. The paper is quite well written. In particular, my comments have been addressed satisfactorily in the revision.

The data file provided via Zenodo is well organized with a README file, and I have no particular concerns about the reproducibility of the experiment results.

Review #3
Anonymous submitted on 28/Apr/2023
Review Comment:

The authors have addressed all the issues in my review comments properly. Thanks a lot for the efforts.

Minor issues:

- There is some strange spacing on page 45
- The references part is called "Appendix. References"