欢迎来到.net学习网

欢迎联系站长一起更新本网站!QQ:879621940

您当前所在位置:首页 » 关系数据库基础教程 » 正文

数据库学习教程-关系演算

创建时间:2012年05月31日 11:02  阅读次数:(7599)
分享到:
把数理逻辑的谓词演算引入到关系运算中,就可得到以关系演算为基础的运算。关系演算又可分为元组关系演算和域关系演算,前者以元组为变量,后者以属性(域)为变量。

元组关系演算


在元组关系演算(Tuple Relational Calculus)中,元组关系演算表达式简称为元组表达式,其一般形式为  { t | P(t)},其中,t是元组变量,表示一个元数固定的元组;P是公式,在数理逻辑中也称为谓词,也就是计算机语言中的条件表达式。{ t | P(t)}表示满足公式P的所有元组t的集合。 

在元组表达式中,公式由原子公式组成。
原子公式(Atoms)有下列三种形式
  ① R(s) 
  ② s[i]θu[j] 
  ③ s[i]θa或aθu[j]。 
在定义关系演算操作时,要用到“自由”(Free)和“约束”(Bound)变量概念。在一个公式中,如果元组变量未用存在量词?或全称量词?符号定义,那么称为自由元组变量,否则称为约束元组变量。 

公式(Formulas)的递归定义如下:
 ① 每个原子是一个公式。其中的元组变量是自由变量。
 ② 如果P1和P2是公式,那么┐P1、P1∨P2、P1∧P2和P1?P2也都是公式。 
 ③ 如果P1是公式,那么(?s)(P1)和(?s)(P1)也都是公式。 
 ④ 公式中各种运算符的优先级从高到低依次为:θ,?和?,┐,∧和∨,?。在公式外还可以加括号,以改变上述优先顺序。 
 ⑤ 公式只能由上述四种形式构成,除此之外构成的都不是公式。 

在元组关系演算的公式中,有下列三个等价的转换规则:
 ①  P1∧P2等价于┐(┐P1∨┐P2);
  P1∨P2等价于┐(┐P1∧┐P2)。
 ②(?s)(P1(s))等价于┐(?s)(┐P1(s));
(?s)(P1(s))等价于┐(?s)(┐P1(s))。
 ③1?P2等价于 ┐P1∨P2。

注:该部分有些字符html显示不了,请下载原ppt文档,下载地址:
数据库学习教程(二)-关系模型和关系运算理论

关系代数表达式到元组表达式的转换
例2.17 
 R∪S可用{ t | R(t)∨S(t)}表示;
 R-S可用{ t | R(t)∧┐S(t)} 表示; 
 R×S可用{ t |(?u)(?v)(R(u)∧S(V) ∧t[1]=u[1] ∧t[2]=u[2]∧t[3]=u[3]∧t[4]=v[1] ∧t[5]=v[2] ∧t[6]=v[3])} 表示。
设投影操作是π2,3(R),那么元组表达式可写成:
{ t |(?u)(R(u)∧t[l]=u[2]∧t[2]=u[3])}
   σF(R)可用{ t |R(t)∧F'}表示,F'是F的等价表示形式。譬如σ2='d'(R)可写成{ t |(R(t)∧t[2]='d')。  

域关系演算


原子公式有两种形式:
 ⑴ R(x1…xk);
 ⑵ xθy。                                                            
公式中也可使用∧、∨、┐和?等逻辑运算符,(?x)和(?x),但变量x是域变量,不是元组变量。
自由域变量、约束域变量等概念和元组演算中一样。
域演算表达式是形为{t1…tk∣P(t1,…,tk)}的表达式,其中P(t1,…,tk)是关于自由域变量t1,…,tk 的公式。

元组表达式到域表达式的转换
我们可以很容易地把元组表达式转换成域表达式,转换规则如下:
⑴ 对于k元的元组变量t,可引入k个域变量t1…tk,在公式中t用t1…tk替换,元组分量t[i]用ti替换。
⑵ 对于每个量词(?u)或(?u),若u是m元的元组变量,则引入m个新的域变量u1…um。在量词的辖域内,u用u1…um替换,u[i]用ui替换,(?u)用(?u1)…(?um)替换,(?u)用(?u1)…(?um)替换。

关系运算的安全约束和等价性


在数据库技术中,不产生无限关系和无穷验证的运算称为安全运算,相应的表达式称为安全表达式,所采取的措施称为安全约束。

并、差、笛尔卡积、投影和选择是关系代数最基本的操作,并构成了关系代数运算的最小完备集。已经证明,在这个基础上,关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全等价的。 

关系代数表达式的优化
在关系代数表达式中需要指出若干关系的操作步骤。那么,系统应该以什么样的操作顺序,才能做到既省时间,又省空间,而且效率也比较高呢?这个问题称为查询优化问题。
在关系代数运算中,笛卡儿积和联接运算是最费时间的。

例2.23 设关系R和S都是二元关系,属性名分别为A,B和C,D。设有一个查询可用关系代数表达式表示:
E1=πA(σB=C∧D='99'(R×S))

也可以把选择条件D=‘99’移到笛卡儿积中的关系S前面:
E2=πA(σB=C(R×σD='99'(S))

还可以把选择条件B=C与笛卡儿积结合成等值联接形式:
E3=πA(R ? σD=‘99’(S))
B=C

这三个关系代数表达式是等价的,但执行的效率大不一样。显然,求El,E2,E3的大部分时间是花在联接操作上的。

关系代数表达式的优化算法
在关系代数表达式中,最花费时间和空间的运算是笛卡尔积和联接操作,为此,引出三条启发式规则,用于对表达式进行转换,以减少中间关系的大小。
·尽可能早地执行选择操作;
·尽可能早地执行投影操作;
·避免直接做笛卡尔积,把笛卡尔积操作之前和之后的一连串选择和投影合并起来一起做。u覻 TNt^劅0<
来源:.net学习网
说明:所有来源为 .net学习网的文章均为原创,如有转载,请在转载处标注本页地址,谢谢!
【编辑:Wyf】

打赏

取消

感谢您的支持,我会做的更好!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

最新评论

共有评论0条
  • 暂无任何评论,请留下您对本文章的看法,共同参入讨论!
发表评论:
留言人:
内  容:
请输入问题 19+95=? 的结果(结果是:114)
结  果: