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: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Computer Science - Databases General Engineering [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Databases (cs.DB) Logic in Computer Science (cs.LO) [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
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 |
Externí odkaz: |
načítá se...