数据库管理系统及其实现

数据库管理系统及其实现东南大学计算机科学与工程系徐立臻南京，2013.32数据库管理系统及其实现,徐立臻CourseGoalanditsPreliminaryCoursesThePreliminaryCoursesare:DataStructureDatabasePrinciplesDatabaseDesignandApplicationThestudentsshouldalreadyhavethebasicconceptsaboutdatabasesystem,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:数据库管理系统及其实现,徐立臻目录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分布式数据库系统WhatisDDB?ADDBisacollectionofcorrelateddatawhicharespreadacrossanetworkandmanagedbyasoftwarecalledDDBMS.两种：(1)物理上分布，逻辑上统一(一般的DDB)(2)物理上分布，逻辑上也分布(FDBS)本课程以第一种DDBS为主。15数据库管理系统及其实现,徐立臻DistributionCorrelationDDBMSDDBS特征：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命令消息或数据格式化的消息/数据消息或数据消息或数据状态信息或物理块应用n.........ufi/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核心Pipe0Pipe1StateTupNumAttNumAttNameAttTypeAttLen┅┅TmpFileName一个属性的定义其它属性的定义Pipe0：发送SQL语句、内部命令；Pipe1：返回结果。结果格式：26数据库管理系统及其实现,徐立臻进程/线程间通信协议State：0—出错，1—插、删、改操作成功，2—查询成功，需进一步处理结果。TupNum：结果中元组数。AttNum：结果中属性个数。AttName：属性名。AttType：属性类型。AttLen：属性长度。TmpFileName：存放结果数据的临时文件名，其中的数据要用上述字典信息来解释。27数据库管理系统及其实现,徐立臻2.3DDBMS核心的构成DBDCDDDDBKLDB1DBDCDDDDBKLDB2Site1Site2DB：数据库管理DC：通信控制DD：数据字典管理DDBK：核心。负责语法分析、分布事务管理、并发、恢复以及全局查询优化等。28数据库管理系统及其实现,徐立臻全局查询优化例全局查询优化根据代价估算得出一个执行计划表。比如：(1)将R2Site1，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%)查询某一特定记录查询某些记录(15%)范围查询记录的更新33数据库管理系统及其实现,徐立臻文件组织堆文件：按插入先后次序存放，顺序搜索，最基本、通用的文件组织形式直接文件：按某属性值散列映射成记录地址索引文件：索引＋堆文件/簇集动态散列：p111栅格文件结构：p114（多属性查询）RawDisk（注意区别文件的逻辑块和物理块，利用RawDisk可直接控制物理块）34数据库管理系统及其实现,徐立臻索引技术B＋树（√√）簇集索引（√）倒排文件动态散列栅格结构文件和分段散列位图索引（数据仓库）其它类型的索引35数据库管理系统及其实现,徐立臻位图索引－索引本身就是数据DateStoreStateClassSales3/1/9632NYA63/1/9636MAA93/1/9638NYB53/1/9641CTA113/1/9643NYA93/1/9646RIB33/1/9647CTB73/1/9649NYA12BinaryIndexforSales8bit4bit2bit1bit01101001010110111001001101111100forClassABC100100010100100010010100BinaryIndexforStateAKARCACOCTMANYRI……0000001000000100000000100000100000000010000000010000100000000010总销售量＝？(4*8+4*4+4