第一章 概述

1.1 基本概念

1.1.1 分布式数据库

  分布式数据库——多个分布在计算机网络上的逻辑相关的数据库的集合。

  分布式数据库中，存放在不同网络节点上的数据库称作局部数据库，由局部数据库构成的逻辑整体称为全局数据库。全局数据库中的关系称为全局关系，局部数据库中的关系称为逻辑片段，或简称片段。

  全局关系与片段之间的映射关系称为分片。全局数据库与局部数据库之间的映射关系由一组分片模式来体现。一个逻辑片段可以保存在网络的一个节点上，也可以在网络的多个节点上保存多个副本，逻辑片段如何在网络上存放，称为分配。

1.1.2 数据管理的透明性

• 分片透明：用户使用数据库时，不需要知道全局数据库与多个局部数据库之间的逻辑关系。
• 复制（分配）透明：用户使用数据库时，不需要知道数据在网络上不同节点间的复制情况。
• 网络透明：用户使用数据库时，用全局唯一的对象名指代所要操作的对象，不需知道数据在网络上的位置。
• 数据独立性（无分布透明）：用户应用不受数据库逻辑结构变化的影响，用户应用不需关注数据库数据保存的物理结构。集中式数据库就具有这样的特性。

1.1.3 可靠性

  事务是数据库上的一致的可靠的计算单元，事务由一串具有原子性的数据库操作组成。

  事务具有ACID四个特性。

• 原子性（Atomicity），组成一个事务的一串操作要么全部完成，要么全部没做。
• 一致性（Consistency），并发执行的事务总是使得数据库从一个一致的状态转变为另一个一致的状态。
• 隔离性（lsolation），一个事务执行过程中无法看到其他并发事务的中间结果。
• 持久性（Durability），已完成事务的结果将会被可靠地永久地保存，直至被另一个事务所更新。

  事务的性质在分布式数据库中必须得到保证。在分布式环境中保障事务性质显然与集中式环境有很多不同。集中式数据库环境中若服务器节点失效，数据库系统将无法运转，而在分布式数据库环境中，在某些条件满足时，即使某个服务器节点失效，数据库系统仍能运转。

1.1.4 分布式数据库与集中式数据库的区别

  集中式数据库中数据库存放在网络上的一个节点上，而分布式数据库数据库分布存放在网络上不同节点上。

1.2 体系结构

1. 客户机/服务器模式：多客户机/单服务器、多客户机/多服务器
2. 对等节点模式：
3. 多数据库模式：含全局概念模式、不含全局概念模式。

1.3 全局目录

  全局目录是分布式数据库中描述全局数据库与局部数据库关系的信息集合（分片模式和分配模式的集合）。只有分布式数据库有全局目录的问题。在分布式数据库中全局目录是目录的一部分。

  目录本身也是一个数据库。目录可以集中存放在一个节点上，也可以分为全局目录和局部目录，分布存放在网络的不同节点上。

  分布式数据库的设计技术同样适用于目录。分布式环境中，一个目录可以只在一个节点上存放一个拷贝，也可以在多个节点上存放多个拷贝。

1.4 关系代数

1.4.1 基操

1.4.2 关系表达式

  由关系代数运算经有限次复合而成的式子称为关系代数表达式。这种表达式的运算结果仍然是一个关系。可以用关系代数表达式表示对数据库的查询和更新操作。

例如：
数据库中有三个关系如下：
学生关系 Stu1(sid, sname, sage, sgender)，Stu2(sid, sname, sage, sgender)
选课关系 SC(sid, cid, grade)
课程关系 Cou(cid, cname, cteacher)

1. 查询学号为112的学生年龄
   $${\pi }_{sage}({\sigma }_{sid{=}^{\prime }112^{\prime }}(Stu1))$$
2. 查询学号为112或者212的学生性别
   $${\pi }_{sgender}({\sigma }_{sid{=}^{\prime }112^{\prime }\vee sid{=}^{\prime }212^{\prime }}(Stu1\cup Stu2))$$
