DBA 分布式数据库复习总结

查询变换：从全局查询到片段查询的变换？

 

l  限定关系:  R:Q_R 称为R的限定关系，其中Q_R 表示查询。逻辑片段就是一个限定关系。

s _{city=‘london’}(Supplier) 的限定关系:  [Supplier: s _{city=‘london’}]

 

 

3、   基于关系代数等价变换的查询优化实例（重点看P80-82）

基本原理：把查询问题转换为关系表达式；关系表达式到查询树（语法树）的变换；全局查询到片段查询的变换（把全局查询树中的全局关系名，用重构该全局关系的各片段名替换，变换成相应片段上的查询树）；利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。

 

 

4、   基于半连接的算法的查询优化的操作过程和代价估算（83-84） （重点看PPT例题）

 

 

5、   基于直接连接算法的查询优化处理的四种方法，重点1、2、4算法。 (重点看书P85)

l  站点依赖：如果两个关系不同站点的分片在属性A上没有交集（说明它们之间连接结果为空，只进行本站点片段连接再合并就够了），则可以只在同一站点上做片段连接操作，然后合并连接结果。

l  分片和复制：如果不符合站点依赖的条件，则选择一组站点，把查询引用的某个关系的所有片段分布到这些站点上，其余被引用关系则复制到每个选定站点中去，这样在每个站点进行本地连接，再合并结果，必然会覆盖到所有该连接的元组（因为每一个站点都有另一个关系的完全副本）。

l  Hash划分：如果两个关系不符合站点依赖的条件，利用Hash函数对分片关系上的连接属性作站点依赖计算，再据此分片，比如按连接属性取值为奇偶数来把元组发送到不同站点，这样分片后两个关系必然就满足站点依赖条件，再进行本地连接。这实际是构造站点依赖的一种方法。

 

 

 

 

 

 

 

 

 

 

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

 

1、分布式事务的定义和特性  P97

定义：事务是访问数据库的最小逻辑工作单位，它是一个操作序列。分布式事务是一个分布式操作的序列，被操作的数据分布在不同站点上。

ACID特性：

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

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

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

l  隔离性（ Isolation）：事务在提交前，决不允许把它对共享数据所作改变的结果提供给其他事务使用。

 

2、分布式事务的结构  P99

（一个应用由若干个分布式事务组成，每个分布式事务由不同站点的若干子事务组成）

分布式事务的一般结构：

Begin Transaction原语：开始一个事务

           T1[]

           T2[]

              :                子事务或操作序列

              :

           Tn[]

Commit原语：事务成功完成的结束

Rollback或Abort原语：事务失败的结束

 

3、   分布式事务执行的控制模型（三种）P105

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

l  主从模型：分布式事务管理器作为主控制器，局部事务管理器（LTM）作为从属控制器，LTM之间无通信。

l  三角模型：控制权是分布式事务管理器和LTM之间分享的。LTM之间可以传递数据，避免了主从之间不必要的传输。

 

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

 

 

4、事务恢复的概念  P108

当发生故障时，保证事务原子性的措施称为事务故障恢复，简称事务恢复，主要依靠日志来实现。

 

5、事务的状态和状态转移  P109

事务在执行过程中的状态变化：事务开始后立即进入活动状态，可以进行读写操作；事务结束时进入部分提交状态；事务到达提交点时进入提交状态；如果检查出故障或者事务在活动状态期间被撤销，则进入故障状态；终止状态表明事务已经离开系统。

   

 

6、本地事务恢复的过程（P.112）

本地事务恢复的过程类似于集中式数据库系统中事务的恢复：

1）   从“重启动文件”  读出最近Checkpoint的地址, 定出Checkpoint在Log文件中的位置。  （找最近的检查点）

2）   创建Redo表（初态为空）；创建 Undo表(即Checkpoint Record中的活动事务表)。

3）   从Checkpoint Record起沿log向前检索，遇到begin transaction的log记录，其对应的事务记入Undo表；遇到commit的log记录，其对应事务从UNDO表移入Redo表，直至log完。   （在Undo表和Redo表中加响应的事务）

4）   反向检索Log, 将Undo表中事务, 按log记录的操作，做Undo，直到遇到对应的Begin Transaction。  （执行Undo）

