数据库原理及应用教案市公开课一等奖百校联赛特等奖课件.pptx

数据库原理及应用教案数据库原理及应用教案河北化工医药职业技术学院河北化工医药职业技术学院第1页 第2章 关系数据库n2.1 关系数据库与关系模型n2.2 关系形式定义n2.3 关系运算代数n2.4 查询优化n2.5 关系数据库规范化理论第2页 2.1关系数据库与关系模型2.1.1 基本概念n1关系数据库系统n关系数据库系统是支持关系数据模型数据库系统。关系数据库应用数学方法来处理数据库中数据。n关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。n关系数据库管理系统RDBMS如著名IBM DB2，Oracle，Ingres，SYBASE，Informix等。第3页2关系相关名词n域：域：域是一组含有相同数据类型值集合。n普通在关系数据模型中，对域还加了一个限制，全部域都应是原子数据（atomic data）。n目或度（Degree）：设相关系R(D1，D2，Dn)，这里R表示关系名字，n是关系目或度。n属性属性：在现实世界中，要描述一个事物经常取若干特征来表示。这些特征称为属性（attribute）。n目关系必有n个属性。第4页2关系相关名词n候选码（Candidate Key）：若关系中某一属性或属性组值能唯一标识一个元组，则称该属性或属性组为候选码。n主码（Primary Key）：若一个关系有多个候选码，则选定其中一个为主码。n主属性（Non-Key attribute）：主码诸属性称为主属性。不包含在任何候选码中属性称为非码属性。据(Data)是数据库中存放基本对象第5页2关系相关名词n外码（Foreign key）：假如关系模式 R中属性或属性组非该关系码，但它是其它关系码，那么该属性集对关系模式 R而言是外码。n比如，客户与贷款之间借贷联络c-l（c-id，loan-no），属性 c-id 是客户关系中码，所以c-id是外码；属性loan-no是贷款关系中码，所以loan-no也是外码。第6页2关系相关名词n全码（All-key）：关系模型全部属性组是这个关系模式候选码，称为全码。n比如，关系模式R（T，C，S），属性T表示教师，属性 C表示课程，属性 S表示学生。假设一个教师能够讲授多门课程，某门课程能够由多个教师讲授，学生能够听不一样教师讲授不一样课程，那么，要想区分关系中每一个元组，这个关系模式R码应为全属性T、C和S，即All-key。第7页3关系三种类型n基本关系（通常又称为基本表或基表）：是实际存在表，它是实际存放数据逻辑表示。n查询表：查询结果对应表。n视图表：是由基本表或其它视图表导出表。因为它本身不独立存放在数据库中，数据库中只存放它定义，所以常称为虚表。第8页 2.1.2 关系模型n1关系模型三要素 关系数据模型由关系数据结构、关系操作集合和关系完整性约束三大要素组成。n(1)关系数据结构n关系模型数据结构单一，在关系模型中，现实世界实体以及实体间各种联络均用关系来表示，在用户看来，关系模型中数据逻辑结构是一张二维表。第9页1关系模型三要素n(2)关系操作集合n关系操作特点是集合操作方式，即操作对象和结果都是集合。这种操作方式也称为一次一个集合方式。对应地，非关系数据模型数据操作方式则为一次一个统计方式。n关系模型中惯用关系操作包含：选择(select)、投影(Project)、连接(join)、除(divide)、并(union)、交(intersection)、差(differencc)等，以及查询(query)操作和增(insert)、删(delete)、改(update)操作两大部分。查询表示能力是其中最主要部分。第10页(2)关系操作集合n关系操作能力可用两种方式来表示：代数方式和逻辑方式。n关系代数是用对关系运算来表示查询要求方式。n关系演算是用谓词来表示查询要求方式。关系演算又可按谓词变元基本对象是元组变量还是域变量分为元组关系演算和域关系演算。对于关系代数、元组关系演算和域关系演算均是抽象查询语言，在表示能力上是完全等价。第11页1关系模型三要素n(3)关系完整性约束n数据库数据完整性是指数据库中数据正确性和相容性，是一个语义概念，包含两个方面：n与现实世界中应用需求数据相容性和正确性。n数据库内数据之间相容性和正确性。n比如，学生学号必须惟一，性别只能是男或女，学生所选修课程必须是已开设课程，等等。n数据库中数据是否具备完整性关系到数据库系统能否真实地反应现实世界，所以，数据库完整性是十分主要。第12页(3)关系完整性约束n数据完整性由完整性规则来定义，关系模型完整性规则是对关系某种约束条件。关系模型中能够有3类完整性约束:实体完整性、参考完整性和用户定义完整性。n实体完整性和参考完整性是关系模型必须满足完整性约束条件，应该由关系系统自动支持。n用户定义完整性是应用领域需要遵照约束条件，表达了详细领域中语义约束，普通由关系系统提供编写伎俩、由 DBMS完整性检验机制负责检验。第13页2关系模式n定义2.1 关系描述称为关系模式。能够形式化表示为 R（U，D，dom，F）n其中，R表示关系名；U是组成该关系属性名集合；D是属性域；dom是属性向域映象集合；F为属性间数据依赖关系集合。第14页2关系模式n通常将关系模式简记为：R（U）或R(A1，A2，A3，An)n其中 R为关系名，A1，A2，A3，An为属性名或域名，属性向域映象经常直接说明属性类型、长度。通常在关系模式主属性上加下划线表示该属性为主码属性。第15页举例n【例2.1】学生关系 S有学号Sno、学生姓名Same、性别Sex、系名SD、年纪Age属性；课程关系 C有课程号Cno、课程名Cname、先修课程号PCno属性；学生选课关系SC有学号Sno、课程号 Cno、成绩Grade属性。写出这三个关系模式。第16页举例n解：n(1)学生关系模式S（Sno，Sname，Sex，SD，Age）n(2)课程关系模式C（Cno，Cname，PCno）Dom（PCno）=Cno。n(3)学生选课关系模式SC（Sno，Cno，Grade）。SC关系中Sno、Cno又分别为外码。因为它们分别是S、C关系中主码。第17页2.1.3关系三类完整性规则n关系模型完整性规则是对关系某种约束条件。关系完整性共分为三类：n实体完整性n参考完整性（也称引用完整性）n用户定义完整性。第18页1实体完整性（Entity Integrity）n【规则2.1】若属性A是关系R主属性，则属性A不能取空值。n比如：关系学生(学号，姓名，性别，专业号，年纪)中，主码为“学号”，则“学号”不能取空值。在关系选修(学号，课程号，成绩)中，“学号、课程号”为主码，则“学号”和“课程号”两个属性都不能取空值。第19页2参考完整性（Referential Integrity）n在关系模型中实体及实体间联络是用关系来描述，这么自然就存在着关系与关系间引用。n比如，员工和部门关系模式表示以下：n员工（员工号，姓名，性别，参加工作时间，部门号）n部门（部门号，名称，电话，责任人）n这两个关系存在着属性引用，即员工关系中“部门号”值必须是确实存在部门部门号，即部门关系中有该部门统计。也就是说，员工关系中“部门号”属性取值要参考部门关系“部门号”属性取值。第20页2参考完整性（Referential Integrity）n【规则2.2】若F是基本关系 R外码，它与基本关系S主码Ks相对应（基本关系R和S不一定是不一样关系）则对于 R中每个元组在F上值必须为：n(1)或者取空值（F每个属性值均为空值）n(2)或者等于S中某个元组主码值。第21页3.用户定义完整性（User defined Integrity）n实体完整性规则定义了对关系中主属性取值约束，即对主属性值域约束；n参考完整性规则定义了参考关系和被参考关系外码与主码之间参考约束，即对参考关系外码属性值域约束，要求外码属性值域只能是空值或是对应被参考关系主码属性值。n用户定义完整性就是针对某详细应用要求来定义约束条件，它反应某一详细应用所包括数据必须满足语义要求。第22页n比如，某个属性必须取惟一值，一些属性值之间应满足一定函数关系，某个属性取值范围在0100 之间等。用户定义完整性通常是定义对关系中除主码与外码属性之外其它属性取值约束，即对其它属性值域约束。n对属性值域约束也称为域完整性约束，是指对关系中属性取值正确性限制，包含数据类型、精度、取值范围、是否允许空值等。3.用户定义完整性（User defined Integrity）第23页22关系形式定义2.2.1 关系形式定义n1笛卡尔积数据定义n定义2.2 设 为任意集合，定义 笛卡儿积为：第24页22关系形式定义n其中每一个元素 叫做一个 n 元组（n-tuple属性个数），元组每一个值 叫做元组一个分量，若 为有限集，其基数（Cardinal number元组个数）为 ，则 基数为：。笛卡儿积能够用二维表来表示。第25页举例【例2.2】若 求：n解:依据定义，笛卡尔积中每一个元素应该是一个三元组，每个分量来自不一样域，所以结果为:n用二维表表示如图2-1所表示。第26页图2-1 笛卡尔积二维表表示第27页2关系n定义定义2.3 子集叫做在域 上关系，记为 ，称关系R为n元关系。n从定义2.3能够得出一个关系也能够用二维表来表示。关系中属性个数称为“元组”，元组个数称为“基数”。关系模型中术语与普通术语对应情况能够经过图2-2中学生关系说明。第28页第29页2.2.2 关系模型优点n1关系性质n(1)列是同质，即每一列中分量均是同一类型数据，即均来自同一个域。n(2)不一样列能够出自同一个域，每一列称为一个属性；属性不能重名。n(3)列次序是无关，即列次序能够变换。但次序一旦固定，就不再改变，不能造成冲突发生。n(4)任意两个元组不能完全相同。n(5)行次序是无关，即行次序能够交换。n(6)每一分量必须是不可分数据项。第30页2关系模型优点n(1)关系模型使关系数据库研究含有坚实理论基础，这一理论有利于关系数据库设计和用户对数据库信息需求有效处理。n(2)关系模型逻辑结构与对应操作完全独立于数据存放方式，含有高度数据独立性，使得用户无须关心物理存放细节。第31页2关系模型优点n(3)关系模型提供单一数据结构形式，含有高度简明性和准确性，用户很轻易掌握和利用基于关系模型数据库系统。n(4)关系数据库语言与一阶谓词逻辑固有内在联络，使得以关系数据库为基础推理系统和知识库系统研究提供了良好基础。第32页2.2.3 E-R模型向关系模型转换n从 E-R模型向关系模型转换时，全部实体和联络都要转换成对应关系模式，转换规则为：n(1)每个实体类型转换成一个关系模式；n(2)一个1:1联络可转换为一个关系模式，或与任意一端关系模式合并，若独立转换为一个关系模式，那么，两端关系码及联络属性为该关系属性；若与一端合并，那么将另一端码及联络属性合并到该端。第33页2.2.3 E-R模型向关系模型转换n(3)一个1:n联络可转换为一个关系模式，或与 n端关系模式合并。若独立转换为一个关系模式，那么，两端关系码及联络属性为关系属性，而n端码为关系码。n(4)一个n:m联络可转换为一个关系模式，那么，两端关系码及联络属性为关系属性，而关系码为两端实体码组合。第34页2.2.3 E-R模型向关系模型转换n(5)三个或三个以上多对多联络可转换为一个关系模式，那么，诸关系码及联络属性为关系属性，而关系码为各实体码组合。n(6)含有相同码关系能够合并。第35页举例S SC CCLASSCLASSSCSCm mn nCTCTn n1 1SnoSnoSnameSnameSageSageSexSexSDSDGradeGradeCnoCnoCnameCnamePcnoPcnoDateDateCLnoCLnoCLnameCLnameTelTel【例2.3】将图2-3E-R图转换成关系模式。图2-3 学生班级课程E-R图第36页举例n从图中能够看出有3个实体:学生 S、课程 C、班级CLASS，依据转换规则转换成3个关系模式。联络CT是一个1:n类型，依据转换规则可将CLASS码CLno，加上联络属性Date并入n端。联络 SC是一个 n:m 类型，依据转换规则转换成一个独立关系模式，所以将S码Sno和C码Cno，加上联络属性 Grade作为关系 SC属性，该关系码是Sno和Cno。第37页举例n依据上述分析转换关系模式以下：nS(Sno，Sname，SD，Sage，Sex，CLno，Date)nC(Cno，Cname，Pcno)nCLASS(CLno，CLname，Tel)第38页23 关系运算2.3.1关系代数五种基本运算n关系代数运算符有四类：n集合运算符n专门关系运算符n算术比较符n逻辑运算符n依据运算符不一样，关系代数运算可分为n传统集合运算n专门关系运算第39页23 关系运算n传统集合运算是从关系水平方向进行，包含：并、交、差及广义笛卡尔积。n专门关系运算既能够从关系水平方向进行运算，又能够向关系垂直方向运算，包含：选择、投影、连接以及除法。如表 2-1所表示。第40页表2-1第41页1.并（Union）n关系R与S含有相同关系模式，即 R与S元数相同（结构相同）。关系 R与S并由属于R或属于S元组组成集合组成，记作 ，其形式定义以下：n式中t 为元组变量。第42页2.差（Difference）n关系R与S含有相同关系模式，关系R与S差由属于R但不属于S元组组成集合，记作 ，其形式定义以下：第43页3.广义笛卡尔积（Extended Cartesian Product）n 两个元数分别为n目和m目标关系R 和S 广义笛卡尔积是一个（n+m）列元组集合。元组前n列是关系R一个元组，后m列是关系S一个元组。记作 ，其形式定义以下：n假如R和S中有相同属性名，可在属性名前加关系名作为限定。若R 有K1个元组，S 有K2个元组。则R和S广义笛卡尔积有个 元组。第44页4.投影（Projection）n投影运算是从关系垂直方向进行运算，在关系R中选择出若干属性列A组成新关系，记作 ，其形式定义以下：第45页5.选择（Selection）n 选择运算是从关系水平方向进行运算，是从关系R中选择满足给定条件诸元组，记作 ，其形式定义以下：n其中，F中运算对象是属性名(或列序号)或常数，运算符算术比较府（，=，)和逻辑运算符(，)。第46页5.选择（Selection）n比如，表示选取R关系中第一个属性值大于等于第六个属性值元组；表示选取R关系中第一个属性值大于等于“6”元组。第47页举例【例2.4】设相关系R、S如图2-4所表示，请求出：第48页举例n解解:结果如图2-5所表示。其中，后生成关系属性名有重复，按照关系“属性不能重名”性质，通常采取“关系名.属性名”格式。对于 含义是 后“选取第三个属性值小于第四个属性值”元组。因为 第三个属性为R.C，第四个属性是S.A，所以 含义也是 后“选取R.C值小于S.A值”元组。第49页图2-5 运算结果第50页2.3.2关系代数组合运算n扩展关系运算能够从基本关系运算中导出。主要包含：选择、投影、连接、除法、广义笛卡尔积、外联接。第51页1.交（Intersection）n关系R与S含有相同关系模式，关系R与S交由属于R同时又属于S元组组成集合，关系R与S交记作 ，其形式定义以下：n显然，或者第52页2.连接（Join）n连接分为：n连接n等值连接n自然连接n连接运算是从两个关系R和S笛卡尔积中选取满足条件元组。笛卡尔积是无条件连接，其它连接 操作认为是有条件连接。下面分述以下。第53页2.连接（Join）n(1)连接：从R与S笛卡尔积中选取属性间满足一定条件元组。记作：n其中:“”为连接条件，是比较运算符，X和Y分别为R和S上度数相等且可比属性组。表示R中 元组对应属性X一个分量。表示S中 元组对应属性Y一个分量。第54页(1)连接：n需要说明是:连接也能够表示为：n其中:i=1，2，3，n，j=1，2，3，m。“”含义为从两个关系R和S中选取R第i列和S第j列之间满足运算元组进行连接。n连接能够由基本关系运算笛卡儿积和选取运算导出，所以可表示为:或 第55页举例【例2.5】设相关系R，S如图2-4所表示，求：。n解:本题连接条件为R.AS.B，意为将R关系中属性A值小于S关系中属性B值元组取出来作为结果集元组。结果集为 后选出满足条件元组，而且结果集属性为R.A，R.B，R.C，S.A，S.B，S.C。结果如图2-6所表示。图2-6 第56页2.连接（Join）n(2)等值连接：当为“=”时,称之为等值连接,记为 ,其形式定义以下:第57页2.连接（Join）n(3)自然连接:是一个特殊等值连接，它要求两个关系中进行比较分量必须是相同属性组，而且在结果中将重复属性列去掉。记为 ，其形式定义以下:第58页（3）自然连接n自然连接能够由基本关系运算投影、选取和笛卡儿积导出。n注意注意：普通连接是从关系水平方向运算，而自然连接不但要从关系水平方向，而且要从关系垂直方向运算。因为自然连接要去掉重复属性，假如没有重复属性，那麽自然连接就转化为笛卡儿积。第59页举例：【例2.6】设相关系如图2-7所表示,求：。第60页举例：n解：本题要求 R与 S自然连接，自然连接是一个特殊等值连接，它要求两个关系中进行比较分量必须是相同属性组，而且在结果中将重复属性列去掉。本题 R与 S关系中相同属性组为AC，所以，结果集中属性列应为ABCD。其结果如图2-8所表示。第61页3.除（Division）n除运算是同时从关系水平方向和垂直方向进行运算。给定关系 R(X，Y)和S(Y，Z)，X，Y，Z为属性组。应该满足元组在X上分量值x象集Yx包含关系S在属性组Y上投影集合。其形式定义以下：n其中:Yx为x在R中象集，x=，且 结果集属性组为X。第62页举例n【例2.7】设相关系R、S如图2-9（a）（b）所表示，求：。第63页举例n解:n依据除法定义，此题X为属性AB，Y为属性CD。应该满足元组在属性AB上分量值x象集Yx包含关系S在CD上投影集合。第64页举例n关系S在Y上投影为 =(c，d)，(e，f)。对于关系R，属性组X(即AB)能够取3个值(a，b)，(b，d)，(c，k)，它们象集分别以下:n象集CD(a，b)=(c，d)，(e，f)，(h，k)n象集CD(b，d)=(e，f)，(d，l)n象集CD(c，k)=(c，d)，(e，f)n因为上述象集包含 有(a，b)和(c，k)，所以，n =(a，b)，(c，k)，结果如图2-9(c)所表示。第65页2.3.3关系代数外连接运算n外连接运算是连接运算扩展，能够处理缺失信息。对于图2-10S和 SC关系，对其进行自然连接时，结果如图2-11所表示。第66页2.3.3关系代数外连接运算第67页第68页2.3.3关系代数外连接运算n由图2-11能够看出 S与SC自然连接结果丢失了拂晓、刘明远、赵国庆相关信息。使用外连接能够防止这么信息丢失。外连接运算有3种：n左外连接n右外连接n全外连接第69页2.3.3关系代数外连接运算n1)左外连接(left outer join)n取出左侧关系中全部与右侧关系中任一元组都不匹配元组，用空值null 填充全部来自右侧关系属性，组成新元组，将其加入自然连接结果中。对于图 2-10S和SC关系，对其进行左外连接S SC时，结果如图2-12所表示。第70页 图2-12 S SC第71页2.3.3关系代数外连接运算n2)右外连接(right outer join)n取出右侧关系中全部与左侧关系中任一元组都不匹配元组，用空值null填充全部来自左侧关系属性，组成新元组，将其加入自然连接结果中。对于图 2-10S和SC关系，对其进行左外连接S SC时，结果如图2-13所表示。第72页 图2-13 S SC第73页2.3.3关系代数外连接运算n3)全外连接(right outer join)n填充左侧关系中全部与右侧关系中任一元组都不匹配元组，又填充右侧关系中全部与左侧关系中任一元组都不匹配元组，将产生新元组加入自然连接结果中。第74页 2.3.4关系代数运算举例n【例2.8】设学生课程数据库中有：学生S、课程C、学生选课SC三个关系，如图 2-14 所表示。请用关系代数表示式表示以下检索问题。n（1）检索选修课程名为“数学”学生号和学生姓名。n（2）检索最少选修了课程号为“1”和“3”学生号。n（3）检索选修了“操作系统”或“数据库”课程学号和成绩。n（4）检索年纪在 18到 20之间（含18和20）女生学号、姓名及年纪。n（5）检索选修全部课程学生姓名及所在系。n（6）检索选修课程包含“1042”学生所学课程学生学号。第75页 图2-14 S，C SC关系第76页24查询优化2.4.1关系代数表示式优化问题n查询处理：是指从数据库中提取数据一系列活动。这一系列活动包含：将高级数据库语言表示查询语句翻译成为能在文件系统这一物理层次上实现表示式，为优化查询进行各种转换，以及查询实际执行。第77页24查询优化n查询处理代价：通常取决于磁盘访问，磁盘访问比内存访问速度要慢。对于一个给定查询，能够有许多可能处理策略，复杂查询更是如此。就所需磁盘访问次数而言，策略好坏差异很大，有时甚至相差几个数量级。所以，系统多花一点时间选择一个很好查询策略是很值得。第78页2.4.1关系代数表示式优化问题n查询优化：是为了查询选择最有效查询计划过程。查询优化一方面是在关系代数级进行优化，要做是力图找出与给定表达式等价，但执行效率更高一个表达式。查询优化其次涉及查询语句处理详细策略选择，例如选择执行运算所采用具体算法以及将使用特定索引等等。第79页2.4.2关系代数表示式等价变换规则n1优化准则n(1)提早执行选取运算。对于有选择运算表示式，应优化成尽可能先执行选择运算等价表示式，以得到较小中间结果，降低运算量和从外存读块次数。n(2)合并乘积与其后选择运算为连接运算。在表示式中，当乘积运算后是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以防止做完乘积后，需再扫描一个大乘积关系进行选择运算。第80页1优化准则n(3)将投影运算与其后其它运算同时进行，以防止重复扫描关系。n(4)将投影运算和其前后二目运算结合起来，使得没有必要为去掉一些字段再扫描一遍关系。第81页1优化准则n(5)在执行连接前对关系适当地预处理，就能快速地找到要连接元组。方法有两种：索引连接法、排序合并连接法。n(6)存放公共子表示式。对于有公共子表示式结果应存于外存（中间结果），这么，当从外存读出它时间比计算时间少时，就可节约操作时间。第82页2.关系代数表示式等价变换规则n优化策略均包括关系代数表示式，所以讨论关系代数表示式等价变换规则显得十分主要。惯用等价变换规则有以下10种：n（1）连接、笛卡尔积交换率n设E1和E2是关系代数表示式，F是连接运算条件，则有第83页2.关系代数表示式等价变换规则n（2）连接、笛卡尔积结合率n设E1，E2，E3是关系代数表示式，F1，F2是连接运算条件，则有第84页2.关系代数表示式等价变换规则n（3）投影串接定律n设E是关系代数表示式，A1，An和B1，Bm，且B1，Bm是A1，An子集，则有n该规则目标是使一些投影消失。第85页2.关系代数表示式等价变换规则n（4）选择串接定律n设E是关系代数表示式，F1，F2是选取条件表示式，选择串接定律说明选择条件能够合并，则有第86页2.关系代数表示式等价变换规则n（5）选择与投影交换律n设E是关系代数表示式，F是选取条件表示式，而且只包括A1，An属性，则有第87页2关系代数表示式等价变换规则n（6）选择与笛卡尔积交换律n若F包括都是E1中属性，则n假如F=F1F2，而且F1只包括中E1属性，F2只包括E2中属性，则有第88页2关系代数表示式等价变换规则n（7）选择与并交换律n设E=E1E2，E1，E2有相同属性，则n（8）选择与差交换律n设E1，E2有相同属性，则第89页2关系代数表示式等价变换规则n（9）投影与笛卡尔积交换律n设E1，E2是两个关系代数表示式，A1，An是E1中属性，B1，Bm是E2中属性，则n（10）投影与并交换律n设E1，E2有相同属性，则第90页2.4.3关系代数表示式优化算法n算法：关系代数表示式优化n输入：一个关系代数表示式语法树n输出：计算该表示式程序。第91页n方法：n（1）利用规则4将形如 变换为：n（2）对每一选择，用规则48尽可能将它移到树叶端。n（3）对每一个投影，利用规则3、9，10，5中普通形式尽可能将它移到树叶端。2.4.3关系代数表示式优化算法第92页n（4）利用规则35将选择和投影串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。n（5）将上述得到语法树内节点分组。每一双目运算(，-)和它全部直接祖先为一组（这些直接祖先是，运算）。假如其后代直到叶子全部是单目运算，则将它并入该组。方法：第93页n（6）生成一个程序，每组节点计算是程序中一步。各步次序是任意，只要确保任何一组计算不会在它后代组之前计算。方法：第94页举例n【例2.12】供给商数据库中有：供给商、零件、项目、供给四个基本表（关系）：nS(Sno，Sname，Status，City)nP(Pno，Pname，Color，Weight)nJ(Jno，Jname，City)nSPJ(Sno，Pno，Jno，Qty)第95页举例n用户有一查询语句：检索使用上海供给商生产红色零件工程号。n(1)试写出该查询关系代数表示式；n(2)试写出查询优化关系代数表示式；n(3)画出该查询初始关系代数表示式语法树；n(4)使用优化算法，对语法树进行优化，并画出优化后语法树。第96页举例解:n(1)该查询关系代数表示式以下:n(2)查询优化关系代数表示式以下:n(3)该查询初始关系代数表示式语法树如图2-221所表示。n(4)优化后语法树如图2-22 所表示。第97页图2-21 优化前图2-22 优化后第98页25关系数据库规范化理论n规范化理论研究是关系模式中各属性之间依赖关系及其对关系模式性能影响，提供判断关系模式优劣理论标准，预测可能出现问题，提供自动产生各种模式算法。n关系数据库设计理论关键是数据间函数依赖，衡量标准是关系规范化程度及分解无损连接和保持函数依赖性。第99页2.5.1函数依赖n数据依赖是经过一个关系中属性间值相等是否表达出来数据间相互关系，是现实世界属性间联络和约束抽象，是数据内在性质，是语义表达。函数依赖则是一个最主要、最基本数据依赖。第100页1.函数依赖定义n定义2.4 设R(U)是属性集U上关系模式，X、Y是U子集。若对R(U)任何一个可能关系r，r中不可能存在两个元组在X上属性值相等，而在 Y上属性值不等，则称X函数决定Y或Y函数依赖于X，记作：XY。n注意注意，函数依赖XY定义要求关系模式 R 任何可能r都满足上述条件。所以不能仅考查关系模式 R在某一时刻关系r，就断定某函数依赖成立。第101页举例n比如，关系模式Student(Sno，Sname，SD，Sage，Sex)可能在某时刻，Student关系r中每个学生年纪都不一样，也就是说没有两个元组在Sage属性上取值相同，而在 Sno 属性上取值不一样，但我们决不可据此就断定Sage Sno。很有可能在某一时刻，Student关系 r中有两个元组在Sage属性上取值相同，而在Sno属性上取值不一样。第102页1.函数依赖定义n非平凡函数依赖：假如XY，但 YX，则称XY是非平凡函数依赖。普通情况下总是讨论非平凡函数依赖。n平凡函数依赖：假如XY，但YX，则称XY是平凡函数依赖。第103页1.函数依赖定义n定义2.5 在R(U)中，假如XY，而且对于X任何一个真子集X，都有X不能决定Y，则称Y对X完全函数依赖，记作：。n假如XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：。部分函数依赖也称局部函数依赖。n定义2.6在R(U，F)中，假如XY，YX，Y X，YZ，则称Z对X传递函数依赖。第104页举例【例2.13】n在关系模式SC(Sno，Cno，Grade，Credit)中，n(Sno，Cno)Grade 成绩完全函数依赖于学号和课程号n Cno Credit 学分函数依赖于课程号n(Sno，Cno)Credit 学分部分函数依赖于学号第105页举例n在关系模式 Student(Sno，Sname，SD，Sdname，Sage，Sex)中，nSno Sname，Sno Sagen又因为Sno SD，SD Sno，SD SDname，所以能够得出Sno Sdname，即系名传递依赖于学号。第106页2.码n定义2.7 设K为R(U，F)中属性或属性组合，若K U，且对于K任何一个真子集K，都有K不能决定U，则K为R候选码(Candidate key)，若有多个候选码，则选一个作为主码(Primary key)。候选码通常也称候选关键字。n包含在任何一个候选码中属性叫做主属性(Prime attribute)，不然叫做非主属性(Nonprime attribute)。第107页举例【例2.14】关系模式CSZ(CITY，ST，ZIP)，其属性组上函数依赖集为n F(CITY，ST)ZIP，ZIPCITYn即城市、街道决定邮政编码，邮政编码决定城市。轻易看出，(CITY，ST)和(ST，ZIP)是两个候选码。CITY、ST、ZIP都是主属性。第108页2.码n定义2.8 若R(U，F)中属性或属性组X非R码，但 X 是另一个关系码，则称X是R外码(Foreign key)。n定义2.9 若关系模式 R（U）中，X、Y、Z是U子集，而且 Z=U-X-Y。当且仅当对R（U）任何一个关系r，给定一对（x，z）值，有一组Y值，这组值仅仅决定于x值而与z值无关，则称“Y多值依赖于X”或“X多值决定Y”成立。记为：XY。第109页多值依赖含有以下六条性质：n(1)多值依赖含有对称性。即若XY，则XZ，其中Z=U-X-Y。n(2)多值依赖传递性。即若XY，YZ，则XZ-Y。n(3)函数依赖能够看成是多值依赖特殊情况。n(4)若XY，XZ，则XYZ。n(5)若XY，XZ，则XY Z。n(6)若XY，XZ，则XZ-Y。第110页3.逻辑蕴涵与Armstrong公理系统n定义2.10 设R(U，F)是一个关系模式，X、Y是U中属性组，若在R(U，F)任何一个满足F中函数依赖关系r上，都有函数依赖XY成立，则称F逻辑蕴含XY。n在关系模式 R(U，F)中为F所逻辑蕴含函数依赖全体称做F闭包，记做 。第111页3.逻辑蕴涵与Armstrong公理系统n比如，关系模式Student(Sno，Sname，Age，SD，SDname)，其属性组上函数依赖集为FSnoSname，SnoSage，SnoSD，SDSDname，SnoSDname就是F所逻辑蕴含一个函数依赖。第112页3.逻辑蕴涵与Armstrong公理系统 函数依赖公理系统（Armstrong公理系统）:关系模式R 来说有以下推理规则：nAl.自反律（Reflexivity）：若Y X U，则X Y为F所蕴含。nA2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。nA3.传递律（Transitivity）：若XY及YZ为F 所蕴含，则XZ为F所蕴含。注意：由自反律所得到函数依赖均是平凡函数依赖，自反律使用并不依赖于F第113页举例【例2.15】利用 Armstrong公理系统推理规则，对于【例2.14】关系模式CSZ已知条件，证实(ST，ZIP)(CITY，ST，ZIP)。第114页举例n证实:依据题意不难看出只要证实(ST，ZIP)是一个候选码即可，证实步骤以下:n 因为ZIPCITY (F中已给出)n 所以(ST，ZIP)(CITY，ST)(利用增广率，即在函数依赖两端加ST)n (ST，ZIP)(CITY，ST，ZIP)(用增广率，加ZIP)第115页举例n严格地说，要证实(ST，ZIP)是候选码，还需要说明 ST(CITY，ST，ZIP)和ZIP(CITY，ST，ZIP)都不在 。第116页3.逻辑蕴涵与Armstrong公理系统n依据上述三条推理规则又可推出下述三条推理规则：n合并规则：由XY，XZ，有XYZ。（A2，A3）n伪传递规则：由XY，WYZ，有XWZ。（A2，A3）n分解规则：由XY及 ZY，有XZ。（A1，A3）第117页4.属性集闭包定义2.11 设F为属性集U上一组函数依赖，X U，XF+=A|XA能由F 依据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 闭包第118页求闭包算法算法：求属性集X（X U）关于U上闭包XF+输入：X，F输出：XF+步骤：第119页步骤n（1）令X（0）=X，i=0n（2）求B，这里B=A|(V)(W)(VWF V X（i）A W)；n（3）X（i+1）=BX（i）n（4）判断X（i+1）=X（i）吗?n（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。n（6）若否，则 i=i+l，返回第（2）步。第120页举例【例2.16】已知关系模式R(U，F)，U=A，B，C，D，E，F=AB，DC，BCE，ACB，求 、。n解:第121页举例n(1)求 ，依据上述算法，设X(0)=AE。n计算 X(1)。逐一扫描F中各个函数依赖，找到左部为A、E或 AE函数依赖，找到一个AB。故有 X(1)=AEYB。n计算 X(2)。逐一扫描F中各个函数依赖，找到左部为ABE或ABE子集函数依赖，因为找不到这么函数依赖，所以 X(1)=X(2)。算法终止，=ABE。第122页举例n(2)求 ，依据上述算法，设X(0)=AD。n计算X(1)。逐一扫描F中各个函数依赖，找到左部为A、D或AD函数依赖，找到两个AB，DC函数依赖。故有X(1)=ADYBC。n计算X(2)。逐一扫描F中各个函数依赖，找到左部为 ADBC或ADBC子集函数依赖，得到两个BCE，ACB函数依赖。故有 X(2)=ABCDYE。因为X(2)=ABCDE=U，所以算法终止，=ABCDE。第123页5.最小函数依赖集n定义2.12 一个关系模式R（U，F）上两个依赖集F和G，假如F+=G+，则称F和G是等价，记做FG。n若FG，则称G是F一个覆盖，反之亦然。两个等价函数依赖集在表示能力上是完全相同。第124页5.最小函数依赖集n定义2.13 假如函数依赖集F满足以下条件，则称F为最小函数依赖集或最小覆盖。n（1）F中任何一个函数依赖右部仅含有一个属性；n（2）F 中不存在这么一个函数依赖 XA，使得F与F-XA等价；n（3）F中不存在这么一个函数依赖XA，X有真子集Z使得F-XAZA与F等价。第125页5.最小函数依赖集n算法:计算最小函数依赖集。n输入:一个函数依赖集。n输出:F一个等价最小函数依赖集G。第126页5.最小函数依赖集n步骤:n(1)用分解规则，使 F 中任何一个函数依赖右部仅含有一个属性。n(2)去掉多出函数依赖。逐一检验 F 中各函数依赖XY，并将XY从F中去掉，然后在剩下函数依赖集F中求属性X闭包 ，看 是否包含Y，若是，则去掉XY，不然不能去掉。依次做下去，直到找不到冗余函数依赖。第127页步骤:n(3)去掉各依赖左部多出属性。一个一个地检验函数依赖左部非单个属性依赖。比如XYA，若要判Y为多出，则以XA代替 XYA，并判断是否等价。若A ，则Y是多出，能够去掉。第128页举例n【例2.17】已知关系模式R(U，F)，U=A，B，C，D，E，G，F=ABC，DEG，CA，BEC，BCD，CGBD，ACDB，CEAG，请将F化为最小函数依赖集。第129页6.候选关键字求解方法n给定一个关系模式R(U，F)，U=A1，A2，An，F是R函数依赖集，那么，能够见属性分为以下四类：nL：仅出现在函数依赖集F左部属性