元组关系演算(补充2)元组关系演算(补充2).ppt

An Introduction to Database Systenm 2.4 关系演算 关系演算 以数理逻辑中的谓词演算为基础 元组关系演算语言ALPHA 元组关系演算语言ALPHA 2.4 关 系 演 算 域关系演算 域演算的原子公式有以下两种形式： R(x1…xk)，R是k元关系，每个xi是常量或域变量。　　xθy，其中x，y是常量或域变量，但至少有一个是域变量，θ是算术比较运算符。 * 2.5 关 系 演 算 2.5.1 元组关系演算 2.5.2 域关系演算 EXISTS 存在谓词 IN 包含谓词 ＞、≥、＜、≤、＝、≠ 比较谓词 常见的谓词如下表所示 种类：按谓词变元不同分类 1.元组关系演算： 以元组变量作为谓词变元的基本对象 元组关系演算语言ALPHA 2.域关系演算： 以域变量作为谓词变元的基本对象 域关系演算语言QBE 元组关系演算 (1) 在元组关系演算（Tuple Relational Calculus）中，元组关系演算表达式简称为元组表达式，其一般形式为 { t | P（t）} （元组成为谓词变元） 其中，t是元组变量，表示一个元数固定的元组； P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。 { t | P（t）}表示满足公式P的所有元组t的集合。 元组关系演算 (2) 在元组表达式中，公式由原子公式组成。 定义2.4 原子公式（Atoms）有下列三种形式： ① R（s） ② s[i]θu[j] ③ s[i]θa或aθu[j]。 （R是关系，s和u是元组，a是常量） 在一个公式中，如果元组变量未用存在量词?或全称量词?符号定义，那么称为自由元组变量（Free） ，否则称为约束元组变量（Bound） 。 元组关系演算 (3) 定义2.5 公式（Formulas）的递归定义如下： ① 每个原子是一个公式。其中的元组变量是自由变量。 ② 如果P1和P2是公式，那么┐P1、P1∨P2、P1∧P2和 P1?P2也都是公式。 ③ 如果P1是公式，那么(?s)(P1)和(?s)(P1)也都是公式。 ④ 公式中各种运算符的优先级从高到低依次为： θ，?和?，┐，∧和∨，?。在公式外还可以加括号，以改变上述优先顺序。 ⑤ 公式只能由上述四种形式构成，除此之外构成的都不是公式。 元组关系演算 (4) 例2.16 图2.20的（a）、（b）是关系R和S，（c）～（g）分别是下面五个元组表达式的值 图2.20 元组关系演算的例子 R1 = { t | S（t）∧t[1]2 } R2 = { t | R（t）∧┐S（t）} R3 = { t |（?u）（S（t）∧R（u）∧t[3]u[2]}} R4 = { t |（?u）（R（t）∧ S（u）∧t[3]u[1]）} R5 = { t |（?u）（?v）（R（u）∧ S（v）∧u[1]v[2]∧t[1]=u[2]∧t[2]=v[3]∧t[3]=u[1]）} 元组关系演算 (5) 在元组关系演算的公式中，有下列三个等价的转换规则： ① P1∧P2等价于┐(┐P1∨┐P2)； P1∨P2等价于┐（┐P1∧┐P2）。 ② （?s）（P1（s））等价于┐(?s)（┐P1（s））； （?s）（P1（s））等价于┐(?s）（┐P1（s））。 ③ P1?P2等价于 ┐P1∨P2。 元组关系演算 (6) 关系代数表达式到元组表达式的转换 例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’）。 元组关系演算的例子 例2.16 图2.20的（a）、（b）是关系R和S，（c）～（g）分别是下面五个元组表达式的值 图2.20 元组关系演算的例子 R1 = { t | S（t）∧t[1]2 } R2 = { t | R（t）∧┐S（t）} R3 = { t |（?u）（S（t）∧R（u）∧t[3]u[2]}} R4 = { t |（?u）（R（t）∧