18-4 1 关系及其性质

1、数理逻辑 Mathematical Logic,第三章 数学推理 Chapter 3 Mathematical Reasoning,复习,递归算法 递归与迭代 递归定义把在正整数处的函数值表达成在更小的整数处的函数值 迭代是连续地应用递归定义来求出在更大的整数处的函数值,数理逻辑 Mathematical Logic,第四章 关系 Chapter 4 Relations,Outline,关系及其性质 二元关系的定义 关系的性质 关系的组合 n元关系及其应用 n元关系的定义 数据库和关系,4.1 关系及其性质 Relations and their properties,一、引言,可以用两个相关

2、元素构成的有序对来表达两个集合的元素之间的关系 定义：设A和B是集合，一个从A到B的二元关系是AB的子集 有序对的集合R是一个从A到B的二元关系，aRb表示(a,b)R，aRb表示(a,b)R；当(a,b)R时叫做a与b有关系R,例：设A是学校的学生的集合，B是课程的集合。令R是由(a,b)对构成的关系，其中a是选修课程b的学生。 若张三和李四选修了数理逻辑，则有序对(张三，数理逻辑)和(李四，数理逻辑)都属于R； 如果王五选修了JAVA语言，则有序对（王五，JAVA语言）属于R； 如果赵六没有选修数理逻辑，那么有序对（赵六，数理逻辑）不在R中,一、引言,P368 - 例2 例3：设A0,1,

3、2，B=a,b，那么 R(0,a),(0,b),(1,a),(2,b)是从A到B的关系 0Ra 1Rb 表示为图或者表,一、引言,注意:相关性与指定的规则有关。 扑克牌中的方块k与梅花k 同花关系：不相关 同点关系：相关 父子二人 同辈关系：不相关 父子关系：相关,一、引言,二、函数作为关系,一个从集合A到集合B的函数，对于A中的每个元素都指定B中一个唯一的元素 f的图示是使得bf(a)的有序对(a,b)的集合，其是AB的子集，因此，它也是一个从A到B的关系 如果R是从A到B的关系，并且使得A中的每个元素是R中恰好一个有序对的第一个元素，那么R就可以定义一个函数 一对一，多对一，一对多，多对多

4、,三、集合上的关系,定义：集合A上的关系是从A到A的关系。换句话说：集合A上的关系是AA的子集。 例：设A是集合1,2,3,4，A上的关系R=(a,b)|a整除b中有哪些有序对？,例：考虑下面这些整数集合上的关系，哪些包含了 (1,1) R1,R3,R4,R6 (1,2) R1,R6 (2,1) R2,R5,R6 (1,-1) ? (2,2) ？,三、集合上的关系,例：包含n个元素的集合上有多少个关系？ 集合A上的关系是AA的子集 当A是包含n个元素的集合时，AA有n2个元素 m个元素的集合有2m个子集 故AA的子集有 个 因此，包含n个元素的集合有 个关系,三、集合上的关系,四、关系的性质,

5、自反性 对称性 反对称性 传递性,定义：如果对每个元素aA有(a,a)R，那么集合A上的关系R叫做自反的。 例：R是所有人集合上的关系，若x和y有相同的父亲和相同的母亲，那么(x,y)属于R 对每个人x来说，有xRx,四、关系的性质,例：考虑1,2,3,4上的关系，自反？,四、关系的性质,四、关系的性质,例：例5中哪些关系是自反的？ R1,R3,R4 例：正整数集合上的整除关系是自反的吗？ 解：因为只要a是正整数，就有a|a，因此，整除关系是自反的。,定义：对于a,bA，如果只要(a,b)R就有(b,a)R，则集合A上的关系R叫做对称的； 对于a,bA，若(a,b)R且(b,a)R，则a=b，

