Static Analysis of Graph Database Transformations
Document type :
Communication dans un congrès avec actes
Title :
Static Analysis of Graph Database Transformations
Author(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]
University of Warsaw [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]
University of Warsaw [UW]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Conference title :
Symposium on Principles of Database Systems
City :
Seattle
Country :
Etats-Unis d'Amérique
Start date of the conference :
2023-06-18
English keyword(s) :
graph databases
data transformations
graph schemas
data transformations
graph schemas
HAL domain(s) :
Informatique [cs]/Base de données [cs.DB]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- document
- Open access
- Access the document
- main.pdf
- Open access
- Access the document