最新资料第4章关系数据库方法ppt模版课件

第4章 关系数据库方法,本章主要内容,本章将主要介绍关系数据库的基本概念，关系运算和关系表达式的优化问题，其中关系运算和关系表达式的优化问题是本课程的重点内容之一。关系运算是关系数据模型的理论基础。,关系数据库方法,4.1 关系数据库的基本概念 4.2 关系代数 4.3 关系演算 4.4 关系查询优化 本章小结,4.1 关系数据库的基本概念,4.1.1 关系的形式化定义 4.1.2 关系模式、关系子模式和存储模式 4.1.3 关系模型的完整性规则 4.1.4 关系数据库模式,4.1.1 关系的形式化定义,1.关系的集合表示 一个关系由若干个不同元组组成。 一个关系可以看成是元组的集合。 关系中每个属性都有其相应的取值范围，即域,4.1.1 关系的形式化定义,给定一组域D1，D2， ，Dn 则其笛卡尔积 D1D2 Dn =(d1， d2， ，dn) diDi,i=1,2,n 每个元素(d1，d2，dn)称为一个元组。 若Di（i=1,2,n）为有限集，其基数为mi（i=1,2，n)， 则D1D2Dn的基数为：,4.1.1 关系的形式化定义,【例4-1】设有两个域:教师名域T胡恒，丁伟、课程名域CC语言，数据结构，计算机原理，T和C的笛卡儿积定义为集合： TC（胡恒，C语言），（胡恒，数据结构），（胡恒，计算机原理），（丁伟，C语言），（丁伟，数据结构），（丁伟，计算机原理）,该笛卡儿积的基数为236，也就是说，TC一共236个元组.,4.1.1 关系的形式化定义,如果取该笛卡儿积的这六个元素，并将它们放到一张名为T_C的二维表中就构成一个关系。,例， 给出三个域： D1=导师= 张清玫，刘逸 D2=专业=计算机专业，信息专业 D3=研究生=李勇，刘晨，王敏,4.1.1 关系的形式化定义,则D1，D2，D3的笛卡尔积为： D1D2D3 (张清玫，计算机专业，李勇)， (张清玫，计算机专业，刘晨)， (张清玫，计算机专业，王敏)， (张清玫，信息专业，李勇)， (张清玫，信息专业，刘晨)， (张清玫，信息专业，王敏)， (刘 逸，计算机专业，李勇)， (刘 逸，计算机专业，刘晨)， (刘 逸，计算机专业，王敏)， (刘 逸，信息专业，李勇)， (刘 逸，信息专业，刘晨)， (刘 逸，信息专业，王敏) ,4.1.1 关系的形式化定义,在上述笛卡尔积中取出有实际意义的元组来构造关系。 关系：SAP(SUPERVISOR，SPECIALITY， POSTGRADUATE) 如，SAP关系可以包含三个元组： (张清玫，信息专业，李勇)， (张清玫，信息专业，刘晨)， (刘逸，信息专业，王敏) ,4.1.1 关系的形式化定义,定义4-1：一个在域D1,D2，,Dn上的关系就是笛卡儿积D1D2Dn的子集，用R(D1,D2，,Dn)表示, 关系的成员为元组，即笛卡儿积的子集的元素(d1，d2，dn)。 当n=1时，称关系为单元关系 当n=2时，称关系为二元关系,4.1.1 关系的形式化定义,2. 关键码和表之间的联系 在关系数据库中，通常有如下几种键： (1)超 键 在一个关系中，能惟一标识元组但含有多余属性的属性组合，称为关系的超键。 (2)候选键 如果一个属性组能唯一标识元组，且又不含有多余的属性，那么这个属性组称为关系的候选键。 (3)主 键 若一个关系中有多个候选键，则选其中的一个为关系的主键。,4.1.1 关系的形式化定义,用主键实现关系定义中：表中任意两行（元组）不能相同的约束。 主键中任何属性的取值不能为空，主键的值不能重复。 包含在任何一个候选键中的属性称为主属性，不包含在任何键中的属性称为非主属性或非键属性。,4.1.1 关系的形式化定义(8),在上表中，“职工编号”、“身份证号”可以作候选键。 关系的候选键可以有多个，但不能同时使用，只能使用一个，譬如使用“职工编号”来标识职工，那么“职工编号”就是主键了。,4.1.1 关系的形式化定义,(4)外键 若一个关系R中包含有另一个关系S的主键所对应的属性集F,则称F为R的外键。并称关系S为被参照关系或目标关系，关系R为依赖关系或参照关系。,例如，职工关系和部门关系分别为： 职工（职工编号，姓名，部门编号，性别，年龄，身份证号码） 部门（部门编号，部门名称，部门经理）,职工关系的主键为职工编号，部门关系的主键为部门编号，在职工关系中，部门编号是它的外键。,4.1.1 关系的形式化定义,4.1.1 关系的形式化定义,3.关系的一阶谓词表示 关系模型不但可以用关系代数表示，还可以用一阶谓词演算表示。,定义4-2：设有关系模式R，其原子谓词表示形式为P (t)。其中，P是谓词，t为个体变元，以元组为其表现形式。,4.1.1 关系的形式化定义,关系R(元组的集合)与谓词P (t)之间的联系描述为：RtP (t) 表示所有使谓词P为真或满足谓词P的元组t都属于关系R。 关系R与原子谓词P之间的关系如下： P(t)True，t在R内, P(t)False，t不在R内。,4.1.2 关系模式、关系子模式和存储模式,1）关系模式 关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的主键。具体的关系称为实例。 一般形式是R(A1,A2，,An)，其中R是关系名, A1,A2，,An是该关系的属性名。,4.1.2 关系模式、关系子模式和存储模式,学生关系模式S(SNO, SNAME，AGE, SEX, DNAME) 课程关系模式C（CNO, CNAME，DNAME, TNAME） 选课关系模式SC(SNO, CNO, SCORE),将该实体联系图(ER图)转换成关系模式集如下：,4.1.2 关系模式、关系子模式和存储模式,4.1.2 关系模式、关系子模式和存储模式,4.1.2 关系模式、关系子模式和存储模式,2）关系子模式 关系子模式是对用户所需数据的结构的描述 是从若干关系模式中抽取满足一定条件的数据，其中包括这些数据来自哪些模式和应满足哪些条件。,4.1.2 关系模式、关系子模式和存储模式,例如：用户需要用到成绩子模式G(SNO, SNAME, CNO, SCORE)。子模式G对应的数据来源于表S和表SC,构造时应满足它们的SNO值相等。子模式G的构造过程如图所示。,G,3）存储模式 存储模式描述了关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现此外，还可以对任意的属性集建立辅助索引。,4.1.2 关系模式、关系子模式和存储模式,SCORE,4.1.3 关系模型的完整性规则,关系模型的完整性规则是对数据的约束。 关系模型提供了三类完整性规则，实体完整性规则、参照完整性规则、用户定义的完整性规则。 其中实体完整性规则和参照完整性规则是关系模型必须满足的完整性的约束条件，称为关系的两个不变性。,4.1.3 关系模型的完整性规则,1）实体完整性规则 实体完整性规则：关系中元组的主码值不能为空且不能重复。主码若包含多个属性，则其中的任何属性取值都不能为空。 如：选课关系模式SC(SNO, CNO, SCORE)，其主码由SNO，CNO组成，因此，SNO和CNO的取值都不能为空。,4.1.3 关系模型的完整性规则,2）参照完整性规则 （1）关系间的引用 在关系模型中实体及实体间的联系都是用关系来描述的，因此可能存在着关系与关系间的引用。 在关系数据库中，关系与关系之间的引用是通过公共属性实现的。,4.1.3 关系模型的完整性规则,例1：学生实体、专业实体以及专业与学生间的一对多联系用关系模式表示如下，这两个关系之间通过公共属性“专业号”进行联系。 学生（学号，姓名，性别，专业号，年龄） 专业（专业号，专业名） 说明：学生表中的“专业号”属性的取值要参照专业表中的主码“专业号”的值，不能取专业表中“专业号”以外的值。 。,学生（学号，姓名，性别，专业号，年龄）,专业（专业号，专业名）,4.1.3 关系模型的完整性规则,4.1.3 关系模型的完整性规则,例2、学生、课程、学生与课程之间的多对多联系 学生（学号，姓名，性别，专业号，年龄） 课程（课程号，课程名，学分） 选修（学号，课程号，成绩）,学生,学生选课,课程,4.1.3 关系模型的完整性规则,例3 学生实体及其内部的领导联系(一对多) 学生（学号，姓名，性别，专业号，年龄，班长）,4.1.3 关系模型的完整性规则,（2）外码 参照完整性规则是通过外码来实现的。 外码（Foreign Key）的定义：设F是基本关系R的一个或一组属性，但不是关系R的主码。如果F与基本关系S的主码Ks相对应，则称F是基本关系R的外码.,4.1.3 关系模型的完整性规则,基本关系R称为参照关系（Referencing Relation） 基本关系S称为被参照关系（Referenced Relation）或目标关系（Target Relation）。,4.1.3 关系模型的完整性规则,（3）参照完整性规则： 若属性（或属性组）F 是基本关系 R 的外码，它与基本关系 S 的主码 Ks 相对应，则对于 R 中的每个元组，其在 F 上的取值只有以下两种情况： 或者取空值（F 中的每个属性值均为空值） 或者等于S 中某个元组的主码值。,4.1.3 关系模型的完整性规则,例4： 学生（学号，姓名，性别，专业号，年龄） 专业（专业号，专业名） 学生关系中每个元组的“专业号”属性只能取以下两种值： （1）空值，表示尚未给该学生分配专业 （2）非空值，这时该值必须是专业关系中某个元组的“专业号”值，表示该学生不可能分配到一个不存在的专业中,外码,4.1.3 关系模型的完整性规则,例5、在选修（学号，课程号，成绩）中， “学号”和“课程号”是选修关系中的主属性，按照实体完整性和参照完整性规则， 它们只能取被参照关系“学生”和“课程”中已经存在的主码值，而不能取空值。 因为主码中的任何属性都不能为空。,推论：当外码是其所在表的主码中的一部分时，不能取空值。只有当外码不是其所在表的主码中的一部分时，才可以取空值。,4.1.3 关系模型的完整性规则,例6、学生（学号，姓名，性别，专业号，年龄，班长） “班长”属性值可以取两类值： （1）空值，表示该学生所在班级尚未选出班长，或该学生本人即是班长； （2）本关系中某个元组的学号值,4.1.3 关系模型的完整性规则,导师,研究生,允许为空值,这是一个错误值 (引用了不存在的编码318),例如，图中研究生表的主码是学号，不包含空的数据项；导师表的主码是导师编号，也不包含空的数据项， 所以，这两个表都满足实体完整性规则 违反了参照完整性规则。,4.1.3 关系模型的完整性规则,3）用户定义的完整性规则 这是针对某一具体数据的约束条件，由应用环境决定。它反映某一具体应用所涉及的数据必须满足的语义要求。 例如：学生成绩应该大于或等于零，职工的工龄应小于年龄，等等。,4.1.4 关系数据库模式,一个关系数据库是多个关系的集合，这些具体关系构成了关系数据库的实例。由于每个关系都有一个模式，所以，构成该关系数据库的所有关系模式的集合构成了关系数据库模式。,例如，一个学生选课数据库系统的模式有下面三个关系模式构成： S(SNO，SNAME，SEX，AGE，DNAME) C(CNO，CNAME，PRE_CNO) SC(SNO，CNO，SCORE）,4.2 关系代数,4.2.1 关系代数的五个基本操作 4.2.2 关系代数的组合操作 4.2.3 关系代数表达式应用举例,4.2.1 关系代数的五个基本操作,关系代数操作集, , , 是个完备的操作集，任何其他关系代数操作都可以用这五种操作来表示。这五种操作被称为关系代数的五个基本操作。,并，差，笛卡尔积，选择，投影,4.2.1 关系代数的五个基本操作,设关系R和S具有相同结构的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为RS。形式定义如下： RSt | tR tS，t是元组变量，R和S的元数相同。,1） 并（Union）,4.2.1 关系代数的五个基本操作,例如：有库存和进货两个表（见下表），要将两个表合并为一个表，可利用并运算来实现。,2）差（Difference）,设关系R和S具有相同结构的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为RS。形式定义如下： RS t | tR t S，R和S的元数相同。,例如：有考生成绩合格者名单和身体不合格名单两个关系，按录取条件将成绩合格且身体健康的考生中产生录取名单关系。,事例,3)笛卡尔积(Cartesian Product),设有关系R和S，它们分别是n目和m目关系（即它们的属性个数分别为n和m），分别有p和q个元组。则关系R,S经笛卡尔积运算的结果T是一个nm目关系，共有pq个元组，这些元组是由R与S的元组组合而成的。,关系R与S的笛卡尔积记为RS，形式定义如下：,3）笛卡尔积举例,表4.6（b）MANAGER（经理）,例4.3:假定部门信息存放在表DEPTINFO中（见表4.7），则表MANAGER与表DEPTINFO的笛卡尔积如表4.8所示。,3）笛卡尔积举例,R,S,R S,4）选择运算(Selection),选择操作是根据某些条件对关系做水平分割，即在一个关系内选择符合条件的元组称为选择运算。选择运算可表示为：C（R）ttRCt=True 选择运算是从行的角度进行的运算。,选择运算举例,1、对表WORKER执行下列选择运算：,练习题：查询1号部门年龄低于30的员工信息。,选择运算举例,Student,选择运算举例,例1 查询信息系（IS系）全体学生 Sdept = IS (Student) 或 5 =IS (Student) 结果：,选择运算举例,例2 查询年龄小于20岁的学生 Sage 20(Student) 或 4 20(Student) 结果：,5）投影(Project),投影操作是对一个关系进行垂直分割，即从一个关系中选择出若干属性列组成新的关系。 A(R) = tA | t R A：R中的属性列 投影操作主要是从列的角度进行运算,5）投影(Project),注意：投影之后不仅取消了原关系中的某些列，还要取消某些重复的行 。因此，经过投影运算后得到的新关系的元组数目肯定小于或等于原来关系的元组数。,投影举例,对例4-2中的表WORKER执行下列投影运算： NAME,AGE（WORKER）、 DEPTNO(WORKER) 其结果如表所示。,投影运算事例,取消了重复的部门号,4.2.2 关系代数的组合操作,1）交集运算（intersection） 设关系R和S具有相同的元数n，相应的属性取自同一个域，则关系R和S的交集运算记为RS，由既属于R又属于S的元组组成，其结果仍然一个n元关系。形式定义如下： RSttRtS,t是元组变量。,关系R和S 的交集可以用关系的差来表示， RSR（RS） 或 RSS（SR）,1）交集运算（intersection）,例如：以上例中的WORKER和MANAGER为例，其交运算WORKERMANAGER的结果表4.13（E）所示。可以其按差运算WORKER（WORKERMANAGER）来计算，其结果分别如表4.13（E1）、表4.13（E2）所示。,交集运算举例,2）连接(Join)运算,可见，连接操作是笛卡尔积和选择操作的组合。,（1）条件连接 条件连接运算又可称-连接，这是一个二目运算，通过它将两个关系合并成一个关系。设有关系S和n目关系R以及比较表达式ij ,其中i是R中的属性,j是S的属性, 为比较运算符。形式定义如下：,说明：当为“=”时又称其为等值连接。,连接运算举例,EMP ELIT,（2）自然连接(Natural Join),自然连接是等值连接的一种特例，可以定义为:,RS,可以用“两个相同，一个取消”来简单地记忆自然连接的特点。即两个关系根据相同的属性组上值相同的原则进行连接，连接的结果要去除重复的属性列。,自然连接的特点： 两个关系中进行比较的分量必须是相同的属性组 在结果中要把重复的属性列去掉,自然连接事例 MANAGER DEPTINFO,3）除法运算(Division）,RS是由R中那些不出现在S中的属性组成，其元组则是S中所有元组在R中对应值相同的那些元组值。,在SC表中，S1对应的CNO集合为 C1,C2,S2为 C1,C2，C3,S3为 C3,只有S2对应的CNO包含了C表中的所有课程号，所以商为S2。,象集,除法运算举例,R,S,小结,l 关系代数运算 关系代数运算 并、差、交、笛卡尔积、投影、选择、连接、除 基本运算 并、差、笛卡尔积、投影、选择 交、连接、除 可以用5种基本运算来表达 引进它们并不增加语言的能力，但可以简化表达,4.2.3 关系代数应用举例,（1）检索“陈军”老师所授课程的课程号（CNO）和课程名（CNAME）,CNO, SNAME（TEACHER=陈军（C）,（2）检索年龄大于21的男学生学号（SNO）和姓名（SNAME）,SNO,SNAME（AGE21 SEX=男 （S）,（3）检索至少选修“陈军”老师所授全部课程的学生姓名（SNAME）,SNAME（S（SNO, CNO（SC） CNO（TEACHER=陈军（C）,S（SNO，SNAME，AGE，SEX，DNAME） C（CNO，CNAME，PRE_CNO，TEACHER） SC（SNO，CNO，SCORE）,应用举例,（4）检索“李强”同学不学课程的课程号（CNO）,CNO（C）CNO（SNAME=李强（S）SC）,（5）检索至少选修两门课程的学生学号（SNO）,SNO（1=4 25 （SCSC）,（6）检索全部学生都选修的课程的课程号（CNO）和课程名（CNAME）,CNO, CNAME（C（SNO, CNO（SC）SNO（S）,（7）检索选修课程包含“陈军”老师所授课程之一的学生学号（SNO）,SNO（SCCNO（TEACHER=陈军（C）,S（SNO，SNAME，AGE，SEX，DNAME） C（CNO，CNAME，PRE_CNO，TEACHER） SC（SNO，CNO，SCORE）,应用举例,（10）检索选修课程包含学号为S2的学生所修课程的学生学号（SNO）,SNO, CNO（SC）CNO（SNO=S2（SC）,（11）检索选修课程名为“C语言”的学生学号（SNO）和姓名（SNAME）,SNO, SNAME（S（SNO（SC（CNAME=C语言（C）,SNO, CNO（SC）CNO （CNO=k1 CNO=k5 （C）,（8）检索选修课程号为k1和k5的学生学号（SNO）,（9）检索选修全部课程的学生姓名（SNAME）,SNAME（S（SNO, CNO （SC） CNO（C）,S（SNO，SNAME，AGE，SEX，DNAME） C（CNO，CNAME，PRE_CNO，TEACHER） SC（SNO，CNO，SCORE）,4.3 关系演算,把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。 关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。 4.3.1 元组关系演算 4.3.2 域关系演算,4.3.1 元组关系演算,在元组关系演算中，元组关系演算表达式的一般形式为: t | P（t） 表示满足公式P的所有元组t的集合。,设关系R和S的谓词分别为R(u)和S(v)，用它们表示并、差、选择、投影和笛卡儿积如下： 1）并：RStR（t）S（t） 2）差：RStR（t） S（t） 3）选择：F (R)tR（t）F 其中F是条件表达式F在谓词演算中的表示形式。,4.3.1 元组关系演算,4）投影： 5）笛卡儿积 ：,元组关系演算表达查询举例,设有关系模式S(SNO, SNAME, SEX, SA, SDEPT) 例4.11：列出计算机科学系CS的所有学生：,例4.12：列出所有年龄大于或等于20的学生：,例4.13：求学生姓名及所在的系：,4.3.2 域关系演算,域演算的运算符基本上与元组关系演算相同，主要区别是公式中的变元不再是元组而是元组分量的域，简称域变量。 域演算表达式的形式是： X1，X2，Xk（X1，X2，Xk）,原子公式有三类： (1) R（X1，X2，Xk）,R是K元关系，Xi是域变量或常量。R（X1，X2，Xk）表示由分量X1，X2，Xk组成的元组属于R。 (2) XY，X、Y是域变量,是算术比较符，XY表示X与Y满足比较关系。 (3) Xc或cX,这里c为常数，表示域变量x与常数c之间满足比较关系。,4.4 关系查询优化,查询是数据库的最基本、最常用、最复杂的操作。 数据库的查询一般从查询语句出发，直到获得查询结果，需要一个处理过程，这个过程叫做查询处理。 在关系数据库的查询中用户不必关心查询语言的具体执行过程，而由DBMS确定合理的、有效的执行策略，称为查询优化。,4.4.1 查询优化的一般策略,(1)尽可能早地执行选择、投影等一目运算。 (2)先做选择，后作连接运算。 (3) 把投影同其前