6、集合A上的关系R叫做反对称的。 对称与反对称的概念不是对立的,四、关系的性质,一个关系由(x,y)对构成， x和y至少学一门公共课程 x比y的平均成绩高 关系R是对称的 当且仅当如果a与b相关，则b与a就相关 关系R是反对称的 当且仅当不存在由不同元素a和b构成的有序对，使得a与b相关并且b与a也相关,四、关系的性质,四、关系的性质,例：例7中的哪些关系是对称的？哪些是反对称的？ R2和R3是对称的 R4，R5和R6是反对称的,四、关系的性质,例：例5中哪些关系是对称的？哪些是反对称的？ R3，R4和R6是对称的 R1，R2，R4和R5是反对称的,例：正整数集合上的整除关系是对称的吗？是反对称

7、的吗？ 解：这个关系不是对称的，因为1|2，但是2|1不成立； 它是反对称的，因为若a和b是正整数，并且a|b和b|a，那么a=b。,四、关系的性质,定义：对于a,b,cA，如果(a,b)R，并且(b,c)R，则(a,c)R，那么集合A上的关系R称为传递的。 例：例7的关系中哪些是传递的？ 解：R4,R5和R6是传递的,四、关系的性质,四、关系的性质,例：例5的关系中哪些是传递的？ R1,R2,R3和R4是传递的,例：正整数集合上的整除关系是传递的吗？ 解：假设a整除b，而且b整除c，那么存在正整数k和l，使得b=ak和c=bl； 因此，c=akl，即a整除c； 这个关系是传递的。,四、关系的

8、性质,例：具有n个元素的集合上有多少个自反的关系？ 解：A上的关系是AA的子集； AA共有n2个有序对，现在要看这n2个有序对是否在R中？ 如果R是自反的，对于aA，n个有序对(a,a)中的每一个都必须在R中； 其它n(n-1)个形如(a,b)的有序对，ab，可能在也可能不在R中；,四、关系的性质,例：具有n个元素的集合上有多少个自反的关系？ 解：因此，共有2n(n-1)种可能 所以，存在2n(n-1)个自反的关系。 例：具有n个元素的集合上有多少个对称关系和反对称关系？ 存在2n(n+1)/2个对称的关系 存在2n 3n(n-1)/2个反对称的关系,四、关系的性质,自反性：每个顶点都有自回路

9、； 对称性：任二个顶点间或没有边，或有 二条相对而指的有向边； 反对称性：任二个顶点至多只有一条有 向边； 传递性：若x到y有边，y到z有边， 则x到z必有边。,四、关系的性质,五、关系的组合,因为从A到B的关系是AB的子集 可以按照两个集合组合的任何方式来组合两个关系 例：设A=1,2,3和B=1,2,3,4，组合关系R1=(1,1),(2,2),(3,3)和R2=(1,1),(1,2),(1,3),(1,4)可以得到：,例：设A和B分别是学校的所有学生和所有课程的集合，假设： R1由所有有序对(a,b)组成，其中a是选修课程b的学生； R2由所有有序对(a,b)构成，其中课程b是a的必修课

10、。 求什么是关系R1R2，R1R2，R1R2，R1-R2和R2-R1？,五、关系的组合,组合关系还有另外一种方式，其类似于函数的合成 定义：设R是从集合A到集合B的关系，S是从集合B到集合C的关系。R和S的合成是由有序对(a,c)构成的关系，其中aA、cC，并且对于它们存在一个元素bB，使得(a,b)R和(b,c)S。用SR表示R与S的合成。,五、关系的组合,例：R是从1,2,3到1,2,3,4的关系且R=(1,1),(1,4),(2,3),(3,1),(3,4)，S是从1,2,3,4到0,1,2的关系，且S=(1,0),(2,0),(3,1),(3,2),(4,1)，R与S的合成是什么？ S

11、R=(1,0),(1,1),(2,1),(2,2),(3,0),(3,1),五、关系的组合,五、关系的组合,定义：设R是集合A上的关系。幂Rn，n=1,2,3,，递归地定义为： R1=R Rn+1= RnR。 例：设R=(1,1),(2,1),(3,2),(4,3)，求幂Rn，n=2,3,4,五、关系的组合,定理：集合A上的关系R是传递的，当且仅当n=1,2,3,时，有 。 证：首先证明充分条件，即假设对n=1,2,3,来说， 特别地，有 ，如果(a,b)R，(b,c)R，根据合成定义有(a,c)R2。 因为 ，所以(a,c)R。 因此，R是传递的。,五、关系的组合,定理：集合A上的关系R是传

