第二章关系数据库 2.1关系数据库概述 2.2关系数据结构 2.3关系的完整性 2.4关系代数 2.5关系演算** 2.6关系数据库管理系统

2.1关系数据库概述 关系数据库系统是支持关系模型的数据库系统 关系理论是建立在集合代数理论基础上的，关系的定义和各种操作运算可以用集合代数给出 关系模型的三要素 关系数据结构：二维表 关系操作：选择、投影、连接、除、并，交、差等查询以及增、删、改 完整性约束 ：实体、参照、自定义

关系数据语言 关系代数语言 ISBL 关系演算语言 具有关系代数和关系演算双重特点的语言 SQL 元组关系演算语言 ALPHA，QUEL 域关系演算语言 QBE 具有关系代数和关系演算双重特点的语言 SQL

2.2关系数据结构 2.2.1关系 域：域是一组具有相同数据类型的值的集合。值的个数称为域的基数 笛卡儿乘积 :给定一组域：D1，D2，……Dn，域可以相同，定义D1D2……Dn的笛卡儿乘积为：D1×D2×……×Dn＝{(d1，d2，……dn) |di∈Di，i＝1，2，……n} ; （d1，d2，……dn）称为一个元组 关系(Relation)：笛卡儿乘积D1×D2×……×Dn的任一子集D’，称作D1，D2，……Dn上的关系。 用R（D1，D2……Dn）来表示 D’中的每个元素（d1，d2，……dn）是关系的一个元组 实际应用中关系往往是笛卡儿乘积中有意义的子集构成 n＝1是单元关系/一元关系；n＝2是二元关系

举例 域 笛卡儿乘积 关系 性别集＝{男、女}。基数＝2 月份集＝{1，2，3，4，5，6，7，8，9，10，11，12}，基数＝12 D1＝姓名集合＝{赵一平，钱峰，孙英} D2＝性别集合＝{男，女} D3＝年龄集合＝{16，17，18} 关系 姓名 性别 年龄 赵一平 男 16 钱峰 17 孙英 女

2.2.2关系模式 关系的描述称为关系模式（Relation schema）,一般表示为R(U,D,DOM,F) 其中，R是关系名，U是组成该关系的属性集合，D为属性组U中属性所来自的域，DOM是属性向域的映象集合，F是属性间数据的依赖关系集合。 2.2.3关系数据库 在一个给定的现实世界领域里，所有实体及实体间的联系的关系所构成的集合是一个关系数据库 关系数据库有型和值之分：关系数据库的型也称关系数据库模式，是对关系数据库的描述它包括若干域的定义以及在这些域上定义的若干关系模式；关系数据库的值也称为关系数据库，是这些关系模式在某一时刻对应的关系的集合 关系数据库的值与关系数据库模式通称为关系数据库

2.3关系的完整性 实体完整性 参照完整性 自定义完整性 若属性A是基本关系R的主属性，则A不能取空值 若属性（或属性组）F是基本关系R的外码，它与基本关系S的主码Ks相对应（关系R、S不一定是不同的关系），则对于R中的每一个元组在F上的取值必须: 取空值（F的每个属性值均取空值） 等于S中某个元组的主码值 ] 自定义完整性

2.4关系代数 关系代数由一组关系运算组成，是对于关系的操作集。关系运算以一个或多个关系作为操作的对象，运算结果是一个新的关系。用关系运算实现查询 关系代数运算符 集合运算符：∪（并）－（差）∩（交）×（笛卡儿积） 专门运算符：σ选择 П 投影  连接 ÷ 除 比较运算符： > ≥ < ≤ = ≠ 逻辑运算符： 非 ∧与 ∨或 常用的关系运算 交、并、差、笛卡儿积、投影、选择、连接、除 基本关系运算有 并、差、笛卡儿积、投影、选择 同类关系：具有相同的度，且两个关系每个属性属同一个域

2.4.1传统的集合运算 假设： Name Sex Age Zhang F 22 Wang M 25 Lu 37 Chen 27 S R Name Sex Age Zhang F 22 Wang M 25 Lu 37 Chen 27 S Name Sex Age Zhang F 22 Wang M 25 Lu 30 Sun 28

