关系运算关系演算

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元组关系演算如果在一阶谓词演算表达式中，变量是以元组为演算单位，就称其为元组关系演算(TupleRelationCalculus)，其中元组变量表示关系中的元组，变量取值范围是整个关系。1.关系的元组演算表示(1)关系与谓词的对应为了得到关系操作的元组关系演算表达式，需要考虑关系与谓词的联系。z由关系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中)。z由谓词P表示关系R由于关系代数中R是元组集合，一般而言，集合是可以用满足它的某种特殊性质来刻画与表示。如果谓词P表述了关系R中元组的本质特性，就可以将关系R写为：R={t|P(t)}这个公式就建立了关系(元组集合)的谓词表示，称之为关系演算表达式。(2)元组关系演算表达式元组关系演算表达式的严格数学描述是由“归纳定义”方式完成的。按照通常的思路，元组演算表达式是由“关系演算公式”组成；“关系演算公式”是由“原子公式”组成。①原子公式下述三类称为元组演算原子公式，简称原子公式：z谓词R(t)是原子公式。zu(i)θv(j)是原子公式。zu(i)θa是原子公式。其中，t=(r1,r2,…,rm)是P的成真指派；u(i)表示元组u的第i个分量，v(j)表示元组v的第j个分量；a是常量，u(i)θa表示u的第i个分量与常量a有关系θ。②关系演算公式利用原子公式可以递归定义关系演算公式：z原子公式是公式。z如果φ1，φ2是公式，则φ1∧φ2，φ1∨φ2，φ1→φ2和¬φ1均是公式。z如果φ是公式，r是φ中自由变元，则∃r(φ)，∀r(φ)是公式。z所有公式由且仅由上述三种方式经过有限次操作生成。在公式中，各种运算的优先次序规定如下：z比较运算符：、、≤、≥、=、≠。z量词：、∀。∃z否定词：¬。z合取、析取、蕴含运算符：∧、∨、→。③关系演算表达式有了公式φ的概念，以公式φ作为特性就构成一个有若干元组组成的集合，即关系R，这种形式的元组集合就称其为关系演算表达式。关系演算表达式的一般形式为：{t|φ(t)}其中，φ(t)为公式，t为φ中出现的自由变元。关系演算表达式也简称为关系表达式或者表达式。2.关系操作的元组演算表示关系操作由5种基本操作，它们在关系代数中分别对应5种基本运算，这5种基本运算可以用一阶谓词演算中的公式表示。设有关系R、S，其谓词表示为R(t)和S(t)，此时有zRS={t|R(t)S(t)}；∪∨zR–S=(t|R(t)¬S(t))；∧zσF(R)={t|R(t)F}，其中F是一个谓词公式；∧z(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|uv(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)∧t[5]='CS'}例2-21查询年龄大于20岁的学生姓名：S20={t|S(t)∧t[4]20}例2-22查询学生姓名和所在系：S1={t(2)|(∃u)(S(u)∧t[1]=u[2]∧t[1]=u[5])2.4.2域关系演算1.关系的域演算表示域关系演算(DomainRelationCalculus)简称为域演算，它是关系演算的另外一种形式。域关系和元组关系演算十分类似，这是因为它们都建立在谓词演算之上；两者又有区别，这是因为有两点不同：其一是谓词变元的不同，元组演算以元组为变元，域演算以元组的分量即属性域为变元，而在实际上，人们就将关系的属性名视为域变元；其二是元组变元的变化范围为整个关系，而域变元的变化范围是某个属性域。域演算表达式的一般形式为：{t1,t2,…,tk|P(t1,t2,…,tk)}其中，t1,t2,…,tk是域变量，P(t1,t2,…,tk)是域演算表达式。为了揭示域演算表达式的语义，我们同样需要进行递归定义。(1)原子公式下述三类称为域演算原子公式，简称原子公式：z如果R(t1,t2,…,tk)表示命题“以t1,t2,…,tk为分量的元组在关系R之中”，则R(t1,t2,…,tk)是原子公式，其中，R是k元关系，ti是t的第i个分量；ztiθC或者Cθti是原子公式，其中ti是元组变量的第i个分量，C是常量，θ是算数比较符；ztiθuj是原子公式，其中，ti表示元组变量t的第i个分量，uj表示元组变量u的第j个分量，它们之间满足运算θ。例如t1=u4表示t的第一个分量大于等于u的第四个分量。(2)域演算公式域演算公式(简称为公式)可以递归定义如下：z原子公式是公式。z如果φ1，φ2是公式，则φ1∧φ2，φ1∨φ2，φ1→φ2和¬φ1均是公式。z如果φ1是公式，∃ti(φl)，∀ti(φl)是公式。z所有公式由且仅由上述三种方式经过有限次操作生成。例如φ(x1,x2,x3,x4,x5)=S(x1,x2,x3,x4,x5)∧(x521)∨¬x4='M'是一个域演算公式。域演算公式φ中变量的自由出现与约束出现、公式中自由变量x的型T(x,φ)以及域演算合法公式、域常量带入公式的规则和公式的解释规则等均与元组演算类似。下面举例说明。例2-23设φ=z[Sex](S(x∃1x2zx422))∧¬z='M'，则x1，x2，x4在φ中为自由变量，x3为约束变量。例2-24设φ=x∃2[Sn，Sex]y∀1(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。{x1[S#]x2[Sn]x3[Sex]x4[Sa]x5[Sd]|XS(x1，x2，x3，x4，x5)∧x3='F'}例2-26查询所有男生的S#、Sa。{x1[S#]x2[Sa]|∃y1y2y3y4y5(XS(y1，y2，y3，y4，y5))∧x3='M'∧y1=x1y∧4=x2}例2-27查询所有年龄小于20岁的男生的S#、C#和G。{x1[S#]x2[C#]x3[G]|y∃1y2y3y4y5(XS(y1,y2,y3,y4,y5))∧x3='M'∧y420z∧∃1z2z3(XSC(z1z2z3)z∧1=y1z∧2=x2z∧3=x3)y2=x1}2.4.3关系运算的安全性1.安全性问题的提出对于任何一个计算机系统来说，它都要受到两个“有限”的制约：z系统的存储容量是有限的，它不可能存储无限关系。这里所说的“无限关系”是指元组个数为无限的关系。z系统的计算速度是有限的，在计算机上进行无限次运算是无法得到正确结果的，因为运算总是不会完结。为了使关系运算能够在一个计算机系统中有效进行，应当避免上述两种情况的发生，需要对关系运算符加上必要的限制，采取一定措施。在数据库技术中，称不出现无限关系和无限运算的关系运算过程是安全的，相应的关系运算表达式就称为是安全表达式，为了得到安全表达式所采取的措施称为安全性限制或安全性约束。2.关系运算中安全性分析关系代数基于集合理论，关系演算基于数理逻辑，两者之间有着密切关系，这就使得我们可以有统一的观点来分析关系运算中的安全性问题。在实际运算当中，人们实际上是自觉或不自觉地假定所涉及的初始对象是“有限”的，但这并不能自动得到运算过程或者运算结果就一定“不涉及”到无限。例如在集合运算中，即使初始集合是“有限”的，但如果对其进行“补”运算，有限集合的“补集”就有可能是无限集合。在关系代数当中，任何一个关系代数表达式，只要是有限关系，由于其中只包含有限次代数运算，而这些运算只能是并运算、差运算、广义笛卡尔乘积运算、选择运算和投影运算5种基本运算，不存在集合的“补运算”，所以关系代数运算总是安全的。在关系演算当中，尽管初始情形可以是有限的，也有可能出现无限关系的问题和无限运算的过程。例如在元组关系演算表达式中，就有下述两种情况：z对于表达式{t|R(t)}，其语义是所有不在关系R中的元组集合。如果关系中某一属性的定义域是无限的，则{t|¬¬R(t)}就是一个具有无限元组的集合，此时该式表示的关系就是一个无限关系的问题，要求出它的所有元组是不可能的。z另外，如果要判定表达式(∃t)(w(t))为假，必须对t的所有可能取值进行验证，当且仅当其中没有一个值为真时，才可判定该表达式为假，如果t的取值范围是无穷的，则验证过程就是无限的。由此可见，在关系演算中，必须要有安全限制的相应措施，方可保证关系演算表达式是安全的。3.关系演算中的安全性限制对元组演算表达式进行安全性限制，通常的做法是对其中的公式φ进行限制。对于φ来说，定义一个有限的符号集DOM(φ)，φ的符号集DOM(φ)由两类符号组成：zφ中的常量符号。zφ中涉及的所有关系的所有元组的各个分量。由于DOM(φ)是有限集合，如果将关系演算限制在DOM(φ)上就是安全的，不会出现任何的无限问题。一般认为，一个表达式{t|φ(t)}要成为安全的，其中的公式φ就应该满足下面三个条件：z若t满足公式φ，即t使得φ为真，则t的每个分量必须是DOM(φ)中的元素；z对φ中每一个形为(∃t)(w(t))的子公式，如u满足W，即u使得w为真，则u的每一个分量一定属于DOM(φ)；z对φ中每一个形为(t)(w(t))的子公式，如u不满足W，即u使得w为假，则u的每一个分量一定属于DOM(φ)；也就是说，若u的某个分量不属于DOM(φ)，则w(u)为真。∀对于域关系演算的安全性，也可以做类似的讨论，这里从略。2.4.4关系代数、元组演算、域演算的等价性关系代数和关系演算所依据的理论基础是相同的，因此可以进行相互间的转换。在我们讨论元组关系演算时，实际上就研究了关系代数中5种基本运算与元组关系演算间的相互转换；在讨论域关系演算时，实际上也涉及了关系代数与域关系演算间的相互转换，由此可以知道，关系代数、元组关系演算、域演算三类关系运算是可以相互转换的，它们对于数据操作的表达能力是等价的。结合安全性的考虑，经过进一步的分析，人们已经证明了如下重要结论：z每一个关系代数表达式都有一个等价的安全的元组演算表达式。z每一个安全的元组演算表达式都有一个等价的安全的域演算表达式。z每一个安全的域演算表达式都有一个等价的关系代数表达式。按照上述三结论，即得到关系代数、元组关系演算和域演算的等价性。