第3章--关系运算及关系系统

第3章关系运算及关系系统第3章关系运算及关系系统3.1关系代数3.2关系演算3.3关系代数、元组演算、域演算的等价性3.4查询优化3.5关系系统习题第3章关系运算及关系系统3.1关系代数第2.2节已对关系模型的数据结构和完整性约束做了介绍。本节主要讨论数据操作，即关系运算。关系运算分为两种方法：一种方法基于代数的定义，称为关系代数；另一种方法基于逻辑的定义，称为关系演算。下面分两节讨论关系运算。第3章关系运算及关系系统关系代数是一种抽象的查询语言，是关系数据操纵语言的一种传统表达方式。关系代数中给出的功能在任何实际语言中应该都能实现。关系代数是通过关系的运算来表达查询的。它的运算对象是关系，运算结果也是关系。第3章关系运算及关系系统关系代数的运算分为两类：（1）传统的集合运算：并、交、差和广义笛卡尔乘积。（2）专门的关系运算：选择、投影、连接和除。在集合运算中，还涉及到两类辅助运算符：（1）比较运算符：＞（大于）、≥（大于等于）、＜（小于）、≤（小于等于）、＝（等于）、≠（不等于）。（2）逻辑运算符：｛~~｝（非）、∧（与）、∨（或）。第3章关系运算及关系系统3.1.1传统的集合运算传统的集合运算是二目运算（又称二元操作）。以下运算用到的两个关系R和S均为n度关系，且相应的属性取自同一个域。基本运算如下：1．并（Union）关系R和S的并为：R∪S={t|t∈R∨t∈S}其结果仍为n目关系。任取元组t，当且仅当t属于R或t属于S时，t属于R∪S。第3章关系运算及关系系统2．差（Difference）关系R和S的差为：R－S={t|t∈R∧t(S}其结果仍为n目关系。任取元组t，当且仅当t属于R且t不属于S时，t属于R-S。3．交（Intersection）关系R和S的交为：R∩S={t|t∈R∧t∈S}其结果仍为n目关系。任取元组t，当且仅当t既属于R又属于S时，t属于R∩S。从集合论的观点分析，关系的交运算可表示为差运算：R∩S=R-(R-S）。第3章关系运算及关系系统4．笛卡尔乘积（CartesianProduct）设R为m目关系，S为n目关系，则R和S的广义笛卡尔乘积为：R×S={t|t=〈tr，ts〉∧tr∈R∧ts∈S}其结果为m+n目关系。元组的前m列是关系R的一个元组，元组的后n列是关系S的一个元组。若R有k1个元组，S有k2个元组，则R×S有k1×k2个元组。第3章关系运算及关系系统实际运算时，可从R的第一个元组开始，依次与S的每一个元组组合，然后对R的下一个元组进行同样的操作，直至R的最后一个元组也进行完相同操作为止，即可得到R×S的全部元组。【例3.1】给定两个相容性关系R和S，计算R∪S，R－S，R∩S，R×S的结果。解：依据四种运算的定义，可得到如图3.2(a)、(b)、(c)、(d)所示的结果。第3章关系运算及关系系统第3章关系运算及关系系统图3.2传统集合运算举例第3章关系运算及关系系统3.1.2专门的关系运算专门的关系运算包括选择、投影、连接和除。前两个是一元操作，后两个为二元操作。1．选择（Selection）设R是n目关系，F是命题公式，其结果为逻辑值，取“真”或“假”，则R的选择操作定义为：σF（R）={t|t∈R∧F（t）=true}即取出满足条件F的所有元组。其中，F包含下列两类符号：第3章关系运算及关系系统运算对象（元组分量（属性名或列序号）、常数）；运算符（＞、≥、＜、≤、＝、≠、｛~~｝、∧、∨）。例如，对表3.1可写出：σ学号＞′9811018′（student），σ性别=′男′∧6≥′600′（student）。前者取出学号大于9811018的元组，后者取出入学成绩大于等于600的男性。F中的常量需用单引号括起。选择操作一般从行的角度进行运算。第3章关系运算及关系系统2．投影（Projection）设R是n目关系，R在其分量为1到m之间的整数，可不连续）上的投影操作定义为：1212,,,(;,,,miiimAAAmniii1212,,1{|,,,,,,}mmmiiiiiiinttttttttR即取出所有元组在特定分量12,,,miiiAAA上的值。第3章关系运算及关系系统例如，对图3.1可写出：π姓名，入学成绩（student），π1，4，6（student）。前者取出所有元组的姓名、入学成绩两个分量的值，后者取出第一、第四、第六分量的值。ACa1a2c1c2图3.3投影说明举例第3章关系运算及关系系统投影操作一般从列的角度进行运算，可以改变关系中列的顺序。需要说明的是，投影操作消去部分列后，可能会出现重复元组，根据关系特性，应将重复元组删去。如例3.1给出的关系S，在域列A，C上投影后结果如图3.3所示。第3章关系运算及关系系统3．连接（Join）连接也称为θ连接，是从两个关系的笛卡尔乘积中选取属性间满足一定条件的元组。记作：={t|t=〈tr，ts〉∧tr∈R∧ts∈S∧tr［A］θts［B］}=σAθB（R×S）其中，A和B分别是R和S上目数相等且可比的属性组（名称可不相同）。AθB作为比较公式F，F的一般形式为F1∧F2∧…∧Fn，每个Fi是形为tr［Ai］θs［Bj］的式子。ABRS第3章关系运算及关系系统下面介绍两种比较重要的连接：等值连接和自然连接。（1）等值连接（Equijoin)。当一个连接表达式中所有运算符θ取“=”时的连接就是等值连接，是从两个关系的广义笛卡尔乘积中选取A，B属性间相等的元组。记作：={t|t=〈tr，ts〉∧tr∈R∧ts∈S∧tr［A］=ts［B］}=σA=B（R×S）若A和B的属性个数为n，A和B中属性相同的个数为k（n≥k≥0），则等值连接结果将出现k个完全相同的列，即数据冗余，这是它的不足。ABRS第3章关系运算及关系系统（2）自然连接（Naturaljoin）。等值连接可能出现数据冗余，而自然连接将去掉重复的列。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且将去掉结果中重复的属性列。如果R和S有相同的属性组B，Att（R）和Att（S）分别表示R和S的属性集，则自然连接记作：{πAtt(R)∪(Att(S)-{B})（σt［B］=t［B］(R×S）)}此处t表示：{t|t∈R×S}。RS第3章关系运算及关系系统自然连接和等值连接的区别是：①等值连接相等的属性可以是相同属性，也可以是不同属性；自然连接相等的属性必须是相同的属性。②自然连接必须去掉重复属性（指相等比较属性，其它相同属性不管），而等值连接无此要求。③一般地，自然连接用于有公共属性的情况中。如果两个关系没有公共属性，那么它们的自然连接就退化为笛卡尔乘积。第3章关系运算及关系系统例3.2给定如下关系R和S，计算：σB＞′5′（R），πA，B（R），RB＜DS，RR.B=S.B∧R.C=S.CS及RS（R和S及结果如图3.4所示）。第3章关系运算及关系系统图3.4选择、投影、连接举例第3章关系运算及关系系统图3.4选择、投影、连接举例第3章关系运算及关系系统4．除(Division)给定关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性或属性组合。R中的Y和S中的Y可以有不同的属性名，但必须出自相同的域集。R÷S是满足下列条件的最大关系：其中每个元组t与S中的各个元组s组成的新元组〈t，s〉必在关系R中。定义形式为：R÷S=πX（R）－πX（（πX（R）×S）－R）={t|t∈πX（R）且s∈S，〈t，s〉∈R}关系的除操作需要说明的是：第3章关系运算及关系系统（1）R÷S的新关系属性是由属于R但不属于S的所有属性构成的。（2）R÷S的任一元组都是R中某元组的一部分。但必须符合下列要求：即任取属于R÷S的一个元组t，则t与S的任一元组相接后，结果都为R中的一个元组。（3）R（X，Y）÷S（Y，Z）≡R（X，Y）÷πY（S）第3章关系运算及关系系统（4）R÷S的计算过程如下：①T=πX（R）;②W=（T×S）－R;③V=πX（W）;④R÷S=T－V。【例3.3】给定关系R和S，求R÷S（如图3.5）。第3章关系运算及关系系统图3.5除法操作举例第3章关系运算及关系系统【例3.4】基于前边给出的关系数据库E、P、EP：E（E＃，EN，EA，EE，ED）Key={E＃}P（P＃，PN，PL）Key={P＃}EP（E＃，P＃，L）Key={E＃，P＃}用关系代数完成下列问题的查询：第3章关系运算及关系系统用关系代数完成下列问题的查询：①检索维修班的全体职工。σED=′WX′（E）②检索年龄大于48岁的女职工。σEE=′女′∧3＞′48′（S）③查询职工的姓名和所在的部门。πEN，ED（P）第3章关系运算及关系系统④检索参与了P5项目的职工的职工号与工时，进而给出对应职工的姓名。π1，3（σ2=′P5′（EP））πEN（（σP＃=′P5′（EP））E）⑤检索未参与名为“礼堂”项目的职工号、姓名。πEN（（（σPN=′礼堂′（P））EP）E）πEN（E）－πEN（（（σPN=′礼堂′（P））EP）E）第3章关系运算及关系系统⑥检索参与项目号为P2或P4的职工号、姓名。T=πE＃（σP＃=′P2′∨P＃=′P4′（EP））R=πEN（TE）⑦检索同时参与项目号为P2和P4的职工号。π2（σ2=′P2′∧5=′P4′∧1=4（EPEP））或构造临时关系T，再求πE＃，P＃（EP）÷T第3章关系运算及关系系统⑧检索参与全部项目职工姓名。πEN（（（πE＃，P＃（EP））÷πP＃（P））E）⑨检索参与项目包含职工E3参与项目的职工号，或参与项目不包含职工E3所参与项目的职工号及姓名。πE＃，P＃（EP）÷πP＃（σE＃=′E3′（EP））πE＃（E）－（πE＃，P＃（EP）÷πP＃（σE＃=′E3′（EP）））πEN（（πE＃（E）－（πE＃，P＃（EP）÷πP＃（σE＃=′E3′（EP））））E）第3章关系运算及关系系统3.1.3扩充的关系代数运算根据前面讨论可知，涉及两个及两个以上关系表的查询必然用到连接运算,包括等值连接、非等值连接、自然连接。除此之外，为了保留更多信息，还有外连接、半连接、外部并、复合连接，这四类连接就是扩充的关系代数运算。第3章关系运算及关系系统1．外连接（Outerjoin）两个关系R和S在作自然连接时，选择两个关系在所有公共属性上值相等的元组组成新关系的元组。此时，两个关系公共属性上值不相等的元组无法进入连接后的新关系，造成R和S中部分元组值被舍弃。这种舍弃是正常的，但有时希望该舍弃的元组继续保留在新关系中。第3章关系运算及关系系统【例3.5】关系数据库S和SC两个关系有如下元组（如图3.6）：S（S＃，SN，SA，SE，SD）SC（S＃，C＃，G）执行运算SSC后，结果如图3.7。第3章关系运算及关系系统图3.6基本关系R和S第3章关系运算及关系系统图3.7SSC运算结果第3章关系运算及关系系统从例3.5可见，结果关系中没有95003和95004两个学生的数据，原因在于他们没有选课，即SC中无相应元组，这是正确的。但是，有时我们想以S为主体列出每个学生的基本情况及其选课情况，若该生未选课，则只输出其基本信息，其选课信息为空值，即产生如图3.8所示的结果(此时用到外连接)。第3章关系运算及关系系统图3.8外连接说明举例第3章关系运算及关系系统【定义3.1】如果R和S在作自然连接时，把该舍弃的元组也保留在新关系中，在新增加的属性上填上空值（NULL），那么这种操作称为外连接，用符号：RS表示。根据保留元组的不同，外连接又分为左外连接和右外连接。（1）左外连接。如果R和S在作自然连接时，只把R中原该舍弃的元组保留在新关系中，那么这种操作称为左外连接，用符号RS表示。第3章关系运算及关系系统（2）右外连接。如果R和S在作自然连接时，只把S中原该舍弃的元组保留在新关系中，那么这种操作称为右外连接，用符号：RS表示。【例3.6】在图3.9中给出两个基本关系R和S为(a)和(b)，可将其自然