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.

翻译：我们研究了使用基于无环双向正则路径查询(acyclic C2RPQs)的Datalog规则定义的图转换，并研究了两个基本的静态分析问题:在图模式的存在下的类型检查和转换的等效性。此外，我们还研究了目标模式引出问题，旨在构建一个模式，可以紧密捕获符合输入模式的图的所有输出。我们通过将它们化简为C2RPQ包含模式来展示所有这些问题都在EXPTIME时间内完成;我们也提供了匹配的下界。我们使用循环反转将查询包容性减少到在描述逻辑中表示的理论模中的无限制（有限或无限）满足C2RPQ的问题。