元组关系演算
之前学习了一下关系代数表达式，现在再学习一下元组关系的演算，这样就全了。这篇东西的符号打出来费了好多时间，比较麻烦，还好看着还能看懂，关键是全文本的，好下面开始正文。
为了讨论方便，先允许关系的基数是无限的。然后再对这种情况下定义的演算作适当的修改，保证关系演算中的每一个公式表示的是有限关系。
在元组关系演算系统中，称 {t|Φ(t)}为元组演算表达式。其中t是元组变量，Φ(t) 为元组关系演算公式，简称公式。
它由原子公式和运算符组成。
原子公式有三类：
(1) R(t)
R是关系名，t是元组变量。R(t)表示t是R中的元组。于是，关系R可表示为：{t|R(t)}
(2) t[i]θu[j]
t和u是元组变量，θ是算术比较运算符。t[i] θ u[j] 表示断言“元组t的第i个分量与元组u的第j个分量满足比较关系θ”。例如，t[2]< u[3]表示元组t的第2个分量小于元组u的第3个分量。
(3) t[i]θc 或 cθt[i]
这里c是常量，该公式表示“t的第i个分量与常量C满足比较关系θ”。例如：t[4]=3表示元组t的第4个分量等于3。
在关系演算中定义了“自由元组变量”和“约束元组变量”的概念。这些概念和谓词演算中的概念完全一样。若公式中的一个元组变量前有“全称量词”或“存在量词”，则称该变量为约束元组变量，否则称自由元组变量。
公式可以递归定义如下：
(l) 每个原子公式是公式。
(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) 有限次地使用上述五条规则得到的公式是元组关系演算公式，其他公式不是元组关系演算公式。
一个元组演算表达式{t|Φ(t)}表示了使 Φ(t)为真的元组集合。
关系代数的运算均可以用关系演算表达式来表示(反之亦然)。下面用关系演算表达式来表示五种基本运算：
(1) 并
R∪S={t|R(t)∨S(t)}
(2) 差
R－S={t|R(t)∧﹁S(t)}
(3) 笛卡尔积
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)
(4) 投影
πt1,t2,...,tk(R)={t(k)|(∃u)(R(u)∧t[1]=u[i1]∧...t[k]=u[ik])}
(5) 选择
σF(R)={t|R(t)∧F}
注：F是公式。F用t[i]代替运算对象i得到的等价公式。
例1 查询信息系(IS系)全体学生：
SIS={Student(t)∧t[5]='IS'}
例2 查询年龄小于20岁的学生。
S20={Student(t)∧t[4]<20}
例3 查询学生的姓名和所在系。
S={t(2)|(∃u)(Student(u)∧t[1]=u[2]∧t[2]=u[5])}
上面定义的关系演算允许出现无限关系。例如{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)为真。
例4 设有关系 R如图2.8(a
)，S={t|﹁R(t)}，若不进行安全限制，则可能是一个无限关系。所以定义
dom(Φ)=
π
A
(R)∪
π
B
(R)
∪
π
C
(R)
={{a1,a2},{b1,b2},{c1,c2}}
则S是dom(Φ)中各域值中元素的笛卡儿积与R的差集。结果如图2.8(b)。注意，在做笛卡儿积时各个域中的元素不能搞混。
附：其他类型举例：
-----------------------------------------------------------------------------------------
1、下列等式中恒等的是：
①
π
A1,A2
(σF(E))≡σF(πA1,A2(E))
②
σ
F
(E1×E2)≡σF(E1)×σF(E2)
③
σ
F
(E1-E2)≡σF(E1)-σF(E2)
④
π
A1,A2,B1,B2
(E
E)≡πA1,A2(E)πB1,B2(E)
① 当F包含A1,A2以外的限制时，不恒等
② 当F包含大于E1(或E2)个数的限制时，不恒等
③ 恒等
④ 等式不可能成立，右边没有相同属性
2、以下元组的意义：
{t|(∃u)((R(u)∨S(u))∧(∀v)(T(v)→(∃w)((R(w)∨S(w))∧w[1]=u[1]∧w[2]=v[1]∧w[3]=v[2]))∧t[1]=u[1]}
据说是表示R∪S÷T的意思，但是我实在是看不懂。
3、以下元组表达式转换为关系代数表达式
{t|∃u∃v(R(u)∧S(v)∧u[3]=v[1]∧u[4]=v[2]∧u[1]>v[3]∧t[1]=u[2])}
其中R(A,B,C,D) S(C,D,E)
关系代数表达式为：πB(σA>E(RS))
4、把下列关系代数表达式转换为元组表达式
π
1,4(RS)
其中R(A,B,C) S(B,D)
元组演算表达式为：{t|∃u∃v(R(u)∧S(v)∧u[2]=v[1]∧t[1]=u[1]∧t[2]=v[2])}
5、关系代数表达式 → 元组演算表达式
π
1,5,6(σ1>5(R×S)) --注意中间是乘法不是自然连接
其中R(A,B,C) S(A,B,C)
{t|∃u∃v(R(u)∧S(v)∧u[1]>v[2]∧t[1]=u[1]∧t[2]=v[2]∧t[3]=v[3])}
6、下列查询效率最高的一组是：
① E1=