关于数据库:图查询语言的历史回顾短文

本文首发于 Nebula 公众号：图查询语言的历史回顾短文

前言

最近在对图查询语言 GQL 和国际标准草案做个梳理，调研过程中找到上面这篇 mark 了没细看的旧文（毕竟珍藏就是看过）。做个简略的记录。

摘要

本短文会波及到的图查询语言有 Cypher、Gremlin、PGQL 和 G-CORE。

背景

本文次要摘录翻译自 [Tobias2018]（见参考文献），并未波及到 SPARQL 和 RDF，只探讨了属性图。

文章撰写的工夫是 2018 年，能够看做 GQL（Graph Query Language）的一些后期筹备。GQL 有多个相干的起源，参见上面这张图。

因为 Cypher 的历史和 Neo4j 严密相干，本文会提一些 Neo4j 晚期的历史。[Angles2008]（见参考文献）和 [Wood2012]（见参考文献）是两个不错的对于图模型和图查询语言的总结。

年表简述

• 2000 年，Neo4j 的创始人产生将数据建模成网络（network）的想法。
• 2001 年，Neo4j 开发了最早的外围局部代码。
• 2007 年，Neo4j 以一个公司的形式运作。
• 2009 年，Neo4j 团队借鉴 XPath 作为图查询语言，Gremlin 最后也是基于这个想法。
• 2010 年，Neo4j 和 Marko Rodriguez 采纳术语属性图（Property Graph）来形容 Neo4j 和 Tinkerpop / Gremlin 的数据模型。[PG2010]（见参考文献）
• 2011 年，第一个公开发行版本 Neo4j 1.4 公布了第一个版本的 Cypher。
• 2012 年，Neo4j 1.8 为 Cypher 减少写入图的能力。
• 2012 年，Neo4j 2.0 减少了标签和索引，Cypher 成为申明式的语言。
• 2015 年，Oracle 为 PGX 创造查询语言 PGQL。
• 2015 年，Neo4j 将 Cypher 开源为 openCypher。
• 2015 年，LDBC 成立图查询语言工作组。
• 2016 年，LDBC 工作组开始设计 G-CORE。
• 2017 年，WG3 工作组开始探讨如何将属性图查问能力引入 SQL。
• 2017 年，LDBC 工作组实现了 G-CORE 的初始设计 [GCORE2018]（见参考文献）。
• 2018 年，Cypher 形式化语义的论文发表 [Cypher2018]（见参考文献）。

Gremlin、Cypher、PGQL 和 G-CORE 的演进

Neo4j 的晚期历史

Neo4j 和属性图这种数据模型，最早构想于 2000 年。Neo4j 的创始人们过后在开发一个媒体管理系统，所应用的数据库的 schema 常常会产生重大变动。为了反对这种灵活性，Neo4j 的联结创始人 Peter Neubauer，受 Informix Cocoon 的启发，心愿将零碎建模为一些概念相互连接的网络。印度理工学院孟买分校的一群研究生们实现了最早的原型。Neo4j 的联结创始人 Emil Eifrém 和这些学生们花了一周的工夫，将 Peter 最后的想法扩大成为这样一个模型： 节点通过关系连贯，key-value 作为节点和关系的属性 。这群人开发了一个 Java API 来和这种数据模型交互，并在关系型数据库之上实现了一个形象层。

尽管这种网络模型极大的进步了生产力，然而性能始终很差。所以 Neo4j 联结创始人 Johan Svensson 花精力，为这种网络模型实现了一个原生的数据管理系统。这个就成为了 Neo4j。在最后的几年，Neo4j 作为一个外部产品很胜利。在 2007 年，Neo4j 的知识产权转移给了一家独立的数据库公司。

Neo4j 的第一个公开发行版中，数据模型由节点和有类型的边形成，节点和边都有 key-value 组成的属性。Neo4j 的晚期版本没有任何的索引，应用程序只能从根节点开始本人结构查问构造（search structure）。因为这样对于应用程序十分轻便，Neo4j 2.0（2013 年 12 月公布）引入了一个新概念——点上的标签（label）。基于点标签，Neo4j 能够为一些预约义的节点属性建设索引。

节点、关系、属性、关系只能有一个标签、节点能够有零个或者多个标签，以上这些形成了 Neo4j 属性图的数据模型定义 。起初减少的索引性能，让 Cypher 成为了与 Neo4j 交互的次要形式。因为这样利用开发者只须要关注于数据自身，而不是上段提到的那个开发者本人构建的查问构造（search structure）。

图或者说网络类型的数据模型（多对多的关系）和其数据库的历史，能够追溯到 80 年代。见 Kleppmann 2017 第二章（见参考文献局部）。

Gremlin 的发明

最后与 Neo4j 的查问形式是通过 Java API。应用程序能够将查问引擎作为库嵌入到应用程序中，而后应用 API 查问图。如果是自定义查问引擎，而后应用程序近程拜访服务器，这样就比拟艰难。

