关系模型与关系代数.ppt

第2章 关系模型与关系代数,数据库系统原理与设计,目 录,关系模型,关系代数,关系模型,系统而严格地提出关系模型的是美国IBM公司的E.F.Codd 1970年提出关系数据模型 E.F.Codd, “A Relational Model of Data for Large Shared Data Banks”, Communication of the ACM,1970 关系数据库系统是支持关系数据模型的数据库系统。关系数据库管理系统是当今的主流数据库管理系统。 关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。,关系数据结构,关系 关系模型的数据结构非常简单，它就是二维表，亦称为关系 。 关系数据库是表的集合，即关系的集合。 表是一个实体集，一行就是一个实体，它由共同表示一个实体的有关联的若干属性的值所构成。 由于一个表是这种有关联的值的集合(即行的集合)，而表这个概念和数学上的关系概念密切相关，因此称为关系模型。 关系模型中，现实世界的实体以及实体间的各种联系都是用关系来表示。,关系数据结构,关系数据结构的形式化定义 域是一组具有相同数据类型的值的集合。 笛卡尔积 给定一组域D1, D2, , Dn，它们之中可以有相同的域。D1, D2, , Dn的笛卡尔积为： D1D2Dn = (d1, d2, , dn)diDi, i=1, 2, , n 其中，集合中的每一个元素(d1, d2, , dn)称为一个n元组, 简称为元组；元素中的每一个值di称为一个分量。 若Di (i=1, 2, , n)为有限集，假设其基数为mi (i=1, 2, , n)，则D1D2Dn的基数M为：,举例： 给定两个域： 学生的姓名集合：D1 = 李小勇, 刘方晨, 王红敏 课程的名称集合：D2 = 数据库系统概论, 操作系统 则D1, D2的笛卡尔积为： D1D2= (李小勇, 数据库系统概论), (李小勇, 操作系统), (刘方晨, 数据库系统概论), (刘方晨, 操作系统), (王红敏, 数据库系统概论), (王红敏, 操作系统) ,关系数据结构,关系数据结构的形式化定义 关系 D1D2Dn的子集称为在域D1, D2, , Dn上的关系，表示为 ： r(D1, D2, , Dn) 其中，r表示关系的名字，n是关系的目或度(degree)。当 n=1时，称该关系为单元关系；当n=2时，称该关系为二元 关系。 关系是笛卡尔积的有限子集，所以关系也是一个二维表, 表的每行对应于关系的一个元组，表的每列对应于关系的一个域。由于域可以相同，为了区别就必须给每列起一个名字，称为属性(attribute)。n目关系共有n个属性。,关系数据结构,关系数据结构的形式化定义 超码：对于关系r的一个或多个属性的集合A，如果属性集A可以唯一地标识关系r中的一个元组，则称属性集A为关系r的一个超码(superkey) 。 候选码：对于关系r的一个或多个属性的集合A，如果属性集A的任意真子集都不能成为关系r的超码，则称属性集A为候选码(candidate key) 。 主码：若一个关系有多个候选码，则可以选定其中的一个候选码作为该关系的主码 。 空值：所有可能的域的一个取值，表明值未知或不存在。 如果某学生的speciality属性值为null，则表示该学生还没有明确所学专业，或不知道他的所学专业。,举例：Student关系 studentNo studentName sex birthdayspeciality 0701001 李小勇 男 1990-12-21 计算机 0701008 王 红 男 1992-04-26 计算机 0802002 刘方晨 女 1990-11-11 信息系统 0802005 王红敏 女 1990-10-01 信息系统 0703045 王 红 男 1992-04-26 会计学 0703010 李宏冰 女 1992-03-09 会计学 超码：studentNo，studentNo, studentName、studentNo, sex、 studentNo, studentName, speciality、 候选码：studentNo 和 studentName, speciality 与语义有关 主码：studentNo,关系数据结构,关系模式 对于一个二维表，有表头部分和表体部分，表头部分定义了该表的结构，即定义了该表由哪些列构成(假设由n列构成)，每个列的名字和取值范围等；表体就是所有数据行的集合，每一个数据行都是由表头部分规定的n列有关联的取值的集合构成。 对应于关系数据库，表的每一个数据行对应于关系的一个元组，表体对应于关系，关系是元组的集合，关系是值的概念； 表头部分对应于关系模式，关系模式是型的概念，它定义了元组集合的结构，即定义了一个元组由哪些属性构成(假设由n个属性构成)，每个属性的名字和来自的域等.,关系数据结构,关系模式 关系的描述称为关系模式(relation schema)。 形式化地表示为：r(U, D, DOM, F) r为关系名，U为组成该关系的属性名的集合，D为属 性集U中所有属性所来自的域的集合，DOM为属性向 域的映像集合，F为属性间数据的依赖关系集合(即体 现一个元组的各属性取值之间的“关联”性)。 关系模式通常被简记为 ：r(U) 或 r(A1, A2, , An) r为关系名，U为属性名的集合A1, A2, , An ,关系数据结构,关系模式 关系数据库也有型和值之分，型就是关系数据库模式，即它所包含的所有关系模式的集合；值就是这些关系模式在某一时刻所对应的关系的集合，通常就称为关系数据库实例 。 在实际应用中，人们经常把关系数据库模式和关系数据库实例都笼统地称为关系数据库。,举例：学生成绩管理数据库ScoreDB的模式 Class( classNo: char(6), className: varchar(30), institute: varchar(30), grade: smallint, classNum: tinyint ) Student( studentNo: char(7), studentName: varchar(20), sex: char(2), birthday: datetime, native: varchar(20), nation: varchar(30), classNo: char(6) ) Course( courseNo: char(5), courseName: varchar(30), creditHour: numeric, courseHour: int, priorCourse: char(5) ) Score( studentNo: char(7), courseNo: char(5), term: char(5), score: numeric ) 说明：基本数据类型请参见P112113,关系完整性约束条件,实体完整性 若属性集A是关系r的主码，则A不能取空值null。 例如，关系Student，由于studentNo是关系Student的主码，因此它在任何时候的取值都不能为空值null，但其他属性如sex、birthday、speciality等都可以取空值，表示当时该属性的值未知或不存在。 如果主码是由若干个属性的集合构成，则要求构成主码的每一个属性的值都不能取空值。 例如，学生成绩管理数据库ScoreDB中的关系Score，它的主码是studentNo, courseNo, term，因此这3个属性都不能取空值。,关系完整性约束条件,参照完整性 设F是关系r的一个属性(或属性集)，Ks是关系s的主码。如果F与Ks相对应，则称F是关系r参照关系s的外码(foreign key)，简称F是关系r的外码。并称关系r为参照关系，关系s为被参照关系或目标关系。 若属性(或属性集)F是关系r的外码，它与关系s的主码Ks相对应，则对于关系r中的每一个元组在属性F上的取值要么为空值null，要么等于关系s中某个元组的主码值。,关系完整性约束条件,举例： 多对一联系的属性引用 学生成绩管理数据库ScoreDB中，学生关系Student与班级关系Class之间存在多对一的“归属”联系。 多对多联系的联系关系及属性引用 学生成绩管理数据库ScoreDB中，假设每一个学生一个学期可以选修若干门课程，每一门课程同时有若干个学生选修，那么学生关系Student与课程关系Course之间存在多对多的“选修”联系，且课程的开课学期term和修读成绩score为联系属性。 关系内部属性间的引用联系 学生成绩管理数据库ScoreDB中，假设一门课程可能存在先修课程，且关系Course中的priorCourse属性用来存放先修课程的课程编号。课程关系Course中的priorCourse属性需要引用课程关系Course的主码“课程编号”courseNo。,关系完整性约束条件,数据库模式导航图 一个含有主码和外码依赖的数据库模式可以通过模式导航图来表示。,关系完整性约束条件,数据库模式导航图 一个含有主码和外码依赖的数据库模式可以通过模式导航图来表示。 关系Student与关系Class之间存在多对一的“归属”联系(一个班由多个学生组成，一个学生只能归属于某个班)，通过外码classNo实现该联系。 关系Course与关系Student之间存在多对多的“选修”联系。 关系Score的主码是studentNo, courseNo, term，显然同一个学生在同一个学期不允许修读同一门课程多次。 关系Course的priorCourse属性参照本关系的主码courseNo属性,关系完整性约束条件,数据库模式导航图,关系完整性约束条件,数据库模式导航图 一个含有主码和外码依赖的数据库模式可以通过模式导航图来表示 关系Student与关系Class之间、关系Class与关系Institute之间、关系Teacher与关系Institute之间都存在多对一的“归属”联系 。 关系Course的priorCourse属性参照本关系的主码courseNo属性 关系CourseClass与关系Course之间存在多对一的“开课”联系(每个学期一门课程可能开设多个教学班，一个教学班只讲授一门课程)。 关系CourseClass与关系Classroom之间存在多对一的“上课”联系 关系CourseClass与关系Teacher之间存在多对一的“授课”联系 关系CourseClass与关系Student之间存在多对多的“选课”联系 。 关系SC的主码是cClassNo, studentNo，显然同一个学生不允许选修同一个教学班的课程多次。,关系完整性约束条件,用户自定义完整性 任何关系数据库管理系统都应该支持实体完整性和参照完整性 。 用户定义的完整性就是针对某一具体应用要求来定义的约束条件，它反映某一具体应用所涉及的数据必须满足的语义要求。例如， 限制关系中某些属性的取值要符合业务语义要求。 限制关系中某些属性的取值之间需要满足一定的逻辑关系。 限制关系中某属性集上的取值必须唯一。,关系操作,关系操作 关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称为一次一个集合的方式。相应地，非关系数据模型的数据操作方式则为一次一个记录的方式。 关系模型中的关系操作有查询操作和更新操作(包括插入删除和修改)两大类 。查询操作是关系操作中最主要的部分.查询操作又可以分为选择(select)、投影(project)、连接(join)、除(divide)、并(union)、交(intersection)、差(except)、笛卡尔积等。,关系操作,关系操作能力可用两种方式来表示：代数方式和逻辑方式。 关系代数是用代数方式表达的关系查询语言。 关系演算是用逻辑方式表达的关系查询语言。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。 对于关系代数、元组关系演算和域关系演算均是抽象的查询语言，在表达能力上是完全等价的。,目 录,关系模型,关系代数,关系代数,关系代数 关系代数是通过关系代数运算构成的表达式来表达查询。 基本的关系代数运算有选择、投影、集合并、集合差、笛卡尔积和更名等。 关系代数运算是以一个或两个关系作为输入(即运算对象)产生一个新的关系作为结果。,关系代数,传统的集合运算 前提假设：关系r和关系s具有相同的n个属性，且相应的属性取自同一个域。t是元组变量，tr表示t是r的一个元组。 并运算 关系r与关系s的并记作 ：rs = ttrts 其结果关系仍为n目关系，由属于r或属于s的所有元组 组成。,关系代数,传统的集合运算 差 关系r与关系s的差记作 ：r-s = ttrts 其结果关系仍为n目关系，由属于r而不属于s的所有元组组成。 交 关系r与关系s的交记作：rs = ttrts 其结果关系仍为n目关系，由既属于r又属于s的所有元组组成。关系的交可以通过差来表达，即rs = r-(r-s)。,关系代数,传统的集合运算 笛卡尔积 两个分别为n目和m目的关系r和s的笛卡尔积是一个n+m目元组的集合。 元组的前n列是关系r的一个元组，后m列是关系s的一个元组 若关系r有kr个元组，关系s有ks个元组，则关系r和s的笛卡尔积有krks个元组。记作 ： rs = trtstrrtss ,成绩管理数据库ScoreDB的实例数据（P56）,关系Student、Course和Score可分别描述为： Student(学号，姓名，性别，出生日期，所学专业) Course(课程号，课程名称，学时，学分) Score(学号，课程号，学期，成绩) 关系模型要求关系必须是规范化的，即要求关系必须满足一定的规范条件。 最基本的规范条件是： 关系的每一个分量必须是一个不可分的数据项，即不允许表中有表,Student关系 StudentNo StudentName sex birthday native nation classNo 0701001 李小勇 男 1990-12-21 南昌 汉族 CS0701 0701008 王 红 男 1992-04-26 上海 汉族 CS0701 0703010 李宏冰 女 1992-03-09 太原 蒙古族 AC0703 0703045 王 红 男 1992-04-26 北京 汉族 AC0703 0802002 刘方晨 女 1990-11-11 南昌 傣族 ISO802 0802005 王红敏 女 1990-10-01 上海 蒙古族 ISO802,Course关系 CourseNoCourseName creditHour courseHour priorCourse AC001 基础会计 48 3 null CN028大学语文 48 3 nul CS012操作系统 80 5 null CS015 数据库系统 64 4 CS012,Score关系 StudentNocourseNoterm score 0701001CN0280708185 0701001CS0120708288 0701001CS0150809192 0701008AC0010708176 0701008CN0280708186 0701008CS0120708293 0701008CS0150809196 0703010AC0010708192 0703010CN0280708183 0703010CS0120708273 0703045AC0010708152 0703045AC0010809194 0703045 CN028 07081 80 0703045 CS015 08091 82 0802002AC0010809198 0802002CN0280809172 0802002CS0150910185 0802005AC0010910188 0802005CS0120809290 0802005CS0150910187,Class关系 ClassNoClassName instiute grade ClassNum AC0703会计学08(3)班 会计学院 2008 46 CS0701计算机07(1)班 信息学院 2007 48 ISO802信息系统08(2)班 信息学院 2008 43,关系代数,传统的集合运算 对于数据库ScoreDB，笛卡尔积ClassCourse的结果关系为：,关系代数,专门的关系运算 选择 选择操作是在关系r中查找满足给定谓词(即选择条件)的所有元组，记作： P (r) = ttrP(t) P表示谓词(即选择条件)，它是一个逻辑表达式，取值为“真”或“假”。,关系代数,专门的关系运算 选择 例如，在数据库ScoreDB中，查找2007级的所有班级情况 grade=2007(Class),ClassNo ClassName instiute grade ClassNum AC0703 会计学08(3)班 会计学院 2007 46 CS0701 计算机07(1)班 信息学院 2007 48,例如，在数据库ScoreDB中，查找所有1992年及以后出生 的女学生情况 ，year(birthday)=1992sex=女(Student),StudentNoStudentName sex birthday native nation classNo 0703010 李宏冰 女 1992-03-09 太原 蒙古族 AC0703,关系代数,专门的关系运算 投影 关系是一个二维表，对它的操作可以从水平(行)的角度进行，即选择操作；也可以从纵向(列)的角度进行，即投影操作。 关系r上的投影是从r中选择出若干属性列组成新的关系。记作： A(r) = tAtr A为关系r的属性集合。,关系代数,专门的关系运算 投影 例如，在数据库ScoreDB中，查找所有学生的姓名和民族 studentName, nation(Student),例如，在数据库ScoreDB中，查找所有“蒙古族”学生的 姓名和籍贯,StudentName nation 李小勇 汉族 王红 汉族 王宏冰 蒙古族 刘方晨 傣族 王红敏 蒙古族,StudentName native 王宏冰 太原 王红敏 上海,studentName, native(nation=蒙古族(Student),关系代数,专门的关系运算 连接 连接也称为连接。记为A op B，其中A、B分别为关系r和s中的度数相等且可比的连接属性集，op为比较运算符。 连接是从两个关系的笛卡尔积中选取连接属性间满足谓词的所有元组。记作 ： r s = trtstrrtss(r.A op s.B) 连接运算就是从关系r和s的笛卡尔积rs中，选取r关系在A属性集上的值与s关系在B属性集上的值满足连接谓词的所有元组，即 r s =,关系代数,专门的关系运算 连接 连接运算中有两种最常用、最重要的连接，一种是等值连接(equijoin)，另一种是自然连接(natural join)。为等值比较谓词的连接运算称为等值连接。 自然连接是一种特殊的等值连接，它要求两个参与连接的关系具有公共的属性集，并在这个公共属性集上进行等值连接；同时，还要求将连接结果中的重复属性列去除掉，即在公共属性集中的列只保留一次。,关系代数,专门的关系运算 例如，在数据库ScoreDB中，查找所有2008级的“蒙古族”学生的姓名,StudentName 王红敏,分析： nation=蒙古族(Student)可以找到所有蒙古族学生的情况，但关系Student中没有年级的信息，因此必须将关系Student与关系Class关联起来。, 根据模式导航图可知，关系Student与关系Class可通过外码classNo关联起来，这种外码引用关系可通过自然连接表示 Student Class =Student.classNo=Class.classNo(StudentClass), 最后的查询可表达为： studentName(nation=蒙古族(Student) grade=2008(Class),studentName(nation=蒙古族(Student) grade=2008(Class) =studentName(Student.classNo=Class.classNo(nation=蒙古族(Student)grade=2008(Class) =studentName(Student.classNo=Class.classNo(nation=蒙古族grade=2008(StudentClass) =studentName(nation=蒙古族grade=2008Student.classNo=Class.classNo(StudentClass) =studentName(nation=蒙古族grade=2008(Student.classNo=Class.classNo(StudentClass) =studentName(nation=蒙古族grade=2008(Student Class),关系代数,关系代数,例如，在数据库ScoreDB中，查找课程号为“AC001”课程的考试中比学号为“0703045”的学生考得更好的所有学生的姓名和成绩。,分析： 找出学号为“0703045”的学生在课程号为“AC001”的课 程中的成绩元组 (结果关系记为r1)，可表达为：studentNo=0703045courseNo=AC001(Score), 找出选修了课程号为“AC001”课程的所有学生的成绩元 组 (结果关系 记为r2) ，其查询可表达为: courseNo=AC001(Score), 将关系r1与关系r2进行连接 (结果关系记为r3)，其查询可表达为： r1 r1.scorer2.score r2 = r1.scorer2.score(r1r2), 将关系r3与学生关系Student按外码studentNo进行自然连接，并对连接 结果在属性studentName和r2.score上进行投影，其查询可表达为： studentName, r2.score(r3 Student) = studentName, r2.score(r2.studentNo=Student.studentNo(r3Student) = studentName, r2.score(r2.studentNo=Student.studentNo(r1.scorer2.score(r1r2) Student),Score关系 StudentNocourseNoterm score 0701001CN0280708185 0701001CS0120708288 0701001CS0150809192 0701008AC0010708176 0701008CN0280708186 0701008CS0120708293 0701008CS0150809196 0703010AC0010708192 0703010CN0280708183 0703010CS0120708273 0703045AC0010708152 0703045AC0010809194 0703045 CN028 07081 80 0703045 CS015 08091 82 0802002AC0010809198 0802002CN0280809172 0802002CS0150910185 0802005AC0010910188 0802005CS0120809290 0802005CS0150910187,关系代数,关系代数,专门的关系运算 除运算 例如，需要查找修读过信息学院开设的所有课程的学生学号，如何表达查询？,分析：查找出修读过信息学院课程的所有学生 r1 = studentNo, courseNo(courseNo LIKE CS%(Score),找出信息学院开设的所有课程 r2 = courseNo(courseNo LIKE CS%(Course),StudentNo courseNo 0701001CS012 0701001CS015 0701008CS012 0701008CS015 0703010CS012 0703045 CS015 0802002CS015 0802005CS012 0802005CS015,CourseNo CS012 CS015,关系代数,专门的关系运算 （象集的概念见P58）, 比较图2-20(a)和(b) ，修读过信息学院开设的所有课程的学生 就是关系r1中满足“courseNo列包含关系r2的所有行”的那些学生 。,关系代数,专门的关系运算 设关系r(R)和s(S)，属性集S是R的子集，即SR，则关系rs是关系r中满足下列条件的元组在属性集R-S上的投影： trr，记 x= trR-S，则关系r中属性集R-S的取值x的象集Sx包含关系s。记作 rs = trR-StrrsSx ,关系代数,专门的关系运算 例如，关系数据库ScoreDB 中，求以下结果 Score(courseNo(courseNo=AC001(Course) 的结果为：, Score(courseNo(courseNo=CN028(Course)的结果为：,StudentNoterm score 0701008 07081 76 0703010 07081 92 0703045 07081 52 0703045 08091 94 0802002 08091 98 0802005 09101 88,StudentNoterm score 0701001 07081 85 0701008 07081 86 0703010 07081 83 0703045 07081 80 0802002 08091 72,Score关系 StudentNocourseNoterm score 0701001CN0280708185 0701001CS0120708288 0701001CS0150809192 0701008AC0010708176 0701008CN0280708186 0701008CS0120708293 0701008CS0150809196 0703010AC0010708192 0703010CN0280708183 0703010CS0120708273 0703045AC0010708152 0703045AC0010809194 0703045 CN028 07081 80 0703045 CS015 08091 82 0802002AC0010809198 0802002CN0280809172 0802002CS0150910185 0802005AC0010910188 0802005CS0120809290 0802005CS0150910187,Score关系 StudentNocourseNoterm score 0701001CN0280708185 0701001CS0120708288 0701001CS0150809192 0701008AC0010708176 0701008CN0280708186 0701008CS0120708293 0701008CS0150809196 0703010AC0010708192 0703010CN0280708183 0703010CS0120708273 0703045AC0010708152 0703045AC0010809194 0703045 CN028 07081 80 0703045 CS015 08091 82 0802002AC0010809198 0802002CN0280809172 0802002CS0150910185 0802005AC0010910188 0802005CS0120809290 0802005CS0150910187,关系代数查询综合举例,给定一个查询需求，构造其关系代数表达式的步骤 明确该查询涉及到哪些属性； 明确该查询涉及到哪些关系； 根据数据库模式导航图，通过多对一联系(或一对多联系)把所有涉及的关系连接起来，每一个多对一联系(或一对多联系)都可以表示为外码属性的自然连接。,关系代数查询综合举例,例如，ScoreDB数据库中，查找“蒙古族”学生所修各门课程的情况，要求输出学生姓名、课程名和成绩。 分析： 该查询共涉及4个属性，分别是民族nation、姓名studentName课程名courseName和成绩score，其中，nation属性用于选择条件notion=蒙古族。 共涉及3个关系，分别是学生关系Student、课程关系Course和成绩关系Score。 成绩关系Score分别通过外码studentNo和courseNo与学生关系Student和课程关系Course建立多对一的联系 。,studentName, courseName, score(nation=蒙古族(Student Score) Course),关系代数查询综合举例,例如，ScoreDB数据库中，查找2007级的“南昌”籍同学修读 了哪些课程，要求输出学生姓名、课程名。 分析： 该查询共涉及4个属性，分别是年级grade、籍贯native、姓名studentName和课程名courseName，其中年级grade和籍贯native用于选择条件。 共涉及3个关系，分别是班级关系Class、学生关系Student和课程关系Course。 学生关系Student与班级关系Class之间是多对一联系 ；学生关系Student和课程关系Course之间是多对多联系，并借助关系Score才能建立。因此，该查询还需涉及Score关系。,studentName, courseName(grade=2007Class native=南昌Student) Score) Course),关系代数查询综合举例,例如，SCDB数据库中，查找“吴文君”老师教过的2008级 学生的姓名。 分析： 该查询共涉及3个属性，分别是职工名teacherName、年级grade和学生姓名studentName ，职工名teacherName和年级grade都是用于选择条件。 共涉及3个关系，分别是教师关系Teacher、班级关系Class和学生关系Student。 学生关系Student与班级关系Class之间是多对一联系 ；学生关系Student和教师关系Teacher之间是多对多联系，这种多对多联系不是直接通过一个联系关系就能建立 。,studentName(grade=2008Class Student) SC) CourseClass) teacherName=吴文君Teacher),关系代数查询综合举例,例如，SCDB数据库中，查找“吴文君”老师在“操作系统” 课程中教过的“信息学院”学生的姓名。 分析： 该查询共涉及4个属性，分别是职工名teacherName、课程名courseName、学院名称instituteName和学生姓名studentName，职工名teacherName、课程名courseName和学院名称instituteName都是用于选择条件。 共4个关系，分别是教师关系Teacher、课程关系Course、学院关系Institute和学生关系Student。 学生关系Student与班级关系Class之间是多对一联系。班级关系Class又与学院关系Institute之间是多对一联系 。学生关系Student和教师关系Teacher之间是多对多联系，这种多对多联系不是直接通过一个联系关系就能建立。,studentName( ( (instituteName=信息学院Institute Class) Student) SC) (CourseClass courseName=操作系统Course) teacherName=吴文君Teacher),本章结束！,请同学们对本章内容进行复习、总结！,