数据库关系演算实例

数据库关系演算实例第1页，共31页，2023年，2月20日，星期六2.5关系演算关系演算以数理逻辑中的谓词演算为基础按谓词变元不同进行分类1.元组关系演算：以元组变量作为谓词变元的基本对象元组关系演算语言ALPHA2.域关系演算：以域变量作为谓词变元的基本对象域关系演算语言QBE2第2页，共31页，2023年，2月20日，星期六2.5.1公式由E.F.Codd提出INGRES所用的QUEL语言是参照ALPHA语言研制的在元组演算系统中称{t|φ(t)}为元组演算表达式，其中t为元组变量，且为自由变元，φ(t)为元组关系演算公式，简称公式，它由原子公式和运算符组成3第3页，共31页，2023年，2月20日，星期六1、原子公式

原子公式有三类：

①R(t):

R为关系名，t为元组变量，R（t）表示t是R中的元组这样一个命题函数。

②t[i]θu[j]：t和u是两个元组，i和j表示元组分量的序号，θ是算术比较符，所表示的命题函数是元组t第i个分量与元组u第j个分量满足θ关系。

③t[i]θC或Cθt[i]：表示的命题函数是元组第i个分量与常数C满足θ关系。4第4页，共31页，2023年，2月20日，星期六2、逆归定义元组运算公式

①每一个原子公式是一个公式

②设φ1，φ2是公式则φ1∧φ2，φ1∨φ2，┑φ1也是公式

③

设t的域值为T={t1,t2,…tn}

则：

④有限次使用①②③生成的公式5第5页，共31页，2023年，2月20日，星期六3、元组运算公式中运算符优先次序①算术比较符②量词次之，且量词高于量词

③逻辑运算符④括号最优先

6第6页，共31页，2023年，2月20日，星期六元组运算公式{t|φ(t)}表示了所有使φ为真的元组集合，它所表示的仍是一个关系，其中t为自由变元。典型的数据库为ALPHA(P60—P65)7第7页，共31页，2023年，2月20日，星期六2.5.2关系代数用元组运算替代1、并

R∪S={t|R(t)∨S(t)}2、差

R-S={t|R(t)∧┑S(t)}

3、笛卡尔积

R×S={tm+n|(um)∧(vn)∧R(u)∧S(v)∧

t[1]=u[1]∧t[2]=u[2]∧...t[m]=u[m]∧

t[m+1]=v[1]∧....t[m+n]=v[n]}8第8页，共31页，2023年，2月20日，星期六2.5.2关系代数用元组运算替代4、投影

Πx(R)={tk|(u(R(u)∧t[1]=u[i1]∧…t[k]=u[ik]))}5、选取

бp(R)={t|R(t)∧P}9第9页，共31页，2023年，2月20日，星期六2.5.3元组演算运算实例

①查找l1从书店s1购买的图书号及其册数

{t2|u(LBS(u)∧u[1]='l1'∧u[3]='s1'∧

t[1]=u[2]∧t[2]=u[4])}10第10页，共31页，2023年，2月20日，星期六

2.5.3元组演算运算实例②取出馆址在上海shanghai的馆名和电话号码

{t2|u(L(u)∧u[3]='shanghai'∧t[1]=u[2]∧t[2]=u[4])}11第11页，共31页，2023年，2月20日，星期六2.5.3元组演算运算实例

③取出S3发行的图书书名和数量

{t2|(u)(v)(LBS(u)∧B(v)∧u[3]='S3'∧

u[2]=v[1]∧t[1]=v[2]∧t[2]=u[4])}12第12页，共31页，2023年，2月20日，星期六2.5.3元组演算运算实例④查找选购了所有图书的馆名

{t1|(v)(u)(w)(L(v)∧B(u)∧LBS(w)∧

w[1]=v[1]∧w[2]=u[1]∧t[1]=v[2])}13第13页，共31页，2023年，2月20日，星期六2.5.3元组演算运算实例⑤查找同时收藏有b1和b2这两本书的图书馆名

{t1|(u)(v)(w)(LBS(u)∧LBS(v)∧L(w)

∧u[2]='b1'∧v[2]='b2'∧u[1]=v[1]∧

u[1]=w[1]∧t[1]=w[2])}14第14页，共31页，2023年，2月20日，星期六2.5.3元组演算运算实例

⑥查找没有收藏computer这本书的图书馆名

{t1|(u)(v)(w)(L(u)∧LBS(v)∧B(w)∧

w[2]='computer'∧v[2]≠w[1]∧u[1]=v[1]

∧t[1]=u[1])}

或者

