Conjunctive query answering over unrestricted OWL 2 ontologies

This article presents 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. These techniques led to the development of two new systems: RSAComb and ACQuA, which is the implementation of the proposed hybrid architecture combining RSAComb, PAGOdA, and HermiT. The experiments in this paper show that 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.
However, there are some disadvantages:
1.The article does not demonstrate the discarding of axioms when describing the transition from a general SROIQ ontology to ALCHOIQ. If there are axioms that need to be discarded, will discarding these axioms lead to misinterpretation of the original expression of KB, resulting in errors in subsequent queries?
2.This paper proposes a new hybrid query answering architecture combined with black-box services, which integrates RSAComb, PAGOdA, and HermiT to provide a CQ answering service ACQuA for OWL. Although the system is scalable and efficient, how is the interpretability?
3.The content of the discussion and conclusions part and the introduction part have a lot of repetition, which is somewhat redundant.
4.8.1.1 appears in the text, but there is no 8.1.2. The title layout is not very reasonable.
5.Is there a relevant reason for the inability to reproduce the results of UOBM with PAGOdA?
6.The related experiments of RSAComb and PAGOdA can be further carried out. ACQuA includes PAGOdA. Is there any unfairness in comparing ACQuA with PAGOdA only?

The authors introduce a hybrid approach for conjunctive query (CQ) answering over general OWL 2 ontologies. The hybrid approach computes an upper bound and a lower bound for the query answers by approximating the ontology into tractable fragments, which allows an efficient query engine to be deployed for computing those bounds. Then, only the answers falling in the gap between the two bounds need to be verified with a full-fledged OWL 2 reasoner. Such a hybrid approach allows expressive ontologies to be handled efficiently as the number of answers falling in the gap is often small in practice.

Existing hybrid query answering (QA) system PAGOdA approximate ontologies into the OWL 2 RL profile and use a Datalog reasoner to compute the upper and lower bounds. Yet the number of "gap" answers may still be high and the frequent use of OWL 2 reasoner introduces expensive computation. Following a similar approach, the authors propose to approximate ontologies into the role safety acyclic (RSA) fragment, a recently proposed tractable fragment that covers all the OWL 2 profiles. More specifically, RSA is a fragment of Horn-ALCHOIQ obtained by restricting the interactions of axioms to avoid exponential or infinite canonical models. A combined approach for QA in RSA has been developed.

The major contributions of the paper 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. The most novel parts in my opinion are the ontology approximations to RSA and RSA+ fragments for the computation of lower and upper bounds. While the technical details may not be too involved, they are well developed and presented with detailed proofs. A comprehensive evaluation has been conducted which demonstrates the effectiveness of the approach in practical datasets.

The paper is well written, with technical details presented in a rather clear and self-contained manner. I enjoyed reading the technical background in Sections 2.2-2.3 and the discussions of related work in Section 7. Yet due to the wide range of reasoning techniques involved, it would be useful to summarise some intuition behind the techniques through for instance diagrams or tables. For example,
- It would be useful to show a high-level comparison between the combined and hybrid QA approaches; in particular, if there is any common intuition behind their model approximations. While hybrid QA methods approximate ontologies, they essentially approximate (canonical) models.
- Similarly, it would be helpful to summarise and compare the approximations between PAGOdA and the proposed approach. In particular, how is the use of b^A_{R,B} in Equation (22) different from PAGOdA?
- The running example is quite helpful for understanding the technical details, and to help readers to keep track of the examples throughout the paper, some visual illustration, e.g., diagrams, of the examples would be desirable.

The experiment results look convincing but it is pity that the original implementation of the combined QA in RSA is not available, as a comparison with which would largely strengthen the contribution of RSAComb. The following details may be worth some further explanation.
- Figure 7 shows the approximation to RSA increases with the data size. It would be useful to discuss which part of the approximation method is affected by the data sizes. Also, are the approximation sizes impacted by the data sizes?
- In the discussion of Figure 9, it is not quite clear to me what "less than 0.1%" refers to. Some comments on this observation would be desired.
- Figure 11b uses an estimate of PAGOdA's performance. It is unclear how the estimate is obtained.
Finally, some errors in PAGOdA's results are observed, which is quite interesting. As ACQuA integrates PAGOdA as its component, it is worth discussing whether the errors in PAGOdA affect the correctness of ACQuA.

Some detailed comments are as follows:
- p1, l25, RSA should be briefly introduced or at least have its full name provided when it is first mentioned in the Abstract.

- p4, l27, \pi(K)^{\approx,top}