3. 查询同时出现在两个学生关系中的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1\cap Stu2)$$
4. 查询出现在学生关系1且不在学生关系2中的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1-Stu2)$$
5. 查询学号为112的学生的数据库课程成绩
   $${\pi }_{grade}({\sigma }_{sid{=}^{\prime }112^{\prime }\wedge cname{=}^{\prime }数据{库}^{\prime }}(Cou{\bowtie }_{Cou.cid=SC.cid}SC))$$
6. 查询学生关系1中选过课的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1{⋉}_{Stu1.sid=SC.sid}SC)$$
   【注：半连接返回左表中与右表至少匹配一次的数据行，通常体现为 EXISTS 或者 IN 子查询】

1.4.3 查询树

  关系表达式可进一步转换为查询树，查询树包含关系操作的先后顺序，数据库系统可依据查询树控制查询操作。

例如：

1. 查询学号为112的学生年龄
   $${\pi }_{sage}({\sigma }_{sid{=}^{\prime }112^{\prime }}(Stu1))$$

2. 查询学号为112或者212的学生性别
   $${\pi }_{sgender}({\sigma }_{sid{=}^{\prime }112^{\prime }\vee sid{=}^{\prime }212^{\prime }}(Stu1\cup Stu2))$$

3. 查询同时出现在两个学生关系中的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1\cap Stu2)$$

4. 查询出现在学生关系1且不在学生关系2中的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1-Stu2)$$

5. 查询学号为112的学生的数据库课程成绩
   $${\pi }_{grade}({\sigma }_{sid{=}^{\prime }112^{\prime }\wedge cname{=}^{\prime }数据{库}^{\prime }}(Cou{\bowtie }_{Cou.cid=SC.cid}SC))$$

6. 查询学生关系1中选过课的学生学号和姓名
   $${\pi }_{sid,sname}(Stu1{⋉}_{Stu1.sid=SC.sid}SC)$$

第二章 分布式数据库的设计

2.1 设计策略

  当数据库的设计是从头开始时，自顶向下的设计是合适的。然而有时一些数据库已经存在，设计是为了集成已存在的一些数据库，这时需要自底向上的设计方法。

  自底向上的设计方法所涉及的需要集成的多个数据库常常是异构的。

2.2 分布设计的目标

1. 分布设计的多个子目标之间相互矛盾，只能进行平衡折中的处理。
2. 分布设计应使每个应用访问的局部数据库尽可能少。
3. 分布设计应尽可能提高应用的并发程度。
4. 分布设计应尽可能减少应用执行过程中的网络通信量。
5. 分布设计应尽可能让用户应用在网络上就近访问。

2.3 水平分片设计

2.3.1 需求分析

• 收集用户查询所用的谓词。
• 用户查询无穷无尽，无法全部收集，通常在80/20规则的指导下进行。即:20%的最活跃的查询可以反映80%的数据访问情况。

2.3.2 简单谓词集合的精炼处理

谓词： P i : A i    θ    V a l u e        θ ∈ { = , < , > , ≠ , ≤ , ≥ } P_i: A_i \;\theta\; Value\;\;\; \theta \in \{=,<,>,\not=,\le,\ge\} Pi​:Ai​θValueθ∈{=,<,>,=,≤,≥}
例如：$P_1:LOC="Montreal"$

P r i = { p i 1 , P i 2 , . . . , p i m } P_{ri} = \{p_{i1}, P_{i2},. . ., p_{im}\} Pri​={pi1​,Pi2​,...,pim​} 是针对关系 $r_i$ 收集的简单谓词集合。
$P_{ri}$ 经算法COM-MIN处理后得到 $P_{ri}^{\prime }$。对于关系 $r_i$ ， $P_{ri}^{\prime }$ 是满足分布设计要求的最小简单谓词集合。

