DDIA 读书分享 第二章：数据模型和查询语言（2）

MapReduce 查询

Google 的 MapReduce 模型

1. 借鉴自函数式编程。
2. 一种相当简单的编程模型，或者说原子的抽象，现在不太够用。
3. 但在大数据处理工具匮乏的蛮荒时代（03年以前），谷歌提出的这套框架相当有开创性。

                         MapReduce 实际上是四个过程

MongoDB  的 MapReduce 模型

MongoDB 使用的 MapReduce 是一种介于

1. 声明式：用户不必显式定义数据集的遍历方式、shuffle 过程等执行过程。
2. 命令式：用户又需要定义针对单条数据的执行过程。

两者间的混合数据模型。

需求：统计每月观察到鲨类鱼的次数。

查询语句：

PostgresSQL

SELECT date_trunc('month', observation_timestamp) AS observation_month, 
 sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks' GROUP BY observation_month;

MongoDB

db.observations.mapReduce(
 function map() { // 2. 对所有符合条件 doc 执行 map
  var year = this.observationTimestamp.getFullYear();
  var month = this.observationTimestamp.getMonth() + 1; 
  emit(year + "-" + month, this.numAnimals); // 3. 输出一个 kv pair
 },
 function reduce(key, values) { // 4. 按 key 聚集
  return Array.sum(values);    // 5. 相同 key 加和
 },
  {
  query: { family: "Sharks" }, // 1. 筛选
  out: "monthlySharkReport"    // 6. reduce 结果集
 } 
);

上述语句在执行时，经历了：筛选→ 遍历并执行 map → 对输出按 key 聚集（shuffle）→ 对聚集的数据注意 reduce → 输出结果集。

MapReduce 一些特点：

1. 要求 Map 和 Reduce 是纯函数。即无任何副作用，在任意地点、以任意次序执行任何多次，对相同的输入都能得到相同的输出。因此容易并发调度。
2. 非常底层、但表达力强大的编程模型。可基于其实现 SQL 等高级查询语言，如 Hive。

但要注意：

1. 不是所有的分布式 SQL 都基于 MapReduce 实现。
2. 不是只有 MapReduce 才允许嵌入通用语言（如 js）模块。
3. MapReduce 是有一定理解成本的，需要熟悉其执行逻辑才能让两个函数紧密配合。

MongoDB 2.2+ 进化版，aggregation pipeline:

db.observations.aggregate([
 { $match: { family: "Sharks" } },
 { $group: {
  _id: {
   year:  { $year:  "$observationTimestamp" },
   month: { $month: "$observationTimestamp" }
  },
  totalAnimals: { $sum: "$numAnimals" } }}
]);

Graph-Like 数据模型

• 文档模型的适用场景？
  你的数据集中存在着大量一对多（one-to-many）的关系。
  
• 图模型的适用场景？
  你的数据集中存在大量的多对多（many-to-many）的关系。
  

基本概念

图数据模型的基本概念一般有三个：点，边和附着于两者之上的属性。

常见的可以用图建模的场景：

• 同构（homogeneous）数据和异构数据
  图中的点可以都具有相同类型，但是，也可以具有不同类型，并且更为强大。
  

本节都会以下图为例，它表示了一对夫妇，来自美国爱达荷州的 Lucy 和来自法国 的 Alain。他们已婚，住在伦敦。

有多种对图的建模方式：

1. 属性图（property graph）：比较主流，如 Neo4j、Titan、InfiniteGraph
2. 三元组（triple-store）：如 Datomic、AllegroGraph

属性图（PG，Property Graphs）

• Q：有一个疑惑点，为什么书中对于 PG 点的定义中没有 Type ？
  如果数据是异构的，应该有才对；莫非是通过不同的属性来标记不同的类型？
  

如果感觉不直观，可以使用我们熟悉的 SQL 语义来构建一个图模型，如下图。（Facebook TAO 论文中的单机存储引擎便是 MySQL）

// 点表
CREATE TABLE vertices (
 vertex_id integer PRIMARYKEY, 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);

图是一种很灵活的建模方式：

1. 任何两点间都可以插入边，没有任何模式限制。
2. 对于任何顶点都可以高效（思考：如何高效？）找到其入边和出边，从而进行图遍历。
3. 使用多种标签来标记不同类型边（关系）。

相对于关系型数据来说，可以在同一个图中保存异构类型的数据和关系，给了图极大的表达能力！

这种表达能力，根据图中的例子，包括：

1. 对同样的概念，可以用不同结构表示。如不同国家的行政划分。
2. 对同样的概念，可以用不同粒度表示。比如 Lucy 的现居住地和诞生地。
3. 可以很自然的进行演化。

将异构的数据容纳在一张图中，可以通过图遍历，轻松完成关系型数据库中需要多次 Join 的操作。

Cypher 查询语言

Cypher 是 Neo4j 创造的一种查询语言。

Cypher 和 Neo 名字应该都是来自 《黑客帝国》（The Matrix）。想想 Oracle。

Cypher 的一大特点是可读性强，尤其在表达路径模式（Path Pattern）时。

结合前图，看一个 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)

如果我们要进行一个这样的查询：找出所有从美国移居到欧洲的人名。

转化为图语言，即为：给定条件， BORN_IN 指向美国的地点，并且 LIVING_IN 指向欧洲的地点，找到所有符合上述条件的点，并且返回其名字属性。

用 Cypher 语句可表示为：

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

注意到：

1. 点 ()，边 -[]→，标签\类型 ：，属性 {}。
2. 名字绑定或者说变量：person
3. 0 到多次通配符：*0...

正如声明式查询语言的一贯特点，你只需描述问题，不必担心执行过程。但与 SQL 的区别在于，SQL 基于关系代数，Cypher 类似正则表达式。

无论是 BFS、DFS 还是剪枝等实现细节，都不需要关心。

使用 SQL 进行图查询

前面看到可以用 SQL 存储点和边，以表示图。

那可以用 SQL 进行图查询吗？

Oracle 的 PGQL：

CREATE PROPERTY GRAPH bank_transfers
     VERTEX TABLES (persons KEY(account_number))
     EDGE TABLES(
                  transactions KEY (from_acct, to_acct, date, amount)
                  SOURCE KEY (from_account) REFERENCES persons
                  DESTINATION KEY (to_account) REFERENCES persons
                  PROPERTIES (date, amount)
       )

其中有一个难点，就是如何表达图中的路径模式（graph pattern），如多跳查询，对应到 SQL 中，就是不确定次数的 Join：

() -[:WITHIN*0..]-> ()

使用 SQL:1999 中 recursive common table expressions （PostgreSQL, IBM DB2, Oracle, and SQL Server 支持）的可以满足。但是，相当冗长和笨拙。