=Paper=
{{Paper
|id=Vol-1879/paper58
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1879/paper58.pdf
|volume=Vol-1879
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-1879/paper58.pdf</pdf>
<pre>
  Answering Conjunctive Queries for Expressive
        DLs with the Restricted Chase

              David Carral, Irina Dragoste, and Markus Krötzsch

     Center for Advancing Electronics Dresden (cfaed), TU Dresden, Germany

    The restricted chase is a sound and complete algorithm that solves conjunc-
tive query answering over expressive, non-deterministic DL ontologies. The al-
gorithm branches on disjunctive choices and computes all the possible inferences
that have not already been satisfied, risking non-termination.
    For this reason, we develop new acyclicity conditions[1] that guarantee re-
stricted chase termination of a TBox over any ABox, by extending known
acyclicity notions to the restricted disjunctive case. We put forward restricted
joint acyclicity and the more general restricted model-summarizing acyclicity
(RMSA), both of which can be checked in polynomial time. An even more general
notion is restricted model-faithful acyclicity (RMFA), but checking membership
of a DL ontology is ExpTime-complete. Moreover, we show that the complexity
of query answering over acyclic ontologies is coN2ExpTime-complete.
    Acyclicity conditions are sufficient, but not necessary for termination. Thus,
we introduce the first cyclicity notion for non-termination of the oblivious and
the restricted chase, which imply that there exists some ABox for which some
chase tree would be infinite. Checking this condition is 2ExpTime-complete.
    We conducted experiments on a large corpus of real-world ontologies to eval-
uate the empirical generality of our notions. Indeed, our acyclicity notions im-
prove the generality of existing ones by 4.2% for deterministic ontologies and
9.2% for non-deterministic ones, with RMSA significantly improving over MSA.
Moreover, combining cyclicity and acylicity notions allows us to decide restricted
chase termination of 96.3% ontologies in the deterministic case (from 72.4% using
only MFA) and 42.4% in the non-deterministic one (from 25.2% with MFA), re-
spectively. The high percentage of unclassified ontologies in the non-deterministic
case can be explained by the loose approximation of disjunctive axioms conse-
quences when determining facts necessarily entailed during the chase.
    We present the first systematic study about termination of the restricted
chase on expressive, non-deterministic ontologies in which we characterize ter-
mination for a larger subset of real-world ontologies than in previous works.
Moreover, we present a cyclicity notion that allows us to establish chase non-
termination, thus assessing the space for improvement of acyclicity notions.
    Our work also motivates and enables further research on efficient chase-based
reasoning procedures for expressive, non-deterministic ontologies. Many tableau-
based OWL reasoners already implement chase-like algorithms. We believe this
is a highly promising direction in description logics and existential rules alike.
1. Carral, D., Dragoste, I., Krötzsch, M.: Restricted chase (non)termination for ex-
   istential rules with disjunctions. In: Proceedings of IJCAI , Melbourne, Australia
   (2017), to appear (https://iccl.inf.tu-dresden.de/web/Inproceedings3140)

</pre>