例如，针对关系PROJ得到了 P ′ = { p 1 , P 2 , P 3 , P 4 , P 5 } P'= \{p1, P2, P3, P4, P5\} P′={p1,P2,P3,P4,P5}
p1：LOC = “Montreal”
p2：LOC = “New York”
p3：LOC = "Paris’
p4：DUDGET ≤200000
p5：DUDGET > 200000

2.3.3 最小谓词集合处理

M i = { m i j ∣ m j j = ∧ p i k ∗ ,    1 < j < z ,    p i k ∗ = p i k ∣ ¬ p i k ,    p i k ∈ P r i ′ } M_i = \{m_{ij}|m_{jj} = \wedge p^*_{ik}, \; 1<j<z, \;p^*_{ik}=p_{ik}|\neg p_{ik},\; p_{ik}∈P'_{ri} \} Mi​={mij​∣mjj​=∧pik∗​,1<j<z,pik∗​=pik​∣¬pik​,pik​∈Pri′​}  $M_i$是关于关系$r_i$最小项谓词集合从$P_{ri}^{\prime }$中得到，是进行水平分片的依据。

例如，由 P ′ = { p 1 , p 2 , p 3 , p 4 , p 5 } 可得 M = { m j }    ( 1 ≤ j ≤ 2 5 ) P'=\{p_1,p_2,p_3, p_4, p_5\}可得M=\{m_j\}\;(1≤j≤2^5) P′={p1​,p2​,p3​,p4​,p5​}可得M={mj​}(1≤j≤25)。然而，谓词间隐含着一些语意。

$i_1:p1\Rightarrow \neg p2\wedge \neg p_3$
$i_2:p2\Rightarrow \neg p1\wedge \neg p_3$
$i_3:p3\Rightarrow \neg p1\wedge \neg p_2$
$i_4:p4\Rightarrow \neg p5$
$i_5:p5\Rightarrow \neg p4$
$i_6:\neg p4\Rightarrow p5$
$i_7:\neg p5\Rightarrow p4$

由$i_{1-7}$可知，$p_{1-3}$不可能同时存在，$p_{4-5}$不可能同时存在，删除非法和重复的最小谓词项后，得到 M = { m i , 1 ≤ i ≤ 6 } M=\{m_i, 1 \le i \le 6\} M={mi​,1≤i≤6}

最后根据最小谓词集合M进行水平分片：

分片结果如下：

  其中$PRO{J}_2,PRO{J}_5$为空，那是由PROJ的当前值决定的，数据库是动态的，PROJ的值也是动态的。

2.3.4 诱导分片

  水平分片可以直接对一个关系搜集应用信息，设计分片，也可以从另一个关系诱导其分片方案。如图所示，关系间存在着link ,如L1,L2,L3。用关系代数的术语来讲，link表示一个关系的外键是另一个关系的主键。例如，L3表示ASG的外键JNO是PROJ的主键。

对于owner关系直接设计其水平分片，对于member关系从owner关系诱导出水平分片的设计。诱导分片的设计方法是半连接。例如，关于ASG的水平分片可如下设计：

  有的member有多个owner，例如，EMP和PROJ都是ASG的owner。这种情况下，从不同的owner诱导出不同的水平分片方案。最终由设计者根据系统分配的需求选取一种。

2.3.5 正确性检查

• 完整性:全局关系的任何数据至少可在一个分片中找到，并且每个分片被访问的概率相同。
• 重构性：$R=\cup R_i，\forall R_i\in F_R。$
• 不相交性：$R_i\cap R_j=\varnothing ，\forall i,j{R}_i,R_j\in F_R。$

2.4 垂直分片设计

  在分布式数据库中可采用垂直分片分割全局关系，在集中式数据库中也可采用垂直分片设计存储结构，把经常一起被访问的列聚集存放在一起，提高存储效率。
  垂直分片可选方案非常多。m个非主键属性可能的垂直分片方案的数量是B(m),当m = 10时，B(m) ≈ 115000，当m = 15时，B(m) ≈$10^9$，当m = 30时，B(m) ≈ $10^{23}$。因此，垂直分片的设计是非常困难的。
  两种启发式的途径：成组和切分。

2.4.1 使用矩阵

$A_1=PNO,A_2=PNAME,A_3=BUDGET,A4=LOC$

$$use(q_i,A_j)=\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 1& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 1\end{array}\right)$$

