License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.3
URN: urn:nbn:de:0030-drops-103057
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10305/
Go to the corresponding LIPIcs Volume Portal

Krötzsch, Markus ; Marx, Maximilian ; Rudolph, Sebastian

The Power of the Terminating Chase (Invited Talk)

pdf-format:
LIPIcs-ICDT-2019-3.pdf (0.6 MB)

Abstract

The chase has become a staple of modern database theory with applications in data integration, query optimisation, data exchange, ontology-based query answering, and many other areas. Most application scenarios and implementations require the chase to terminate and produce a finite universal model, and a large arsenal of sufficient termination criteria is available to guarantee this (generally undecidable) condition. In this invited tutorial, we therefore ask about the expressive power of logical theories for which the chase terminates. Specifically, which database properties can be recognised by such theories, i.e., which Boolean queries can they realise? For the skolem (semi-oblivious) chase, and almost any known termination criterion, this expressivity is just that of plain Datalog. Surprisingly, this limitation of most prior research does not apply to the chase in general. Indeed, we show that standard - chase terminating theories can realise queries with data complexities ranging from PTime to non-elementary that are out of reach for the terminating skolem chase. A "Datalog-first" standard chase that prioritises applications of rules without existential quantifiers makes modelling simpler - and we conjecture: computationally more efficient. This is one of the many open questions raised by our insights, and we conclude with an outlook on the research opportunities in this area.

BibTeX - Entry

@InProceedings{krtzsch_et_al:LIPIcs:2019:10305,
  author =	{Markus Kr{\"o}tzsch and Maximilian Marx and Sebastian Rudolph},
  title =	{{The Power of the Terminating Chase (Invited Talk)}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10305},
  doi =		{10.4230/LIPIcs.ICDT.2019.3},
  annote =	{Keywords: Existential rules, Tuple-generating dependencies, all-instances chase termination, expressive power, data complexity}
}

Keywords: Existential rules, Tuple-generating dependencies, all-instances chase termination, expressive power, data complexity
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI