/
4、关系演算.md
219 lines (109 loc) · 9.02 KB
/
4、关系演算.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
204
205
206
207
208
209
210
211
212
213
214
215
216
### 关系演算
* 关系演算是以数理逻辑中的谓词演算(谓词表示个体的一种属性)为基础的
* 关系演算是描述关系运算的另一种思维方式,以个体为单位,不以集合为单位
* SQL语言是继承了关系代数和关系演算各自的优点所形成的
* 按照谓词变量的不同,可分为关系元组演算和关系域演算
* 关系元组演算是以元组变量作为谓词变量的基本对象
* 关系域演算是以域变量作为谓词变量的基本对象
#### 元组演算
关系元组演算公式的基本形式:{t | P(t) }
* 表示:所有使谓词P 为真的元组t 的集合
* t 是元组变量
* t $\in$r 表示元组t 在关系r 中
* t [A] 表示元组t 的分量,即t 在属性A 上的值
* P 是与谓词逻辑相似的公式, P(t)表示以元组t 为变量的公式
* P(t)可以如下递归地进行定义
* 三种形式的原子公式是公式:s ∈R、s[A] $\theta$c、s[A] $\theta$u[B]
* s ∈R:t 是关系R 中的一个元组
* s[A] $\theta$c:元组分量s[A]与常量c 之间满足比较关系$\theta$
* s[A] $\theta$u[B]:s[A] 与u[B] 为元组分量,A和B分别是某些关系的属性,他们之间满足比较关系$\theta$.
* $\theta$是比较运算符, $\theta$$\in${ $\gt$, $\geq$, $\lt$, $\leq$,=,$\lt\gt$}
* 如果P是公式,那么$\urcorner$P也是公式
* 如果P1 , P2是公式,则P1 $\wedge$P2, P1 $\vee$P2 也是公式
* 如果P(t)是公式,R是关系,则$\exists$(t$\in$R)(P(t)) 和 $\forall$(t$\in$R)(P(t))也是公式
* 需要时可加括弧
* 上述运算符的优先次序自高至低为:括弧;$\theta$;$\exists$;$\forall$;$\urcorner$;$\wedge$;$\vee$;
* 公式只限于以上形式
元组演算例子:
已知 学生关系:Student(S#, Sname, Sage, Ssex, Sclass)课程关系:Course(C#, Cname, Chours, Credit, Tname)选课关系:SC(S#, C#, Score)
* 求学过李明老师讲授所有课程的学生姓名(全都学过)
* 关系代数:$\prod_{Sname}$($\prod_{Sname,C\#}$(Student $\Join$ SC $\Join$ Course ) $\div$ $\prod_{C\#}$($\sigma_{Tname=‘李明’}$ (Course)))
* 关系演算:{ t[Sname] | t $\in$ Student $\wedge$ $\forall$(u$\in$Course $\wedge$ u[Tname]=‘李明’)($\exists$(w$\in$SC)(w[S#]=t[S#] $\wedge$ w[C#]=u[C#] )) }
* 求没学过李明老师讲授任一门课程的学生姓名(全没学过)
* 关系代数:$\prod_{Sname}$(Student) $-$ $\prod_{Sname}$($\sigma_{Tname=‘李明’}$(Student $\Join$ SC $\Join$ Course))
* 关系演算:{ t[Sname] | t$\in$Student $\wedge$$\exists$ (u$\in$Course $\wedge$ u[Tname]=‘李明’)($\urcorner$$\exists$(w$\in$SC)(w[S#]=t[S#] $\wedge$ w[C#]=u[C#] )) }
* 求至少学过一门李明老师讲授课程的学生姓名(至少学过一门)
* 关系代数:$\prod_{Sname}$($\sigma_{Tname=‘李明’}$(Student $\Join$ SC $\Join$ Course))
* 关系演算:{ t[Sname] | t$\in$Student $\wedge$ $\exists$(u$\in$Course) $\exists$(w$\in$SC)( u[Tname]=‘李明’ $\wedge$ w[S#]=t[S#] $\wedge$ w[C#]=u[C#] ) }
* 求至少有一门李明老师讲授课程没有学过的学生姓名(至少有一门没学过)
* 关系代数:$\prod_{Sname}$(Student) $-$$\prod_{Sname}$($\prod_{Sname,C\#}$(Student $\Join$ SC $\Join$ Course) $\div$ $\prod_{C\#}$($\prod_{Tname=‘李明’}$(C)))
* 关系演算:{ t[Sname] | t$\in$Student $\wedge$ $\exists$(u$\in$Course $\wedge$ u[Tname]=‘李明’) ($\urcorner$$\exists$(w$\in$SC)$\wedge$w[S#]=t[S#] $\wedge$ w[C#]=u[C#] ) }
与关系代数的五种基本操作等价性
* 运算:R $\bigcup$S = { t | t$\in$R$\wedge$t$\in$S}
* 差运算:R$-$S = { t | t$\in$R$\wedge$$\urcorner$t$\in$S}
* 交运算:R $\bigcap$S = { t | t$\in$R$\wedge$t$\in$S}
* 广义笛卡尔积R(A) $\times$S(B) = { t | $\exists$(u$\in$R)$\exists$(s$\in$S)(t[A] = u[A] $\wedge$t[B] = s[B])}
* 选择运算:$\sigma_{con}$(R)={ t | t$\in$R $\wedge$F(con) }
* 投影运算: $\prod_A$( R ) = { t[A] | t$\in$R }
#### 域演算
关系域演算公式的基本形式:{ < x1, x2, ... , xn > | P ( x1, x2, ... , xn)}其中,xi 代表域变量或常量,P为以xi为变量的公式.
* 公式P可以递归地进行构造:
* 三种形式的原子公式是公式
* < x1, x2, ... , xn >∈R。其中xi 代表域变量或常量, 表示由域变量构成的< x1, x2, ... , xn >是属于关系R的
* x $\theta$c。其中,域变量x与常量c之间满足比较关系$\theta$。
* x $\theta$y。其中,域变量x与域变量y之间满足比较关系$\theta$
* $\theta$是比较运算符, $\theta$$\in${ $\gt$, $\geq$, $\lt$, $\leq$,=,$\lt\gt$}
* 如果P是公式,那么$\urcorner$P也是公式
* 如果P1 , P2是公式,则P1 $\wedge$P2, P1 $\vee$P2 也是公式
* 如果P(t)是公式,R是关系,则$\exists$(t$\in$R)(P(t)) 和 $\forall$(t$\in$R)(P(t))也是公式
* 需要时可加括弧
* 上述运算符的优先次序自高至低为:括弧;$\theta$;$\exists$;$\forall$;$\urcorner$;$\wedge$;$\vee$;
* 公式只限于以上形式
示例:
* 检索出不是03系的所有学生
{ <a,b,c,d,e,f> | <a,b,c,d,e,f>$\in$Student $\wedge$ e<>’03’}
* 检索不是(小于20岁的男同学)的所有同学的姓名
{ \<b> | $\exists$a,c,d,e,f (<a,b,c,d,e,f>$\in$Student $\wedge$ $\urcorner$(d< 20c = ‘男’))}
* 检索成绩不及格的同学姓名、课程及其成绩
{ <b,h,m> |$\exists$a,c,d,e,f,g,I,j,k (<a,b,c,d,e,f>$\in$Student$\wedge$(g,h,I,j,k) $\in$Course$\wedge$(a,g,m) $\in$SC $\wedge$ m<60 ) }
域演算与关系代数
* 域演算的所有操作都可以转化成关系代数,关系代数所有操作的定义都是用域演算定义的
域演算与关系元组演算的比较
* 基本形式
* 元组演算的基本形式:{ t | P(t) }
* 域演算的基本形式:{ < x1, x2, ... , xn> | P ( x1, x2, ... , xn)}
* 谓词变量
* 元组演算是以元组为变量,以元组为基本处理单位,先找到元组,然后再找到元组分量,进行谓词判断;
* 域演算是以域变量为基本处理单位,先有域变量,然后再判断由这些域变量组成的元组是否存在或是否满足谓词判断。
* 公式的运算符($\wedge$(与)、$\vee$(或)、$\urcorner$(非)、$\forall$(全称量词)和$\exists$(存在量词))是相同的,只是其中的变量不同
* 元组演算和域演算可以等价互换。
#### 安全性
* 不产生无限关系和无穷验证的运算被称为是安全的
关系代数是一种集合运算,是安全的
* 集合本身是有限的,有限元素集合的有限次运算仍旧是有限的。
关系演算不一定是安全的
* 例如:{ t | $\urcorner$(R(t)) }, { t | R(t) $\vee$t[2]>3 }可能表示无限关系
* R(t)是有限的,但不在R(t)中的元素就可能是无限的,后例中的t[2]>3是无限的。
* 再例如:($\exists$u)(con(u)), ($\forall$u)(con(u)) 可能导致无穷验证
* 前者被称为“假验证”,即验证所有元素是否都使得con(u)为false;
* 后者被称为“真验证”,即验证所有元素是否都使得con(u)为true。检验所有元素就可能造成无穷。
安全约束有限集合DOM
* 需要对关系演算施加约束条件,即任何公式都在一个集合范围内操作,而不是无限范围内操作,才能保证其安全性。
* DOM($\psi$)是一个有限集合,其中的每个符号要么是$\psi$中明显出现的符号,要么是出现在$\psi$中的某个关系R的某元组的分量。
* DOM主要用于约束中一些谓词的计算范围,它不必是最小集合。
#### 三种关系运算比较
关系运算有三种:关系代数、关系元组演算和关系域演算
三种关系运算都是抽象的数学运算,体现了三种不同的思维
* 关系代数---以**集合**为对象的操作思维,由集合到集合的变换
* 元组演算---以**元组**为对象的操作思维,取出关系的每一个元组进行验证,有一个元组变量则可能需要一个循环,多个元组变量则需要多个循环
* 域演算---以**域变量**为对象的操作思维,取出域的每一个变量进行验证看其是否满足条件
思维方式
* 关系代数:集合思维(并、差、积、选择、投影)
* 关系演算:逻辑思维($\wedge$(与)、$\vee$(或)、$\urcorner$(非)、$\forall$(全称量词)和$\exists$(存在量词))
三种运算之间是等价的
* 关系代数 与 安全的元组演算表达式 与 安全的域演算表达式 是等价的。即一种形式的表达式可以被等价地转换为另一种形式
三种关系运算都可说是非过程性的
* 相比之下:域演算的非过程性最好,元组演算次之,关系代数最差
三种关系运算虽是抽象的,但却是衡量数据库语言完备性的基础
* 一个数据库语言如果能够等价地实现这三种关系运算的操作,则说该语言是完备的
* 目前多数数据库语言都能够实现这三种运算的操作,在此基础上还增加了许多其他的操作,如赋值操作、聚集操作等