12、递的，当且仅当n=1,2,3,时，有 。 证：其次证明必要条件，即如果R是传递的，那么对n=1,2,3,来说， 应用数学归纳法证明，n=1时， 显然成立； 假定 ，归纳假设，必须证明该假设能推出Rn+1也是R的子集；,五、关系的组合,定理：集合A上的关系R是传递的，当且仅当n=1,2,3,时，有 。 证：假设(a,b)Rn+1，那么因为Rn+1= RnR，存在元素xA，使得(a,x)R，并且(x,b)Rn。 由归纳假设 ，推出(x,b)R； 又因为R是传递的，所有(a,b)R； 这就证明了,五、关系的组合,4.2 n元关系及其应用 n-ary relations and their appli

13、cations,一、引言,两个以上集合的元素中常常会产生某种关系 学生姓名、学生专业、学生成绩 航班的航空公司、航班号、出发地、目的地、起飞时间、到达时间 第一个整数比第二个整数大，第二个整数比第三个整数大 n元关系,一、引言,用于表示计算机的数据库 有利于查询数据库中所存的信息 哪些学生主修计算机并且成绩大于60？ 哪些航班在下午两点到三点之间降落在首都机场？,二、n元关系,定义：设A1, A2, , An是集合。在这些集合上的n元关系是A1A2An的子集。 集合A1, A2, , An叫做关系的域 n叫做关系的阶,二、n元关系,例：设R是由5元组(A,N,S,D,T)构成的表示飞机航班的关

14、系，其中A: 航空公司，N: 航班号，S: 出发地，D: 目的地，T: 起飞时间。 (国航，1603，北京，哈尔滨，9:40) R 这个关系的阶是5 域是所有航空公司的集合，航班号的集合，城市的集合以及时间的集合,二、数据库和关系,关系型数据库 数据库由记录组成 记录是由字段构成的n元组 一个记录表示成一个n元关系 学生记录数据库 字段：学生的姓名、学号、专业、成绩 4元组：（姓名、学号、专业、成绩） （张三、200901、计算机、85）,二、数据库和关系,表 表示、存储数据库的关系,二、数据库和关系,主键码 n元组的某个域的值能够确定这个n元组 这个域就叫做主键码 没有两个n元组在这个域具有

15、相同的值 通常需要对数据库增加或删除记录，因此，一个域是否为主键也是变化的 应当选择不受数据库改变影响的字段,二、数据库和关系,例：假设不再增加记录，哪个域是主键码？,二、数据库和关系,例：假设不再增加记录，哪个域是主键码？,二、数据库和关系,例：假设不再增加记录，哪个域是主键码？,二、数据库和关系,复合键码 域的组合也可以唯一地标识n元组 当这一组域的值确定了一个关系中的n元组时，这些域的笛卡尔积就叫做复合键码 例：假设不再增加记录，专业的域和成绩的域的笛卡尔积是复合键码吗？ 主键码和复合键码用于唯一地标识记录 学号,二、数据库和关系,投影运算 通过删除关系的每个记录中同样的一些字段来构成新

16、的n元关系 定义：投影Pi1,i2,im将n元组(a1,a2,an)映到m元组(ai1,ai2,aim)，其中mn 投影Pi1,i2,im删除了n元组的n-m个分量，保留了第i1,i2,im分量 例：投影P1,3施用到4元组(2,3,0,4)的结果？,二、数据库和关系,投影运算 例：投影P1,4施用到学生记录数据库？,二、数据库和关系,投影运算 投影运算有可能使关系表中的行变少 某些n元组在投影的m个分量中的值都相同，而只在被投影删除的分量有不同的值,P1,2,二、数据库和关系,连接运算 当两个表具有相同字段时，连接运算将这两个表合成一个表 一个表包含航空公司、航班号、出发地、起飞时间，另一个表包含航空公司、航班号、目的地、到达时间。可以组合成一个包含航空公司、航班号、出发地、起飞时间、目的地、到达时间字段的表,二、数据库和关系,连接运算 定义：设