并（Union）： 同类关系R和S的并记为R∪S，或R union S 定义：R∪S={t|t∈R ∨ t∈S}注意去除重复元组 R∪S Name Sex Age Zhang F 22 Wang M 25 Lu 37 Chen 27 30 Sun 28

交（Intersection） 同类关系R和S的交记为R∩S，或R intersect S 定义：R∩S＝{ t|t∈R ∧ t∈S } R－（R－S） R∩S Name Sex Age Zhang F 22 Wang M 25

差（Minus/Difference） 同类关系R和S的差记为R－S或R minus S 定义：R－S＝{ t|t∈R ∧ tS } Name Sex Age Lu M 37 Chen F 27

笛卡儿积（Cartesian Product） 关系R和S的笛卡儿积记为R×S 定义：R×S＝{ t⌒s|t∈R， s∈S } R S CNo CN C-11 OS C-21 DB SNo SN Age S-01 Huang 21 S-21 Lin 20 S-30 Shao 22 R×S CNo CN SNo SN Age C-11 OS S-01 Huang 21 S-21 Lin 20 S-30 Shao 22 C-21 DB

2.4.2专门的关系运算 引入以下记号 : 设关系模式R（A1，A2，……An），它的一个关系为Rt，t∈Rt表示t是Rt的一个元组。t[Ai]则表示元组t中相应于Ai的一个分量 若A＝{Ai1，Ai2，……Aik}是A1，A2，……An的一部分，k<=n，则A称为属性列（组）或域列。t[A]=（t[Ai1]，t[Ai2]，……t[Aik]）表示元组在属性列A上诸分量的集合 R为n元关系，S为m元关系。tr∈R，ts∈S，tr ⌒ ts称为元组的连接（Concatenation）。它是一个m＋n列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组 给定一个关系R（X，Z），X和Z为属性组，定义：当t[X]=x时，x在R中的象集（image set）为 Zx＝{t[Z]|t∈R，t[X]=x}，表示R中属性组X上值为x的诸元组在Z属性组上的分量的集合

投影（Projection） 关系R上的投影是从R中选择出若干属性，并且去掉重复元组组成一个新关系，属于单目运算 记作： A(R)＝{t[A]| t∈R } A为R中的属性列 假设Student SNo SName Sex Age S01 Wang F 17 S02 Zhang M 20 S03 Lin 18 S04 Sun 19 SName Age Wang 17 Zhang 20 Lin 18 Sun 19 Sna=Sname，Age(Student)

选择（Selection） 又称限制（Restriction），在给定的关系R中，抽出满足条件的元组，组成一个新关系，新关系与原关系同类，是原关系一个子集 记做：  F(R)={t| t∈R ∧ F（t）=’真’ } F表示条件 Sa18＝  age>=18(Student) SNo SName Sex Age S02 Zhang M 20 S03 Lin 18 S04 Sun F 19

等值连接（equi－join）：为“＝”时称为等值连接 从两个关系的笛卡儿乘积中选取属性满足一定条件的元组，组成新的关系 记做：R  S ＝{tr⌒ts| tr∈R ∧ts∈S ∧ tr[A]ts[B]}  AB AB (R×S) AB表示R上的属性A和S上的属性B满足条件，是比较运算符，A、B的度数相等且可比。这里假设AB分别在R、S关系的第i、j列，R度为r 等值连接（equi－join）：为“＝”时称为等值连接 记：R  S ＝{tr⌒ts| tr∈R ∧ts∈S ∧ tr[A]＝ts[B]} A=B 自然连接（Natioal Join）：两个关系中具有相同的属性，并且在相同的属性上做等值连接。自然连接需要取消重复列，而等值连接不需要 。 记：R  S ＝{tr⌒ts| tr∈R ∧ts∈S ∧ tr[A]＝ts[A]}

假设 R S A C D 30 C1 D3 40 C2 50 C3 D1 10 C4 B E F 20 E1 F1 50 E2 F3 40 E3 R  S A>B A B C D E F 30 20 C1 D3 E1 F1 40 C2 50 C3 D1 E3

除法（Division） 给定关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性组，R中的Y与S中的Y可以不同属性名，但必须有相同的域。记R÷S。令P（X）＝R÷S，则P是R中满足以下条件的元组在X属性列上的投影：元组在X上的分量值x的象集Yx包含S在Y上投影的集合 记做：R÷S＝{tr[X]|tr∈R ∧ YxY(S)} R÷S  X(R)－X((X(R)×Y(S))－R)