2.4.2 亲密矩阵

  使用矩阵没有包含应用调用查询的频率信息，不能足够反应出属性之间的亲密程度。为此，进一步给出属性间的亲密度定义:

其中，$ac{c}_l(q_k)$是应用 I 调用查询 $q_k$的频率。

计算方法：

1. 先计算 $acc(q_k)={\sum }_{l=1}^{3}ac{c}_l(q_k)$
   $acc(q_1)=15+20+10=45$
   $acc(q_2)=5+0+0=5$
   $acc(q_3)=25+25+25=75$
   $acc(q_4)=3+0+0=3$
2. 再计算亲密矩阵的上三角元素$a_{ij}={\sum }_{k=1}^{4}acc(q_k)\ast (use(q_k,A_i)\wedge use(q_k,A_j))$，其中 $use(q_k,A_i)\wedge use(q_k,A_j)$的值为使用矩阵 use 对应元素“与”的结果。
   $a_{11}=45\ast (1\wedge 1)+5\ast (0\wedge 0)+75\ast (0\wedge 0)+3\ast (0\wedge 0)=45$
   $a_{12}=45\ast (1\wedge 0)+5\ast (0\wedge 1)+75\ast (0\wedge 1)+3\ast (0\wedge 0)=0$
   $a_{13}=45\ast (1\wedge 1)+5\ast (0\wedge 1)+75\ast (0\wedge 0)+3\ast (0\wedge 1)=45$
   $a_{14}=45\ast (1\wedge 0)+5\ast (0\wedge 0)+75\ast (0\wedge 1)+3\ast (0\wedge 1)=45$
   $a_{22}=45\ast (0\wedge 0)+5\ast (1\wedge 1)+75\ast (1\wedge 1)+3\ast (0\wedge 0)=80$
   $a_{23}=45\ast (0\wedge 1)+5\ast (1\wedge 1)+75\ast (1\wedge 0)+3\ast (0\wedge 1)=5$
   $a_{24}=45\ast (0\wedge 0)+5\ast (1\wedge 0)+75\ast (1\wedge 1)+3\ast (0\wedge 1)=75$
   $a_{33}=45\ast (1\wedge 1)+5\ast (1\wedge 1)+75\ast (0\wedge 0)+3\ast (1\wedge 1)=53$
   $a_{34}=45\ast (1\wedge 0)+5\ast (1\wedge 0)+75\ast (0\wedge 1)+3\ast (1\wedge 1)=3$
   $a_{44}=45\ast (0\wedge 0)+5\ast (0\wedge 0)+75\ast (1\wedge 1)+3\ast (1\wedge 1)=78$
3. 亲密矩阵 aff 为对称矩阵，根据对称性补完剩下的下三角元素
   

2.4.3 聚集的属性亲密矩阵（理解即可，有点复杂）

  属性亲密度矩阵显然让垂直分片设计工作前进了一步。但是仍然无法直接给出垂直分片方案。如果亲密的属性聚集在一起，设计垂直分片将会比较容易。聚集的属性亲密度矩阵就是亲密属性聚集在一起的属性亲密度矩阵。聚集的属性亲密度矩阵是由属性亲密度矩阵经过行间交换以及对应的列间交换得到的。为通过算法得到这样的矩阵，定义全局亲密度度量：

具体例子：

