关系运算----关系演算

《关系运算----关系演算》由会员分享，可在线阅读，更多相关《关系运算----关系演算（5页珍藏版）》请在金锄头文库上搜索。

1、2.4 关系运算(二)关系演算 关系代数是将整个关系看作变元， 并以其作为基本运算单位， 同时以集合方法为关系运 算的理论基础。 如果将组成关系的基本成分例如元组或者属性域看作变量， 以其作为基本运 算单位， 同时以数理逻辑中谓词演算为相应关系演算的理论基础， 就得到了另外一种形式的 关系数据语言关系演算。 关系演算基于谓词演算。在谓词演算中，如果谓词中的变元是关系中的元组，则得到所 谓元组关系演算；如果谓词中的变元是关系中的属性域，则得到所谓域关系演算。这样，关 系演算就分为元组关系演算和域关系演算两类。 在 2.4 节和 2.5 节，均以本章 2.3.4 节中的关系数据库S,C,SC为背景

2、举例。这里 S (S#,Sn,Sex,Sa,Sd)；C (C#,Cn,P#,Tn)；SC (S#,C#,G)，其中各个属性的含义见 2.3.4 节。 2.4.1 元组关系演算 如果在一阶谓词演算表达式中，变量是以元组为演算单位，就称其为元组关系演算 (Tuple Relation Calculus)，其中元组变量表示关系中的元组，变量取值范围是整个关系。 1. 关系的元组演算表示 (1) 关系与谓词的对应 为了得到关系操作的元组关系演算表达式，需要考虑关系与谓词的联系。 ? 由关系 R 确定的谓词 P 在数理逻辑中我们知道，关系可用谓词表示，n 元关系可以由 n 元谓词表示。 设有关系R，它有

3、元组(r1,r2,rm)，定义关系R对应如下一个谓词 P (x1,x2, ,xn)。 当t =(r1,r2, ,rm)属于R时，t为P的成真的真值指派，而其他不在R中的任意元组t则是P 的成假指派。即是说，由关系R定义一个谓词P具有如下性质： P(t) = T (当 t 在 R 中)； P(t) = F (当 t 不在 R 中)。 ? 由谓词 P 表示关系 R 由于关系代数中 R 是元组集合，一般而言，集合是可以用满足它的某种特殊性质来刻 画与表示。如果谓词 P 表述了关系 R 中元组的本质特性，就可以将关系 R 写为： R=t | P(t) 这个公式就建立了关系(元组集合)的谓词表示，称之为

4、关系演算表达式。 (2) 元组关系演算表达式 元组关系演算表达式的严格数学描述是由“归纳定义”方式完成的。按照通常的思路， 元组演算表达式是由“关系演算公式”组成；“关系演算公式”是由“原子公式”组成。 原子公式 下述三类称为元组演算原子公式，简称原子公式： ? 谓词 R(t)是原子公式。 ? u(i)v(j)是原子公式。 ? u(i)a 是原子公式。 其中，t =(r1,r2,rm)是P的成真指派；u(i)表示元组u的第i个分量，v(j)表示元组v的第j 个分量；a是常量，u(i)a表示u的第i个分量与常量a有关系。 关系演算公式 利用原子公式可以递归定义关系演算公式： ? 原子公式是公式。

5、 ? 如果1，2是公式，则12，12，12和1均是公式。 ? 如果 是公式，r 是 中自由变元，则r()，r()是公式。 ? 所有公式由且仅由上述三种方式经过有限次操作生成。 在公式中，各种运算的优先次序规定如下： ? 比较运算符：、=、。 ? 量词：、。 ? 否定词：。 ? 合取、析取、蕴含运算符：、。 关系演算表达式 有了公式 的概念，以公式 作为特性就构成一个有若干元组组成的集合，即关系 R， 这种形式的元组集合就称其为关系演算表达式。关系演算表达式的一般形式为： t | (t) 其中，(t)为公式，t 为 中出现的自由变元。关系演算表达式也简称为关系表达式或 者表达式。 2. 关系操作

6、的元组演算表示 关系操作由 5 种基本操作， 它们在关系代数中分别对应 5 种基本运算， 这 5 种基本运算 可以用一阶谓词演算中的公式表示。 设有关系 R、S，其谓词表示为 R(t)和 S(t)，此时有 ? RS=t | R(t)S(t)； ? R S = (t | R(t)S(t)； ? F(R)= t | R(t)F ，其中F是一个谓词公式； ? (k) ui1,ui2,uik(R)=t|( u)R(u) t(1)=u(i1)t(2)=u(i2)t(k)=u(ik)? 其中 t (k)所表示的元组有 k 个分量，而 t(i)表示 t 的第 i 个分量，u(j)表示 u 的第 j 个分 量

7、。 (r+s)RS=t| u v(R(u)S(v)t(1)=u(i1)t(2)=u(i2)t(r)=u(ir)t(r+1)=v(j1)t(r+2)=v(j2)t(r+s)=v(js) ? ?例例 2-20 查询计算机科学系(CS)全体学生 Scs=t | S(t)t5= CS 例例 2-21 查询年龄大于 20 岁的学生姓名： S20=t | S(t)t4u4表示t的第一个分量大于等于u的第四个分量。 (2) 域演算公式 域演算公式(简称为公式)可以递归定义如下： ? 原子公式是公式。 ? 如果1，2是公式，则12，12，12和1均是公式。 ? 如果1是公式，ti(l)，ti(l)是公式。 ?

8、 所有公式由且仅由上述三种方式经过有限次操作生成。 例如(x1,x2,x3,x4,x5)=S(x1,x2,x3,x4,x5)(x521)x4=M是一个域演算公式。 域演算公式 中变量的自由出现与约束出现、 公式中自由变量 x 的型 T(x,)以及域演算 合法公式、域常量带入公式的规则和公式的解释规则等均与元组演算类似。下面举例说明。 例例 2-23 设=zSex(S(x1 x2 z x4 22)z=M，则x1，x2，x4在中为自由变量，x3为 约束变量。 例例 2-24 设=x2Sn，Sex y1(C#)(S(x1，x2，x3，x4，x5)x5y2)，这里x1，x3，x4， x5在中为自由出现

9、，其他变量均为约束出现，并且有T(x1，)=d(S#)，T(x3，)=d(Sex)， T(x5,)=d(Sa)，T(y2,)=d(G)。注意只有当d(Sa)=d(G)时，公式才是合理的。 2. 域演算举例 例例 2-25 查询所有女生的 S#、Sn，Sex、Sa 和 Sd。 x1S#x2Snx3Sexx4Sax5Sd | XS(x1，x2，x3，x4，x5) x3=F 例例 2-26 查询所有男生的 S#、Sa。 x1S#x2Sa | y1y2y3y4y5(XS(y1，y2，y3，y4，y5)x3=M y1=x1 y4=x2 例例 2-27 查询所有年龄小于 20 岁的男生的 S#、C#和 G

10、。 x1S#x2C#x3G |y1y2y3y4y5(XS(y1,y2,y3,y4,y5)x3=My420z1z2z3 (XSC(z1z2z3)z1=y1 z2=x2 z3=x3)y2=x1 2.4.3 关系运算的安全性 1. 安全性问题的提出 对于任何一个计算机系统来说，它都要受到两个“有限”的制约： ? 系统的存储容量是有限的，它不可能存储无限关系。这里所说的“无限关系”是指 元组个数为无限的关系。 ? 系统的计算速度是有限的， 在计算机上进行无限次运算是无法得到正确结果的， 因 为运算总是不会完结。 为了使关系运算能够在一个计算机系统中有效进行， 应当避免上述两种情况的发生， 需 要对关系

11、运算符加上必要的限制，采取一定措施。在数据库技术中，称不出现无限关系和无 限运算的关系运算过程是安全的， 相应的关系运算表达式就称为是安全表达式， 为了得到安 全表达式所采取的措施称为安全性限制或安全性约束。 2. 关系运算中安全性分析 关系代数基于集合理论，关系演算基于数理逻辑，两者之间有着密切关系，这就使得我 们可以有统一的观点来分析关系运算中的安全性问题。 在实际运算当中，人们实际上是自觉或不自觉地假定所涉及的初始对象是“有限”的， 但这并不能自动得到运算过程或者运算结果就一定“不涉及”到无限。例如在集合运算中， 即使初始集合是“有限”的，但如果对其进行“补”运算，有限集合的“补集”就有

12、可能是 无限集合。 在关系代数当中，任何一个关系代数表达式，只要是有限关系，由于其中只包含有限次 代数运算，而这些运算只能是并运算、差运算、广义笛卡尔乘积运算、选择运算和投影运算 5 种基本运算，不存在集合的“补运算”，所以关系代数运算总是安全的。 在关系演算当中， 尽管初始情形可以是有限的， 也有可能出现无限关系的问题和无限运 算的过程。例如在元组关系演算表达式中，就有下述两种情况： ? 对于表达式t| R(t)，其语义是所有不在关系 R 中的元组集合。如果关系中某一 属性的定义域是无限的，则t|R(t)就是一个具有无限元组的集合，此时该式表 示的关系就是一个无限关系的问题，要求出它的所有元

13、组是不可能的。 ? 另外，如果要判定表达式(t)(w(t)为假，必须对 t 的所有可能取值进行验证，当且 仅当其中没有一个值为真时， 才可判定该表达式为假， 如果 t 的取值范围是无穷的， 则验证过程就是无限的。 由此可见，在关系演算中，必须要有安全限制的相应措施，方可保证关系演算表达式是 安全的。 3. 关系演算中的安全性限制 对元组演算表达式进行安全性限制，通常的做法是对其中的公式 进行限制。对于 来说，定义一个有限的符号集 DOM()， 的符号集 DOM()由两类符号组成： ? 中的常量符号。 ? 中涉及的所有关系的所有元组的各个分量。 由于 DOM()是有限集合，如果将关系演算限制在

14、DOM()上就是安全的，不会出现任 何的无限问题。 一般认为， 一个表达式t | (t)要成为安全的， 其中的公式 就应该满足下面三个条件： ? 若 t 满足公式 ，即 t 使得 为真，则 t 的每个分量必须是 DOM()中的元素； ? 对 中每一个形为 (t)(w(t)的子公式，如 u 满足 W，即 u 使得 w 为真，则 u 的 每一个分量一定属于 DOM()； ? 对 中每一个形为(t)(w (t)的子公式，如 u 不满足 W，即 u 使得 w 为假，则 u 的每一个分量一定属于 DOM()；也就是说，若 u 的某个分量不属于 DOM()，则 w(u)为真。 对于域关系演算的安全性，也可

15、以做类似的讨论，这里从略。 2.4.4 关系代数、元组演算、域演算的等价性 关系代数和关系演算所依据的理论基础是相同的，因此可以进行相互间的转换。 在我们讨论元组关系演算时， 实际上就研究了关系代数中 5 种基本运算与元组关系演算 间的相互转换； 在讨论域关系演算时， 实际上也涉及了关系代数与域关系演算间的相互转换， 由此可以知道，关系代数、元组关系演算、域演算三类关系运算是可以相互转换的，它们对 于数据操作的表达能力是等价的。结合安全性的考虑，经过进一步的分析，人们已经证明了 如下重要结论： ? 每一个关系代数表达式都有一个等价的安全的元组演算表达式。 ? 每一个安全的元组演算表达式都有一个等价的安全的域演算表达式。 ? 每一个安全的域演算表达式都有一个等价的关系代数表达式。 按照上述三结论，即得到关系代数、元组关系演算和域演算的等价性。