关于用于查询关系数据库中属性图的语言的表现力

《Proceedings of the ACM on Management of Data》：On the Expressiveness of Languages for Querying Property Graphs in Relational Databases

SQL/PGQ标准通过属性图查询视图扩展relational data，分析其三个片段：只读核心、读写扩展和丰富视图定义。结果表明图创建决定表达能力，只读弱于读写且低于NL类，允许任意arity标识符后达到NL，形成严格层次，有序结构下层级崩溃，反映视图构造的核心作用。

　　

摘要

SQL/PGQ 是一种新兴的 ISO 标准，用于查询定义为关系数据视图的属性图。我们从三个方面对其表达能力进行了形式化分析：只读核心、读写扩展以及具有更丰富视图定义的扩展版本。研究结果表明，图创建在决定表达能力方面起着核心作用。

只读部分的表达能力严格弱于读写部分，而读写部分的复杂度仍低于 NL 类。通过添加任意元数的标识符来扩展视图定义可以缩小这一差距：扩展版本能够精确地表达 NL 类的所有查询。这形成了 SQL/PGQ 各部分之间的严格层次结构，它们的并集涵盖了所有 NL 类的查询。在有序结构上，这种层次结构会变得简单：一旦允许使用二元数标识符，更高元数的标识符并不会增加额外的表达能力，这与经典的传递闭包现象相符，同时也突显了视图构建在属性图查询中的核心作用。