确定分割点

  对于n个属性，在CA中有n-1个分割点。每个分割点可以计算一个z值，选取z值最大的那个分割点对属性集合进行划分。这样的划分可迭代进行下去，直到给定的条件满足为止。
  假设AS1，AS2，.…. ，ASx是通过上述方法对一个关系进行属性集划分得到的k个属性子集。然后，对这些属性集进行如下处理:

2.4.5 正确性检查

2.5 分解树和重构树

  水平分片和垂直分片可以混合使用，如图所示：

  上图的树被称作分解树，描述了全局关系与逻辑片段之间的关系。全局关系可由逻辑片段通过重构树（下图所示）的操作序列重构出来。

2.6 分配

每个逻辑片段可以保存在一个节点上，也可以在多个节点上保存多个副本。保存多个副本有利于提高查询的效率，但是却会增加更新的代价。分配是一个非常复杂的优化问题。可简单表述如下:

第三章 分布式查询

3.1 查询分解

3.1.1 规范化

  查询条件可由谓词表达式表示，将查询的谓词表达式进行规范化处理有助于删除冗余操作。规范化形式有合取规范化和析取规范化。

1. 合取规范化【$(a+b)\ast (b+c)\ast (c+d)\ast ...$】
   
2. 析取规范化【$ab+bc+cd+...$】
   

3.1.2 规范化规则

3.1.3 逻辑规则

3.1.4 冗余消除

3.1.5 查询树优化

  查询经前述处理后被写成一颗查询树，为减少计算量，需对查询树进行优化处理，优化处理所依据的规则如下。R,S,T表示不同的关
系，A= {A1,A2,……. ,An} 和 B={B1,B2,… ,Bn} 分别表示R, S的属性集。

  下页左图是一颗查询树，查询树优化的目标就是从等价的查询树中找出代价最小的那一颗。但是等价的查询树数量太多，无法比较所有的查询树代价。可行的办法就是采用启发式的方法寻找较优的查询树。一个启发式途径是：采用下移一元操作的方式优化查询树。

3.2 数据定位

3.2.1 合并重构树

  优化后的查询树的叶节点是全局关系，在分布式数据库中全局关系是虚拟的，如果操作没有定位到逻辑片段，查询是无法进行的。将查询操作落实到具体的逻辑片段上，这一工作称为数据定位。数据定位最简单的做法是：用全局关系的重构树代替查询树中的全局关系，把重构树合并到查询树中来。
  但是，合并重构树是不够的。因为，对于一个具体的查询有的逻辑片段是不可能有结果，针对这样的逻辑片段进行计算完全是浪费。这里把查询树中不可能有结果的逻辑片段称为无用节点，删除无用节点是需要开展的下一步优化工作。

3.2.2 水平分片的裁剪

例如：
  EMP(ENO, ENAME, TITLE) 和 ASG 被如下分片:

对于查询1：

  该查询经初步优化和合并重构树后得到左图所示的查询树，根据规则1裁剪无用节点，得到右图所示的查询树。显然，右图的查询树与左图的查询树相比，可以省掉很多计算，却能够得到同样的结果。

对于查询2：
$$\begin{array}{rl}& SELETE\ast \\ & FROMEMP，ASG\\ & WHEREEMP.ENO=ASG.ENO\end{array}$$

上图的查询树可经过并与连接转换，规则2的转换，变换为下图的查询树。下图的查询树计算量远低于上图。

3.2.3 垂直分片的裁剪

对于查询：

该查询经初步优化和合并重构树后得到下图所示的查询树。

上图的查询树经一元操作幂等律、投影与连接的交换、垂直分片的裁剪转换为下图的查询树。

3.2.4 诱导分片的裁剪

对于查询：

查询树如下：

优化【删除空选择】

优化【交换连接与并】

优化【根据诱导分片，删除空子树】

3.2.5 混合分片的裁剪

查询树为：

优化后

3.3 全局优化

3.3.1 目标

