Rewriting the Infinite Chase - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Rewriting the Infinite Chase

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Identifiants

Citer

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⟩
110 Consultations
80 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More