5）   从Checkpoint Record起正向检索Redo表中事务的Log记录, 并执行之, 直到对应的Commit记录。 （执行Redo）

 

7、两阶段提交协议定义和原则（P115-116）

将本地原子性提交行为的效果扩展到分布式事务, 保证了分布式事务提交的原子性。基本思想是：坚持在分布式事务结果生效之前，所有参与执行分布式事务的站点都同意提交。（2PC把提交过程分为两个阶段：表决阶段—目的是形成共同的决定；执行阶段—目的是实现这个决定。）

全局提交规则：

l  只要至少有一个参与者撤销事务，协调者就必须做出全局撤销的决定；

l  只有所有参与者都同意提交事务，协调者才能做出全局提交的决定。

 

8、两阶段提交协议的通信结构（P117，还是把ppt上图看一下）

?    集中式：通信只发生在协调者和参与者之间，参与者之间不交换信息

?    分层式：协调者是在树根的DTM代理者，协调者与参与者之间的通信不使用直接广播，而是使用报文在树中上下传播。每个DTM代理是通信树的一个内部节点，它从下层节点处收集报文或向它们广播报文。

?    线性：参与者之间可以互相通信。系统中的站点间要排序，消息串行传递。

?    分布式：允许所有参与者在第一阶段相互通信，从而可以独立做出事务终止决定。

 

9、主文本更新法

分布式数据库中数据更新方法之一。

指定一个副本为主文本, 更新时只对主文本进行；然后由主文本站点将主文本更新内容及时发送到各辅文本站点，各辅文本的更新可以并行进行。

问题--更新传播必须在短时间内完成, 否则将获得“过时”数据；主文本不可用, 将引起其它辅文本也不可用。改进方法--移动主文本法。

 

 

 

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

 

1、并发控制的定义  P131

并发控制就是负责正确协调并发事务的执行，保证并发存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。

 

2、串行调度、可串行化调度和一致性调度的定义  P133

?    串行调度：若一个调度S，其每个事务的执行均有Ti<Tj，即事务Ti的所有操作都先于事务Tj的操作， 每个事务相继执行，这样的调度S为称串行调度。

?    可串行化调度：如果一个调度等价于某个串行调度，则该调度称为可串行化调度。

?    一致性调度：执行一个调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度。

?    事务的可串行性：若干个事务并发执行的结果与按希望那个的顺序执行的结果相同时，称诸事务是可串行的。

 

3、并发控制算法的分类   P140

并发控制机制分为两种类型：悲观算法和乐观算法。悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法将同步化延迟到事务执行周期的结束。

 

4、基于封锁的并发控制算法  P141

基本思想：事务访问数据项之前要对该数据项加锁，如果已经被其他事务加锁，就要等待，直到那个事务释放该锁为止。

 

5、封锁粒度、锁的类型    P141

锁的粒度：锁定数据项的范围。锁粒度小，并发度高，锁开销大。

包括以下几个层次：

?    数据库记录中的一个字段值

?    一条数据库记录

?    一个磁盘块（页面）

?    一个完整的文件

?    整个数据库

     锁的类型：

–        共享锁：Share锁，S锁或者读锁

–        排它锁：eXclusive锁，X锁，拒绝锁或写锁

–        更新锁：Update锁，U锁

 

6、两阶段封锁协议   P147

     一个事务所有的封锁操作（读写）都在第一个解锁操作之前，则该事务遵守两阶段封锁协议。这样一个事务可以被分成两个阶段：

l  上升阶段(成长阶段)：只能获取新锁，而不能释放已有的锁

