1 关系型数据库缺少联系

• 关系型数据库设计之初是为了处理纸质表格以及表格化结构，然后在处理“关系（联系）”上做的却并不好

  • 经常需要对连接实体的联系进行语义的区分，并为其定义权重，但关联关系什么也做不了
  • 随着离群数据（outlier data）的成倍增加，数据集的宏观结构会越发复杂和不规整，关系模型将造成大量表连接、稀疏行和非空检查逻辑
  • 关系世界中连通性的增强都将转化为连接操作的增加，这会阻碍性能，并使已有的数据库难以响应变化的业务需求

• 关系模式（relational schema）设计对应用程序产生了很大影响，使有些查询非常简单，而有些异常困难

  • 如下表：

1569376334528.png

• 表连接增加了偶发复杂性，使得业务数据与外键元数据混杂起来
• 外键约束增加了额外的开发与维护成本，而目的仅仅是为了让数据库工作
• 带有空置列的稀疏表在代码中需要额外检查，尽管模式本身提供了相关支持
• 仅因为想要看客户买了什么就需要好几个昂贵的连接
• 反向查询(reciprocal query)的代价更高，
  • “有哪些客户买了某个商品” 比 “某个客户买了哪些商品”的代价还要高
  • 虽然可以引入索引，然而即使使用索引，随着递归程度的增加，如“哪些买这个商品的客户，也买了那个商品”，这样的递归问题的代价变得异常高昂

举例一个记录朋友关系的简单的连接设计，

• 表结构如下：

1569392222689.png

• 回到“谁是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'

• 该语句不是一个代价高昂或困难的查询，因为使用了“WHERE Person.person='Bob'”，使得返回的行数是可预期的和有限的
• 朋友不是自反关系（reflexive relationship），如前面问题的反向查询“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'

• 这个反向查询也很简单，但是数据库端的花销就略微大些，因为所有的数据行都在表PersonFriend中
• 虽然加入索引，然而仍会涉及代价高昂的中间层。如问题是“谁知Alice的朋友的朋友”
  • SQL的层级结构使用了递归连接，使得查询语法和计算都更加复杂
  • 虽然有数据库提供了这种查询的语法糖，如Oralce提供了函数 CONNECT BY，可以简化查询语句，但并不能降低底层的计算复杂度

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的朋友的朋友”这样的问题还是能在合理的时间内通过查询得到答案，但是当查询延伸到第4度、第5度或第6度的朋友关系时，由于递归的连表查询使此时的时间空间复杂度非常高，从而使查询的效率严重恶化

经过前面的分析，我们总结关系型数据库存在如下问题：

• 查询和计算复杂度高
• 模式太死板、太脆弱
  • 需要在创建稀疏表的同时，在代码中处理异常情况，因为没有一个能容纳我们所用到的各类数据的通用的模式
  • 增加了耦合度的同时也摧毁了其貌似存在的凝聚力
  • 当应用程序发生变化时，需要增加额外的工作从一个模式迁移到另一个模式

2 NoSQL数据库也缺少联系

NoSQL数据库如下都无关联的文档/值/列:

• 键值数据库
• 文档数据库
• 基于列的数据库

一种广为人知的添加联系的策略是在某个聚合数据（aggregate）中嵌入另一个聚合数据标识符，即添加外键，缺点是这需要在应用层连接聚合数据，其代价急速增加。

1569417382553.png

• 从上图我们可以看到一些属性值确实引用了数据库汇总的其他的聚合数据，然而将这些引用转化为可导航的结构并非没有代价
• 聚合数据之间的联系并非数据模型中的一等公民--多数聚合存储只是以内嵌映射结构的方式装饰在聚合数据之内
• 应用程序使用数据库时必须从这种扁平的、无关联的数据结构中建立起联系；还必须确保应用程序能够随着剩余数据的变化更新或删除外部聚合引用，否则存储将积累不用的引用，从而破坏数据的质量和查询性能
• 没有反向指针（外部聚合引用的指针当然不是自反的），数据库丧失了运行其他有趣的查询的能力，比如想查询谁买了某种商品，就是一个代价高昂的操作，可行的方式是：
  • 导出数据集并在外部计算框架（如Hadoop）上运行它们来暴力获得结果
  • 回头将外部聚合引用反向插入，随后才能查询结果
  • 但无论哪种方法，结果都不是直接的，而是隐含的

