元组关系演算
(2012-02-13 11:55:51)
标签:
杂谈 |
分类: 计算机 |
原子公式有下列三种形式:
(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 也是公式。分别表示:
(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(Φ) 不必是最小集。
(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。
前一篇:Facebook 办公室内的标语
后一篇:如何定义成功?