=Paper=
{{Paper
|id=Vol-2373/paper-41
|storemode=property
|title=From Horn-SRIQ to Datalog: A Data-Independent Transformation that Preserves Assertion Entailment
|pdfUrl=https://ceur-ws.org/Vol-2373/paper-41.pdf
|volume=Vol-2373
|authors=David Carral,Larry González,Patrick Koopmann
|dblpUrl=https://dblp.org/rec/conf/dlog/CarralGK19
}}
==From Horn-SRIQ to Datalog: A Data-Independent Transformation that Preserves Assertion Entailment==
https://ceur-ws.org/Vol-2373/paper-41.pdf
From Horn-SRIQ to Datalog:
A Data-Independent Transformation that
Preserves Assertion Entailment?
David Carral1 , Larry González1 , and Patrick Koopmann1,2
1
Knowledge-Based Systems Group, TU Dresden, Dresden, Germany
2
Institute for Theoretical Computer Science TU Dresden, Germany
Assertion retrieval (AR)—i.e., the task of inferring all implicit assertions from
a Description Logics (DL) knowledge base (KB)—is an important reasoning task
with many applications in knowledge representation and data management. To
access data efficiently, one approach is to rewrite the ontology into Datalog,
and then use powerful Datalog engines to compute implicit entailments. Exist-
ing rewriting techniques support DL languages from ELH to Horn-SHIQ [3].
We present the first such transformation for Horn-SRIQu , an expressive DL
that allows for the use of the role chain constructor. Furthermore, we show
that the resulting method for assertion retrieval is worst-case optimal for ELH,
Horn-SHIQ, and Horn-SRIQu . We empirically show that the use of Datalog
rewritings can outperform state-of-the-art reasoners and that we can construct
rewritings of moderate sizes for many real-world ontologies.
To give a formal intuition about our approach, our method computes an
AR-rewriting in the following sense.
Definition 1. Let O = hT , Ai be a Horn-SRIQu KB. A Datalog rule set RT
is an AR-rewriting for T iff, for every ABox A and assertion α defined over
the signature of T , hT , Ai and hRT , Ai are equi-satisfiable and hT , Ai |= α iff
KO = hRT , Ai |= α.
A well-known way of characterising entailments from KBs is the chase [2].
An alternative characterisation of Definition 1 is that RT is an AR-rewriting of
∞
O if the chase of KO (denoted with KO ) coincides with the chase of O (denoted
with O∞ ) on all assertions over the signature of T . The challenge in constructing
Datalog AR-rewritings is that facts in O∞ may contain an unbounded amount
of nulls (i.e., “unnamed” terms that are introduced to satisfy existential restric-
tions), whereas Datalog rules can only derive facts containing a fixed amount of
∞
constants. To replicate assertion entailments in KO , we encode the relevant in-
formation about the null successors of an individual in O∞ by introducing fresh
concepts and roles. Here, we benefit from a well-known automata technique [4,5]
to trace the paths of complex roles in the chase.
To ascertain when information about one of these fresh predicates needs to
be used in KO , we make use of the calculus from [3], which is also used to infer
?
The full paper will be published in the proceedings of the 33rd AAAI Conference on
Artificial Intelligence (AAAI’19) [1].
2 David Carral, Larry González, and Patrick Koopmann
103 Reactome 103 Uniprot 105
102 102
103
101 101
101
0 0
10 10
2.8M 5.1M 6.7M 8.1M 9M 17.8M 26.2M 33.9M
Fig. 1. On the left: time in seconds for RDFox (dark) and Konclude (bright), each over
four ABoxes with increasing numbers of assertions. On the right, Size of TBoxes and
their rewritings.
axioms relevant to our Datalog program. Since this calculus was originally de-
signed for Horn-SHIQ, we first need to extend our input TBox T to a TBox T+
in which the behaviour of complex role inclusion axioms is sufficiently simulated.
To show practical feasibility of our approach, we implemented a prototype
and performed two different experiments. We first compared the performance
of solving AR using our Datalog rewritings versus using the DL reasoner Kon-
clude [8]. We considered two real-world, data-intensive ontologies from the bi-
ological domain, Reactome and Uniprot [9] which we normalised and enriched
with 3 and 5 complex role inclusion axioms, respectively. The resulting TBoxes
contain 485 and 304 axioms. The rewritten Datalog programs contain 539 and
367 rules, and were computed in 221 and 182 seconds. For each ontology, we con-
sidered ABoxes of various sizes, generated by sampling the real-world ABoxes
using the method by Zhou et al. [9]. We use RDFox [6] as Datalog engine for
computing the chase of our rewritings, and compare its performance with that
of Konclude. Figure 1 shows the wall-clock times measured in this experiment,
ignoring the time used for parsing and loading, in logarithmic scale.
In our second experiment, we computed rewritings for 121 selected TBoxes
from MOWLCorp [7]. Figure 1 shows the number of axioms of the input ontolo-
gies (blue bars) and the number of rules of the Datalog rewritings (red bars).
For some ontologies, the rewritings got substantially larger. This was expected,
and in theory unavoidable, due to the double exponential time complexity of
assertion entailment in Horn-SRIQu : for Datalog, this complexity is only poly-
nomial (since predicate arity is bounded), which is why our rewritings are in
the worst case double exponential in the size of the input. Our evaluation con-
firms that these blow-ups are not only of theoretical nature, but may actually
happen for some real-world ontologies. However, in most cases, the size of the
computed Datalog rule sets was still of comparable dimensions: in 59% of cases,
the increase was at most by 100%, and in 74% of cases, it was at most by 200%.
Acknolwedgements. The first two authors are funded by Deutsche Forschungs-
gemeinschaft in project number 389792660 (TRR 248, Center for Perspicuous
Systems) and Emmy Noether grant KR 4381/1-1 (DIAMOND). The third au-
thor is funded by DFG in the CRC 912 (HAEC).
From Horn-SRIQ to Datalog: Extended Abstract 3
References
1. Carral, D., González, L., Koopmann, P.: From Horn-SRIQ to datalog: A data-
independent transformation that preserves assertion entailment. In: Proceedings of
the 33rd Conference on Artificial Intelligence (AAAI 2019) (January 2019)
2. Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: Proc. PODS’ 08.
ACM SIGMOD-SIGACT-SIGART. ACM (2008)
3. Eiter, T., Ortiz, M., Šimkus, M., Tran, T., Xiao, G.: Query rewriting for Horn-
SHIQ plus rules. In: Proc. AAAI’12. AAAI Press (2012)
4. Horrocks, I., Kutz, O., Sattler, U.: The irresistible SRIQ. In: Proc. OWLED’05.
CEUR Workshop Proceedings, vol. 188. CEUR-WS.org (2006)
5. Kazakov, Y.: An extension of complex role inclusion axioms in the description logic
SROIQ. In: Proc. IJCAR’10. Lecture Notes in Computer Science, vol. 6173, pp.
472–486. Springer (2010)
6. Motik, B., Nenov, Y., Piro, R., Horrocks, I., Olteanu, D.: Parallel materialisation of
Datalog programs in centralised, main-memory RDF systems. In: Proc. AAAI’14.
pp. 129–137. AAAI Press (2014)
7. Parsia, B., Matentzoglu, N., Gonçalves, R.S., Glimm, B., Steigmiller, A.: The OWL
reasoner evaluation (ORE) 2015 competition report. J. of Autom. Reasoning 59(4),
455–482 (2017)
8. Steigmiller, A., Liebig, T., Glimm, B.: Konclude: System description. J. of Web
Semantics 27, 78–85 (2014)
9. Zhou, Y., Cuenca Grau, B., Nenov, Y., Kaminski, M., Horrocks, I.: PAGOdA: Pay-
as-you-go ontology query answering using a Datalog reasoner. J. of Artif. Intell. Res.
54, 309–367 (2015)