2. 数据模型与查询语言 - 图数据模型 - 《设计数据密集型应用 - 中文翻译》

图数据模型

图数据模型

如我们之前所见，多对多关系是不同数据模型之间具有区别性的重要特征。如果你的应用程序大多数的关系是一对多关系（树状结构化数据），或者大多数记录之间不存在关系，那么使用文档模型是合适的。

但是，要是多对多关系在你的数据中很常见呢？关系模型可以处理多对多关系的简单情况，但是随着数据之间的连接变得更加复杂，将数据建模为图形显得更加自然。

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

社交图谱

顶点是人，边指示哪些人彼此认识。

网络图谱

顶点是网页，边缘表示指向其他页面的HTML链接。

公路或铁路网络

顶点是交叉路口，边线代表它们之间的道路或铁路线。

可以将那些众所周知的算法运用到这些图上：例如，汽车导航系统搜索道路网络中两点之间的最短路径，PageRank可以用在网络图上来确定网页的流行程度，从而确定该网页在搜索结果中的排名。

在刚刚给出的例子中，图中的所有顶点代表了相同类型的事物（人，网页或交叉路口）。不过，图并不局限于这样的同类数据：同样强大地是，图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象。例如，Facebook维护一个包含许多不同类型的顶点和边的单个图：顶点表示人，地点，事件，签到和用户的评论;边缘表示哪些人是彼此的朋友，哪个签到发生在何处，谁评论了哪条消息，谁参与了哪个事件，等等【35】。

在本节中，我们将使用图2-5所示的示例。它可以从社交网络或系谱数据库中获得：它显示了两个人，来自爱达荷州的Lucy和来自法国Beaune的Alain。他们已婚，住在伦敦。

图2-5 图数据结构示例（框代表顶点，箭头代表边）

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

属性图

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

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

每条 边（edge） 包括：

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

可以将图存储看作由两个关系表组成：一个存储顶点，另一个存储边，如例2-2所示（该模式使用PostgreSQL json数据类型来存储每个顶点或每条边的属性）。头部和尾部顶点用来存储每条边；如果你想要一组顶点的输入或输出边，你可以分别通过head_vertex或tail_vertex来查询edges表。

例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现在的住所被指定为一个城市，而她的出生地点只是在一个州的级别）。

你可以想象延伸图还能包括许多关于Lucy和Alain，或其他人的其他更多的事实。例如，你可以用它来表示食物过敏（为每个过敏源增加一个顶点，并增加人与过敏源之间的一条边来指示一种过敏情况），并链接到过敏源，每个过敏源具有一组顶点用来显示哪些食物含有哪些物质。然后，你可以写一个查询，找出每个人吃什么是安全的。图表在可演化性是富有优势的：当向应用程序添加功能时，可以轻松扩展图以适应应用程序数据结构的变化。

Cypher查询语言

Cypher是属性图的声明式查询语言，为Neo4j图形数据库而发明【37】。（它是以电影“黑客帝国”中的一个角色来命名的，而与密码术中的密码无关【38】。）

例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的所有顶点和边被添加到数据库后，让我们提些有趣的问题：例如，找到所有从美国移民到欧洲的人的名字。更确切地说，这里我们想要找到符合下面条件的所有顶点，并且返回这些顶点的name属性：该顶点拥有一条连到美国任一位置的BORN_IN边，和一条连到欧洲的任一位置的LIVING_IN边。

例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

查询按如下来解读：

找到满足以下两个条件的所有顶点（称之为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中的图查询

例2-2建议在关系数据库中表示图数据。但是，如果把图数据放入关系结构中，我们是否也可以使用SQL查询它？

答案是肯定的，但有些困难。在关系数据库中，你通常会事先知道在查询中需要哪些连接。在图查询中，你可能需要在找到待查找的顶点之前，遍历可变数量的边。也就是说，连接的数量事先并不确定。

在我们的例子中，这发生在Cypher查询中的() -[:WITHIN*0..]-> ()规则中。一个人的LIVES_IN边可以指向任何类型的位置：街道，城市，地区，地区，国家等。城市可以在一个地区，在一个州内的一个地区，在一个国家内的一个州等等。LIVES_IN边可以直接指向正在查找的位置，或者一个在位置层次结构中隔了数层的位置。

在Cypher中，用WITHIN * 0非常简洁地表述了上述事实：“沿着WITHIN边，零次或多次”。它很像正则表达式中的*运算符。

