元组关系演算
之前学习了一下关系代数表达式,现在再学习一下元组关系的演算,这样就全了。这篇东西的符号打出来费了好多时间,比较麻烦,还好看着还能看懂,关键是全文本的,好下面开始正文。
为了讨论方便,先允许关系的基数是无限的。然后再对这种情况下定义的演算作适当的修改,保证关系演算中的每一个公式表示的是有限关系。
在元组关系演算系统中,称 {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
(EE)≡π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=