{t1|┑((u)(v)(w)(L(u)∧LBS(v)∧B(w)∧

w[2]='computer'∧v[2]=w[1]∧u[1]=v[1]

∧t[1]=u[1])）}

注意：第二种方法存在安全问题15第15页，共31页，2023年，2月20日，星期六第二章关系数据库2.1关系模型概述2.2关系数据结构2.3关系的完整性2.4关系代数2.5元组演算2.6域演算2.7小结16第16页，共31页，2023年，2月20日，星期六2.6域演算

类似于元组运算，只不过公式中的变量用元组各分量对应的域变量来描述，域演算的谓词变元是域变量，域演算表达式的一般形式为：

{t1,t2,...tk|φ(t1,t2,...tk)}

其中t1,t2,...tk分别是域变量，φ是域演算公式17第17页，共31页，2023年，2月20日，星期六2.6.1公式递归定义域运算公式：

1、原子公式

①R(t1,t2…tn)，R为n元关系，ti是域变量或常量，表示的谓词含义：以t1,t2…tn为分量的元组在关系R中

②tiθuj：ti为元组t第i个分量，uj为元组u第j个分量，θ为算术比较符，表示的谓词含义为t的第i个分量与u的第j个分量满足θ关系。

③tiθc：c为常量，表示的谓司含义是t的第i个分量与常数C满足θ关系。2、递归定义

①原子公式是域运算公式

②若φ1，φ2是公式，则φ1∨φ2，φ1∧φ2，┑φ1也是公式

③

④有限次使用①②③也是公式18第18页，共31页，2023年，2月20日，星期六2.6.1公式运算符优先次序同元组运算公式

域演算表达式{t1,t2…tn|φ(t1,t2…tn)}表示所有使得φ为真的那些t1,t2…tn组成的元组集合。

典型的数据库为QBE数据库

19第19页，共31页，2023年，2月20日，星期六2.6.2域演算运算实例①查找l1从书店s1购买的图书号及其册数20第20页，共31页，2023年，2月20日，星期六2.6.2域演算运算实例②取出馆址在上海shanghai的馆名和电话号码

{t1t2|ョu1(L(u1t1'shanghai't2))}21第21页，共31页，2023年，2月20日，星期六2.6.2域演算运算实例③取出S3发行的图书书名和数量

{t1t2|ョu1ョu2ョv3

(LBS(u1u2's3't2)∧B(u2t1v3))}22第22页，共31页，2023年，2月20日，星期六2.6.2域演算运算实例④查找同时收藏有b1和b2这两本书的图书馆名

{t1|(ョu1ョu3ョu4)(ョv3ョv4)(ョw3ョw4)

(LBS(u1'b1'u3u4)∧LBS(u1'b2'v3v4)∧L(u1t1w3w4)}23第23页，共31页，2023年，2月20日，星期六构造安全约束与安全表达式查询的几个要素元组演算的安全问题，域演算同元组演算

在关系运算表达式中形如{t|┑R(t)}、

{t|R(t)∨{t}∧t[2]＞3}等皆为无限关系,计算机无法实现的,

形如

若判断为真，必须对所有的X进行验证,若X为无穷集合,则导致无穷验证，必须进行一种限制即安全约束。24第24页，共31页，2023年，2月20日，星期六1基本概念安全运算不产生无穷关系或无穷验证的运算。安全表达式安全运算的运算表达式叫安全表达式。在关系代数中由于不存在运算，关系代数是一个安全的运算表达式。25第25页，共31页，2023年，2月20日，星期六安全表达式满足的条件

表达式{t|φ(t)}为安全表达式满足如下的条件：定义一个与ф有关的有限集合DOM(ф)，其元素是在ф中所有出现的符号。若元组t使ф(t)为真则t的每个分量ti∈DOM(ф)若R中每一个形如ョuф(u)的子表达式，若u满足ф，则u的每个分量∈DOM(ф)若R中每一个形如uф(u)的子表达式，若u满足ф，则u中必有某个分量不属于DOM(ф)，因为

uф(u)<==>┑ョu┑ф(u)经过安全约束的表达式称为安全表达式。26第26页，共31页，2023年，2月20日，星期六实例

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第27页，共31页，2023年，2月20日，星期六实例28第28页，共31页，2023年，2月20日，星期六定理1

如果E是一个由五种基本关系代数运算经过有限次组合而成的关系代数表达式，则在元组运算中存在一个与E等价的安全的元组运算表达式。实例

设R和S为二目关系则

П1,4(б2=3(R×S))={t|ョuョv(R(u)∧S(v)∧

u[2]=3∧t[1]=u[1]∧t[2]=v[2])}

29第29页，共31页，2023年，2月20日，星期六定理2

对于每一个元组运算安全表达式，一定存在一个与之等价的安全域运算表达式。

若u的目数为m，则引入m个域变量u1u2…um，并在u的受限