• 在查询操作落实到逻辑片段并裁剪了无用节点之后，查询还需要进一步优化。进一步优化需要考虑执行操作的位置，执行操作的顺序，执行操作的代价等问题。
• 目标是:寻找一个代价最小且与原查询树等价的查询树。
• 代价包括数据通信量、CPU时间、I/O时间等。

这仍然是一个NP困难问题，只能采用启发式方法寻求较优的方案。

3.3.2 代价的估算

  查询的代价可以是查询所消耗的总时间，也可以是查询的响应时间。总时间指执行查询的各个操作所消耗的时间总和，响应时间指查询开始到查询完成所经历的时间。

  无论是总时间还是响应时间，都需通过数据库的统计数据来估算。

常用的统计量

  关系R的属性集为 A = { A 1 , A 2 , … , A n } A= \{A_1,A_2,…,A_n\} A={A1​,A2​,…,An​}，被分片为$R_1,R_2,\dots ,R_n$

3.3.3 主要优化问题

  前面的优化处理已经把操作落实到了逻辑片段上并尽可能下推了一元运算，这时的主要问题是选择连接运算的场地和运算次序。

半连接处理

3.3.4 主要算法

1. Distributed INGRES Algorithm
2. R* Algorithm
3. SDD-1 Algorithm

3.4 局部优化

  对那些已经定位到一个场地上的一系列操作采用集中式数据库中的优化方法继续进行局部优化。

  局部优化有动态优化和静态优化两种策略，大多数商业关系型数据库系统采用静态优化的策略。

第四章 分布式并发控制

4.1 串行化理论

• 并发控制关系到事务的隔离性和一致性。
• 串行化理论是被广泛接受的判断并发控制正确性的标准。

例如，有以下事务及其之上的调度：

T 1 = { R 1 ( x ) , W 1 ( x ) , G 1 } T_1=\{R_1(x), W_1(x),G_1\} T1​={R1​(x),W1​(x),G1​}
T 2 = { W 2 ( x ) , W 2 ( y ) , R 2 ( z ) , C 2 } T2= \{W_2(x),W_2(y), R_2(z),C_2\} T2={W2​(x),W2​(y),R2​(z),C2​}
T 3 = { R 3 ( x ) ， R 3 ( y ) , R 3 ( z ) , C 3 } T3=\{R_3(x)，R_3(y),R_3(z),C_3\} T3={R3​(x)，R3​(y),R3​(z),C3​}
S = { W 2 ( x ) , W 2 ( y ) , R 2 ( z ) , C 2 , R 1 ( x ) , W 1 ( x ) , C 1 , R 3 ( x ) , R 3 ( y ) , R 3 ( z ) , C 3 } S=\{W_2(x), W_2(y),R_2(z),C_2,R_1(x), W_1(x),C_1, R_3(x), R_3(y),R_3(z),C_3\} S={W2​(x),W2​(y),R2​(z),C2​,R1​(x),W1​(x),C1​,R3​(x),R3​(y),R3​(z),C3​}

  S是对事务T1，T2，T3的一个调度。s是一个串行调度，执行的顺序是T2→T1→T3。串行调度可以保证事务的隔离性和一致性，串行调度是正确的调度。但是串行调度完全排斥事务的并发性，效率太低，不可接受。
  串行化理论提供了判断并发调度等价于串行调度的方法，把等价于串行调度的调度称为可串行化调度。

4.1.1 集中式可串行化

  对同一数据项的读写操作、写写操作被称为冲突操作。例如$W_2(x),W_1(x)$是一对冲突操作，$W_2(y),R_3(y)$是另一对冲突操作。冲突操作$W_2(x),W_1(x)$中$W_2(x)$先于$W_1(x)$，记为$W_2(x)\prec W_1(x)$。同样地，$W_2(y)\prec R_3(y)$。根据调度冲突关系绘制调度冲突图，图中无环则为可串行化调度，否则不能判定为可串行化调度
