# Static Analysis of Graph Database Transformations

arXiv: https://arxiv.org/abs/2304.05070 · HTML: https://mlsanity.com/paper/2304.05070/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2023.

## Built on by (most cited first, 3 of 3)

- [SHACL2FOL: An FOL Toolkit for SHACL Decision Problems](https://mlsanity.com/paper/2406.08018/) (2024)
- [SHACL Validation under Graph Updates (Extended Paper)](https://mlsanity.com/paper/2508.00137/) (2025)
- [Transforming Shape Schemas with Composable Property-Graph Queries (Extended Version)](https://mlsanity.com/paper/2606.14309/) (2026)

## Abstract (arXiv)

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.