图模型

如我们之前所见，多对多关系是不同数据模型之间具有区别性的重要特征。如果你的应用程序大多数的关系是一对多关系（树状结构化数据），或者大多数记录之间不存在关系，那么使用文档模型是合适的。关系模型可以处理多对多关系的简单情况，但是随着数据之间的连接变得更加复杂，将数据建模为图形显得更加自然。

一个图由两种对象组成：顶点（vertices）（也称为节点（nodes）或实体（entities）），和边（edges）（也称为关系（relationships）或弧（arcs））。多种数据可以被建模为一个图形。典型的例子包括：

社交图谱：顶点是人，边指示哪些人彼此认识。
网络图谱：顶点是网页，边缘表示指向其他页面的 HTML 链接。
公路或铁路网络：顶点是交叉路口，边线代表它们之间的道路或铁路线。

可以将那些众所周知的算法运用到这些图上：例如，汽车导航系统搜索道路网络中两点之间的最短路径，PageRank 可以用在网络图上来确定网页的流行程度，从而确定该网页在搜索结果中的排名。这里图中的所有顶点代表了相同类型的事物（人，网页或交叉路口）。不过，图并不局限于这样的同类数据：同样强大地是，图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象。例如，Facebook 维护一个包含许多不同类型的顶点和边的单个图：顶点表示人，地点，事件，签到和用户的评论;边缘表示哪些人是彼此的朋友，哪个签到发生在何处，谁评论了哪条消息，谁参与了哪个事件，等等。

譬如下图可以从社交网络或系谱数据库中获得：它显示了两个人，来自爱达荷州的 Lucy 和来自法国 Beaune 的 Alain。他们已婚，住在伦敦。

有几种不同但相关的方法用来构建和查询图表中的数据。在本节中，我们将讨论属性图模型（由 Neo4j，Titan 和 InfiniteGraph 实现）和三元组存储（triple-store）模型（由 Datomic，AllegroGraph 等实现）。我们将查看图的三种声明式查询语言：Cypher，SPARQL 和 Datalog。除此之外，还有像 Gremlin 这样的图形查询语言和像 Pregel 这样的图形处理框架。

图模型与网络模型

在 CODASYL 中，数据库有一个模式，用于指定哪种记录类型可以嵌套在其他记录类型中。在图形数据库中，不存在这样的限制：任何顶点都可以具有到其他任何顶点的边。这为应用程序适应不断变化的需求提供了更大的灵活性。
在 CODASYL 中，达到特定记录的唯一方法是遍历其中的一个访问路径。在图形数据库中，可以通过其唯一 ID 直接引用任何顶点，也可以使用索引来查找具有特定值的顶点。
在 CODASYL，记录的后续是一个有序集合，所以数据库的人不得不维持排序（这会影响存储布局），并且插入新记录到数据库的应用程序不得不担心的新记录在这些集合中的位置。在图形数据库中，顶点和边不是有序的（只能在查询时对结果进行排序）。
在 CODASYL 中，所有查询都是命令式的，难以编写，并且很容易因架构中的变化而受到破坏。在图形数据库中，如果需要，可以在命令式代码中编写遍历，但大多数图形数据库也支持高级声明式查询语言，如 Cypher 或 SPARQL。

属性图

在属性图模型中，每个顶点（vertex）包括：

唯一的标识符
一组出边（outgoing edges）
一组入边（ingoing edges）
一组属性（键值对）

每条边（edge）包括：

唯一标识符
边的起点/尾部顶点（tail vertex）
边的终点/头部顶点（head vertex）
描述两个顶点之间关系类型的标签
一组属性（键值对）

关系模式存储

可以将图存储看作由两个关系表组成：一个存储顶点，另一个存储边。头部和尾部顶点用来存储每条边；如果你想要一组顶点的输入或输出边，你可以分别通过 head_vertex 或 tail_vertex 来查询 edges 表。

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);

关于这个模型的一些重要方面是：

任何顶点都可以有一条边连接到任何其他顶点。没有模式限制哪种事物可不可以关联。
给定任何顶点，可以高效地找到它的入边和出边，从而遍历图，即沿着一系列顶点的路径前后移动。
通过对不同类型的关系使用不同的标签，可以在一个图中存储几种不同的信息，同时仍然保持一个清晰的数据模型。