l  收缩阶段(衰退阶段）：只能释放已有的锁，而不能获得新锁

保守2PL：要求事务在开始执行之前就持有所有它要访问的数据项上的锁。

严格2PL：事务提交或撤销之前，绝对不释放任何一个写锁；在事务结束时，同时释放所有的锁。

严酷2PL：事务在提交或撤销之前，不能释放任何一个锁。

 

7、多粒度锁、意向锁的定义和锁的相容性   P153

多粒度锁：封锁的粒度不是单一的一种粒度，而是有多种粒度

意向锁：如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁；对任一节点封锁时，必须先对它的上层节点加意向锁。包括意向共享锁（IS）、意向排他锁（IX）以及共享意向排他锁（SIX）三种类型。

锁的相容性：

8、基于时标的并发控制方法基本概念、基本思想、时标分配方法  P163

基本概念：不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现；时标是用来唯一识别每个事务并允许排序的标识；如果 ts(T1) < ts(T2) … < ts(Tn), 则调度器产生的序是: T1,T2, ... Tn。

基本思想：每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行。如果发生冲突，是通过撤销并重新启动一个事务来解决的。事务重新启动时，则赋予新的时标。优点是没有死锁，不必设置锁。

时标分配方法：

–   全局时标：使用全局的单调递增的计数器

–   局部时标：<本地计数器值，站点标识符>。每个站点基于其本地计数器自治地指定一个时标，同时附加上其自身的站点标识符。

 

9、多版本法的基本概念  P166

并发控制的多版本技术。

多版本并发控制协议：维护了一个数据项的多个版本值。思想是：通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作。

 

10、多版本2PL的基本思想  P167

当一个事务T持有数据项X的写锁时，其他事务T’依旧可以读X。通过X的两个版本实现这样的功能：一个版本是最近已提交版本；另外一个X’是事务T获得该项上写锁时创建的新版本。其它事务可以继续读X的已提交版本，而事务T可以根据需要更新X’的值。在T提交之前需要获得X的验证锁，一旦获得验证锁，老版本改为最新版本。

 

 

第六章 分布式数据库中的可靠性

 

1、可靠性和可用性的概念及其两者的关系   P173

可靠性：数据库在一给定时间间隔内不产生任何失败的概率。强调数据库的正确性。

可用性：给定的时间t，数据库可以正常运行的概率。强调的是当需要访问数据库时，它是可用的。

    两者关系：

–        通常认为构建可用性系统比可靠性系统容易

–        两者是统一的，可靠性高的系统可用性自然好

–        两者又是矛盾的，增加错误风险的情况下，可提高可用性；采用太谨慎的策略会降低可用性。

 

2、MTTD、MTBF、MTTR三者的定义，及其图示  P178

l  平均检测时间(MTTD)：一个故障在它发生一段时间后才被检测出，这一段时间叫潜伏期，同种系统的平均故障潜伏时间称为平均故障检测时间。

l  平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间。

l  平均故障间隔时间(MTBF)：可以自我修复的系统中相继失败之间的期望时间。

3、分布式可靠性协议的执行过程  P179

–   Begin-Transacrion：登录

–   Read：LTM先在事务处理的缓冲区中读，若不在，则向缓冲区管理器发Fetch命令，读出数据后，LTM将它交给调度程序

–   Write：若在Buffer中得到，则在那更新，否则对Buffer Manager发Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入日志。

–   Abort：根据日志做Undo

–   Commit：将事务结束记录写入日志

 

4、分布式可靠性协议的组成（三个协议）  P180

分布式数据库系统的可靠性协议包括提交协议、终结协议、恢复协议。

–        提交和恢复协议详细说明提交命令和恢复命令是如何执行的

–        终结协议解决一个站点失效时，未失效站点如何处理该失效事件的问题

 

5、非阻断协议的充要条件和三阶段提交协议的定义   P187

提交协议是非阻断的充要条件是, 在其状态转换图中不存在:

?         没有状态同时与提交状态和撤销状态“相邻”

?         没有不可提交状态与提交状态“相邻”

在2PC的等待状态和提交状态之间增加一个状态，作为一个缓冲，用于在准备提交但是还没有提交的时候。因为从初始状态到提交状态之间有三次状态转换，所以称为三阶段提交协议。

 

6、三阶段提交协议的超时处理  P189

?    协调者

–   在等待状态超时：协调者单方面Abort

–   在预备提交状态超时：将所有参与者移入预备提交状态

–   在提交/撤销状态超时：忽略

?    参与者超时

–   在初始状态超时：与2PC中的情况相同

–   在就绪状态超时：终结协议

–   在预备提交状态超时：终结协议

 

7、网络分割中基于表决的协议    P192

     分为多数表决法和法定人数表决法？

多数表决法的基本思想是：如果大多数站点提议执行某事务，那么该事务就被执行。概括为表决基于法定人数。实现提交协议必须满足的规则：

每个站点i有选票数Vi, 系统总投票数为V。

l  事务在提交前，它必须获得提交法定票数Vc

l  事务在撤销前，它必须获得撤销法定票数Va

l  Va+Vc≤V, 当0 ≤Va, Vc ≤V。

前两条指出事务终结时必须获得的投票数；最后一条保证事务不能同时既被撤销又被提交。

 

8、采用版本号检测不一致性  P200

允许对数据项操作的站点的副本是主副本, 其它是孤立或隔离的副本。正常工作期间, 全部副本都是主副本, 并且互相一致, 每份副本维持一个原版号和一个当前版本号。初始时原版本号置为0，当前版本号置为1；每当对副本执行一次更新，只是当前版本号加1。网络分割时, 每个孤立副本的原版本号被置为当前版本号值。这样直到分割修复为止, 此原版号不会改变。这时比较所有副本的当前版本号和原版本号就能暴露出不一致性。（如果分割修复时，发现分割区域原版本号和未分割区域当前版本号不同且分割区域原版本号和分割区域当前版本号也不同，则不一致。各个分割区域中当前版本号不同，也可能不一致。）

 

 

 

 

 

 

第七章 分布式数据库的安全性和目录管理

 

1、不安全因素的三个方面  P207

--数据存储在各个站点上存在的不安全因素

--访问各个站点上数据存在的不安全因素

--数据在各站点之间传输时存在的不安全因素

 

2、安全层次（五个层次）  P209

?         物理层：保护数据不受侵入者的物理破坏

?         用户层：防止保密字被盗

?         OS层：从访问系统的口令到并发进程之间隔离，都要提供保护

?         网络层：保证是与可信赖的站点通信,保证链路没有被窃听和篡改

?         数据库系统：为不同需求的合法用户授予不同的权限

 

3、   数据库安全的术语  P211

1）   主体(Subject)：引起信息流动或改变系统状态的主动实体, 如用户、程序、进程。

2）   客体(Object)：蕴含或接收信息的被动实体，信息的载体,如DB, 表,记录, 视图,属性等。

3）   可信计算基（trusted computing base）：实现安全保护机制的集合体（包含硬件、固件和软件）。

4）   域：主体有能力存取的客体集合

5）   安全级(Security Level)：主体和客体的访问特权, 一般主体安全级表示主体对客体敏感信息的操作能力,客体安全级表示客体信息的敏感度

6）   敏感度标记：表示客体和主体的安全级的一条信息。可信计算基使用它来确定是否使用强制访问控制。

7）   最小特权原理：主体在执行授权任务时，应被授予完成该任务所需的最小存取权。

8）   访问监控器：监控主体和客体之间授权访问关系的部件。

9）   信道：系统内的传输信息的通路。

10)    隐蔽信道(Covert Channel)：以危害系统安全的隐蔽方式传输信息的通信信道

