Hostname: page-component-7b7567c8c-kwt9d Total loading time: 0 Render date: 2026-11-13T22:11:48.757Z Has data issue: false hasContentIssue false
  • English
  • Français

Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation

Published online by Cambridge University Press:  30 June 2020

ARASH KARIMIOpen the ORCID record for ARASH KARIMI[Opens in a new window],
HENG ZHANG and
JIA-HUAI YOU
ARASH KARIMI
Affiliation:
Department of Computing Science, University of Alberta, Edmonton, Canada, (e-mail: akarimi@ualberta.ca)
HENG ZHANG
Affiliation:
College of Intelligence and Computing, Tianjin University, Tianjin, China, (e-mail: h.zhang@hotmail.com)
JIA-HUAI YOU
Affiliation:
Department of Computing Science, University of Alberta, Edmonton, Canada, (e-mail: jyou@ualberta.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The chase procedure for existential rules is an indispensable tool for several database applications, where its termination guarantees the decidability of these tasks. Most previous studies have focused on the skolem chase variant and its termination analysis. It is known that the restricted chase variant is a more powerful tool in termination analysis provided a database is given. But all-instance termination presents a challenge since the critical database and similar techniques do not work. In this paper, we develop a novel technique to characterize the activeness of all possible cycles of a certain length for the restricted chase, which leads to the formulation of a framework of parameterized classes of the finite restricted chase, called $k$-$\mathsf{safe}(\Phi)$ rule sets. This approach applies to any class of finite skolem chase identified with a condition of acyclicity. More generally, we show that the approach can be applied to the hierarchy of bounded rule sets previously only defined for the skolem chase. Experiments on a collection of ontologies from the web show the applicability of the proposed methods on real-world ontologies.

Keywords

existential rulesontological reasoningtermination analysiscomplexity of reasoning

References

Abiteboul, S., Hull, R. and Vianu, V. 1995. Foundations of Databases: The Logical Level. Addison-Wesley Longman Publishing Co., Inc.Google Scholar
Baget, J.-F. 2004. Improving the forward chaining algorithm for conceptual graphs rules. In Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press, 407–414.Google Scholar
Baget, J.-F., Garreau, F., Mugnier, M.-L. and Rocher, S. 2014a. Extending acyclicity notions for existential rules. In Proceedings of the 21st European Conference on Artificial Intelligence. IOS Press, 39–44.Google Scholar
Baget, J.-F., Garreau, F., Mugnier, M.-L. and Rocher, S. 2014b. Revisiting chase termination for existential rules and their extension to nonmonotonic negation. In Proceedings of the 15th International Workshop on Non-Monotonic Reasoning (NMR 2014).Google Scholar
Baget, J.-F., Gutierrez, A., Leclere, M., Mugnier, M.-L., Rocher, S. and Sipieter, C. 2015. Datalog+, RuleML and OWL 2: Formats and translations for existential rules. In Proceedings of the RuleML 2015 Challenge (Challenge+ DC@ RuleML). CEUR Workshop Proceedings, vol. 1417. CEUR-WS.org.Google Scholar
Baget, J.-F., Leclère, M., Mugnier, M.-L., Rocher, S. and Sipieter, C. 2015. Graal: A toolkit for query answering with existential rules. In Proceedings of the International Symposium on Rules and Rule Markup Languages for the Semantic Web. LNCS, vol. 9202. Springer, 328–344.Google Scholar
Baget, J.-F., Leclère, M., Mugnier, M.-L. and Salvat, E. 2009. Extending decidable cases for rules with existential variables. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, 677–682.Google Scholar
Baget, J.-F., Leclère, M., Mugnier, M.-L. and Salvat, E. 2011. On rules with existential variables: Walking the decidability line. Artificial Intelligence 175, 9, 1620–1654.CrossRefGoogle Scholar
Beeri, C. and Vardi, M. Y. 1981. The implication problem for data dependencies. In Proceedings of the 8th International Colloquium on Automata, Languages, and Programming. LNCS, vol. 115. Springer, 73–85.Google Scholar
Beeri, C. and Vardi, M. Y. 1984. A proof procedure for data dependencies. Journal of the ACM 31, 4, 718–741.CrossRefGoogle Scholar
Benedikt, M., Konstantinidis, G., Mecca, G., Motik, B., Papotti, P., Santoro, D. and Tsamoura, E. 2017. Benchmarking the chase. In Proceedings of the 36th ACM Symposium on Principles of Database Systems. ACM, 37–52.Google Scholar
Bourhis, P., Manna, M., Morak, M. and Pieris, A. 2016. Guarded-based disjunctive tuple-generating dependencies. ACM Transactions on Database Systems 41, 4, 27:1–27:45.Google Scholar
Calautti, M., Gottlob, G. and Pieris, A. 2015. Chase termination for guarded existential rules. In Proceedings of the 34th ACM Symposium on Principles of Database Systems. ACM, 91–103.Google Scholar
Calautti, M. and Pieris, A. 2019. Oblivious chase termination: The sticky case. In Proceedings of the Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17:1–17:18.Google Scholar
Cali, A., Gottlob, G., Lukasiewicz, T., Marnette, B. and Pieris, A. 2010. Datalog+/-: A family of logical knowledge representation and query languages for new applications. In Proceedings of the Twenty-Fifth Annual IEEE Symposium on Logic in Computer Science. IEEE, 228–242.Google Scholar
Carral, D., Dragoste, I., González, L., Jacobs, C., Krötzsch, M. and Urbani, J. 2019. Vlog: A rule engine for knowledge graphs. In Proceedings of the16th International Semantic Web Conference. LNCS, vol. 11779. Springer, 19–35.Google Scholar
Carral, D., Dragoste, I. and Krötzsch, M. 2017. Restricted chase (non) termination for existential rules with disjunctions. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. ijcai.org, 922–928.Google Scholar
Carral, D., Feier, C., Grau, B. C., Hitzler, P. and Horrocks, I. 2014. EL-ifying ontologies. In Proceedings of the7th International Joint Conference on Automated Reasoning. LNCS, vol. 8562. Springer, 464–479.Google Scholar
Cuenca Grau, B., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B. and Wang, Z. 2013. Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research 47, 741–808.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374–425.CrossRefGoogle Scholar
Delivorias, S., Leclère, M., Mugnier, M.-L. and Ulliana, F. 2018. On the k-boundedness for existential rules. In Proceedings of the 2nd International Joint Conference on Rules and Reasoning. LNCS, vol. 11092. Springer, 48–64.Google Scholar
Deutsch, A., Nash, A. and Remmel, J. 2008. The chase revisited. In Proceedings of the Twenty-Seventh ACM Symposium on Principles of Database Systems. ACM, 149–158.Google Scholar
Fagin, R., Kolaitis, P. G., Miller, R. J. and Popa, L. 2003. Data exchange: Semantics and query answering. In Proceedings of the 9th International Conference on Database Theory. LNCS, vol. 2572. Springer, 207–224.Google Scholar
Fagin, R., Kolaitis, P. G., Miller, R. J. and Popa, L. 2005. Data exchange: Semantics and query answering. Theoretical Computer Science 336, 1, 89–124.CrossRefGoogle Scholar
Gogacz, T., Marcinkowski, J. and Pieris, A. 2019. All-instances restricted chase termination: The guarded case. arXiv preprint arXiv:1901.03897.CrossRefGoogle Scholar
Grahne, G. and Onet, A. 2018. Anatomy of the chase. Fundamenta Informaticae 157, 3, 221–270.CrossRefGoogle Scholar
Grau, B. C., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B. and Wang, Z. 2013. Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research 47, 741–808.Google Scholar
Hell, P. and Nešetřil, J. 1992. The core of a graph. Discrete Mathematics 109, 1-3, 117–126.CrossRefGoogle Scholar
Hillebrand, G. G., Kanellakis, P. C., Mairson, H. G. and Vardi, M. Y. 1995. Undecidable boundedness problems for datalog programs. Journal of Logic Programming 25, 2, 163–190.CrossRefGoogle Scholar
Horridge, M. and Bechhofer, S. 2011. The OWL API: A java API for OWL ontologies. Semantic Web 2, 1, 11–21.CrossRefGoogle Scholar
Immerman, N. 1988. Nondeterministic space is closed under complementation. SIAM Journal on Computing 17, 5, 935–938.CrossRefGoogle Scholar
Karimi, A., Zhang, H. and You, J.-H. 2018. Restricted chase termination: A hierarchical approach and experimentation. In Proceedings of the 2nd International Joint Conference on Rules and Reasoning. LNCS, vol. 11092. Springer, 98–114.Google Scholar
Krötzsch, M., Marx, M. and Rudolph, S. 2019. The power of the terminating chase. In Proceedings of the Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 3:1–3:17.Google Scholar
Krötzsch, M. and Rudolph, S. 2011. Extending decidable existential rules by joining acyclicity and guardedness. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. IJCAI/AAAI, 963–968.Google Scholar
Leclère, M., Mugnier, M.-L., Thomazo, M. and Ulliana, F. 2019. A single approach to decide chase termination on linear existential rules. In Proceedings of Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 18:1–18:19.Google Scholar
Marcinkowski, J. 1999. Achilles, turtle, and undecidable boundedness problems for small datalog programs. SIAM Journal on Computing 29, 1, 231–257.CrossRefGoogle Scholar
Marnette, B. 2009. Generalized schema-mappings: from termination to tractability. In Proceedings of the Twenty-Eighth ACM Symposium on Principles of Database Systems. ACM, 13–22.Google Scholar
Matentzoglu, N. and Parsia, B. 2014. The Manchester OWL Corpus (MOWLCorp), original serialisation.Google Scholar
Onet, A. 2013. The chase procedure and its applications in data exchange. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, vol. 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1–37.Google Scholar
Rutenburg, V. 1986. Complexity of generalized graph coloring. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science. LNCS, vol. 233. Springer, 573–581.Google Scholar
Savitch, W. J. 1970. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4, 2, 177–192.CrossRefGoogle Scholar
Zhang, H., Zhang, Y. and You, J.-H. 2015. Existential rule languages with finite chase: Complexity and expressiveness. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, 1678–1685.Google Scholar