第4章_关系数据模型及其运算基础

-1-第4章关系数据模型及其运算基础在本课程的1.2.3节中已经介绍了关系模型。关系模型是由：关系数据模型结构—表、关系操作集合和关系的三类完整性约束组成的。其中表和三类完整性已作了详细的介绍。关系的操作也通过对SQL语言的学习，有了大致的了解。评价实际关系语言的理论是关系代数和关系演算。实际的关系语言，有的是基于关系代数的，有的是基于关系演算的，有的是介于两者之间的，我们前面学习过的结构化查询语言SQL就是介于关系代数和关系演算之间的一种关系语言。关系演算又分为元组关系演算和域关系演算两种。理论已证明关系代数、元组关系演算和域关系演算三者是等价的。本章重点介绍的是关系代数，对元组关系演算和域关系演算只作一般性介绍。4.1关系模型的基本概念关系操作是集合操作，操作的对象是集合，操作的结果也是集合。因此，关系操作的基础是集合代数。4.1.1笛卡尔积（CartesianProduct）1、域（Domain）：域是一组具有相同数据类型的值的集合。例如：自然数、整数、实数、长度小于8的字符串等都可以是域。2、笛卡尔积：给定一组域D1，D2，…，Dn，这些域中可以有相同的元素。D1，D2，…，Dn的笛卡尔积为：niDddddiin,,2,1,|,,,DDD21n21其中：每一个元素nddd,,,21叫作一个n元组（n-tuple）或简称元组（Tuple）；元组中的每一个值id叫作该元组在相应域Di上的一个分量（Component）；每一个元组是组成该元组各分量的有序集合（强调各分量的有序性）；若niDi,,2,1为有限集，其基数（Cardinalnumber）为nimi,,2,1，则-2-nDDD21的基数M为:niimM1＝m1×m2×…×mn基数即集合中元素的个数；笛卡尔积实际上就是一个二维表。表中每一行对应一个元组，每列对应一个域。参看P65例4.14.1.2关系（Relation）笛卡尔积nDDD21的任意一个子集,称为在域D1，D2，…，Dn上的一个n元关系，简称关系，又称为表。每个关系都有一个名字称为关系名。关系是笛卡尔积的一个子集，所以关系也是一个二维表。二维表：表名、列、列名、表中一行、关系：关系名、属性、属性名、一个元组、以上是二维表与关系的对应关系。一个属性的取值范围Di（i＝1，2，…n）称为该属性的域（Domain）。不同的属性可以有相同的域。从第2章可见，实际的关系有三种类型：基本表、查询表和视图表。其中基本表是实际存在的表；查询表是查询结果对应的表；视图表是从基本表和／或已定义的视图中导出的表，是虚表，只有存放在数据库中的定义，而实际上不存在。关系的其它术语，如主码、主属性、外部码等在1.2.3节中已经作了详述，在此不再重复。4.2关系模式前已学过，一个关系的关系模式是该关系的关系名及其全部属性名的集合，一般表示为：关系名（属性名1，属性名2，…，属性名n）可见：关系模式是型，是对关系的描述。关系是值，是关系模式的具体体现；关系模式是稳定的。关系是变化的，关系是某一时刻关系模式的内容。完整的关系模式应该定义为：R（U,D,dom,F）其中：R为关系名；U为该关系所有属性名的集合；D为属性组U中属性所来自的域的集合；-3-Dom为属性向域映象的集合；F为属性间数据依赖关系的集合。关系模式常简记为：R（U）或R（A1，A2，…，An）其中：R为关系名，Ai（i=1,2,…,n）为属性名。域名及属性向域的映象一般即为定义中属性的类型和长度。4.3关系数据库关于关系数据库，记住以下三点：一个应用范围内，所有关系的集合就形成了一个关系数据库。对关系数据库的描述称为关系数据库的模式，也称为关系数据库的型。全部关系模式在某一时刻的值的集合即全部关系的集合为关系数据库的值，简称为关系数据库。关于关系数据库的其它概念我们将在以后的学习中逐渐领会。4.4关系代数关系代数运算的对象是关系，运算的结果也是关系。关系代数的运算可分为传统的集合运算和专门的关系运算两类。关系代数用到的运算符包括四类：集合运算符：并（∪）、差（－）、交（∩）和广义的笛卡尔积（×）专门的关系运算符：投影（π）、选择（）、连接（）和除（÷）比较运算符：＞、≥、＜、≤、＝、≠逻辑运算符：∨（或）、∧（与）、（非）后两种运算符是用来辅助前两种运算符进行操作的。4.4.1传统的集合运算传统的集合运算是二目运算。设关系R和S的目都是n（都有n个属性），且相应的属性取自同一域，则1、关系R和S的并（Union）为：RS＝｛t|tR∨tS｝含义：任取元组t，当且仅当t属于R或t属于S时，t属于R∪S。R∪S是一个n目关系。2、R和S的差（Difference）为：R－S＝｛t|tR∧tS｝含义：当且仅当t属于R并且不属于S时，t属于R－S。R－S也是一个n目关系。3、R和S的交（Intersection）为：R∩S＝｛t|tR∧tS｝-4-含义：当且仅当t属于R又属于S时，tR∩S。4、广义笛卡尔积：（ExtendedCartesianProduct）广义笛卡尔积不要求参加运算的两个关系具有相同的目。设R为n目关系，S为m目关系，则R和S广义笛卡尔积为R×S＝｛tr^ts|trR∧tsS｝tr^ts表示由两个元组tr和ts前后有序连接而成的一个元组。任取元组tr和ts，当且仅当tr属于R且ts属于S时，tr和ts的有序连接即为R×S的一个元组。R和S的广义笛卡尔积是一个（n+m）目的关系。其中任何一个元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有K1个元组，S有K2个元组，则R×S有K1×K2个元组。实际操作时，可从R的第一个元组开始，依次与S的每一个元组组合，然后，对R的下一个元组进行同样的操作，直至R的最后一个元也进行同样的操作为止。即可得到R×S的全部元组。4.4.2专门的关系运算专门的关系运算包括：投影、选择、连接、自然连接和除等操作，其中前两者为一元操作，后三者为二元操作。1、投影（Projection）表示格式：∏属性名表（R）式中：属性名表中的所有属性都是关系R的属性，其中属性名也可以用属性在原关系中的序号代替。R：关系名，即表名。表示原关系R中各元组只保留属性名表中的诸分量后形成的新的关系。投影的特点是：取消了原关系中的某些列；去掉重复的元组；还可以改变属性的排列次序。2、选择（Selection）选择是在一个关系中，选取符合某给定条件的全体元组，生成新的关系。记为：条件（R）-5-例:Dno=’01’∧5=’1’(Employee)上例是从职工表中选取部门＝‘01’且第5列婚否＝‘1’的元组组成的结果关系。特点：结果关系中所有属性名都是原关系的属性名；结果关系中各元组都是原关系中的元组。不难证明，下列等式是成立的。条件1（条件2（R））＝条件2（条件1（R））＝条件1∧条件2（R）3、连接（Join）连接是从两个关系的笛卡尔积中选取满足某规定条件的全体元组，形成一个新的关系。记为RS＝AθB（R×S）式中：A是R的属性，B是S的属性AθB的实际形式应该写成这样：A11B1∧A22B2∧…∧AkkBk其中Ai，Bi分属于关系R和S的属性组。Ai和Bi可以不同名，但必须可比；θi｛＜，＞，≤，≥，＝，≠｝当连接表达式中所有θi都是“＝”时，称该连接为等值连接（Equivalencejoin）4、自然连接（Naturaljoin）自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果关系中把重复的属性列去掉。若R和S具有相同的属性组B，则自然连接可记作：RS＝｛tr^ts|trR∧tsS∧tr[B]＝ts[B]｝式中tr[B]＝ts[B]表示R和S中相同的属性列的值分别相等。自然连接与等值连接的差别在于：自然连接要求相等的分量必须有共同的属性名，等值连接则不要求；自然连接要求把重复的属性名去掉，等值连接却不这样做。一般的连接是从行的角度进行运算，但自然连接还需要取消重复列，所以，是同时从行和列的角度进行运算。-6-5、除（Division）（1）除法的简单形式设关系S的属性是关系R的属性的一部分，则R÷S为这样一个关系：此关系的属性是由属于R但不属于S的所有属性组成；R÷S的任一元组都是R中某元组的一部分。但必须符合下列要求，即任取属于R÷S的一个元组t，则t与S的任一元组连串后，都为R中原有的一个元组。（2）除法的一般形式设有关系R（X，Y）和S（Y，Z），其中X、Y、Z为关系的属性组，则R（X，Y）÷S（Y，Z）＝R（X，Y）÷∏Y（S）（3）关系的除运算是关系运算中最复杂的一种，关系R与S的除运算的以上叙述解决了R÷S关系的属性组成及其元组应满足的条件要求，但怎样确定关系R÷S元组，仍然没有说清楚。为了说清楚这个问题，首先得引进一个概念：象集：给定一个关系R（X，Y），X和Y为属性组。定义，当t［X］＝x时，x在R中的象集（ImageSet）为：Yx={t[Y]|tR∧t[X]=x}上式中：t［Y］和t［X］分别表示R中的元组t在属性组Y和X上的分量的集合。例如在关系Student（Dno,Clno，Sno，Sname，Ssex）中有一个元组值为：（01,200201，20020102，张三，男）假设X＝｛Clno，Dno｝，Y＝｛Sno，Snmae，Ssex｝，则上式中的t[X]的一个值x=(01,200201)此时，Yx为t［X］＝x＝(01,200201)时所有t[Y]的值。即01系200201班全体学生的学号，姓名，性别信息表。下面，我们再回过头来讨论除法的一般形式：设有关系R（X，Y）和S（Y，Z），其中X、Y、Z为关系的属性组，则R÷S＝｛tr[X]|trR∧∏Y（S）Yx请看书P71页例4.3有两个关系：学生选课(姓名，课程)和课程(课程)，套上列公式，X＝姓名，Y＝课程，显然，在关系学生选课中，姓名可以取四个值｛张航，王昆，李跃山，曲军｝。其中：张航的象集为：｛数学，物理｝；王昆的象集为：｛数学｝-7-李跃山的象集为：｛数学，物理｝；曲军的象集为：｛物理｝课程在课程上的投影为：｛数学，物理｝显然，以上张航和李跃山的象集包含了课程在课程上的投影的投影，所以学生选课÷课程＝｛张航，李跃山｝以上我们学习了关系代数的基本内容，关系代数分为两大类：即传统的集合运算和专门的关系运算。传统的集合运算将关系看成元组的集合，其运算是从关系的“水平”方向即行的角度来进行的。而专门的关系运算不仅涉及行而且涉及列。传统集合运算是二目运算，包括：并，差，交，广义笛卡尔积四种运算；专门的关系运算包括：投影、选择、连接和除等四种运算。以上八种关系代数运算中，并、差、笛卡尔积、投影和选择五种运算为基本运算。其它三种运算，即交、连接和除，均可以用前五种基本运算来表达。引进它们，并不增加语言的能力，但可以简化表达。关系代数中，这些运算经有限次复合后形成的式子称为关系代数表达式。关系代数是通过对关系的运算来表达查询的。它的运算对象是关系，运算结果也是关系。4.5关系演算把数理逻辑中的谓词演算应用到关系运算中就得到关系演算。关系演算分为元组关系演算和域关系演算两种。元组关系演算以元组为变量，简称元组演算；域关系演算以域为变量，简称域演算。4.5.1元组关系演算元组关系演算是以元组为变量的，它用表达式｛t|）（t｝表示。式中：t为元组变量，）（t为元组关系演算公式，简称公式，表示所有使为真的元组的集合。）（t可以是最基本的原子公式，也可以是由原子公式组成的复合公式1、原子公式：-8-2、元组关系演算公式）（t的完整定义（1）每个原子公式是公式。（2）若1和2为公式，则1∧2，1∨2和￢1也为公式。并且当：1和2都为真时，1∧2为真；1和