b1 c2 b2 c1 c3 b2 c3 b3 c7 b4 c6 b6 c6 假设 R S A B C a1 b1 c2 a2 b3 c7 D b1 c2 d1 b2 c1 c3 d2 R÷S 象集: Yx＝a1 Yx＝a2 Yx＝a3 Yx＝a4 A a1 b1 c2 b2 c1 c3 b2 c3 b3 c7 b4 c6 b6 c6

外连接（Outer Join） 外部并（Outer Union） 半连接（Semijoin） 如果R和S在做自然连接时，把该舍弃的元组也保存在新关系中，在新增加的属性上填空值（null），这种操作称为“外连接”。如果把R中该舍弃的元组保留在新关系中称左连接；把S中该舍弃的元组保留在新关系中称右连接 外部并（Outer Union） 若关系R和S不同类，则新关系的属性由R和S的属性组成，公共属性只取一次，新关系的元组由属于R或S的元组构成，新增的属性上均填空（null） 半连接（Semijoin） 关系R和S的半连接定义为R和S的自然连接在关系R的属性集上的投影

假设 R S A B C a b c f d B C D b c d e a f g R Outer Join S R left Outer Join S A B C D a b c d e f null g A B C D a b c d e f null

R right Outer Join S R Outer Union S A B C D a b c d e null f g A B C D a b c null f d e g R Semijoin S  R(R  S) S Semijoin R  S（R  S） A B C a b c d B C D b c d e a

检索选修课程名为Maths的学生学号与姓名 2.4.3*关系代数运算应用举例 假设 S(S＃,SN,SSEX,SAGE) C(C＃,CN,TEACHER) SC(S＃,C＃,GRADE) 检索学习课程号为C2的学生学号与成绩 S#，GRADE( C#=’C2’(SC)) 或1，3( 2=’C2’(SC)) 检索学习课程号为C2的学生学号与姓名 S#，SN( C#=’C2’(S  SC)) 检索选修课程名为Maths的学生学号与姓名 S#，SN( CN=’Maths’(S  SC  C))

检索所学课程包含学生S3所学课程的学生学号 检索选修课程为C2或C4的学生学号 S#( C#=’C2’ ∨ C#=’C4’(SC) ) 检索至少选修课程为C2和C4的学生学号 S#( 1＝4 ∧ 2=’C2’ ∧ 5=’C4’(SC×SC) 检索不选修C2课程的学生姓名与年龄 SN，SAGE (S)－SN，SAGE( C#=’C2’(SC  S)) 检索选修全部课程的学生姓名 SN(S (S#，C#(SC)÷ C#(C) ) ) 检索所学课程包含学生S3所学课程的学生学号 S#，C#(SC)÷ C# ( S#=’S3’(SC))

2.4.4关系代数式的等价规则 1.连接、笛卡尔积交换律 2.连接、笛卡尔积结合律 E1×E2 ≡ E2×E1 E1  F E2 ≡ E2  F E1 2.连接、笛卡尔积结合律 (E1×E2) ×E3 ≡ E1×(E2×E3) (E1  E2)  E3 ≡ E1 (E2  E3) (E1  F1 E2)  F2 E3 ≡ E1  F1 (E2  F2 E3)

3.投影的串接定律 4.选择的串接定律 5.选择与投影的交换律 例：  A ( R.A=S.B(R×S)) A1,A2,…An(Ak1,Ak2,…Akm (R)) ≡ A1,A2,…An (R) A1,A2,…An是Ak1,Ak2,…Akm 的子集 4.选择的串接定律  F1( F2(R)) ≡  F1^F2(R) 5.选择与投影的交换律  A1,A2,…An (F(R)) ≡  F(A1,A2,…An (R)) A1,A2,…An (F(R)) ≡  A1,A2,…An (F(A1,A2,…An,B1,B2,..Bn (R))) 例：  A ( R.A=S.B(R×S)) ≡  A ( R.A=S.B( A,B (R×S))) ≡  A ( R.A=S.B( A(R)×B(S)))

6.选择对笛卡尔积的分配率  F ( E1×E2) ≡  F1 ( E1)×  F2 ( E2) F=F1^F2,F1只涉及E1，F2只涉及E2  F ( E1×E2) ≡  F ( E1)× E2 F只涉及E1  F ( E1×E2) ≡  F2( F1 ( E1)× E2) F1只涉及E1，F2涉及E1，E2