这些特性为数据建模提供了很大的灵活性，如前图所示。图中显示了一些传统关系模式难以表达的事情，例如不同国家的不同地区结构（法国有省和州，美国有不同的州和州），国中国的怪事（先忽略主权国家和国家错综复杂的烂摊子），不同的数据粒度（Lucy 现在的住所被指定为一个城市，而她的出生地点只是在一个州的级别）。你可以想象延伸图还能包括许多关于 Lucy 和 Alain，或其他人的其他更多的事实。例如，你可以用它来表示食物过敏（为每个过敏源增加一个顶点，并增加人与过敏源之间的一条边来指示一种过敏情况），并链接到过敏源，每个过敏源具有一组顶点用来显示哪些食物含有哪些物质。然后，你可以写一个查询，找出每个人吃什么是安全的。图表在可演化性是富有优势的：当向应用程序添加功能时，可以轻松扩展图以适应应用程序数据结构的变化。

Cypher 查询语言

Cypher 是属性图的声明式查询语言，为 Neo4j 图形数据库而发明，每个顶点都有一个像 USA 或 Idaho 这样的符号名称，查询的其他部分可以使用这些名称在顶点之间创建边，使用箭头符号：（Idaho）- [：WITHIN] ->（USA） 创建一条标记为 WITHIN 的边，Idaho 为尾节点，USA 为头节点。

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)

所有顶点和边被添加到数据库后，让我们提些有趣的问题：例如，找到所有从美国移民到欧洲的人的名字。更确切地说，这里我们想要找到符合下面条件的所有顶点，并且返回这些顶点的 name 属性：该顶点拥有一条连到美国任一位置的 BORN_IN 边，和一条连到欧洲的任一位置的 LIVING_IN 边。下例展示了如何在 Cypher 中表达这个查询。在 MATCH 子句中使用相同的箭头符号来查找图中的模式：(person) -[:BORN_IN]-> () 可以匹配 BORN_IN 边的任意两个顶点。该边的尾节点被绑定了变量 person，头节点则未被绑定。

