分布式数据库总结

数据库：长期存储在计算机内的有组织的，可共享的相关数据的集合。

数据库管理系统：DBMS是介于用户与操作系统之间的一层数据管理软件。为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。DBMS基于某种数据模型。

数据库系统：数据库系统（DBS）通常是指带有数据库的计算机应用系统。包括数据库、相应的硬件、软件和各类人员。

数据库技术：数据库技术是研究数据库的结构、存储、设计、管理和使用的一门软件学科；是一门综合性较强的学科。

数据抽象：视图抽象——外模式；概念抽象——概念模式；物理抽象——内模式

数据模型：数据模型三要素：数据结构；数据操作；完整性约束

模式/内模式映象：该映象存在于模式与内模式之间，用于定义模式与内模式之间的对应性。本映象一般在内模式中描述。

外模式/模式映象：该映象存在于外模式与模式之间，用于定义外模式和模式之间的对应性。本映象一般在外模式中描述。

物理性：在数据库系统的三级模式结构中，存在模式/内模式的映 象，当内模式发生变化时，只要修改模式/内模式的映象，就可以保持模式不变，从而保证程序与数据的物理性。逻辑性：在数据库系统的三级模式结构中，存在外模式/模式的映象，当模式发生变化时，只要修改外模式/模式的映象，即可保持外模式不变，从而保证程序和数据的逻辑性。

DDBS具有如下四个基本特点：物理分布性 逻辑整体性 场地自治性 场地之间协作性

计算机网络：定义为相互联接、彼此的计算机系统的集合。相互联接指两台或多台计算机通过信道互连，从而可进行通信；彼此则强调在网络中，计算机之间不存在明显的主从关系，即网络中的计算机不具备控制其他计算机的能力，每台计算机都具有的操作系统。   计算机网络的组成：通信子网和资源子网

分布式数据库定义：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。

分布式数据库系统的特点：①物理分布性：数据不是存放在一个站点上  ②逻辑整体性：是与分散式数据库系统的区别  ③站点自治性：是与多处理机系统的区别  ④数据分布透明性

⑤集中与自治相结合  ⑥存在适当的数据冗余度  ⑦事务管理的分布性

分布式数据库的分类：

㈠按局部DBMS的数据模型分类

①同构型DDBS:各个站点上数据库的数据模型都是同一数据模型。

⒈同构同质型：同一类型，同一种DBMS

⒉同构异质型：同一类型，不是同一种DBMS

②异构型DDBS：各个站点上数据库的数据模型的类型是各不相同的。

㈡按DDBS的全局控制类型分类

①全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点

②全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。

③全局控制可变型DDBS：也称主从型DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。

分布式数据库的组成成分：

①应用数据库，它是分布式数据库的主体，关于应用所需要的数据的集合；

1、局部数据（只提供本站点的局部应用所需要的数据）；

2、全局数据（虽然物理上存储在个站点上，但是参与全局应用）

②描述数据库（数据字典、数据目录或元数据）关于数据库中该数据结构的定义，以及全局数据的分片、分布的描述。

1、局部数据目录（局部站点上的数据词典）

2、全局数据目录（提供全局数据的描述和管理相关信息）

数据分片要准守的原则：①完备性原则：要把所有的数据映射到各个片断中；②可重构原则：关系分片后的各个片断可重构整个关系；③不相交原则：关系分片后的各个片断不能重叠

分布式数据库是多层的：①全局外层（全局外模式） ②全局概念层：（全局概念模式、分片模式和分配模式）描述分布式数据库总全局数据的逻辑结构和数据结构。   ③局部概念层：局部概念模式   ④局部内层：局部内模式

DDBS的体系结构自上而下有六个层次：全局外模式；全局概念模式；分片模式；分配模式；     局部概念模式；局部内模式

模式结构：全局外模式，全局概念模式，分片模式，分配模式，局部概念模式，局部内模式。

分布式数据库管理系统的功能模块：要保证数据库的共享性、可用性、安全性、完整性、分布透明性等功能的实现，应该包括如下四个基本功能模块：①查询处理模块：查询分析和查询优化 ②完整性处理模块 ③调度处理模块 ④可靠性处理模块 

DDBMS在物理硬件层和集中式系统的主要区别是：各种各样被称为站点或节点的计算机必须通过通信网络连接起来，在站点间传输数据和命令。

分布式数据库管理系统的参考模型的主要成分：处理器和模式。

分布式数据库中的数据性：①逻辑性②物理性 ③分布性（分布透明性）：分三个层次：分片透明性（完全分布透明性）；位置透明性（中级分布透明性）；局部数据模型透明性（低级分布透明性）； 无分布透明性：异构数据

分布透明性的定义：指用户或用户程序使用分布式数据库如同使用集中式数据库那样，不必关心全局数据的分布情况，包括全局数据的逻辑分片情况、逻辑片段的站点位置分配情况，各站点数据库的数据模型等情况对用户和用户程序是透明的。

