Static Analysis of Graph Database Transformations
Type de document :
Communication dans un congrès avec actes
Titre :
Static Analysis of Graph Database Transformations
Auteur(s) :
Boneva, Iovka [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Groz, Benoit [Auteur]
Données et Connaissances Massives et Hétérogènes - LISN [LaHDAK]
Laboratoire Interdisciplinaire des Sciences du Numérique [LISN]
Hidders, Jan [Auteur]
Birkbeck College [University of London]
Murlak, Filip [Auteur]
Uniwersytet Warszawski [Polska] = University of Warsaw [Poland] = Université de Varsovie [Pologne] [UW]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Groz, Benoit [Auteur]
Données et Connaissances Massives et Hétérogènes - LISN [LaHDAK]
Laboratoire Interdisciplinaire des Sciences du Numérique [LISN]
Hidders, Jan [Auteur]
Birkbeck College [University of London]
Murlak, Filip [Auteur]
Uniwersytet Warszawski [Polska] = University of Warsaw [Poland] = Université de Varsovie [Pologne] [UW]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Titre de la manifestation scientifique :
Symposium on Principles of Database Systems
Ville :
Seattle
Pays :
Etats-Unis d'Amérique
Date de début de la manifestation scientifique :
2023-06-18
Mot(s)-clé(s) en anglais :
graph databases
data transformations
graph schemas
data transformations
graph schemas
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Résumé en anglais : [en]
We investigate graph transformations, defined using Datalog-like rules based on acyclic conjunctive two-way regular path queries (acyclic C2RPQs), and we study two fundamental static analysis problems: type checking and ...
Lire la suite >We investigate graph transformations, defined using Datalog-like rules based on acyclic conjunctive two-way regular path queries (acyclic C2RPQs), and we study two fundamental static analysis problems: type checking and equivalence of transformations in the presence of graph schemas. Additionally, we investigate the problem of target schema elicitation, which aims to construct a schema that closely captures all outputs of a transformation over graphs conforming to the input schema. We show all these problems are in EXPTIME by reducing them to C2RPQ containment modulo schema; we also provide matching lower bounds. We use cycle reversing to reduce query containment to the problem of unrestricted (finite or infinite) satisfiability of C2RPQs modulo a theory expressed in a description logic.Lire moins >
Lire la suite >We investigate graph transformations, defined using Datalog-like rules based on acyclic conjunctive two-way regular path queries (acyclic C2RPQs), and we study two fundamental static analysis problems: type checking and equivalence of transformations in the presence of graph schemas. Additionally, we investigate the problem of target schema elicitation, which aims to construct a schema that closely captures all outputs of a transformation over graphs conforming to the input schema. We show all these problems are in EXPTIME by reducing them to C2RPQ containment modulo schema; we also provide matching lower bounds. We use cycle reversing to reduce query containment to the problem of unrestricted (finite or infinite) satisfiability of C2RPQs modulo a theory expressed in a description logic.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- document
- Accès libre
- Accéder au document
- main.pdf
- Accès libre
- Accéder au document