  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.
