1.1.3　图技术发展简史

图数据库技术的本质是图计算与存储技术（事实上所有IT技术在本质上都是计算、存储与网络，因为计算有网络计算、分布式计算，存储有网络存储、分布式存储，因此我们经常省略网络而只说计算和存储），而图计算（图分析）的理论基础是图论。本节通过回顾图论相关学科与技术的发展历史来更好地了解图技术。

1.图计算溯源

图计算最早可以追溯到250年前，欧拉（Leonhard Euler）被认为是人类历史上最伟大的数学家，他是图论与拓扑学的开创人，生于瑞士巴塞尔（金融领域中的“巴塞尔协议Ⅲ”就得名于此地——这种小知识的延展就是典型的2步关联）。

欧拉通过对哥尼斯堡七桥（Seven Bridges of Konigssberg）问题的描述而开创了图论学科。在哥尼斯堡（现俄罗斯的加里宁格勒市，于1946年改名）的一个公园里，有七座桥将普雷格尔河（Pregel）中两个岛及岛与河岸连接起来（图1-15a）。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点呢？欧拉于1736年研究并证明了此问题，他把问题归结为“一笔画”问题，证明一笔画的走法是不可能的。

图1-15b是把陆地与桥分别抽象为点、边后所形成的一个简单拓扑图（拓扑网络）。在这张图中，上面的“一笔画”问题变成了寻找是否存在一条“欧拉路径”问题，即是否存在一条路径可以遍历图中的每一条边仅一次（欧拉环是欧拉路径的一种特例，它的定义是存在一条路径可以从一个点出发遍历所有路径后回到该点）。

欧拉是如何证伪这个“一笔画”问题的呢？按照欧拉路径的定义，只有起点与终点可能存在奇数条边，其他所有途经节点都只可能是偶数条边。显然，图1-15b不符合这个特征，所以一笔画无法实现。如果延展为欧拉环的问题，那么条件会苛刻到所有顶点都必须是偶数条边。按照充分与必要的条件，没有欧拉路径，就一定不会有欧拉环。在这个过程中引入了图论（图计算）的一个基础概念——度（degree），即我们提到的每个顶点的相连边的概念，如果是无向图（忽略图中边的方向），那么每个顶点的相连边的数量就是它的度。而在有向图中，每个顶点的度等于入度边的数量加上出度边的数量。

2.图论的早期应用场景

图论早期应用的一个主要场景是地图渲染（染色），随着15—17世纪大航海时代的到来以及法国大革命（1789—1799年）之后民族国家概念的兴起，世界各国都开始绘制更高精度的地图，而绘图中如何用最少的颜色来保证相邻的两个区域（国家、州、省）用不同的颜色区别开来的问题是个经典的图论问题（图1-16）。

19世纪中叶，数学家们以手工计算的方式证明了“五色地图”问题，而直到整整一个世纪之后的1976年，才在计算机算力的帮助下初步证明了“四色地图”的可行性。这类证明随着计算机算力的提升被不断地演进，直至2005年，通过复杂的人机交互理论证明软件的帮助，以通用的方式证明了四色地图的可行性。这也是通过计算机程序的“穷举计算”来辅助证明的第一个主流理论。

图1-17展示了通过图计算优化后，以四色图取代了五色图。地图上色问题是数学中典型的NP完全（NPC或NP-Complete,Non-deterministic Polynomial-time Complete，非确定性多项式时间完全）问题，即NP中最难的决定性问题。

3.拓扑

欧拉解决了七桥问题之后又过了110年，另一位德国数学家利斯汀（Johann B.Listing，1808—1882年）在1847年率先提出了拓扑的概念。拓扑学研究的范畴包括维数、连通性、紧致性等。例如对莫比乌斯带（Mobius Strip）的研究，莫比乌斯带在日常生活中有广泛的应用，比如动力机械的皮带就做成“莫比乌斯带”状，这样皮带就不会只磨损一面。它还有很多神奇的特性，如果从中间剪开一个莫比乌斯带，不会得到两个窄的带子，而会形成一个旋转了两次再结合的环。如果你把带子的宽度进行三分，并沿着分割线剪开的话，会得到两个环，一个是窄一些的莫比乌斯带，另一个则是旋转了两次再结合的环（见图1-18）。

