我们之前看到，多对多关系是不同数据模型之间的重要区别特征。 如果您的应用程序主要具有一对多关系（树状结构化数据）或者记录之间没有关系，则文档模型是适当的。
但是如果多对多关系在您的数据中非常常见呢？ 关系模型可以处理多对多关系的简单情况，但随着数据中的连接变得更加复杂，开始将数据建模为图形变得更自然。
一个图由两种对象组成：顶点（也称为节点或实体）和边（也称为关系或弧）。 许多种数据都可以用图来模拟。 典型的例子包括：
社交图表：顶点是人，边缘表示哪些人彼此认识。
网络图：顶点是网页，边缘表示指向其他页面的HTML链接。
公路或铁路网络：顶点是连接点，边线代表它们之间的道路或铁路线。
众所周知的算法可以对这些图进行操作：例如，汽车导航系统搜索道路网络中两点之间的最短路径，PageRank可用于网络图确定网页的受欢迎程度，从而确定在搜索结果中的排名。
在刚刚给出的例子中，图中的所有顶点代表相同类型的事物（人，网页或交叉路口）。 然而，图并不限于这种同类数据：图的同样强大的用途是提供一种将完全不同类型的对象存储在单个数据存储中的一致方式。 例如，Facebook维护一个包含许多不同类型的顶点和边的单个图：顶点代表用户创建的人，位置，事件，签到和评论; 边缘指示哪些人是彼此的朋友，哪些地点发生在哪个位置，谁评论了哪个帖子，谁参加了哪个事件等等。
在本节中，我们将使用图2-5中显示的示例。 它可以来自社交网络或家谱数据库：它显示了两个人，来自爱达荷州的Lucy和法国Beaune的Alain。 他们已婚并住在伦敦。
图2-5. 图形结构数据的示例（框表示顶点，箭头表示边）
有几种不同的，但相关的方法来构建和查询图表中的数据。 在本节中，我们将讨论属性图模型（由Neo4j，Titan和InfiniteGraph实现）和三元组模型（由Datomic，AllegroGraph等实现）。 我们将看图的三种声明式查询语言：Cypher，SPARQL和Datalog。 除此之外，还有命令式图形查询语言，如Gremlin和图形处理框架（如Pregel）（请参阅第10章）。
属性图
在属性图模型中，每个顶点由以下部分组成：
唯一的标识符
一组传出边缘
一组传入边缘
一组属性（键值对）
每个边缘包括：
唯一标识符
边缘开始的顶点（尾部顶点）
边缘结束的顶点（头顶点）
描述两个顶点之间关系类型的标签
一组属性（键值对）
如例2-2所示（此模式使用PostgreSQL json数据类型来存储每个顶点或边的属性），您可以将图商店想象为由两个关系表组成，其中一个用于顶点，另一个用于边。 头部和尾部顶点为每个边缘存储; 如果您想要一组顶点的输入或输出边，可以分别通过head_vertex或tail_vertex查询边缘表。
例2-2： 使用关系模式表示属性图
CREATE TABLE vertices (
vertex_id integer PRIMARY KEY,
properties json
);
CREATE TABLE edges (
edge_id integer PRIMARY KEY,
tail_vertex integer REFERENCES vertices (vertex_id),
head_vertex integer REFERENCES vertices (vertex_id),
label text, properties json
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);
这个模型的一些重要方面是：
任何顶点都可以有一条边与其他顶点连接。 没有限制哪种事物可以或不可以关联的模式。
给定任何顶点，您可以高效地找到它的输入边和输出边，并因此遍历图 - 即沿着一系列顶点链的路径 - 向前和向后。 （这就是为什么示例2-2在tail_vertex和head_vertex列上都有索引的原因。）
通过为不同类型的关系使用不同的标签，您可以在单个图中存储几种不同类型的信息，同时仍保持单独的数据模型。
这些特性为图形提供了很大的数据建模灵活性，如图2-5所示。 该图显示了一些在传统关系模式中难以表达的东西，例如不同国家的不同类型的区域结构（法国有省份和区域，而美国有县和州），历史怪癖，例如 一个国家内的国家（目前忽略主权国家和国家的错综复杂）以及不同的数据粒度（Lucy当前的居住地被指定为一个城市，而她的出生地仅限于一个州的级别）。
你可以想象延伸图表还包括许多关于露西和阿兰或其他人的其他事实。 例如，您可以用它来表示食物过敏（通过引入每个过敏原的顶点，以及人与过敏原之间的边缘来指示过敏），并将过敏原与一组顶点连接起来，以显示哪些过敏原 食物含有哪些物质。 然后你可以写一个查询来找出每个人吃的食物是否安全。 图表对于可演化性很好：当您向应用程序添加功能时，可以轻松扩展图形以适应应用程序数据结构的变化。
Cypher查询语言（The Cypher Query Language）
Cypher是属性图的声明性查询语言，为Neo4j图形数据库创建（它以电影The Matrix中的角色命名，与密码学中的密码无关）。
例2-3显示了将图2-5的左边部分插入图形数据库中的Cypher查询。 图的其余部分可以类似地添加，为了便于阅读而省略。 每个顶点都有一个符号名称，例如USA或Idaho，查询的其他部分可以使用这些名称在顶点之间创建边，使用箭头符号：(Idaho) -[:WITHIN]-> (USA)创建边 标记为WITHIN，Idaho为尾节点，USA为头节点。
例2-3。 图2-5中的数据子集，表示为Cypher查询：
CREATE
(NAmerica:Location {name:'North America', type:'continent'}),
(USA:Location {name:'United States', type:'country' }),
(Idaho:Location {name:'Idaho', type:'state' }),
(Lucy:Person {name:'Lucy' }),
(Idaho) -[:WITHIN]-> (USA) -[:WITHIN]-> (NAmerica),
(Lucy) -[:BORN_IN]-> (Idaho)
当图2-5的所有顶点和边被添加到数据库时，我们可以开始提出有趣的问题：例如，查找从美国移民到欧洲的所有人的姓名。 更确切地说，在这里我们想要找到所有在美国有一个BORN_IN边缘的顶点，还有一个LIVING_IN边缘到欧洲的一个位置，并返回每个顶点的name属性。
例2-4展示了如何在Cypher中表达该查询。 在MATCH子句中使用相同的箭头符号来查找图中的模式：(person) -[:BORN_IN]-> () 通过标记为BORN_IN的边匹配任何两个相关的顶点。 该边的尾部顶点被绑定到变量person，并且顶部顶点未被命名。
例2-4：Cypher查询寻找从美国移民到欧洲的人
MATCH
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
(person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name
该查询可以被读取如下：
找到满足以下两个条件的任何顶点（称之为人）：
人有一个传出的BORN_IN边缘到某个顶点。 从该顶点开始，您可以沿着一系列传出的WITHIN边直到最终到达类型为Location的顶点，其名称属性等于“美国”。
同一个人顶点也有一个传出的LIVES_IN边缘。 在该边缘之后，然后是一系列传出的WITHIN边缘，最终到达类型为Location的顶点，其名称属性等于“Europe”。 对于每个这样的人物顶点，返回name属性。
有几种可能的方式来执行查询。 这里给出的描述表明，您首先扫描数据库中的所有人，检查每个人的出生地和居住地，然后仅返回符合条件的人。
但是等价地，您可以从两个位置顶点开始并向后工作。 如果名称属性上有一个索引，则可以高效地找到代表美国和欧洲的两个顶点。 然后，您可以继续查找所有进入的WITHIN边缘，分别在美国和欧洲查找所有位置（州，地区，城市等）。 最后，您可以查找可通过位于某个顶点的传入BORN_IN或LIVES_IN边缘找到的人员。
对于声明式查询语言来说，典型的情况是，编写查询时不需要指定这样的执行细节：查询优化器会自动选择预测效率最高的策略，因此您可以继续编写其余的你的请求。
SQL中的图型查询（Graph Queries in SQL）
例2-2建议可以在关系数据库中表示图数据。 但是，如果我们将图形数据放入关系结构中，我们是否也可以使用SQL查询它？答案是肯定的，但有一些困难。 在关系数据库中，您通常会事先知道在查询中需要哪些连接。 在图形查询中，您可能需要遍历可变数量的边缘，然后才能找到要查找的顶点 - 也就是说，连接数量并未提前确定。
在我们的例子中，这发生在Cypher查询中的()-[:WITHIN * 0 ..]->()规则中。 一个人的LIVES_IN边缘可以指向任何类型的位置：街道，城市，地区，地区，州等。城市可以位于一个地区内，州内的地区，国家内的州等 。LIVES_IN边可能直接指向您要查找的位置顶点，或者可能会在位置层次结构中删除多个级别。
在Cypher中，：WITHIN * 0 ..表示这个事实非常简洁：它意味着“遵循WITHIN边缘，零次或多次”。它就像正则表达式中的*运算符。
自SQL：1999以来，查询中可变长度遍历路径的思想可以使用称为递归公用表达式（WITH RECURSIVE语法）的方式来表示。 示例2-5显示了相同的查询 - 查找使用此技术（在PostgreSQL，IBM DB2，Oracle和SQL Server中受支持）从SQL移植到美国和欧洲的人员的姓名。 但是，与Cypher相比，语法非常笨拙。
例2-5。 与例2-4相同的查询，使用递归公用表达式在SQL中表达：
递归公用表达式在SQL中表达
1.首先找到名称属性值为“United States”的顶点，并将其作为顶点集in_usa中的第一个元素。
2.沿着集合in_usa中顶点的所有入口进行跟踪，并将它们添加到同一集合中，直到边缘内的所有入站都被访问完毕。
3.从name属性值为“Europe”的顶点开始，并建立顶点集in_europe。
4.对于集合in_usa中的每个顶点，请按照传入的born_in边缘来查找出生在美国某个地方的人。
5.同样，对于集合in_europe中的每个顶点，请按照传入的lives_in边缘来查找居住在欧洲的人。
6.最后，通过加入他们，将在美国出生的人与在欧洲居住的人相交。
如果相同的查询可以用一种查询语言的4行写入，但在另一个查询语言中需要29行，这只是表明不同的数据模型被设计为满足不同的用例。 选择适合您的应用程序的数据模型非常重要。
三元组和SPARQL
三元组大多相当于属性图模型，用不同的词来描述相同的想法。 不过值得讨论，因为有三元组的各种工具和语言，可以作为建立应用程序工具箱的重要补充。
在三元组中，所有信息都以非常简单的三部分语句形式存储（subject，predicate，object）。 例如，在triple (Jim, likes, bananas)中，Jim是subject，likes是predicate，而bananas是object。
三元组的主题相当于图中的一个顶点。 该对象是两件事之一：
原始数据类型中的值，例如字符串或数字。 在这种情况下，三元组的predicate和object相当于subject顶点上的属性的键和值。 例如，（lucy，age，33）就像属性{“age”：33}的顶点lucy。
图中的另一个顶点。 在这种情况下，predicate是图中的边，subject是尾部顶点，而object是顶点。 例如，在（lucy，marriedTo，alain）中，subject和object：lucy和alain都是顶点，而predicate：marriedTo是连接它们的边的标签。
示例2-6显示了与示例2-3中相同的数据，以称为Turtle的格式（称为Notation3（N3）的子集）的三元组形式写入。
@prefix : .
_:lucy a :Person.
_:lucy :name "Lucy".
_:lucy :bornIn
_:idaho.
_:idaho a :Location.
_:idaho :name "Idaho".
_:idaho :type "state".
_:idaho :within _:usa.
_:usa a :Location.
_:usa :name "United States".
_:usa :type "country".
_:usa :within
_:namerica.
_:namerica a :Location.
_:namerica :name "North America".
_:namerica :type "continent".
在这个例子中，图的顶点被写为：someName。 这个名字并不意味着这个文件以外的任何东西; 它的存在只是因为我们不知道哪个三元组指向同一个顶点。 当predicate表示边时，该object就是顶点，如：idaho：在：usa内。 当predicate是一个属性时，该object是一个字符串字面值，如：usa：name“United States”中所示。
一遍又一遍地重复相同的主题是相当重复的，但幸运的是，您可以使用分号来说明关于同一subject的多重内容。 这使得Turtle格式相当不错并且可读：参见例2-7。
例2-7： 示例2-6中写入数据的更简洁的方式：
@prefix : .
_:lucy a :Person; :name "Lucy"; :bornIn _:idaho.
_:idaho a :Location; :name "Idaho"; :type "state"; :within _:usa.
_:usa a :Location; :name "United States"; :type "country"; :within _:namerica.
_:namerica a :Location; :name "North America"; :type "continent".
语义网络
如果你阅读更多关于三元组的信息，你可能会被吸引到写有关语义网的文章中。 三元组模型完全独立于语义网络，例如，Datomic是一种三元组，但不声称与它有任何关系。但是，由于这两者在许多人的心目中如此紧密地联系在一起，我们 应该简要地讨论一下。
语义网络从根本上说是一个简单而合理的想法：网站已经将信息发布为文本和图片供人类阅读，为什么他们不把信息发布为计算机可读的机器可读数据呢？ 资源描述框架（RDF）旨在作为不同网站以一致格式发布数据的一种机制，允许来自不同网站的数据自动合并到一个数据网络中 - 这是一种全因特网“一切的数据库”。
不幸的是，语义网在21世纪初被过度使用，但到目前为止还没有显示出在实践中已经实现的任何迹象，这使得许多人对此非常愤世嫉俗。
但是，如果你仔细观察这些素材，那么语义Web项目中也有很多好的工作。 即使您没有兴趣在语义网上发布RDF数据，三元组也可以成为应用程序的良好内部数据模型。
RDF数据模型
我们在例2-7中使用的Turtle语言是RDF数据的可读格式。 有时RDF也是用XML格式编写的，它可以更详细地完成同样的事情 - 参见例2-8。 Turtle / N3是最好的选择，因为它更容易阅读，而像Apache Jena这样的工具可以根据需要在不同的RDF格式之间自动转换。
例2-8。 示例2-7的数据使用RDF / XML语法表示
RDF/XML语法
RDF有一些怪癖，因为它设计用于互联网范围内的数据交换。 三元组的主题，声明和对象通常是URI。 例如，声明可能是一个URI，如http://my-company.com/namespace#within或http://my-company.com/namespace#lives_in，而不仅仅是WITHIN或LIVES_IN。 这种设计背后的原因是，你应该能够将你的数据与其他人的数据结合起来，如果他们给单词或lives_in中的单词赋予不同的含义，你将不会得到冲突，因为它们的声明实际是http://other.org/foo#within和http://other.org/foo#lives_in。
从RDF的角度来看，URL http://my-company.com/namespace不一定需要解析任何东西，它只是一个命名空间。 为避免可能与http:// URL混淆，本节中的示例使用不可解析的URI，例如urn：example：within。 幸运的是，您只需在文件顶部指定一次该前缀，然后忘记它。
SPARQL查询语言
SPARQL是使用RDF数据模型的三重商店的查询语言（它是SPARQL协议和RDF查询语言的缩写，发音为“sparkle”）。它早于Cypher，并且由于Cypher的模式匹配是从SPARQL借用的，它们看起来非常相似。
与从前从美国转移到欧洲的人相同的查询 - 在SPARQL中比在Cypher中更加简洁（请参见示例2-9）。
例2-9。 与示例2-4相同的查询，用SPARQL表示：
PREFIX :
SELECT ?personName WHERE {
?person :name ?personName.
?person :bornIn / :within* / :name "United States".
?person :livesIn / :within* / :name "Europe".
}
结构非常相似。 以下两个表达式是等价的（变量以SPARQL中的问号开头）：
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (location) # Cypher
?person :bornIn / :within* ?location. # SPARQL
由于RDF不区分属性和边，而只是为两者使用声明，所以可以使用相同的语法来匹配属性。 在下面的表达式中，变量usa绑定到任何具有name属性，其值为字符串“United States”的顶点：
(usa {name:'United States'}) # Cypher
?usa :name "United States". # SPARQL
SPARQL是一种很好的查询语言 - 即使没有语义网络，它也可以成为应用程序内部使用的强大工具。
图形数据库与网络模型相比较
在第36页的“文档数据库是否重复历史记录？”中，我们讨论了CODASYL和关系模型如何相互竞争以解决IMS中的多对多关系问题。乍一看，CODASYL的网络模型看起来与图模型很相似。图表数据库是CODASYL的第二次出现，伪装？ 不，他们在几个重要方面有所不同：
•在CODASYL中，数据库有一个模式，用于指定哪种记录类型可嵌套在其他记录类型中。在图形数据库中，不存在这样的限制：任何顶点都可以具有任何其他顶点的边。这为应用程序适应不断变化的需求提供了更大的灵活性。
•在CODASYL中，达到特定记录的唯一方法是遍历其中的一条访问路径。在图形数据库中，可以通过其唯一ID直接引用任何顶点，也可以使用索引来查找具有特定值的顶点。
•在CODASYL中，记录的孩子是有序集合，因此数据库必须维护该订单（这对存储布局有影响）以及将新记录插入数据库的应用程序必须担心新记录的位置在这些集合中。在图形数据库中，顶点和边缘不是有序的（您只能在查询时对结果进行排序）。
•在CODASYL中，所有查询都是必要的，难以编写，并且很容易被架构中的更改破坏。在图形数据库中，如果需要，可以在命令式代码中编写遍历，但大多数图形数据库也支持高级声明式查询语言，如Cypher或SPARQL。
Datalog
Datalog是一种比SPARQL或Cypher更早的语言，在20世纪80年代由学者广泛研究。 它在软件工程师中并不为人所知，但它却很重要，因为它为后来的查询语言构建奠定了基础。
在实践中，Datalog在一些数据系统中使用：例如，它是Datomic的查询语言，Cascalog是用于在Hadoop中查询大型数据集的Datalog实现。
Datalog的数据模型与triple-store模型类似，有点泛化。 我们将它写成predicate(subject, object)，而不是将三元组写作（subject, predicate, object）。 例2-10显示了如何在Datalog中写入我们例子中的数据。
例2-10： 图2-5中的数据子集，表示为Datalog facts
name(namerica, 'North America').type(namerica, continent).
name(usa, 'United States').type(usa, country).within(usa, namerica).
name(idaho, 'Idaho').type(idaho, state).within(idaho, usa).
name(lucy, 'Lucy').born_in(lucy, idaho).
现在我们已经定义了数据，我们可以像之前一样编写相同的查询，如例2-11所示。 它看起来与Cypher或SPARQL中的等价物有点不同。 Datalog是Prolog的一个子集，如果您已经学习过计算机科学，您可能会了解到它。
例2-11。 与示例2-4相同的查询，在Datalog中表示。
within_recursive(Location, Name) :- name(Location, Name). /* Rule 1 */
within_recursive(Location, Name) :- within(Location, Via), /* Rule 2 */
within_recursive(Via, Name).
migrated(Name, BornIn, LivingIn) :- name(Person, Name), /* Rule 3 */
born_in(Person, BornLoc),
within_recursive(BornLoc, BornIn),
lives_in(Person, LivingLoc),
within_recursive(LivingLoc, LivingIn).
?- migrated(Who, 'United States', 'Europe').
*/* Who = 'Lucy'. */
Cypher和SPARQL利用SELECT立即跳转，但Datalog一次只需要一小步。 我们定义告诉数据库有关新声明的规则：在这里，我们定义了两个新的声明，在_recursive和migrated内。 这些声明不是存储在数据库中的三元组，而是它们来自数据或其他规则。 规则可以引用其他规则，就像函数可以调用其他函数或递归调用自己一样。 像这样，复杂的查询可以一次构建一小块。
在规则中，以大写字母开头的单词是变量，声明匹配如Cypher和SPARQL。 例如，name（Location，Name）与可变绑定Location = namerica和Name ='North America'的name（namerica，'North America'）匹配。
如果系统可以在 - 操作符的右侧找到所有声明的匹配项，则适用该规则。 当规则适用时，就好像将 - 的左边添加到数据库（用变量替换了它们匹配的值）。
因此，应用规则的一种可能方式是：
1.name(namerica, 'North America') exists in the database, so rule 1 applies. It generates within_recursive(namerica, 'North America').
2. within(usa, namerica) exists in the database and the previous step generated
within_recursive(namerica, 'North America'), so rule 2 applies. It generates
within_recursive(usa, 'North America').
3. within(idaho, usa) exists in the database and the previous step generated
within_recursive(usa, 'North America'), so rule 2 applies. It generates
within_recursive(idaho, 'North America').
通过重复应用规则1和2，within_recursive谓词可以告诉我们数据库中包含的所有North America（或任何其他位置名称）。 这个过程如图2-6所示。
图2-6. 确定Idaho在North America，使用来自美国的Datalog规则
现在规则3可以找到出生在BornIn某地的人，并住在LivingIn的某个地方。 通过查询BornIn ='United States'和LivingIn ='Europe'，并将该人作为变量Who，我们要求Datalog系统找出变量Who可以显示哪些值。 因此，最终我们得到与早先的Cypher和SPARQL查询相同的答案。
Datalog方法需要对本章讨论的其他查询语言进行不同的思考，但这是一种非常强大的方法，因为规则可以在不同的查询中进行组合和重用。 简单的一次性查询不太方便，但如果数据很复杂，它可以更好地应对。
概要（Summary）
数据模型是一个巨大的课题，在本章中我们快速浏览了各种不同的模型。 我们没有时间深入了解每个模型的所有细节，但希望总览足以激发您的兴趣，可更多地了解最适合您应用程序需求的模型。
从历史上看，数据开始被表示为一棵树（分层模型），但这对于表示多对多关系并不好，所以发明了关系模型来解决这个问题。 最近，开发人员发现某些应用程序也不适合在关系模型中使用。 新的非关系型“NoSQL”数据存储在两个主要方向上有分歧：
1.文档数据库 的目标是数据来自自包含文档以及一个文档与另一个文档之间的关系很少的用例。
2.图形数据库走向相反的方向，针对任何可能与一切有关的用例。
所有三种模型（文档，关系和图形）今天都被广泛使用，并且每个模型在其各自领域都很出色。 一个模型可以用另一个模型来模拟 - 例如，图形数据可以在关系数据库中表示 - 但结果往往很尴尬。 这就是为什么我们针对不同目的有不同的系统，而不是一个单一的万能解决方案。
文档和图形数据库有一个共同点，那就是它们通常不会为它们存储的数据强制执行模式，这可以使应用程序适应不断变化的需求变得更加容易。 但是，您的应用程序很可能仍然假定数据具有一定的结构; 这只是模式是明确的（强制写入）还是隐含的（在读取时处理）的问题。
每个数据模型都带有自己的查询语言或框架，我们讨论了几个示例：SQL，MapReduce，MongoDB的聚合管道，Cypher，SPARQL和Datalog。 我们还谈到了CSS和XSL/XPath，它们不是数据库查询语言，而是有有趣的相似之处。
尽管我们已经讨论覆盖了很多地方，但仍有许多数据模型未提及。 举几个简单的例子：
1.使用基因组数据的研究人员通常需要执行序列相似性搜索，这意味着需要一个非常长的字符串（代表DNA分子），并将其与大量相似但不相同的字符串数据库进行匹配。 这里所描述的数据库都不能处理这种用法，这就是为什么研究人员编写GenBank等专用基因组数据库软件的原因。
2.粒子物理学家数十年来一直在进行大数据类型的大规模数据分析，像大型强子对撞机（LHC）这样的项目现在可以工作数百PB！ 在这样的规模下，需要定制解决方案来阻止硬件成本从失控中解脱出来。
3.全文检索可以说是一种常用于数据库的数据模型。 信息检索是一本很大的专业主题，本书不会详细介绍，但我们将在第3章和第III部分介绍搜索索引。
我们暂时讨论到这。 在下一章中，我们将讨论在实施本章描述的数据模型时会发挥的一些权衡。
网友评论