。

  调度S本身是串行调度，判断为可串行化调度理所当然。调度S’是一个并发调度，用上述方法判断一下其是否为可串行化的。

4.1.2 分布式可串行化

  串行化理论扩展到分布式环境上才能解决分布式数据库中的调度问题。
  假设调度S’中与x数据项有关的操作以及C1操作发生在场地x上，与y数据项有关的操作以及C2操作发生在场地y上，与z数据项有关的操作以及C3操作发生在场地z上，则S’可改写成：

S x ′ = { W 2 ( x ) , R 1 ( x ) , W 1 ( × ) , C 1 , R 3 ( x ) } S'_x=\{W_2(x),R_1(x), W_1(×),C_1, R_3(x)\} Sx′​={W2​(x),R1​(x),W1​(×),C1​,R3​(x)}
S y ′ = { W 2 ( y ) , R 3 ( y ) , C 2 } S'_y = \{ W_2(y),R_3(y),C_2\} Sy′​={W2​(y),R3​(y),C2​}
S z ′ = { R 2 ( z ) , R 3 ( z ) , C 3 } S'_z=\{R_2(z),R_3(z),C_3\} Sz′​={R2​(z),R3​(z),C3​}

  可分别为 $S_x^{\prime },S_y^{\prime },S_z^{\prime }$ 绘制冲突调度图，然后合并为一张图，若无环则为可串行化调度，否则不能作出此判断。

4.2 并发控制概况

现有的并发控制$\subset$可串行化的并发控制$\subset$正确的并发控制$\subset$并发控制

4.3 基于锁的并发控制

4.3.1 基本概念

	$R{L}_i(x)$	$W{L}_i(x)$
$R{L}_j(x)$	兼容	互斥
$W{L}_j(x)$	互斥	互斥

  WL为写锁，RL为读锁。在对数据项进行操作前要上锁，如果没有遇到不兼容的锁，上锁成功才能进行实际操作，否则只有等拥有该锁的事务释放该锁时才会有机会上锁成功。

例如：

  S是关于事务T1,T2的一个基于锁的调度，其中$l{r}_i(z)$表示释放事务$T_i$对数据项z的锁。

• 假设在两个事务执行之前x、y的值分别为 50 和 20，T1, T2串行的结果是多少?
  102和38，或者101和39
• 依据调度S的执行结果是多少?
  102和39
• 这说明S并不是一个可串行化的调度。请用可串行化理论对此作一判断。【并不是基于锁的调度就是可串行化调度】
  

4.3.2 两段锁协议（2PL）

  2PL指2-phase locking，意指把事务的加锁和解锁过程分成两个阶段，加锁阶段和解锁阶段。加锁阶段只加锁不解锁，解锁阶段只解锁不加锁。

4.3.2.1 集中式数据库中2PL的可串行性

4.3.2.2 分布式数据库中2PL的可串行性

4.4 死锁问题

第五章 分布式恢复

第六章 区块链技术

第七章 NewSQL数据库

第八章 NoSQL数据库

第九章 课程设计

9.1 需求

1. 单车信息应按城市水平分片
2. 用户量大，用户描述信息（包含用户余额）需分片。
3. 行程信息量更大，还需记录行程轨迹（用 bigtable 类似存储）。
4. 用户的优惠卷信息，到期自动删除。
5. 公司的充值活动、优惠卷活动，活动结束自动删除。
6. 充值、兑现、购买优惠卷的支付处理（跨数据库的一致性提交）。
7. 开锁处理（含判断是否有钱）
8. 上锁处理（含付费）

  设计文档包括表及其结构、表间的关联、表的分布设计、<key, value>存储及其与表之间的联系、关键事务的描述、主要的查询流程。

9.2 设计

9.2.1 表及其结构（类图）

9.2.2 表间的关联（ER图）

9.2.3 表的分布设计

9.2.4 <key, value>存储及其与表之间的联系（索引）

9.2.5 关键事务的描述

9.2.6 主要的查询流程