数据库关系演算实例

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据库系统原理与设计,第,1 章 数据库系统概论,单击此处编辑母版标题样式,第二章 关系数据库,2.1 关系模型概述,2.2 关系数据结构,2.3 关系的完整性,2.4 关系代数,2.5 元组演算,2.6 域演算,2.7 小结,1,2.5 关系演算,关系演算,以数理,逻辑,中的谓词演算为基础,按谓词变元不同 进行分类,1.元组关系演算：,以,元组变量,作为谓词变元的基本对象,元组关系演算语言,ALPHA,2.域关系演算：,以,域变量,作为谓词变元的基本对象,域关系演算语言,QBE,2,2.5.1,公式,由提出,INGRES所用的QUEL语言是参照ALPHA语言研制的,在元组演算系统中称t|(t)为元组演算表达式，其中t为元组变量，且为自由变元，(t)为元组关系演算公式，简称公式，它由原子公式和运算符组成,3,1、原子公式,原子公式有三类：,R(t):R为关系名，t为元组变量，R（t）表示t是R中的元组这样一个命题函数。,tiuj：t和u是两个元组，i和j表示元组分量的序号，是算术比较符，所表示的命题函数是元组t第i个分量与元组u第j个分量满足关系。,tiC或Cti：表示的命题函数是元组第i个分量与常数C满足关系。,4,2、逆归定义元组运算公式,每一个原子公式是一个公式,设1，2是公式则12，12，,1 也是公式,设t的域值为T=t1,t2,tn 则：,有限次使用生成的公式,5,3、元组运算公式中运算符优先次序,算术比较符,量词次之，且 量词高于 量词,逻辑运算符,括号最优先,6,元组运算公式t|(t)表示了所有使为真的元组集合，它所表示的仍是一个关系，其中t为自由变元。,典型的数据库为ALPHA(P60P65),7,2.5.2 关系代数用元组运算替代,1、并,RS=t|R(t)S(t),2、差,R-S=t|R(t)S(t),3、笛卡尔积,RS=t,m+n,|(,u,m,)(,v,n,)R(u)S(v),t1=u1t2=u2.tm=um,tm+1=v1.tm+n=vn,8,2.5.2 关系代数用元组运算替代,4、投影,x,(R)=t,k,|(,u(R(u)t1=ui,1,tk=ui,k,),5、选取,p(R)=t|R(t)P,9,2.5.3 元组演算运算实例,查找l1从书店s1购买的图书号及其册数,t,2,|,u(LBS(u)u1=l1u3=s1,t1=u2t2=u4),10,2.5.3 元组演算运算实例,取出馆址在上海shanghai的馆名和电话号码,t,2,|,u(L(u)u3=shanghait1=u2t2=u4),11,2.5.3 元组演算运算实例,取出S3发行的图书书名和数量,t,2,|(,u)(,v)(LBS(u)B(v)u3=S3,u2=v1t1=v2t2=u4),12,2.5.3 元组演算运算实例,查找选购了所有图书的馆名,t,1,|(,v)(u)(,w)(L(v)B(u)LBS(w),w1=v1w2=u1t1=v2),13,2.5.3 元组演算运算实例,查找同时收藏有b1和b2这两本书的图书馆名,t,1,|(,u)(,v)(,w)(LBS(u)LBS(v)L(w),u2=b1v2=b2u1=v1,u1=w1t1=w2),14,2.5.3 元组演算运算实例,查找没有收藏computer这本书的图书馆名,t,1,|(,u)(v)(,w)(L(u)LBS(v)B(w),w2=computerv2w1u1=v1,t1=u1),或者,t,1,|(,u)(,v)(,w)(L(u)LBS(v)B(w),w2=computerv2=w1u1=v1,t1=u1)）,注意：第二种方法存在安全问题,15,第二章 关系数据库,2.1 关系模型概述,2.2 关系数据结构,2.3 关系的完整性,2.4 关系代数,2.5 元组演算,2.6 域演算,2.7 小结,16,2.6 域演算,类似于元组运算，只不过公式中的变量用元组各分量,对应的域变量来描述，域演算的谓词变元是域变量，域演,算表达式的一般形式为：,t1,t2,.tk|(t1,t2,.tk),其中t1,t2,.tk分别是域变量，是域演算公式,17,2.6.1 公式,递归定义域运算公式：,1、原子公式,R(t,1,t,2,t,n,)，R为n元关系，t,i,是域变量或常量，表示的谓词含义：以t,1,t,2,t,n,为分量的元组在关系R中,t,i,u,j,：t,i,为元组t第i个分量，u,j,为元组u第j个分量，为算术比较符，表示的谓词含义为t的第i个分量与u的第j个分量满足关系。,t,i,c：c为常量，表示的谓司含义是t的第i个分量与常数C满足关系。,2、递归定义,原子公式是域运算公式,若1，2是公式，则12，12，1也是公式,有限次使用也是公式,18,2.6.1 公式,运算符优先次序同元组运算公式,域演算表达式t,1,t,2,t,n,|(t,1,t,2,t,n,)表示所有使得为真的那些t,1,t,2,t,n,组成的元组集合。,典型的数据库为QBE数据库,19,2.6.2 域演算运算实例,查找l1从书店s1购买的图书号及其册数,20,2.6.2 域演算运算实例,取出馆址在上海shanghai的馆名和电话号码,t,1,t,2,|u,1,(L(u,1,t,1,shanghait,2,),21,2.6.2 域演算运算实例,取出S3发行的图书书名和数量,t,1,t,2,|u,1,u,2,v,3,(LBS(u,1,u,2,s3t,2,)B(u,2,t,1,v,3,),22,2.6.2 域演算运算实例,查找同时收藏有b1和b2这两本书的图书馆名,t,1,|(u,1,u,3,u,4,)(v,3,v,4,)(w,3,w,4,),(LBS(u,1,b1u,3,u,4,),LBS(u,1,b2v,3,v,4,)L(u,1,t,1,w,3,w,4,),23,构造安全约束与安全表达式查询的几个要素,元组演算的安全问题，域演算同元组演算,在关系运算表达式中形如 t|R(t)、,t|R(t)tt23等皆为无限关系,计算机无法实现的,形如,若判断为真，必须对所有的X进行验证,若X为无穷集合,则导致无穷验证，必须进行一种限制即安全约束。,24,1 基本概念,安全运算,不产生无穷关系或无穷验证的运算。,安全表达式,安全运算的运算表达式叫安全表达式。,在关系代数中由于不存在 运算，关系代数是一个安全的运算表达式。,25,安全表达式满足的条件,表达式t|(t)为安全表达式满足如下的条件：,定义一个与有关的有限集合DOM()，其元素是在中所有出现的符号。,若元组t使(t)为真则t的每个分量tiDOM(),若R中每一个形如u(u)的子表达式，若u满足，则u的每个分量 DOM(),若R中每一个形如 u(u)的子表达式，若u满足，则u中必有某个分量不属于DOM()，因为,u(u)u(u),经过安全约束的表达式称为安全表达式。,26,实例,R=(a1,b1,c1),(a2,b2,c2),DOM（R）=A(R)B(R)C(R),=a1,a2,b1,b2,c1,c2,S=t|R(t),即：S是Dom(R)中各域值元素的笛卡尔积与R的差积。,27,实例,28,定理1,如果E是一个由五种基本关系代数运算经过有限次组合而成的关系代数表达式，则在元组运算中存在一个与E等价的安全的元组运算表达式。,实例,设R和S为二目关系则,1,4,(,2=3,(RS)=t|uv(R(u)S(v),u2=3t1=u1t2=v2),29,定理2,对于每一个元组运算安全表达式，一定存在一个与之等价的安全域运算表达式。,若u的目数为m，则引入m个域变量u,1,u,2,u,m,，并在u的受限范围内用u,i,代替ut，用R(u,1,u,2,u,m,)代替R(u)，用u,1,u,2,u,m,代替U，,用 代替 ，显然它等价于原元组运算表达式。,30,定理3,对于每一个域运算表达式，总存在一个与之等价的关系代数表达式。,从上面的定理可知，这三种运算在安全定义范围内是可以互相转换的。,31,