Formalising openCypher Graph Queries in Relational Algebra

ADBIS 2017

从数据库理论视角把 openCypher 的核心只读查询形式化为“关系图代数”，给出精确语义与到代数的系统化映射，为实现一致性与优化奠定基础。

论文要点

  • 动机与定位：openCypher 已有语法和测试，但缺乏严格语义。论文补上形式化语义，避免“以实现为准”的模糊空间，降低实现分歧和锁定风险。
  • 属性图模型定义：用数学对象刻画节点、边、标签、边类型与属性（属性允许缺失值），明确查询输出是关系（bag of tuples），不是图结构本身。
  • 核心查询子集：覆盖 MATCH/WHERE/WITH/RETURN/UNWIND/OPTIONAL MATCH 等只读查询；不含写操作（CREATE/MERGE/DELETE/SET）。
  • 模式匹配的唯一性约束：在单个 MATCH 子句中，同一条边变量不可重复绑定（边唯一性），节点可重复，这是语义层面的核心规则。
  • 分组与聚合规则：openCypher 没有显式 GROUP BY。论文给出算法，从 RETURN/WITH 的表达式列表推导分组键；聚合函数必须是表达式最外层，嵌套聚合非法。
  • 关系图代数（RGA）算子：在关系代数基础上引入 get-vertices、expand-out/in/both、可变长度路径扩展、all-different（边不重复）等算子，并配合选择、投影、连接、去重、排序、limit/skip。
  • 编译式映射：给出从 openCypher 到 RGA 的自底向上翻译规则：先把 MATCH 变成“起点获取 + 多次 expand”，再接 WHERE 过滤、OPTIONAL MATCH 的左外连接、WITH/RETURN 的分组投影排序等。
  • 优化与可移植性价值：形式化代数为等价变换、代价优化、跨系统一致性测试提供依据，利于构建标准化查询优化器与多引擎实现。
  • 局限与扩展方向：当前仅覆盖只读核心，未涉及写操作、复杂表达式/类型；后续可扩展到增量维护、动态图更新与分布式执行计划。

对系统实现的启发

  • 查询编译器更易模块化：把 openCypher 语法树映射到 RGA，可复用成熟的关系代数优化框架。
  • 执行层可复用关系算子：选择/投影/连接/分组等算子与关系数据库类似，图特有部分集中在扩展与路径算子。
  • 一致性测试基准：可把 RGA 作为“中间表示”的语义真值，降低不同实现间的不一致。

读后感

论文为 openCypher 提供了一个基于关系代数的数学语义基础和系统映射算法，明确了图查询语言可以被系统性、模块化地规约为关系查询算子组合，这为未来图 + SQL 混合优化器、可扩展执行引擎设计提供了理论保障。

该方案似乎并未从根本上解决多类型走图查询的复杂性，仍然需要将多类型查询手动拆解为多条子查询并通过 union 进行组合，无法像 Neo4j 那样自然地支持全类型的 all node scan。