Rewriting the infinite chase

Autor: Michael Benedikt, Maxime Buron, Stefano Germano, Kevin Kappelmann, Boris Motik
Přispěvatelé: University of Oxford, Représentation de Connaissances et Langages à Base de Règles pour Raisonner sur les Données (BOREAL), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Ingénierie des Agro-polymères et Technologies Émergentes (UMR IATE), Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut Agro Montpellier, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Montpellier (UM)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut Agro Montpellier, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Montpellier (UM), Technische Universität München = Technical University of Munich (TUM)
Rok vydání: 2022
Předmět:
Zdroj: VLDB 2022-48th International Conference on Very Large Databases
VLDB 2022-48th International Conference on Very Large Databases, Sep 2022, Sydney, Australia. pp.3045-3057, ⟨10.14778/3551793.3551851⟩
ISSN: 2150-8097
DOI: 10.14778/3551793.3551851
Popis: 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.
Databáze: OpenAIRE
načítá se...