David Carral[0000 0001 7287 4709] and Markus Krotzsch[0000 0002 9172 2601] Among the many approaches towards e cient reasoning in description logics (DLs), consequence-preserving translations of DL theories into rule languages are among the most prominent. Table 1 gives an overview of works in this area. The natural strength of rule reasoners is their good scalability towards large sets of facts. Indeed, all of the rewritings in Table 1 are independent of the given facts (ABox), which can be used unchanged for reasoning with the rule-based theory. In general, we can describe this idea of rewriting as follows: De nition 1. Consider fragments L1 and L2 of rst-order logic that include ground facts. An L2-theory T2 is a fact-entailment preserving rewriting (or simply rewriting in our context) of an L1-theory T1 if, for every set F of ground facts and every ground fact ' over the signature of T1, we have T1; F j= ' i T2; F j= '. If such a rewriting can always be computed, then L1 is (e ectively, fact-entailment preserving) rewritable to L2.
sizes (and especially predicate arities). The last two lines in Table 1 are rewritings that use constant rule sets and rewrite TBoxes to facts in (sub)polynomial time. This works for E L++ due to its P-complexity, and for Horn-ALC due to the high expressive power of Datalog9 theories, even when these are constant.
Given this rich body of
research in rule rewritings, Work Source Target Size
there is a surprising
shortage of rewriting-based reason- [
A possible explanation is Table 1. From DLs to rule languages, where
that known rewritings still suf- Datalog_ and Datalog9 denote Datalog extended
fer from many shortcomings. with disjunctions and existential quanti ers
Indeed, exponentially large rule
sets (Table 1, lines 1{7) and rule sizes in the order of the ontology (lines 8{9) both
impair practical performance, whereas static rewritings (lines 10{11) are often
better implemented in dedicated \consequence-based" reasoners rather than
relying on general-purpose rule reasoners [
In our work [
Finally, we also consider Horn-ALCHIQ, the disjunction-free fragment of ALCHIQ. Whereas our rewriting of ALCHIQ to Datalog_ and Datalog_9, respectively, could be applied here, it produces rule sets that always contain disjunctions. We therefore combine several known results to obtain alternative, disjunction-free rewritings for this case.
The details of our rule-based rewritings are published at the 29th
International Joint Conference on Arti cial Intelligence (IJCAI 2020) [
Rewriting ALCHIQ to Disjunctive Existential Rules (Extended Abstract)