自SQL:1999，查询可变长度遍历路径的思想可以使用称为递归公用表表达式（WITH RECURSIVE语法）的东西来表示。例2-5显示了同样的查询 - 查找从美国移民到欧洲的人的姓名 - 在SQL使用这种技术（PostgreSQL，IBM DB2，Oracle和SQL Server均支持）来表述。但是，与Cypher相比，其语法非常笨拙。

例2-5 与示例2-4同样的查询，在SQL中使用递归公用表表达式表示

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是连接他们的边的标签。

例2-6显示了与例2-3相同的数据，以称为Turtle的格式（Notation3（N3）【39】）的一个子集形式写成三元组。

例2-6 图2-5中的数据子集，表示为Turtle三元组

@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格式相当不错，可读性强：参见例2-7。

例2-7 一种相对例2-6写入数据的更为简洁的方法。

@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".

语义网络

如果你阅读更多关于三元组存储的信息，你可能会被卷入关于语义网络的文章漩涡中。三元组存储数据模型完全独立于语义网络，例如，Datomic【40】是三元组存储^vii，并没有声称与它有任何关系。但是，由于在很多人眼中这两者紧密相连，我们应该简要地讨论一下。

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

不幸的是，这个语义网在二十一世纪初被过度使用，但到目前为止没有任何迹象表明已在实践中实现，这使得许多人呲之以鼻。它还遭受了过多的令人眼花缭乱的缩略词，过于复杂的标准提议和狂妄自大的苦果。

然而，如果仔细观察这些失败，语义Web项目还是拥有很多优秀的工作成果。即使你没有兴趣在语义网上发布RDF数据，三元组也可以成为应用程序的良好内部数据模型。

RDF数据模型

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

例2-8 用RDF/XML语法表示例2-7的数据

<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，如 <http://my-company.com/namespace#within>或<http://my-company.com/namespace#lives_in>，而不仅仅是WITHIN或LIVES_IN。这个设计背后的原因为了让你能够把你的数据和其他人的数据结合起来，如果他们赋予单词within或者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数据模型的查询语言，【43】。（它是SPARQL协议和RDF查询语言的缩写，发音为“sparkle”。）SPARQL早于Cypher，并且由于Cypher的模式匹配借鉴于SPARQL，这使得它们看起来非常相似【37】。

与之前相同的查询 - 查找从美国转移到欧洲的人 - 使用SPARQL比使用Cypher甚至更为简洁（参见例2-9）。

例2-9 与示例2-4相同的查询，用SPARQL表示

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

SPARQL是一种很好的查询语言——哪怕语义网从未实现，它仍然可以成为一种应用程序内部使用的强大工具。

图形数据库与网络模型相比较
在“文档数据库是否在重蹈覆辙？”中，我们讨论了CODASYL和关系模型如何竞相解决IMS中的多对多关系问题。乍一看，CODASYL的网络模型看起来与图模型相似。CODASYL是否是图形数据库的第二个变种？

不，他们在几个重要方面有所不同：

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

基础：Datalog

Datalog是比SPARQL或Cypher更古老的语言，在20世纪80年代被学者广泛研究【44,45,46】。它在软件工程师中不太知名，但是它是重要的，因为它为以后的查询语言提供了基础。

在实践中，Datalog被用于少数的数据系统中：例如，它是Datomic 【40】的查询语言，Cascalog 【47】是一种用于查询Hadoop大数据集的Datalog实现[^viii]。

[^viii]: Datomic和Cascalog使用Datalog的Clojure S表达式语法。在下面的例子中使用了一个更容易阅读的Prolog语法，但两者没有任何功能差异。

Datalog的数据模型类似于三元组模式，但进行了一点泛化。把三元组写成谓语（主语，宾语），而不是写三元语（主语，谓语，宾语）。例2-10显示了如何用Datalog写入我们的例子中的数据。

例2-10 用Datalog来表示图2-5中的数据子集

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一次只进行一小步。我们定义规则，以将新谓语告诉数据库：在这里，我们定义了两个新的谓语，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谓语可以告诉我们在数据库中包含北美（或任何其他位置名称）的所有位置。这个过程如图2-6所示。

图2-6 使用示例2-11中的Datalog规则来确定爱达荷州在北美。

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

相对于本章讨论的其他查询语言，我们需要采取不同的思维方式来思考Datalog方法，但这是一种非常强大的方法，因为规则可以在不同的查询中进行组合和重用。虽然对于简单的一次性查询，显得不太方便，但是它可以更好地处理数据很复杂的情况。