11)    自主访问控制(Discretionary Access Control)：基于主体身份或主体所属组的身份或二者结合来限制对客体访问的方法.具有访问权的主体能自行决定其访问权直接或间接转授给别人。

12)    强制访问控制(Mandatory Access Control)：基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问.标记是由系统安全员指派,用户不能随意修改, 更不能转让。

13)    数据库的安全策略:根据用户需求、安装环境、建立规则和法律等方面的限制来制定的，用来描述访问规则和访问特征的关系。

14)    形式化安全保护策略模型：安全保护策略的完整精确描述。

15)    安全保护策略模型：安全保护策略的非形式化描述

 

4、面向用户的口令法   P215

   面向用户的口令系统是每个用户或每个组用户有一个口令，该口令允许用户只能访问他所需要的数据对象。

 

5、多级安全模型的系统状态定义  P217

多级安全BLP模型系统状态v是集合V中的元素， V=(B′ M ′ F ′ H) ：B为当前存取集, B í (S ′ O ′ A) ,S为主体集， O为客体集 ，A为访问方式集合；M是存取控制矩阵，每个元素表示主体对客体的访问权限集合；F为安全级函数；H为当前客体层次结构。

 

6、自主访问控制和强制访问控制  

    见术语部分

 

7、数据库安全评估标准的分类和分级   P227

    1991年美国国家计算机安全中心根据TCSEC制订紫皮书《可信计算机系统评估标准的可信DBMS说明》，DBMS的安全分4类,7级, 25条评估标准：

–        D：最低保护

–        C：自主保护类,基于主体身份来限制对客体访问。

?         C1级：自主安全保护

?         C2级：可控存取保护

–        B：强制保护类,基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问

?         B1级：标记安全保护

?         B2级：结构化保护

?         B3级：安全域保护

–        A：验证保护类

?         A1级：可验证保护

 

8、身份认证的三个级别    P229

系统登录认证： OS检查

数据库连接 ：DBMS验证

数据库对象使用：DBMS核实其对数据对象的存取权限

 

 

 

 

 

第八章 分布式数据库与C/S模式结构

 

1、C/S模式定义和当前流行的两种模式  P242

C/S模式系统：某些站点是客户机站点，而另一些站点是服务器站点；所有的数据驻留在服务器站点；所有的应用都在客户机站点运行；一般不提供完全的位置透明性。

当前流行的两种模式：

1）传统的两层结构C/S-----服务器（或服务器群）存储数据，客户机群存取数据，服务器扮演支配角色。

2）正在涌现的三层C/S------数据层、功能层和表示层：数据层是驻留在主机上的DBMS；功能层是应用服务器，负责应用逻辑处理；表示层由客户机实现，是应用的用户接口。

 

2、   计算环境演变过程中的五个系统   P249

l  主机处理系统：所有程序在一个主机上运行

l  文件处理系统：应用处理(包括数据处理)都发生在PC工作站，文件服务器仅从硬盘查询所需要的文件通过网络发送给用户PC机。

l  C/S处理系统：Client通过网络请求服务，Server提供服务。

l  多处理器服务系统：存在两个或两个以上服务器的C/S系统

l  对等处理系统：C/S系统的最终归宿, 站点既是客户机又是服务器

 

3、   数据分布基本形式   P260

复制数据、子集数据、重新组织的数据、分区数据、独立模式数据、不相容数据

 

4、   分布式数据访问的几种类型    P266

l  远程请求：只涉及单个远程服务器的单个请求

l  远程事务：允许一个事务中包含多个数据访问请求，这些请求都引用同一个远程服务器站点上的数据

l  分布式事务：一个事务包含多个数据请求, 每个请求只能访问单个服务器，不同请求可以访问不同的远程服务器站点

l  分布式请求：一个事务包含多个数据请求,每个请求都可以引用驻留于多个服务器站点数据

 

5、   基于B/S模式系统的Microsoft实现方案 

 

 

第十章   云计算

 

1、云计算的定义（自己总结）

由专业网络公司将存储和计算能力集中起来成为一个虚拟的资源池来为整个网络提供服务，用户通过浏览器就可以很方便的访问，把“云”作为资料存储以及应用服务的中心。“云”可以计费，用户按需购买。这种模式类似于用电不需要家家装备发电机，直接从电力公司购买一样。

 

2、云计算的几种形式（七种）

1）SAAS（软件即服务）：通过浏览器把程序传给成千上万的用户

2）实用计算：为IT行业创造虚拟的数据中心，把存储和计算能力集中起来

3）网络服务：提供API让开发者能够开发更多基于互联网的应用

4）平台即服务：把开发环境作为一种服务来提供

5）MSP（管理服务提供商）：面向的IT管理人员，例如用于电子邮件的病毒扫描服务

6）商业服务平台 ：为用户和提供商之间的互动提供了一个平台

7）互联网整合 ：将互联网上提供类似服务的公司整合起来

 

3、当前典型的几个云计算平台（Amazon, Google, IBM, Microsoft)

l  Amazon使用弹性计算云（EC2）和简单存储服务（S3）为企业提供计算和存储服务

l  Google推出了谷歌应用软件引擎服务，让开发人员可免费使用谷歌的基础设施来进行托管（最高存储空间达 500MB）

l  IBM提供“蓝云”计算平台，为客户带来即买即用的云计算平台，它包括一系列的自动化、自我管理和自我修复的虚拟化云计算软件

l  微软提供均衡搭配的企业级软件、合作伙伴托管服务以及云服务，即软件加服务

DBA 分布式数据库复习总结

标签：