分布式数据库系统-复习414课件

主讲教师:孟桂娥分布式数据库系统1.考核方式1.平时成绩(出勤+课堂练习+大作业）（40%）2.期末考试（闭卷）（60%）2.考试题型填空题（总20分，每空1分）简答题（总30分）计算与分析（总50分，3题）3.第一章4.数据库计算机网络分布式数据库5.1数据库系统知识DBMS

数据库应用程序员

最终用户2最终用户1最终用户3应用程序员存取数据库中的大量数据，或编写程序来存取并处理数据库中的数据。

最终用户通过终端设备，使用简便的查询命令来存取数据库中的数据。

数据库管理员全面负责建立、维护和管理数据库系统。数据库管理员数据库系统用户6.1.数据库系统知识数据间的联系

一对一的联系，记为1﹕1

一对多的联系，记为1﹕n

多对多的联系，记为m﹕n7.

数据库系统结构数库据应用程序应用程序应用程序外模式A外模式B

外模式/模式

概念模式

模式/内模式用户级数据库概念级数据库物理级数据库DBMSOS

内模式数据库系统知识回顾1所谓视图，就是指观察、认识和理解数据的范围、角度和方法，是数据库在用户“眼中”的反映。8.1．模式：也称为概念模式，是数据库全体数据的全局逻辑结构和特征的描述。2．外模式：是关于用户数据的局部逻辑结构和特征的描述，是模式的逻辑子集。3．内模式：是数据库数据的物理结构和存储结构的描述。4．模式/内模式映象：该映象存在于模式与内模式之间，用于定义模式与内模式之间的对应性。本映象一般在内模式中描述。5．外模式/模式映象：该映象存在于外模式与模式之间，用于定义外模式和模式之间的对应性。本映象一般在外模式中描述。在数据库系统的三级模式结构中，存在模式/内模式的映象，当内模式发生变化时，只要修改模式/内模式的映象，就可以保持模式不变，从而保证程序与数据的物理独立性。6．物理独立性：在数据库系统的三级模式结构中，存在外模式/模式的映象，当模式发生变化时，只要修改外模式/模式的映象，即可保持外模式不变，从而保证程序和数据的逻辑独立性。7．逻辑独立性：

数据库系统结构数据库系统知识回顾19.

分布式数据库的定义和特点分布式数据库系统的定义和分类分布式数据库定义（P.4）：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。分布式数据库系统的特点（P.4~5）物理分布性：数据不是存放在一个站点上逻辑整体性：是与分散式数据库系统的区别站点自治性：是与多处理机的系统的区别10.

分布式数据库的分类分布式数据库系统的定义和分类按局部DBMS的数据模型分类（P.7）同构型DDBS同构同质型同构异质型异构型DDBS按DDBS的全局控制类型分类（P.8）全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。全局控制可变型DDBS：也称主从型DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。11.数据分片（P.10）又称数据分割、数据分段，局部数据库是由全局数据库分割而成水平分片（对全局关系施加选择运算）垂直分片（对全局关系施加投影运算）混合分片（两种方法的混合）数据分片要准守的原则：完备性原则：要把所有的数据映射到各个片断中可重构原则：关系分片后的各个片断可重构整个关系不相交原则：关系分片后的各个片断不能重叠DDBS中数据的分片与分布

分布式数据库系统的体系结构和组成成分12.分布式数据库是多层的，国内分为四层：全局外层：全局外模式全局概念层：全局概念模式、分片模式和分配模式局部概念层：局部概念模式局部内层：局部内模式

分布式数据库的模式结构分布式数据库系统的体系结构和组成成分13.最重要的问题是通信网络速度问题。如何尽可能地减少对网络的使用，即尽可能地减少在网络上传输的数据量和通信次数，是DDBS设计的最重要的目标。DDBS中存在的技术问题DDBS的优点和存在的技术问题14.第二章15.DDBS创建方法组合法(又叫:集成法)重构法16.假若有全局关系R被分片为子关系(片段)集合

R={R1,R2,…,Rn},则R满足完整性如果x

R,RiR必有

xRi

，i=1,2,…,n可重构性R=∪Ri(水平分片）,R=∞

Ri

（垂直分片）不相交性Ri

∩

Rj

=空集,i≠j,i,j=1,2,…,n(水平分片)Ri

∩

Rj

=主键属性,i,j=1,2,…,n(垂直分片)2.2

数据的分片设计2自顶向下设计DDB

分片原则17.P={p1,p2,…,pn}是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。具有完整性和最小性不是必要条件,但是对于简化分配问题有好处2.2

数据的分片设计2自顶向下设计DDB

基本水平分片18.例子EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定，应用经常查询的内容是属于部门1且是程序员的职员。则可能有的水平分段限定

P={DEPT=1}（不是完整的）

P={DEPT=1,JOB=‘P’}（是完整的、最小的）

P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）2.2

数据的分片设计2自顶向下设计DDB

基本水平分片19.第三章20.1.2

分布式查询优化准则和代价分析1分布式查询优化概述准则：使得通讯费用最低和响应时间最短，即以最小的总代价，在最短的响应时间内获得需要的数据。21.专门的关系运算学号学生姓名所属系名学生年龄

S#SNSDSAS1ACS20S2BCS21S3CMA19S4DCI19S5EMA20S6FCS22S(S#,SN,SD,SA)2.1

关系代数知识回顾2分布式查询优化中的基础知识22.

在关系R中选择满足给定条件的元组，记做：

σF(R)={t|t∈RΛF(t)=‘真’}F是一个公式，表示形式为由逻辑运算符（∧,∨,٦)连接各算术表达式组成。算术表达式的基本形式为：XθY.θ={>,≥,<,≤,=,≠}

。例1求计算机科学系CS的学生σSD=‘CS’(S)学号学生姓名所属系名学生年龄

S#SNSDSAS1ACS20S2BCS21S3CMA19S4DCI19S5EMA20S6FCS22(a)(S)(S’)S#SNSDSAS1ACS20S2BCS21S6FCS22σSD=‘CS’(S)

选择运算Select*fromSwhereSD=‘CS’;23.

在关系R中选择满足给定条件的元组，记做：

σF(R)={t|t∈RΛF(t)=‘真’}例2求计算机科学系CS，年龄不超过21岁的学生。σ

SD=‘CS’∧SA≤21(S)(S’)S#SNSDSAS1ACS20S2BCS21

选择运算(S’)S#SNSDSAS1ACS20S2BCS21S6FCS22σSD=‘CS’(S)学号学生姓名所属系名学生年龄

S#SNSDSAS1ACS20S2BCS21S3CMA19S4DCI19S5EMA20S6FCS22(S)Select*fromSwhereSD=‘CS’andAGE<=21;24.

投影运算

这是从列的角度进行的运算。例3πSN,SD(S)

即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。πSN,SD(S)学号学生姓名所属系名学生年龄

S#SNSDSAS1ACS20S2BCS21S3CMA19S4DCI19S5EMA20S6FCS22(a)(S)

关系R上的投影是从R中选择若干属性列组成新的关系。记做：

πA(R)={t[A]|t∈R}投影之后不仅取消了某些列，还可能取消某些元组。SNSDACSBCSCMADCIEMAFCSselectSN,SDfromS;25.2.1关系代数知识回顾2分布式查询优化中的基础知识连接运算内连接(innerjoin)使用比较运算符进行表间某(些)列数据的比较操作，并列出这些表中与连接条件相匹配的数据行。

等值连接自然连接(特殊情况:半连接)

不等连接外连接(outerjoin)与内连接不同的是，外连接不只列出与连接条件相匹配的行，而是列出左表(左外连接时)、右表(右外连接时)或两个表(全外连接时)中所有符合搜索条件的数据行。

左外连接(LEFTOUTERJOIN或LEFTJOIN)

右外连接(RIGHTOUTERJOIN或RIGHTJOIN)

全外连接(FULLOUTERJOIN或FULLJOIN)交叉连接没有where子语句,等价于广义笛卡尔积连接运算26.

内连接之一---等值连接例5设关系R、S如下图：2b52b310b37b23b1EBS12b4a28b3a26b2a15b1a1CBARAR.BCS.BEa1b15b13a1b26b27a2b38b310a2b38b32RS∞

R.B=S.Bθ为“＝”的连接运算称为等值连接:

select*fromRinnerjoinSonR.B=S.B;

27.ABCEa1b153a1b267a2b3810a2b382RS∞

AR.BCS.BEa1b15b13a1b26b27a2b38b310a2b38b32RS∞

R.B=S.B自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。

例6关系R、S的自然连结：RS∞

selectdistinctR.*,S.EfromRinnerjoinSonR.B=S.B;

内连接之二---自然连接(∞)28.

内连接特殊形式:半连接

在R、S自然连接后仅保留对R的属性的投影，记为：R∝S

例7关系R、S的半连接：ABCEa1b153a1b267a2b3810a2b382RS∞

ABCa1b15a1b26a2b38R∝S2b52b310b37b23b1EBS12b4a28b3a26b2a15b1a1CBARselectR.*fromRinnerjoinSonR.B=S.B;

29.内连接之三---不等连接（θ连接）

连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记做:RS.

其中，F是条件表达式，它涉及到对两个关系中的属性的比较。∞

FS2b52b310b37b23b1EB12b4a28b3a26b2a15b1a1CBARRS∞

C<E10b38b3a210b36b2a17b26b2a110b35b1a17b25b1a1ES.BCR.BA例4设关系R、S如下图：RS∞

C<Eselect*fromRinnerjoinSonR.C<S.E;

30.2.1

用关系代数和SQL语句表示一个查询2分布式查询优化中的基础知识关系代数基本操作：并（∪）、交（∩）、笛卡尔积（×）选择（）、投影（）关系代数到处操作：差（－）、除（÷）

θ连接（∞θ

）、自然连接（∞）、半连接（∝）31.SQL与代数的等价描述E1SELECTSNAMEFROMS,SCWHERES.S#=SC.S#andSC.C#=‘C03’;代数描述

SNAME(S.S#=SC.S#andSC.C#=‘C03’(S×SC))2.1

用关系代数和SQL语句表示一个查询2分布式查询优化中的基础知识设教学数据库中有三个关系：学生关系S（S#，SNAME，AGE，SEX）课程关系C（C#，CNAME,TEACHER）学习关系SC（S#，C#，GRADE）查询选修课程号为’C03’的学生姓名。32.E2SELECTSNAMEFROMSWHERES.S#in(SELECTSC.S#FROMSCWHERC#=‘C03’);代数描述

SNAME(S.S#=SC.S#(S×

SC.C#=‘C03’SC))E3SELECTSNAMEFROMS,(SELECTSC.S#FROMSCWHERC#=‘C03’)SCCWHERES.S#=SCC.S#;代数描述

SNAME(S∞

SC.C#=‘C03’SC)33.SQL与代数的等价描述E1SELECTSNAMEFROMS,SCWHERES.S#=SC.S#andSC.C#=‘C03’;代数描述

SNAME(S.S#=SC.S#andSC.C#=‘C03’(S×SC))2.1

用关系代数和SQL语句表示一个查询2分布式查询优化中的基础知识设教学数据库中有三个关系：学生关系S（S#，SNAME，AGE，SEX）课程关系C（C#，CNAME,TEACHER）学习关系SC（S#，C#，GRADE）查询选修课程号为’C03’的学生姓名。34.E2SELECTSNAMEFROMSWHERES.S#in(SELECTSC.S#FROMSCWHERC#=‘C03’);代数描述

SNAME(S.S#=SC.S#(S×

SC.C#=‘C03’SC))E3SELECTSNAMEFROMS,(SELECTSC.S#FROMSCWHERC#=‘C03’)SCCWHERES.S#=SCC.S#;代数描述

SNAME(S∞

SC.C#=‘C03’SC)35.2.2

查询树2分布式查询优化中的基础知识

sname

s.s#=sc.s#c#=‘c03’

SSC

sname

s.s#=sc.s#

S

c#=‘c03’SC

sname∞

S

c#=‘c03’SC(a)对于E1的查询树(b)对于E2的查询树(c)对于E3的查询树节点表示一个一元或二元操作符叶子表示已知关系树根表示查询结果36.局部查询：只涉及本地单个站点的数据,优化同集中式。选择和投影早做，中间结果大大减少连接前进行预处理（属性排序、属性索引）同时执行一串投影和选择操作3.1

分布式查询分类3分布式查询的分类与层次结构37.第四章38.ACID特性原子性（Atomicity）

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

并发执行的多个事务,其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同。隔离性（

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

持久性（Durability）

当事务提交后,其操作的结果将永久化,而与提交后发生的故障无关。1.1

分布式事务定义和特性1分布式事务概述分布式事务特性39.第五章40.调度等价S1与S2等价,也就是说,对于冲突操作,<Oi,Oj>,Oi<Oj在S1中成立,同时Oi<Oj

在S2中也成立可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度。1.2

事务可串行化理论1并发控制的概念和理论41.优先图P(S)调度S的优先图是一个有向图G(N,E)，其中N:一组节点N={T1T2,…,Tn},S中的事务E:一组有向边E={e1,e2,…,en},Ti

Tj

是图中的一条边，当且仅当pTi,qTj

使得p,q冲突，并且p<Sq1.3

分布式事务的可串行化调度测试1并发控制的概念和理论42.测试调度S的可串行化对于调度S中的事务Ti，在图中创建一个节点Ti；对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（Ti→Tj）；对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj）；对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj）。当且仅当优先图中没有闭环时，调度S是可串行化的。1.3

分布式事务的可串行化调度测试1并发控制的概念和理论43.测试调度S的可串行化优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的。调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须在Tj之前。某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边。如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度。1.3

分布式事务的可串行化调度测试1并发控制的概念和理论44.1.3

分布式事务的可串行化调度测试1并发控制的概念和理论S1的优先图S2的优先图S3的优先图XYXYXY存在环路45.考虑如下3个事务：

T1: