关系演算(数据库)

时间：2022-12-24 14:30:01 | 来源：信息时代

时间：2022-12-24 14:30:01 来源：信息时代

    关系演算 : 用一阶谓词逻辑研究关系模型的一种数学理论,它分为域关系演算及元组关系演算。其中,域关系演算是由Pirotte首先提出的,而元组关系演算是由Codd首先提出的。
1.域关系演算
域关系演算由提问元组及公式两部分组成。提问元组是形如〈x,y,…,z〉的表达式,这里x,y,…,z是变量。若Ω={R₁,…,R_n}是一个关系数据库模式,则公式递归定义如下:
(1)若R_k＝{A₁,…,A_m}∈Ω,则形如R_k{x₁,…,x_m}的表达式称为原子公式,这里x₁,…,x_m是变量。
(2)形如w₁θw₂的式子称为原子不等式。这里w₁、w₂是变量或常数,但不同时为常数,θ∈{<,≤,=,≥,>,≠}。
(3)原子公式是公式,原子不等式是公式。
(4)ψ₁、ψ₂是公式, 则ψ₁∧ψ₂,ψ₁∨ψ₂,ψ₁及ψ₁加小括号(ψ₁)都是公式。
(5)ψ是公式,则(∀x)ψ是公式,x是全称变量,(∀x)表示“对所有x”。
(6)ψ是公式,则(∃x)ψ是公式,x是存在变量,(∃x)表示“存在着x”。
(7)只有以上形成的是公式。
若ω是Ω上的关系数据库,则域关系演算的运算结果是对于该数据库,能使公式成立的提问元组的所有可能取值。
如果不加什么限制,域关系演算的运算结果可能是由无穷多个元组组成,例如R={A,B},dom(A)=dom(B)=N(这里N是所有自然数的集合),R上的关系r如下:

A	B
1	2
3	4

则以下域关系演算: 提问元组:〈x,y〉公式:∃x₁∃y₁R〈x₁,y₁〉∧x≠x₁∧y≠y₁,运算的结果是集合:{〈x,y〉|x,y∈N,〈x,y〉≠〈1,2〉,〈x,y〉≠〈3,4〉},显然包括无穷多个元组。
为了避免出现运算结果有无穷多个元组的情况,需要定义一种安全的域关系演算。
设Ω是一个数据库模式,Ω={R₁,…,R_n},而ω={r₁,…,r_n}是Ω上的一个关系数据库,对于由提问元组〈x₁, …, x_k〉及公式组成的域关系演算,若S是中的所有符号的集合, 则令:

即dom(,ω)是出现在关系r₁, …,r_n中所有值与所有中的符号组成的集合。
如果该域关系演算满足以下条件则称它(对ω)是安全的: ①若为真, 则每个x_i必属于dom(,ω)。②若(∃u)(₁₎是中的一个子公式, 则使₁为真的u,其各分量必须都在dom(,ω)中。③若(∀u)(₁₎是中的一个子公式, 则使₁为假的u, 其各分量必须都在dom(,ω)中。 已证明安全的域关系演算运算的结果一定不会有无穷多个元组。
2.元组关系演算
元组关系演算也是由提问元组及公式两部分组成。提问元组是一个代表元组的变量,例如t。若Ω={R₁,…,R_n}是一个关系数据库模式,每个关系模式R_k(1≤k≤n)中的属性都有一个指定的次序,则公式递归定义如下:
(1)若R_k＝{A₁,…,A_m}∈Ω,t是一个代表元组的变量,则形如R_k〈t〉的表达式称为原子合式(1≤k≤m)。
(2)若t,s分别是代表R_p及R_q上元组的变量,则形如t[i]θs[j],或t[i]θa,或bθs[j]的表达式称为原子不等式,其中t[i]及s[j]分别表示按R_p中属性次序及R_q中属性次序,t在R_p的第i个属性及s在R_q的第j个属性上的取值,a、b是常数,而θ∈{<,≤,=,≥,>,≠}。
(3)原子合式是公式,原子不等式是公式。
(4)ψ₁、ψ₂是公式, 则ψ₁∧ψ₂,ψ₁∨ψ₂,ψ₁及ψ₁加小括号(ψ₁)都是公式。
(5)ψ是公式,则(∀x)ψ是公式,x是全称变量,(∀x)表示“对所有x”。
(6)ψ是公式, 则(∃x)ψ是公式,x是存在变量,(∃x)表示“存在着x”。
(7)只有以上形成的是公式。
若ω是Ω上的关系数据库(关系数据库请参看关系数据库条目),则元组关系演算的运算结果是能使公式成立的提问元组的所有可能值。
如果不加什么限制,元组关系演算的运算结果也可能是由无穷多个元组组成,例如R={A,B},dom(A)=dom(B)=N(这里N是所有自然数的集合),R上的关系r如表1所示。
则以下元组关系演算:提问元组:t公式:R〈t〉的运算的结果是集合{〈x,y〉|x,y∈N,〈x,y〉≠〈1,2〉,〈x,y〉≠〈3,4〉},显然包括无穷多个元组。
为了避免出现运算结果有无穷多个元组的情况,需要定义一种安全的元组关系演算。
若是一个元组关系演算中的公式, Ω是一个数据库模式,Ω={R₁,…,R_n},而ω={r₁,…,r_n}是Ω的一个关系数据库,而S是中的所有符号的集合,则令:

dom(,ω)={u[A_j]|u∈r_i,A_j∈R_i}∪S。

即dom(,ω)是由出现在关系r₁, …,r_n中所有值以及所有中的符号组成的集合。
我们说一个以t为提问元组, 以为公式的元组关系演算(对ω)是安全的是指: ①只要t满足, t的每个分量就是dom(,ω)的元素。 ②对中的每个形如(∃u)(`)的子公式, 若u适合`, 则u的每个分量都是dom(`,ω)的元素。③对中的每个形如(∀u)(`)的子公式,若u的某个分量不在dom(`,ω)中, 则u就满足`。 已证明安全的元组关系演算运算的结果一定不会有无穷多个元组。
Codd及Pirotte已证明域关系演算、安全的元组关系演算、关系代数是等价的。