基本概念
- 关系代数：是从抽象的观点出发学习数据库查询的问题， 定义查询运算符
- 关系代数中，表达式的运算数是关系，关系用关系名表示
- 将要描述的任何运算符用于关系或用于关系的表达式，逐渐构造更为复杂的表达式
- 一个查询就是关系代数的一个表达式
- 关系代数运算包括:
- 集合运算符：∪(并)，-(差)，∩(交)，╳((广义)笛卡尔积)
- 专门的关系运算符：σ(选择)，π(投影)，θ(连接)，|╳|(自然连接)，÷(除)
- 逻辑运算符：∧(与)，∨(或)，┐(非)
- 算术比较运算符：>(大于)，≥(大于等于)，<(小于)，≤(小于等于)，=(等于)，≠(不等于)
- 并集、差集、选择、投影、改名运算不能由其他关系运算导出，称为基本运算。
- 交集、笛卡尔积、θ连接、自然连接可由其他关系运算导出，称为导出运算(非基本运算)。
- 设关系模式R(A1,A2,……An)，它的一个关系为R，则用t∈R表示t是R的一个元组，t[Ai]表示元组t中相应于属性Ai 的一个分量。
- 象集(image set)：给定一个关系R(X,Y)，X和Y为属性集， 当t[X]=x时，x在R中的象集是
- R中的属性集X上值为x的诸元组在Y上分量的集合，表示为Yx={t[Y]|t∈R,t[X]=x}
集合运算
- 集合运算：并、交、差。对于关系R和S，
- R∪S R和S的并，是在R中或在S中的元组的集合，即R和S的所有元组合并，结果中有重复的元组，则只保存一次。R∪S={t|t∈R∨t∈S}
- R∩S R和S的交，是在R和S中都存在的元组的集合。R∩S={t|t∈R∧t∈S}
- R-S R和S的差，是在R中而不在S中的元组的集合。R-S={t|t∈R∧┐t∈S}
- 交运算可以用差运算来表示：R∩S=R-(R-S)
- R-S不同于S-R，后者是在S中而不在R中的元组的集合。这三种基本集合运算不改变关系模式。
- 是否任意两个关系都可以进行集合运算？
关系的集合运算
是否任意两个关系都可以进行集合运算？ 需要R和S两个关系满足下面条件：
- R和S的模式必须具有相同个数的属性集
- R中第i个属性和S中第i个属性必须来自同一个域（相同的数据类型）
- 如果要对属性数相同但属性名不同的关系进行集合运算， 则可以利用改名运算符来改变其中一个或两个关系的模式， 使它们具有相同的属性集
关系的集合运算举例
假定有两个关系R和S，都是关系MovieStar的实例。R和S的当前实例分别在下图给出。
投影
- 投影运算符：从关系R产生一个只有R的某些列的新关系
投影运算是单目运算。表示为 πA1,A2,…An®={t[A1,A2,…An]|t∈R}
- 结果关系的模式是属性集{A1,A2,…,An}，并保持列出的顺序
- 投影后有重复的元组，则结果中只保存一次。投影运算可以改变关系的属性次序！
投影举例
考虑关系模式Movie，将该关系投影到前三个属性上
| title |
year |
length |
inColor |
studioName |
produc# |
| Star Wars |
1977 |
124 |
true |
Fox |
11111 |
| Mighty Ducks |
1991 |
104 |
true |
Disney |
22222 |
| Wayne’s World |
1992 |
95 |
true |
Paramount |
33333 |
用上面投影表达式将该关系投影到前三个属性上，结果如下
| title |
year |
length |
| Star Wars |
1977 |
124 |
| Mighty Ducks |
1991 |
104 |
| Wayne’s World |
1992 |
95 |
选择
- 选择运算符：将关系R中满足某种条件C的元组组成一个新的关系，记为σC®。选择运算是单目运算。σC®={t|t∈R∧C(t)为真}
- 运算结果关系的模式中属性的顺序应保持与R同样的顺序
- 条件C由运算项和运算符组成
- 运算项是常量或R的属性（用属性名表示）
- 运算符有算术比较运算符（>，≥，<，≤，=，≠）和逻辑运算符（ ∧ ∨ ┐）
- 条件C的结果为逻辑值“真”或“假”
- 运算方法：
- 把条件C用于R的每个元组t，计算是否满足条件。如果将条件C的每个属性用元组中的相应属性代替后条件C为真，那么， 元组t就是出现在选择运算σC®的结果中的元组之一，否则t不出现在结果中
选择举例
| title |
year |
length |
inColor |
studioName |
produc# |
| Star Wars |
1977 |
124 |
true |
Fox |
11111 |
| Mighty Ducks |
1991 |
104 |
true |
Disney |
22222 |
| Wayne’s World |
1992 |
95 |
true |
Paramount |
33333 |
查询长度不少于100分钟的电影信息
| title |
year |
length |
inColor |
studioName |
produc# |
| Star Wars |
1977 |
124 |
true |
Fox |
11111 |
| Mighty Ducks |
1991 |
104 |
true |
Disney |
22222 |
| title |
year |
length |
inColor |
studioName |
produc# |
| Star Wars |
1977 |
124 |
true |
Fox |
11111 |
- 选择是从关系的水平方向上进行运算的，而投影则是从关系的垂直方向上进行的
笛卡尔积
- 笛卡尔积：关系R、S的笛卡尔积是两个关系的元组对的集合所组成的新关系，用R╳S表示。该元素对是选择R的任何元素作为第一个元素，S的元素作为第二个元素构成的
- 结果关系模式是R和S的模式的并集，按代数表达式的顺序，R的分量在S的分量之前
- 若R有k1个元组，S有k2个元组，则关系R和关系S的笛卡尔积有k1*k2个元组
- 如果R和S有同名属性，就需要为同名属性改名
- 例如：R和S的模式中都有属性A，则在结果关系模式中对来自R的属性用R.A表示，对来自S的属性用S.A表示
笛卡尔积举例
假设关系R和S具有如下给出的模式和元组。求乘积R╳S包括的元组。
自然连接
- 自然连接：两个关系R和S的自然连接是从R×S的结果集中，选取在公共属性上具有相同值的元组，组成新的关系。表示为R|╳|S。该运算是二目运算
- R、S的公共属性是指属性集的交集（名称及类型相同）
- 公共属性在结果关系模式中只出现一次
- 假设A1,A2,…,An是R和S的公共属牲，当且仅当R的元组r和S的元组s在A1,A2,…,An每个属性上都一致时，R的元组r和S 的元组s才能成功地组成一对，作为自然连接的结果。此时构成一个连接元组
- 没能在连接中和另一个关系的任何元组匹配的元组称为悬挂元组
- 自然连接中可能会出现R中一个元组和S中几个元组连接的情况
自然连接举例
- R和S的自然连接可看作是在广义笛卡尔积R×S中选出同名属性上符合相等条件元组，再进行投影，去掉重复的同名属性，组成新的关系。
即首先R╳S。然后在如下条件C下进行选择
R.A1=S.A1 AND R.A2=S.A2 AND … AND R.An=S.An
其中，A1,A2,…,An是R和S的公共属性。最后再投影。
- 假设L是一个属性表，其中前面的属性是关系R的所有属性，后面的属性是除了共有属性以外的关系S的属性。则 R|╳|S=πL(σC(R╳S))
基本和导出运算举例
- 关系U和V的自然连接可以用乘积、选择和投影的形式写出:πA,U.B,U.C,D(σ(U.B=V.B)∧(U.C=V.C)(U╳V))， 即首先得到乘积U╳V，然后在每对同名属性（在这个例子中是B和C）之间进行等值选择。最后投影到所有的属性上，但只保留其中一个B和一个C
θ连接
- θ连接，把两个关系的元组按指定条件匹配成对。R和S基于条件C的θ连接表示为R|╳|CS。该运算是二目运算
- 该运算的步骤如下:
- 获得R和S的笛卡尔积
- 从乘积中选择满足条件C的元组
- 结果模式是R和S模式的并集，如果需要指出属性来自哪个模式，则可在属性前面加上前缀R.或S.
- θ连接可以通过乘积和选择两个运算表达R|╳|CS=σC(R╳S)
θ连接举例
- 图中的结果模式包括所有6个属性，U和V的公共属性用U.和V.作为前缀加在相应的属性前面以区别它们
- 若θ连接的条件是两个关系的公共属性相等，则是否等同于自然连接？
- 不同，自然连接的公共属性合并成一个副本
改名
- 改名：使用运算符ρs(A1,A2,…,An)®把关系R改名
- 结果关系和初始关系R有完全相同的元组，但关系名是S，并且结果关系S的属性从左至右依次命名为A1,A2,…,An
- 如果只想把关系改名为S，而属性名和R中的一样，用ρs®
- 求R╳ρs(X,C,D)(S)
除法
- 除法：是二目运算
- 设有关系R(X,Y)与关系S(Y,Z)，其中X,Y,Z为属性集合，R中的Y与S中的Y可以有不同的属性名，但对应属性必须出自相同的域
- 关系R除以关系S所得的商是一个新关系P(X)，P是R中满足下列条件的元组在X上的投影：
- 元组在X上分量值x的象集Yx包含S在Y上投影的集合。记作：
- R÷S={tr[X]|tr∈R∧πy(S)⊆Yx}
- 其中，Yx为x在R中的象集，x=tr[X]
- 除法运算为非基本运算，可以表示为：R÷S=πx®－πx(πx®×πy(S)－R)
除法举例
查询中的复合运算
- 可以通过将运算符用于子表达式，必要时用括号表明运算项分组，来构造关系代数表达式
- 查询“由Fox公司制作的至少有100分钟长的电影的名称和年份是什么?”
Movie(title,year,length,filmType,studioName)
- 要计算这个查询的答案，可以按下面步骤进行
- 选择长度length≥l00的Movie元组
- 选择StudioName='Fox’的Movie元组
- 计算(1)和(2)的交集
- 将来自(3)的关系投影到属性title和year上
- 自然连接运算的一个用途是重组被分解的关系
- 设Movie1具有模式
{title,year,length,filmType,studioName}，Movie2具有模式 {title,year,starName}，查询“主演的电影至少100分钟长的影星的名字”
- 该查询首先用自然连接|╳|把在title和year上一致的元组成功地匹配成对,也就是把同一部电影的元组匹配成对，然后使用一个选择，其条件是要求电影的长度至少是100分钟。然后投影到所要求的属性starName上。表达式如下：
- 除法运算同时从行和列的角度进行运算，适合于包含“全部”之类的短语的查询。
SCore(SNO,CNO,grade),Course(CNO,Cname,Ccredit), Student(SNO,Sname,Ssex,Sbirthday)查询选修了全部课程的学生的学号和姓名。- 首先需要获得全部课程信息，然后利用除法得到具有全部课程成绩的学生的学号， 再利用自然连接将学生的姓名获得。
- (πSNO,CNO(SCore)÷πCNO(Course))|╳|πSNO,SName(Student)
关系代数习题注意事项
- 问题要求回答的内容才要显示，其他内容不能有。别忘了用投影显示要查询的属性
- 笛卡尔积、自然连接和θ连接要分清
- 笛卡尔积是两个关系的元组的排列组合，没有任何条件
- 自然连接要求元组中相同属性有相同的值
- θ连接是在做了笛卡尔积之后再选择符合条件的组合
- 复杂的查询可以首先将它分解成一步一步的简单的查询
关系代数练习1
有关系模式如下，写出关系代数表达式回答下列查询： Product(maker(制造商),model,producttype(产品类型)) PC(model(型号),speed,ram(内存),hd(硬盘),cd(光驱),price)
- 找出PC速度至少为150的型号
- 列出制造商制造的所有的PC的型号、速度、价格和相应的制造商名
- 找出价格高于1000美元的PC的制造商
- 找出速度大于133或者内存大于256的PC的型号
关系代数练习2
有关系模式如下，写出关系代数表达式回答下列查询： Product(maker(制造商),model,producttype(产品类型)) PC(model(型号),speed,ram(内存),hd(硬盘),cd(光驱),price) Laptop(model,speed,ram,hd,screen,price) Printer(model,color(颜色),type(类型),price)
对关系的约束
- 如果R和S是关系代数表达式，则
- R=Ø是一个约束，它表明“R的值必须为空”，即“在R的结果中没有元组”
- R⊆S(R属于S)是一个约束。它表明“R中的每个元组也必须在S中”。而S可能包括不是R的元组。
- 约束R⊆ S也可以写为R-S=Ø，R=Ø也可以写为R⊆Ø。R-R=Ø
- 参照完整性约束：如果实体A与实体B相关，那么B必须实际存在
在关系模型中，如果一个关系R的一个元组有一个分量值为v, 那么根据用户的设计意图，可以期望v将出现在另一个关系S 的某个元组的特定分量中
参照完整性约束举例
- 考虑两个关系
Movie(title,year,length,inColor,studioName,producerC#) MovieExec(name,address,cert#,networth)
- 如果要求它们之间存在参照完整性约束，即假定每部电影的制片人必须出现在MovieExec关系中
- 也就是每个Movie元组的producerC#分量也必须出现在某 个MovieExec元组的cert#分量中
- 则可以用集合的包含关系来表达这个约束
- 如果某个参照完整性约束涉及到多个属性，也可以类似地表达。例如，要求在关系
starsIn(movieTitle,movieYear,starName)中涉及到的任何电影也出现在下面的关系中Movie(title,year,length,inColor,studioName,producerC#) 在两个关系中电影都用title-year对表示。则用下面表达式表达这样的参照完整性约束
- 注意前后投影顺序要一致
附加约束
- 域约束就是要求属性的值有特定的数据类型，例如整型或长度为30的字符串
- 如果域约束涉及到属性所需要的特定值，属性可取值的集合可以用选择条件语言表达，那么这个域约束就可以用代数约束语言表达
- 假定希望MovieStar“性别”属性仅有的合法值为‘F’ 和‘M’。则可以用如下的代数方法表示这个约束
附加约束举例
- 有关系MovieExec(name,address,cert#,networth)和Studio(name,address,presC#)，假定要求一个人必须至少有 净资产$10000000才可以做电影制片公司的总裁。试将该约束用关系代数表示。
- 首先用θ连接把两个关系连起来，θ连接中利用的条件是来自studio的presC#和来自MovieExec的cert#相等。该连接把包含制片公司和行政长官的两个元组组合成对。
- 如果从这个关系中选择净资产少于$10000000的元组，则要求它必须为空。这样，可以把该约束表达为
关系代数小结
- 并R∪S、交R∩S、差R-S
- 投影 从关系R产生一个只有R的某些列的新关系
- 选择 σC®保留满足条件C的R中的元组
- 笛卡尔积 R╳S是两个关系R和S的元素对的集合
- 自然连接 R|╳|S，结果关系的元组是R和S元组在公共属性上取值一致的所有元组的组合
- θ连接 R|╳|CS，结果关系是首先获得R和S的积(笛卡尔积)，然后从乘积中选择满足条件C的元组
- 改名 ρs(A1,A2,…,An)®，结果关系名是S，属性从左至右依次命名为A1,A2,…,An
- 除法R÷S是R中满足下列条件的元组在X上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合