4.从图到随机图理论的研究

“图”（graph）这个概念被单独提出是在1878年，英国数学家西尔维斯特（J.J.Sylvester）在《自然》（Nature）杂志发表的一篇论文中首次提出图的概念：一张图由一些顶点（实体）和连接这些顶点的边（关系）组成（读者对于西尔维斯特1850年“发明”的另一个名词——矩阵（matrix）绝不会感到陌生）。

20世纪60年代左右，匈牙利数学家厄多斯（Erdos）和瑞利（Rényi）建立了随机图理论（random graph theory），在数学上开始了随机图理论的系统性研究。在随后的40多年里，随机图理论一直是研究复杂网络的基本理论。

到20世纪90年代初，互联网之父伯纳斯·李（Tim B.Lee）提出了语义互联网络（semantic web）的概念，也就是说把整个Web上的所有页面都看作一个巨大网络中的资源节点，这些节点间是相互关联的。这个把互联网资源图论化的设想催生了W3C的RDF（Resource Definition Framework，资源描述框架）标准的推出，被视作图计算的鼻祖。只不过相比于学术气息浓郁的RDF而言，LPG（Labeled Property Graph，标签属性图）或PG（Property Graph，属性图）对于图中顶点与关系的描述更为简单高效。语义网络虽然具有一定的学术高度，但在工业界并没有获得巨大的成功，倒是催生了不少互联网搜索引擎的巨头，先是90年代中后期如日中天的Yahoo，随后是基于PageRank算法（一种高度并发的浅层的图算法）的谷歌公司，再之后就是基于社交图计算而构建起来的社交平台Facebook（后改名为Meta），可以毫不夸张地说，Facebook的社交图计算的理念核心就是6度分隔理论，即任意两个人之间的关联关系不会超过6步，该理念在社交网络的蓬勃发展中至关重要，Twitter、微博、微信、LinkedIn（领英）、eBay、PayPal可以说或多或少是依托这个理念构建而成的。

5.关系型数据库和非关系型数据库

图计算系统或图数据库一般被认为是NoSQL数据库的子集。NoSQL是相对于以SQL为中心的关系型数据库而言的，它确切的涵义是Not Only SQL，也就是说在SQL之外的广阔天地是NoSQL数据库所覆盖的范畴。众所周知，自20世纪80年代开始成为主流的SQL关系型数据库，至今还在各种大小公司的IT环境中广泛应用，它的核心理念是关系表，用二维表以及表与表之间的关联关系来对纷繁复杂的问题进行数据建模。图数据库的理论基础是图论，它的核心理念是用高维的图来表述、还原同样高维的世界——用最简单的顶点与边来表达任意复杂的关联关系。在大数据计算领域，图论有许多应用场景，例如导航、地图染色、资源调度、搜索和推荐引擎，然而这些场景所对应的大数据框架及解决方案并没有真正意义上使用原生化的图的存储与计算模式。换句话说，人们依然在用关系型数据库、列数据库甚至文档数据库来解决图论的问题，也就是说低效、低维的工具被用来强行解决复杂、高维的问题，那么它的用户体验可能很差或投入产出比极为糟糕。最近几年，发明互联网40年后，随着知识图谱逐步深入人心，图数据库和图计算的发展才开始重新受到重视。

近半个世纪，有很多图计算的算法问世，包括从知名的Dijkstra算法（图最短路径问题，1956年），到谷歌创始人Larry Page在20世纪末发明的PageRank算法，以及更复杂的各类社区发现算法（用于检测社区、客群、嫌疑人之间的关联）。简而言之，今天许多大型互联网企业、金融科技公司都是基于图计算技术而诞生的，例如：

·谷歌。PageRank是一种大规模页面（或链接）排序的算法，可以说，谷歌早期的核心技术就是一种浅层的并发图计算技术。

