数据库管理系统数据库管理系统

数据库管理系统及其实现东南大学计算机科学与工程系徐立臻南京,2013.
32数据库管理系统及其实现,徐立臻CourseGoalanditsPreliminaryCoursesThePreliminaryCoursesare:DataStructureDatabasePrinciplesDatabaseDesignandApplicationThestudentsshouldalreadyhavethebasicconceptsaboutdatabasesystem,suchasdatamodel,dataschema,SQL,DBMS,transaction,databasedesign,etc.
NowwewillintroducetheimplementationtechniquesofDatabaseManagementSystems.
Thegoalistobuildthefoundationoffurtherresearchindatabasefieldandtousedatabasesystembetterthroughthestudyofthiscourse.
3数据库管理系统及其实现,徐立臻主要内容数据库管理系统(DBMS)的体系结构及其实现.
主要内容包括:DBMS体系结构、用户接口、语法分析、查询处理、目录管理、并发控制、恢复机制、物理存储管理等.
不管什么样的数据库系统,其DBMS一般都含有以上几个部分,只不过具体的实现方法及考虑问题的侧重点有所不同.
本课程的主要内容就是介绍DBMS核心所涉及的基本概念、基本原理及其实现方法.
4数据库管理系统及其实现,徐立臻课程重点由于关系模型是主流数据模型,而分布式数据库管理系统在并发控制、恢复等方面包容了集中式数据库管理系统的所有内容,所以本课程将以关系型分布式数据库管理系统为主线,介绍数据库管理系统中各部分的实现.
并适当补充一些其它类型数据库系统的内容.
5课程沿革数据库系统原理(~1984)—关系模型理论、一些查询优化算法.
分布式数据库系统(~1994)—全面、系统地介绍DDBMS的各项实现技术及算法.
数据库管理系统及其实现(1995~)—不限于DDBMS,更全面地介绍DBMS的实现技术,因为DDBMS只是数据库技术发展的一个分支.
将随着技术的发展不断调整、添加新的内容.
数据库管理系统及其实现,徐立臻6数据库管理系统及其实现,徐立臻主要参考书1)StefanoCeri,―DistributedDatabases‖2)王能斌,"数据库系统教程(上下册)",电子工业出版社,20083)RaghuRamakrishnan,JohannesGehrke,―DatabaseManagementSystems‖,3rdEdition,McGraw-HillCompanies,20024)HectorGarcia-Molina,Jeffrey.
D.
Ullman,―DatabaseSystems:theCompleteBook‖5)S.
BingYaoetal,―QueryOptimizationinDDBS‖6)Courseware:http://cse.
seu.
edu.
cn/people/lzxu/resource7数据库管理系统及其实现,徐立臻目录1.
概述数据库系统的发展、分类、及主要研究内容;分布式数据库系统2.
DBMS体系结构DBMS的组成及进程结构;分布式数据库系统的体系结构3.
数据库访问管理物理文件组织、索引及存取原语4.
数据分布数据的分割及分布、分布式数据库设计、联邦式数据库设计、并行数据库设计、数据目录及其分布8数据库管理系统及其实现,徐立臻目录5.
查询优化基本问题;查询优化技术;分布式数据库系统的查询处理;其它类型DBMS的查询处理6.
恢复机制基本问题;更新策略及恢复技术;分布式数据库系统的恢复机制7.
并发控制基本问题;并发控制技术;分布式数据库系统的并发控制;其它类型DBMS的并发控制1.
概述数据库管理系统及其实现,徐立臻10数据库管理系统及其实现,徐立臻1.
1数据库技术的发展历史及分类(1)从数据模型的发展来看无管理(60年代之前):科学计算文件系统:简单的数据管理数据管理需求不断增长,数据库管理系统应运而生.
1964,美通用电气公司开发出第一个DBMS:IDS,网状1969,IBM推出第一个商品化DBMS,层次1970,IBM研究员E.
F.
Codd提出关系模型其它数据模型:面向对象、演绎、XML等11数据库管理系统及其实现,徐立臻(2)从DBMS体系结构的发展来看集中式数据库系统并行数据库系统分布式数据库系统(含联邦式数据库系统)移动数据库系统(3)从基于数据库的应用系统的发展来看集中式结构:主机+哑终端分布式结构Client/Server结构三层/多层结构移动计算网格计算(数据网格)、云计算12数据库管理系统及其实现,徐立臻(4)从应用领域的拓展来看OLTP工程数据库演绎数据库多媒体数据库时态数据库空间数据库数据仓库、OLAP及数据挖掘等XML数据库大数据,NoSQL,NewSQL13数据库管理系统及其实现,徐立臻14数据库管理系统及其实现,徐立臻1.
2分布式数据库系统WhatisDDBADDBisacollectionofcorrelateddatawhicharespreadacrossanetworkandmanagedbyasoftwarecalledDDBMS.
两种:(1)物理上分布,逻辑上统一(一般的DDB)(2)物理上分布,逻辑上也分布(FDBS)本课程以第一种DDBS为主.
15数据库管理系统及其实现,徐立臻DistributionCorrelationDDBMSDDBS特征:16数据库管理系统及其实现,徐立臻DDBS优点:地方自治可用性好(由于支持多复本)灵活性好系统代价较低效率较高(大多数访问就地处理,减少通信)并行处理能力DDBS弱点:DB集成较难太复杂(系统本身及使用,如DDB设计)17数据库管理系统及其实现,徐立臻DDBS中的主要问题:与集中式DBMS相比,DDBS的不同主要体现在以下几个方面:查询处理(目标不同)并发控制(要考虑全局)恢复机制(要考虑复杂的故障组合)作为DDB,还多一个问题:数据分布2.
DBMS体系结构数据库管理系统及其实现,徐立臻19数据库管理系统及其实现,徐立臻主要内容DBMS核心组成DBMS进程结构DDBMS核心组成DDBMS进程结构20数据库管理系统及其实现,徐立臻2.
1DBMS核心的构成应用1操作系统磁盘语义分析和查询处理DDLQLDMLDCL权限检查词法及语法分析器应用i接口m应用j接口1并发控制恢复机制存取机制语句/程序存取原语系统调用数据库语言语句语法树I/O命令消息或数据格式化的消息/数据消息或数据消息或数据状态信息或物理块应用nufi/API.
.
.
21数据库管理系统及其实现,徐立臻2.
2DBMS进程结构单进程结构多进程结构多线程结构进程/线程间通信协议22数据库管理系统及其实现,徐立臻单进程结构应用程序与DBMS核心编译为一个EXE,单进程运行.
应用程序代码DBMS核心(函数)SQL语句运行结果23数据库管理系统及其实现,徐立臻多进程结构一个应用进程对应一个DBMS核心进程应用进程1DBMS核心进程1管道(pipe)SQL语句查询结果应用进程2DBMS核心进程2管道(pipe)SQL语句查询结果应用进程nDBMS核心进程n管道(pipe)SQL语句查询结果24数据库管理系统及其实现,徐立臻数据目录锁表缓冲DaemonDBMS进程多线程结构只有一个DBMS进程,每个应用进程对应一个DBMS核心线程应用进程1DBMS核心线程1pipe/socketSQL语句查询结果pipe/socket应用进程2DBMS核心线程2SQL语句查询结果pipe/socket应用进程nDBMS核心线程nSQL语句查询结果25数据库管理系统及其实现,徐立臻进程/线程间通信协议应用程序通过DBMS提供的API或嵌入式SQL访问数据库,根据通信协议进行同步控制:即席界面或应用程序DBMS核心Pipe0Pipe1StateTupNumAttNumAttNameAttTypeAttLenTmpFileName一个属性的定义其它属性的定义Pipe0:发送SQL语句、内部命令;Pipe1:返回结果.
结果格式:26数据库管理系统及其实现,徐立臻进程/线程间通信协议State:0—出错,1—插、删、改操作成功,2—查询成功,需进一步处理结果.
TupNum:结果中元组数.
AttNum:结果中属性个数.
AttName:属性名.
AttType:属性类型.
AttLen:属性长度.
TmpFileName:存放结果数据的临时文件名,其中的数据要用上述字典信息来解释.
27数据库管理系统及其实现,徐立臻2.
3DDBMS核心的构成DBDCDDDDBKLDB1DBDCDDDDBKLDB2Site1Site2DB:数据库管理DC:通信控制DD:数据字典管理DDBK:核心.
负责语法分析、分布事务管理、并发、恢复以及全局查询优化等.
28数据库管理系统及其实现,徐立臻全局查询优化例全局查询优化根据代价估算得出一个执行计划表.
比如:(1)将R2Site1,R'(2)在Site1上执行:Select*FromR1,R'WhereR1.
a=R'.
b;R1R2Site1Site2Select*FromR1,R2WhereR1.
a=R2.
b;29数据库管理系统及其实现,徐立臻2.
4DDBMS进程结构LDBMS进程局部库1LDBMS进程局部库2LDBMS进程局部库3Daemon结点1Daemon结点2Daemon结点3DDBMS核心线程应用进程2应用进程1SQL/结果SQL/结果SQL/结果SQL/结果SQL/结果SQL/结果SQL/结果SQL/结果DDBMS核心线程1DDBMS核心线程2DDBMS核心线程3.
数据库访问管理数据库管理系统及其实现,徐立臻31数据库管理系统及其实现,徐立臻主要内容对数据库的操作最终要落实到对文件的操作,文件结构及其所提供的存取路径直接影响数据访问的速度,一种文件结构不可能对所有数据访问都有效的.
访问类型文件组织索引技术存取原语32数据库管理系统及其实现,徐立臻访问类型查询文件的全部或相当多的记录(>15%)查询某一特定记录查询某些记录(数据库管理系统及其实现,徐立臻文件组织堆文件:按插入先后次序存放,顺序搜索,最基本、通用的文件组织形式直接文件:按某属性值散列映射成记录地址索引文件:索引+堆文件/簇集动态散列:p111栅格文件结构:p114(多属性查询)RawDisk(注意区别文件的逻辑块和物理块,利用RawDisk可直接控制物理块)34数据库管理系统及其实现,徐立臻索引技术B+树(√√)簇集索引(√)倒排文件动态散列栅格结构文件和分段散列位图索引(数据仓库)其它类型的索引35数据库管理系统及其实现,徐立臻位图索引-索引本身就是数据BinaryIndexforSales8bit4bit2bit1bit01101001010110111001001101111100forClassABC100100010100100010010100BinaryIndexforStateAKARCACOCTMANYRI……0000001000000100000000100000100000000010000000010000100000000010总销售量=(4*8+4*4+4*2+6*1=62)NY的A类店有多少(3)NY的A类店销售量=(2*8+2*4+1*2+1*1=27)CT有多少家店(2)处理连接(查NY的A类店销售产品清单)36数据库管理系统及其实现,徐立臻存取原语intdbopendb(char*dbname)功能:打开一个数据库.
intdbclosedb(unsigneddbid)功能:关闭一个数据库.
intdbTableInfo(unsignedrid,TableInfo*tinfo)功能:取得rid对应的表的信息.
intdbopen(char*tname,intmode,intflag)功能:以flag打开一个名为tname的表并为其分配rid.
intdbclose(unsignedrid)功能:关闭以rid为标识的表,释放rid.
intdbrename(oldname,newname)功能:重命名表.
37数据库管理系统及其实现,徐立臻存取原语intdbcreateattr(unsignedrid,sstree*attrlist)功能:在rid关系中创建一些属性.
intdbupdateattrbyidx(unsignedrid,intnth,sstreeattrinfo)功能:更新关系rid中第nth个属性说明.
intdbupdateattrbyname(unsignedrid,char*attrname,sstreeattrinfo)功能:更新关系rid中名为attrname的属性说明.
intdbinsert(unsignedrid,char*tuple,intlength,intflag)功能:将长为length的元组插入标识为rid的关系中.
38数据库管理系统及其实现,徐立臻存取原语intdbdelete(unsignedrid,longoffset,intflag)功能:删除rid对应的表中偏移为offset的元组.
intdbupdate(unsignedrid,longoffset,char*newtuple,intflag)功能:对偏移为offset的元组用newtuple更新.
intdbgetrecord(unsignedrid,intnth,char*buf)功能:取出rid表中的第n个元组放入buf中.
intdbopenidx(unsignedrid,indexattrstruct*attrarray,intflag)功能:打开表rid的索引文件并为其分配一个iid.
39数据库管理系统及其实现,徐立臻存取原语intdbcloseidx(unsignediid)功能:关闭标识为iid的索引.
intdbfetch(unsignedrid,char*buf,longoffset)功能:从表rid中取出标识为offset的元组到buf中.
intdbfetchtid(unsignediid,void*pvalue,long*offsetbuf,flag)功能:在标识为iid的索引文件中取出索引属性值与pvalue有flag关系的元组的标识(实际上是元组在文件中的偏移量)放入offsetbuf中.
intdbpack(unsignedrid)功能:对关系进行压缩,对有删除标志的记录进行物理删除并重整文件.
4数据分布数据库管理系统及其实现,徐立臻41数据库管理系统及其实现,徐立臻4.
1数据分布策略(1)Centralized:即分布式系统,但数据还是集中存放的.
最简单,但无DDB优点.
(2)Partitioned:数据是分布的,但数据间不能重复(无复本).
(3)Replicated:AcompletecopyofDBateachnode.
Goodforretrieval-intensivesystem.
(4)Hybrid(前几种混合):AnarbitraryfractionofDBatvariousnodes.
最灵活、最复杂的分布方法.
42数据库管理系统及其实现,徐立臻四种分布方式比较1234flexibilitycomplexityAdvantageofDDBSProblemswithDDBS43数据库管理系统及其实现,徐立臻4.
2数据分布的单位(1)以关系(或文件)为单位(即不划分)(2)以裂片(fragments)为单位水平分割(Horizontalfragmentation):tuplepartition垂直分割(Verticalfragmentation):attributepartition混合分割(Mixedfragmentation):both44数据库管理系统及其实现,徐立臻分割准则:(1)Completeness:每个元组或属性都要在fragmentation中有它的映象.
(2)Reconstruction:要能由fragments→globalrelation.
(3)Disjointness:对水平分割而言.
45数据库管理系统及其实现,徐立臻(1)HorizontalFragmentation由带谓词的选择操作来定义,用并操作重构.
分割方法Rn个裂片(用P1,P2,…,Pn)满足:PiPj=false(i≠j)P1P2…Pn=trueSELECT*FROMRWHEREP;DerivedFragmentation:不是据本关系属性的特征来划分,而是据另一关系的划分来做.
46数据库管理系统及其实现,徐立臻导出分割例子TEACHER(TNAME,DEPT)COURSE(CNAME,TNAME)设TEACHER已按DEPT水平分割,COURSE中无DEPT属性,但可按TNAME所在系对课程按系划分,此即由TEACHER导出的分割.
Semijoin:RS=R(RS)TEACHER9=SELECT*FROMTEACHERWHEREDEPT=9th';COURSE9=COURSETEACHER947数据库管理系统及其实现,徐立臻(2)VerticalFragmentation由投影操作定义,用连接操作重构.
注意:Completeness:每个属性至少在某个裂片中出现.
Reconstruction:分割时要满足无损连接条件.
a.
在每个裂片中都包含一个原关系的主键.
b.
在每个裂片中都包含一个系统产生的元组标识符(TID).
48数据库管理系统及其实现,徐立臻(3)MixedFragmentationApplyfragmentationoperationsrecursively.
Canbeshowedwithafragmentationtree:RR13R2R1R12R11GlobalrelationFragmentsVH49数据库管理系统及其实现,徐立臻4.
3不同级别的透明性采用informationhiding的方法简化复杂问题Level1:FragmentationTransparency用户只看到globalrelation,而不知它是如何划分的,当然也就不需要了解这些裂片的分布情况了,在这种情况下,用户感觉不到数据的分布,就好像他在使用一个集中式数据库一样.
50数据库管理系统及其实现,徐立臻Level2:LocationTransparency用户要了解关系被分成多少fragments,但不需知道它们的存放位置.
Level3:LocalMappingTransparency用户需了解fragments及其存放位置,但各结点上的局部库使用何种DBMS、何种DML,用户不需了解.
Level4:NoTransparency51数据库管理系统及其实现,徐立臻4.
4数据分布带来的问题1)Multicopyconsistency2)Distributionconsistency主要是由于更新操作引起的元组存放位置的改变.
解决:(1)RedistributionAfterUpdate:Select-Move-Insert-Delete(2)Piggybacking更新后立即检查,如不符随响应信息返回.
52数据库管理系统及其实现,徐立臻3)TranslationofGlobalQueriestoFragmentQueriesandSelectionofPhysicalCopies.
4)DesignofDatabaseFragmentsandAllocationofFragments.
上述1)~3)应由DDBMS解决;而4)是分布式数据库设计的问题.
53数据库管理系统及其实现,徐立臻4.
5分布式数据库设计1)分布式数据库数据分割的设计裂片分布方案的设计根据需求,对每个应用,提出基本问题:该应用的发生结点该应用发生的频度要访问的数据对象54数据库管理系统及其实现,徐立臻集中式数据库设计流程图需求分析概念设计逻辑设计物理设计信息需求处理需求需求说明DBMS特性硬件、操作系统特性与DBMS无关的数据模式外模式、概念模式内模式A55数据库管理系统及其实现,徐立臻分布式数据库设计流程图A数据分割方案设计数据分布方案设计各结点上物理设计信息需求处理需求外模式、概念模式DDBMS特性各结点各自的硬件、操作系统特性数据分布单位各结点上的局部子模式内模式B56数据库管理系统及其实现,徐立臻(1)数据分割的设计DDB中,裂片并非分得越细越好,完全根据应用的需要.
例如下面两个应用:应用1:SELECTGRADEFROMSTUDENTWHEREDEPT=cANDAGE>20;应用2:SELECTAVG(GRADE)FROMSTUDENTWHERESEX=Male';是否应将STUDENT按系作水平分割57数据库管理系统及其实现,徐立臻一般的规则:①选择一些重要的、经常发生的典型应用.
②分析这些应用的访问局部性.
对水平分割:③用合适的谓词将全局关系划分成裂片以适应不同结点上的局部需求.
如有矛盾,以更重要的应用的需求为准.
④分析应用的连接操作以决定是否需要作导出分割.
58数据库管理系统及其实现,徐立臻对垂直分割:③分析属性亲密度.
结合考虑:节省空间和I/O代价安全性.
某些属性不让某些用户看到.
(2)数据分布方案的设计通过代价估算以决定各分布单位的合适的存放位置(结点).
王书p252.
59数据库管理系统及其实现,徐立臻2)并行数据库什么是并行数据库系统无共享(SN)结构垂直并行和水平并行查询操作可分解为若干执行步骤,这些步骤间的并行执行就是垂直并行.
对扫描类子任务,如被扫描关系事先分割成若干裂片存放在SN结构并行机的不同硬盘上,则可以按并行扫描的方式进行.
这就是水平并行.
60数据库管理系统及其实现,徐立臻例子:SELECT*FROMR,SWHERER.
a=S.
aANDR.
b>20ANDS.
c20(R)S'=σc数据库管理系统及其实现,徐立臻并行数据库设计流程图A数据分割设计数据在并行机各处理器上的分布设计各处理器上的物理设计信息需求处理需求外模式、概念模式PDBMS特性及所用并行机系统的特性数据分布单位各处理器上的局部子模式内模式C62数据库管理系统及其实现,徐立臻PDB中数据分割方式(1)任意方式将某关系R以任意方式分割成裂片,分别存放在不同的处理器上.
比如可以将R等分成几段、以hash方式散列成n段等.
(2)基于表达式方式将满足某一条件的元组指定存储于某个裂片内,适合于对该关系的查询大多基于分片条件的情况——分块排除.
可以与方式1配合使用.
63数据库管理系统及其实现,徐立臻PDB与DDB关于数据的分割与分布的区别PDBDDB分割与分布的目的提高处理的并行性,充分利用并行机的并行处理能力提高访问的局部性,减少网上数据传输量分割依据所用并行机系统及PDBMS的特性,结合用户处理需求用户的处理需求,结合所用DDBMS的特性分布方式在一台并行机的多个处理器上分布在网络的多个结点上分布64数据库管理系统及其实现,徐立臻带PDB的DDB系统设计流程BC普通DDB中的局部物理设计结点i是否为并行机系统内模式YN65数据库管理系统及其实现,徐立臻3)联邦式数据库应用中需要解决已有的、分布的、异构的多数据库的集成.
各成员自治并相互协商合作的数据库系统——联邦式数据库.
无全局模式,联邦成员保持各自的数据模式.
成员之间通过协商确定输入/输出模式从而建立彼此的数据共享关系.
66数据库管理系统及其实现,徐立臻联邦式数据库的模式结构FS1FS3FS2IS3IS2IS1ES3ES2ES1CS3CS2CS1DB1DB2DB3结点1结点3结点267数据库管理系统及其实现,徐立臻FSi=CSi+ISiFSi是结点i上的用户所看到的所有可用数据.
ISi通过与其它结点的ESj协商而得(ji).
用户对FSi的查询对CSi和ISi的查询对相应ESj的查询.
对ESj的查询结果对应ISi的结果,ISi的结果和CSi的结果最后综合成FSi的结果.
68数据库管理系统及其实现,徐立臻4.
6数据目录的分布Catalog——Dataaboutdata.
主要用于将用户需求转换成系统内的物理目标.
4.
6.
1ContentsofCatalogs(1)对象的类型(如关系、视图…)及其模式(2)分布信息(如fragmentlocation)(3)存取路径(4)授权信息(5)用于决定优化的存取计划的一些统计信息69数据库管理系统及其实现,徐立臻(1)~(4)不常变化,而(5)每次更新操作时就会变化.
对此:定期成批更新每次Update之后更新4.
6.
2目录的特征(1)主要是读操作(2)对系统的效率及数据分布的透明性很重要(3)对结点自治很重要(4)某些一致性要求不像数据那么严格(5)目录的分布由DDBMS的体系结构决定70数据库管理系统及其实现,徐立臻4.
6.
3目录的分布策略(1)集中式Acompletecatalogstoredatonesite.
Extendedcentralizedcatalog:开始时集中于一点;用完留下.
更新时通知.
(2)全复制目录:Catalogsarereplicatedateachsite.
Simpleinretrieval.
Complexinupdate.
Poorinautonomy.
(3)局部目录:Catalogsforlocaldataarestoredateachsite.
即目录随数据存放.
71数据库管理系统及其实现,徐立臻如要查其它结点的数据:(广播找人)MasterCatalog:在某结点上存放一个全部目录,使每个目录项都有两个复本.
Cache:取得其它结点目录信息后,用完留下.
通过比较版本号更新Cache的目录RR'scatalog(VerNo.
)CacheofR'scatalog(VerNo.
)72数据库管理系统及其实现,徐立臻(4)DifferentCombinationoftheabove对目录中的不同内容,采用上述的不同目录分布方法,从而得到不同的组合.
如:a.
对分布信息(2)采用全复制,其它内容局部存放.
b.
对统计信息采用局部存放,其它部分全复制.
73数据库管理系统及其实现,徐立臻4.
6.
4R*的目录管理——结点自治特点:无全局模式的概念(指目录)独立的命名和数据定义平稳地实现数据增长最重要的概念——系统范围名(SWN)::=User@UserSite.
ObjectName@BirthSiteObjectName:用户为相应对象起的名字User:用户名.
它可使不同用户用相同的名字访问不同的数据.
74数据库管理系统及其实现,徐立臻UserSite:用户所在结点.
它可使不同结点上的不同用户使用相同的用户名.
BirthSite:该数据的产生结点.
R*目录无全局模式:Atthebirthsitetheinformationaboutthedataisalwayskepteventhedataismigratedtoothersite.
打印名:用户在各种语句中所用的数据对象名.
::=[User[@UserSite].
]ObjectName[@birthSite]75数据库管理系统及其实现,徐立臻NameResolution—MappingPNtoSWN为每个用户建立一张同义词表(用DefineSynonym语句).
ObjectNameSWN变换时可能有以下几种情况:1)PrintName=SWN,不需转换2)只有ObjectName:查当前结点上的当前用户的同义词表3)User.
ObjectName:查当前结点上User用户的同义词表4)User@UserSite.
ObjectName76数据库管理系统及其实现,徐立臻5)ObjectName@BirthSiteIfnomatchfortheObjectNameisfoundin(2),(3)orprintnameisintheformof(4)or(5),namecompletionisused:补缺规则:AmissingUserisreplacedbycurrentUser.
AmissingUserSiteorBirthSiteisreplacedbycurrentsiteID.
5查询处理数据库管理系统及其实现,徐立臻78数据库管理系统及其实现,徐立臻简介首先对用户所写的程序(查询)进行"改写",然后确定最有效的具体操作方法和步骤,获得查询结果.
目标是以最小的代价、最快的速度得出用户查询的结果.
795.
1DDBMS查询处理概述全局查询(GlobalQuery):用户所写的针对全局关系的查询裂片查询(FragmentQuery):系统处理后转换的针对裂片的查询数据库管理系统及其实现,徐立臻80数据库管理系统及其实现,徐立臻总流程GlobalQuery转化成fragmentqueries1)对queriestree进行变换(以便执行更有效)2)查询分解(分解成若干可局部处理的子查询)3)决定操作执行的顺序和地点按执行计划中的调度执行各操作查询结果Querytree查询处理计划全局查询优化局部查询优化代数优化操作优化81数据库管理系统及其实现,徐立臻例子:S(SNUM,SNAME,CITY)SP(SNUM,PNUM,QUAN)P(PNUM,PNAME,WEIGHT,SIZE)设分割情况如下:S1=σCITY=Nanjing'(S)S2=σCITY=Shanghai'(S)SP1=SPS1SP2=SPS282数据库管理系统及其实现,徐立臻GlobalQuery:SELECTSNAMEFROMS,SP,PWHERES.
SNUM=SP.
SNUMANDSP.
PNUM=P.
PNUMANDS.
CITY=Nanjing'ANDP.
PNAME=Bolt'ANDSP.
QUAN>1000;83数据库管理系统及其实现,徐立臻QuerytreeS1S2(S.
SNAME)σ1CITY=Nanjing'σ2QUAN>1000σ3P.
PNAME=Bolt'PSP.
PNUM=P.
PNUMS.
SNUM=SP.
SNUMSSPSP1SP284数据库管理系统及其实现,徐立臻经过等价变换:S1S2(S.
SNAME)σ3PSP.
PNUM=P.
PNUMS.
SNUM=SP.
SNUMSP1SP231122σ2σ2σ1σ11=(S.
SNUM,S.
SNAME)2=(SP.
SNUM,SP.
PNUE)3=(P.
PNUM)S1'S2'SP1'SP2'P'85数据库管理系统及其实现,徐立臻变换结果:S1'S2'(S.
SNAME)P'SP.
PNUM=P.
PNUMS.
SNUM=SP.
SNUMSP1'SP2'86数据库管理系统及其实现,徐立臻子树部分的操作优化:先看分布JN:(1)(S1'US2')JN(SP1'USP2')(2)DistributedJoin再考虑SiteSelection,产生很多组合每个Join本身,也有很多实现方法:SRSitejSiteiRSitej,RSSSitei,SRJN属性(S)Sitei,SRSitej,(SR)R查询优化就是要从这些可能的方案中找出较好的.
复杂.
87数据库管理系统及其实现,徐立臻5.
2查询的等价变换即代数优化.
对原查询进行一系列的变换,将其转换成便于执行的最佳形式.
但变换必须等价.
例NAME,DEPTDEPT=15(EMP)≡DEPT=15NAME,DEPT(EMP)(1)查询树例SNUMAREA=NORTH'(SUPPLYDEPTNUMDEPT)(SNUM)σAREA=North'DEPTDEPTNUM=DEPTNUMSupply树叶:GlobalRelation中间结点:一元/二元操作叶根:操作的执行顺序88数据库管理系统及其实现,徐立臻(2)关系代数的等价变换规则1)/*的交换律:E1*E2≡E2*E12)/*的结合律:E1*(E2*E3)≡(E1*E2)*E33)的串接律:A1…An(B1…Bm(E))≡A1…An(E)A1…An为{B1…Bm}的子集时才合法.
4)的串接律:F1(F2(E))≡F1∧F2(E)5)与的交换律:F(A1…An(E))≡A1…An(F(E))如F中也包括不属于A1…An的属性B1…Bm,则A1…An(F(E))≡A1…AnF(A1…An,B1…Bm(E))6)如F中出现的属性全是E1中的属性,则F(E1*E2)≡F(E1)*E289数据库管理系统及其实现,徐立臻如F有形式F1∧F2,且F1中只出现E1的属性,F2只出现E2的属性,则F(E1*E2)≡F1(E1)*F2(E2)如F有形式F1∧F2,且F1中只含E1的属性,而F2含E1和E2两者的属性,则F(E1*E2)≡F2(F1(E1)*E2)7)F(E1E2)≡F(E1)F(E2)8)F(E1-E2)≡F(E1)-F(E2)9)设A1…An为一列属性,其中的B1…Bm是E1的属性,C1…Ck为E2的属性,则90数据库管理系统及其实现,徐立臻A1…An(E1*E2)≡B1…Bm(E1)*C1…Ck(E2)10)A1…An(E1E2)≡A1…An(E1)A1…An(E2)可见,代数优化的目的在于简化查询的执行,目标是尽量减少参与2元操作的操作数的规模.
(SNUM)(DEPTNUM)DEPTNUM=DEPTNUM(SNUM,DEPTNUM)SupplyDEPTσAREA=North'(3)代数优化的一般过程见王书p11891数据库管理系统及其实现,徐立臻5.
3将GlobalQueries转换成FragmentQueries方法:对水平分割:R=R1R2…Rn对垂直分割:S=S1S2…Sn将上式带入替换GlobalRelation即可.
带入后的正则表达式需用前述规则变换,原则:1)将一元操作尽可能向下压.
2)寻找并合并公共子表达式(CommonSub-expression)定义:在查询表达式中不止出现一次的表达式.
如找出这种子表达式,对其只计算一次,无疑会提高效率.
92数据库管理系统及其实现,徐立臻一般方法:(1)合并操作树上的相同叶结点.
(2)合并相对于带相同操作数的相同操作的中间结点.
例:emp.
name(emp(mgrnum=373dept)–(sal>35000emp)(mgrnum=373dept))emp.
namedeptnum=deptnumdept-σmgrnum=373empdeptσmgrnum=373σsal>35000emp①合并②合并④上移⑤合并③合并93数据库管理系统及其实现,徐立臻emp.
namedeptnum-deptσmgrnum=373σsal>35000emp公共子表达式:emp(mgrnum=373dept)性质:RR≡RRR≡RR-R≡ΦRF(R)≡F(R)RF(R)≡RR-F(R)≡notFRF1(R)F2(R)≡F1∧F2(R)F1(R)F2(R)≡F1∨F2(R)F1(R)-F2(R)≡F1∧notF2(R)94数据库管理系统及其实现,徐立臻emp.
namedeptnumdeptσmgrnum=373σsal数据库管理系统及其实现,徐立臻3)确定并消除空的子表达式dept2deptnum20dept1σdeptnum=14)消除无用的垂直分割AR2σFR1IfAAttr(F)Attr(R1)AσFR196数据库管理系统及其实现,徐立臻5.
4将查询分解成子查询考虑到结点的情况,将查询分解成可局部处理的若干子查询:R1R2R6R3R42143σ4σ3σ2σ1R56σ65σ5设:Rij—存放在结点j上的裂片Ri11112397数据库管理系统及其实现,徐立臻分解方法:对查询树进行后序遍历,直到发现j为2时,暂停,得到第1棵子树,依此类推,得到所有子树.
R41R11R21R312143σ4σ3σ2σ1R1R55σ5R2R66σ6R3R1R2R3Site1Site3Site2总装树98数据库管理系统及其实现,徐立臻5.
5二元操作执行的优化上述局部子查询的执行由相应结点的局部DBMS负责,DDBMS的查询优化负责解决Globaloptimization问题,即总装树的执行.
由于一元操作经代数优化、查询分解后全部交由局部DBMS负责,所DDBMS的全局查询优化只需考虑二元操作,主要是Join操作.
本节介绍的就是如何根据具体环境,找到一个"好"的存取策略来计算出经代数优化"改良"过的查询.
99数据库管理系统及其实现,徐立臻一.
全局查询优化中的主要问题1)决定查询所涉及的fragments的复本,即复本选择(或Siteselection)2)StrategiesforjoinoperationNon_distributedjoin:(R2R3)R1Distributedjoin:(R1R2)(R1R3)DirectjoinUseofsemi_join3)选择每个操作的执行方法(主要对directjoin而言)100数据库管理系统及其实现,徐立臻Nestedloop:实际相当于二重循环,对外循环关系的每个元组,将内循环关系扫描一遍.
关系不是以元组为单位,而是以物理块为单位从磁盘取到内存的.
所以为提高效率,对于RS,如果以R为外关系,S为内关系,bR为R的物理块数,bS为S的物理块数,系统提供nB个缓冲区(nB>=2),其中nB-1个块为外关系的缓冲区,1个块为内关系的缓冲区,则总的访盘次数为:bR+bR/(nB-1)*bS101数据库管理系统及其实现,徐立臻Mergescan:将R、S事先按连接属性排序,则可按序比较两者的元组,各扫描一遍即可.
如R、S事先未按连接属性排序,则需仔细权衡是否用此方法.
(参王书p122)利用索引或散列寻找匹配元组法:在嵌套循环法中,如内关系有合适的存取路径,则可考虑使用这些存取路径取代顺序扫描,特别当连接属性上有簇集索引或散列时,最为有利.
散列连接法:R、S连接属性有相同的域,用同一散列函数将R、S散列到同一散列文件中.
102数据库管理系统及其实现,徐立臻上述均为集中式关系DBMS中的经典算法,在DDBMS中用directjoin实现连接时,思路类似.
二.
优化方法一般有三种:1)Bycostcomparison(也称exhaustivesearch)2)Byheuristicrule.
小系统用的较多.
例王书p124连接方法的启发式规则.
3)Combinationof1,2:基本同1,但可先用2去掉明显不合适的方案,减小解空间.
三.
CostestimationTotalquerycost=Processingcost+Transmissioncost103数据库管理系统及其实现,徐立臻根据环境不同:Forwideareanetwork:传输率100bps~50Kbps,比机内处理速度低得多,所以Processingcost通常忽略不计.
Forlocalareanetwork:传输率可达1000Mbps,这时两项都必须考虑.
1)TransmissioncostTC(x)=C0+C1xx:传输数据量;C0:初始化代价;C1:网上传送1个数据的代价.
C0、C1依赖于网络特性.
104数据库管理系统及其实现,徐立臻2)ProcessingcostProcessingcost=costcpu+costI/O一般costcpu可以忽略.
costofoneI/O=D0+D1D0平均寻道时间(ms);D1:I/O一个数据(s)costI/O=no.
ofI/O*D0注意:精确计算querycost是不必要也是不现实的,我们的目的是在不同查询执行策略之间进行比较,所以只需在相同运行环境下对不同方案的执行代价进行估算.
105数据库管理系统及其实现,徐立臻5.
6用semi_join实现join操作一.
semi_join的作用Semi_joinisusedtoreducetransmissioncost.
SoitissuitableforWANonly.
RS=R(RS)如果R、S分别存放在结点1、2,用实现RS的步骤:1)将A(S)结点1,A是连接属性2)在结点1上做RA(S)=RS(压缩R)3)将RS结点24)在结点2上做(RS)S=RS106数据库管理系统及其实现,徐立臻代价比较Costofdirectjoin=C0+C1min(r,s)——①r,s——|R|,|S|(关系的大小)Costofjoinviasemi_join=min(2C0+C1s'+C1r‖,2C0+C1r'+C1s‖)=2C0+C1min(s'+r‖,r'+s‖)——②s',r'——|A(S)|,|A(R)|s‖,r‖——|SSJR|,|RSJS|仅当②数据库管理系统及其实现,徐立臻二.
关于semi_join的评论1)采用SJ对传输代价的减少是以牺牲处理代价为代价的.
2)Semi_join的可选方案很多如查询R1R2R3…Rn,对R1做:R1R2,R1(R2R1),R1(R2R3)…要从所有可能方案中选出最好的几乎不可能.
3)Bernsteincanberegardedasreducers.
Def:Achainofsemi_jointoreduceRiscalledreducerprogramforR.
108数据库管理系统及其实现,徐立臻RED(Q,R):AsetofallreducerprogramsforRinqueryQ.
Fullreducer:满足下列条件的reducer:(1)RED(Q,R)(2)reduceRmostly但fullreducer并不是优化应该追求的目标例1:Qisaquerywithqualification:q=(R1.
A=R2.
B)∧(R1.
C=R3.
D)∧(R2.
E=R4.
F)∧(R3.
G=R5.
H)∧(R3.
J=R6.
K)109数据库管理系统及其实现,徐立臻Querygraph:两关系间有关系就用一条线连接,便可得Querygraph.
左图这种查询称为treequery(TQ).
R1R2R3R5R6R4例2:q=(R1.
A=R2.
B)∧(R2.
C=R3.
D)∧(R3.
E=R1.
F)R1R2R3左图这种查询称为cyclicquery(CQ).
例3:q=(R1.
A=R2.
B)∧(R2.
B=R3.
C)∧(R3.
C=R1.
A)这是一个TQ而不是CQ,因为R3.
C=R1.
A可由传递得到.
110数据库管理系统及其实现,徐立臻可以证明:1)FullreducerexistsforTQ.
2)NofullreducerexistsforCQinmanycases.
R1AB0134R2CD1245R3EF2350q=(R1.
B=R2.
C)∧(R2.
D=R3.
E)∧(R3.
F=R1.
A)查询结果为空,但R1、R2、R3都无法通过SJ减小,所以不存在fullreducer.
111数据库管理系统及其实现,徐立臻q=(R.
B=S.
B)∧(S.
C=T.
C)∧(T.
A=R.
A)查询结果RAB1a2b3cSBCaxbyczTCAx2y3z4R'=RT=AB2b3cS'=SR'=BCbyczT'=TS'=CAy3z4R‖=R'T'=AB3cS‖=S'R‖=T‖=T'S‖=BCczCAz4112数据库管理系统及其实现,徐立臻R‖'=R‖T‖=Φ,所以R的fullreducer:①R'=RT②S'=SR'③T'=TS'④R‖=R'T'⑤S‖=S'R‖⑥T‖=T'S‖⑦R‖'=R‖T‖=Φ结论:对CQ:一般没有fullreducer,即使有,其长度随查询中某关系的元组数线性增长(3(m-1)).
对TQ:fullreducer的长度V——顶点的集合,包含所有参与调度的事务.
E——边的集合,通过分析冲突操作来决定.
如果下列条件之一成立,可在E中加边Ti→Tj:Ri(x)在Wj(x)之前Wi(x)在Rj(x)之前Wi(x)在Wj(x)之前最后,看构造好的前趋图中是否有环路,如果有,则该调度不可串行化;否则,可串行化.
157数据库管理系统及其实现,徐立臻可串行化时,决定等价串行调度序列的算法:1)由于无环路,必有入度为0的顶点.
将它们及其有关的边从图中移去并将这些顶点存入一个队列.
2)对剩下的图作同样处理,不过移出的顶点要队列中已有顶点之后.
3)重复1,2直至所有顶点移入队列为止.
例对{T1,T2,T3,T4}的一个调度sS=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)它是否可串行化如可串行化找出其等价的串行执行序列.
158数据库管理系统及其实现,徐立臻S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)并发控制的任务就是对并发执行的事务加以控制,使之按某种可串行化的调度序列来执行.
T1T2T3T4T2T3T4队列:T1T2T4队列:T1,T3T4队列:T1,T3,T2等价串行序列:T1→T3→T2→T4空159数据库管理系统及其实现,徐立臻7.
2LockProtocol封锁法是最基本的并发控制方法之一,它可以有多种实现方式.
7.
2.
1XlocksOnlyonetypeoflock,forbothreadandwrite.
相容矩阵:NL-nolockX-XlockY-相容N-不相容待加已有NLXNLYYXYNX_lockRUpdateRX_unlockREOTTAX_lockRwaitX_lockRReadRTB160数据库管理系统及其实现,徐立臻*TwoPhaseLockingDef1:Inatransaction,ifalllocksprecedeallunlocks,thenthetransactioniscalledtwophasetransaction.
Thisrestrictioniscalledtwophaselockingprotocol.
Def2:Inatransaction,ifitfirstacquiresalockontheobjectbeforeoperatingonit,itiscalledwell-formed.
T1LockALockBLockCUnlockAUnlockBUnlockCT2LockALockBUnlockAUnlockBLockCUnlockC2PLnot2PLGrowingphaseShrinkingphaseTheorem:IfSisanyscheduleofwell-formedand2PLtransactions,thenSisserializable.
(王书p151证明)161数据库管理系统及其实现,徐立臻结论:1)Well-formed+2PL:serializable2)Well-formed+2PL+unlockupdateatEOT:serializableandrecoverable.
(不会有多米诺现象)3)Well-formed+2PL+holdingalllockstoEOT:stricttwophaselockingtransaction.
7.
2.
2(S,X)locksSlock——ifreadaccessisintended.
Xlock——ifupdateaccessisintended.
待加已有NLSXNLYYYSYYNXYNN162数据库管理系统及其实现,徐立臻7.
2.
3(S,U,X)locksUlock——updatelock.
ForanupdateaccessthetransactionfirstacquiresaU-lockandthenpromoteittoX-lock.
目的:减少排他时间,提高并发度,减少死锁.
待加已有NLSUXNLYYYYSYYYNUYYNNXYNNNX(S,X)(S,U,X)concurrencyoverhead163数据库管理系统及其实现,徐立臻7.
3DeadLock&LiveLock死锁:循环等待,谁也无法得到全部资源.
活锁:虽然其它事务都在有限长的时间内释放了资源,但某事务就是无法得到想要的资源.
X_lockR1X_lockR2waitTAX_lockR2X_lockR1waitTBRT1:S-lockT2:S-lockT:x-lock活锁较简单,只需稍加修改调度策略,如FIFO死锁:(1)防(不允许发生);(2)治(允许,能消除)164数据库管理系统及其实现,徐立臻7.
3.
1DeadlockDetection1)Timeout:Ifatransactionwaitsforsomespecifiedtimethendeadlockisassumedandthetransactionshouldbeaborted.
2)Detectdeadlockbywait-forgraphG=V—setoftransactions{Ti|TiisatransactioninDBS(i=1,2,…n)}E-{|TiwaitsforTj(i≠j)}若图中有环路则说明已经发生死锁.
Whentodetect1)wheneveronetransactionwaits.
2)periodically165数据库管理系统及其实现,徐立臻Whattodowhendetected1)Pickavictim(youngest、minimumabortcost…)2)Abortthevictimandreleaseitslocksandresources3)Grantawaiter4)restartthevictim(automaticallyormanually)7.
3.
2Deadlockavoidance1)Requestingalllocksatinitialtimeoftransaction.
2)Requestinglocksinaspecifiedorderofresource.
3)Abortonceconflicted.
4)TransactionRetry166数据库管理系统及其实现,徐立臻Everytransactionisuniquelytimestamped.
IfTArequiresalockonadataobjectthatisalreadylockedbyTB,oneofthefollowingmethodsisused:a)Wait-die:TAwaitsifitisolderthanTB,otherwiseit―dies‖,i.
e.
itisabortedandautomaticallyretriedwithoriginaltimestamp.
b)Wound-wait:TAwaitsifitisyoungerthanTB,otherwiseit―wound‖TB,i.
e.
TBisabortedandautomaticallyretriedwithoriginaltimestamp.
上述方法中,都只有一个方向的等待,年老→年轻或年轻→年老,所以不会出现循环等待,从而避免了死锁的发生.
167数据库管理系统及其实现,徐立臻7.
4LockGranularities7.
4.
1多级封锁从减少lock开销来讲,封锁单位越大越好;从提高事务运行并发度来讲,粒度越小越好.
所以大数据库中封锁单位分几级:DB-File-Record-FieldInthissituation,ifatransactionacquiresalockonanodethenitacquiresimplicitlythesamelockoneachdescendantofthatnode.
所以多级封锁有两种锁法:ExplicitlockImplicitlock168数据库管理系统及其实现,徐立臻7.
4.
2意向锁如何检查implicitlocksIBM的intentionlock:提供IS、IX和SIX三种意向锁.
例如低级某对象加了S锁,则在它所属的高级各对象上加IS锁,作为警告信息.
这样在高级某对象上要加X锁时,就可以发现隐含的冲突.
IS-IntentionsharelockIX-IntentionexclusivelockSIX-S+IXDBFileRecordFieldSISIS169数据库管理系统及其实现,徐立臻多级封锁时的相容矩阵:待加已有NLISIXSSIXXNLYYYYYYISYYYYYNIXYYYNNNSYYNYNNSIXYYNNNNXYNNNNNXSIXIXSISNL强弱排他性加锁时可以以强(排他性)代弱,但不能以弱代强.
170数据库管理系统及其实现,徐立臻加锁原则:Locksarerequestedfromroottoleavesandreleasedfromleavestoroot.
recordfileDB(1)SISIS(2)XIXIX(3)AllreadandsomewriteSIXIX,IS加锁顺序对要写的record加X锁以强代弱DBFileRecordField例:171数据库管理系统及其实现,徐立臻7.
5LockingonIndex(B+Tree)TransactionsaccessconcurrentlynotonlythedatainDB,butalsotheindexesonthesedata,andapplyoperationsonindexes,suchassearch,insert,delete,etc.
Soindexesalsoneedconcurrencycontrolwhilemultigranularitylockingissupported.
HowcanweefficientlylockaparticularleafnodeBtw,don'tconfusethiswithmultiplegranularitylocking!
Onesolution:Ignorethetreestructure,justlockpageswhiletraversingthetree,following2PL.
Thishasterribleperformance!
Rootnode(andmanyhigherlevelnodes)becomebottlenecksbecauseeverytreeaccessbeginsattheroot.
172数据库管理系统及其实现,徐立臻SomeUsefulObservationsEveryaccesstoB+treeneedatraversefromroottosomeleaf.
Onlyleaveshavedetailinformationaboutdata,suchasTID,whilehigherlevelsofthetreeonlydirectsearchesforleafpages.
Onenodeoccupiesonepagegenerally,sothelockunitofB+treeispage.
Don'tneedmultigranularitylocks,onlyS,Xlockonpagelevelareenough.
B+treeiskeyresourceaccessedfrequently,liabletobethebottleneckofsystem.
Performanceisveryimportantinindexconcurrencycontrol.
Ifoccurconflictwhiletraversethetree,discardalllocksapplied,andsearchfromrootagainaftersomedelay.
Avoiddeadlockresultedbywait.
173数据库管理系统及其实现,徐立臻SomeUsefulObservationsOriginally,locksonindexareonlyusedtokeeptheconsistencyofindexitself.
Thecorrectnessofconcurrenttransactionsisresponsibleby2PL.
Fromthissense,thelocksonindexdon'tneedkeepingtoEOT,theycanreleaseimmediatelyafterfinishthemappingfromattributevaluetotuples'addresses.
Butin7.
6wewillknow,eventhestrict2PLhasleakwhilemultigranularitylocksarepermitted.
ThelockonleafofB+treeshouldbekepttoEOTinordertomakeuptheleakofstrict2PLinthissituation,whilelocksonothernodesofthetreecanbereleasedafterfinishingofsearch.
174数据库管理系统及其实现,徐立臻ExampleROOTABCDEFGHI203520*384422*23*24*35*36*38*41*44*23Traversingthetree175数据库管理系统及其实现,徐立臻TreeLockingAlgorithm1.
Whiletraversing,applySlockonrootfirst,thenapplySlockonthechildnodeselected.
OncegetSlockonthechild,theSlockonparentcanbereleased,becausetraversingcan'tgoback.
Searchlikethisuntilarriveleafnode.
Aftertraversing,onlySlockonwantedleafisleft.
KeepthisSlocktillEOT.
2.
Whileinsertingnewindexitem,traversefirst,findtheleafnodewherethenewitemshouldbeinsertedin.
ApplyXlockonthisleafnode.
Ifitisnotfull,insertdirectly.
Ifitisfull,splitnodeaccordingtotheruleofB+tree.
Whilesplitting,besidestheoriginalleaf,thenewleafandtheirparentshouldaddXlock.
Ifparentisalsofull,thesplittingwillcontinue.
Ineverysplitting,mustapplyXlockoneachnodetobechanged.
TheseXlockscanbereleasedwhenthechangesarefinished.
Aftertheallinsertingprocessiscompleted,theXlockonleafnodeischangedtoSlockandkepttoEOT.
176数据库管理系统及其实现,徐立臻TreeLockingAlgorithm3.
Whiledeletinganindexitemfromthetree,theprocedureissimilarasinserting.
DeletingmaycausethecombinationofnodesinB+tree.
ThenodechangedmustbeXlockedfirstandXlockreleasedafterfinishingchange.
TheXlockonleafnodeisalsochangedtoSlockandkepttoEOT.
177数据库管理系统及其实现,徐立臻7.
6PhantomandItsPreventionTheassumptionthattheDBisafixedcollectionofobjectsisnottruewhenmultigranularitylockingispermitted.
ThenevenStrict2PLwillnotassureserializability:T1locksallpagescontainingsailorrecordswithrating=1,andfindsoldestsailor(say,age=71).
Next,T2insertsanewsailor;rating=1,age=96.
T2alsodeletesoldestsailorwithrating=2(and,say,age=80),andcommits.
T1nowlocksallpagescontainingsailorrecordswithrating=2,andfindsoldest(say,age=63).
NoconsistentDBstatewhereT1is―correct‖!
178数据库管理系统及其实现,徐立臻TheProblemT1implicitlyassumesthatithaslockedthesetofallsailorrecordswithrating=1.
AssumptiononlyholdsifnosailorrecordsareaddedwhileT1isexecuting!
Needsomemechanismtoenforcethisassumption.
(Indexlockingandpredicatelocking)Exampleshowsthatconflictserializabilityguaranteesserializabilityonlyifthesetofobjectsisfixed!
Ifthesystemdon'tsupportmultigranularitylocking,orevenifsupportmultigranularitylocking,thequeryneedtoscanthewholetableandaddSlockonthetable,thenthereisnotthisproblem.
Forexample:selects#,average(grade)fromSCgroupbys#;179数据库管理系统及其实现,徐立臻IndexLockingIfthereisadenseindexontheratingfield,T1shouldlocktheindexnodecontainingthedataentrieswithrating=1andkeepituntilEOT.
Iftherearenorecordswithrating=1,T1mustlocktheindexnodewheresuchadataentrywouldbe,ifitexisted!
WhenT2wantstoinsertanewsailor(rating=1,age=96),hecan'tgettheXlockontheindexnodecontainingthedataentrieswithrating=1,sohecan'tinsertthenewindexitemtorealizetheinsertofanewsailor.
Ifthereisnosuitableindex,T1mustlockthewholetable,nonewrecordscanbeaddedbeforeT1commitofcourse.
r=1DataIndex180数据库管理系统及其实现,徐立臻PredicateLockingGrantlockonallrecordsthatsatisfysomelogicalpredicate,e.
g.
age>2*salary.
Indexlockingisaspecialcaseofpredicatelockingforwhichanindexsupportsefficientimplementationofthepredicatelock.
WhatisthepredicateinthesailorexampleIngeneral,predicatelockinghasalotoflockingoverhead.
Itisalmostimpossibletorealizeit.
181数据库管理系统及其实现,徐立臻7.
7IsolationLevelofTransactionSupportforisolationleveloftransactionisaddedfromSQL-92.
Eachtransactionhasanaccessmode,adiagnosticssize,andanisolationlevel.
SETTRANSACTIONstatementIsolationLevelPossibleresultLockdemandDirtyReadUnrepeatableReadPhantomProblemReadUncommittedMaybeMaybeMaybeNolockwhenread;Xlockwhenwrite,keepuntilEOTReadCommittedNoMaybeMaybeSlockwhenread,releaseafterread;Xlockwhenwrite,keepuntilEOTRepeatableReadsNoNoMaybeAccordingtoStrict2PLSerializableNoNoNoStrict2PLandkeepSlockonleafofindexuntilEOT182数据库管理系统及其实现,徐立臻Example:SETTRANSACTIONREADONLYISOLATIONLEVELREPEATABLEREAD;SETTRANSACTIONISOLATIONLEVEL{READCOMMITTED|READUNCOMMITTED|REPEATABLEREAD|SERIALIZABLE}183数据库管理系统及其实现,徐立臻7.
8面向对象数据库管理系统中的封锁机制1)封锁粒度:OODB中,对象一般作为最小并发控制粒度.
DB-类-对象2)单级封锁:利用S,X锁直接封锁要操作的对象.
只适于面向CAD这类应用的OODBMS,对需要经常进行联想查询的场合不太合适.
3)多粒度封锁:利用上节所述的S,X,IS,IX,SIX等类型的锁,是多粒度封锁的典型应用.
但这时的类级封锁只锁该类的直属实例,不包括该类的子类.
对级联查询或模式修改不合适.
4)复杂多粒度封锁:增加2个类层次锁RL和WL184数据库管理系统及其实现,徐立臻RL-相当于在类及其所有子类都加了S锁WL-相当于在类及其所有子类都加了X锁待加已有NLISIXSSIXXRLWLNLYYYYYYYNISYYYYYNYNIXYYYNNNNNSYYNYNNYNSIXYYNNNNNNXYNNNNNNNRLYYNYNNYNWLYNNNNNNN185数据库管理系统及其实现,徐立臻RL(WL)加锁步骤:a)在该类的任一超类链及DB上加IS(IX)b)在该类加RL(WL)c)自上而下检查该类的子类有无与RL(WL)冲突的锁,若无,可在最先遇到的多继承子类上加RL(WL),子类检查结束d)以上步骤如发现冲突,锁申请失败ABCDEFGIKHJRLISISRLWLIXIXWL5)复杂对象加锁:点到才加锁(按简单多粒度协议)186数据库管理系统及其实现,徐立臻7.
9TheTimeStampMethod1.
T.
S---Anumbergeneratedbycomputer'sinternalclockinchronologicalorder.
2.
T.
Sforatransaction---thecurrentT.
Swhenthetransactioninitials.
3.
T.
Sforandataobject:1)Readtime(tr)–highestT.
Spossessedbyanytransactiontohavereadtheobject.
2)Writetime(tw)–highestT.
Spossessedbyanytransactiontohavewrittentheobject.
4.
ThekeyideaofT.
SmethodisthatthesystemwillenforcetheconcurrenttransactionstoexecuteinthescheduleequivalentwiththeserialexecutionaccordingtoT.
Sorder.
187数据库管理系统及其实现,徐立臻Read/WriteoperationsunderT.
Smethod5.
LetR---adataobjectwithT.
Strandtw.
T---atransactionwithT.
St.
TransactionTreadsR:readRif(t>=tw)then/*OK*/tr=Max(tr,t)else/*atransactionyoungerthanThasalreadywriteRaheadofT,conflict*/restartTwithanewT.
S188数据库管理系统及其实现,徐立臻TransactionTwritesR:if(t>=tr)thenif(t>=tw)then/*OK*/writeRtw=telse/*tr数据库管理系统及其实现,徐立臻Remarks:1.
Comparedwithlockmethod,themostobviousadvantageisthatthereisnodeadlock,becauseofnowait.
2.
Disadvantage:everytransactionandeverydataobjecthasT.
S,andeveryoperationneedtoupdatetrortw,sotheoverheadofthesystemishigh.
3.
Solution:EnlargethegranularityofdataobjectaddedT.
S.
(Lowconcurrencydegree)T.
SofdataobjectarenotactuallystoredinnonvolatilestoragebutinmainmemoryandpreservedforaspecifiedtimeandtheT.
SofdataobjectswhoseT.
Sisnotinmainmemoryareassumedtobezero.
190数据库管理系统及其实现,徐立臻7.
10OptimisticConcurrencyControlMethodThekeyideaofoptimisticmethodisthatitsupposesthereisrareconflictwhenconcurrenttransactionsexecute.
Itdoesn'ttakeanycheckwhiletransactionsareexecuting.
TheupdatesarenotwrittenintoDBdirectlybutstoredinmainmemory,andcheckifthescheduleofthetransactionisserializablewhenatransactionfinishes.
Ifitisserializable,writetheupdatingcopiesinmainmemoryintoDB;Otherwise,abortthetransactionandtryagain.
Thelockmethodandtimestampmethodintroducedabovearecalled―pessimisticmethod‖.
191数据库管理系统及其实现,徐立臻Threephasesoftransactionexecution:1.
Readphase:readdatafromdatabaseandexecuteeverykindofprocessing,butupdateoperationsonlyformupdatecopiesinmemory.
2.
Validatephase:checkifthescheduleofthetransactionisserializable.
3.
Writephase:ifpassthechecksuccessfully,writetheupdatecopiesinmemoryintoDBandcommitthetransaction;Orthrowawaytheupdatecopiesinmemoryandabortthetransaction.
192数据库管理系统及其实现,徐立臻Informationmustbereserved:1.
Readsetofeachtransaction2.
Writesetofeachtransaction3.
Thestartandendtimeofeachphaseofeachtransaction193数据库管理系统及其实现,徐立臻Checkingmethodwhiletransactionends:WhentransactionTiends,onlyneedtocheckifthereisconflictamongTiandthetransactionswhichhavecommittedandothertransactionswhicharealsoincheckingphase.
Thetransactionswhichareinreadphasedon'tneedtobeconsidered.
SupposeTjisanytransactionwhichhascommittedorisbeingchecked,TipassesthecheckifitfulfillsoneofthefollowingconditionsforallTj:1.
TjhadfinishedwritephasewhenTibeganreadphase,Tj→Ti2.
TheintersectionofTi'sreadsetandTj'swritesetisempty,andTibeganwritephaseafterTjfinifhedwritephase.
3.
BothTi'sreadsetandwritesetdon'tintersectwithTj'swriteset.
4.
ThereisnotanyaccessconflictbetweenTiandTj.
194数据库管理系统及其实现,徐立臻7.
11LockinginDDBMS分布式数据库中的并发控制与集中式数据库一样,要求并发事务的执行可串行化.
问题:Multi_copyCommunicationoverhead7.
11.
1writelockall,readlockoneReadR-S_lockonanycopyofRWriteR-X_lockallcopiesofRHoldthelockstoEOT通信开销:设n-No.
ofcopies195数据库管理系统及其实现,徐立臻7.
11.
2MajoritylockingReadR-S_lockonamajorityofcopiesofRWriteR-X_lockonamajorityofcopiesofRHoldthelockstoEOT通信开销:Majority-(n+1)/2CanbemergedWrite:nlockMSGnlockgrantsnupdateMSGnACK[nunlockMSG]Read:1lockMSG1lockgrants1readMSG4n2196数据库管理系统及其实现,徐立臻对7.
11.
1,如两个事务都要写,竞争X锁,可能各自拿到一部分锁,但都不能X-lockall,所以很容易死锁,而此法只要n是奇数就不会发生上述这种形式的死锁,因为总有一个事务先过半数.
Read:(n+1)/2lockMSG(n+1)/2lockgrants1readMSGn+13n+1Write:(n+1)/2lockMSG(n+1)/2lockgrantsnupdateMSGnACK197数据库管理系统及其实现,徐立臻7.
11.
3k-out-of-nlockingWriteR-X_lockonkcopiesofR,k>n/2ReadR-S_lockonn-k+1copiesofRHoldthelockstoEOT对读写冲突:k+(n-k+1)=n+1>n,所以至少可以在一个复本上检测出冲突.
对写写冲突:2k>n,所以也能保证检测出冲突.
所以前两种方法实际上是它的两个特例:7.
11.
1就是k=n;7.
11.
2就是k=(n+1)/2K可在(n+1)/2~n间浮动,k越大对读越有利.
198数据库管理系统及其实现,徐立臻7.
11.
4PrimaryCopyMethodR-dataobjectAssignthelockresponsibilityforlockingRtoagivensite.
ThissiteiscalledprimarysiteofR.
通信开销:Read:1lockMSG1lockgrants1readMSG22n+1Write:1lockMSG1lockgrantsnupdateMSGnACK此法效率较高但易受损害.
为此有很多变种.
经常和主复本更新策略配合使用.
199数据库管理系统及其实现,徐立臻T1AT2AT1BT2BSiteASiteB7.
11.
5GlobalDeadlock上图所示就是一个全局死锁.
如何发现这种死锁全局等待图:在原来的基础上增加EXT结点,如果事务T是分布式事务,在其它结点有子事务,且T在当前结点等待图的链头,则增加EXT→T;如果在当前结点等待图的链尾,则增加T→EXT等待lock等待lock等T1A完成等T2B完成T1和T2均为分布式事务,分别在结点A、B上各有两个子事务.
T1A、T1B必须同时commitT2A、T2B必须同时commit200数据库管理系统及其实现,徐立臻全局等待图的处理方法:例如某结点上有:EXT→Ti→Tj→→Tk→EXT1)找到另一结点:EXT→Tk→Tl→→Tx→EXT2)ifTx=Ti:globaldeadlockisdetected.
ifTx≠Ti:mergetwowait-forgraphs:EXT→Ti→Tj→→Tk→Tl→→Tx→EXT3)重复第1步,看Tx是否会像Tk那样因符合上面条件而产生全局死锁,如各结点上的等待图都检查过而未产生全局回路——无死锁发生.
201数据库管理系统及其实现,徐立臻7.
12TimeStampTechniqueinDDBMS7.
12.
1全局时间戳为避免各结点到来的事务的时间戳相同,设置:GlobalT.
S=LocalT.
S+SiteID各结点时钟可能不同,不要紧,关键是保证:timeofreceipt>=timeofdelivery解决:tatreceiptsite:=max(t1,t2)t1-currentT.
Satreceiptsitet2-T.
SofMSG202数据库管理系统及其实现,徐立臻7.
12.
2读写操作1)Write-updatetwofallcopies.
2)Read-updatetrofthecopyread.
3)WhenwritingwecheckT.
Sofallcopies.
IftWhenreadingwecheckT.
Softhecopyread.
Ift