Invited ICDT Tutorial

We are very pleased to announce the invited ICDT2019 tutorial speaker.

The Power of the Terminating Chase (Slides)
by Markus Kroetzsch

Abstract: The chase procedure has become a staple of modern database theory. Elegant and mathematically appealing, yet intuitive and practical, it is our first choice whenever we need a universal model of some Horn logic theory – as we frequently do in data integration, query optimisation, data exchange, ontology-based query answering, logic programming, and many other areas. The sheer number of theoretical studies and practical implementations of this cherished approach is hard to keep track of. Of course, our interest is usually in cases where the chase terminates and the resulting model is finite. The undecidability of this situation has been met by creating a sizeable arsenal of sufficient termination criteria that apply to many – if not to all – practical cases.

Surprisingly, we know very little about the actual expressive power of theories for which the chase terminates (on all input databases). Reviewing what is known, we quickly realise that essentially all termination criteria lead to query languages that are hardly more expressive than traditional Datalog. Was all our struggle of taming the looming infinity of fresh nulls just a vain mathematical exercise in inventing syntactically contrived Datalog variants? Is the terminating chase always weak? We answer with a resounding no: not only can theories with a universally terminating standard chase surpass Datalog on queries in PTime, but they can actually express Boolean queries of non-elementary (data) complexity. These insights expose a surprisingly large discrepancy between our current understanding of the chase and its true potential.

This invited tutorial starts with a gentle introduction of the main variants of the chase, followed by an overview of what is known about chase termination and expressivity of rules. We then review the limits of current approaches, and show example theories that go beyond those limits. Our discussion raises more questions than it answers, and we conclude with an outlook on the research opportunities in this area.

Dan Olteanu Markus is a full professor of the Faculty of Computer Science of the Technical University of Dresden, where he is holding the chair for Knowledge-Based Systems. He obtained his Ph.D. from the Institute of Applied Informatics and Formal Description Methods (AIFB) of Karlsruhe Institute of Technology (KIT) in 2010, and thereafter worked as a researcher and departmental lecturer at the Department of Computer Science of the University of Oxford until October 2013. From November 2013 till his appointment as a professor in July 2016, he was leading an Emmy Noether research group at TU Dresden. Markus has made important contributions to the development of Wikipedia's free knowledge base Wikidata. Further activities of his include the efficient ELK reasoner for OWL EL, the popular content management system Semantic MediaWiki, the W3C OWL 2 standard, and most recently the rule engine VLog. His research has contributed to the fields of lightweight and rule-based ontology languages, query answering, reasoning complexity, and content management and integration platforms for the Web of Data.