·Facebook。Facebook的技术框架核心是它的社交图谱（Social Graph），即朋友关联朋友再关联朋友。Facebook开源了很多东西，但是这个核心的图计算引擎与架构从未开源过。

·Twitter。Twitter 2014年曾经短暂地在GitHub上开源了Flock DB，但随后就下线了，原因很简单，图计算是Twitter的商业与技术核心，开源模式并没有增加其商业价值。换句话说，任何商业公司的核心技术与机密如果构建在开源之上，其商业价值形同虚设。

·LinkedIn。LinkedIn是专业职场社交网络，最核心的社交特点是推荐距离你2步至3步的职场人，提供这种推荐服务必须使用图计算引擎（或图数据库）。

·高盛集团。在2007—2008年爆发的世界金融危机中，莱曼兄弟公司破产，高盛集团却能全身而退，背后的真实原因是高盛集团应用了强有力的图数据库系统SecDB，它成功计算并预测到即将发生的金融危机。

·全球最大的私募基金管理机构黑石集团。该集团最核心的IT系统阿拉丁（Aladdin）——即资债管理系统在本质上是通过构建流动性风险要素间的依赖图（dependency graph）来完成对全球超过20万亿美元资产的管理的。这一数额超过了全球金融资产的10%。

·PayPal、易趣和许多其他金融或电子商务公司。对于这些技术驱动的新型互联网公司，图计算并不罕见，图的核心竞争力可以帮助他们揭示数据的内部关联，而传统的关系型数据库或大数据技术实在太慢了，它们在设计之初就不是用来处理数据间的深度关联关系的。

6.图计算与后关系型数据库时代

任何一项技术的发展都会经历技术的萌芽、发展、膨胀、过热、降温、再发展的一个曲线周期，在这个过程中通常会有一些规范或既定事实的标准出现，并以此来增强业界的合作与互通（参见1.2.1节）。图计算的规范有两种。

1）RDF：W3C规范；

2）LPG→GQL：从既成事实的业界实践标准LPG演进到第二个数据库查询语言标准GQL（Graph Query Language）。

W3C的RDF规范（2004年发布v1.0版本，2014年发布v1.1版本）最初是用来描述元数据模型（meta-data）的，通常被用来进行知识管理。今天学术界和相当一部分知识图谱公司都在使用RDF来描述图谱当中的“元数据”。RDF默认的查询语句是SPARQL，但RDF和SPARQL存在逻辑复杂、冗长等问题，很难维护。很快，开发者就不喜欢它了。打个比方，你更喜欢XML还是JSON？可能是JSON，因为它更简单、便捷，毕竟轻量和快速是互联网时代的主旋律。

与RDF同时间也催生了LPG，顾名思义，LPG是带有属性的图，也就是说图中的两大基础数据类型——点和边都可以带有属性，如名称、类型、权重、时间戳等。LPG代表着新一代图技术与产品，而其中最早也最知名的一个是Neo4j，它是由瑞典团队成立的公司在2011年发布的第一款LPG图数据库产品。这个领域也出现了不少竞争者和新的玩家，如TitanDB（2016年退出市场）、JanusGraph（Titan的衍生品）、AWS的Neptune、百度的HugeGraph、DGraph、TigerGraph、ArangoDB、Ultipa Graph等。这些图数据库产品的特征各不相同，例如它们在技术底层所采取的架构构建方式，它们触达用户的服务模式、商业模式、可编程API与SDK都有所差异。很显然，图数据库的发展处于一个百花齐放的阶段，市场的发展极为迅速，且用户的需求五花八门，如果某一种图数据库是为了适应某些具体的场景而搭建起来的，那么它在通用性上就难免会存在问题。

好消息是在SQL成为数据库领域唯一国际标准的40年之后，终于将迎来第二个国际标准GQL。有趣的是，在过去10年大数据领域中NoSQL的发展都没有催生任何国标，反而是图数据库的发展迎来了属于自己的国际标准，这恰恰说明图数据库的（标准化的）未来可期。 jjzpmYDg4vtxg7tfBLd9ZH+4ilmCD3Q8vX/El41nqkS7Ud+Oe+lAAnTLjFu8GV/i