关系代数全解

《关系代数全解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关系代数(数据库)关系代数是一阶逻辑的分支，是闭合于运算下的关系的集合。运算作用于一个或多个关系上来生成一个关系。关系代数是计算机科学的一部分。在纯数学中的关系代数是有关于数理逻辑和集合论的代数结构。介绍关系代数在1970年E.F.Codd发表数据的关系模型之前很少受到注意。Codd曾是皮尔士选集编辑者ArthurW.Burks的博士研究生。Codd提议这样一种代数作为数据库查询语言的基础。第一个基于Codd的代数的查询语言是ISBL，许多作者都认同这个先驱的工作展示了一个使Codd的想法成为有用语言的方式。商务系统12是追随ISBL先例的短命工业级实

2、力的关系DBMS。在1998年ChrisDate和HughDarwen提议了一种叫TutorialD的语言，意图用于教学关系数据库理论，它的查询语言也吸取了ISBL的想法。Rel是TutorialD的一个实现。即使SQL的查询语言也松散的基于了关系代数，尽管SQL中的操作数(表)不完全是关系，很多有用的关于关系代数的理论在SQL对应者中不成立。因为关系被解释为某个谓词的外延，关系代数的每个运算在谓词演算中都有对应者。例如，自然连接是逻辑AND()的对应者。如果关系R和S分别表示谓词p1和p2的外延，则R和S的自然连接(RS)是表示谓词p1p2的外延的关

3、系。认识到Codd的代数事实上关于一阶逻辑不完备是很重要的。实现它会引起不可逾越的特定计算困难。为了克服这些困难，他限制操作数为有限关系，并提议了对否定(NOT)和析取(OR)的有限支持。类似的限制在很多其他基于逻辑的计算机语言中也能见到。Codd定义术语关系完备性来称呼一个语言除了他提议的限制之外关于一阶逻辑是完备的。在实践中这些限制对他的关系代数用于数据库用途的适用性没有不利作用。原始运算如同任何代数，一些运算是原始的，而可以通过原始运算来定义的另一些运算是导出的。尽管逻辑中的AND,OR和NOT的选取，某种程度上是任意性的是众所周知的，Codd对

4、他的代数作了类似的任意选取。Codd的代数的六个原始运算是“选择”、“投影”、笛卡尔积(也叫做“叉积”或“交叉连接”)、并集、差集和“重命名”。(实际上，Codd忽略了重命名，而ISBL的发明者显著的包括了它)。这六个运算在省略其中任何一个都要损失表达能力的意义上是基本的。已经依据这六个原始运算定义了很多其他运算。其中最重要的是交集、除法和自然连接。事实上ISBL显著的用自然连接替代了笛卡尔积，它是笛卡尔积的退化情况。总之，关系代数的运算有与域关系演算或元组关系演算同样的表达能力。但是出于前面介绍中给出的原因，关系代数有严格弱于没有函数符号的一阶谓词演

5、算的表达能力。关系代数实际上对应于一阶逻辑的子集，即没有递归和否定的Horn子句。集合运算尽管六个基本运算中有三个取自集合论，在它们的关系代数对应者中存在额外的约束:对于并集和差集，涉及到的两个关系必须是“并集相容”的—就是说，两个关系必须有同样的属性集合。因为交集可以用差集来定义，交集所涉及的两个关系也必须是并集相容的。笛卡尔积定义得与集合论有所不同，这里的元组是平坦的、无子元组的。就是说，不同于集合论，那里的n元组和m元组的笛卡尔积是2元组，而关系代数中它们的笛卡尔积把这个2元组展平为n+m元组。更形式的说，R×S被定义为:RS={rs

6、rR,sS

7、}此外，对于要定义的笛卡尔积，涉及的两个关系必须有不相交表头—就是说，它们一定不能有公共属性名字。投影(π)主条目：投影(关系代数)投影是写为的一元运算，这里的是属性名字的集合。这种投影的结果定义为当所有在中的元组被限制为集合的时候所获得的集合。选择(σ)主条目：选择(关系代数)广义选择是写为的一元运算，这里的是由正常选择中所允许的原子和逻辑算子(与)、(或)和(非)构成的命题公式。这种选择选出中使成立的所有元组。重命名(ρ)主条目：重命名(关系代数)重命名是写为的一元运算，这里的结果同一于，除了在所有元组中的字段被重命名为字段之外。它被简单的用来重命

8、名关系的属性或关系自身。连接和类似连接的运算自然连接(⋈)自然连接是写为(R⋈S)的二元运算，这里的R和S是关系。[1]自然连接的结果是在R和S中的在它们的公共属性名字上相等的所有元组的组合。例如下面是表格“雇员”和“部门”和它们的自然连接:雇员NameEmpIdDeptNameHarry3415财务Sally2241销售George3401财务Harriet2202销售部门DeptNameManager财务George销售Harriet生产Charles雇员⋈部门NameEmpIdDeptNameManagerHarry3415财务GeorgeSal

9、ly2241销售HarrietGeorge3401财务GeorgeHarriet2202销售H