数据库原理及应用教案课件

数据库原理及应用教案数据库原理及应用教案河北化工医药职业技术学院河北化工医药职业技术学院 第2章 关系数据库n2.1 关系数据库与关系模型n2.2 关系的形式定义n2.3 关系运算代数n2.4 查询优化n2.5 关系数据库的规范化理论 2.1关系数据库与关系模型2.1.1 基本概念n1关系数据库系统n关系数据库系统是支持关系数据模型的数据库系统。关系数据库应用数学方法来处理数据库中的数据。n关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。n关系数据库管理系统RDBMS如著名的IBM DB2，Oracle，Ingres，SYBASE，Informix等。2关系的相关名词n域：域：域是一组具有相同数据类型的值的集合。n一般在关系数据模型中，对域还加了一个限制，所有的域都应是原子数据（atomic data）。n目或度（Degree）：设有关系R(D1，D2，Dn)，这里的R表示关系的名字，n是关系的目或度。n属性属性：在现实世界中，要描述一个事物常常取若干特征来表示。这些特征称为属性（attribute）。n目关系必有n个属性。2关系的相关名词n候选码（Candidate Key）：若关系中的某一属性或属性组的值能唯一的标识一个元组，则称该属性或属性组为候选码。n主码（Primary Key）：若一个关系有多个候选码，则选定其中一个为主码。n主属性（Non-Key attribute）：主码的诸属性称为主属性。不包含在任何候选码中的属性称为非码属性。据(Data)是数据库中存储的基本对象2关系的相关名词n外码（Foreign key）：如果关系模式 R中的属性或属性组非该关系的码，但它是其它关系的码，那么该属性集对关系模式 R而言是外码。n例如，客户与贷款之间的借贷联系c-l（c-id，loan-no），属性 c-id 是客户关系中的码，所以c-id是外码；属性loan-no是贷款关系中的码，所以loan-no也是外码。2关系的相关名词n全码（All-key）：关系模型的所有属性组是这个关系模式的候选码，称为全码。n例如，关系模式R（T，C，S），属性T表示教师，属性 C表示课程，属性 S表示学生。假设一个教师可以讲授多门课程，某门课程可以由多个教师讲授，学生可以听不同教师讲授的不同课程，那么，要想区分关系中的每一个元组，这个关系模式R的码应为全属性T、C和S，即All-key。3关系的三种类型n基本关系（通常又称为基本表或基表）：是实际存在的表，它是实际存储数据的逻辑表示。n查询表：查询结果对应的表。n视图表：是由基本表或其它视图表导出的表。由于它本身不独立存储在数据库中，数据库中只存放它的定义，所以常称为虚表。2.1.2 关系模型n1关系模型的三要素 关系数据模型由关系数据结构、关系操作集合和关系完整性约束三大要素组成。n(1)关系数据结构n关系模型的数据结构单一，在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示，在用户看来，关系模型中数据的逻辑结构是一张二维表。1关系模型的三要素n(2)关系操作集合n关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称为一次一个集合的方式。相应地，非关系数据模型的数据操作方式则为一次一个记录的方式。n关系模型中常用的关系操作包括：选择(select)、投影(Project)、连接(join)、除(divide)、并(union)、交(intersection)、差(differencc)等，以及查询(query)操作和增(insert)、删(delete)、改(update)操作两大部分。查询的表达能力是其中最主要的部分。(2)关系操作集合n关系操作能力可用两种方式来表示：代数方式和逻辑方式。n关系代数是用对关系的运算来表达查询要求的方式。n关系演算是用谓词来表达查询要求的方式。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。对于关系代数、元组关系演算和域关系演算均是抽象的查询语言，在表达能力上是完全等价的。1关系模型的三要素n(3)关系的完整性约束n数据库的数据完整性是指数据库中数据的正确性和相容性，是一种语义概念，包括两个方面：n与现实世界中应用需求的数据的相容性和正确性。n数据库内数据之间的相容性和正确性。n例如，学生的学号必须惟一，性别只能是男或女，学生所选修的课程必须是已开设的课程，等等。n数据库中数据是否具备完整性关系到数据库系统能否真实地反映现实世界，因此，数据库的完整性是十分重要的。(3)关系的完整性约束n数据完整性由完整性规则来定义，关系模型的完整性规则是对关系的某种约束条件。关系模型中可以有3类完整性约束:实体完整性、参照完整性和用户定义的完整性。n实体完整性和参照完整性是关系模型必须满足的完整性约束条件，应该由关系系统自动支持。n用户定义完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束，一般由关系系统提供编写手段、由 DBMS的完整性检查机制负责检查。2关系模式n定义2.1 关系的描述称为关系模式。可以形式化的表示为 R（U，D，dom，F）n其中，R表示关系名；U是组成该关系的属性名集合；D是属性的域；dom是属性向域的映象集合；F为属性间数据的依赖关系集合。2关系模式n通常将关系模式简记为：R（U）或R(A1，A2，A3，An)n其中 R为关系名，A1，A2，A3，An为属性名或域名，属性的向域的映象常常直接说明属性的类型、长度。通常在关系模式主属性上加下划线表示该属性为主码属性。举例n【例2.1】学生关系 S有学号Sno、学生姓名Same、性别Sex、系名SD、年龄Age属性；课程关系 C有课程号Cno、课程名Cname、先修课程号PCno属性；学生选课关系SC有学号Sno、课程号 Cno、成绩Grade属性。写出这三个关系模式。举例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关系中的主码。2.1.3关系的三类完整性规则n关系模型的完整性规则是对关系的某种约束条件。关系的完整性共分为三类：n实体完整性n参照完整性（也称引用完整性）n用户定义完整性。1实体的完整性（Entity Integrity）n【规则2.1】若属性A是关系R的主属性，则属性A不能取空值。n例如：关系学生(学号，姓名，性别，专业号，年龄)中，主码为“学号”，则“学号”不能取空值。在关系选修(学号，课程号，成绩)中，“学号、课程号”为主码，则“学号”和“课程号”两个属性都不能取空值。2参照的完整性（Referential Integrity）n在关系模型中实体及实体间的联系是用关系来描述的，这样自然就存在着关系与关系间的引用。n例如，员工和部门关系模式表示如下：n员工（员工号，姓名，性别，参加工作时间，部门号）n部门（部门号，名称，电话，负责人）n这两个关系存在着属性的引用，即员工关系中的“部门号”值必须是确实存在的部门的部门号，即部门关系中有该部门的记录。也就是说，员工关系中的“部门号”属性取值要参照部门关系的“部门号”属性取值。2参照的完整性（Referential Integrity）n【规则2.2】若F是基本关系 R的外码，它与基本关系S的主码Ks相对应（基本关系R和S不一定是不同的关系）则对于 R中每个元组在F上的值必须为：n(1)或者取空值（F的每个属性值均为空值）n(2)或者等于S中某个元组的主码值。3.用户定义的完整性（User defined Integrity）n实体完整性规则定义了对关系中主属性取值的约束，即对主属性的值域的约束；n参照完整性规则定义了参照关系和被参照关系的外码与主码之间的参照约束，即对参照关系的外码属性值域的约束，规定外码属性的值域只能是空值或是相应被参照关系主码属性的值。n用户定义的完整性就是针对某具体应用要求来定义的约束条件，它反映某一具体应用所涉及的数据必须满足的语义要求。n例如，某个属性必须取惟一值，某些属性值之间应满足一定的函数关系，某个属性的取值范围在0100 之间等。用户定义的完整性通常是定义对关系中除主码与外码属性之外的其他属性取值的约束，即对其他属性的值域的约束。n对属性值域的约束也称为域完整性约束，是指对关系中属性取值的正确性限制，包括数据类型、精度、取值范围、是否允许空值等。3.用户定义的完整性（User defined Integrity）22关系的形式定义2.2.1 关系的形式定义n1笛卡尔积数据的定义n定义2.2 设 为任意集合，定义 的笛卡儿积为：22关系的形式定义n其中每一个元素 叫做一个 n 元组（n-tuple属性的个数），元组的每一个值 叫做元组的一个分量，若 为有限集，其基数（Cardinal number元组的个数）为 ，则 的基数为：。笛卡儿积可以用二维表来表示。举例【例2.2】若 求：n解:根据定义，笛卡尔积中的每一个元素应该是一个三元组，每个分量来自不同的域，因此结果为:n用二维表表示如图2-1所示。图2-1 笛卡尔积的二维表表示2关系n定义定义2.3 的子集叫做在域 上的关系，记为 ，称关系R为n元关系。n从定义2.3可以得出一个关系也可以用二维表来表示。关系中属性的个数称为“元组”，元组的个数称为“基数”。关系模型中的术语与一般术语的对应情况可以通过图2-2中的学生关系说明。2.2.2 关系模型的优点n1关系的性质n(1)列是同质的，即每一列中的分量均是同一类型的数据，即均来自同一个域。n(2)不同的列可以出自同一个域，每一列称为一个属性；属性不能重名。n(3)列的顺序是无关，即列的次序可以变换。但顺序一旦固定，就不再变化，不能导致冲突发生。n(4)任意两个元组不能完全相同。n(5)行的顺序是无关的，即行的次序可以交换。n(6)每一分量必须是不可分的数据项。2关系模型的优点n(1)关系模型使关系数据库的研究具有坚实的理论基础，这一理论有助于关系数据库的设计和用户对数据库信息需求的有效处理。n(2)关系模型的逻辑结构与相应的操作完全独立于数据的存储方式，具有高度的数据独立性，使得用户不必关心物理存储细节。2关系模型的优点n(3)关系模型提供单一的数据结构形式，具有高度的简明性和精确性，用户很容易掌握和运用基于关系模型的数据库系统。n(4)关系数据库语言与一阶谓词逻辑的固有内在联系，使得以关系数据库为基础的推理系统和知识库系统的研究提供了良好的基础。2.2.3 E-R模型向关系模型的转换n从 E-R模型向关系模型转换时，所有实体和联系都要转换成相应的关系模式，转换规则为：n(1)每个实体类型转换成一个关系模式；n(2)一个1:1的联系可转换为一个关系模式，或与任意一端的关系模式合并，若独立转换为一个关系模式，那么，两端关系的码及联系的属性为该关系的属性；若与一端合并，那么将另一端的码及联系的属性合并到该端。2.2.3 E-R模型向关系模型的转换n(3)一个1:n的联系可转换为一个关系模式，或与 n端的关系模式合并。若独立转换为一个关系模式，那么，两端关系的码及联系的属性为关系的属性，而n端的码为关系的码。n(4)一个n:m的联系可转换为一个关系模式，那么，两端关系的码及联系的属性为关系的属性，而关系的码为两端实体的码的组合。2.2.3 E-R模型向关系模型的转换n(5)三个或三个以上多对多的联系可转换为一个关系模式，那么，诸关系的码及联系的属性为关系的属性，而关系的码为各实体的码的组合。n(6)具有相同码的关系可以合并。举例S SC CCLASSCLASSSCSCm mn nCTCTn n1 1SnoSnoSnameSnameSageSageSexSexSDSDGradeGradeCnoCnoCnameCnamePcnoPcnoDateDateCLnoCLnoCLnameCLnameTelTel【例2.3】将图2-3的E-R图转换成关系模式。图2-3 学生班级课程的E-R图举例n从图中可以看出有3个实体:学生 S、课程 C、班级CLASS，根据转换规则转换成3个关系模式。联系CT是一个1:n类型，根据转换规则可将CLASS的码CLno，加上联系的属性Date并入n端。联系 SC是一个 n:m 类型，根据转换规则转换成一个独立的关系模式，所以将S的码Sno和C的码Cno，加上联系的属性 Grade作为关系 SC的属性，该关系的码是Sno和Cno。举例n根据上述分析转换的关系模式如下：nS(Sno，Sname，SD，Sage，Sex，CLno，Date)nC(Cno，Cname，Pcno)nCLASS(CLno，CLname，Tel)23 关系运算2.3.1关系代数的五种基本运算n关系代数运算符有四类：n集合运算符n专门的关系运算符n算术比较符n逻辑运算符n根据运算符的不同，关系代数运算可分为n传统的集合运算n专门的关系运算23 关系运算n传统的集合运算是从关系的水平方向进行的，包括：并、交、差及广义笛卡尔积。n专门的关系运算既可以从关系的水平方向进行运算，又可以向关系的垂直方向运算，包括：选择、投影、连接以及除法。如表 2-1所示。表2-11.并（Union）n关系R与S具有相同的关系模式，即 R与S的元数相同（结构相同）。关系 R与S并由属于R或属于S的元组构成的集合组成，记作 ，其形式定义如下：n式中t 为元组变量。2.差（Difference）n关系R与S具有相同的关系模式，关系R与S的差由属于R但不属于S的元组构成的集合，记作 ，其形式定义如下：3.广义笛卡尔积（Extended Cartesian Product）n 两个元数分别为n目和m目的关系R 和S 的广义笛卡尔积是一个（n+m）列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。记作 ，其形式定义如下：n如果R和S中有相同的属性名，可在属性名前加关系名作为限定。若R 有K1个元组，S 有K2个元组。则R和S的广义笛卡尔积有个 元组。4.投影（Projection）n投影运算是从关系的垂直方向进行运算，在关系R中选择出若干属性列A组成新的关系，记作 ，其形式定义如下：5.选择（Selection）n 选择运算是从关系的水平方向进行运算，是从关系R中选择满足给定条件的诸元组，记作 ，其形式定义如下：n其中，F中的运算对象是属性名(或列的序号)或常数，运算符算术比较府（，=，)和逻辑运算符(，)。5.选择（Selection）n例如，表示选取R关系中第一个属性值大于等于第六个属性值的元组；表示选取R关系中第一个属性值大于等于“6”的元组。举例【例2.4】设有关系R、S如图2-4所示，请求出：举例n解解:结果如图2-5所示。其中，后生成的关系属性名有重复，按照关系“属性不能重名”的性质，通常采用“关系名.属性名”的格式。对于 的含义是 后“选取第三个属性值小于第四个属性值”的元组。由于 的第三个属性为R.C，第四个属性是S.A，因此 的含义也是 后“选取R.C值小于S.A值”的元组。图2-5 运算结果2.3.2关系代数的组合运算n扩展的关系运算可以从基本的关系运算中导出。主要包括：选择、投影、连接、除法、广义笛卡尔积、外联接。1.交（Intersection）n关系R与S具有相同的关系模式，关系R与S的交由属于R同时又属于S的元组构成的集合，关系R与S的交记作 ，其形式定义如下：n显然，或者2.连接（Join）n连接分为：n连接n等值连接n自然连接n连接运算是从两个关系R和S的笛卡尔积中选取满足条件的元组。笛卡尔积是无条件连接，其它的连接 操作认为是有条件连接。下面分述如下。2.连接（Join）n(1)连接：从R与S的笛卡尔积中选取属性间满足一定条件的元组。记作：n其中:“”为连接条件，是比较运算符，X和Y分别为R和S上度数相等且可比的属性组。表示R中 元组的相应属性X的一个分量。表示S中 元组的相应属性Y的一个分量。(1)连接：n需要说明的是:连接也可以表示为：n其中:i=1，2，3，n，j=1，2，3，m。“”的含义为从两个关系R和S中选取R的第i列和S的第j列之间满足运算的元组进行连接。n连接可以由基本的关系运算笛卡儿积和选取运算导出，因此可表示为:或 举例【例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 2.连接（Join）n(2)等值连接：当为“=”时,称之为等值连接,记为 ,其形式定义如下:2.连接（Join）n(3)自然连接:是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中将重复属性列去掉。记为 ，其形式定义如下:（3）自然连接n自然连接可以由基本的关系运算投影、选取和笛卡儿积导出。n注意注意：一般连接是从关系的水平方向运算，而自然连接不仅要从关系的水平方向，而且要从关系的垂直方向运算。因为自然连接要去掉重复属性，如果没有重复属性，那麽自然连接就转化为笛卡儿积。举例：【例2.6】设有关系如图2-7所示,求：。举例：n解：本题要求 R与 S的自然连接，自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中将重复属性列去掉。本题 R与 S关系中相同的属性组为AC，因此，结果集中的属性列应为ABCD。其结果如图2-8所示。3.除（Division）n除运算是同时从关系的水平方向和垂直方向进行运算。给定关系 R(X，Y)和S(Y，Z)，X，Y，Z为属性组。应当满足元组在X上的分量值x的象集Yx包含关系S在属性组Y上投影的集合。其形式定义如下：n其中:Yx为x在R中的象集，x=，且 的结果集的属性组为X。举例n【例2.7】设有关系R、S如图2-9（a）（b）所示，求：。举例n解:n根据除法定义，此题的X为属性AB，Y为属性CD。应当满足元组在属性AB上的分量值x的象集Yx包含关系S在CD上投影的集合。举例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)，所以，=(a，b)，(c，k)，结果如图2-9(c)所示。2.3.3关系代数的外连接运算n外连接运算是连接运算的扩展，可以处理缺失的信息。对于图2-10的S和 SC关系，对其进行自然连接时，结果如图2-11所示。2.3.3关系代数的外连接运算2.3.3关系代数的外连接运算n由图2-11可以看出 S与SC的自然连接的结果丢失了黎明、刘明远、赵国庆的相关信息。使用外连接可以避免这样的信息丢失。外连接运算有3种：n左外连接n右外连接n全外连接2.3.3关系代数的外连接运算n1)左外连接(left outer join)n取出左侧关系中所有与右侧关系中任一元组都不匹配的元组，用空值null 填充所有来自右侧关系的属性，构成新的元组，将其加入自然连接的结果中。对于图 2-10的S和SC关系，对其进行左外连接S SC时，结果如图2-12所示。图2-12 S SC2.3.3关系代数的外连接运算n2)右外连接(right outer join)n取出右侧关系中所有与左侧关系中任一元组都不匹配的元组，用空值null填充所有来自左侧关系的属性，构成新的元组，将其加入自然连接的结果中。对于图 2-10的S和SC关系，对其进行左外连接S SC时，结果如图2-13所示。图2-13 S SC2.3.3关系代数的外连接运算n3)全外连接(right outer join)n填充左侧关系中所有与右侧关系中任一元组都不匹配的元组，又填充右侧关系中所有与左侧关系中任一元组都不匹配的元组，将产生的新元组加入自然连接的结果中。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”学生所学的课程的学生学号。图2-14 S，C SC关系24查询优化2.4.1关系代数表达式的优化问题n查询处理：是指从数据库中提取数据的一系列活动。这一系列活动包括：将高级数据库语言表示的查询语句翻译成为能在文件系统这一物理层次上实现的表达式，为优化查询进行各种转换，以及查询的实际执行。24查询优化n查询处理的代价：通常取决于磁盘的访问，磁盘的访问比内存访问速度要慢。对于一个给定的查询，可以有许多可能的处理策略，复杂查询更是如此。就所需的磁盘访问次数而言，策略好坏差别很大，有时甚至相差几个数量级。所以，系统多花一点时间选择一个较好的查询策略是很值得的。2.4.1关系代数表达式的优化问题n查询优化：是为了查询选择最有效的查询计划的过程。查询优化一方面是在关系代数级进行优化，要做的是力图找出与给定表达式等价，但执行效率更高的一个表达式。查询优化的另一方面涉及查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法以及将使用的特定索引等等。2.4.2关系代数表达式的等价变换规则n1优化的准则n(1)提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数。n(2)合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。1优化的准则n(3)将投影运算与其后的其它运算同时进行，以避免重复扫描关系。n(4)将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。1优化的准则n(5)在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。n(6)存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。2.关系代数表达式的等价变换规则n优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要。常用的等价变换规则有如下10种：n（1）连接、笛卡尔积交换率n设E1和E2是关系代数表达式，F是连接运算的条件，则有2.关系代数表达式的等价变换规则n（2）连接、笛卡尔积结合率n设E1，E2，E3是关系代数表达式，F1，F2是连接运算的条件，则有2.关系代数表达式的等价变换规则n（3）投影的串接定律n设E是关系代数表达式，A1，An和B1，Bm，且B1，Bm是A1，An的子集，则有n该规则的目的是使一些投影消失。2.关系代数表达式的等价变换规则n（4）选择的串接定律n设E是关系代数表达式，F1，F2是选取条件表达式，选择的串接定律说明选择条件可以合并，则有2.关系代数表达式的等价变换规则n（5）选择与投影的交换律n设E是关系代数表达式，F是选取条件表达式，并且只涉及A1，An属性，则有2关系代数表达式的等价变换规则n（6）选择与笛卡尔积的交换律n若F涉及的都是E1中的属性，则n如果F=F1F2，并且F1只涉及中E1的属性，F2只涉及E2中的属性，则有2关系代数表达式的等价变换规则n（7）选择与并的交换律n设E=E1E2，E1，E2有相同的属性，则n（8）选择与差的交换律n设E1，E2有相同的属性，则2关系代数表达式的等价变换规则n（9）投影与笛卡尔积的交换律n设E1，E2是两个关系代数表达式，A1，An是E1中的属性，B1，Bm是E2中的属性，则n（10）投影与并的交换律n设E1，E2有相同的属性，则2.4.3关系代数表达式的优化算法n算法：关系代数表达式的优化n输入：一个关系代数表达式的语法树n输出：计算该表达式的程序。n方法：n（1）利用规则4将形如 变换为：n（2）对每一选择，用规则48尽可能将它移到树的叶端。n（3）对每一个投影，利用规则3、9，10，5中的一般形式尽可能将它移到树的叶端。2.4.3关系代数表达式的优化算法n（4）利用规则35将选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。n（5）将上述得到的语法树的内节点分组。每一双目运算(，-)和它所有的直接祖先为一组（这些直接祖先是，运算）。如果其后代直到叶子全部是单目运算，则将它并入该组。方法：n（6）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。方法：举例n【例2.12】供应商数据库中有：供应商、零件、项目、供应四个基本表（关系）：nS(Sno，Sname，Status，City)nP(Pno，Pname，Color，Weight)nJ(Jno，Jname，City)nSPJ(Sno，Pno，Jno，Qty)举例n用户有一查询语句：检索使用上海供应商生产的红色零件的工程号。n(1)试写出该查询的关系代数表达式；n(2)试写出查询优化的关系代数表达式；n(3)画出该查询初始的关系代数表达式的语法树；n(4)使用优化算法，对语法树进行优化，并画出优化后的语法树。举例解:n(1)该查询的关系代数表达式如下:n(2)查询优化的关系代数表达式如下:n(3)该查询初始的关系代数表达式的语法树如图2-221所示。n(4)优化后的语法树如图2-22 所示。图2-21 优化前图2-22 优化后25关系数据库的规范化理论n规范化理论研究的是关系模式中各属性之间的依赖关系及其对关系模式性能的影响，提供判断关系模式优劣的理论标准，预测可能出现的问题，提供自动产生各种模式的算法。n关系数据库设计理论的核心是数据间的函数依赖，衡量的标准是关系规范化的程度及分解的无损连接和保持函数依赖性。2.5.1函数依赖n数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系，是现实世界属性间联系和约束的抽象，是数据内在的性质，是语义的体现。函数依赖则是一种最重要、最基本的数据依赖。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，就断定某函数依赖成立。举例n例如，关系模式Student(Sno，Sname，SD，Sage，Sex)可能在某时刻，Student的关系r中每个学生的年龄都不同，也就是说没有两个元组在Sage属性上取值相同，而在 Sno 属性上取值不同，但我们决不可据此就断定Sage Sno。很有可能在某一时刻，Student的关系 r中有两个元组在Sage属性上取值相同，而在Sno属性上取值不同。1.函数依赖的定义n非平凡的函数依赖：如果XY，但 YX，则称XY是非平凡的函数依赖。一般情况下总是讨论非平凡的函数依赖。n平凡的函数依赖：如果XY，但YX，则称XY是平凡的函数依赖。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传递函数依赖。举例【例2.13】n在关系模式SC(Sno，Cno，Grade，Credit)中，n(Sno，Cno)Grade 成绩完全函数依赖于学号和课程号n Cno Credit 学分函数依赖于课程号n(Sno，Cno)Credit 学分部分函数依赖于学号举例n在关系模式 Student(Sno，Sname，SD，Sdname，Sage，Sex)中，nSno Sname，Sno Sagen又因为Sno SD，SD Sno，SD SDname，所以可以得出Sno Sdname，即系名传递依赖于学号。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)。举例【例2.14】关系模式CSZ(CITY，ST，ZIP)，其属性组上的函数依赖集为n F(CITY，ST)ZIP，ZIPCITYn即城市、街道决定邮政编码，邮政编码决定城市。容易看出，(CITY，ST)和(ST，ZIP)是两个候选码。CITY、ST、ZIP都是主属性。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。多值依赖具有如下六条性质：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。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闭包，记做 。3.逻辑蕴涵与Armstrong公理系统n例如，关系模式Student(Sno，Sname，Age，SD，SDname)，其属性组上的函数依赖集为FSnoSname，SnoSage，SnoSD，SDSDname，SnoSDname就是F所逻辑蕴含的一个函数依赖。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举例【例2.15】利用 Armstrong公理系统的推理规则，对于【例2.14】的关系模式CSZ的已知条件，证明(ST，ZIP)(CITY，ST，ZIP)。举例n证明:根据题意不难看出只要证明(ST，ZIP)是一个候选码即可，证明步骤如下:n 因为ZIPCITY (F中已给出)n 所以(ST，ZIP)(CITY，ST)(利用增广率，即在函数依赖的两端加ST)n (ST，ZIP)(CITY，ST，ZIP)(用增广率，加ZIP)举例n严格地说，要证明(ST，ZIP)是候选码，还需要说明 ST(CITY，ST，ZIP)和ZIP(CITY，ST，ZIP)都不在 。3.逻辑蕴涵与Armstrong公理系统n根据上述三条推理规则又可推出下述三条推理规则：n合并规则：由XY，XZ，有XYZ。（A2，A3）n伪传递规则：由XY，WYZ，有XWZ。（A2，A3）n分解规则：由XY及 ZY，有XZ。（A1，A3）4.属性集的闭包定义2.11 设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包求闭包的算法算法：求属性集X（X U）关于U上的闭包XF+输入：X，F输出：XF+步骤：步骤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）步。举例【例2.16】已知关系模式R(U，F)，U=A，B，C，D，E，F=AB，DC，BCE，ACB，求 、。n解:举例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。举例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。5.最小函数依赖集n定义2.12 一个关系模式R（U，F）上的两个依赖集F和G，如果F+=G+，则称F和G是等价的，记做FG。n若FG，则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。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等价。5.最小函数依赖集n算法:计算最小函数依赖集。n输入:一个函数依赖集。n输出:F的一个等价的最小函数依赖集G。5.最小函数依赖集n步骤:n(1)用分解的规则，使 F 中的任何一个函数依赖的右部仅含有一个属性。n(2)去掉多余的函数依赖。逐一检查 F 中的各函数依赖XY，并将XY从F中去掉，然后在剩下的函数依赖集F中求属性X的闭包 ，看 是否包含Y，若是，则去掉XY，否则不能去掉。依次做下去，直到找不到冗余的函数依赖。步骤:n(3)去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XYA，若要判Y为多余的，则以XA代替 XYA，并判断是否等价。若A ，则Y是多余的，可以去掉。举例n【例2.17】已知关系模式R(U，F)，U=A，B，C，D，E，G，F=ABC，DEG，CA，BEC，BCD，CGBD，ACDB，CEAG，请将F化为最小函数依赖集。6.候选关键字的求解方法n给定一个关系模式R(U，F)，U=A1，A2，An，F是R的函数依赖集，那么，可以见属性分为如下四类：nL：仅出现在函数依赖集F左部的属性nR：仅出现在函数依赖集F右部的属性nLR：在函数依赖集F左右部都出现的属性nNLR：在函数依赖集 F左右部都未出现的属性举例【例2.18】设关系模式R(U，F)，其中U=A，B，C，D，F=AC，CB，ADB。求R的候选码。举例n解:根据结论(1)可以求得R的候选码为AD，而且AD是R唯一的候选码。分析如下:n(1)检查 F发现，A，D只出现在函数依赖的左部，所以为L类属性，而F包含了全属性，即不存在NLR类的属性。n(2)根据求属性闭包的算法，F中AC，ADB可以求得 =ABCD=U，而在 AD中不存在一个真子集能决定全属性，故AD为R的候选码。举例【例2.19】设关系模式R(U，F)，其中U=H，I，J，K，L，M，F=HI，KI，LMK，IK，KHM。求R的候选码。举例n解:根据结论(1)、(2)、(3)和(4)可以求得R的候选码为HLJ，而且HLJ是R唯一的候选码。分析如下:n(1)检查 F发现，H，L只出现在函数依赖的左部，所以为L类属性，J为NLR类的属性。n(2)根据求属性闭包的算法，F中HI，IK，KHM可以求得 =HIJKLM=U，而在HIJ中不存在一个真子集能决定全属性，故HIJ为R的候选码。2.5.2 规范化n关系数据库设计的方法之一就是设计满足适当范式的模式，通常可以通过判断分解后的模式达到几范式来评价模式规范化的程度。n范式有：1NF、2NF、3NF、BCNF、4NF和 5NF，其中 1NF 级别最低。这几种范式之间满足如下关系：n范式之间的关系如图 2-23所示。范式之间的关系图图2-23 范式之间的关系图范式之间的关系图2.5.2 规范化n通过分解，可以将一个低一级范式的关系模式转换成若干个高一级范式的关系模式，这种过程叫做规范化。11NF（第一范式）n定义2.14 若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)。记为R1NF。11NF（第一范式）n例如，供应者和它所提供的零件信息，关系模式FIRST和函数依赖集F如下：nFIRST(Sno，Sname，Status，City，Pno，Qty)nF=SnoSname，SnoStatus，StatusCity，（Sno，Pno）Qty11NF（第一范式）n显然，关系模式FIRST的码是（Sno，Pno）。对于非主属性Status、Sname和City是部分依赖于码（Sno，Pno）。函数依赖图如图 2-24 所示，图中虚线为部分函数依赖。11NF（第一范式）对具体的关系FIRST如表2-2所示。图2-24 FIRST函数依赖图n(1)冗余度大：例如每个供应者的Sno，Sname，Status，City要与其供应的零件的种类一样多。n(2)引起修改操作的不一致性：例如供应者 S1从“天津”搬到“上海”，若稍不注意，就会使一些数据被修改，另一些数据没有被修改，导致数据修改的不一致性。1NF存在的四个问题 n(3)插入异常：关系模式FRIST的主码为Sno、Pno，按照关系模式实体完整性规定主码不能取空值或部分取空值。这样，当某个供应者的某些信息未提供时（如 Pno），则不能进行插入操作，这就是所谓的插入异常。n(4)删除异常：若供应商 S4的P2零件销售完了，并且以后不再销售P2零件，那么应删除该元组。这样，在基本关系 FIRST找不到S4，可S4又是客观存在的。1NF存在的四个问题22NF（第二范式）n定义2.15 若关系模式R1NF，且每一个非主属性完全依赖于码，则关系模式R2NF。n换句话说，当 1NF消除了非主属性对码的部分函数依赖，则称为2NF。22NF（第二范式）n例如：FIRST关系中的码是Sno、Pno，而SnoStatus，因此非主属性Status部分函数依赖于码，故非2NF的。若此时，将FIRST关系分解为：n FIRST1（Sno，Sname，Status，City）2NFn FIRST2（Sno，Pno，Qty）2NF n分解后的函数依赖图如图2-25所示。图2-25 分解后的函数依赖图22NF（第二范式）22NF（第二范式）n因为分解后的关系模式 FIRST1的码为Sno，非主属性Sname，Status，city完全依赖于码Sno，所以属于2NF；关系模式 FIRST2的码为Sno、Pno，非主属性 Qty完全依赖于码，所以也属于2NF。33NF（第三范式）n定义2.16关系模式R（U，F）中若不存在这样的码X，属性组Y及非主属性Z（Z Y）使得XY，（Y X）YZ成立，则关系模式R 3NF。n即当2NF消除了非主属性对码的传递函数依赖，则称为3NF。33NF（第三范式）n例如：FIRST1 3NF，因为在分解后的关系模式FIRST1 中有 SnoStatus，StatusCity，存在着非主属性 City传递依赖于码Sno。若此时将FIRST1继续分解为：nFIRST11（Sno，Sname，Status）3NFnFIRST12（Status，City）3NF 33NF（第三范式）n通过上述分解，数据库模式FIRST转换为nFIRST11(Sno，Sname，Status)nFIRST12(Status，City)nFIRST2(Sno，Pno，Qty)n由于这3个子模式都达到了3NF，因此称分解后的数据库模式达到了3NF。33NF（第三范式）n可以证明，3NF 的模式必是2NF的模式。产生冗余和异常的两个重要原因是部分依赖和传递依赖。因为 3NF模式中不存在非主属性对码的部分函数依赖和传递函数依赖，所以具有较好的性能。对于非3NF的1NF、2NF，其性能弱，一般不宜作为数据库模式，通常要将它们变换成为 3NF或更高级别的范式，这种变换过程称为“关系模式的规范化处理”。4BCNF（Boyce-Codd范式）n定义2.17 若关系模式R1NF，若XY且YX时，X必含有码，则关系模式RBCNF。n换句话说，当3NF消除了主属性对码的部分和传递函数依赖，则称为BCNF。4BCNF（Boyce-Codd范式）n一个满足BCNF的关系模式应有如下性质：n(1)所有非主属性对每一个码都是完全函数依赖；n(2)所有非主属性对每一个不包含它的码，也是完全函数依赖；n(3)没有任何属性完全函数依赖于非码的任何一组属性.举例n例如，设R（Pno，Pname，Mname）的属性分别表示零件号、零件名和厂商名，如果约定，每种零件号只有一个零件名，但不同的零件号可以有相同的零件名；每种零件可以有多个厂商生产，但每家厂商生产的零件应有不同的零件名。这样我们可以得到如下一组函数依赖：nPnoPname，（Pname，Mname）Pnon若将R分解成：R1(Pno，Pname)和R2(Pno，Mname)，则R1、R2是BCNF。举例n由于该关系模式R的候选码为(Pname，Mname)或(Pno，Mname)，因而关系模式R的属性都是主属性，不存在非主属性对码的传递依赖，所以R是3NF的。但是，主属性由于 Pname传递依赖于码(Pname，Mname)，因此R不是BCNF。若将R分解成R1(Pno，Pname)和R2(Pno，Mname)，就可以解决上述问题，并且分解后的R1、R2都属于BCNF。5.4NF(第四范式)n定义2.18（4NF）关系模式R1NF，若对于R的每个非平凡多值依赖XY且Y X时，X必含有码，则关系模式R(U，F)4NF。n4NF是限制关系模式的属性间不允许有非平凡且非函数依赖的多值依赖。举例n【例2.20】关系模式WSC(W，S，C)中，W表示仓库，S表示保管员，C表示商品。假设每个仓库有若干个保管员，有若干种商品。每个保管员保管所在的仓库的所有商品，每种商品被所在商店的所有保管员保管。列出关系如表2-3所示。表2-3 仓库、保管员与商品举例n按照语义对于S的每一个值Si，S有一个完整的集合与之对应而不论C取何值，故SW。又由于C与W完全对称，必然有SC成立。n在WSC中，WS，WC，它们都是非平凡的多值依赖。而关系模式WSC的码是All Key，即码为(W，S，C)，W不是码，对照4NF的定义WSC 4NF。举例非4NF的关系模式的问题:n一个关系模式如果已达到了 BCNF但不是4NF，这样的关系模式仍然具有不好的性质。WSC 4NF，但是 WSCBCNF，对于WSC的某个关系，若某一仓库 W；有n个保管员，存放m件物品，则关系中分量为Wi的元组数目一定有mn个。每个保管员重复存储 m 次，每种物品重复存储 n次，数据的冗余度太大，因此还应该继续规范化使关系模式WSC达到4NF。n解决办法：n仍采用分解的方法消去非平凡且非函数依赖的多值依赖。例如我们可以把 WSC 分解为WS(W，S)，WC(W，C)。在 WS中虽然有WS，但这是平凡的多值依赖。WS中已不存在非平凡的非函数依赖的多值依赖。所以WS 4NF，同理WC 4NF。非4NF的关系模式的问题:n注意：如果只考虑函数依赖，关系模式最高的规范化程度是 BCNF；如果考虑多值依赖，关系模式最高的规范化程度是4NF。5.4NF(第四范式)2.5.3 关系模式分解n关系模式的规范化过程是通过关系模式的分解来实现的。把低一级的关系模式分解为若干个高一级的关系模式。n分解不是唯一的。1分解n定义2.20 关系模式R(U，F)的一个分解是指=R1(U1，F1)，R2(U2，F2)，Rn(Un，Fn)，其中：，并且没有Ui Uj，1i，jn，Fi是F在Ui上的投影，Fi=XY|XY F+XY Ui。1分解n对一个给定的模式的分解，分解后的模式是否与原来的模式等价有三种情况：n(1)分解具有无损连接性；n(2)分解要保持函数依赖；n(3)分解既要无损连接性；又要保持函数依赖。2无损连接n定义2.21 =R1(U1，F1)，R2(U2F2)Rk(Uk，Fk)是关系模式R(U，F)的一个分解，若对 R(U，F)的任何一个关系 r 均有r=m(r)成立，则成分解 具有无损连接性，简称无损分解。其中，2无损连接n定理2.1关系模式R(U，F)的一个分解，=R1(U1，F1)，R2(U2，F2)具有无损连接的充分必要的条件是：nU1U2U1-U2 F+n或U1U2U2-U1 F+举例【例2.21】对给定的关系模式R(U，F)，U=A，B，C，F=AB，如下的两个分解：n（1）1=AB，BCn（2）2=AB，ACn判这两个分解是否无损。举例解:n（1）可根据无损连接定理判断本题n ABBC=Bn AB-BC=An BC-AB=Cn n故1为有损连接。举例n（2）根据无损连接定理判断本题n ABAC=An AB-AC=Bn AC-AB=Cnn2为无损连接。注意:尽管，但根据无损连接定理充分必要条件只要满足一个即可，故2为无损连接。3保持函数依赖n定义2.22 设关系模式R(U，F)的一个分解，=R1(U1，F1)，R2(U2，F2)，Rk(Uk，Fk)，如果 则称分解保持函数依赖。4分解的无损连接性和保持函数依赖n算法2.1判别一个分解的无损连接性。n=R1(U1，F1)，R2(U2，F2)，Rk(Uk，Fk)是关系模式R(U，F)的一个分解，U=A1，A2，An，F=FD1，FD2，FD，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下：n(1)建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj Ui，则在j列i行上填上aj，否则填上bij；算法算法2.12.1步骤步骤n(2)对于每一个 FDi 做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中 li 列的元素，若其中有 aij，则全部改为 aij，否则全部改为bmli，m是这些行的行号最小值。n如果在某次更改后，有一行成为：a1，a2，an，则算法终止。且分解具有无损连接性，否则不具有无损连接性。n 对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。算法算法2.12.1步骤步骤n(3)比较扫描前后，表有无变化，