Back to Search
Start Over
Static Analysis of Graph Database Transformations
- Source :
- Symposium on Principles of Database Systems, Jun 2023, Seattle, United States
- Publication Year :
- 2023
-
Abstract
- 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.
- Subjects :
- Computer Science - Databases
Subjects
Details
- Database :
- arXiv
- Journal :
- Symposium on Principles of Database Systems, Jun 2023, Seattle, United States
- Publication Type :
- Report
- Accession number :
- edsarx.2304.05070
- Document Type :
- Working Paper