=Paper=
{{Paper
|id=Vol-2211/paper-43
|storemode=property
|title=Tractable Query Answering for DL Ontologies and Existential Rules: Extended Abstract
|pdfUrl=https://ceur-ws.org/Vol-2211/paper-43.pdf
|volume=Vol-2211
|authors=David Carral,Irina Dragoste,Markus Krötzsch
|dblpUrl=https://dblp.org/rec/conf/dlog/CarralDK18
}}
==Tractable Query Answering for DL Ontologies and Existential Rules: Extended Abstract==
https://ceur-ws.org/Vol-2211/paper-43.pdf
Tractable Query Answering for Expressive Ontologies
and Existential Rules: Extended Abstract?
David Carral, Irina Dragoste, Markus Krötzsch
Center for Advancing Electronics Dresden (cfaed), TU Dresden, Germany
Answering conjunctive queries (CQs) over knowledge bases (KBs) containing dis-
junctive existential rules is a relevant reasoning task which can be addressed using
the disjunctive chase algorithm—a sound and complete materialisation-based proce-
dure where all relevant consequences are pre-computed, allowing queries to be directly
evaluated over materialised sets of facts—and acyclicity notions [7,8]—sufficient con-
ditions that guarantee termination of this procedure [2]. As shown in [5,6], acyclicity
notions can be used to determine that the chase will indeed terminate over a large subset
of real-world ontologies. Nevertheless, even if a KB is characterised as acyclic, CQ
answering still remains a problem of high theoretical complexity: CQ answering over
acyclic programs with disjunctive existential rules is coN2ExpTime-complete [3]. For
acyclic Horn-SROIQ ontologies, it is ExpTime-complete [6]. Moreover, CQ answering
becomes even harder if we consider non-deterministic ontologies.
Example 1. Let Rn = {Di−1 (x) → ∃yi .Li (x, yi ) ∧ Di (yi ), Di−1 (x) → ∃zi .Ri (x, zi )
∧ Di (zi ) | i = 1, . . . , n} with n ≥ 0. The chase of the program P = hRn, {D0 (c)}i is
exponentially large in n. Note that P is acyclic with respect to all notions described in
[6] and can be expressed in most DL fragments.
We study the limits of tractable reasoning using the chase and propose a series of
restrictions that, if combined, prevent the exponential blow-up highlighted in the previous
example. An important concept for predicting the behaviour of the chase procedure is
the dependency graph of a rule set, defined next. Our definition refers to the skolem
chase, which uses functional terms to denote fresh elements.
Definition 2. Consider a rule set R where (without loss of generality) rules do not share
variables. The dependency graph G(R) of R has the existentially quantified variables
in R as nodes, and an edge y → z if the skolem chase of some program hR, Ii contains
terms of the form fz (t®) and fy (®s), where fz and fy are the skolem functions for z and y,
respectively, and fy (®s) occurs among the terms in t®.
Intuitively, y → z means that a domain element created for the existential variable
y was involved in an application of the rule of z (to instantiate a variable that occurred
in body and head). Let Rn be the rule set from Example 1. Then, G(Rn ) = ∅ if n ≤ 1,
and G(Rn ) = {yi−1 → yi, yi−1 → zi, zi−1 → yi, zi−1 → zi | i = 2, . . . , n} otherwise.
The key to our tractability results is the notion of a braid, which, intuitively speaking,
consists of a possibly large number of intertwined paths.
? The full version of this paper was published at ISWC 2017 [4].
(f, b, w, p)
coNP/P
(f, b, w) (f, b, p)
coNPNP /NP (f, w, p) (b, w, p)
(f, p)
(f, b) (f, w) (b, w) (b, p) (w, p)
coNExpTime/ExpTime coN2ExpTime/2ExpTime
(f) (b) (w) (p)
Fig. 1. Combined complexity of Boolean CQ entailment (non-deterministic/deterministic rules)
with respect to the size of a rule set that satisfies (a) and a combination of (f), (b), (w) and (p)
Definition 3. Consider a directed graph G. A path is a sequence of nodes α1, . . . , αn
with αi → αi+1 ∈ G for all i = 1, . . . , n − 1. The graph G is acyclic if, for every path
α1, . . . , αn with n ≥ 2, α1 , αn . A simple path is a path which does not contain two
occurrences of the same node. A braid is a sequence of nodes α1, . . . , αn such that, for
all i = 1, . . . , n − 1, there are at least two different simple paths from αi to αi+1 .
As our main theoretical contribution, we study the complexity of reasoning over a
rule set R that satisfies some combination of the following restrictions:
(a) The graph G(R) is acyclic.
(f) The arity of all function symbols in sk(R) is at most 1.
(b) The length of the braids in G(R) is bounded.
(w) The treewidth of the rules in R is bounded.
(p) The arity of the predicates in R is bounded.
We summarise our findings in Figure 1, where we assume that the rule set satisfies (a),
as otherwise reasoning becomes undecidable. All the complexity results are tight.
We empirically study the generality of these restrictions using (deterministic and
non-deterministic) real-world ontologies without equality from the MOWL Corp (MC)
[9] and Oxford Ontology Library (OOL) [1]. To do so, we transform the DL ontologies
in these corpora into KBs with disjunctive existential rules, and then check how many of
them satisfy (a-p). Since rule sets resulting from the transformation of normalised DL
ontologies satisfy (f), (w), and (p), we check how many satisfy (a) and (b). We found
that 61.8% (974) of the ontologies from MC and (76%) (171) from OOL satisfy (a).
Moreover, 78.3% of the acyclic ontologies from MC contain braids of length at most 1,
90.8% of length at most 2, 95.5% at most 3, 98.8% at most 4 and 99% at most 5. In the
OOL, 51.4% of the acyclic ontologies feature braids of length at most 1, 69.5% at most
2, 81.2% at most 3, 92.3% at most 4, 97.6 % at most 5, and 98.2 % at most 6. Our work
therefore suggests a new approach to efficient CQ answering that might be applicable to
many real-world ontologies.
Acknowledgements This work was supported by the DFG within the cfaed Cluster of
Excellence, CRC 912 (HAEC), and Emmy Noether grant KR 4381/1-1.
References
1. The oxford ontology library. Available at https://www.cs.ox.ac.uk/isg/ontologies/
2. Bourhis, P., Morak, M., Pieris, A.: The impact of disjunction on query answering under
guarded-based existential rules. In: Proc. 23rd Int. Joint Conf. on Artificial Intelligence (IJ-
CAI’13). pp. 796–802. AAAI Press/IJCAI (2013)
3. Carral, D., Dragoste, I., Krötzsch, M.: Restricted chase (non)termination for existential rules
with disjunctions. In: Sierra, C. (ed.) Proc. 26th Int. Joint Conf. on Artificial Intelligence
(IJCAI’17). pp. 922–928. IJCAI (2017)
4. Carral, D., Dragoste, I., Krötzsch, M.: Tractable query answering for expressive ontologies
and existential rules. In: Proc. 16th Int. Semantic Web Conf. (ISWC’17). LNCS, vol. 10587,
pp. 156–172 (2017)
5. Carral, D., Feier, C., Hitzler, P.: A practical acyclicity notion for query answering over Horn-
SRIQ ontologies. In: The 15th International Semantic Web Conference, Kobe, Japan, 2016,
Proceedings, Part I. LNCS, vol. 9981, pp. 70–85 (2016)
6. Cuenca Grau, B., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.:
Acyclicity notions for existential rules and their application to query answering in ontologies.
J. of Artificial Intelligence Research 47, 741–808 (2013)
7. Krötzsch, M., Rudolph, S.: Extending decidable existential rules by joining acyclicity and
guardedness. In: Proc. 22nd Int. Conf. on Artificial Intelligence (IJCAI’11). pp. 963–968.
IJCAI (2011)
8. Marnette, B.: Generalized schema-mappings: from termination to tractability. In: Paredaens,
J., Su, J. (eds.) Proc. 28th Symposium on Principles of Database Systems (PODS’09). pp.
13–22. ACM (2009)
9. Matentzoglu, N., Bail, S., Parsia, B.: A snapshot of the OWL Web. In: Proc. 12th Int. Semantic
Web Conf. (ISWC’13). LNCS, vol. 8218, pp. 331–346. Springer (2013)