分布透明性的三个层次：①分片透明性：分布透明性中的最高层，位于全局概念模式与分片模式之间。    ②位置透明性：分布透明性的中间层，位于分片模式和分配模式之间。

③局部数据模型透明性：分布透明性的最底层，位于分配模式与局部概念模式之间。

%%%%%%%%%%%%%%%第二章：分布式数据库系统的设计

设计集中式数据库的一般方法包括四个阶段：需求分析，概念设计，逻辑设计，物理设计

分布式数据库加一阶段：分布设计，包括数据的分片设计和pain段的位置分配设计。

需求分析阶段输出：应用的频率表，实体的划分表，数据与应用的计划表。

DDBS设计方法：自顶向下（重构法）；自底向上（组合法）；混合法

分片应遵守的原则：(1)完整性条件； (2)可重构条件； (3)不相交条件

分片的方式：(1)水平分片：是对全局关系执行“选择”操作。分为基本分片和基于到处分片。(2)垂直分片；是通过“投影”操作把它的属性分成若干组。导出分片 ；混合分片

分布式查询策略：

代价公式： QC = I/O 代价 + CPU 代价 + 通讯代价

通讯代价： TC = 传输延迟时间C0 + (传输数据量X *  数据传输速率C1)

%%%%%%%%%%%%%%%%%%%%%第三章：分布式数据库的查询处理与优化

分布式查询分类：局部查询，远程查询，全局查询

（1）层次结构：分布式数据库查询处理的层次结构，查询处理可分为四个层次：①查询分解：将查询问题转换成一个定义在全局关系上的关系代数式；②数据本地化：把一个在全局关系上的查询，进行具体化，落实到适合片段上的查询；③全局优化：寻找最优策略；④局部优化：每个子站点上执行的子查询； 

（2）查询优化的方式：①基于关系代数等价变换的查询优化处理; ②基于半连接算法的查询优化处理; ③基于直接连接算法的查询优化处理

基于半联接的查询优化策略的主要思想是不参与联接的值或无用的值不必在网络中来回传输

半连接表示连接的代价估算：

Card(R)片段关系R的元组数目    Size(A)属性A的大小(即字节数)

Size(R)片段关系的大小,  属性大小之和    Val(A[R])属性A在R中出现的不同值的个数

①选择操作   S= σF（R）

Card(S)= ρ *Card(R)  Size(S)=Size(R)  Val(B[S])是Val(B[R]),  Card(S), Card(R)的函数

②并操作   T=R∪S

Card(T) ≤Card(R)+Card(S)  Size(T)=Size(R)=Size(S)  Val(A[T])≤Val(A[R])+Val(A[S])

③连接操作    T=R∞S

Card(T) =(Card(R)*Card(S))/Val(A[R])     Size(T) = Size(R)+Size(S) –Size(A)

Val(A[T]) ≤Min(Val(A[R]), Val(B[S]))   A 是连接属性

Val(A[T]) ≤Val(A[R])+Val(B[S])         A不是连接属性 

④半连接   T=R∝S

ρ =Val(A[S])/Val(Dom(A))      Card(T) = ρ *Card(R)

Size(T) = 第一个操作数Size（R）     Val(A[T]) = ρ *Val(A[R])

采用半连接的总代价

T半R= 2C0+C1* (size (R’)* card( R’) +size (B)* val( B[S]))

T半S= 2C0+C1* (size (S’)* card( S’) +size (A)* val( A[R]))

比较T半R 与T半S,   取最优者

例：举例：已知R1分段F11和F12的大小为: |F11|=|F12|=50，R2分段F21和F22的大小为: |F21|= 100    |F22|=200

设数据通讯C0=0, C1=1,  

本地连接Cost=J(x1, x2)=5*(x1+x2)

并操作Cost = U(x1, x2) = 2*(x1+x2)

①令R1保持分片状态, 则: 站点S1的完成时间     

 FT(Q, S1, R1) = 200+2*(100+200)+5*(50+300)=2550

同理: FT(Q, S2, R1) = 100+2*(100+200)+5*(50+300)=2450

因此, 查询响应时间在R1保持分片状态为 2550.

②令R2保持分片状态, 则: 站点S1的完成时间

FT(Q, S1, R2) = 50+2*(50+50)+5*(100+100)=1250

同理: FT(Q, S2, R2) = 50+2*(50+50)+5*(200+100)=1750

因此, 查询响应时间在R2保持分片状态为 1750.

因为:   R1保持分片状态的响应时间>R2保持分片状态的响应时间

所以:   选择R2保持分片计算查询

设关系R（A，B，C）在场地1，关系S（C，D，E）在场地2，现欲在场地2得到R⋈S的操作结果。（1）用联接的方法，如何执行上述操作。

（2）用半联接的方法，如何执行上述操作。

