第二讲 关系代数和数据依赖概念

1 关系代数

    1970年IBM公司的E.F.Cood博士在论文“一个通用关系式数据库系统的模型”中首先提出了关系模型，它提供了格式化数据库系统难以做到的数据独立性和数据相容性。此模型后来又由Codd加以改进，被许多人认为是一切数据库系统的未来。

    关系数据库之所以发展如此之快，因为关系数据库的模型简明，便于用户理解使用方便等等特点，更重要的是，关系数据库有着网状和层次数据库没有的数学基础----关系代数，可以利用关系代数对表格进行任意的分割和组装，随机地产生用户所需要的各种新表，这为关系数据的发展提供了基础和保证。

1.1 基本概念

术语

定义 给定一组集合D₁，D₂，...，D_n，它们可以是相同的，若R是这样一个有序n元组：

则称R是对于这n个集合的一个关系，并称集合D₁，D₂，...，D_n为关系R的域，称n为关系的度。

1.2 关系运算

在关系模型中，实体以及实体间的联系采用了单一数据结构----关系来表示。对数据的操作就是对关系的运算。关系运算的形式可分为两大类：

（1）关系代数：把关系看作集合，以关系为运算对象的关系运算。
（2）关系演算：使用数理逻辑谓词演算概念的关系运算。

1.2.1 并(Union)

    设R和S为同类关系，即具有相同的度和相应属性在相同的域中取值，但并不要求属性名一致，则关系R和S的并由属于R或属于S的所有元组构成，记作RÈS。

例：

SQL语句:    Select * from R Union Select * from S

1.2.2 交(Intersection)

    设R和S为同类关系，则关系R和S的交由属于R同时属于S的所有元组构成，记作RÇS。

例：

SQL语句：    Select R.A,R.B,R.C from R,S where R.A=S.A and R.B=S.B and R.C=S.C

1.2.3 差(Difference)

    设R和S为同类关系，则关系R和S的差由属于R但不属于S的所有元组构成，记作R-S。

例：

1.2.4 笛卡尔积(Cartesian Product)

    设R为k₁元关系，S为k₂元关系，则关系R和S的笛卡尔积是一个（k₁+k₂）元的关系，其中每个元组的前k₁个分量取自R中的一个元组，后k₂个分量取自S中的一个元组，记作R´S。

例：

SQL语句：    Select * from R,S

1.2.5 投影(Projection)

    设R为k元关系，A_i1，A_i2，...，A_im分别是它的第i1，i2，...，im个属性，则关系R在A_i1，A_i2，...，A_im上的投影是一个m元关系，其属性为A_i1，A_i2，...，A_im，记作：

p_i1,i2,…,im（R）

    投影的基本思想是从一个关系中选择我们需要的属性成分，并按要求排列组成一个新的关系，新的关系的各属性值来自原来关系中相应的属性值，并去掉重复元组。

例：对关系R，做投影 p_3,1（R），得

SQL语句：    Select Distinct C, A from R

1.2.6 选择(Selection)

    设F是一个命名公式，则在关系R上的F选择是在R中挑选满足F的所有元组，组成一个新的关系，这个新的关系是R的一个子集，记为：s_F（R）

其中F由下列三部分组成：运算对象、算术比较符、逻辑运算符。

例：对关系R，做选择 s_{[1]=a V [3]=f}（R），得

SQL语句：    Select * into R1 from R where A='a' or C='f'

1.2.7 连接(Join)

    连接运算把两个关系的共同的域按某种条件约束结合在一起形成新的关系。设R为k₁元关系，S为k₂元关系，算术比较符是q。则关系R的第i列和关系S的第j列的连接定义为：

    从定义可以看出，连接运算是从两个关系的笛卡尔积中选取满足一定连接条件的元组的集合，连接的结果是一个（k₁+k₂）元的关系。也称为一般连接。

例：

SQL语句：（c）Select * from R, S where R.A < S.D

         （d）Select * from R, S where R.C = S.C

