数据库管理系统vb连接sql数据库

数据库管理系统及其实现东南大学计算机科学与工程系徐立臻南京,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%)查询某一特定记录查询某些记录(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::=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σsal20dept1σ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|仅当②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/*trn/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