（1）用联接的方法执行，就是直接把关系R从场地1传输到场地2，在场地2执行自然联

解得：（1）用联接的方法执行，就是直接把关系R从场地1传输到场地2，在场地2执行自然联接。

（2）① 在场地2，求πC（S）的值；

② 把πC（S）的值从场地2传输到场地1；

③ 在场地1执行R⋈πC（S）操作；

④ 把（R⋈πC（S））的值从场地1传输到场地2；

⑤ 在场地2执行（R⋈πC（S））⋈S操作，即求得R⋈S的值。

即R⋈S=（R⋈πC（S））⋈S

 =（R ⋉S）⋈S

%%%%%%%%%%%%%%%%%%%%%第四章：分布式数据库中的事务管理和恢复

事务概念：①事务是访问或更新各种数据项的最小逻辑工作单位。②它是一个操作序列

③它可以使数据库从一个一致状态到另外一个一致状态  ④事务必须保证数据库的一致性

⑤事务执行期间数据库可能不一致

分布式数据库中的事务  分类：全局事务  局部事务

分布式事务特性（ACID特性）

原子性（Atomicity）：事务的操作要么全部执行, 要么全部不执行 ,保证数据库一致性状态

一致性（Consistency）：事务的正确性，串行性，并发执行的多个事务,其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同.  

持久性（Durability）：当事务提交后, 其操作的结果将永久化, 而与提交后发生的故障无关 

隔离性（ Isolation）：虽然可以有多个事务同时执行，但是单个事务的执行不应该感知其他事务的存在，因此事务执行的中间结果应该对其他并发事务隐藏  

进程：系统中可以并行执行的一段操作序列，分布式事务中的子事务序列是进程方式完成的

进程说明：定义进程的行为模式，数据和数据上的操作，功能等

进行执行：按模式来启动这个进程，执行其中的操作

过程：不可并行执行的操作序列

事务代理（Agent）：应用在各个Site上执行的若干进程，称作应用在该Site上的代理。代理可以执行应用程序员写的程序，也可以执行系统的原语函数，不同代理间通过报文实现通讯

根代理（Root Agent） 应用启动Site上的代理。根代理所在的Site称作原发Site. 一般，根代理负责发系统原语，只有根代理可以请求创建新代理。

分布式事务管理目标：维护事务的ACID性质；获得最小的主存和CPU开销，降低报文数目，加快响应时间；获得最大限度的可靠性和可用性

目的：事务能有效、可靠、并发的执行

分布式事务执行的控制模型：

是指协调分布式事务中各成员DBMS执行其子事务的通用方法，有三种:

①主从模型：主、从控制器，LTM之间无通信

②三角模型：LTM之间可以传递数据，避免了主从之间不必要的传输

③层次控制模型：LTM还可再创建Agent，控制其它LTM执行，比前两种复杂

分布式数据库系统中的故障：

事务恢复：当发生故障时，保证事务原子性的措施称为事务故障恢复，简称事务恢复

2PC: 将本地原子性提交行为的效果扩展到分布式事务, 保证了分布式事务提交的原子性, 并在不损坏Log的情况下, 实现快速故障恢复, 提高DDB系统的可靠性.

第一阶段：表决阶段   第二阶段：执行阶段

两类代理:协调者(Coordinator)：提交和撤销事务的决定权，一般是总代理

参与者(Participants)：负责在本地数据库中执行写操作，并且向协调者提出提交和撤销子事务的意向

%%%%%%%%%%%%%%第五章：分布式数据库中的并发控制

锁的相容矩阵：

在如下R, S的概貌上计算     R∞A=B S

    Size(R)=50,   Card(R)=100,   Val(A[R])=50,   Size(A)=3

    Size(S)=5,    Card(S)=50,     Val(B[S])=50,   Size(B)=3

     R∝A=B S  的选择度     ρ =  0.2

     S∝A=B  R  的选择度     ρ =  0.8

C0=0,C1=1

问:

   1. 使用 ∝简化程序在R的站点执行∞

   2. 使用 ∝简化程序在S的站点执行∞

   3. 使用直接连接在R站点执行∞

   4. 使用直接连接在S站点执行∞

 那种方案较优?

解：

1   CostT1 = 2C0+C1(Size(A)*Val(A[R])+Size(S)*Card(S)*ρS∞R)

          = 2C0+C1(3*50+5*50*0.8)

          = 2C0+350C1

               = 350

2   CostT2= 2C0+C1(Size(B)*Val(B[S])+Size(R)*Card(R)*ρR∞S)

          = 2C0+C1(3*50+5*100*0.2)

          = 2C0+1150C1

          =1150

3   CostT3=C0+C1* size (S)* card(S)       4   CostT4=C0+C1* size (R)* card( R)

          = C0+C1*5*50                            = C0+C1*50*100

          = C0+250C1                                             = C0+5000C1

                =250                                   =5000  综上，第三种方案最好