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)