资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
2.4 关系运算(二)关系演算 关系代数是将整个关系看作变元, 并以其作为基本运算单位, 同时以集合方法为关系运 算的理论基础。 如果将组成关系的基本成分例如元组或者属性域看作变量, 以其作为基本运 算单位, 同时以数理逻辑中谓词演算为相应关系演算的理论基础, 就得到了另外一种形式的 关系数据语言关系演算。 关系演算基于谓词演算。在谓词演算中,如果谓词中的变元是关系中的元组,则得到所 谓元组关系演算;如果谓词中的变元是关系中的属性域,则得到所谓域关系演算。这样,关 系演算就分为元组关系演算和域关系演算两类。 在 2.4 节和 2.5 节,均以本章 2.3.4 节中的关系数据库S,C,SC为背景举例。这里 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,它有元组(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) 这个公式就建立了关系(元组集合)的谓词表示,称之为关系演算表达式。 (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有关系。 关系演算公式 利用原子公式可以递归定义关系演算公式: ? 原子公式是公式。 ? 如果1,2是公式,则12,12,12和1均是公式。 ? 如果 是公式,r 是 中自由变元,则r(),r()是公式。 ? 所有公式由且仅由上述三种方式经过有限次操作生成。 在公式中,各种运算的优先次序规定如下: ? 比较运算符:、=、。 ? 量词:、。 ? 否定词:。 ? 合取、析取、蕴含运算符:、。 关系演算表达式 有了公式 的概念,以公式 作为特性就构成一个有若干元组组成的集合,即关系 R, 这种形式的元组集合就称其为关系演算表达式。关系演算表达式的一般形式为: t | (t) 其中,(t)为公式,t 为 中出现的自由变元。关系演算表达式也简称为关系表达式或 者表达式。 2. 关系操作的元组演算表示 关系操作由 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 个分 量。 (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)是公式。 ? 所有公式由且仅由上述三种方式经过有限次操作生成。 例如(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在中为自由出现,其他变量均为约束出现,并且有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。 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. 安全性问题的提出 对于任何一个计算机系统来说,它都要受到两个“有限”的制约: ? 系统的存储容量是有限的,它不可能存储无限关系。这里所说的“无限关系”是指 元组个数为无限的关系。 ? 系统的计算速度是有限的, 在计算机上进行无限次运算是无法得到正确结果的, 因 为运算总是不会完结。 为了使关系运算能够在一个计算机系统中有效进行, 应当避免上述两种情况的发生, 需 要对关系运算符加上必要的限制,采取一定措施。在数据库技术中,称不出现无限关系和无 限运算的关系运算过程是安全的, 相应的关系运算表达式就称为是安全表达式, 为了得到安 全表达式所采取的措施称为安全性限制或安全性约束。 2. 关系运算中安全性分析 关系代数基于集合理论,关系演算基于数理逻辑,两者之间有着密切关系,这就使得我 们可以有统一的观点来分析关系运算中的安全性问题。 在实际运算当中,人们实际上是自觉或不自觉地假定所涉及的初始对象是“有限”的, 但这并不能自动得到运算过程或者运算结果就一定“不涉及”到无限。例如在集合运算中, 即使初始集合是“有限”的,但如果对其进行“补”运算,有限集合的“补集”就有可能是 无限集合。 在关系代数当中,任何一个关系代数表达式,只要是有限关系,由于其中只包含有限次 代数运算,而这些运算只能是并运算、差运算、广义笛卡尔乘积运算、选择运算和投影运算 5 种基本运算,不存在集合的“补运算”,所以关系代数运算总是安全的。 在关系演算当中, 尽管初始情形可以是有限的, 也有可能出现无限关系的问题和无限运 算的过程。例如在元组关系演算表达式中,就有下述两种情况: ? 对于表达式t| R(t),其语义是所有不在关系 R 中的元组集合。如果关系中某一 属性的定义域是无限的,则t|R(t)就是一个具有无限元组的集合,此时该式表 示的关系就是一个无限关系的问题,要求出它的所有元组是不可能的。 ? 另外,如果要判定表达式(t)(w(t)为假,必须对 t 的所有可能取值进行验证,当且 仅当其中没有一个值为真时, 才可判定该表达式为假, 如果 t 的取值范围是无穷的, 则验证过程就是无限的。 由此可见,在关系演算中,必须要有安全限制的相应措施,方可保证关系演算表达式是 安全的。 3. 关系演算中的安全性限制 对元组演算表达式进行安全性限制,通常的做法是对其中的公式 进行限制。对于 来说,定义一个有限的符号集 DOM(), 的符号集 DOM()由两类符号组成: ? 中的常量符号。 ? 中涉及的所有关系的所有元组的各个分量。 由于 DOM()是有限集合,如果将关系演算限制在 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)为真。 对于域关系演算的安全性,也可以做类似的讨论,这里从略。 2.4.4 关系代数、元组演算、域演算的等价性 关系代数和关系演算所依据的理论基础是相同的,因此可以进行相互间的转换。 在我们讨论元组关系演算时, 实际上就研究了关系代数中 5 种基本运算与元组关系演算 间的相互转换; 在讨论域关系演算时, 实际上也涉及了关系代数与域关系演算间的相互转换, 由此可以知道,关系代数、元组关系演算、域演算三类关系运算是可以相互转换的,它们对 于数据操作的表达能力是等价的。结合安全性的考虑,经过进一步的分析,人们已经证明了 如下重要结论: ? 每一个关系代数表达式都有一个等价的安全的元组演算表达式。 ? 每一个安全的元组演算表达式都有一个等价的安全的域演算表达式。 ? 每一个安全的域演算表达式都有一个等价的关系代数表达式。 按照上述三结论,即得到关系代数、元组关系演算和域演算的等价性。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号