复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）03/30

四、投影运算 在数据库中,用关系来描述数据时常用投 影运算进行数据操作。 定义210:设R是A1,A2,n的n元关系, 定义R在A1,A2…,Amn上的投影是一个m 元关系,它是通过选取R中的每个有序m元 组的第i1,第i2…第n个分量组成有序m元 组作为m元关系中的元素这个投影记为 Ail, Ai2,.,Aim (R)

四、投影运算 在数据库中, 用关系来描述数据时常用投 影运算进行数据操作。 定义 2.10：设R是A1 ,A2 ,…,An的n元关系, 定义R在Ai1 ,Ai2 ,…,Aim上的投影是一个m 元关系,它是通过选取R中的每个有序n元 组的第i1 ,第i2 ,…,第im个分量组成有序m元 组作为m元关系中的元素,这个投影记为 Ai1,Ai2,…,Aim (R)

例:四元关系R和三元关系S定义如下: R ABC D E F a b c g SDbd ga a d a f h a b d g 「ABD (R) IEF (S) AB D ad Ega Faf a

例：四元关系R和三元关系S定义如下: R S A B C D D E F a b c g b g a d a f h d a f a b d g ABD(R) EF(S) A B D E F a b g g a d a h a f a b g ABD(R) EF(S) A B D E F a b g g a d a h a f ABD(R) EF(S) A B D E F a b g g a d a h a f

Tac (r) Aada Ccfd 关系R的投影的元素个数≤R的元素个数

关系R的投影的元素个数R的元素个数。 AC(R) A C a c d f a d

讨论了关系的性质自反,反自反,对称,反 对称传递 通常一些关系不一定具有这些性质但若 在此关系基础之上适当增加一些元素就 可以使之具有所要的性质了。 例:R={(a,b),(b,a)a,c}不对称。 若增加元素(c,a),得R'={(a,b),(b,a),(a,c), (c,a)},而且R是一个包含R的不可减少 任何元素的对称关系 闭包

讨论了关系的性质:自反,反自反,对称,反 对称,传递 通常一些关系不一定具有这些性质,但若 在此关系基础之上适当增加一些元素,就 可以使之具有所要的性质了。 例：R={(a,b),(b,a),(a,c)},不对称。 若增加元素(c,a),得R'={(a,b),(b,a),(a,c), (c,a)}，而且R'是一个包含R的不可减少 任何元素的对称关系 闭包

25关系的闭包 一、闭包的定义 从给定关系R出发构造一个新关系R,使 得R包含R并且R是具有某种性质的关 系,同时R又是包含R的最小关系。 从关系R得到新关系R'的运算通称为闭 包运算

2.5 关系的闭包 一、闭包的定义 从给定关系R出发构造一个新关系R' ,使 得R'包含R,并且R'是具有某种性质的关 系,同时R'又是包含R的最小关系。 从关系R得到新关系R'的运算通称为闭 包运算

定义211:设R是A上的二元关系,定义R 的自反对称传递团包记为R,满足下列 三个条件 (1)R'是自反的(对称的,传递的) (2)RCR; (3)对任一自反(对称,传递)关系R",若 RcR",则RR"。R的自反闭包对称闭 包和传递闭包分别记为r(R)(R)和 t(R)((R)又记为R)

定义 2.11：设R是A上的二元关系,定义R 的自反(对称,传递)闭包记为R',满足下列 三个条件： (1)R'是自反的(对称的, 传递的)； (2) RR'； (3)对任一自反(对称, 传递)关系R",若 RR",则R'R"。R的自反闭包,对称闭 包 和 传 递 闭 包 分 别 记 为 r(R),s(R) 和 t(R)(t(R)又记为R+ )

自反的(对称的,传递的);RR';对任一自反 (对称,传递)关系R"若RcR",则R'R" 例:若R对称,s(R)=? 也就是说,R对称当且仅当s(R)=R 定理2.5:设R是A上的二元关系,则 (1)R是自反的当且仅当r(R=R; (2)R是对称的当且仅当(R=R; (3)R是传递的当且仅当(R)=R

例：若R对称，s(R)=? 也就是说，R对称当且仅当s(R)=R 定理 2.5：设R是A上的二元关系, 则 (1)R是自反的当且仅当r(R)=R； (2)R是对称的当且仅当s(R)=R； (3)R是传递的当且仅当t(R)=R。 自反的(对称的, 传递的)； RR'；对任一自反 (对称, 传递)关系R",若RR",则R'R

定理25:设R是A上的二元关系,则 (1)R是自反的当且仅当r(R)=R; (2)R是对称的当且仅当s(R=R; (3)R是传递的当且仅当(R=R。 定理2.6:设R1和R2是A上的二元关 系R1三R2则 (1r(R1∈r(R2) (2)s(R1s(R2) (3)t(R1)∈t(R2)o

定理 2.5：设R是A上的二元关系, 则 (1)R是自反的当且仅当r(R)=R； (2)R是对称的当且仅当s(R)=R； (3)R是传递的当且仅当t(R)=R。 定理 2 .6：设R1和R2是A上的二元关 系,R1R2则 (1)r(R1 )r(R2 )； (2)s(R1 )s(R2 )； (3)t(R1 )t(R2 )

设A={1,2,3},R={(1,2),(1,3),则 r(R)={(1,1)2,2),(3,3),(1,2),(1,3)} S(R)={(1,2),(1,3),(2,1),(3,1)} t(R)={(1,2),(1,3)} 二、确定闭包的方法 定理27:设R是集合A上的二元关系,I 是集合A上的恒等关系则r(R)=R (IA={(a2,)a∈A 证明:令R'=RUIA。验证R满足闭包的 三个条件

设A={1,2,3},R={(1,2),(1,3)},则 r(R)={(1,1),(2,2),(3,3),(1,2),(1,3)} s(R)={(1,2),(1,3),(2,1),(3,1)} t(R)={(1,2),(1,3)} 二、确定闭包的方法 定理 2.7：设R是集合A上的二元关系,IA 是集合A上的恒等关系,则r(R)=R∪IA。 (IA={(a,a)|aA}) 证明：令R'=R∪IA。验证R'满足闭包的 三个条件

(1)自反 (2)RcR’, (3)假设有A上的二元关系R",R"自反且RcR", (目标是R'R") 定理28:设R是集合A上的二元关系,则 s(R)=RUR。 证明:令R′=RUR。验证R'满足闭包的三个条 件 (1)R'=RUR1对称(R是对称的当且仅当R=R) (2RCRURIER' (3)假设有A上二元关系R",R"对称且RcR", (目标RcR")

(1) 自反 (2) RR'， (3)假设有A上的二元关系R''，R''自反且RR''， (目标是R'R'') 定理 2.8：设R是集合A上的二元关系, 则 s(R)=R∪R-1 。 证明：令R'=R∪R-1 。验证R'满足闭包的三个条 件 (1) R'=R∪R-1对称(R是对称的当且仅当R=R-1) (2)RR∪R-1=R'， (3)假设有A上二元关系R''，R''对称且RR''， (目标R'R'')