CyEqSet

CyEqSet是一个包含148对等价Cypher查询的数据集，由等效SQL查询对转换而来，并通过对开源图数据库基准测试和广泛使用的开源Cypher项目收集的查询进行等价转换构成。数据集涵盖了简单和复杂的图模式，用于评估图查询等价证明器GraphQE的性能。

CyEqSet is a dataset comprising 148 pairs of equivalent Cypher queries. Derived from equivalent SQL query pairs, it is constructed via equivalence transformation of queries collected from open-source graph database benchmarks and widely adopted open-source Cypher projects. Covering both simple and complex graph patterns, this dataset is intended for evaluating the performance of the graph query equivalence prover GraphQE.

搜集汇总

数据集介绍

构建方式

CyEqSet数据集的构建采用了两种主要方法。首先，研究人员将Calcite数据集中等价的SQL查询对手动翻译为对应的Cypher查询对，成功构建了79对等价Cypher查询。其次，从流行的开源图数据库基准测试和广泛使用的开源Cypher项目中收集了36个真实世界的Cypher查询，通过应用现有的Cypher查询重写规则，构建了68对等价Cypher查询。最终，CyEqSet包含了148对等价Cypher查询，涵盖了从简单到复杂的多种图模式。

特点

CyEqSet数据集具有显著的特点。首先，它包含了148对等价的Cypher查询，覆盖了多种Cypher查询片段，如MATCH、OPTIONAL MATCH、RETURN、WHERE等。其次，数据集还包含了高级或复杂的Cypher特性，如可变长度路径、排序和截断操作等。此外，数据集中的查询对既包括简单的图模式，也包括复杂的图模式，如可选图模式和可变长度路径，这使得数据集在测试Cypher查询等价性证明工具时具有广泛的代表性和挑战性。

使用方法

CyEqSet数据集主要用于评估Cypher查询等价性证明工具的有效性。研究人员可以使用该数据集来测试其工具是否能够正确识别和证明查询对的等价性。具体使用方法包括：将数据集中的查询对输入到证明工具中，运行工具进行等价性验证，然后统计工具成功证明的查询对数量及其性能表现。此外，数据集还可用于比较不同证明工具的性能和准确性，为进一步优化和开发新的证明算法提供基准。

背景与挑战

背景概述

CyEqSet数据集由中国科学院软件研究所的Lei Tang、Wensheng Dou等研究人员于2025年创建，旨在解决图数据库领域中的Cypher查询等价性证明问题。该数据集包含148对等价的Cypher查询，主要用于评估自动化证明工具GraphQE的有效性。作为首个专注于图查询等价性验证的基准数据集，CyEqSet填补了图数据库理论研究的空白，并为查询优化、错误检测等应用提供了重要基础。其核心价值在于通过标准化测试案例推动图查询语义形式化建模的发展。

当前挑战

CyEqSet面临的挑战主要体现在两个方面：在领域问题层面，需解决图查询语言与关系型SQL在数据模型（属性图vs关系模型）和查询模式（图模式匹配vs元组演算）的本质差异带来的语义建模难题；在构建过程中，需克服复杂Cypher特性（如变长路径、排序截断等）的形式化表达挑战，以及从SQL查询到Cypher查询的语义保真转换问题。此外，确保生成的查询对在多样化图模式覆盖性与语义等价性之间的平衡也构成显著挑战。

常用场景

经典使用场景

在知识图谱构建与查询优化领域，CyEqSet数据集通过148对语义等价的Cypher查询对，为验证图查询等价性证明工具GraphQE的有效性提供了基准测试环境。该数据集典型应用于评估图数据库查询优化器的正确性，例如检测Neo4j等系统中因查询重写规则应用不当导致的执行计划偏差。其核心价值在于覆盖了属性图模型下的复杂查询模式，包括可变长度路径、多标签节点匹配及带排序限制的子查询等场景。

衍生相关工作

围绕CyEqSet衍生的经典工作包括：1) GraphQE验证框架成为首个支持Cypher的自动化等价证明器，其基于LIA*理论的SMT求解方法被后续SPARQL验证工具借鉴；2) 从该数据集提炼的22种查询重写规则被Neo4j优化器采纳；3) 基于其构建的Cypher-Gremlin跨语言等价测试套件成为LDBC基准的核心组件。这些工作共同推动了图查询语言形式化验证领域的方法标准化。

数据集最近研究

最新研究方向

近年来，随着图数据库技术的快速发展，Cypher查询等价性证明成为图数据库领域的重要研究方向。GraphQE作为首个针对Cypher查询的自动化等价性证明工具，通过基于U-semiring的图原生代数表示方法，成功解决了传统SQL等价性证明器无法直接应用于图查询的问题。该工具将Cypher查询的等价性证明转化为对应代数表示的等价性验证，并利用SMT求解器进行自动化验证。在构建的CyEqSet数据集上，GraphQE成功验证了138对等价Cypher查询，平均延迟仅为38毫秒，展现了其在图查询优化、错误检测等方面的应用潜力。这一研究不仅填补了图查询等价性证明的空白，也为图数据库系统的可靠性保障和性能优化提供了新的理论基础和技术支持。

相关研究论文

• Proving Cypher Query Equivalence

  中国科学院软件研究所，中国 stress testing 系统软件国家重点实验室，中国科学院大学，南京大学，南京软件技术研究所 · 2025年