-- 查找所有从美国移民到欧洲的人的Cypher查询
MATCH
	(person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
	(person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

该查询会按照如下来解读，找到满足以下两个条件的所有顶点（称之为 person 顶点）：

person 顶点拥有一条到某个顶点的 BORN_IN 出边。从那个顶点开始，沿着一系列 WITHIN 出边最终到达一个类型为 Location，name 属性为 United States 的顶点。
person 顶点还拥有一条 LIVES_IN 出边。沿着这条边，可以通过一系列 WITHIN 出边最终到达一个类型为 Location，name 属性为 Europe 的顶点。
对于这样的 Person 顶点，返回其 name 属性。

执行这条查询可能会有几种可行的查询路径。这里给出的描述建议首先扫描数据库中的所有人，检查每个人的出生地和居住地，然后只返回符合条件的那些人。等价地，也可以从两个 Location 顶点开始反向地查找。假如 name 属性上有索引，则可以高效地找到代表美国和欧洲的两个顶点。然后，沿着所有 WITHIN 入边，可以继续查找出所有在美国和欧洲的位置（州，地区，城市等）。最后，查找出那些可以由 BORN_IN 或 LIVES_IN 入边到那些位置顶点的人。

通常对于声明式查询语言来说，在编写查询语句时，不需要指定执行细节：查询优化程序会自动选择预测效率最高的策略，因此你可以继续编写应用程序的其他部分。

SQL 中的图查询

在关系数据库中，你通常会事先知道在查询中需要哪些连接。在图查询中，你可能需要在找到待查找的顶点之前，遍历可变数量的边。也就是说，连接的数量事先并不确定。在我们的例子中，这发生在 Cypher 查询中的() -[:WITHIN*0..]-> ()规则中。一个人的LIVES_IN边可以指向任何类型的位置：街道，城市，地区，地区，国家等。城市可以在一个地区，在一个州内的一个地区，在一个国家内的一个州等等。LIVES_IN边可以直接指向正在查找的位置，或者一个在位置层次结构中隔了数层的位置。

在 Cypher 中，用WITHIN * 0非常简洁地表述了上述事实：“沿着WITHIN边，零次或多次”。它很像正则表达式中的*运算符。自 SQL:1999，查询可变长度遍历路径的思想可以使用称为递归公用表表达式（WITH RECURSIVE语法）的东西来表示。

WITH RECURSIVE
  -- in_usa 包含所有的美国境内的位置ID
    in_usa(vertex_id) AS (
    SELECT vertex_id FROM vertices WHERE properties ->> 'name' = 'United States'
    UNION
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'within'
  ),
  -- in_europe 包含所有的欧洲境内的位置ID
    in_europe(vertex_id) AS (
    SELECT vertex_id FROM vertices WHERE properties ->> 'name' = 'Europe'
    UNION
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'within' ),

  -- born_in_usa 包含了所有类型为Person，且出生在美国的顶点
    born_in_usa(vertex_id) AS (
      SELECT edges.tail_vertex FROM edges
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'born_in' ),

  -- lives_in_europe 包含了所有类型为Person，且居住在欧洲的顶点。
    lives_in_europe(vertex_id) AS (
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'lives_in')

  SELECT vertices.properties ->> 'name'
  FROM vertices
    JOIN born_in_usa ON vertices.vertex_id = born_in_usa.vertex_id
    JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

首先，查找name属性为United States的顶点，将其作为in_usa顶点的集合的第一个元素。
从in_usa集合的顶点出发，沿着所有的with_in入边，将其尾顶点加入同一集合，不断递归直到所有with_in入边都被访问完毕。
同理，从name属性为Europe的顶点出发，建立in_europe顶点的集合。
对于in_usa集合中的每个顶点，根据born_in入边来查找出生在美国某个地方的人。
同样，对于in_europe集合中的每个顶点，根据lives_in入边来查找居住在欧洲的人。
最后，把在美国出生的人的集合与在欧洲居住的人的集合相交。

同一个查询，用某一个查询语言可以写成 4 行，而用另一个查询语言需要 29 行，这恰恰说明了不同的数据模型是为不同的应用场景而设计的。选择适合应用程序的数据模型非常重要。

三元组存储和 SPARQL

三元组存储模式大体上与属性图模型相同，用不同的词来描述相同的想法。不过仍然值得讨论，因为三元组存储有很多现成的工具和语言，这些工具和语言对于构建应用程序的工具箱可能是宝贵的补充。在三元组存储中，所有信息都以非常简单的三部分表示形式存储（主语，谓语，宾语）。例如，三元组 (吉姆, 喜欢 ,香蕉) 中，吉姆是主语，喜欢是谓语（动词），香蕉是对象。

三元组的主语相当于图中的一个顶点。而宾语是下面两者之一：

原始数据类型中的值，例如字符串或数字。在这种情况下，三元组的谓语和宾语相当于主语顶点上的属性的键和值。例如，(lucy, age, 33)就像属性{“age”：33}的顶点 lucy。
图中的另一个顶点。在这种情况下，谓语是图中的一条边，主语是其尾部顶点，而宾语是其头部顶点。例如，在(lucy, marriedTo, alain)中主语和宾语lucy和alain都是顶点，并且谓语marriedTo是连接他们的边的标签。

下面将前面的例子以称为 Turtle 的格式（Notation3（N3））的一个子集形式写成三元组。

@prefix : <urn:example:>.
_: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。这个名字并不意味着这个文件以外的任何东西。它的存在只是帮助我们明确哪些三元组引用了同一顶点。当谓语表示边时，该宾语是一个顶点，如_:idaho :within _:usa.。当谓语是一个属性时，该宾语是一个字符串，如_:usa :name "United States"。一遍又一遍地重复相同的主语看起来相当重复，但幸运的是，可以使用分号来说明关于同一主语的多个事情。这使得 Turtle 格式相当不错，可读性强：

@prefix : <urn:example:>.
_:lucy      a :Person;   :name "Lucy";          :bornIn _:idaho.
_:idaho     a :Location; :name "Idaho";         :type "state";   :within _:usa
_:usa       a :Loaction; :name "United States"; :type "country"; :within _:namerica.
_:namerica  a :Location; :name "North America"; :type "continent".

语义网络

从本质上讲语义网是一个简单且合理的想法：网站已经将信息发布为文字和图片供人类阅读，为什么不将信息作为机器可读的数据也发布给计算机呢？资源描述框架（RDF）的目的是作为不同网站以一致的格式发布数据的一种机制，允许来自不同网站的数据自动合并成一个数据网络，即一种互联网范围内的“关于一切的数据库“。

值得注意的是，三元组存储数据模型完全独立于语义网络，例如，Datomic 是三元组存储。

RDF 数据模型

Turtle 语言是一种用于 RDF 数据的人可读格式。有时候，RDF 也可以以 XML 格式编写，不过完成同样的事情会相对啰嗦，Turtle/N3 是更可取的，因为它更容易阅读，像 Apache Jena 这样的工具可以根据需要在不同的 RDF 格式之间进行自动转换。

<rdf:RDF xmlns="urn:example:"
         xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
    <Location rdf:nodeID="idaho">
        <name>Idaho</name>
        <type>state</type>
        <within>
            <Location rdf:nodeID="usa">
                <name>United States</name>
                <type>country</type>
                <within>
                    <Location rdf:nodeID="namerica">
                        <name>North America</name>
                        <type>continent</type>
                    </Location>
                </within>
            </Location>
        </within>
    </Location>
    <Person rdf:nodeID="lucy">
        <name>Lucy</name>
        <bornIn rdf:nodeID="idaho"/>
    </Person>
</rdf:RDF>

RDF 有一些奇怪之处，因为它是为了在互联网上交换数据而设计的。三元组的主语，谓语和宾语通常是 URI。例如，谓语可能是一个 URI，如 或，而不仅仅是WITHIN或LIVES_IN。这个设计背后的原因为了让你能够把你的数据和其他人的数据结合起来，如果他们赋予单词within或者lives_in不同的含义，两者也不会冲突，因为它们的谓语实际上是和。

从 RDF 的角度来看，URL 不一定需要能解析成什么东西，它只是一个命名空间。为避免与http://URL混淆，本节中的示例使用不可解析的 URI，如urn：example：within。幸运的是，你只需在文件顶部指定一个前缀，然后就不用再管了。

SPARQL 查询语言

SPARQL 是一种用于三元组存储的面向 RDF 数据模型的查询语言，它是 SPARQL 协议和 RDF 查询语言的缩写，发音为“sparkle”。SPARQL 早于 Cypher，并且由于 Cypher 的模式匹配借鉴于 SPARQL，这使得它们看起来非常相似。与之前相同的查询，查找从美国转移到欧洲的人，使用 SPARQL 比使用 Cypher 甚至更为简洁：

PREFIX : <urn:example:>
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 被绑定到任意具有值为字符串"United States"的 name 属性的顶点：

(usa {name:'United States'})   # Cypher
?usa :name "United States".    # SPARQL

Datalog

Datalog 是比 SPARQL 或 Cypher 更古老的语言，在 20 世纪 80 年代被学者广泛研究。它在软件工程师中不太知名，但是它是重要的，因为它为以后的查询语言提供了基础。在实践中，Datalog 被用于少数的数据系统中：例如，它是 Datomic 的查询语言，Cascalog 是一种用于查询 Hadoop 大数据集的 Datalog 实现。

Datalog 的数据模型类似于三元组模式，但进行了一点泛化。把三元组写成谓语（主语，宾语），而不是写三元语（主语，谓语，宾语）。

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).

既然已经定义了数据，我们可以像之前一样编写相同的查询：

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 一次只进行一小步。我们定义规则，以将新谓语告诉数据库：在这里，我们定义了两个新的谓语，within_recursive和migrated。这些谓语不是存储在数据库中的三元组中，而是它们是从数据或其他规则派生而来的。规则可以引用其他规则，就像函数可以调用其他函数或者递归地调用自己一样。像这样，复杂的查询可以一次构建其中的一小块。

在规则中，以大写字母开头的单词是变量，谓语则用 Cypher 和 SPARQL 的方式一样来匹配。例如，name(Location, Name)通过变量绑定Location = namerica和Name ='North America'可以匹配三元组name(namerica, 'North America')。

要是系统可以在:- 操作符的右侧找到与所有谓语的一个匹配，就运用该规则。当规则运用时，就好像通过:-的左侧将其添加到数据库（将变量替换成它们匹配的值）。

因此，一种可能的应用规则的方式是：

数据库存在name(namerica, 'North America')，故运用规则 1。它生成within_recursive(namerica, 'North America')。
数据库存在within(usa, namerica)，在上一步骤中生成within_recursive(namerica, 'North America')，故运用规则 2。它会产生within_recursive(usa, 'North America')。
数据库存在within(idaho, usa)，在上一步生成within_recursive(usa, 'North America')，故运用规则 2。它产生within_recursive(idaho, 'North America')。

通过重复应用规则 1 和 2，within_recursive 谓语可以告诉我们在数据库中包含北美（或任何其他位置名称）的所有位置。

现在规则 3 可以找到出生在某个地方 BornIn 的人，并住在某个地方 LivingIn。通过查询 BornIn =‘United States’和 LivingIn =‘Europe’，并将此人作为变量 Who，让 Datalog 系统找出变量 Who 会出现哪些值。因此，最后得到了与早先的 Cypher 和 SPARQL 查询相同的答案。

最近更新于 0001-01-01