加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

元组关系演算

(2012-02-13 11:55:51)
标签:

杂谈

分类: 计算机
 在元组关系演算中,元组关系演算表达式(简称为元组表达式)用表达式{t│Q(t)}来表示,其中t是元组变量,它表示一个定长的元组,Q(t)是公式,公式是由原子公式组成的。

原子公式有下列三种形式:
 (1)R(s),其中R是关系名,s是元组变量。它表示这样的一个命题:“s是关系R的一个元组”。
 (2)s[i]θu[j],其中s和u都是元组变量,θ是算术比较运算符。该原子公式表示这样的命题:“元组s的第i个分量与元组u的第j个分量之间满足θ关系”。例如,s[1]<u[2]表示元组s的第一个分量必须小于元组u的第二个分量。
(3)s[i]θa 或 aθs[i],这里a是一个常量。前一个原子公式表示这样的命题:“元组s的第i个分量与常量a之间满足θ关系”。
在一个公式中,如果一个元组变量的前面没有存在量词 ∃ 或全称量词 ∀ 等符号,那么称之为自由元组变量,否则称之为约束元组变量。元组表达式的一般形式{t│Q(t)}中,t是Q中唯一的自由元组变量。

公式可以递归定义如下:
(1)每个原子公式是公式。
(2)如果 Φ 1 和 Φ 2 是公式,则 Φ 1 ∧ Φ 2 、 Φ 1 ∨ Φ 2 、 ﹁ Φ1 也是公式。分别表示:
     ① 如果 Φ 1 和 Φ 2 同时为真。则 Φ 1 ∧ Φ 2 才为真,否则为假;
     ② 如果 Φ 1 和 Φ 2 中一个或同时为真,则 Φ 1 ∨ Φ 2 为真,仅 Φ 1 和 Φ 2 同时为假时, Φ 1 ∨ Φ 2 才为假; 
     ③ 如果 Φ 1 真,则 ﹁ Φ 1 为假。
(3)若 Φ 是公式,则 ∃ t(Φ) 也是公式。其中符号 ∃ 是存在量词符号, ∃ t(Φ) 表示: 
  若有一个 t 使 Φ 为真,则 ∃ t(Φ) 为真,否则 ∃ t(Φ) 为假。
(4)若 Φ 是公式,则 ∀ t( Φ ) 也是公式。其中符号 ∀ 是全称量词符号, ∀ t( Φ ) 表示:如果对所有 t ,都使 Φ 为真,则 ∀ t( Φ ) 必为真,否则 ∀ t( Φ ) 为假。 
(5)在元组演算公式中,各种运算符的优先次序为:
     ① 算术比较运算符最高;
     ② 量词次之,且 ∃ 的优先级高于 ∀ 的优先级;
     ③ 逻辑运算符最低,且 ﹁ 的优先级高于 ∧ 的优先级, ∧ 的优先级高于 ∨ 的优先级;
     ④ 加括号时,括号中运算符优先,同一括号内的运算符之优先级遵循 ①②③ 各项。
(6)有限次地使用上述五条规则得到的公式是元组关系演算公式,其他公式不是元组关系演算公式。

关系代数的6种基本运算均可用元组表达式来表示(反之亦然)。其表示如下:
(1)并
R ∪ S={t|R(t) ∨ S(t)}
(2)交 
R ∩ S={t|R(t) ∧  S(t)}
(3)差 
R - S={t|R(t) ∧ ﹁ S(t)}
(4)笛卡尔积 
R×S={t (n+m) |( ∃ u (n) )( ∃ v (m) )(R(u) ∧ S(v) ∧ t[1]=u[1] ∧ ... ∧ t[n]=u[n] ∧ t[n+1]=v[1] ∧ ... ∧ t[n+m]=v[m])} 注: t (n+m) 表示 t 有目数 (n+m)
(5)投影 
π t1,t2,...,tk (R)={t (k) |( ∃ u )(R(u) ∧ t[1]=u[t1] ∧ ...t[k]=u[tk] )}
(6)选择 
σ F (R)={t|R(t) ∧ F’} 注: F 是公式,F’是用 t[i] 代替 运 算 对 象 i 得到的等价公式。

上面定义的关系演算允许出现无限关系。例如 {t| ﹁ R(t)} 表示所有不属于 R 的元组 ( 元组的目数等于 R 的目数 ) 。要求出这些可能的元组是做不到的,所以必须排除这类无意义的表达式。把不产生无限关系的表达式称为安全表达式,所采取的措施称为安全限制。安全限制通常是定义一个有限的符号集 dom(Φ) , dom(Φ) 一定包括出现在 Φ 以及中间结果和最后结果的关系中的所有符号 ( 实际上是各列中值的汇集 ) 。 dom(Φ) 不必是最小集。

 当满足下列条件时,元组演算表达式 {t|Φ(t)} 是安全的:
(1)如果 t 使 Φ(t) 为真,则 t 的每个分量是 dom(Φ) 中的元素。
(2)对于 Φ 中每一个形如 ( ∃ t)(W(u)) 的子表达式,若 u 使 W(u) 为真,则 u 的每个分量是 dom(Φ) 中的元素。
(3)对于 Φ 中每一个形如 ( ∀ t)(W(u)) 的子表达式,若 u 使 W(u) 为假,则 u 的每个分量必属于 dom(Φ) 。换言之,若 u 某一分量不属于 dom(Φ) ,则 W(u) 为真。

等价的转换规则
(1)P1∧P2等价┓(┓P1∨┓P2)
(2)P1∨P2等价于┓(┓P1∧┓P2)
(3)(∀s)(P1(s))等价于┓(∃s)(┓P1(s))
(4)(∃s)(P1(s))等价于┓(∀s)(┓P1(s))
(5)P1→P2等价于┓P1∨P2。

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有