详情
本书系统地介绍了图数据库的历史由来、建模方法、工作原理和一些真实的用户用例，详细地说明了图数据解决的是什么样的问题，并以Neon4j数据库和Cypher查询语言为例，阐述了图数据库的建模方法和领域用例，最后还介绍了图数据库的工作原理以及一些实用的图论算法。
书名：图数据库
ISBN：978-7-115-37604-6
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 [美] Ian Robinson Jim Webber Emil Eifrem
译 刘 璐 梁 越
责任编辑 杨海玲
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
Copyright ©2013 by O’Reilly Media, Inc.
Simplified Chinese Edition, jointly published by O’Reilly Media, Inc. and Posts & Telecom Press, 2015. Authorized translation of the English edition, 2015 O’Reilly Media, Inc., the owner of all rights to publish and sell the same.
All rights reserved including the rights of reproduction in whole or in part in any form. 本书中文简体版由O’Reilly Media, Inc.授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式复制或抄袭。
版权所有，侵权必究。
世界上的大部分领域实际上都可以建模成图，而软件开发人员或是数据库管理人员却在辛辛苦苦地将这些图转化成关系型数据库中的表。想象一下，假如你再也不用去做这样的转化，假如数据库的迁移可以变得轻松简单，你愿意去接受一个全新的数据库吗？图数据库就是这样一个完全不同于关系型数据库的新型数据库，它处理的是大规模的数据和不断变化的需求。
本书系统地介绍了图数据库的历史由来、建模方法、工作原理和一些真实的用户用例，详细地说明了图数据解决的是什么样的问题，并以Neo4j数据库和Cypher查询语言为例，阐述了图数据库的建模方法和领域用例，最后还介绍了图数据库的工作原理以及一些实用的图论算法。本书的三位作者均为Neo4j Technology公司的技术高手，他们对图数据库及其解决方案有丰富的经验，其中一位甚至还是Neo4j图数据库的联合创始人。
本书适合开发人员和数据库管理人员了解和学习图数据库时阅读，作为一门新的知识和独特的数据库领域来拓宽视野，也适合提供解决方案的负责人了解行业动向和新的解决问题的方式。通过阅读本书，读者可以对图数据库这一领域有一个透彻的了解。
O’Reilly Media通过图书、杂志、在线服务、调查研究和会议等方式传播创新知识。自1978年开始，O’Reilly一直都是前沿发展的见证者和推动者。超级极客们正在开创着未来，而我们关注真正重要的技术趋势——通过放大那些“细微的信号”来刺激社会对新科技的应用。作为技术社区中活跃的参与者，O’Reilly的发展充满了对创新的倡导、创造和发扬光大。
O’Reilly为软件开发人员带来革命性的“动物书”；创建第一个商业网站（GNN）；组织了影响深远的开放源代码峰会，以至于开源软件运动以此命名；创立了《Make》杂志，从而成为DIY革命的主要先锋；公司一如既往地通过多种形式缔结信息与人的纽带。O’Reilly的会议和峰会集聚了众多超级极客和高瞻远瞩的商业领袖，共同描绘出开创新产业的革命性思想。作为技术人士获取信息的选择，O’Reilly现在还将先锋专家的知识传递给普通的计算机用户。无论是通过书籍出版、在线服务或者面授课程，每一项O’Reilly的产品都反映了公司不可动摇的理念——信息是激发创新的力量。
“O’Reilly Radar博客有口皆碑。”
——Wired
“O’Reilly凭借一系列（真希望当初我也想到了）非凡想法建立了数百万美元的业务。”
——Business 2.0
“O’Reilly Conference是聚集关键思想领袖的绝对典范。”
——CRN
“一本O’Reilly的书就代表一个有用、有前途、需要学习的主题。”
——Irish Times
“Tim是位特立独行的商人，他不光放眼于最长远、最广阔的视野并且切实地按照Yogi Berra的建议去做了：‘如果你在路上遇到岔路口，走小路（岔路）。’回顾过去Tim似乎每一次都选择了小路，而且有几次都是一闪即逝的机会，尽管大路也不错。”
——Linux Journal
1999年，我们的开发团队每天都工作23小时，至少感觉上是这样的。似乎每天都有一个疯狂的想法付诸实施，而这些想法刚刚获得数百万美元的融资。我们的竞争对手都有数百个工程师，而我们只是一个20人左右的开发团队，其中还有10个工程师要将他们的大部分时间花在关系型数据库上。
我们花了一段时间去寻找原因。当深挖企业内容管理系统的数据持久层时，我们意识到我们的软件不但需要管理大量独立的离散数据项，还要管理数据项之间的关联。尽管离散数据可以很容易地使用关系表来处理，但对于关联数据，其存储更具挑战性，而且其查询速度也异常缓慢。
出于对关系型数据库完全的绝望，我和我的两个Neo联合创始人Johan和Peter开始尝试使用其他数据模型处理数据，尤其是那些基于图的模型。我们欣喜地发现以图为中心的模型似乎可以替代扁平的SQL语法，使开发者更容易地操作关联数据。我们观察到，有了图数据模型，我们的开发团队在数据库上节约了一半的时间。
当然，我们要说，我们不是独自在战斗。图论已经存在了近300年，且被广泛应用于各种不同的数学问题，一定可以有能拥抱图的数据库！
因此我们在早期互联网上使用Altavistad[1]搜索类似的数据库却一无所获。经过几个月的调查，我们（天真地）着手从无到有地创建一个天然支持图的数据库。我们的愿景是：在保留所有关系型数据库的已被验证的特性（事务、ACID、触发器等）的基础上使用21世纪的数据模型。于是Neo项目诞生了，伴随它诞生的还有我们现在所知的图数据库。
新千年的第一个10年，Google、Facebook、Twitter这些改变世界的新业务融入大众生活。它们有一个共同点：将关联的数据—图—作为业务的中心。15年后的今天，图无处不在。
以Facebook为例，它的创建理念认为：尽管诸如使用者的名字、行为等离散信息是有价值的，但是使用者的联系更具有价值。Facebook的创始人Mark Zuckerberg正是基于在社交图（social graph）中捕获社交联系这样的洞见建立了一个宏大的帝国。
同样，Google的Larry Page和Sergey Brin提出了存储和处理离散的网页文件以及网页文件之间的关联的方法。Google建立了网络图（Web graph），这使其成为过去10年中最具影响力的公司。
如今，图已成功地被网络巨头以外的公司接纳。全球最大的物流公司之一使用图数据库建立包裹的实时路由，一家大型航空公司使用图处理其多媒体内容元数据，一家顶尖金融公司基于Neo4j完全改写了其信息系统基础设施。图数据库在几年前还鲜为人知，而如今已广泛应用于医疗、零售、石油和天然气、媒体、游戏，以及更多的领域，并以爆炸式的速度繁荣发展。
这些想法发展出一种新的工具—通用数据库管理技术，即包含关联数据且支持图的思想。这就是我在1999年挣扎于关系型数据库时所希望找到的现成的可用工具。
我希望本书能很好地将图数据库技术这个新兴世界介绍给你，同时希望本书能鼓舞你在下一个项目中使用图数据库，这样你也将能解开图的非凡力量。祝你好运！
——Emil Eifrem
Neo4j联合创始人，NeoTechnology公司CEO
[1] 年轻读者可能会震惊曾经存在一个没有Google的时代。是的，恐龙曾经统治地球，而搜索引擎只有Altavista、Lycos和Excite这些，我们主要用它们在互联网上寻找可以购买宠物食品的电子商务网站。
图数据库应对的是当今一个宏观商业世界的大趋势：凭借高度关联的数据中复杂而动态的联系获得洞察力并赢得竞争优势。无论我们想了解的是客户之间的联系，电话或数据中心网络元素之间的联系，娱乐产品制作者和消费者之间的联系，还是基因和蛋白质之间的联系，都会涉及大量的高度关联的数据。这些数据又会构成庞大的图，而理解和分析这些图的能力将成为公司在未来十年的核心竞争力。
对于任何达到一定规模或价值的数据，图数据库都是呈现和查询这些关联数据的最好方式。关联数据是这样的一种数据：它需要我们首先理解它的组成元素之间的关联方式。为了理解这个，很多时候我们需要去给这些事物之间的关联加以命名和限定。
尽管在一段时间以前一些大公司就已经意识到这个问题，并着手开发各自专有的图处理技术，但我们正处在一个技术全民化的时代。现如今，通用的图数据库已经成为现实，主流用户不必去投资建设自己的图架构，就可以享受关联数据带来的好处。
这次图数据和图思考复兴的伟大之处正在于图论本身并不是一个新事物。自18世纪欧拉创建了图论以来，数学家、社会学家、人类学家和其他领域工作者一直在研究和完善图论。然而，图论和图思考在信息管理中的应用却是最近几年的事情。那个时候，图数据库已经在社交网络、主数据管理（master data management）、地理空间、推荐系统以及其他领域帮我们解决了许多重要问题。有两股力量驱动我们对图数据库的日益关注：一股力量是那些获得巨大商业成功的公司，如Facebook、Google和Twitter，他们都将自己的商业模式紧紧地围绕在他们专有的图技术上；另一股力量就是通用的图数据库开始进入到技术领域里。
本书的目的是为技术实践者介绍图和图数据库，包括开发人员、数据库专业人士和技术决策者。阅读本书将会让你对图数据库有一个贴近实际的理解。我们将演示图模型如何“塑造”数据，以及如何用图数据库查询、推断、理解和处理数据。我们讨论了多种适合用图数据库处理的问题，配以从实际应用中提取的用户案例，还将展示如何规划和实施一个图数据库解决方案。
本书使用下列排版约定。
此图标表示一个提示、建议或一般性注释。
此图标表示警告或慎用。
这本书的目的是帮助你完成工作。一般来说，如果这本书包括代码示例，你可以在你的程序和文档中使用本书的代码。你不需要联系我们申请权限，除非你要直接复制相当大的一部分代码。例如，在编写程序的过程中使用了本书中的几段代码，这不需要授权。售卖或者分发O'Reilly的图书示例光盘显然是需要授权的。引用本书或引用示例代码来回答问题是不需要授权的，但将本书的大量示例代码纳入产品的文档是需要授权的。
我们对你在使用时声明引用信息表示赞赏，但并不做强制要求。引用信息通常包括书名、作者、出版社和ISBN，如“Graph Databases by Ian Robinson, Jim Webber, and Emil Eifrem (O'Reilly). Copyright 2013 Neo Technoogy, Inc., 978-1-449-35626-2”。
如果你认为对示例代码的使用需要授权，请通过这个邮箱联系我们：permissions@oreilly.com。
如果你想就本书发表评论或有任何疑问，敬请联系出版社。
美国：
O'Reilly Media Inc.
1005 Gravenstein Highway North
Sebastopol, CA 95472
中国：
北京市西城区西直门南大街2号成铭大厦C座807室（100035）
奥莱利技术咨询（北京）有限公司
我们为本书提供了专门的网页，上面有勘误表、示例，以及其他额外的信息，可以通过http://oreil.ly/graph-databases访问该网页。
为本书提供建议和咨询技术问题，请发送邮件到bookquestions@oreilly.com。
想了解更多关于我们的书籍、课程、会议，以及新闻等信息，请登录我们的网站：http://www.oreilly.com。
我们的其他联系方式如下。
Facebook: http://facebook.com/oreilly
Twitter: http://twitter.com/oreillymedia
YouTube:http://www.youtube.com/oreillymedia
我们要感谢本书的技术审稿人Michael Hunger、Colin Jack、Mark Needham和Pramod Sadalage。
我们赞赏并感谢本书的编辑Nathan Jepson。
在本书成书的过程中，Neo Technology的同事极大地贡献了他们的时间、经验和努力。特别感谢Anders Nawroth对本书的工具组提供了宝贵的帮助；感谢Andrés Taylor对Cypher部分提供的热情帮助；感谢Philip Rathle对行文提供的建议和所做的贡献。
感谢Neo4j社区的所有人，感谢你们这些年对图数据库做出的许多贡献。
还要特别感谢我们的家人Lottie、Tiger、Elliot、Kath、Billy、Madelene和Noomi，谢谢他们付出的爱和支持。
虽然本书大部分内容是讨论图数据模型的，但这并不是一本关于图论的书。[1]使用图数据库并不需要太多的理论知识：只要知道什么是图就够了。记住这一点，下面来大体回顾一下我们对图的认识。
说得正式一点儿，图仅仅是顶点和边的集合，或者说更简单一点儿，图就是一些节点和关联这些节点的联系（relationship）的集合。图将实体表现为节点，实体与其他实体连接的方式表现为联系。我们可以用这个通用的、富有表现力的结构来建模各种场景，从宇宙火箭的建造到道路系统，从食物的供应链及原产地追踪到人们的病历，甚至更多其他的场景。
无处不在的图
在我们了解科学、政府和商业领域的数据集广泛多样性的过程中，图起到了极大的作用。现实世界完全不同于关系型数据库背后的基于表的模型，它是丰富的且相互之间充满关联：有些部分是统一而规则的，而其他部分是特殊的、不规则的。一旦理解了图，你就会发现图无处不在。比如，Gartner定义了商业世界的5个图—社交、意向、消费、兴趣和移动，并指出运用这些图的能力是一个“可持续的竞争优势”。
就拿Twitter来说，它的数据很容易表示为一张图。在图1-1中我们可以看到由互相关注的人组成的一个小的社交网络。联系是这里建立语义上下文的关键，也就是说，Billy关注了（FOLLOWS）Harry，反过来，Harry也关注了Billy，Ruth和Harry同样也是互相关注的，但是，尽管Ruth关注了Billy，但Billy却对他无动于衷。
图1-1 一个小型社交图
当然，实际的Twitter图比图1-1要大数亿倍，但它们的工作原理是一样的。在图1-2中，我们把Ruth发布的消息也包含到图里面来。
图1-2 发布消息
尽管图很简单，但图1-2还是展示出了图模型的表现力。我们很容易从中看出Ruth发布了一连串的消息。通过标记为CURRENT的联系可以找到最新的一条消息；PREVIOUS联系建立了消息时间线。
属性图模型
在讨论图1-2的过程中，我们也顺便提一下一个最流行的图模型变体—属性图（property graph）（在附录A中我们会更详细地讨论其他可替代的图数据模型）。属性图具有如下特征。
它包含节点和联系。
节点上有属性（键值对）。
联系有名字和方向，并总是有一个开始节点和一个结束节点。
联系也可以有属性。
对于大部分人来说，属性图模型是直观且容易理解的。不过简单归简单，使用图将有价值的见解融入到数据中的大多数场景却都可以用属性图来描述。
近年来，无数用于管理、处理和分析图的项目和产品纷纷涌入市场。技术选择的陡增使我们难以跟进这些工具并摸清它们之间的区别，即便对我们这些一直活跃在这个领域的人来说也是如此。本节的内容对理解新兴的图领域提供了一个“高空俯览”。
从1万英尺高空往下看，我们可以将图领域划分成以下两部分。
这类技术被称为图数据库，正是本书主要讨论的内容。它们和“通常的”关系型数据库世界中的联机事务处理（online transactional processing，OLTP）数据库是一样的。
这类技术被称为图计算引擎。它们可以和其他大数据分析技术看做一类，如数据挖掘和联机分析处理（online analytical processing，OLAP）。
我们可以从另一个视角去划分图领域，去观察各种技术使用的图模型。主流的图模型有3种，分别是属性图、资源描述框架（Resource Description Framework，RDF）三元组和超图。我们将会在附录A中对它们进行详细的说明。市场上常见的大多数图数据库使用的都是属性图模型，因此，在本书的剩余部分我们也将使用这一模型。
图数据库管理系统（以下将简称图数据库）是一种在线的数据库管理系统，它支持对图数据模型的增、删、改、查（CRUD）方法。图数据库一般用于事务（OLTP）系统中。相应地，它们也对事务性能进行了优化，在设计时通常考虑了事务完整性和操作可用性。
在研究图数据库技术时，有两个特性需要多加考虑。
一些图数据库使用原生图存储，这类存储是优化过的，并且是专门为了存储和管理图而设计的。不过并不是所有图数据库使用的都是原生图存储，也有一些图数据库会将图数据序列化，然后保存到关系型数据库或面向对象数据库，或是其他通用数据存储中。
一些定义要求图数据库使用免索引邻接，这意味着，关联节点在数据库中物理意义上“指向”彼此[2]。如果看得更远一点：站在用户的角度，任何看起来像是图数据库的都可以称为图数据库（比如说，提供了对图数据模型的CRUD操作的数据库）。然而，我们得承认这个事实，免索引邻接带来巨大的性能优势是其他数据库无法比拟的，因此我们使用原生图处理来代表使用免索引邻接的图数据库。
需要注意的是，原生图存储和原生图处理并不一定比其他方式更好或更差—这不过是典型的工程取舍而已。原生图存储的好处是，它的栈是专门为性能和扩展性设计建造的。但相对的，非原生图存储通常建立在非常成熟的非图后端（如MySQL）之上，运维团队对它们的特性烂熟于心。原生图处理（无索引邻接）虽然在遍历查询时性能优势很大，但代价是一些非遍历类的查询会比较困难，而且还要占用巨大的内存。
与那些需要额外增加像外键这样的属性或者使用map-reduce这样的额外处理来推测实体间关联的数据库管理系统不同，联系在图数据模型中是“一等公民”。图数据库通过将节点和联系的简单抽象组装为相互关联的结构，使我们能够建造任意复杂的模型，来形象地映射我们的问题域。比起那些传统的关系型数据库和其他NoSQL存储，我们所得到的模型更简单，也更具表现力。
根据其存储和处理模型不同，图1-3生动形象地展示了现在市场上的一些图数据库。
图1-3 图数据库概览
图计算引擎技术使我们可以在大数据集上使用全局图算法。图计算引擎主要用于识别数据中的集群，或是回答类似于“在一个社交网络中，平均每个人有多少联系？”这样的问题。
因为偏重于全局查询，图计算引擎通常为扫描和批处理大规模信息做过优化，在这个方面，它们和其他批分析技术（如在关系型数据库世界中大家都很熟悉的数据挖掘和OLAP）类似。只有一部分图计算引擎有自己的图存储层，其他的（几乎可以说大部分）则只完全关注于如何处理外部传入的数据和返回结果。
图1-4展示了一个通用的图计算引擎部署架构。该架构包括一个带有OLTP属性的记录系统（SOR）数据库（如MySQL、Oracle或Neo4j），它给应用程序提供服务，请求并响应应用程序在运行中发送过来的查询。每隔一段时间，一个抽取、转换和加载（ETL）作业就会将记录系统数据库的数据转入图计算引擎，供离线查询和分析。
图1-4 典型图计算引擎部署的示意图
图计算引擎多种多样。最出名的有内存的、单机的图计算引擎Cassovary和分布式的图计算引擎Pegasus和Giraph。大部分分布式图计算引擎基于Google发布的Pregel白皮书，其中讲述了Google如何使用图计算引擎来计算网页排名。
本书重点关注图数据库
通过前面的部分，我们对图领域有了一个大致的了解。在这之后，本书将主要关注图数据库。我们的目标始终是试图向读者解释清楚图数据库的概念。我们会在适当的时候穿插一些例子来说明这些概念。这些例子都来自于我们使用属性图模型和Neo4j数据库开发解决方案的过程中获得的经验。读者不必在意我们的例子中使用了什么具体的图模型或图数据库，这些关键概念对于其他的图数据库同样适用。
虽然事实上我们可以将任何东西都建模成图，但我们生活在一个很现实的世界里，它充满了预算限制、项目限期、企业标准，还有商业化的技术选型。图数据库提供了强大而新颖的数据建模方法，但它本身却无法为其能够替换那些已经享有盛誉并被用户充分认识的数据平台提供足够的理由。必须要有一个直接而明显的好处，人们才会使用它。对于图数据库来说，这个动机可以用一系列用例和数据模式来说明：采用图的方案，性能可以提升一个甚至几个数量级，而且比起聚合的批处理，其延迟也小很多。除此之外，图数据库还提供极其灵活的数据模型，这也和当今敏捷软件交付实践推崇的交付模式相一致。
其中一个充分的理由就是，与关系型数据库和NoSQL存储处理关联数据相比，选择图数据库会有绝对的性能提升。随着数据集的不断增大，关系型数据库处理密集join（join-intensive）查询的性能也会随之变差，而图数据库则不然。在数据集增大时，它的性能趋向于保持不变，这是因为查询总是只与图的一部分相关。因此，每个查询的执行时间只和满足查询条件的那部分遍历的图的大小（而不是整个图的大小）成正比。
作为开发者和数据架构师，我们希望根据问题域决定如何连接数据。这样，就不需要在对数据的真实模样和复杂度了解最少的时候，被迫预先做出决定。随着我们对问题域了解的加深，结构和schema会自己浮现出来。图数据库正中我们下怀。正如我们在第3章中将要展示的，图数据模型表示和适应业务需求的方式，使IT部门终于可以跟得上业务的变化速度。
图天生就是可扩展的，这意味着我们可以对一个已经存在的结构增加不同种类的联系、新节点和新子图，而不用担心破坏已有的查询或应用程序的功能。这些特点对于开发者的生产力和项目风险一般都有积极的意义。同时由于图模型的灵活性，我们不必在项目最初就穷思竭虑地把领域中的每一个细枝末节都考虑到模型中—这种做法在不断变化的业务需求面前，简直就是蛮干。图的天然可扩展性也意味着我们会做更少的数据迁移，从而降低维护开销和风险。
通过使用与当今增量及迭代的软件交付实践相吻合的技术，我们希望能够就像改进应用程序的其他部分一样改进我们的数据模型。现代图数据库还让我们拥有平滑的开发方式，配以优雅的系统维护。尤其是图数据库天生不需要schema，再加上其API和查询语言的可测性，使我们可以用一个可控的方式来开发应用程序。
同时，正是因为图数据库不需要schema，所以它缺少以schema为导向的数据管理机制，即在关系世界中我们已经熟知的机制。但这并不是一个风险，相反，它促使我们采用了一种更可见的、可操作的管理方式。正如我们在第4章会讲到的，图数据库的管理通常作用于编程方式，利用测试来驱动数据模型和查询，以及依靠图来断言业务规则。这不再是一个有争议的做法，事实上这已经比关系型开发应用更广了。图数据库开发方式非常符合当今的敏捷软件开发和测试驱动软件开发实践，这使得以图数据库为后端的应用程序可以跟上不断变化的业务环境。
本章介绍了属性图模型，在表示关联数据上，它简单却传神。属性图用生动而灵活的方式捕捉复杂的领域，与此同时，图数据库则使我们可以运用图模型以更加简单的方式开发应用程序。
在下一章中，我们将更详细地探讨不同的技术是怎样应对关联数据带来的挑战的，从关系型数据库开始，到聚合NoSQL存储，最后到图数据库。在讨论的过程中，我们将看到为什么图和图数据库是建模、存储和查询关联数据的最佳方式。之后的几章将会展示如何设计和实施一个以图数据库为基础的解决方案。
[1] 关于图论的介绍，请参考Richard J. Trudeau的《Introduction to Graph Theory》（Dover，1993）和Gary Chartrand的《Introductory Graph Theory》（Dover，1985）。如果想要了解图是怎样给复杂的时间和行为提供洞察力的，请参考David Easley和Jon Kleinberg的《Networks, Crowds, and Markets: Reasoning about a Highly Connected World》（Cambridge University Press，2010）。
[2] 参考Rodriguez, M. A.和Neubauer, P.的《The Graph Traversal Pattern》（2010）。
我们生活在互联的世界中。为了发展进步，我们需要理解并影响所处的网络。
如今的技术是如何处理关联数据的呢？本章关注于关系型数据库和聚合NoSQL存储如何管理图和关联数据，并比较这些数据库或存储与图数据库在处理图和关联数据方面的性能。对NoSQL有兴趣的读者可以深入阅读附录中描述的4种主流NoSQL数据库。
数十年来，开发者试图使用关系型数据库处理关联的、半结构化的数据集。关系型数据库设计之初是为了处理纸质表格以及表格化结构—有些方面关系型数据库做得非常好—它们试图对这种实际中的特殊联系进行建模。然而讽刺的是，关系型数据库在处理联系上做得却并不好。
联系确实存在于关系型数据库自身的术语中，但只是作为连接表的手段。前面章节在对关联数据的讨论中曾经提到，我们经常需要对连接实体的联系进行语义的区分，同时限制它们的使用。关联关系什么也做不了。更糟糕的是，随着离群数据（outlier data）的成倍地增加，数据集的宏观结构将愈发复杂和不规整，关系模型将造成大量表连接、稀疏行和非空检查逻辑。关系世界中连通性的增强都将转化为连接操作的增加，这会阻碍性能，并使已有的数据库难以响应变化的业务需求。
图2-1展示了一个以客户为中心的、事务型应用程序存储顾客订单的关系模式（relational schema）。
这种schema的设计对该应用程序产生了很大影响，使有些查询非常简单，而有些异常困难。
图2-1 语义联系隐藏在关系型数据库中
关系型数据库在强关联领域做着斗争。让我们通过社交网络领域中一些简单的和不那么简单的查询来理解关系型数据库中关联查询的成本吧。
图2-2展示了一个记录朋友关系的简单的连接表设计。
图2-2 关系型数据库中对于朋友和朋友的朋友的建模
回答“谁是Bob的朋友？”这个问题很简单，如示例2-1所示。
示例2-1 Bob的朋友
SELECT p1.Person
FROM Person p1 JOIN PersonFriend
ON PersonFriend.FriendID = p1.ID
JOIN Person p2
ON PersonFriend.PersonID = p2.ID
WHERE p2.Person = 'Bob'基于这个示例数据，答案是Alice和Zach。这不是一个代价高昂或困难的查询，因为它使用了WHERE Person.person='Bob'，使得返回的行数是可预期的和有限的。
朋友关系不总是自反关系（reflexive relationship），因此在示例2-2中，需要回答示例2-1的反向查询：“谁是Bob的朋友？”
示例2-2 谁的朋友是Bob
SELECT p1.Person
FROM Person p1 JOIN PersonFriend
ON PersonFriend.PersonID = p1.ID
JOIN Person p2
ON PersonFriend.FriendID = p2.ID
WHERE p2.Person = 'Bob'这个查询的答案是Alice，很遗憾Zach不认为Bob是他的朋友。这个反向查询在实现上也很简单，但是数据库端的花销就略微大些了，因为所有的数据行都在表PersonFreiend中。
我们可以加入索引，然而仍会涉及代价高昂的间接层。当问题是“谁是我的朋友的朋友？”时就更麻烦了。SQL的层级结构使用了递归连接，这使得查询语法和计算都更加复杂，如示例2-3所示。（有些关系型数据库提供这种查询的语法糖—比如Oracle提供了函数CONNECT BY，它可以简化查询语句，但并不能降低底层的计算复杂度。）
示例2-3 Alice的朋友的朋友们
SELECT p1.Person AS PERSON, p2.Person AS FRIEND_OF_FRIEND
FROM PersonFriend pf1 JOIN Person p1
ON pf1.PersonID = p1.ID
JOIN PersonFriend pf2
ON pf2.PersonID = pf1.FriendID
JOIN Person p2
ON pf2.FriendID = p2.ID
WHERE p1.Person = 'Alice' AND pf2.FriendID <> p1.ID即使只是处理Alice的朋友的朋友们，而不是深入Alice的整个社交网络，这个查询计算也很复杂。当我们试图探究社交网络时，问题则更复杂，代价也更高。虽然“谁是我的朋友的朋友们？”这样的问题还是可能在合理的时间内通过查询得到答案，但是当查询延伸到第4度、第5度或第6度的朋友关系时，由于递归的连表查询使此时的时间空间复杂度非常高，从而使查询的效率严重恶化。
无论试图在关系型数据库中对关联建模还是查询关联，结果都与我们的愿望完全不同。除了之前指出的查询和计算复杂度以外，我们还得去处理schema这个双刃剑。很多时候，schema被证明是死板和脆弱的。死板表现在：我们需要在创建稀疏表的同时在代码中处理异常情况—一切只是因为没有一个能够容纳我们所用到的各类数据的通用的schema。这在增加了耦合的同时也摧毁了其貌似存在的凝聚力。脆弱表现在：当应用程序发生变化时，需要增加额外的工作从一个schema迁移到另一个schema。
大多数NoSQL数据库—无论是键值数据库、文档数据库，还是基于列的数据库—存储的都是无关联的文档/值/列，因此很难将它们用于关联数据和图。
对这些数据库来说，一种广为认知的添加联系的策略是在某个聚合数据（aggregate）中嵌入另一个聚合数据标识符，即添加外键。然而这需要在应用层连接聚合数据，其代价极速增加。
当我们着眼于聚合存储模型（aggregate store model）时，如图2-3所示，我们联想到了联系。看到开头为user: Alice的记录中有对订单的引用order: 1234时，我们推断user: Alice和order: 1234之间存在关联。而这给了我们错误的希望：我们可以使用键值对来管理图。
在图2-3中，我们看到一些属性值确实引用了数据库中其他的聚合数据。然而将这些引用转化为可导航的结构并非是没有代价的，因为聚合数据之间的联系并非数据模型中的一等公民—多数聚合存储只是以内嵌映射结构的方式装饰在聚合数据之内。相反，应用程序使用数据库时必须从这种扁平的、无关联的数据结构中建立起联系。我们还必须确保应用程序能够随着剩余数据的变化更新或删除外部聚合引用，假如不这样做，存储将积累无用的引用，从而破坏数据的质量和查询性能。
图2-3 聚合存储模型中联系的具体化
Riak中的指针（Links）和查找（Walking）
Riak键值存储引擎允许使用指针（Link）元数据去扩展每个存储的值。指针都是单向的，从一个存储的值指向另一个。Riak允许查找（Walk）（Riak术语）任何数量的指针，从而一定程度上将数据模型关联起来。然而，Riak的指针查找是通过map-reduce驱动的，这一定程度上会有延迟。与图数据库不同，这种指针的连接仅适用于简单的图结构编程，对于通用的图算法就不适用了。
这种方案还有另一个弱点。由于没有反向指针（当然，外部聚合引用的指针不是自反的），数据库丧失了运行其他有趣的查询的能力。比如在图2-3中，想要知道是谁买了某种商品（也许问这个问题的目的是想要基于客户资料进行推荐）就是一个代价高昂的操作。想要回答这类问题，我们可能得通过导出数据集并在外部计算框架（如Hadoop）上运行它们来暴力地获得结果。或者只能回过头将外部聚合引用反向插入，随后才能查询结果。无论哪种方法，结果都不是直接的，都是潜在的。
人们很容易认为聚合存储和图数据在关联数据这方面的功能是等同的。但其实不是这样的。聚合存储并不维护关联数据的一致性，也不提供免索引邻接（index-free adjacency），即元素直接与其邻居相连。因此未解决数据关联问题，聚合存储必须使用天生的潜在的方法在数据模型之外创建和查询联系。
让我们看看它们的局限性是如何表现的。图2-4展示了一个使用聚合存储来实现文档存储的小型社交网络。
图2-4 使用聚合存储编码的小型社交网络
通过这种结构，可以很容易地找到用户的直接朋友—假设应用程序一直在努力确保存储在friends属性中的标识符与数据库中的其他记录的ID保持一致。在这种情况下，我们可以简单地通过它们的ID检索直接朋友，这需要对每个朋友进行大量索引查找，但不需要对整个数据集暴力扫描。这样做我们会发现，Bob认为Alice和Zach是他的朋友。
但朋友关系不总是自反的。如果我们想问问“谁的朋友是Bob？”而不是“谁是Bob的朋友？”，问题就比较难以回答了。在这种情况下，我们唯一的选择是暴力扫描整个数据集，从而在所有friends条目中寻找到包含Bob的条目。
O符号和暴力计算
我们用O符号作为描述一个算法的性能随数据集的大小而变化的简写方式。O(1)算法表示性能的时间复杂度为常数时间，也就是说，该算法与数据集大小无关，无论数据集大小如何，执行算法所花时间都是相同的。O(n)算法表示性能的时间复杂度为线性时间，当数据集增加一倍，执行算法所花时间也会增加一倍。O(log n)算法表示性能的时间复杂度为对数时间，当数据集增加一倍，执行算法所花时间增加一个固定的量。在起步阶段，随着数据集的增大，其所花时间的增加相对很多，但数据集变得非常大的时候，时间的增加会渐渐消失趋于稳定。O(m log n)算法表示的时间复杂度是本书所考虑的最差情况。在O(m log n)的算法中，当数据集增加一倍时，执行时间会在加倍的同时有额外的增加，其增加量与数据集中元素数目成正比。
暴力计算整个数据集的时间复杂度是O(n)，因为在数据存储中所有的即n个聚合数据都需要加以考虑。这对于大多数合理规模的数据集来说代价过高，在这里我们要选择一个时间复杂度为O(log n)的算法（这很大程度上是高效的，因为它在每次迭代时能够丢弃掉一半的潜在工作量）或者复杂度更低的算法。
相反，图数据库对于同一个查询提供恒定的查找顺序。在这种情况下，我们只需在图中找到表示Bob的节点，然后寻找任何friend的入度联系，这些联系连接的节点表示那些认为Bob是他们的朋友的人。这比暴力扫描的代价小得多，因为它只和网络中很少的节点相关，即，那些和Bob关联的节点。当然，如果所有人都认为Bob是他们的朋友，我们还是会遍历到整个数据集。
为了避免处理整个数据集，我们可以增加反向指针，但这会反规范化存储模型。通过为每个用户添加另一个属性，也许可以称为friended``_``by，我们可以列出与该用户相关联的入度朋友关系。但这不是没有代价的。对于起点数据，我们要因写入延迟增加初始成本和后续成本，还要为存储额外的元数据增加磁盘使用开销。最重要的是，因为每一跳（hop）都需要通过一次索引查找，所以遍历指针的代价仍然很高。这是因为聚合数据没有局部性这个概念，它不像图数据库那样通过真实的（而不是具体化的）联系自然地提供免索引邻接。如此，通过实现图结构之上的非原生存储，我们获得了局部连通性的好处，但却引入了巨大的开销。
当遍历涉及比一跳更深的时候，这种巨大的开销被放大了。朋友关系是足够简单的，然而想象一下，当试图实时地计算朋友的朋友，或是朋友的朋友的朋友时，这类数据库就不合时宜了，因为遍历一个虚假的联系的代价并不小。这不仅限制了你扩大社交网络的机会，也减少了有益的推荐，错过数据中心的故障设备，并让欺诈采购活动成为漏网之鱼。许多系统试图去维护类图的计算处理，但仍很难避免要分批处理，并不能按照用户需求提供实时的交互。
前面的例子处理了隐式的关联数据。作为用户，我们推断实体之间的语义相关性，但数据模型与数据库本身却忽视这些关联。为了弥补这一点，我们的应用程序必须着手创建一个扁平的、无连接的数据之外的网络，然后再处理那些由反规范化存储导致的缓慢查询和延迟写入。
我们真正想要的是一个全景图，包括元素之间的关联。与我们之前看到的不同，在图的世界中，关联数据被存储为关联数据。业务领域中存在的关联，在数据中也有，如图2-5所示的社交网络。
图2-5 在图中的朋友、同事、工人以及（单相思）恋人的简单建模
在这个社交网络中，有如此多的实际情景中的关联数据，但实体之间的关联并没有表现得与业务领域一致—领域是半结构化的。社交网络是一个非常流行的密集关联、半结构化的网络的例子，它不该被作为一个普适schema，也不该被分割成多个无关联的聚合数据。这个简单的朋友网络已经在规模上变大（潜在的朋友关系的距离已经深达6度），并且在表现力上变得丰富。图模型的灵活性使我们能增加新的节点和新的联系，与此同时不影响现有网络，也不用做数据迁移—原始数据和其意图都保持不变。
这个图为该网络提供了更丰富的信息。我们可以看到谁LOVES（爱着）谁（无论爱是否是单相思的），也可以看到谁是谁的COLLEAGUE_OF（同事），谁是所有人的BOSS_OF（老板）。我们可以看到谁没有市场了，因为他们和别人是MARRIED_TO（结婚）联系。我们甚至可以在其他社交网络中发现不善交际的元素，用DISLIKES（不喜欢）联系来表示。有了通过我们所掌握的这个图，我们现在就可以看看图数据库在处理关联数据时的性能优势了。
图中的关系自然地形成了路径。查询图或是遍历图都涉及路径。由于从根本上数据模型是面向路径的，多数基于路径的图数据库的操作都与数据本身的呈现高度一致，因此它们极为高效。在Neo4j in Action一书中，Partner和Vukotic使用关系存储和Neo4j进行实验。实验通过对比表明，在处理关联数据方面，图数据库比关系存储要快得多。
Partner和Vukotic的实验试图在一个社交网络里找到最大深度为5的的朋友的朋友。假设随机选择两个人，是否存在一条路径，使得关联他们的关系长度最多为5？对于一个包含100万人，每人约有50个朋友的社交网络，结果明显表明，图数据库是用于关联数据的最佳选择，如表2-1所示。
表2-1 在关系型数据库和Neo4j中寻找扩展朋友的性能对比
| 深度 |
关系型数据库的执行时间（s） |
Neo4j的执行时间（s） |
返回的记录条数 |
|---|---|---|---|
| 2 |
0.016 |
0.01 |
～2500 |
| 3 |
30.267 |
0.168 |
～110 000 |
| 4 |
1543.505 |
1.359 |
～600 000 |
| 5 |
未完成 |
2.132 |
～800 000 |
在深度为2时（即朋友的朋友），假设在一个在线系统中使用，无论关系型数据库还是图数据库，它们的执行时间都表现得足够好。虽然Neo4j的查询时间为关系数据库的2/3，但终端用户很难注意到两者间毫秒级的时间差异。当深度为3时（即朋友的朋友的朋友），很明显关系型数据库无法在合理的时间内实现查询：一个在线系统无法接受30 s的查询时间。相比之下，Neo4j的响应时间则保持相对平坦：执行查询仅需要不到1 s，这对在线系统来说足够快了。
在深度为4时，关系型数据库表现出很严重的延迟，使其无法应用于在线系统。Neo4j所花时间也有所增加，但其时延在在线系统的可接受范围内。最后，在深度为5时，关系型数据库所花时间过长以至于没有完成查询。相比之下，Neo4j则在2 s左右的时间就返回了结果。在深度为5时，事实证明几乎整个网络都是我们的朋友：因此在很多实际用例中，我们可能需要修剪结果，并进行时间控制。
聚合存储和关系型数据库对于超出合理规模的集合操作表现得都不太好。当我们试图从图中挖掘路径信息时（比如朋友的朋友那个例子），操作慢了下来。我们并非想要贬低聚合存储和关系型数据库，它们在各自所擅长的方面有很好的技术能力，但在管理关联数据时却无能为力。任何超出寻找直接朋友或是寻找朋友的朋这样的浅遍历的查询，都将因为涉及的索引的数量而使查找变得缓慢。而图数据库由于使用了免索引邻接，确保了遍历关联数据是非常迅速的。
社交网络这个例子有助于说明不同的技术是如何处理关联数据的，但它是否是一个有效的用例呢？我们是否真的需要寻找这样远的“朋友”呢？也许不是。但将社交网络替换为任何其他领域时，你会发现我们在性能、建模和维护方都能面获得类似的好处。无论是音乐还是数据中心管理，无论是生物信息还是足球统计，无论是网络传感器还是时序交易，图都能对这些数据提供强有力而深入的理解。让我们来看看另一个图在当代的应用：基于用户自己的购买历史和他的朋友、邻居以及其他喜欢他的人的购买历史为他推荐商品。这个例子中，我们能将用户生活方式中多个独立的方面汇集起来，做出准确而有商业意义的推荐。
图2-6 用图建模的用户订单历史
首先，我们将用户的购买历史建模为关联数据。这在图中很简单，只需将用户和她的订单链接起来，然后我们再将这些订单链接为购买历史，如图2-6所示。
图2-6所示的图深入洞察了客户行为。我们可以看到用户已经PLACED（订购）的所有订单，同时可以容易地推出每个订单CONTAINS（包含）了什么。到目前为止一切顺利，重要的是，我们丰富了图，使其能支持各种熟知的访问模式。例如，用户往往希望看到自己的订单历史，因此我们在图中增加一个链表结构，这样我们可以通过向外的MOST_RECENT（最近）联系找到用户最近的订单。随后，我们可以通过迭代该链表，沿着每个PREVIOUS（上一个）联系回溯到更早的订单。如果我们希望找到更近的订单，我们则可以反向寻找PREVIOUS联系，或者添加一个反向的NEXT（下一个）联系。
现在我们可以开始进行推荐了。如果我们发现买草莓冰淇淋的用户还购买了意大利咖啡豆，我们就可以推荐那些通常只买冰淇淋的用户也去买意大利咖啡豆。虽然我们通过遍历大量订单保证了草莓冰淇淋和咖啡豆间的强相关性，但这不只过是一个一维的推荐，我们可以做得更好。为了提高图的能力，我们可以将图与其他领域的图连接起来。由于图天然是多维结构，所以可以更直接地提问更复杂的问题，以此获得市场需要微调的部分。例如，我们可以通过图知道“住在某个用户附近、喜欢意式咖啡但不喜欢球芽甘蓝的人们所喜欢的冰淇淋的口味都有哪些？”
为了解释数据，我们需要考虑反复购买同一商品的用户在多大程度上象征着他喜欢这款商品。但如何才能定义“住在附近”？事实证明，地理坐标最应该用图来建模。最流行的表示地理坐标的结构被称为R树。R树是描述有边界区域的类图索引。使用这样的结构可以描述地理区域的重叠层次。例如，我们可以陈述一个事实，伦敦在英国，邮编为SW111BD的地方在巴特西，这是伦敦的一个区域，伦敦在英格兰的东南部，而英格兰在英国。由于英国的邮政编码粒度很细，因此可以把邮编作为标准来界定有相似口味的目标人群。
在SQL中或是聚合存储中写这样的模式匹配查询都非常困难，并且其查询性能都很不好。而图数据库在这方面做了优化，能够在这类遍历和模式匹配查询方面提供精确到毫秒级别的响应。此外，多数图数据库提供了适合表达图结构和图查询的查询语言。下一章我们将讲解Cypher，这是一个适合描述图的模式匹配语言。
除了可以用例子中的图向用户进行推荐，我们还能借此使卖方获益。例如，对于某些购买模式（商品、典型订单的价格等)，我们可以确定一个特定的事务是否是潜在的欺诈。通过图可以很容易地识别特定用户的非常规模式，于是能够将其标记出来并进一步关注（可以使用关于图的数据挖掘文献中的众所周知的相似性度量），从而减少卖方的风险。
从数据从业者的角度来看，很明显，图数据库是处理复杂的、半结构化的、紧密关联的数据的最好的技术，也就是说，对于如此复杂的数据，使用别的方式处理远不如使用图。
我们在本章已经看到，关系型数据库和NoSQL数据存储中的关联需要开发人员在应用程序层实现数据处理，而相比之下，关联在图数据库中则是一等公民。下一章我们将详细地描述图建模。
