Title: Rewriting the Infinite Chase
Abstract: Guarded tuple-generating dependencies (GTGDs) form a natural extension of description logics and referential constraints. Although reasoning problems with GTGDs have been known to be decidable for several decades, there has been little work on concrete algorithms and even less on implementation. We address this gap by revisiting the approach to atomic query answering over GTGDs via backwards reasoning or Datalog-rewriting. We show how sound rewriting-based approaches can be motivated from the “forward reasoning approach”—that is, via the chase. We provide a set of algorithms for rewriting that represent different ways of simulating the chase, along with optimizations of these approaches. We then present an experimental analysis of our methods, based on a combination of synthetic and manually-curated benchmarks.
Room 03/124, Bat 5.
