四、投影运算 在数据库中, 用关系来描述数据时常用投影运算进行数据操作。

Presentation on theme: "四、投影运算 在数据库中, 用关系来描述数据时常用投影运算进行数据操作。"— Presentation transcript:

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

2 例：四元关系R和三元关系S定义如下:

3 关系R的投影的元素个数R的元素个数。

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

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

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

7 定理 2.5：设R是A上的二元关系, 则 (1)R是自反的当且仅当r(R)=R； (2)R是对称的当且仅当s(R)=R；
自反的(对称的, 传递的)； RR'；对任一自反(对称, 传递)关系R",若R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。

8 定理 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)。

9 设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'满足闭包的三个条件

10 定理 2.8：设R是集合A上的二元关系, 则s(R)=R∪R-1。
(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'')

11 例：整数集上的“<”的对称闭包是“≠”
<,>，少了= 任一非空集A，其上的恒等关系的自反(对称)闭包就是恒等关系 其上的空关系的自反闭包是恒等关系 其上的空关系的对称闭包是空关系 定理 2.9：设R是集合A上的二元关系, 则

12 (1)传递：对任意(a,b),(b,c)R'=R∪R2∪R3∪
(a,c)R', (2)RR∪R2∪R3∪=R'， (3)假设有A上的二元关系R''，R''传递且RR''，(目标是R'R'')

13 定理 2.10：设R是有限集A上的二元关系, 且|A|=n,则

14 例：A={a,b,c,d},R={(a,b),(b,a),(b,c),(c,d)},求t(R)

15 四、闭包的性质 定理 2.11：设R是A上的二元关系。 (1)若R是自反的,则s(R)和t(R)都是自反的 (2)若R是对称的,则r(R)和t(R)都是对称的 (3)若R是传递的,则r(R)是传递的。 证明(1)(3) 证明:(1)对任意的aA,目标是(a,a)s(R), (a,a)t(R) (3)对任意(a,b),(b,c)r(R)=R∪IA,目标是(a,c)R∪IA

16 (1)rs(R)=sr(R)(这里rs(R)读作R的对称自反闭包); (2)rt(R)=tr(R); (3)st(R)ts(R)。
不一定 定理 2.12：设R是A上的二元关系, 则 (1)rs(R)=sr(R)(这里rs(R)读作R的对称自反闭包); (2)rt(R)=tr(R); (3)st(R)ts(R)。 定理 2.6:R1R2则t(R1)t(R2), s(R1)s(R2) 定理2.11(2)(若R是对称的,则r(R)和t(R)都是对称的 定理 2.5(2)R是对称的当且仅当s(R)=R ts(R)是否与st(R)相等?

17 2.6 等价关系与划分 一、等价关系 定义 2.13：设R是集合A上的二元关系,若R是自反的、对称的和传递的,则称R是A上的等价关系。若aRb,则称a与b等价。

18 例：设整数集I上的模m同余关系R是I上的等价关系。
证明:(1)自反(目标是证明对任意aI，有aRa) (2)对称(目标是证明若有aRb，则必有bRa) (3)传递(目标是证明若有aRb，bRc，则必有aRc) 因此整数集I上的模m同余关系R是I上的等价关系

19

20 例:设A={a,b,c},考察下列几个由A的子集所组成的集合：
P={{a,b},{c}},S={{a},{b},{c}},T={{a,b,c}},U={{a},{c}},V={{a,b},{b,c}},W={{a,b},{a,c},{c}}, 对于P,由于{a,b}∪{c}={a,b,c}，{a,b}∩{c}=，P是A的划分。 对于S,由于{a}∪{b}∪{c}={a,b,c}，{a}∩{b}={a}∩{c}={b}∩{c}=，S是A的划分。 对于T,显然是A的划分。 对于U, 由于{a}∪{c}≠{a,b,c}，所以不是A的划分 对于V, 尽管{a,b}∪{b,c}={a,b,c}，但{a,b}∩{b,c}={b}≠,所以不是A的划分。 类似可知W也不是A的划分。 注意:定义 2.12 中划分的块数可以是无限的。

21 作业: p ,13(3)14(2) 18(2)(3), 22,23,24 补充:讨论rst(R),srt(R), rts(R),trs(R), tsr(R),str(R)它们的关系