Rewriting the Infinite Chase - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2022

Rewriting the Infinite Chase


Guarded tuple-generating dependencies (GTGDs) are a natural extension of description logics and referential constraints. It has long been known that queries over GTGDs can be answered by a variant of the chase-a quintessential technique for reasoning with dependencies. However, there has been little work on concrete algorithms and even less on implementation. To address this gap, we revisit Datalog rewriting approaches to query answering, where GTGDs are transformed to a Datalog program that entails the same base facts on each base instance. We show that the rewriting can be seen as containing "shortcut" rules that circumvent certain chase steps, we present several algorithms that compute the rewriting by simulating specific types of chase steps, and we discuss important implementation issues. Finally, we show empirically that our techniques can process complex GTGDs derived from synthetic and real benchmarks and are thus suitable for practical use.
Fichier principal
Vignette du fichier
p2537-benedikt-long.pdf (684.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03714595 , version 1 (05-07-2022)


Attribution - NonCommercial - NoDerivatives



Michael Benedikt, Maxime Buron, Stefano Germano, Kevin Kappelmann, Boris Motik. Rewriting the Infinite Chase. VLDB 2022 - 48th International Conference on Very Large Databases, Sep 2022, Sydney, Australia. pp.3045-3057, ⟨10.14778/3551793.3551851⟩. ⟨lirmm-03714595⟩
109 View
79 Download



Gmail Facebook X LinkedIn More