- p6, l48, (T3) and (R1)

- The notations O and K can sometimes be slightly confusing (while not incorrect), e.g., p7 l49 and p8 l1.

- p8, some intuition behind Definition 2.3 would be desirable.

- p9, l49, what is P_{O,q}? or should it be P_{q,K}?

- p12, l25, the relation between RSAComb and ACQuA is not very clear till Section 6.

- p14, l14, it is unclear to me why D is not unique.

- Some comments on the sizes of the lower and upper approximations would be useful.

- p16, l46, the discussion of upper bound computation starts from ALCHOIQ+. Why it does not start from SROIQ? Maybe I missed something important here.

- p17, l24, the discussion on the distance between disjuncts and \bot_f in the dependency graph may worth some elaboration.

- p29, l46, "w.r.t. to"

The paper deals with conjunctive queries with OWL ontologies. Specifically, it combines some techniques for efficiently computing the upper and lower bounds of query answers, and use a full-fledged reasoner if there is a gap between the bounds. The approach has been implemented in the open-source systems RSAComb and ACQuA. Experiments show that the system outperforms the PAGOdA system.

The paper has an overall clear structure. The general idea is not difficult to follow. The notation is a little bit heavy, but I don't see this can be easily avoided. Still, the presentation can be improved (see the details below).

One major issue of the paper is that the contributions should be better explained. Due to the nature of the paper combining many existing techniques, the authors should be more explicit about the novelty of the paper. In particular, the introduction should do a better job of explaining the novelty. Is this "just" an improved version of PAGOdA? How novel is the system RSAComb? Did RSAComb use more techniques than [14, 15]? Are there already some results published as workshop/conference papers? If so, what is the difference with respect to them? All efforts in this direction would greatly help readers understand the novelty of this paper.

More detailed comments:

- In Section 2, all the definitions are without references, but the Theorems are always with references. This causes some confusion. Are there some new definitions introduced in this paper? Or are they all from existing literature? This needs to be clarified

- p4. Table 1.
- Technically, R^- is not an axiom.
- In the translation of axiom T1, V_{i=1}^n Bi(x). n should be m

- p4 l27. What are the "bottom and equality axiomatization rules"?

- p4 l28. What is "\Pi_K"? This seems to be undefined.

- Example 2.1. What is the purpose of this example? Could you explain what is the source of the exponential size of the model? Is R unsafe under Definition 2.1?

Theorem 2.5. How about RSA+?

- p8 l18. "oriented forest" has not been introduced before

- p8 l19. this place introduces RSA+, and it says RSA+ is an extension of RSA. Is RSA+ is a new language introduced in this paper? If I understood correctly, RSA+ is a sub-language of RSA. It is strange to call a sub-language as an extension.

- Definition 2.4.
- What does "confl" stand for? conflict?
- Let **prec** be ... -> \prec

- p10. Theorem 2.5. Do you have results about RSA+?

- Example 3.1.
- It would be very useful to provide some CQs together with the KB. Otherwise, this "Overview" section seems to be incomplete.

- p20. Footnote 12. The link does not point to the right fragment of the page

- Sec 8. Experiments. In general, I feel that the experiments should show distinguish better the **approach** of PAGOdA/RSAComb/ACQuA and the **implementation** of these systems. In several cases, the issues observed from the experiments with PAGOdA are not clear from the approach (limitation of the theory/methodology) or the implementation (e.g. bugs in the system).

- The authors may repeat here the experiments using CQ under certain answer semantics using the SPARQL syntax.

- UOBM: "We could not perform a direct comparison with UOBM since we were unable to reproduce the PAGOdA’s results [12]." -> this should be elaborated. E.g., Do you mean PAGOdA throws exceptions, timeouts, or returns wrong answers?

- Reactome: What happened with other queries other than query 65?

- In the paper, the authors claim that PAGODA and RSAComb are not comparable. Did you observe any case that PAGOdA performs better, which could be beyond the experiments described in the paper?

- 8.3. OOR batch. This batch is a large collection of data sets. The paper should provide more statistics in this part of the evaluation. For example, provide some values of L/U/T similar to Figure 12, but aggregated. This can lead to better insight.

- "PAGOdA was able to process 103 out of 126 ontologies considered", what happened with the ontologies that could not be processed? What are the issues here?

- "We were able to fix the issue in ACQuA". This is a bug?

- The queries are very simple, in terms of conjunctive queries. Most of the queries have a small number of atoms and very small number of existential variables. Can the authors comment on this?

- p37 l32. The last semicolon ";" should be period "."