就在这段时间，NOSQL 这个概念开始呈现。NOSQL 型的数据库引擎个别用 REST 和 HTTP 来交互和查问。Neo4j 的晚期员工 Tobias Lindaaker（和 Ivarsson）思考用 HTTP 的形式拜访 Neo4j 会是一种更好的方法。他们察看到很多的查问语句能够表白为： 图到树的投影映射（projection）。典型的，从根节点开始遍历一个扩张树（spanning tree），而后返回叶子节点。基于这样的察看，并参考一些树结构的查问语句，比方 XPath，兴许能够作为一种图的查问形式。而且，XPath 的语法和个别 URI 的语法很像。这样 XPath 查问能够很天然的作为 HTTP GET 中 URI 的一部分。Neo4j 的联结创始人 Peter Neubauer 喜爱这个想法，找了一个敌人 Marko Rodriguez 来干。两天后，Marko 做了一个原型，用 XPath 作为图查问，Groovy 提供循环构造，分支，和计算。这个就是 Gremlin 最后的原型。2009 年 11 月公布了第一个版本。

起初，Marko 发现同时用两种不同的解析器（XPath 和 Groovy）有很多问题，就将 Gremlin 改为基于 Groovy 的一种内置的畛域特定语言（DSL）。

Cypher 的发明

Gremlin 和 Neo4j 的 Java API 一样，最后用于表白如何查询数据库的一种过程（Procedural）。它容许更短的语法来表白查问，也容许通过网络近程拜访数据库。Gremlin 这种过程式的个性，须要用户晓得如何采纳最好的方法查问后果，这样对于应用程序开发人员来说仍旧有累赘。基于申明式语言 SQL 的胜利：SQL 能够将获取数据的申明形式和引擎如何获取数据离开，Neo4j 的工程师们心愿开发一种申明式的图查询语言。

2010 年，Andrés Taylor 作为工程师退出 Neo4j，在此之前他是 SQL DBA。他开始了一个我的项目，受 SQL 启发，其指标是开发图查询语言，而这种新语言 Cypher 于 2011 年 Neo4j 1.4 公布。

Cypher 的语法根底，是用 “ascii 艺术 (ascii art)” 来形容图模式。这种形式最后来源于 Neo4j 工程师团队在源代码中评注如何形容图模式。能够看下图的例子：

ascii art 简略说，就是如何用可打印文原本形容点和边。Cypher 文本用（）示意点，-[]-> 示意边。(query)–[modeled as]->(drawing) 来示意终点 query，起点 drawing，边 modeled as。

对于程序员来说，当然能够设计一个 API 示意操作点，一个 API 示意操作边. 但这样就不是 SQL 这种申明式语言的目标，对于非程序员应用也太艰难。

Cypher 第一个版本实现了对图的读取，然而须要用户阐明从哪些节点开始查问。只有从这些节点开始，才能够反对图的模式匹配。

稍微学术一点的说，graph patterns（或者 motifs finding）和 navigational expression 是两种不同的图查问操作 Renzo2017（见参考文献局部）。不同语言这两种操作的语义是有肯定差异的。

在前面的版本，2012 年 10 月公布的 Neo4j 1.8 中，Cypher 减少了批改图的能力。但查问还是须要指明从哪些节点开始。

2013 年 12 月，Neo4j 2.0 引入了 label 的概念，label 实质上是个索引。这样，查问引擎就能够利用索引，来抉择模式所匹配到的节点，而不须要用户指定开始查问的节点。

有没有相熟的感觉？

随着 Neo4j 的遍及，Cypher 有着宽泛的开发者群体，和各行各业的应用。

图查询语言也有申明式（Decalarative）和命令式（Imperative）的区别，前者（Cypher）相比后者（Gremlin）更强调目标和伎俩拆散，更依赖于执行优化。但在工程上，两者思维并没有那么大的区别，后者也会有提早计算和优化，前者也能够局部命令式的思维。好的优化在工程上并不是那么容易，业余的用户比查问引擎更分明如何求取、拜访、加工数据 Renzo2017。

openCypher – 一种推动和标准化 Cypher 的开源过程

2015 年 9 月，Neo4j 凋谢了 Cypher 查询语言，通过开源的形式来治理。这个新主体的治理主体是 openCypher Implementors Group（oCIG）。

2016 年，openCypher 我的项目公布 EBNF 和 ANTLR4，Neo4j 也奉献了很多基于 Apache 2.0 的语言功能测试集（openCypher Technology Compatibility Kit, TCK）。将这些作为语言规范定义，任何人都能够为该语言提交新的提议。2016 年，SAP HANA Graph 公布了基于 Cypher 的查问局部的实现，Agens Graph 和 Redis Graph 在 2017 年反对了 Cypher。2017 年 oCIG 也进行了一系列线上线下的会议，探讨语言性能扩大等。

这个治理和探讨形式能够通过如下形式：https://github.com/opencypher/openCypher/blob/master/CIP-PROCESS.adoc

