Document Open Access Logo

Oblivious Chase Termination: The Sticky Case

Authors Marco Calautti, Andreas Pieris

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2019.17.pdf
  • Filesize: 0.57 MB
  • 18 pages

Document Identifiers

Author Details

Marco Calautti
  • School of Informatics, University of Edinburgh, UK
Andreas Pieris
  • School of Informatics, University of Edinburgh, UK

Funding

Calautti and Pieris are funded by the EPSRC grant EP/S003800/1 "EQUID", and the EPSRC programme grant EP/M025268/ "VADA".

Cite AsGet BibTex

Marco Calautti and Andreas Pieris. Oblivious Chase Termination: The Sticky Case. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICDT.2019.17

Abstract

The chase procedure is one of the most fundamental algorithmic tools in database theory. A key algorithmic task is uniform chase termination, i.e., given a set of tuple-generating dependencies (tgds), is it the case that the chase under this set of tgds terminates, for every input database? In view of the fact that this problem is undecidable, no matter which version of the chase we consider, it is natural to ask whether well-behaved classes of tgds, introduced in different contexts such as ontological reasoning, make our problem decidable. In this work, we consider a prominent decidability paradigm for tgds, called stickiness. We show that for sticky sets of tgds, uniform chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: PSpace-complete in general, and NLogSpace-complete for predicates of bounded arity. These complexity results are obtained via graph-based syntactic characterizations of chase termination that are of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database constraints theory
  • Theory of computation → Logic and databases
Keywords
  • Chase procedure
  • tuple-generating dependencies
  • stickiness
  • termination
  • computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, Yehoshua Sagiv, and Jeffrey D. Ullman. Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst., 4(4):435-454, 1979. Google Scholar
  2. 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. Google Scholar
  3. Catriel Beeri and Moshe Y. Vardi. A Proof Procedure for Data Dependencies. J. ACM, 31(4):718-741, 1984. Google Scholar
  4. Marco Calautti, Georg Gottlob, and Andreas Pieris. Chase Termination for Guarded Existential Rules. In PODS, pages 91-103, 2015. Google Scholar
  5. Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. J. Artif. Intell. Res., 48:115-174, 2013. Google Scholar
  6. 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. Google Scholar
  7. Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87-128, 2012. Google Scholar
  8. Alin Deutsch, Alan Nash, and Jeff B. Remmel. The Chase Revisisted. In PODS, pages 149-158, 2008. Google Scholar
  9. Alin Deutsch and Val Tannen. Reformulation of XML Queries and Constraints. In ICDT, pages 225-241, 2003. Google Scholar
  10. 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. Google Scholar
  11. Tomasz Gogacz and Jerzy Marcinkowski. All-Instances Termination of Chase is Undecidable. In ICALP, pages 293-304, 2014. Google Scholar
  12. Gösta Grahne and Adrian Onet. Anatomy of the Chase. Fundam. Inform., 157(3):221-270, 2018. Google Scholar
  13. 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. Google Scholar
  14. Sergio Greco, Cristian Molinaro, and Francesca Spezzano. Incomplete Data and Data Dependencies in Relational Databases. Morgan & Claypool Publishers, 2012. Google Scholar
  15. Sergio Greco, Francesca Spezzano, and Irina Trubitsyna. Stratification Criteria and Rewriting Techniques for Checking Chase Termination. PVLDB, 4(11):1158-1168, 2011. Google Scholar
  16. André Hernich and Nicole Schweikardt. CWA-solutions for data exchange settings with target dependencies. In PODS, pages 113-122, 2007. Google Scholar
  17. David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing Implications of Data Dependencies. ACM Trans. Database Syst., 4(4):455-469, 1979. Google Scholar
  18. Bruno Marnette. Generalized schema-mappings: from termination to tractability. In PODS, pages 13-22, 2009. Google Scholar
  19. Michael Meier, Michael Schmidt, and Georg Lausen. On Chase Termination Beyond Stratification. PVLDB, 2(1):970-981, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact