分布式数据库复习要点

1、分布式数据库的定义（1、分布式数据库的定义（P4）分布式数据库复习要点第一章物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。库系统可以看成是计算机网络和数据库系统的有机结合。22、分布式数据库的两种分类方法（P7）DBMS的数据模型分同构型同构型DDBS：各个站点上数据库使用同一数据模型同构同质型-数据模型相同，且是同一种DBMS（同一厂家）同构异质型-数据模型相同，不是同一种DBMS异构型DDBS：各站点上数据库的数据模型类型不同DDBS的全局控制类型分全局控制集中型全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。3、分布式数据库的组成成分（两部分）（P9）数据：分布式数据库的主体，包括局部数据和全局数据。数据：分布式数据库的主体，包括局部数据和全局数据。4、分布式数据库的数据分片的定义和类型（3种）（P10）数据分片：又称数据分割、数据分段，局部数据库是由全局数据库分割而成。三种类型：数据分片：又称数据分割、数据分段，局部数据库是由全局数据库分割而成。三种类型：择运算。择运算。垂直分片：把全局关系的属性集分成若干个子集，对全局关系施加投影运算。混合分片：以上两种方法的混合。5、分布式数据库的分布策略（4条）（P11）数据分布：根据某种策略把数据分片所得的逻辑片断分散地存储在各个站点上数据分布：根据某种策略把数据分片所得的逻辑片断分散地存储在各个站点上.集中式：所有数据都安排在同一站点上集中式：所有数据都安排在同一站点上分割式：所有数据只有一份，被分割成若干个逻辑片段，每个片段被放置在特定的站点复制式：所有数据有多个副本，每个站点都有一个完整的数据副本混合式：分割式和复制式的混合分四层：6分四层：6、分布式数据库的模式结构（P13）全局外层：全局外层：---全局应用的用户视图。全局概念层：---描述全局数据的逻辑结构和数据特性；---描述全局数据的逻辑划分；---根据数据分布策略，定义各片段的物理存放站点。局部概念层：---各个站点上全部物理映像的集合。---全局/本站点数据在本站点的存储描述。7、分布式数据库的功能模块（P.16-17）查询处理模块：任务是减少查询处理的代价完整性处理模块：负责维护数据库的完整性和一致性调度处理模块：发布局部处理命令，管理数据传输可靠性处理模块：负责监视系统的各个部分是否有故障出现。8、分布透明性的层次（三层P.25-26）分布透明性也叫分布独立性，包括三个层次：分布透明性也叫分布独立性，包括三个层次：分片透明性：用户编写应用程序只对全局关系进行操作，不必考虑数据的逻辑分片。分片透明性：用户编写应用程序只对全局关系进行操作，不必考虑数据的逻辑分片。局部数据模型透明性：不必了解站点上数据库的数据模型及其数据对象的表示性质。第二章第二章DDB设计1、DDB设计的两个方法P39-40自顶向下：（自顶向下：（DDB创建方法中的重构法）从头开始设计分布式数据库。根据系统的实现环境和用户需求，按照分布式数据库系统的设计思想和方法，采用统一的观点，从总体设计环境和用户需求，按照分布式数据库系统的设计思想和方法，采用统一的观点，从总体设计做起，包括各站点上的数据库系统，重新建立一个做起，包括各站点上的数据库系统，重新建立一个DDBS。可以有效解决数据一致性、完整性和可靠性问题。通常是同构异质或者同构同质的。和可靠性问题。通常是同构异质或者同构同质的。自底向上：（DDB创建方法中的组合法）通过聚集现存数据库来设计分布式数据库。利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调DDBS。通常是异构或者同构异质。2、DATAID-D方法P52这是自顶向下设计分布式数据库的一个典型方法，增加的两个阶段：这是自顶向下设计分布式数据库的一个典型方法，增加的两个阶段：分布要求分析阶段分布要求分析阶段输入：用户分布要求、全局数据概念模型、全局数据操作模式；输入：用户分布要求、全局数据概念模型、全局数据操作模式；输出：频率表（各个站点每一应用激活次数）、划分表（各实体的潜在水平分片规则）化表（由一个站点发出的一给定应用访问一给定片段的频率）。分布设计阶段分布设计阶段–分片设计：对实体进行水平分片和垂直分片。–分片设计：对实体进行水平分片和垂直分片。3、数据片断分配法P503、数据片断分配法P50PPT相关部分4DATAID方法的应用P55PPT相关部分第三章分布式查询处理和优化city=‘lonoupplie[Supplieity=‘lonon’非冗余分配：利用最佳适应法，把各片段映射到使用最多的站点上。冗余分配：起初使用非冗余分配，在每次迭代时，计算因增加一副本使其变成本个整数，就把该副本存储到该得益站点。局部模式的重新构造：重新构造片段分配站点上的局部模式。113.6的运算要了解（重点PPT上例题）2、查询树,查询变换,限定关系等定义查询变换：从全局查询到片段查询的变换？限定关系:R:QR的限定关系，其中Q表示查询。逻辑片段就是一个限定关系。RR33（重点基本原理：把查询问题转换为关系表达式；关系表达式到查询树（语法树）的变换；全局查询到片段基本原理：把查询问题转换为关系表达式；关系表达式到查询树（语法树）的变换；全局查询到片段查询的变换（把全局查询树中的全局关系名，用重构该全局关系的各片段名替换，变换成相应片段上的查查询的变换（把全局查询树中的全局关系名，用重构该全局关系的各片段名替换，变换成相应片段上的查询树）；利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。询树）；利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。44、3-8）（重点看PPT例题）5、基于直接连接算法的查询优化处理的四种方法，重124算法。重点看书P85)A（进行本站点片段连接再合并就够了），则可以只在同一站点上做片段连接操作，然后合并连接结果。分布到这些站点上，其余被引用关系则复制到每个选定站点中去，这样在每个站点进行本地连接，再合并结果，必然会覆盖到所有该连接的元组（因为每一个站点都有另一个关系的完全副本）。HashHash点依赖计算，再据此分片，比如按连接属性取值为奇偶数来把元组发送到不同站点，这样分片后两个关系必然就满足站点依赖条件，再进行本地连接。这实际是构造站点依赖的一种方法。第四章分布式数据库中的事务管理和恢复第四章分布式数据库中的事务管理和恢复1、分布式事务的定义和特性P97原子性（Atomicity原子性（Atomicity）：,,保证数据库一致性状态。一致性（Consistency）：,其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同。持久性（Durability）：事务提交后,,与提交后发生的故障无关。隔离性（Isolation）：使用。定义：事务是访问数据库的最小逻辑工作单位，它是一个操作序列。分布式事务是一个分布式操作的序列，被操作的数据分布在不同站点上。ACID特性：22、分布式事务的结构P99（一个应用由若干个分布式事务组成，每个分布式事务由不同站点的若干子事务组成）分布式事务的一般结构：BeginTransaction原语：开始一个事务T1[]T2[]:子事务或操作序列:Tn[]Commit原语：事务成功完成的结束Rollback或Abort原语：事务失败的结束33、分布式事务执行的控制模型（三种）P105分布式事务控制模型是指协调分布式事务中各成员分布式事务控制模型是指协调分布式事务中各成员DBMS执行其子事务的通用方法，有三种:主从模型：分布式事务管理器作为主控制器，局部事务管理器主从模型：分布式事务管理器作为主控制器，局部事务管理器之间无通信。间无通信。LTM之间分享的。LTM之间可以传递数据，避免了主从之间不必要的传输。层次控制模型：LTMAgentLTM执行，比前两种复杂。44、事务恢复的概念P108当发生故障时，保证事务原子性的措施称为事务故障恢复，简称事务恢复，主要依靠日志来实现。5、事务的状态和状态转移P109事务在执行过程中的状态变化：事务开始后立即进入活动状态，可以进行读写操作；事务结束时进入部分提交状态；事务到达提交点时进入提交状态；如果检查出故障或者事务在活动状态期间被撤销，则进入故障状态；终止状态表明事务已经离开系统。6、本地事务恢复的过程（P.112）本地事务恢复的过程类似于集中式数据库系统中事务的恢复：Checkpoint的地址,CheckpointLog找最近的检查点）2）Redo表（初态为空）；创建Undo表(CheckpointRecord中的活动事务表)。3）CheckpointRecordlogbegintransactionlog记录，其对应的事务记入Undo表；遇到commit的log记录，其对应事务从UNDO表移入Redo表，直至log完。（在Undo表和Redo表中加响应的事务）Log,Undo表中事务,logUndoBeginTransaction。（执行Undo）从CheckpointRecordRedo表中事务的Log记录,并执行之,直到对应的Commit7、两阶段提交协议定义和原则（P115-116）将本地原子性提交行为的效果扩展到分布式事务7、两阶段提交协议定义和原则（P115-116）将本地原子性提交行为的效果扩展到分布式事务,保证了分布式事务提交的原子性。基本思想是：坚持在分布式事务结果生效之前，所有参与执行分布式事务的站点都同意提交。—目的是形成共同的决定；执行阶—目的是实现这个决定。）全局提交规则：只要至少有一个参与者撤销事务，协调者就必须做出全局撤销的决定；只要至少有一个参与者撤销事务，协调者就必须做出全局撤销的决定；只有所有参与者都同意提交事务，协调者才能做出全局提交的决定。88、两阶段提交协议的通信结构（P117，还是把ppt上图看一下）集中式：通信只发生在协调者和参与者之间，参与者之间不交换信息集中式：通信只发生在协调者和参与者之间，参与者之间不交换信息DTM代理者，协调者与参与者之间的通信不使用直接广播，而是使用报文在树中上下传播。每个DTM代理是通信树的一个内部节点，它从下层节点处收集报文或向它们广播报文。线性：参与者之间可以互相通信。系统中的站点间要排序，消息串行传递。分布式：允许所有参与者在第一阶段相互通信，从而可以独立做出事务终止决定。99、主文本更新法分布式数据库中数据更新方法之一。指定一个副本为主文本,更新时只对主文本进行；然后由主文本站点将主文本更新内容及时发送到各辅文本站点，各辅文本的更新可以并行进行。问题--更新传播必须在短时间内完,否则将获得“过时”数据；主文本不可,将引起其它辅文本也--第五章分布式数据库中的并发控制1、并发控制的定义P131确保并发执行的多个事务能够正确地运行并获得正确的结果。2、串行调度、可串行化调度和一致性调度的定义P133的操作，每个事务相继执行，这样的调度S的操作，每个事务相继执行，这样的调度S为称串行调度。可串行化调度：如果一个调度等价于某个串行调度，则该调度称为可串行化调度。称调度为一致性调度。事务的可串行性：若干个事务并发执行的结果与按希望那个的顺序执行的结果相同时，称诸事务是可串行的。串行调度：若一个调度TiTj33、并发控制算法的分类P140并发控制机制分为两种类型：悲观算法和乐观算法。悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法将同步化延迟到事务执行周期的结束。4、基于封锁的并发控制算法P141基本思想：事务访问数据项之前要对该数据项加锁，如果已经被其他事务加锁，就要等待，直到那个事务释放该锁为止。5、封锁粒度、锁的类型P141锁的粒度：锁定数据项的范围。锁粒度小，并发度高，锁开销大。包括以下几个层次：数据库记录中的一个字段值数据库记录中的一个字段值一条数据库记录一个磁盘块（页面）一个完整的文件整个数据库锁的类型：锁的类型：共享锁：共享锁：Share锁，S锁或者读锁排它锁：eXclusive锁，X锁，拒绝锁或写锁更新锁：Update锁，U锁66P147（读写）都在第一个解锁操作之前，则该事务遵守两阶段封锁协议。这样一个事务可以被分成两个阶段：上升阶段上升阶段(成长阶段)：只能获取新锁，而不能释放已有的锁收缩阶段(衰退阶段）：只能释放已有的锁，而不能获得新锁保守保守2PL：要求事务在开始执行之前就持有所有它要访问的数据项上的锁。严格2PL：事务提交或撤销之前，绝对不释放任何一个写锁；在事务结束时，同时释放所有的锁。严酷2PL：事务在提交或撤销之前，不能释放任何一个锁。7、多粒度锁、意向锁的定义和锁的相容性P153多粒度锁：封锁的粒度不是单一的一种粒度，而是有多种粒度全局时标：使用全局的单调递增的计数器局部时标：全局时标：使用全局的单调递增的计数器局部时标：<本地计数器值，站点标识符>定一个时标，同时附加上其自身的站点标识符。意向锁：如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁；对任一节点封锁时，必须先对它的上层节点加意向锁。包括意向共享锁（IS）、意向排他锁（IX）以及共享意向排他锁（SIX）三种类型。锁的相容性：8、基于时标的并发控制方法基本概念、基本思想、时标分配方法P163基本概念：不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现；时标是用来唯一识别每个事务并允许排序的标识；如果ts(T1)<ts(T2)…<ts(Tn),则调度器产生的序是:T1,T2,...Tn。基本思想：每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行。如果发生冲突，是通过撤销并重新启动一个事务来解决的。事务重新启动时，则赋予新的时标。优点是没有死锁，不必设置锁。时标分配方法：99、多版本法的基本概念P166并发控制的多版本技术。多版本并发控制协议：维护了一个数据项的多个版本值。思想是：通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作。10、多版本2PL的基本思想P167TXT’XX的两个版本实现这样的功能：X’T获得该项上写锁时创建的新版本。其它事务可以继续读XTX’TX的验证锁，一旦获得验证锁，老版本改为最新版本。第六章分布式数据库中的可靠性1、可靠性和可用性的概念及其两者的关系P173可靠性：数据库在一给定时间间隔内不产生任何失败的概率。强调数据库的正确性。可用性：给定的时间t，数据库可以正常运行的概率。强调的是当需要访问数据库时，它是可用的。两者关系：通常认为构建可用性系统比可靠性系统容易通常认为构建可用性系统比可靠性系统容易两者是统一的，可靠性高的系统可用性自然好22、MTTD、MTBF、MTTR三者的定义，及其图示P178平均检测时间平均检测时间统的平均故障潜伏时间称为平均故障检测时间。统的平均故障潜伏时间称为平均故障检测时间。3、分布式可靠性协议的执行过程3、分布式可靠性协议的执行过程P179平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间。平均故障间隔时间(MTBF)：可以自我修复的系统中相继失败之间的期望时间。Begin-TransacrionBegin-Transacrion：登录dMh命令，读出数据后，LTM将它交给调度程序BufferBufferManagerFetch命令，读出数据并修改，同时数据的前像和修改后的后像写入日志。AbortUndoCommit：将事务结束记录写入日志44、分布式可靠性协议的组成（三个协议）P180分布式数据库系统的可靠性协议包括提交协议、终结协议、恢复协议。提交和恢复协议详细说明提交命令和恢复命令是如何执行的提交和恢复协议详细说明提交命令和恢复命令是如何执行的终结协议解决一个站点失效时，未失效站点如何处理该失效事件的问题55、非阻断协议的充要条件和三阶段提交协议的定义P187提交协议是非阻断的充要条件是,在其状态转换图中不存在:没有状态同时与提交状态和撤销状态“相邻”没有不可提交状态与提交状态“相邻”在2PC的等待状态和提交状态之间增加一个状态，作为一个缓冲，用于在准备提交但是还没有提交的时候。因为从初始状态到提交状态之间有三次状态转换，所以称为三阶段提交协议。6、三阶段提交协议的超时处理P189协调者协调者Abort在预备提交状态超时：将所有参与者移入预备提交状态在提交/撤销状态超时：忽略参与者超时参与者超时2PC中的情况相同在就绪状态超时：终结协议在预备提交状态超时：终结协议77P192分为多数表决法和法定人数表决法？多数表决法的基本思想是：如果大多数站点提议执行某事务，那么该事务就被执行。概括为表决基于法定人数。实现提交协议必须满足的规则：每个站点i有选票数Vi,系统总投票数为V。VcVaVa+Vc≤V,当0≤Va,Vc。前两条指出事务终结时必须获得的投票数；最后一条保证事务不能同时既被撤销又被提交。8、采用版本号检测不一致性P200允许对数据项操作的站点的副本是主副本,其它是孤立或隔离的副本。正常工作期间,全部副本都是主副本,并且互相一致,每份副本维持一个原版号和一个当前版本号。初始时原版本号置为0，当前版本号置为1；每当对副本执行一次更新，只是当前版本号加1。网络分割时,每个孤立副本的原版本号被置为当前版本号值。这样直到分割修复为止,此原版号不会改变。这时比较所有副本的当前版本号和原版本号就能暴露出不一致性。（如果分割修复时，发现分割区域原版本号和未分割区域当前版本号不同且分割区域原版本号和分割区域当前版本号也不同，则不一致。各个分割区域中当前版本号不同，也可能不一致。）第七章分布式数据库的安全性和目录管理1、不安全因素的三个方面P207--数据存储在各个站点上存在的不安全因素--访问各个站点上数据存在的不安全因素物理层：保护数据不受侵入者的物理破坏用户层：防止保密字被盗OS层：从访问系统的口令到并发进程之间隔离，都要提供保护网络层：保证是与可信赖的站点通信物理层：保护数据不受侵入者的物理破坏用户层：防止保密字被盗OS层：从访问系统的口令到并发进程之间隔离，都要提供保护网络层：保证是与可信赖的站点通信,保证链路没有被窃听和篡改数据库系统：为不同需求的合法用户授予不同的权限33、数据库安全的术语P211主体主体(Subject)：引起信息流动或改变系统状态的主动实体,客体(Object),DB,表,记录,视图,属性等。可信计算基（trustedcomputingbase）：实现安全保护机制的集合体（包含硬件、固件和软件）。域：主体有能力存取的客体集合安全级(SecurityLevel)：主体和客体的访问特权,一般主体安全级表示主体对客体敏感信息的操作能力,客体安全级表示客体信息的敏感度可信计算基使用它来确定是否使用强制访问控制。最小特权原理：主体在执行授权任务时，应被授予完成该任务所需的最小存取权。访问监控器：监控主体和客体之间授权访问关系的部件。信道：系统内的传输信息的通路。10)隐蔽信道(CovertChannel)：以危害系统安全的隐蔽方式传输信息的通信信道自主访问控制自主访问控制(DiscretionaryAccessControl)：基于主体身份或主体所属组的身份或二者结合来限制对客体访问的方法.具有访问权的主体能自行决定其访问权直接或间接转授给别人。强制访问控制(MandatoryAccessControl)：基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问.标记是由系统安全员指,,更不能数据库的安全策略:形式化安全保护策略模型安全保护策略的完整精确描述。安全保护策略模型安全保护策略的非形式化描述44、面向用户的口令法P2155、多级安全模型的系统状态定义P217P模型系统状态vV中的元素，BMF)BBSOOA为访问方式集合；M是存取控制矩阵，每个元素表示主体对客体的访问权限集合；F为安全级函数；H为当前客体层次结构。6、自主访问控制和强制访问控制见术语部分7、数据库安全评估标准的分类和分级P2271991TCSEC制订紫皮书《可信计算机系统评估标准的可信DBMS说明》，DBMS的安全分4类,7级,25条评估标准：DD：最低保护C：自主保护类,基于主体身份来限制对客体访问。C1C1级：自主安全保护C2级：可控存取保护––B：强制保护类,基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问客体的访问B1B1级：标记安全保护B2级：结构化保护B3级：安全域保护––A：验证保护类A1A1级：可验证保护88、身份认证的三个级别P229系统登录认证：OS检查数据库连接：DBMS验证第八章分布式数据库与C/S第八章分布式数据库与C/S模式结构1、C/S模式定义和当前流行的两种模式P242C/S所有的应用都在客户机站点运行；一般不提供完全的位置透明性。当前流行的两种模式：传统的两层结构C/S 服务器（或服务器群）存储数据，客户机群存取数据，服务器扮演支配角色。正在涌现的三层C/S 数据层、功能层和表示层：数据层是驻留在主机上的DBMS；功能层是应用服务器，负责应用逻辑处理；表示层由客户机实现，是应用的用户接口。数据库对象使用：DBMS核实其对数据对象的存取权限