关系代数.docx
《关系代数.docx》由会员分享，可在线阅读，更多相关《关系代数.docx（13页珍藏版）》请在冰点文库上搜索。
关系代数
.4关系代数
关系代数是一种抽象的查询语言，通过对关系的运算来表达查询。
关系代数的运算对象是关系，运算结果也是关系。
系代数运算可以分为四类：
1．普通的集合运算：
并、交、差
2．删除一部分关系的运算
选择运算“σ”会删除某些行投影运算“π”会删除某些列
3．合并两个关系的运算
“笛卡儿积”运算把两个关系的元组以所有可能的方式组合起来.
“连接”运算有选择地从两个关系取出元组组合在一起
4．改名运算
不改变关系的元组，只改变关系的模式：
改变属性的名字或者关系本身的名字
一、关系的集合运算
三种最普通的集合运算：
并、交和差：
∪S，R和S的并，它是R中的元素和S中的元素共同组成的集合。
∩S，R和S的交，它是既出现在R中又出现在S中的元素组成的集合。
―S，R和S的差，它是只在R中出现，不在S中出现的元素组成的集合。
要想对两个关系R和S进行上述运算，R和S必须满足如下条件：
R和S的模式具有相同的属性集
在对R和S进行集合运算之前，要对R和S的属性列进行排序，保证两个关系的属性顺序相同
1.并,R∪S={r|r∈R∨r∈S}
关系R：
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
9900548
高亮亮
20
自动化系
关系S
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
9900203
方平
18
外语系
R∪S:
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
9900548
高亮亮
20
自动化系
9900203
方平
18
外语系
2.交,R∩S={r|r∈R∧r∈S}
R∩S:
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
3.差,R-S={r|r∈R∧rS}R-S:
StudentNo
StudentName
Age
Dept
9900548
高亮亮
20
自动化系
二、投影运算
投影运算符是π，该运算作用于关系R将产生一个新关系S，S只具有R的某几个属性列。
投影运算的一般表达式如下：
S=πA1,A2,…,An（R）
S是投影运算产生的新关系，它只具有R的属性A1,A2,…,An所对应的列。
例：
对于关系表：
Student
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
9900548
高亮亮
20
自动化系
9900203
方平
18
外语系
投影运算：
πStudentNo,StudentName（Student）结果为：
StudentNo
StudentName
9900011
李明
9900548
高亮亮
9900203
方平
三、选择运算（σ）
选择运算符是σ，该运算符作用于关系R也将产生一个新关系S，S的元组集合是R的一个满足某条件C的子集。
选择运算的一般表达式为：
S=σC（R）
S的模式与R的模式完全相同。
C是我们所熟悉的条件表达式。
可以由AND，OR，NOT等子条件连成的复杂条件。
例：
仍然用上面的例子，那么作如下运算：
σAge>18（Student）
结果应该是：
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
9900548
高亮亮
20
自动化系
例：
查询计算机系年龄大于18的学生资料，可以用如下表达式：
σAge>18ANDDept=“计算机系”（Student）
结果是：
StudentNo
StudentName
Age
Dept
9900011
李明
19
计算机系
四、笛卡尔积（×）
两个关系R和S的笛卡尔积记作R×S，它的关系模式属性是R和S的模式的并集。
R×S是把R和S的元组以所有可能的方式组合起来，因此，R×S拥有的元组数量应该是R的元组数与S的元组数的乘积。
例：
假设关系R有两个属性，分别是A和B；关系S有三个属性，分别是B、C和D。
R的当前实例有两个元组，S的当前实例有三个元组：
如下图所示：
关系R
A
B
a
l
b
n
R×S:
在关系R×S中，关系模式应有五个属性：
A、、、C和D，R×S有六个元组：
A
RB
SB
C
D
a
l
f
g
h
a
l
l
x
y
a
l
n
p
x
b
n
f
g
h
b
n
l
x
y
b
n
n
p
x
五、自然连接
两个关系R和S的自然连接，记作R￥S，得到的关系模式属性是R和S模式的并集。
公共属性只保留一个。
R￥S的元组是：
假设A1,A2,…,An是R和S的模式中的公共属性，那么如果R的元组r和S的元组s在这些属性上取值都相同，r和s组合而成的元组就
归入R￥S中。
例：
对于上图的R与S，R￥S为：
A
B
C
D
a
l
x
y
b
n
p
x
注意：
只有两个关系的元组在所有公共属性上取值都相同，才可以将它们的组合放入两个关系的自然连接中。
例：
关系U
A
B
C
e
a
c
e
b
c
关系V
B
C
D
a
b
d
a
c
f
g
c
h
六、q连接
两个关系R和S基于条件C的θ连接
用R￥cS表示，它是这样得到的：
先作R和S的笛卡尔积，然后从R╳S的元组中选择满足条件C的元组集合。
θ可以是：
>,<,=,≤,≠,≥合成的条件。
例：
R￥≠S的结果：
例：
R￥≠S的结果:
A
RB
SB
C
D
a
l
f
g
h
a
l
n
p
x
b
n
f
g
h
b
n
l
x
y
θ连接中的条件可以是由AND,OR,NOT连成的复杂条件。
如：
R￥≠ANDC=’g’）S
七、改名（ρ）
运算ρS（A1,A2,…,An）（R）用来把关系R改名为关系S，同时把关系S的属性从左至右依次命名为A1,A2,…,An。
假如我们只想改变关系名，不想改变关系模式中的属性名，那么用如下形式
ρS（R）
例：
ρS（X,C,D）（S），这样，改名后的笛卡尔积
R×ρS（X,C,D）（S）的结果：
A
B
X
C
D
a
l
f
g
h
a
l
l
x
y
a
l
n
p
x
b
n
f
g
h
b
n
l
x
y
b
n
n
p
x
八、复合运算：
将以上各种运算加以组合，完成功能强大的查询。
必要时可用括号来表明运算的次序。
例：
查询计算机系年龄大于18岁的学生的学号和姓名：
πStudentNo,StudentName（σAge>18ANDDept=“计算机系”（Student））
例：
查询成绩超过80分的学生姓名（只要有一门课的成绩超过80分即可），可用如下表达式：
πStudentName（σScore>80（Student￥SC））
九、基本运算和导出运算
交集可以用集合差的形式表达：
R∩S=R―（R―S）
除了交、θ连接、自然连接这三种可由其他运算导出的运算之外，另外六种运算——并、差、选择、投影、笛卡尔积和改名都是基本运算，每一种都
不能由另外五种运算导出。
基本运算：
并、差、选择、投影、笛卡尔积、改名
导出运算：
交、θ连接、自然连接
说明：
1.R∩S=R―（R―S）=S-（S-R）
2.θ连接:
可看成是笛卡尔积后的θ选择的结果。
3.自然连接:
是θ连接的一个特例。
去掉重复属性的等值连接。
关系演算
关系演算分类:
元组关系演算,以元组为变量
域关系演算,以域为变量
元组关系演算
元组关系演算表达式的一般形式：
{t|φ（t）}其中t为元组变量，φ（t）是以元组变量t为基础的公式。
公式：
公式是递归定义的：
1.原子公式是公式；
2.假如φ1（t）和φ2（t）是公式，那么￢φ1，φ1∧φ2，φ1∨φ2也都是公式，它们为真的条件分别是：
“φ1非真”，“φ1和φ2皆为真”，
“φ1与φ2中至少有一个为真”；
3.假如φ是公式，那么（$t）（φ）和（"t）（φ）也都是公式，它们为真的条件分别是：
“至少有1个元组t使得φ为真”，“所有的元组t都使φ为真”
。
其中为$存在量词，为"全称量词。
若在变量前加上量词，则变量为约束变量。
4.只有按上述三个规则的有限次组合形成的才是公式。
原子公式:
1.R（t），R（t）表示t是关系R的一个元组；
2.t[i]qs[j]，其中t和s是元组变量，q是算术比较运算符（如>、=等），t[i]qs[j]表示元组t的第i个分量与元组s的第j个分量满足q关系；
例：
t[1]>s[3]，表示t的第1个分量大于s的第3个分量。
3．t[i]qC或Cqt[i]，其中C表示一个常量，其他含义同上。
t[i]qC表示t的第i个分量与常量C满足q关系，
例如t[1]<8表示t的第1个分量小于8。
元组演算表达式：
{t|φ（t）}其中t为元组变量
其含义：
使φ为真的元组t的集合。
在关系演算公式中，各种运算符的优先级如下：
算术比较运算符优先级最高；
量词优先级次之，且存在优先级高于全称；
逻辑运算符优先级最低，且￢的优先级高于∧，∧的优先级高在于∨；
若加括号，则括号内优先。
关系代数运算的元组运算等价表示：
1.交
R∩S用{t|R（t）∧S（t）}表示。
2.并
R∪S用{t|R（t）∨S（t）}表示。
3.差
R―S用{t|R（t）∧￢S（t）}表示。
4.选择
σC（R）用{t|R（t）∧C’}表示。
其中C’是C的等价条件，只是把C中的属性名在C’中换成t[i]的形式，i代表属性对应的是元组的第几个分量。
5.投影
πi1,i2,…,in（R）={t（n）|（$t）（R（r）∧t[1]=r[i1]∧t[2]=r[i2]∧…∧t[n]=r[in]）}
其中n为投影后得到的元组t的分量数，r[ij]（j=1,2,…,n）代表元组t的属性j所对应的元组r的相应分量。
6.笛卡尔积
R×S用如下形式表示：
{t（m+n）|（$r（m））（$s（n））（R（r）∧S（s）∧t[1]=r[1]…t[m]=r[m]∧t[m+1]=s[1]…∧t[m+n]=s[n]）}
其中R的属性个数为m，S的属性个数为n。
7.自然连接
自然连接的表示基本上与笛卡尔积相似，假设关系R为R（A，B），关系S为S（B，C，D），那么R与S的自然连接可以用关系演算表达式表示如下：
{t（2+3-1）|（$r
（2））（$s（3））（R（r）∧S（s）∧t[1]=r[1]∧t[2]=r[2]∧t[2]=s[1]∧t[3]=s[2]∧t[4]=s[3]）}
表达式中粗体部分表达了等值的连接。
8.θ连接
R∞CS的表示方法可以参考R×S和σC（R）的方法。
例：
R（A，B）与S（B，C，D）的θ连接：
R∞≠S
可以用元组关系演算表达式表示如下：
{t（2+3）|（$r
（2））（$s（3））（R（r）∧S（s）∧t[1]=r[1]∧t[2]=r[2]∧t[3]=s[1]∧t[4]=s[2]∧t[5]=s[3]）∧r[2]≠s[1]}}例：
R
A
B
1
2
3
4
S
A
B
1
4
2
3
1.{t|R（t）∨S（t）}
结果：
A
B
1
2
3
4
1
4
2
3
2.{t|（$s）（R（t）∧S（s）∧t[1]=s[1]）}
结果：
A
B
1
2
3.{t|（"s）（R（t）∧S（u）∧t[2]>u[1]）}
结果：
A
B
3
4
9.复杂的关系代数表达式：
∏Studentname（sscore>80（student∞SC））
用关系演算表示为：
{t
（1）|（$u）（$v）（Student（u）∧SC（v）∧t[1]=u[2]∧u[1]=v[1]∧v[3]>80）}
表达式中，粗体部分表示投影，斜体部分表示连接。
域关系演算
域关系演算与元组关系演算类似，但在表达式中使用的是域变量。
域变量：
指元组分量的变量。
域关系演算中的原子公式与公式的概念与元组关系演算类似。
元组关系演算转换为域关系演算的基本方法：
元组关系演算表达式为：
{t|φ（t）}
转换方法：
（1）.如果是t是有n个分量的元组变量，则为t的每个分量t[i]引进一个域变量ti，用ti来替代公式中所有的t[i]。
相应的域关系表达式则有了n个
域变量，
形式为：
{t1,t2,…,tn|φ（t1,t2,…,tn）}
（2）.出现存在量词（$u）,或者全称量词（"u）时，如果u是有m个分量的元组变量，则为每个分量u[i]引进一个域变量ui,将量词辖域内所有的u用
u1u2…um替换，所有u[i]用ui替换。
例1：
查询计算机系年龄18岁的学生。
元组演算表达式：
{t|Student（t）∧t[3]=18∧t[4]=”计算机系”}
域关系演算表达式：
{t1t2t3t4|Student（t1t2t3t4）∧t3=18∧t4=”计算机系”}
例2：
查询一门课成绩超过80分的学生姓名。
元组演算表达式:
{t
（1）|（$u）（$v）（Student（u）∧SC（v）∧t[1]=u[2]∧u[1]=v[1]∧v[3]>80）}
域关系演算表达式：
{t1|（$u1u2u3u4）（$v1v2v3）（Student（u1u2u3u4）∧SC（v1v2v3）∧t1=u2∧u1=v1∧v3>80）}
观察表达式：
t1=u2∧u1=v1可知，t1可以用来替代u2,u1可用来替代v1,因此
进一步省略几个域变量，则表达式可为：
{t1|（$u1u3u4）（$v2v3）（Student（u1t1u3u4）∧SC（u1v2v3）∧v3>80）}
升级会员 