第10章 关 系l 关系是在集合上定义的一个常用的概念例如， 在自然数之间可以定义相等关系和小于关系，在 命题公式之间可以定义等价关系和永真蕴涵关系 ，在集合A的各子集之间可以定义相等关系和包 含关系此外，在学生和课程之间存在选课关系 ，在课程表上反映了课程、班级、教师、教室、 时间等之间的关系关系就是联系，也就是映射 在数据库的一种重要类型关系数据库中保存了 各数据项之间的关系，关系数据库中的数据结构 就是按照本章所定义的关系设计的101 二元关系1011 二元关系的定义l 定义1011 对集合A和B，AB的任一子集 称为A到B的一个二元关系，一般记作R若R，可记作xRy;若R，可记作x y 在A=B时，AA的任一子集称为A上的一个二 元关系二元关系可简称关系 l 从形式上说，二元关系是笛卡儿积的子集，换句 话说，它是有序对的集合从语义上说，二元关 系是集合A和B元素之间的联系从下面的例子 可以看出这种联系l例1 设A0，1，B=a，b则Rl=，R2=，是A到B的两个二元关系R3，R4，是A上的两个二元关系l 例2 设X1，2，3，定义X上的关系Dx和Lx为Dx=|xXyXx整除yLx|xXyXxy于是，Dx是Dx=，Lx关系是Lx=，l例3 对任意的集合A，在P(A)上的包含关系 R1和真包含关系R2定义为R1=|xP(A)yP(A)xyR2=|xP(A)yP(A)xyl若A，则P(A)，P(A)上的 R1和R2是R1， ，R2，l二元关系是二元组的集合推广这个概念 ，可以用n元组的集合定义n元关系 l定义1012 若nN且n1，A1，A2， ，An是n个集合，则A1A2An的任 一子集称为从A1到An上的一个n元关系10.1.2 特殊的关系l下面定义三个A上的特殊的关系 l定义1013 对任意的集合A(1)A上的恒等关系IA定义为IA=xA，(2)A上的全域关系(全关系)EA定义为EA=|xAyA，(3) 是A上的空关系l例4 设A，则IA=，EA=， 1013 定义域和值域l定义101. 4 对A到B的一个关系R，可以 定义(1)R的定义域dom(R)为dom(R)=x|(y)(R)，(2)R的值域ran(R)为ran(R)=y|(x)(R)，(3)R的域fld(R)为fld(R)=dom(R)U ran(R)，l例5 设Aa，b，c，Bb，c，d，A到 B的关系R=，则dom(R)=a，b，ran(R)b，c，d，fld(R)=a，b，c，dl定理1011 对A到B的关系R如果 R，则xUUR，yUUR 证明 已知R，即x，x，yR 因x，y是R的元素的元素，故x，yU R 因x和y是UR的元素的元素，故 xUUR,yUUR l定理1012 对A到B的关系R，则fld(R)=UU R，证明 对任意的x，若xfld(R)，则 xdom(R)或xran(R)则存在y，使 R或R这时都有xUUR 对任意的t，若tUUR因为R的元素的形 式是x,x，y，所以必存在u，使t,t， uR 或u,u，tR也就是tfld(R)102 关系矩阵和关系图l描述关系的方法有三种：集合表达式、关 系矩阵和关系图。关系的定义使用了集合 表达式，这一节介绍后两种方法，对有限 集合上的关系，采用关系矩阵和关系图的 方法，不仅使分析更加方便，而且有利于 使用计算机处理，1021 关系矩阵l 定义1021 设集合Xxl，x2，xm，Y yl，y2，yn， (1)若R是X到Y的一个关系，则R的关系矩阵是 mn矩阵(m行,n列的矩阵)(2)若R是X上的一个关系，则R的关系矩阵是mm 方阵(m行、m列的矩阵)lA到B的关系R是AB的子集，AB有mn个 有序对矩阵M(R)有m行(行为横向)、n列( 列为竖向)，共有mn个元素因此，M(R) 的每个元素恰好对应AB的一个有序对用 M(R)中元素rij的值表示有序对是否 在R中，因为只有属于和不属于两种情况， 所以rij只取值0和1是合理的l在矩阵右方和下方标注了X和Y的元素，标 注表明，x1对应第1行，x2对应第2行，y1 对应第1列，依此类推因此，第1行第3列 交点的r13=1表示R，而第3行第 1列的r310表示 R在使用关 系矩阵时，集合X和Y中的元素分别进行了 排序这时就不必在矩阵上标注这些元素 ，而且也不难确定一个矩阵元素对应的有 序对l 例2 设A1，2，3，4，A上的大于关系定义为 =， ，则关系的关系矩阵是1022 关系l 定义1022 设集合Xx1，x2，xm，Y y1，y2，yn (1)若只是X到Y的一个关系，则R的关系图是一个 有向图G(R)，它的顶点集是VXY ，边集是E，从xi到yj的有向边eijE，当且仅当 R (2)若R是X上的一个关系，则R的关系图是一个有 向图G(R)，它的顶点集是VX，边集 是E，从xi到xj的有向边eijE当且仅当Rl 例3 对例1中的X到Y的 关系R，关系图G(R)如 图1021所示在 XY时为了图示清楚 ，通常把定义域的元素 x1，x2等画在一边，把 值域中的元素y1,y2画在 另一边l 例4 对例2中的A上的 关系，关系图G()如 图1022所示对 A上的关系关系图中 一般不区分定义域和 值域，每个顶点既可 以发出有向边，又可 以收到有向边l 例5 对A=a,b,c上的关系 R，,，关系图G(R)如图1023 所示图中从a到a的有向边eaa表示R，这 类有向边称为自圈103 关系的逆、合成、限制和象l一个关系的逆是另一个关系，两个关系的 合成是第三个关系求关系的逆与合成都 是构造新关系的方法，也都是关系的运算 1031 定义l定义1031 对X到Y的关系R，Y到Z的 关系S，定义(1)R的逆R-1为Y到X的关系R-1|R，(2)R与S的合成SR为X到Z的关系SR|(z)(R S)此外，对任意的集合A，还可定义(4)A在R下的象RA为集合RAy|(x)(xAR)l 对R的每个有序对，把两个元颠倒得到有 序对，这些的集合就是R-1把R的 关系图中每个有向边的方向颠倒就得到R-1的关系 图 l 如果在关系R和S中各有一个有序对，使R且S，则是关系SR的元素 而且，SR包含全部这样的有序对关系的合 成如图1031所示因为R且S，故SR虽有R，但 不存在y使S，故没有y使SR也 没有x使SRl 注意，X到Y的关系R和Y到Z的关系S合成为SR ，而不写成RS(注：有的书写为RS)SR是X 到Z的关系为了求SR，应把R中每个有序对与 S中每个有序对一一配合，以此确定SR的每个有 序对 l R A是关系R的子集，其中每个有序对满足 xA可以说R A是A到Y的关系也可以说是X 到Y的关系当dom(R) A时，R ARRA 是一个集合，它实质上是只R A的值域l 例1 设集合A上的关系R为A=a，a，a，R=，l例2 设集合N上的关系R和S为R， ，S=，则 R-1，SR，RS1032 SR的关系矩阵l R-1的关系矩阵M(R-1)就是R的关系矩阵的转置矩 阵也就是说，把M(R)中每一对rij和rji(ij)互换就 得到M(R-1)，下面介绍求SR的关系矩阵的方法如果A是有限集合，|A|=n关系R和S都是A上的 关系，R和S的关系矩阵M(R)=(rij)和M(S)(sij)都 是nXn的方阵于是SR的关系矩阵M(SR)(wij)，可以用下述的矩阵逻辑乘法计算( 类似于矩阵乘法)可以写为M(SR)=M(R)M(S)，l其中 wijk=1n(rikskj)这是由M(S)和 M(R)的元素计算M(S，R)的元素wij的方法 式中的和V分别为在集合0，1上的运算 l是逻辑乘，11l，而01=10000( 它对应合取词) lV是逻辑和，0V 00，1V0=0V1=1V11( 它对应析取词)l 例3 设集合A1,2,3,4，A上的关系R,，S,则1033 性质1. 关于逆 l 定理10.3.1 对X到Y的关系R和Y到Z的关系S，则(1)dom(R-1)ran(R)，(2)ran(R-1)=dom(R)，(3)(R-1)-1R，(4)(SR)-1=R-1S-1 注意，左边关系的矩阵描述为(M(R)M(S)T 右边关系的矩阵描述为M(S)TM(R) T ，显然两边相等 证明 (1)对任意的x，有xdom(R-1)(y)(R-1)(y)(R)xran(R)，所以，dom(R-1)ran(R)(2)类似于(1)l 定理10.3.2 对X到Y的关系Q，Y到Z的关系S，Z到 W的关系R，则l 关系的合成是关系的运算定理表明，这个运算 满足结合律但是它不满足交换律，般SRRS 2. 2. 合成满足结合律合成满足结合律l 定理10.3.3 对X到Y的关系R2和R3，Y到Z的关系 R1，有(1)R1(R2UR3)R1R2UR1R3，(2)R1(R2R3)R1R2R1R3 ，对X到Y的关系R3，Y到Z的关系R1、R2，有(3)(R1UR2) R3R1R3UR2R3，(4)(R1R2) R3 R1R3R2R3，(注意，规定关系合成符优先于集合运算符) 证明 P167. 3. 3. 关于合成的分配关于合成的分配律律( (分配分配律律分左右两种；合成对交的分配不能保持分左右两种；合成对交的分配不能保持) )l 定理10.3.3 对X到Y的关系R集合A,B,有(1)RAUBRAURB，(2)RUA=URB | B A，(3)RAB RA RB，(4)RA RB | B A ，A =/= (5)RA-RB RA-B 证明 只证(2)，(3)其他留作思考题， 4. 4.关于象的关于象的分配分配律律4. 4. 关于象的分配律关于象的分配律象对交的分配不能保持；象对交的分配不能保持； 第四条中，第四条中，A A为空集时为空集时 A A无意义，见无意义，见p134p134l上面定理中包含关系为真包含的例子 l例4 设整数集合Z上的关系R为 R|xZyZyx2 (这里的R有具体的含意)， 集合A1，2，BO，-l，-2 于是RA1，4因为R, R 于是RB0，1，4因为. 故RAB , RARB=1，4 此外， RA-RB= , RA-B=1，4 104关系的性质l在实际问题中，我们感兴趣的往往不是一 般的关系，而是具有某些特殊性质的关系 为了更好地处理这些关系，有必要深入 研究关系的性质对A上的关系来说，主要 的性质有：