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