Goal-oriented Type-based Reasoning
                   for Expressive DLs?

            Labinot Bajraktari, Magdalena Ortiz, and Mantas Šimkus

                                  TU Wien, Austria
    Reasoning in expressive Description Logics (DLs) that contain ALC is chal-
lenging, partly because they do not enjoy the useful universal model property of
their Horn counterparts. There are efficient state-of-the-art reasoners for stan-
dard reasoning tasks, but they are still lacking for other tasks that do not reduce
easily to satisfiability. For instance, for query answering, there are a few algo-
rithms 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 different ABoxes, e.g., [3, 2, 1]. Query rewriting is often consid-
ered 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 repre-
sentation of all relevant models of the TBox, for any input ABox.
    In this work we aim at finding 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 configurations of concepts that we call profiles.
We propose a goal-oriented algorithm to compute, from a given set of profiles,
the local configurations 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 profiles. With these types we build a disjunctive Datalog pro-
gram (with negation) that yields the correct answer to any instance query. The
rewriting does not depend on a concrete ABox, but only on the profiles. The ex-
periments 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 profiles. The type computation is feasible, even for
large ontologies; the computed Datalog rewriting is of moderate size, and its
execution is efficient. 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.
1. S. Ahmetaj, M. Ortiz, and M. Šimkus. 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.

?
    Supported by the Austrian Science Funds (FWF) projects P25207, P25518, W1255.