Static Analysis of Graph Database Transformations

Iovka Boneva (1, 2) , Benoit Groz (3, 4) , Jan Hidders (5) , Filip Murlak (6) , Slawomir Staworko (1, 2)

1 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
2 LINKS - Linking Dynamic Data
3 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
4 LaHDAK - Données et Connaissances Massives et Hétérogènes - LISN
5 Birkbeck College [University of London]
6 UW - University of Warsaw

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.

Mots clés: graph databases; data transformations; graph schemas

Domaines: Base de données [cs.DB]

Iovka Boneva, Benoit Groz, Jan Hidders, Filip Murlak, Slawomir Staworko. Static Analysis of Graph Database Transformations. Symposium on Principles of Database Systems, Jun 2023, Seattle, United States. ⟨hal-03937274v2⟩