7.选择对并的分配率 8.选择对差的分配率 9.投影对笛卡尔积的分配率 10.投影对并的分配率  F ( E1∪E2) ≡  F1 ( E1)∪  F2 ( E2) 8.选择对差的分配率  F ( E1 - E2) ≡  F1 ( E1) -  F2 ( E2) 9.投影对笛卡尔积的分配率 A1,A2,…An,B1,B2,..Bn (E1×E2) ≡ A1,A2,…An(E1) ×  B1,B2,..Bn (E2) A1,A2,…An是E1属性，B1,B2,..Bn是E2 属性 10.投影对并的分配率 A1,A2,…An(E1∪E2) ≡ A1,A2,…An(E1)∪A1,A2,…An(E2)

11.选择对自然连接的分配率 12.选择与连接操作的结合率  F ( E1  E2) ≡  F1 ( E1)   F2 ( E2) F=F1^F2,F1只涉及E1，F2只涉及E2 12.选择与连接操作的结合率  F ( E1×E2) ≡ E1 F E2 F形如E1.A  E2.B  F1 ( E1  F2 E2) ≡ E1  F1^F2 E2 F1,F2形如E1.A  E2.B

利用规则优化查询 例：设学生选课系统中，学生关系S有1000条记录，每个学生平均选课10门，则SC关系有10000条记录，课程关系C有1000条记录。若需要查询学生“王芳”所选修课程的成绩在85分以上的课程名。 设 F1表示S.sno=SC.sno F2表示SC.cno=C.cno F3表示S.sn=‘王芳’ F4表示SC.grade>=85  cn(F1^F2^F3^F4(S×SC×C)) 1010条连接记录O(1010)  cn(F3^F4(S F1SC F2C)) 104条记录，运算O(1010)  cn(F3(S)F4(SC)  C)) <=10条记录，运算O(104)

优化过程  cn (F1^F2^F3^F4(S×SC×C)) //式 =  cn (F3^F4F2(F1((S×SC)×C))) //规则4，2 =  cn (F3^F4F2(F1(S×SC)×C)) //规则6 =  cn (F3^F4 F2 ((S  SC)×C)) //规则12 =  cn (F3^F4 ((S  SC)  C)) //规则12 式 =  cn (F3(S)  F4(SC)  C) //规则11 式

基于语法树优化 检索选修DB课程的女生学号及姓名。  sno,sname(cname=‘db’^sex=‘F’(S.sno=SC.sno^SC.cno=C.no (S×SC×C)))  sno,sname cname=‘db’^sex=‘F’ S.sno=SC.sno^SC.cno=C.no × SC C S 初始语法树

 sno,sname  sno,sname S.sno=SC.sno cname=‘db’^sex=‘F’ S.sno=SC.sno^SC.cno=C.no × SC C S  sno,sname sex=‘F’ S.sno=SC.sno × SC C S cname=‘db’ SC.cno=C.no 条件分解 条件下移

 sno,sname  sno,sname sex=‘F’ S.sno=SC.sno × SC C S cname=‘db’ SC.cno=C.no 笛卡尔积和选择合成连接  sno  sno,cno  cno  sno,sname sex=‘F’ S.sno=SC.sno × SC C S cname=‘db’ SC.cno=C.no 投影前移  sno  cno  sno,cno

 sno,sname  sno  sno,sname sex=‘F’  cno  sno,cno S cname=‘db’   sno  sno,sname  sex=‘F’  sno,cno  cno S cname=‘db’ SC C 最终语法树

2.5关系演算** 2.5.1元组关系演算语言ALPHA 2.5.2域关系演算语言QBE

2.6关系数据库管理系统 关系数据库管理系统简称关系系统 一个数据库管理系统可成为关系系统的最小条件 关系数据库（即关系数据结构） 支持选择、投影和连接运算 E.F.Codd思想对关系系统的分类（P63 图2-5） 表式系统：仅只是关系数据结构，不支持集合级操作 最小关系系统：支持关系结构和选择、投影、连接集合操作 关系完备系统：支持关系结构和所有关系代数操作 全关系系统：支持关系模型的所有特征。