下面是一个用文档实现的使用聚合存储的小型社交网络：

1569886874366.png

• 通过ID检索到直接朋友，需要对每个朋友进行大量的索引查找，不需要对整个数据集进行暴力扫描。可以看出Bob认为Alice和Zach是他的朋友
• 但朋友的关系是不对称的，“谁的朋友是Bob”就难以回答了，唯一的选择是暴力扫描整个数据集，从而在所有friends条目中寻找到包含Bob的条目

为了避免处理整个数据集，我们可以增加反向指针，但这会违反规范化存储模型。

• 通过为每个用户添加第二个属性，可以称为friended_by，可以列出与该用户相关联的入度朋友关系
• 代价是对于 起点数据，要因写入延迟增加初始成本和后续成本，还要为存储额外的元数据增加磁盘开销
• 最重要的是，每一跳（hop）都需要通过一次索引查找，遍历指针的代价仍然很高
• 聚合数据没有局部性这个概念，不想图数据库那样通过真实的（而不是具体化的）联系自然的提供免索引邻接
• 总结来看，通过实现图结构之上的非原生存储，虽然获得了局部连通性的好处，但却引入了巨大开销，当遍历涉及两跳或更深的时候，这种巨大的开销被放大了

O符号作为描述一个算法的性能随数据集的大小而变化的简写方式。

• O(1)算法表示性能的时间复杂度为常数，即算法与数据集大小无关，无论数据集大小如何，执行算法所花时间都是相同的
• O(n)算法表示性能的时间复杂度为线性时间，当数据集增加一倍，算法所花时间也会增加一倍。
• O(log n)算法表示性能的时间复杂度为对数时间，当数据集增加一倍，执行算法所花时间增加一个固定的量。在起步阶段，随着数据集的增大，其所花时间的增加相对很多，但数据集变得非常大的时候，时间的增加会渐渐消失区域稳定
• O(m log n)算法表示的时间复杂度是最差的情况，当数据集增加一倍时，执行时间会在加倍的同时有额外的增加，其增加量与数据集中元素数目成正比

3 图数据库拥抱联系

应用程序必须着手创建一个扁平的、无连接的数据之外的网络，然后再处理那些有反规范化存储导致的缓慢查询和延迟写入。关联数据被存储为关联数据，只要问题域中存在关联，数据中就存在关联，如下所示：

在图中对朋友、同事、工人以及（单相思）恋人关系的简单建模

• 在这个社交网络中，有如此多的实际情景中的关联数据，但实体之间的关联在领域之间并没有表现得一致-----域是结构可变的
• 社交网络是一个非常流行的密集关联、结构可变的网络的例子，而不该作为一个普适模式，也不该被分割成多个无关联的聚合数据
• 图模型的灵活性使我们能增加新的节点和新的联系，与此同时不影响现有网络，也不用做数据迁移-----原始数据和其意图都保持不变
• 图中的关系自然地形成了路径，查询图或是遍历图都涉及路径
• 从根本上说，数据模型是面向路径的，多数基于路径的图数据库的操作都与数据模型本身呈现高度一致性，因此即为高效

图中的标签：

• 希望在网络中通过节点所扮演的角色对其进行分类，比如有些节点可能代表用户，而其他的代表订单或产品
• 在Neo4j中，使用labels表示节点在图中扮演的角色。由于一个节点在图中可以满足多钟不同角色，因此Neo4j允许用户对一个节点添加多个标签
• 对于一个包含100万人，每人约有50个朋友的社交网络，结果明显表面图数据库是用于关联数据的最佳选择

1570069070273.png

聚合存储和关系型数据库对于超出中等规模的集合操作表现得都不太好。

当我们试图从图中挖掘路径信息时，操作慢了下来。任何超出寻找直接朋友或是寻找朋友的朋友这样的浅遍历的查询，都将因为涉及的索引数量过的而是查找变得缓慢。

图数据库由于使用了免索引邻接，确保了遍历关联数据是非常迅速的

1570069647847.png

从数据从业者的角度来看，图数据库是处理如下特征数据集的最好技术：

• 复杂的
• 结构可变的
• 密集关联的

4 小结

关系型数据库和NoSQL数据存储中的关联需要开发人员在应用程序层实现数据处理，而相比之下，关联在图数据库中则是一等公民。