1. S. Ahmetaj, M. Ortiz, and M. Simkus. Polynomial datalog rewritings for expressive description logics with closed predicates. In IJCAI 2016, pages 878{885, 2016. 2. M. Bienvenu, B. ten Cate, C. Lutz, and F. Wolter. Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. TODS, 39(4):33:1{44, 2014. 3. U. Hustadt, B. Motik, and U. Sattler. Reasoning in description logics by a reduction to disjunctive datalog. J. Autom. Reasoning, 39(3):351{384, 2007.
Reasoning in expressive Description Logics (DLs) that contain ALC is challenging, partly because they do not enjoy the useful universal model property of their Horn counterparts. There are e cient state-of-the-art reasoners for standard reasoning tasks, but they are still lacking for other tasks that do not reduce easily to satis ability. For instance, for query answering, there are a few algorithms for computing (data-independent) Datalog rewritings. They take as an input a query and a TBox, and compile them into a Datalog query that can be evaluated over di erent ABoxes, e.g., [3, 2, 1]. Query rewriting is often considered the most promising approach to achieve scalable query answering beyond plain instance queries. However, most of the Datalog rewritings proposed so far for expressive DLs, especially those for answering conjunctive queries, are for theoretical purposes (e.g., for showing complexity bounds), and aren't amenable to implementation. Implicitly, this is due to the fact that they embed a representation of all relevant models of the TBox, for any input ABox.
In this work we aim at nding a middle ground between data-independence and practicability, one the assumption that real datasets are not arbitrary, but only use a limited number of local con gurations of concepts that we call pro les. We propose a goal-oriented algorithm to compute, from a given set of pro les, the local con gurations of concepts (known as types) that occur in the set of all the models that are relevant for query answering, for any ABox that uses only the initial pro les. With these types we build a disjunctive Datalog program (with negation) that yields the correct answer to any instance query. The rewriting does not depend on a concrete ABox, but only on the pro les. The experiments carried out with a prototype implementation of our technique yielded promising results. We observed that, over a large range of ontologies, ABoxes use only a moderate set of pro les. The type computation is feasible, even for large ontologies; the computed Datalog rewriting is of moderate size, and its execution is e cient. An extension to conjunctive queries is being developed. We hope this work may inspire more exploration of the `middle ground' between data-independent and data-centric reasoning, and bring us closer to sound and complete query answering engines for expressive DLs.