王珊、萨师煊《数据库系统概论》考研考点讲义

目录第一章绪论 (1)第二章关系数据库 (20)第三章关系数据库标准语言SQL (36)第四章数据库安全性 (60)第五章数据库完整性 (70)第六章关系数据理论 (78)第七章数据库设计 (98)第九章关系查询处理和查询优化 (122)第十章数据库恢复技术 (131)第十一章并发控制 (141)第十二章现代数据库 (155)第一章绪论第1讲数据库系统概述第一部分知识点回顾·数据(Data)ase·数据库管理系统(DBMS)·数据库系统(DBS)数据(Data)是数据库中存储的基本对象数据的定义：描述事物的符号记录数据的特点：数据的含义称为数据的语义，数据与其语义是不可分的的集合。数据库的基本特征：·数据按一定的数据模型组织、描述和储存·可为各种用户共享·冗余度较小·数据独立性较高·易扩展DBMS于用户与操作系统之间的一层数据管理软件；是基础软件，是一个大型复杂的软件系统·数据定义功能—2—提供数据定义语言(DDL)定义数据库中的数据对象·数据组织、存储和管理分类组织、存储和管理各种数据确定组织数据的文件结构和存取方式实现数据之间的联系提供多种存取方法提高存取效率·数据操纵功能提供数据操纵语言(DML)实现对数据库的基本操作(查询、插入、删除和修改)·数据库的事务管理和运行管理数据库在建立、运行和维护时由DBMS统一管理和控制保证数据的安全性、完整性、多用户对数据的并发使用发生故障后的系统恢复·数据库的建立和维护功能(实用程序)数据库初始数据装载转换数据库转储介质故障恢复数据库的重组织性能监视分析等·其它功能DBMS与网络中其它软件系统的通信两个DBMS系统的数据转换异构数据库之间的互访和互操作数据管理：·数据处理的中心问题数据管理技术的发展过程：·人工管理阶段(20世纪40年代中—50年代中)·文件系统阶段(20世纪50年代末—60年代中)·数据库系统阶段(20世纪60年代末—现在)特点：·数据的管理者：用户(程序员)，数据不保存·数据面向的对象：某一应用程序—3—·数据的共享程度：无共享、冗余度极大·数据的独立性：不独立，完全依赖于程序·数据的结构化：无结构·数据控制能力：应用程序自己控制人工管理阶段应用程序与数据的对应关系特点：·数据的管理者：文件系统，数据可长期保存·数据面向的对象：某一应用程序·数据的共享程度：共享性差、冗余度大·数据的结构化：记录内有结构，整体无结构·数据的独立性：独立性差，数据的逻辑结构改变必须修改应用程序·数据控制能力：应用程序自己控制文件系统阶段应用程序与数据的对应关系文件系统中数据的结构·记录内有结构。·数据的结构是靠程序定义和解释的。·数据只能是定长的。可以间接实现数据变长要求，但访问相应数据的应用程序复杂了。·文件间是独立的，因此数据整体无结构。可以间接实现数据整体的有结构，但必须在应用程序中对描述数据间的联系。·数据的最小存取单位是记录。时期：—4—·20世纪60年代末以来产生的背景：·应用背景—大规模管理·硬件背景—大容量磁盘、磁盘阵列·软件背景—有数据库管理系统·处理方式—联机实时处理，分布处理，批处理·数据结构化：整体结构化·数据的共享性高，冗余度低，易扩充：从整体角度看待和描述数据，数据面向整个系统，可以被多个用户、多个应用共享使用。·数据独立性高：物理独立性：当数据的物理存储改变了，应用程序不用改变。逻辑独立性：数据的逻辑结构改变了，用户程序也可以不变。·数据由DBMS统一管理和控制数据库系统应用程序与数据的对应关系第二部分考点试题分析1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是阶段。2．下面列出的数据库管理技术发展的三个阶段中，没有专门的软件对数据进行管理的是。3．数据库的基本特点是。A．(1)数据可以共享(2)数据独立性高—5— (3)数据冗余大，易移植B．(1)数据可以共享 (3)数据冗余小，易扩充C．(1)数据可以共享 (3)数据冗余小，易扩充D．(1)数据非结构化 (3)数据冗余小，易扩充 (4)统一管理和控制 (2)数据独立性高 (4)统一管理和控制 (2)数据互换性 (4)统一管理和控制 (2)数据独立性高 (4)统一管理和控制4．是存储在计算机内有结构的数据的集合。A．数据库系统CA．数据库系统C．数据库管理系统C．数据以及数据之间的联系6．数据库中，数据的物理独立性是指。A．数据库与数据库管理系统的相互独立B．用户程序与DBMS的相互独立C．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的D．应用程序与数据库中数据的逻辑结构相互独立7．数据库的特点之一是数据的共享，严格地讲，这里的数据共享是指。A．同一个应用中的多个程序共享一个数据集合B．多个用户、同一种语言共享数据C．多个用户共享一个数据文件D．多种应用、多种语言、多个用户相互覆盖地使用数据集合8C．数据模型9．下述关于数据库系统的正确叙述是。A．数据库系统减少了数据冗余B．数据库系统避免了一切冗余C．数据库系统中数据的一致性是指数据类型一致D．数据库系统比文件系统能管理更多的数据10．数据库系统的特点是、数据独立、减少数据冗余、避免数据不一致和加强了数据保护。护A．数据共享B．数据存储C．数据应用D．数据保密11．据库系统的最大特点是。A．数据的三级抽象和二级独立性B．数据共享性—6—C．数据的结构12．数据库管理系统能实现对数据库中数据的查询、插入、修改和删除等操作，这种功能称为 。A．数据定义功能C．数据操纵功能13．数据库管理系统是。A．操作系统的一部分B．在操作系统支持下的系统软件C．一种编译程序D．一种操作系统和三个阶段。3．DBMS是指，它是位于和之间的一层管理软件。件的运行管理和数据库的建立以及维护等4个方面。5．数据独立性又可分为和。6．当数据的物理存储改变了，应用程序不变，而由DBMS处理这种改变，这是指数据的 。2．什么是数据库的数据独立性？3．什么是数据字典？数据字典包含哪些基本内容？第2讲数据模型第一部分知识点回顾数据模型·在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。·通俗地讲数据模型就是现实世界的模拟。·数据模型应满足三方面要求能比较真实地模拟现实世界容易为人所理解—7—便于在计算机上实现数据模型分为两类(分属两个不同的层次) (1)概念模型，也称信息模型，它是按用户的观点来对数据和信息建模，用于数据库设计。 (2)逻辑模型和物理模型·逻辑模型主要包括网状模型、层次模型、关系模型、面向对象模型等，按计算机系统的观点对数·物理模型是对数据最底层的抽象，描述数据在系统内部的表示方式和存取方法，在磁盘或磁带上的存储方式和存取方法。·数据结构(描述数据库的组成对象，以及对象之间的联系)·数据操作(对数据库中各种对象(型)的实例(值)允许执行的操作及有关的操作规则)·完整性约束条件(给定的数据模型中数据及其联系所具有的制约和储存规则，用以限定符合数)·信息世界中的基本概念·两个实体型之间的联系·两个以上实体型之间的联系·单个实体型内的联系·概念模型的一种表示方法·一个实例 (1)实体(Entity)客观存在并可相互区别的事物称为实体。 (2)属性(Attribute)实体所具有的某一特性称为属性。一个实体可以由若干个属性来刻画。 (3)码(Key)唯一标识实体的属性集称为码。 (4)域(Domain)属性的取值范围称为该属性的域。 (5)实体型(EntityType)用实体名及其属性名集合来抽象和刻画同类实体称为实体型 (6)实体集(EntitySet)同一类型实体的集合称为实体集 联系(Relationship)现实世界中事物内部以及事物之间的联系在信息世界中反映为实体内部的联系和实体之间的联系。实体内部的联系通常是指组成实体的各属性之间的联系实体之间的联系通常是指不同实体集之间的联系用图形来表示两个实体型之间的这三类联系·两个以上实体型之间一对多联系的。的·实例实体型，一门课程可以有若干个教师讲授，使用若干本参考书，每一个教考书只供一门课程使用·一对多联系—9—实例职工实体型内部具有领导与被领导的联系，某一职工(干部)“领导”若干名职工，一个职工仅被另外一个职工直接领导，这是一对多的联系·实体－联系方法(E－R方法)用E－R图来描述现实世界的概念模型一个实例·非关系模型·关系模型(RelationalModel)l·在用户观点下，关系模型中数据的逻辑结构是一张二维表，它由行和列组成。学生登记表学号姓名年龄性别系名年级王小明女社会学黄大鹏男商品学张文斌女法律………………·关系(Relation)一个关系对应通常说的一张表·元组(Tuple)表中的一行即为一个元组·属性(Attribute)表中的一列即为一个属性，给每一个属性起一个名称即属性名·主码(Key)表中的某个属性组，它可以唯一确定一个元组。·域(Domain)属性的取值范围。·分量元组中的一个属性值。·关系模式对关系的描述·关系必须是规范化的，满足一定的规范条件最基本的规范条件：关系的每一个分量必须是一个不可分的数据项，不允许表中还有表项，不符合关系模型要求职工号姓名职称工资扣除实发基本津贴职务房租水电陈平讲师图1．27一个工资表(表中有表)实例关系术语一般表格的术语关系名表名关系模式表头(表格的描述)关系 (一张)二维表元组记录或行属性列属性名列名属性值列值分量一条记录中的一个列值非规范关系表中有表(大表中嵌有小表)整性约束·数据操作是集合操作，操作对象和操作结果都是关系，即若干元组的集合查询插入删除更新·关系的完整性约束条件实体完整性参照完整性用户定义的完整性·实体及实体间的联系都用表来表示·表以文件形式存储有的DBMS一个表对应一个操作系统文件有的DBMS自己设计文件结构·优点建立在严格的数学概念的基础上概念单一实体和各类联系都用关系来表示对数据的检索结果也是关系关系模型的存取路径对用户透明具有更高的数据独立性，更好的安全保密性简化了程序员的工作和数据库开发建立的工作·缺点存取路径对用户透明导致查询效率往往不如非关系数据模型询请求进行优化，增加了开发DBMS的难度第二部分考点试题解析1．信息世界中的术语，与之对应的数据库术语为。A．文件B．数据库C．字段D．记录2．层次型、网状型和关系型数据库划分原则是。C．C．联系的复杂程度D．数据之间的联系3．传统的数据模型分类，数据库系统可以分为三种类型。5．数据库技术的奠基人之一E．F．Codd从1970年起发表过多篇论文，主要论述的是。D．面向对象数据模型6．在数据库中，产生数据不一致的根本原因是。A．数据存储量太大A．数据存储量太大C．未对数据进行完整性控制7．数据库的概念模型独立于。A．具体的机器和DBMSB．E－R图C．信息世界D．现实世界8．描述数据库全体数据的全局逻辑结构和特性的是。A．模式B．内模式C．外模式D．用户模式9．要保证数据库的数据独立性，需要修改的是。A．模式与外模式CA．模式与外模式C．三层之间的两种映射D．三层模式10．用户或应用程序看到的那部分局部逻辑结构和特征的描述是，它是模式的逻辑子集。ABCD．内模式、和三部分组成的。是对数据库系统的动态特性的描述。3．数据库体系结构按照、和三级结构进行组织。5．数据冗余可能导致的问题有和。1．使用数据库系统有什么好处？2．试述文件系统与数据库系统的区别和联系。3．试述数据库系统的特点。4．试述数据模型的概念、数据模型的作用和数据模型的三个要素。5．试述概念模型的作用。6．试给出三个实际部门的E－R图，要求实体型之间具有一对一，一对多，多对多各种不同的联系。系第3讲数据库系统结构及组成第一部分知识点回顾·从数据库管理系统角度看，数据库系统通常采用三级模式结构，是数据库系统内部的系统结构·从数据库最终用户角度看(数据库系统外部的体系结构)，数据库系统的结构分为：单用户结构主从式结构分布式结构多层结构等型(Type)：对某一类数据的结构和属性的说明例如：ma数据库逻辑结构和特征的描述是型的描述反映的是数据的结构及其联系模式是相对稳定的·实例(Instance)模式的一个具体值反映数据库某一时刻的状态同一个模式可以有很多实例实例随数据库中的数据的更新而变动1．28数据库系统的三级模式结构·模式(也称逻辑模式)数据库中全体数据的逻辑结构和特征的描述所有用户的公共数据视图，综合了所有用户的需求·一个数据库只有一个模式·模式的地位：是数据库系统模式结构的中间层与数据的物理存储细节和硬件环境无关与具体的应用程序、开发工具及高级程序设计语言无关·模式的定义数据的逻辑结构(数据项的名字、类型、取值范围等)数据之间的联系数据有关的安全性、完整性要求·外模式(也称子模式或用户模式)数据库用户(包括应用程序员和最终用户)使用的局部数据的逻辑结构和特征的描述数据库用户的数据视图，是与某一应用有关的数据的逻辑表示·外模式的地位：介于模式与应用之间模式与外模式的关系：一对多外模式通常是模式的子集一个数据库可以有多个外模式。反映了不同的用户的应用需求、看待数据的方式、对数据保密的要求·外模式与应用的关系：一对多同一外模式也可以为某一用户的多个应用系统所使用但一个应用程序只能使用一个外模式·外模式的用途保证数据库安全性的一个有力措施每个用户只能看见和访问所对应的外模式中的数据·内模式(也称存储模式)是数据物理结构和存储方式的描述是数据在数据库内部的表示方式记录的存储方式(顺序存储，按照B树结构存储，按hash方法存储)索引的组织方式数据是否压缩存储数据是否加密数据存储记录结构的规定·一个数据库只有一个内模式例如：学生记录，如果按堆存储，则插入一条新记录总是放在学生记录存储的最后，如下图所示：·如果按学号升序存储，则插入一条记录就要找到它应在的位置插入。如图(b)所示·如果按照学生年龄聚簇存放，假如新插入的S3是16岁，则应插入的位置。如图(c)所示·三级模式是对数据的三个抽象级别·二级映象在DBMS内部实现这三个抽象层次的联系和转换·模式：描述的是数据的全局逻辑结构·外模式：描述的是数据的局部逻辑结构·同一个模式可以有任意多个外模式·每一个外模式，数据库系统都有一个外模式／模式映象，定义外模式与模式之间的对应关系·映象定义通常包含在各自外模式的描述中保证数据的逻辑独立性·当模式改变时，数据库管理员修改有关的外模式／模式映象，使外模式保持不变·应用程序是依据数据的外模式编写的，从而应用程序不必修改，保证了数据与程序的逻辑独立性，简称数据的逻辑独立性。·模式／内模式映象定义了数据全局逻辑结构与存储结构之间的对应关系。例如，说明逻辑记录和字段在内部是如何表示的·数据库中模式／内模式映象是唯一的·该映象定义通常包含在模式描述中保证数据的物理独立性·当数据库的存储结构改变了(例如选用了另一种存储结构)，数据库管理员修改模式／内模式映·应用程序不受影响。保证了数据与程序的物理独立性，简称数据的物理独立性。1．28数据库系统的三级模式结构·数据库·数据库管理系统(及其开发工具)·应用系统·数据库管理员·硬件平台及数据库·软件·人员具体职责： (1)决定数据库中的信息内容和结构 (2)决定数据库的存储结构和存取策略 (3)定义数据的安全性要求和完整性约束条件 (4)监控数据库的使用和运行·周期性转储数据库(数据文件，日志文件)·系统故障恢复；介质故障恢复·监视审计文件 (5)数据库的改进和重组·性能监控和调优·定期对数据库进行重组织，以提高系统的性能·需求增加和改变时，数据库须需要重构造·系统分析员负责应用系统的需求分析和规范说明与用户及DBA协商，确定系统的硬软件配置参与数据库系统的概要设计·数据库设计人员参加用户需求调查和系统分析确定数据库中的数据设计数据库各级模式·应用程序员设计和编写应用系统的程序模块进行调试和安装·用户用户是指最终用户(EndUser)。最终用户通过应用系统的用户接口使用数据库。 (1)偶然用户：不经常访问数据库，但每次访问数据库时往往需要不同的数据库信息，例如企业或组织机构的高中级管理人员； (2)简单用户：主要工作是查询和更新数据库，例如银行的职员、机票预定人员、旅馆总台服务员； (3)复杂用户：直接使用数据库语言访问数据库，甚至能够基于数据库管理系统的API编制自己·数据库系统概述数据库的基本概念数据管理的发展过程·数据模型数据模型的三要素三种主要数据库模型·数据库系统的结构数据库系统三级模式结构数据库系统两层映像系统结构·数据库系统的组成第二部分考点例题解析1．下述不是DBA数据库管理员的职责。B．定义数据库模式B．定义数据库模式D．数据库管理系统设计C2．数据库(DB)，数据库系统(DBS)和数据库管理系统(DBMS)之间的关系是。3．DBS是采用了数据库技术的计算机系统，它是一个集合体，包含数据库、计算机硬件、软件和 。D．操作员4．数将数据库的结构划分成多个层次，是为了提高数据库的①和②。①A．数据独立性B．逻辑独立性C．管理规范性D．数据的共享②A．数据独立性B．物理独立性C．逻辑独立性D．管理规范性5．数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是。A．外模式B．内模式C．存储模式D．模式6．数据库系统的数据独立性是指。A．不会因为数据的变化而影响应用程序B．不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序C．不会因为存储策略的变化而影响存储结构D．不会因为某些存储结构的变化而影响其他的存储结构据组织存储和管理、数据库运行管理和事物管理、数据库的建立和维护功能。2．数据库系统是指在计算机系统中引入数据库后的系统，一般由数据库、、 和数据库管理员构成。3．模型是目前最常用也是最重要的一种数据模型。采用该模型作为数据的组织方式的数据库系统称为。4．数据冗余可能导致的问题有和。1．数据库管理系统的主要功能有哪些？据库管理系统？—20—第二章关系数据库第1讲关系模型三要素第一部分知识点回顾系数据结构及形式化定义 (1)域：域是一组具有相同数据类型的值的集合。 所有域的所有取值的一个组合不能重复·张清玫、计算机专业、李勇等都是分量n笛卡尔积的表示方法·笛卡尔积可表示为一个二维表·表中的每行对应一个元组，表中的每列对应一个域张清玫计算机专业李勇张清玫计算机专业刘晨张清玫计算机专业王敏—21—续表张清玫信息专业李勇张清玫信息专业刘晨张清玫信息专业王敏刘逸计算机专业李男刘逸计算机专业刘晨刘逸计算机专业王敏刘逸信息专业李男刘逸信息专业刘晨刘逸信息专业王敏1)关系其中：2)元组关系中的每个元素是关系中的元组，通常用t表示。3)单元关系与二元关系4)关系的表示关系也是一个二维表，表的每行对应一个元组，表的每列对应一个域5)属性关系中不同列可以对应相同的域起一个名字，称为属性n目关系必有n个属性6)码·候选码(Candidatekey)若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码·全码(All－key)最极端的情况：关系模式的所有属性组是这个关系模式的候选码，称为全码(All－key)·主码—22—若一个关系有多个候选码，则选定其中一个为主码(Primarykey)·主属性不包含在任何侯选码中的属性称为非主属性，或非码属性7)三类关系·基本关系(基本表或基表)：实际存在的表，是实际存储数据的逻辑表示·查询表：查询结果对应的表·视图表：由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据8)基本关系的性质②不同的列可出自同一个域·其中的每一列称为一个属性·不同的属性要给予不同的属性名可以任意交换④任意两个元组的候选码不能相同⑤行的顺序无所谓，行的次序可以任意交换⑥分量必须取原子值这是规范条件中最基本的一条·关系是值·关系模式是对关系的描述·元组集合的结构属性构成属性来自的域属性与域之间的映象关系·元组语义以及完整性约束条件·属性间的数据依赖关系集合—23—关系模式可以形式化地表示为：DU性所来自的域F：属性间的数据依赖关系集合关系模式通常可以简记为注：域名及属性向域的映象常常直接说明为属性的类型、长度·关系模式对关系的描述·关系关系模式在某一时刻的状态或内容态的、随时间不断变化的·关系模式和关系往往统称为关系通过上下文加以区别·在一个给定的应用领域中，所有关系的集合构成一个关系数据库·关系数据库的型：关系数据库模式对关系数据库的描述。·关系数据库模式包括若干域的定义在这些域上定义的若干关系模式·关系数据库的值：关系模式在某一时刻对应的关系的集合，简称为关系数据库—24—·常用的关系操作查询的表达能力是其中最主要的部分·关系操作的特点集合操作方式：操作的对象和结果都是集合，一次一集合的方式·关系代数语言用对关系的运算来表达查询要求·关系演算语言：用谓词来表达查询要求元组关系演算语言谓词变元的基本对象是元组变量域关系演算语言谓词变元的基本对象是域变量·具有关系代数和关系演算双重特点的语言·实体完整性和参照完整性：关系模型必须满足的完整性约束条件称为关系的两个不变性，应该由关系系统自动支持·用户定义的完整性：应用领域需要遵循的约束条件，体现了具体领域中的语义约束若属性A是基本关系R的主属性，则属性A不能取空值例：—25—主码(假设研究生不会重名)不能取空值注意：实体完整性规则规定基本关系的所有主属性都不能取空值，而不仅是主码整体不能取空值。【例】则学号和课程号两个属性都不能取空值·在关系模型中实体及实体间的联系都是用关系来描述的，因此可能存在着关系与关系间的引用。专业(专业号，专业名)·学生关系引用了专业关系的主码“专业号”。·学生关系中的“专业号”值必须是确实存在的专业的专业号，即专业关系中有该专业的记录。·设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码Ks相FR的外码gRelationtRelation。·“专业号”属性是学生关系的外码·专业关系是被参照关系，学生关系为参照关系学生关系—→专业关系专学生关系—→专业关系 ·关系R和S不一定是不同的关系·目标关系S的主码Ks和参照关系的外码F必须定义在同一个(或一组)域上·外码并不一定要与相应的主码同名当外码与相应的主码属于不同关系时，往往取相同的名字，以便于识别·规则2．2参照完整性规则若属性(或属性组)F是基本关系R的外码它与基本关系S的主码Ks相对应(基本关系R和S不一定是不同的关系)，则对于R中每个元组在F上的值必须为：—26—·或者取空值(F的每个属性值均为空值)·或者等于S中某个元组的主码值： (1)空值，表示尚未给该学生分配专业； (2)非空值，这时该值必须是专业关系中某个元组的“专业号”值，表示该学生不可能分配一不存在的专业。·针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求。·关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不要由应用程序承担这一功能。·“课程号”属性必须取唯一值·非主属性“课程名”也不能取空值第二部分考点试题解析AB．至多由一个属性组成C．可由一个或多个其值能惟一标识该关系模式中任何元组的属性组成D．以上都不是2．关系模式的任何属性。C．C．命名在该关系模式中可以不惟一D．以上都不是3．下面的选项不是关系数据库基本特征的是。A．不同的列应有不同的数据类型B．不同的列应有不同的列名C．与行的次序无关D．与列的次序无关4．一个关系只有一个。A．候选码B．外码C．超码D．主码5．关系DBS中，对外部关键字(外码)没有任何限制的操作是。A．插入B．删除C．修改6．现有如下关系：—27—其中，医疗关系中的外码是。C．C．患者编号和患者姓名D．医生编号和患者编号7．现有一个关系：借阅(书号，书名，库存数，读者号，借期，还期)，假如同一本书允许一个读者多次借阅，但不能同时对一种书借多本，则该关系模式的主码是。D．书号＋读者号＋借期8．关系模型中实现实体间N：M联系是通过增加一个。C．关系或一个属性实现C．关系或一个属性实现D．关系和一个属性实现1．一个关系模式的定义格式为。 。3．关系数据库中基于数学上两类运算是和。4．已知系(系编号，系名称，系主任，电话，地点)和学生(学号，姓名，性别，入学日期，专业，系编号)两个关系，系关系的主关键字是，系关系的外关键字，学生关系的主关键字是，外关键字。1．试述关系模型的三个组成部分。2．试述关系数据语言的特点和分类。3．试述关系模型的完整性规则。在参照完整性中，为什么外部码属性的值也可以为空？什么情况下才可以为空？第2讲关系代数及关系演算第一部分知识点回顾·概述(集合运算符，比较运算符，专门关系运算符，逻辑运算符)·传统的集合运算·专门的关系运算—28—)))·关系运算符)))先引入几个记号 (3)trts 专门关系运算符含义—29—一般连接RS的结果如下：等值连接RS的结果如下：—30—自然连接RS的结果如下：·外连接如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值(Null)，这种连接就叫做外连OUTERJOIN。·左外连接如果只把左边关系R中要舍弃的元组保留就叫做左外连接(LEFTOUTERJOIN或LEFTJOIN)·右外连接如果只把右边关系S中要舍弃的元组保留就叫做右外连接(RIGHTOUTERJOIN或RIGHTR÷S＝{trX|tr∈R∧πY(S)YX}—31—分析：【例3】查询选修了全部课程的学生号码和姓名。·关系代数运算·基本运算可以用5种基本运算来表达引进它们并不增加语言的能力，但可以简化表达·关系代数表达式关系代数运算经有限次复合后形成的式子·典型关系代数语言—32—·关系演算以数理逻辑中的谓词演算为基础·按谓词变元不同进行分类以元组变量作为谓词变元的基本对象元组关系演算语言ALPHA以域变量作为谓词变元的基本对象域关系演算语言QBE·关系数据库系统是目前使用最广泛的数据库系统·关系数据库系统与非关系数据库系统的区别：·关系数据结构·关系操作·关系的完整性约束·关系数据语言第二部分考点试题解析1．自然连接是构成新关系的有效方法。一般情况下，当对关系R和S使用自然连接时，要求R和S含有一个或多个共有的。A．元组B．行C．记录D．属性2．关系运算中花费时间可能最长的运算是。A．投影B．选择C．笛卡尔积D．除3．在关系代数运算中，五种基本运算为。4．设有关系R，按条件f对关系RD．πF(D．πF(R)F5．如图所示，两个关系R1和R2，它们进行运算后得到R3。—33—A．交B．并C．笛卡尔积D．连接6．关系代数运算是以为基础的运算。DD数运算7．关系数据库管理系统应能实现的专门关系运算包括。8．关系代数表达式的优化策略中，首先要做的是。D．投影运算9．关系数据库中的投影操作是指从关系中。D．建立相应的图形10．从一个数据库文件中取出满足某个条件的所有记录形成一个新的数据库文件的操作是 操作。ABCD．复制11．关系代数中的联接操作是由操作组合而成。A．选择和投影A．选择和投影D．投影和笛卡尔积12．自然联接是构成新关系的有效方法。一般情况下，当对关系R和S是用自然联接时，要求R和S含有一个或者多个共有的。ABCD．元组13．假设有关系R和S，关系代数表达式R－(R－S)表示的是。14．下面列出的关系代数表达式中，那些式子能够成立。Ⅰ．σf1(σf2(E))＝σf1∧f2(E)EE)∞E3＝E1∞(E2∞E3)Ⅳ．σf1(σf2(E))＝σf2(σf1(E))算有、、和 。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y在关系模式R(U)中，对于U的子集X和Y，如果X→Y，但YX，则称X→Y是非平凡的函数依赖若X→Y，但YX，则称X→Y是平凡的函数依赖 ·若X→Y，则X称为这个函数依赖的决定属性组，也称为决定因素(Determinant)。XY·若Y不函数依赖于X，则记作X→Y。F全函数依赖，记作X—→Y。PXY 传递FF若候选码多于一个，则选定其中的一个做为主码(PrimaryKey)。·主属性与非主属性bute·全码llkey外部码定义6．5关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码(Foreignkey)也称外码。关系模式SC的外部码·主码与外部码一起提供了表示关系间联系的手段·范式是符合某一种级别的关系模式的集合·关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式·范式的种类：(第一范式(1NF) |〈第五范式(5NF)第五范式(5NF)·各种范式之间存在联系：1NF2NF3NFBCNF4NF5NF·一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。·1NF的定义第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。·2NF的定义·3NF的定义若R∈3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。等价于：每一个决定属性因素都包含码。所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码，也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性RNFR只有一个候选码第二部分考点试题分析2．采用E－R数据模型方法对某一应用数据库系统进行需求分析和建立数据模型时，建立的数据模型与将来采用的何种数据管理软件(DBMS)有关吗？5．一个关系的外键可由多个属性构成吗？】ANFBNFCNFD4NF2．关系数据模型是当前最常用的一种数据模型，它是用(①)结构来表示实体类型及实体之间的联系的。关系数据库的数据操作语言(DML)主要包括(②)两类操作，关系模型的关系运算是以关系代数为理论基础的，关系代数的基本操作是(③)。【2004北师大】②A．删除和插入②A．删除和插入C和修改D．检索和更新3．设3．设R和S为两个关系，则R|X|S表示R与S的(①)。若R和S的关系分别图示如下：供选择的答案：②个人借书证号、书号、书名、书价、图书出版社，则该关系模式(①)。他的主要问题是数据冗余。若把R0分解成两个关系模式R1(②)和R2(③)，则可以部分的解决这一问题。R1和R2是规范化程度较供选择的答案：①④⑤D．不是范式②③4．我们在一个关系中()。【2012青岛大学】A．必须定义一个主关键字B．只能创建一个聚集索引(clusterindex)C．只能创建一个稠密索引D．只能定义一个约束5．在DBMS的关系中()。D值都不可以为空C．任何属性值都可以为空个是R的关键字()。7．关于第三范式描述正确的是()。D它就属于第三范式8．关系数据模型是目前最重要的一种数据模型，它的三个要素分别是()。A．实体完整性、参照完整性、用户自定义完整性9．关于分布式数据库系统和并行数据库系统，下列说法正确的是()。A．分布式数据库系统的目标是利用多处理机结点并行地完成数据库任务以提高数据库系统的整体性能B．并行数据库系统目的主要在于实现场地自治和数据全局透明共享C．并行数据库系统经常采用负载平衡方法提供数据库系统的业务吞吐率D．分布式数据库系统中，不存在全局应用时各局部应用的概念，各节点完全不独立，各个节点需要协同工作RA规范化程度最高达到()。F第2讲数据依赖的公理系统第一部分知识点回顾【例9】学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。·用二维表表示Teaching (1)数据冗余度大 (2)插入操作复杂 (3)删除操作复杂 (4)修改操作复杂设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且Z＝U－X－Y。关系模式R(U)中多值依赖X→→Y成立，当且仅当对R(U)的任一关系r，给定的一对(x，z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。对于一个(物理，光学原理)有一组T值{李勇，王军}，这组值仅由课程C上的值(物理)决定，对于另一个(物理，物理习题集)对应的T值仍是{李勇，王军}，因此T多值依赖于C。·多值依赖的另一个等价的形式化的定义： [Z](即交换s，t元组的Y值所得的两个新元组必在r中)，则Y多值依赖于X，记为X→→Y。这里，元组课程教员参考书W物理李明物理习题集T物理李明物理数学方法S物理赵海物理习题集V物理赵海物理数学方法·平凡多值依赖和非平凡的多值依赖XYZXYXY赖用下图表示这种对应多值依赖的性质： (1)多值依赖具有对称性 (2)多值依赖具有传递性 (3)函数依赖是多值依赖的特殊情况 (5)若X→→Y，X→→Z，则X→→YnZ 多值依赖与函数依赖的区别： (1)多值依赖的有效性与属性集的范围有关 (2)·若函数依赖X→Y在R(U)上成立，则对于任何Y＇，Y均有X→Y＇成立·多值依赖X→→Y若在R(U)上成立，不能断言对于任何Y＇，Y有X→→Y＇成立·如果R=4NF，则R=BCNF不允许有非平凡且非函数依赖的多值依赖允许的非平凡多值依赖是函数依赖逻辑蕴含YFXY·A1．自反律(Reflexivity)：若YX→U，则X→Y为F所蕴含。·A2．增广律(Augmentation)：若X→Y为F所蕴含，且Z→U，则XZ→YZ为F所蕴含。·A3．传递律(Transitivity)：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。定理6．1Armstrong推理规则是正确的。 (l)自反律：若YXU，则X→Y为F所蕴含。证：设YXU所以X→Y成立，自反律得证。 (2)增广律：若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。 (3)传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。XYYZ为F所蕴含。 (A2，A3) (A2，A3) 2)根据合并规则和分解规则，可得引理6．1FArmstrong在F＋中；F的闭包关于闭包的引理要条件是YXF＋·用途F的子集的问题。求闭包的算法算法6．1求属性集X(XU)关于U上的函数依赖集F的闭包XF＋ (2)求B，这里B＝{A|(3V)(3W)(V→W∈F∧VX(i)∧A∈W)}； (3)X(i＋1)＝BUX(i)； XiXi (5)若相等或X(i)＝U，则X(i)就是XF＋，算法终止。 U定义6．15如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1)F中任一函数依赖的右部仅含有一个属性。 (2)F中不存在这样的函数依赖X→A，使得F与F－{X→A}等价。 (3)F中不存在这样的函数依赖X→A，X有真子集Z使得F－{X→A}U{Z→A}与F等价。 第2讲逻辑与物理结构设计第一部分知识点回顾根据需求分析的结果确定概念模型。概念模型是对现实世界的一个真实模型，且能满足用户对数据的处理要求。概念模型直观形象、容易和用户沟通。概念模型易于修改。概念模型与具体数据模型无关且容易向数据库模型转化。·概念结构是各种数据模型的共同基础。·为了能够用某一DBMS实现用户需求，还必须将概念结构进一步转化为相应的数据模型，这正是数据库逻辑结构设计所要完成的任务。班名人数……姓名年龄性别王洋女刘兴男………课名学时学分先修课数据库数据结构操作系统………2)一个1：1联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并。①转换为一个独立的关系模式·关系的属性：与该联系相连的各实体的码以及联系本身的属性。·关系的候选码：每个实体的码均是该关系的候选码。②与某一端对应的关系模式合并·合并后关系的属性：加入对应关系的码和联系本身的属性·合并后关系的码：不变注意：·从理论上讲，1：1联系可以与任意一端对应的关系模式合并。但在一些情况下，与不同的关系模式合并效率会大不一样。因此究竟应该与哪端的关系模式合并需要依应用的具体情况而定。·由于连接操作是最费时的操作，所以一般应以尽量减少连接操作为目标。例如，如果经常要查询某个班级的班主任姓名，则将负责联系与班级关系合并更好些。 (3)一个1：n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。①转换为一个独立的关系模式·关系的属性：与该联系相连的各实体的码以及联系本身的属性。·关系的码：n端实体的码。②与n端对应的关系模式合并·合并后关系的属性：在n端关系中加入1端关系的码和联系本身的属性．·合并后关系的码：不变以减少系统中的关系个数，一般情况下更倾向于采用这种方法．①使其成为一个独立的关系模式：负责(班名，辅导员姓名)②将其与班级关系模式合并：负责(班名，人数，辅导员姓名) (4)一个m：n联系转换为一个关系模式。关系的属性：与该联系相连的各实体的码以及联系本身的属性关系的码：各实体码的组合合码：班名课名时间季数据结构季季数据结构季编译原理季 (5)三个或三个以上实体间的一个多元联系转换为一个关系模式。关系的属性：与该多元联系相连的各实体的码以及联系本身的属性关系的码：各实体码的组合系的组合码： (6)具有相同码的关系模式可以合并 例，如果教师实体集内部存在领导与被领导的1：n自联系，我们可以将该联系与教师实体合并，这时主码职工号将多次出现，但作用不同，可用不同的属性名加以区分：·一般的数据模型还需要向特定DBMS规定的模型进行转换。·转换的主要依据是所选用的DBMS的功能及限制。没有通用规则。·对于关系模型来说，这种转换通常都比较简单。·数据库逻辑设计的结果不是唯一的。·得到初步数据模型后，还应该适当地修改、调整数据模型的结构，以进一步提高数据库应用系统的性能，这就是数据模型的优化。查询的投影属性数据更新事务被更新的关系每个关系上的更新操作条件所涉及的属性修改操作要改变的属性值每个事务在各关系上运行的频率和性能要求·关系数据库物理设计的内容 (1)为关系模式选择存取方法(建立存取路径) (2)设计关系、索引等数据库文件的物理存储结构·数据库系统是多用户共享的系统，对同一个关系要建立多条存取路径才能满足多用户的多种应用要求。·物理设计的第一个任务就是要确定选择哪些存取方法，即建立哪些存取路径。·DBMS常用存取方法聚簇(Cluster)方法·选择索引存取方法的主要内容根据应用要求确定对哪些属性列建立索引对哪些属性列建立组合索引对哪些索引要设计为唯一索引·选择索引存取方法的一般规则如果一个(或一组)属性经常在查询条件中出现，则考虑在这个(或这组)属性上建立索引(或组合索引)如果一个属性经常作为最大值和最小值等聚集函数的参数，则考虑在这个属性上建立索引如果一个(或一组)属性经常在连接操作的连接条件中出现，则考虑在这个(或这组)属性上建立索引·关系上定义的索引数过多会带来较多的额外开销(维护开销，查找开销)·聚簇的用途 (1)大大提高按聚簇属性进行查询的效率 (2)节省存储空间·聚簇的局限性 (1)聚簇只能提高某些特定应用的性能 (2)建立与维护聚簇的开销相当大·聚簇的适用范围 (1)既适用于单个关系独立聚簇，也适用于多个关系组合聚簇 (2)当通过聚簇码进行访问或连接是该关系的主要应用，与聚簇码无关的其他访问很少或者是次要的时，可以使用聚簇。·选择聚簇存取方法 (1)设计候选聚簇对经常在一起进行连接操作的关系可以建立组合聚簇；如果一个关系的一组属性经常出现在相等比较条件中，则该单个关系可建立聚簇；如果一个关系的一个(或一组)属性上的值重复率很高，则此单个关系可建立聚簇。即对应每个聚簇码值的平均元组数不太少。太少了，聚簇的效果不明显。 (2)检查候选聚簇中的关系，取消其中不必要的关系从独立聚簇中删除经常进行全表扫描的关系；从独立／组合聚簇中删除更新操作远多于查询操作的关系；从独立／组合聚簇中删除重复出现的关系当一个关系同时加入多个聚簇时，必须从这多个聚簇方案(包括不建立聚簇)中选择一个较优的，即在这个聚簇上运行各种事务的总代价最小。·选择HASH存取方法的规则当一个关系满足下列两个条件时，可以选择HASH存取方法该关系的属性主要出现在等值连接条件中或主要出现在相等比较选择条件中该关系的大小可预知，而且不变；或该关系的大小动态改变，但所选用的DBMS提供了动态HASH存取方法。·确定数据库物理结构的内容影响数据存放位置和存储结构的因素·硬件环境·应用需求存取时间存储空间利用率维护代价这三个方面常常是相互矛盾的例：消除一切冗余数据虽能够节约存储空间和减少维护代价，但往往会导致检索代价的增加。必须进行权衡，选择一个折中方案。·基本原则根据应用情况将易变部分与稳定部分存取频率较高部分与存取频率较低部分分开存放，以提高系统性能·DBMS产品一般都提供了一些存储分配参数同时使用数据库的用户数同时打开的数据库对象数度、个数时间片大小数据库的大小装填因子锁的数目等等·评价内容对数据库物理设计过程中产生的多种方案进行细致的评价，从中选择一个较优的方案作为数据库的物理结构·评价方法·定量估算各种方案存储空间存取时间维护代价·对估算结果进行权衡、比较，选择出一个较优的合理的物理结构·如果该结构不符合用户需求，则需要修改设计·数据库实施的工作内容用DDL定义数据库结构组织数据入库编制与调试应用程序数据库试运行第二部分考点试题解析该系统所涉及的数据存在如下约束：A．一个出版社可以出版多种图书，但一种图书只能在一个出版社出版，在该系统记录的图书出版社信息中包括图书、出版时间、版次及出版数量信息。B．一个书店可以出售同种图书的多本给多个读者，每位读者可以从多个书店购买同种图书的多本，一种图书可以通过多个书店出售多本给同一读者，书店把图书出售给读者后会在系统中记录售书C．一个城市可以有多个书店，但是一个书店只在一个城市有一家店。问题如下：1)请根据以上信息用ER图画出合理的图书销售数据库的概念模型(4分)2)以图书销售表为例说明原数据库表设计的不合理之处。(6分)3)请给出你改进原数据库设计后的图书销售的数据字典(8分)4)给出该数据库符合3NF要求的全部关系模式，并指出关系模式中的全部主码和外码。(6分)5)在第4)步的基础上，现按“图书名称”和“出版数量”进行查询，为提高查询效率，需要建立索引。给出创建索引的两种方法(2分)。选择较合理的一种方法写出其SQL语句(4分)第3讲数据库设计综合考题2．【2012广东工业大学】请为一个局部应用设计一个数据库，它将保存每个部门及其职工的基本一个部门有多个职工，每个部门都有一个部门经理。其中，职工的基本信息包括：职工工号(ENO)、姓名(ENAME)、年龄(AGE)、工资(SALARY)和工作部门(DPT)；部门的基本信息包括：部门编号 (DNO)、部门名称(DNAME)等。n换为杜丽的关系模式)，并指出每个关系的主键和外键(如果存在的情况下)。3．根据上述第1题中的基本关系表完成下述各题。 ARY。 (2)写出以下查询的关系代数表达式和SQL语句：部门编号、部门名称、经理工号、经理姓名和经理工资。4．关系数据库设计(20分)【2011青岛大学】某学校教学单位分院、系两级管理，课程由学院统一设置，学生以系(在实际中对应于专业)为单位进行管理。现欲开发一教学管理系统，分析得出，该系统由两个子系统构成：课程设置子系统和选课管理子系统。对于课程设置子系统，有如下实体：只允许一个学院开设，学院所开设的每门课都要指定开课学期；一个教师可讲授多门课程，一门课程可由多个教师讲授(注：课程与任课教师可以分属于不同学院)，教师讲授的每门课程都有个评价。对于选课管理子系统，有如下实体：多个学生选修，学生选修的每门课程都有个成绩。试完成如下工作： (1)分别设计课程设置和选课管理两个子系统的局部E－R图。(8分) (2)将上述设计完成的E－R图合并成一个全局E－R图。要求：学院和系两类实体合并为“单位”实体，同时显式表达学院和系之间的隶属关系(注：每个学院下设多个系)。(6分) (3)将该全局E－R图转换为关系模型表示的数据库逻辑结构，并分别使用直下划线和波浪下划线标明每个关系的主码(或主键)与外码(或外键)。(6分) (a)可通过数据库中保存的出版社名、地址、右边和电话等信息，向有关图书的出版社增购书籍。出版社名可唯一标识每个出版社； (b)可随时查询书库中现有各种图书的书号、书名、库存数量和存放位置。所有每种图书可由书号唯一标识； (c)可随时查询借书人的可随时查询借书人的借书证号、姓名和工作部门。借书证号可唯一标识每个借书人。其中一个出版社可出版多种图书，同一图书只能由同一个出版社在某一具体的时间出版一定数量的图书(即出版时间和出版数量)：任何借书人可同时借多种图书，任何一种图书可为多个人所借，在每次借还书时要求登记借书日期和还书日期。根据以上情况，可补充字段类型等适当信息，作如下设计： (1)构造该系统的E－R图(要求用字母或数字标识实体间联系的类型，用下划线标识实体的主关键字)； (2)将E－R模型图转换为等价的关系模型的关系模式(要求用下划线标识实体的主关键字)； (3)用SQL语言定义上述关系模式，要求定义每个模式的主关键字和参照完整性。8．商场(商场名、经理名)有如下信息：一个商场内有许多柜台(柜台号，柜台名)，每个柜台有多种商品(商品号，价格)；每个柜台有多个营业员(工号，姓名，性别)；每个营业员卖出许多种商品，一种商品也可被多位营业员卖出。画出该系统的E－R模型；转化为关系模型；说明转化方法；标出各关系中的关键字；如果存在外码，标出外码。(15分)【2008湖北工业大学】试画出用关系代数表示的语法数。再用关系代数表达式优化算法对该语法树进行优化处理，画出优化后的语法树，根据优化后的语法树写出SELECT语句。(10分)第九章关系查询处理和查询优化第一部分知识点回顾关系系统的分类系数据库系统的查询处理查询处理步骤·对查询语句进行扫描、词法分析和语法分析·从查询语句中识别出语言符号·进行语法检查和语法分析·根据数据字典对合法的查询语句进行语义检查·根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查·检查通过后把SQL查询语句转换成等价的关系代数表达式·RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式·把数据库对象的外部名称转换为内部表示·查询优化：选择一个高效执行的查询处理策略·查询优化分类：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择·查询优化方法选择的依据：·依据优化器得到的执行策略生成查询计划·代码生成器(codegenerator)生成执行查询计划的代码考虑＜条件表达式＞的几种情况：·选择操作典型实现方法： (1)简单的全表扫描方法 (2)索引(或散列)扫描方法适合选择条件中的属性上有索引(例如B＋树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组过元组指针在student表中检索到该学生有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。指针·求这2组指针的交集dent·得到计算机系年龄大于20的学生·通过这些元组指针到student表中检索·对得到的元组检查另一些选择条件(如Sage＞20)是否满足·把满足条件的元组作为结果输出。·连接操作是查询处理中最耗时的操作之一·本节只讨论等值连接(或自然连接)最常用的实现算法 ·对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc)·检查这两个元组在连接属性(sno)上是否相等·如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止 ·适合连接的诸表已经排好序的情况·排序－合并连接方法的步骤：排序－合并连接方法示意图 (3)索引连接(indexjoin)方法·步骤： ·步骤：对包含较少元组的表(比如R)进行一遍处理对另一个表(S)进行一遍处理把元组与桶中所有来自R并与之相匹配的元组连接起来系数据库系统的查询优化·查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。 (1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 (2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 (3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。·RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案集中式数据库执行开销主要包括： (1)磁盘存取块数(I／O代价) (2)处理机时间(CPU代价) (3)查询的内存开销分布式数据库·查询优化的总目标：选择有效的策略求得给定关系表达式的值使得查询代价最小(实际上是较小)实际系统的查询优化步骤 (1)将查询转换成某种内部表示，通常是语法树 (2)根据一定的等价变换规则把语法树转换成标准(优化)形式 (3)选择低层的操作算法对于语法树中的每一个操作·计算各种执行算法的执行代价·选择代价小的执行算法 (4)生成查询计划(查询执行方案)·查询计划是由一系列内部操作组成的。·代数优化策略：通过对关系代数表达式的等价变换来提高查询效率·关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的EE可记为E1=E2常用的等价变换规则： (1)连接、笛卡尔积交换律 (2)连接、笛卡尔积的结合律 (3)投影的串接定律E (4)选择的串接定律σF1(σF2(E))=σF1∧F2(E)选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。 (5)选择与投影操作的交换律FAAAnEA1，A2，…An(σF(E)) (6)选择与笛卡尔积的交换律如果F中涉及的属性都是E1中的属性，则σF(E1×E2)=σF(E1)×E2σF(E1×E2)=σF1(E1)×σF2(E2)σF(E1×E2)=σF2(σF1(E1)×E2)它使部分选择在笛卡尔积前先做。 (7)选择与并的分配律 (8)选择与差运算的分配律EEFEEFE－σF(E2) (9)选择对自然连接的分配律σF(E1E2)=σF(E1)σF(E2) (10)投影与笛卡尔积的分配律 (11)投影与并的分配律典型的启发式规则：1．选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条2．把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系3．把投影同其前或其后的双目运算结合起来4．把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算·如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的·当查询的是视图时，定义视图的表达式就是公共子表达式的情况·遵循这些启发式规则，应用9．3．1的等价变换公式来优化关系表达式的算法。达式的优化输入：一个关系表达式的查询树方法： (1)利用等价变换规则4把形如σF1∧F2∧…∧Fn(E)变换为σF1(σF2(…(σFn(E))…))。 (2)对每一个选择，利用等价变换规则4~9尽可能把它移到树的叶端。 注意：·等价变换规则3使一些投影消失·规则5把一个投影分裂为两个，其中一个有可能被移向树的叶端 (4)利用等价变换规则3~5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成 (5)把上述得到的语法树的内节点分组。每一双目运算(×，，∪，－)和它所有的直接祖先为一组(这些直接祖先是(σ，π运算)。·如果其后代直到叶子全是单目运算，则也将它们并入该组·但当双目运算是笛卡尔积(×)，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组，把这些单目运算单独分为一组【例4】下面给出[例3]中SQL语句的代数优化示例。 (1)把SQL语句转换成查询树，如下图所示查询树 (2)对查询树进行优化o·代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径·对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的·物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划第二部分考点试题解析1．学生-课程数据库中包含了三个表。求选修了2号课程的学生姓名。假定学生-课程数据库中有1000个学生记录，10000个选课记录，其中选修2号课程的选修记录为50个。系统可以用多种等价的关系代数表达式来完成这一查询。1)给出用关系代数表示的上述查询三个查询表达式。(6分)2)给出查询优化的一般准则。(6分)3)画出最优的标准语法树。(8分)2．学生—课程数据库中包含了三个表。(9分)此查询要求信息系学生选修了的所有课程名称。1)试画出用关系代数表示的语法树(3分)2)用关系代数表达式优化算法对原始语法树进行优化，画出优化后的标准语法树。(6分)【2006第十章数据库恢复技术第一部分知识点回顾·定义一个数据库操作序列一个不可分割的工作单位恢复和并发控制的基本单位·事务和程序比较在关系数据库中，一个事务可以是一条或多条SQL语句，也可以包含一个或多个程序。一个程序通常包含多个事务 (1)原子性：·事务是数据库的逻辑工作单位事务中包括的诸操作要么都做，要么都不做 (2)一致性：·事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态一致性状态：若数据库中只包含成功事务提交的结果不一致状态：若数据库中包含失败事务的结果 (3)隔离性对并发执行而言：一个事务的执行不能被其他事务干扰·一个事务内部的操作及使用的数据对其他并发事务是隔离的·并发执行的各个事务之间不能互相干扰 (4)持续性·一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。·接下来的其他操作或故障不应该对其执行结果有任何影响。·破坏事务ACID特性的因素多个事务并行运行时，不同事务的操作交叉执行事务在运行过程中被强行停止·故障是不可避免的·数据库的恢复把数据库从错误状态恢复到某一已知的正确状态(亦称为一致状态或完整状态)·故障的影响运行事务非正常中断破坏数据库·数据库管理系统对故障的对策DBMS保证故障发生后，能把数据库中的数据从错误状态恢复到某种逻辑一致的状态保证事务ACID·恢复技术是衡量系统优劣的重要指标