LIPIcs.ICDT.2019.18.pdf
- Filesize: 0.58 MB
- 19 pages
Document
A Single Approach to Decide Chase Termination on Linear Existential Rules
Authors
-
Part of:
Volume:
22nd International Conference on Database Theory (ICDT 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-03-19
File
Document Identifiers
Acknowledgements
We thank the reviewers for their insightful comments, as well as Antoine Amarilli for Example 21, which is simpler than a previous example and shows that the fairness issue already occurs with binary predicates.
Cite AsGet BibTex
Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICDT.2019.18
https://doi.org/10.4230/LIPIcs.ICDT.2019.18
Abstract
Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological knowledge in the context of ontology-based query answering. A knowledge base is then composed of an instance that contains incomplete data and a set of existential rules, and answers to queries are logically entailed from the knowledge base. This brought again to light the fundamental chase tool, and its different variants that have been proposed in the literature. It is well-known that the problem of determining, given a chase variant and a set of existential rules, whether the chase will halt on any instance, is undecidable. Hence, a crucial issue is whether it becomes decidable for known subclasses of existential rules. In this work, we consider linear existential rules with atomic head, a simple yet important subclass of existential rules that generalizes inclusion dependencies. We show the decidability of the all-instance chase termination problem on these rules for three main chase variants, namely semi-oblivious, restricted and core chase. To obtain these results, we introduce a novel approach based on so-called derivation trees and a single notion of forbidden pattern. Besides the theoretical interest of a unified approach and new proofs for the semi-oblivious and core chase variants, we provide the first positive decidability results concerning the termination of the restricted chase, proving that chase termination on linear existential rules with atomic head is decidable for both versions of the problem: Does every chase sequence terminate? Does some chase sequence terminate?
Subject Classification
ACM Subject Classification
- Theory of computation → Logic
- Computing methodologies → Knowledge representation and reasoning
Keywords
- Chase
- Tuple Generating Dependencies
- Existential rules
- Decidability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artif. Intell., 175(9-10):1620-1654, 2011. URL: http://dx.doi.org/10.1016/j.artint.2011.03.002.
- Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Michaël Thomazo. Walking the Complexity Lines for Generalized Guarded Existential Rules. In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 712-717. IJCAI/AAAI, 2011. URL: http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-126.
- Catriel Beeri and Moshe Y. Vardi. The Implication Problem for Data Dependencies. In Shimon Even and Oded Kariv, editors, Automata, Languages and Programming, 8th Colloquium, Acre (Akko), Israel, July 13-17, 1981, Proceedings, volume 115 of Lecture Notes in Computer Science, pages 73-85. Springer, 1981. URL: http://dx.doi.org/10.1007/3-540-10843-2_7.
- Marco Calautti, Georg Gottlob, and Andreas Pieris. Chase Termination for Guarded Existential Rules. In Tova Milo and Diego Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 91-103. ACM, 2015. URL: http://dx.doi.org/10.1145/2745754.2745773.
- Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. Datalog Extensions for Tractable Query Answering over Ontologies. In Roberto De Virgilio, Fausto Giunchiglia, and Letizia Tanca, editors, Semantic Web Information Management - A Model-Based Perspective, pages 249-279. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04329-1_12.
- Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem., 14:57-83, 2012. URL: http://dx.doi.org/10.1016/j.websem.2012.03.001.
- Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. J. Autom. Reasoning, 39(3):385-429, 2007. URL: http://dx.doi.org/10.1007/s10817-007-9078-x.
- David Carral, Irina Dragoste, and Markus Krötzsch. Detecting Chase (Non)Termination for Existential Rules with Disjunctions. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 922-928. ijcai.org, 2017. URL: http://dx.doi.org/10.24963/ijcai.2017/128.
- Alin Deutsch, Alan Nash, and Jeffrey B. Remmel. The chase revisited. In Maurizio Lenzerini and Domenico Lembo, editors, Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, June 9-11, 2008, Vancouver, BC, Canada, pages 149-158. ACM, 2008. URL: http://dx.doi.org/10.1145/1376916.1376938.
- Ronald Fagin. A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst., 6(3):387-415, 1981. URL: http://dx.doi.org/10.1145/319587.319592.
- Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: semantics and query answering. Theor. Comput. Sci., 336(1):89-124, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2004.10.033.
- Tomasz Gogacz and Jerzy Marcinkowski. All-Instances Termination of Chase is Undecidable. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 293-304. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_25.
- Georg Gottlob, Giorgio Orsi, and Andreas Pieris. Query Rewriting and Optimization for Ontological Databases. ACM Trans. Database Syst., 39(3):25:1-25:46, 2014. URL: http://dx.doi.org/10.1145/2638546.
- Gösta Grahne and Adrian Onet. Anatomy of the Chase. Fundam. Inform., 157(3):221-270, 2018. URL: http://dx.doi.org/10.3233/FI-2018-1627.
- Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies. J. Artif. Intell. Res., 47:741-808, 2013. URL: http://dx.doi.org/10.1613/jair.3949.
- Alon Y. Halevy. Answering queries using views: A survey. VLDB J., 10(4):270-294, 2001. URL: http://dx.doi.org/10.1007/s007780100054.
- André Hernich. Computing universal models under guarded TGDs. In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012, pages 222-235. ACM, 2012. URL: http://dx.doi.org/10.1145/2274576.2274600.
- Mélanie König, Michel Leclère, Marie-Laure Mugnier, and Michaël Thomazo. Sound, complete and minimal UCQ-rewriting for existential rules. Semantic Web, 6(5):451-475, 2015. URL: http://dx.doi.org/10.3233/SW-140153.
- Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. CoRR, abs/1602.05828, 2018. URL: http://arxiv.org/abs/1810.02132.
- Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. In Magdalena Ortiz and Thomas Schneider, editors, Proceedings of the 31st International Workshop on Description Logics co-located with 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), Tempe, Arizona, US, October 27th - to - 29th, 2018., volume 2211 of CEUR Workshop Proceedings. CEUR-WS.org, 2018. URL: http://ceur-ws.org/Vol-2211/paper-45.pdf.
- Maurizio Lenzerini. Data Integration: A Theoretical Perspective. In Lucian Popa, Serge Abiteboul, and Phokion G. Kolaitis, editors, Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, Madison, Wisconsin, USA, pages 233-246. ACM, 2002. URL: http://dx.doi.org/10.1145/543613.543644.
- Bruno Marnette. Generalized schema-mappings: from termination to tractability. In Jan Paredaens and Jianwen Su, editors, Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2009, June 19 - July 1, 2009, Providence, Rhode Island, USA, pages 13-22. ACM, 2009. URL: http://dx.doi.org/10.1145/1559795.1559799.
- Marie-Laure Mugnier and Michaël Thomazo. An Introduction to Ontology-Based Query Answering with Existential Rules. In Reasoning Web. Reasoning on the Web in the Big Data Era - 10th International Summer School 2014, Athens, Greece, September 8-13, 2014. Proceedings, pages 245-278, 2014. URL: http://dx.doi.org/10.1007/978-3-319-10587-1_6.
- Dan Olteanu, Jiewen Huang, and Christoph Koch. SPROUT: lazy vs. eager query plans for tuple-independent probabilistic databases. In Yannis E. Ioannidis, Dik Lun Lee, and Raymond T. Ng, editors, Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China, pages 640-651. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/ICDE.2009.123.
- Adrian Onet. The chase procedure and its applications. PhD thesis, Concordia University, Canada, 2012. URL: https://pdfs.semanticscholar.org/6b1b/327a989d3d8e2488f645488063f391391b89.pdf.
- Neil Robertson and Paul D. Seymour. Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7(3):309-322, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90023-4.
- Swan Rocher. Querying Existential Rule Knowledge Bases: Decidability and Complexity. (Interrogation de Bases de Connaissances avec Règles Existentielles : Décidabilité et Complexité). PhD thesis, University of Montpellier, France, 2016. URL: https://tel.archives-ouvertes.fr/tel-01483770.
- Michaël Thomazo. Conjunctive Query Answering Under Existential Rules - Decidability, Complexity, and Algorithms. PhD thesis, Montpellier 2 University, France, 2013. URL: https://tel.archives-ouvertes.fr/tel-00925722.