-
Notifications
You must be signed in to change notification settings - Fork 32
/
Copy path3、关系代数.md
203 lines (100 loc) · 8.86 KB
/
3、关系代数.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
### 关系代数
提出原因
* 复杂动作 = 基本动作的各种方式的组合，所有复杂的 sql 操作最后都会转化成基本操作的组合。
分类
* 纯关系操作
* 集合操作
集合操作前提：并相容性
* 参与运算的两个关系及其相关属性之间有一定的对应性、可比性或意义关联性
* 定义： 关系R 与关系S 存在相容性，当且仅当：
(1) 关系R 和关系S 的属性数目必须相同；
(2) 对于任意i ，关系R 的第i 个属性的域必须和关系S 的第i 个属性的域相同
假设：R(A1, A2, … , An) , S(B1, B2, … ,Bm)，若 R 和S 满足并相容性：n = m 并且 Domain(Ai) = Domain(Bi)
#### 基本操作
并(Union)
* 定义 ：假设关系R 和关系S 是并相容的，则关系R 与关系S的并运算结果也是一个关系，记作：R∪S, 它由或者出现在系 关系R 中， 或者出现在S中的元
组构成。
* 数学描述 ： R$\bigcup$S ={ t | t$\in$R $\vee$ t$\in$S } 中 ，其中 t 是元组
* 并运算是将两个关系的元组合并成一个关系，在合并时去掉重复的元组。
* R ∪S 与S ∪R 运算的结果是同一个关系
差(Difference)
* 定义：假设关系R 和关系S是并相容的，则关系R 与关系S 的差运算结果也是一个关系，记作：R S, 它由出现在关系R中但不出现在关系S中的元组构成。
* 数学描述：R $-$ S ={ t | t$\in$R $\wedge$ t$\notin$S }，其中t是元组
* R $-$ S 与S $-$ R 是不同的
广义笛卡尔积(Cartesian Product)
* 定义：关系R (<a1 ,a2, ..., an >) 与关系S(<b1, b2, ..., bm>) 的广义笛卡尔积(简称广义积,或积或笛卡尔积)运算结果也是一个关系，记作：R x S, 它由关系R中的元组与关系S的元组进行所有可能的拼接(或串接)构成。
* 数学描述：R xS ={ <a1 ,a2, ..., an, b1, b2, ..., bm>| <a1 ,a2, ..., an > $\in$R $\wedge$<b1, b2, ..., bm>$\in$S }
选择(Select)
* 定义：给定一个关系R, 同时给定一个选择的条件condition(简记con), 选择运算结果也是一个关系，记作$\sigma_{con}$(R）, 它从关系R中选择出满足给定条件condition的元组构成。
* 数学描述：$\sigma_{con}$(R）={t | t $\in$R $\wedge$con(t) = ‘‘真’’}，
* 设R(A1,A2 , ... ,An), t是R的元组, t 的分量记为t[Ai], 或简写为Ai
* 条件con由逻辑运算符连接比较表达式组成
* 逻辑运算符：$\wedge$，$\vee$，$\urcorner$ 或写为 and , or, not
* 比较表达式：X $\theta$Y, 其中X, Y 是t的分量、常量或简单函数, $\theta$是比较运算符,$\theta$$\in${ $\gt$, $\geq$, $\lt$, $\leq$,=, ≠}
投影(Project)
* 定义：给定一个关系R, 投影运算结果也是一个关系，记作$\prod_A$(R）, 它从关系R中选出属性包含在A中的列构成。
* 数学描述：$\prod_{Ai1, Ai2, ... ,Aik}$(r） = { <t[Ai1], t[Ai2] , ... , t[Aik]>| t$\in$R }
* 设R(A1,A2, ... ,An)
* { Ai1, Ai2, ... ,Aik}$\in${ A1,A2, ... ,An}
* t[Ai]表示元组t中相应于属性Ai的分量
* 投影运算可以对原关系的列在投影后重新排列
* 投影操作从给定关系中选出某些列组成新的关系, 而选择操作是从给定关系中选出某些行组成新的关系
* 投影主要是从列的角度进行运算，投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复）。
更名（有些教材算在基本操作）
* $\rho_{SC1}$ (SC) 表更名操作，即将表SC 更名为SC1
* 当一个表需要和其自身进行连接运算时，通常要使用更名操作
#### 扩展操作
交(Intersection)
* 定义：假设关系R和关系S是并相容的，则关系R与关系S的交运算结果也是一个关系，记作：R ∩S, 它由同时出现在关系R和关系S中的元组构成。
* 数学描述：R$\bigcap$S ={ t | t$\in$R $\wedge$t$\in$S }，其中t是元组
* R∩S 和S∩R 运算的结果是同一个关系
* 交运算可以通过差运算来实现：R $\bigcap$S = R $-$ (R$-$S) = S $-$(S $-$R)
$\theta$-连接($\theta$-Join, theta-Join)
* 定义：给定关系R和关系S, R与S的$\theta$连接运算结果也是一个关系，记作 $R\Join_{A \theta B}S$ ，它由关系R和关系S的笛卡尔积中, 选取R中属性A与S中属性B之间满足条件的元组构成。
* 数学描述：$R \Join_{A \theta B} S$ = $\sigma_{t[A] \theta s[B]}$(R$\times$S)
* 设R(A1,A2, ... ,An), A$\in${ A1,A2, ... ,An}
* S(B1,B2, ... ,Bm), B$\in${ B1,B2, ... ,Bm}
* t是关系R中的元组，s是关系S中的元组
* 属性A和属性B具有可比性
* $\theta$是比较运算符, $\theta$$\in${ $\gt$, $\geq$, $\lt$, $\leq$,=, ≠}
* 在实际应用中，$\theta$-连接操作经常与投影、选择操作一起使用
* 理论上$\theta$-连接操作时，使用笛卡尔积然后再进行选择来得到结果。但DBMS会进行优化，不必先形成笛卡尔积。
等值连接(Equi-Join)
* 定义：给定关系R和关系S, R与S的等值连接运算结果也是一个关系，记作$R\Join_{A = B}S$ ，它由关系R和关系S的笛卡尔积中选取R中属性A与S中属性B上值相等的元组所构成。
* 数学描述：$R\Join_{A = B}S$ = $\sigma_{t[A] = s[B]}$(R$\times$S)
* 当$\theta$-连接中运算符为“＝”时，就是等值连接，等值连接是$\theta$-连接的一个特例；
* 广义积的元组组合并不是都有意义的，另广义积的元组组合数目也非常庞大，因此采用$\theta$-连接/等值连接运算可大幅度降低中间结果的保存量，提高速度。
自然连接(Natural-Join)
* 定义：给定关系R和关系S, R与S的自然连接运算结果也是一个关系，记作 $R\Join S$ ，它由关系R和关系S的笛卡尔积中选取相同属性组B上值相等的元组所构成。
* 数学描述：$R\Join S$ = $\sigma_{t[B] = s[B]}$(R$\times$S)
* 自然连接是一种特殊的等值连接
* 要求关系R和关系S必须有相同的属性组B(如R,S共有一个属性B1,则B是B1, 如R, S共有一组属性B1, B2, ..., Bn，则B是这些共有的所有属性)
* R, S属性相同，值必须相等才能连接，即R.B1 = S.B1 and R.B2 = S.B2 ... and R.Bn= S.Bn才能连接
* 会在结果中去掉重复的属性列(因结果中R.Bi始终是等于S.Bi所以可只保留一列即可)
#### 复杂扩展
除(Division)
* 除法运算经常用于求解“查询... 全部的/所有的...”问题
* 前提条件：给定关系R(A1,A2, ... ,An)为n度关系，关系S(B1,B2, ... ,Bm)为m度关系。如果可以进行关系R与关系S的除运算，当且仅当：属性集{ B1,B2, ... , Bm}是属性集{ A1,A2, ... ,An }的真子集，即m < n。
* 定义：关系R 和关系S的除运算结果也是一个关系，记作R$\div$S，分两部分来定义。
* 先定义R$\div$S结果的属性应有哪些？
* 设属性集{C1,C2, ... ,Ck } = {A1,A2, ... ,An } – {B1,B2, ... ,Bm}, 则有k=n–m，则R$\div$S结果关系是一k度(n-m度)关系，由{C1,C2, ... ,Ck }属性构成
* 实现：R $\div$S= $\prod_{R-S}$ ( R ) $-$ ($\prod_{R-S}$( ($\prod_{R-S}$(R）) $\times$S )$-$R )
* 示例：（s有四种情况）
外连接(Outer-Join)
* 定义：两个关系R与S进行连接时，如果关系R(或S)中的元组在S(或R)中找不到相匹配的元组，则为了避免该元组信息丢失，从而将该元组与S(或R)中假定存在的全为空值的元组形成连接，放置在结果关系中，这种连接称之为外连接(Outer Join)。
* 外连接= 自然连接(或 $\theta$连接) + 失配的元组(与全空元组形成的连接)
* 外连接的形式：左外连接、右外连接、全外连接
* 左外连接= 自然连接(或 $\theta$连接) + 左侧表中失配的元组，记为：$\sqsupset_\rtimes$
* 右外连接= 自然连接(或 $\theta$连接) + 右侧表中失配的元组，记为：$\ltimes_\sqsubset$
* 全外连接= 自然连接(或 $\theta$连接) + 两侧表中失配的元组，记为：$\sqsupset\Join\sqsubset$
#### 书写思路
检索是否涉及多个表
* 如不涉及，则可直接采用并、差、交、选择与投影，只要注意条件书写正确与否即可
* 如涉及多个表，则检查
* 能否使用自然连接，将多个表连接起来(多数情况是这样的)
* 如不能，能否使用等值或不等值连接($\theta$-连接)
* 还不能，则使用广义笛卡尔积，注意相关条件的书写
* 连接完后，可以继续使用选择、投影等运算，即所谓数据库的“选投联”操作