oCIG 公布 openCypher，采纳英语语言作为标准，对应了 Neo4j 3.3.0 版本中的 Cypher。

PGQL 的创立

2015 年，Oracle 为 PGX 引擎开发了图查询语言 PGQL。PGQL 受 Cypher 的启发，也和 Cypher 很靠近。

G-CORE 的创立

Linked Data Benchmarking Council（LDBC）定义了一种厂商无关的基准测试。在开发这个基准测试的过程中，他们发现市面上没有规范的查询语言来表白图查问。为了解决这个问题，成立了一个特地工作组，调研市面上曾经存在的图查询语言和框架，定义图查问必须的性能，而后为现有语言提供批改倡议。

2016 年，他们想设计一种新语言，而不是对于现有语言的批改。次要起因是不想受现有语言的模型的限度。

G-CORE 是由 LDBC 工作组设计的，但次要受 Cypher 的启发，采纳一样的语义。

论断

Cypher 是 PGQL 和 G-CORE 的独特先人。这几个语言的语法和语义都十分的靠近。PGQL 更靠近一些晚期的 Cypher，而 G-CORE 更冀望语法和语义上都与 Cypher 兼容。

一些集体认识

除去学术上的摸索和一些零散的工程尝试，以 Cypher 作为支流属性图查询语言工程实际的历史基准，也就 10 年的工夫。在后面的几年 2010-2013，Cypher 本身在根底图性能上还有不少缺失，比方索引、图模式，迭代到 2014 年才产生以后应用的一个支流版本，并且还在继续演变 [Nadime2018]（见参考文献局部）。

重头全新设计一种图语言其实很难，很可能会把前人走过的路（坑）再走（掉）一遍（G-CORE 和 nGQL）。这是 GQL 第一个不容易的中央。

一个标准化组织中，有学术和商业机构，各自诉求也很不雷同，商业机构曾经各自有宏大的商业应用群体，这是第二个不容易的中央。

制订完的规范，最初是否会被市场所承受和驳回（vendor、custormer、developer、goverment），又须要多少的布道。这是 GQL 第三个不容易的中央。

除了外围根底的图操作以外的个性，比方 SQL、pregel [Grzegorz2010]（见参考文献局部）、GNN，每个语言 PGQL、GSQL 甚至 Neo4j 本人都各自采纳了齐全不同的形式来反对这些个性，要不要思考这些新呈现的个性。这是 GQL 第四个不容易的中央。

再想想 GQL 和 Apache Tinkerpop/Gremlin 这两条齐全不同的路，这是一个变动很快的时代，计算机又是一个更强调 de facto 规范的行业，GQL 并不容易。(打脸）

参考文献

• [Angles2008] Renzo Angles and Claudio Gutierrez,“Survey of Graph Database Models”, ACM Computing Surveys, Vol. 40, February 2008
• [PG2010] Marko A. Rodriguez and Peter Neubauer,“The Graph Traversal Pattern”, April 2010
• [Wood2012] Peter Wood,“Query Languages for Graph Databases”, SIGMOD Record 2012
• [Cypher2018] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor,“Cypher: An Evolving Query Language for Property Graphs”, SIGMOD 2018
• [GCORE2018] Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter Boncz, George Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan Sequeda, Oskar van Rest, and Hannes Voigt,“G-CORE A Core for Future Graph Query Languages”, SIGMOD 2018
• [Cypher9] openCypher,“Cypher Query Language Reference”, Version 9, Nov. 2017
• Renzo2017 Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5, Article 68 (November 2017), 40 pages.
• Kleppmann2017 Kleppmann, Martin: Designing Data-Intensive Applications. Beijing : O’Reilly, 2017. – ISBN 978-1-4493-7332-0
• [Tobias2018] Title: An overview of the recent history of Graph Query Languages. Authors Tobias Lindaaker, U.S. National Expert.Date: 2018-05-14
• Deutsh2020 Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. 2020. Aggregation Support for Modern Graph Analytics in TigerGraph. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 377–392.
• Grzegorz2010 Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD ’10). Association for Computing Machinery, New York, NY, USA, 135–146.
• Nadime2018 Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD ’18). Association for Computing Machinery, New York, NY, USA, 1433–1445.
• databricks2020https://docs.databricks.com/spark/latest/graph-analysis/graphframes/user-guide-scala.html#motif-finding

交换图数据库技术？退出 Nebula 交换群请先填写下你的 Nebulae 名片，Nebula 小助手会拉你进群~~

查看大厂实际案例？Follow Nebula 公众号 ：NebulaGraphCommunity 回复「PPT」把握【美团的图数据库系统】、【微众银行的数据治理计划】以及其余大厂的风控、常识图谱实际。

举荐浏览

• 浅谈图数据库
• 聊聊图数据库和图数据库的小常识
• Nebula Graph 技术总监陈恒：图数据库怎么和深度学习框架进行联合？
• 图数据库爱好者的团聚在议论什么？