Tractable Query Answering for Expressive Ontologies and Existential Rules: Extended Abstract?

Abstract

Answering conjunctive queries (CQs) over knowledge bases (KBs) containing disjunctive existential rules is a relevant reasoning task which can be addressed using the disjunctive chase algorithm-a sound and complete materialisation-based procedure where all relevant consequences are pre-computed, allowing queries to be directly evaluated over materialised sets of facts-and acyclicity notions [7,8]-sufficient conditions 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-S ROIQ ontologies, it is ExpTime-complete [6]. Moreover, CQ answering becomes even harder if we consider non-deterministic ontologies. Example 1. Let Rn = fDi 1¹xº ! 9yi :Li ¹x; yi º ^ Di ¹yi º; Di 1¹xº ! 9zi :Ri ¹x; zi º ^ Di ¹zi º j i = 1; : : : ; ng with n 0. The chase of the program P = hRn; fD0¹cºgi 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.

-

(f, b, w, p) coNP/P (f, b, w)

(f, b, p) coNPNPNP

(f, w, p) (f, p)

(b, w, p) (f, b) (f, w) (b, w) (b, p) (w, p) coNExpTime/ExpTime

coN2ExpTime/2ExpTime (f) (b) (w) (p) Definition 3. Consider a directed graph G. A path is a sequence of nodes 1; : : : ; n with i ! i+1 2 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 (IJCAI'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 HornSRIQ 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 )