1.2.8 自然连接(Natural Join)

    当两个关系R和S的某些列具有相同的属性名时，可利用这些同名属性列总的相同值作为连接条件将两个关系连接起来，构成自然连接。在连接后的关系中，不仅含有R与S不同的属性列，而且含有相同的属性列，其元组的数目由相同属性列中的相同值决定。

    设R是属性名组为（A₁，A₂，...，A_m，...，A_k1）的k₁元关系，S是属性名组为（A₁，A₂，...，A_m，B_m+1，...，B_k2）的k₂元关系，其中A₁，A₂，...，A_m是同名属性列，则R和S的自然连接定义为...。

进行自然连接的步骤如下：（1）计算R´S；（2）选择A_i·R=A_i·S的所有元组；（3）去掉重复属性。

可以看出，如果两个关系没有公共属性，自然连接就是笛卡尔积。

例：

SQL语句：    Select Distinct R.A, R.B, R.C, S.D from R,S where R.B=S.B and R.C=S.C

1.2.9 除(Division)   

    除运算是指用一个（m+n）度的关系R除以一个n度关系S，运算结果生成一个m元的新关系。这里R的第(m+i)个属性和S的第i个属性（i=1，...，n）必须是在相同的域上定义。当把R的前m个属性看作一个组合属性x，后n个属性看成一个组合属性y，则S也可类似地看成一个组合属性y。这样以S中的y值来对R进行分组，当组中含有y值时，则组中的x值便构成了R除以S的一个元组。R除以S的数学表达式为：

R¸S=p_a(R)-p_a(p_a(R)´S-R)

其中a为关系R中除去与S关系相同的其余属性。

例：

按公式分解计算

关系代数对数据库的数据操作是完备的，利用关系代数可以实现一切数据操作。

2 函数依赖概念

    数据依赖是通过一个关系中数据间值的相等与否体现出来的数据间的相互关系，是现实世界属性间相互关系的抽象，是数据内在的性质。

    数据依赖中最重要的是函数依赖（Functional Dependency）。

2.1 函数依赖

    定义：设有一关系模式R（A₁,A₂,…,A_n),X和Y均为（A₁,A₂,…,A_n)的子集，对于R的值r来说，当其中任意两个元组u,v中对应于X的那些属性分量的值均相等时，则有u,v中对应于Y的那些属性分量的值也相等，称X函数决定Y，或Y依赖于X，记为X->Y。

例：有关系，学生（学号S#，姓名SN，系名SD），子集X（学号S#），子集Y（系名SD）。

每个学生有唯一的一个学号，学生中可以有重名的姓名，每个学生只能属于一个系，每个系有唯一的系代号。有此，可以找出学生关系模式中存在下列函数依赖：

S#->SN；S#->SD

例：有关系，学校简况(学号S#，系名SD，系主任MN，课程CN，成绩G)。可写出函数依赖：

S#->SD；SD->MN；S#,CN->G

根据函数依赖的不同性质，函数依赖可分为完全函数依赖、部分函数依赖和传递函数依赖。

2.2 完全函数依赖

定义：在R(U)中，如果X->Y，对于X的任意一个真子集X’,都有X’不能决定Y，则称Y对X完全函数依赖，记为XY 。

例：（S#,CN）G

2.3 部分函数依赖

定义：在R(U)中，如果X-> Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记为XY 。

例：（S#,CN）G，但（S#,CN）SD

2.4 传递函数依赖

定义：在R(U)中，当且仅当X-> Y，Y->Z时，称Z对X传递函数依赖。

例：描述学生（S#）、班级（SB）、辅导员（TN）的关系U(S#,SB,TN)。一个班有若干学生，一个学生只属于一个班，一个班只有一个辅导员，但一个辅导员负责几个班。根据现实世界可得到一组函数依赖：

F={S#->SB，SB->TN}

学生学号决定了所在班级，所在班级决定了辅导员，所以辅导员TN传递函数依赖于学生学号S#。

    数据依赖还包括多值依赖和连接依赖两种形式。

2.5 关键字（码）

定义：设K为R(U)中的属性或属性组合，若KU，则称K为R的（侯选）关键字，也称为码。若（候选）关键字多于一个，则选定其中的一个作为主关键字。