關系演算(數(shù)據(jù)庫)

時間：2022-12-24 14:30:01 | 來源：信息時代

時間：2022-12-24 14:30:01 來源：信息時代

    關系演算 : 用一階謂詞邏輯研究關系模型的一種數(shù)學理論,它分為域關系演算及元組關系演算。其中,域關系演算是由Pirotte首先提出的,而元組關系演算是由Codd首先提出的。
1.域關系演算
域關系演算由提問元組及公式兩部分組成。提問元組是形如〈x,y,…,z〉的表達式,這里x,y,…,z是變量。若Ω={R₁,…,R_n}是一個關系數(shù)據(jù)庫模式,則公式遞歸定義如下:
(1)若R_k＝{A₁,…,A_m}∈Ω,則形如R_k{x₁,…,x_m}的表達式稱為原子公式,這里x₁,…,x_m是變量。
(2)形如w₁θw₂的式子稱為原子不等式。這里w₁、w₂是變量或常數(shù),但不同時為常數(shù),θ∈{<,≤,=,≥,>,≠}。
(3)原子公式是公式,原子不等式是公式。
(4)ψ₁、ψ₂是公式, 則ψ₁∧ψ₂,ψ₁∨ψ₂,ψ₁及ψ₁加小括號(ψ₁)都是公式。
(5)ψ是公式,則(∀x)ψ是公式,x是全稱變量,(∀x)表示“對所有x”。
(6)ψ是公式,則(∃x)ψ是公式,x是存在變量,(∃x)表示“存在著x”。
(7)只有以上形成的是公式。
若ω是Ω上的關系數(shù)據(jù)庫,則域關系演算的運算結果是對于該數(shù)據(jù)庫,能使公式成立的提問元組的所有可能取值。
如果不加什么限制,域關系演算的運算結果可能是由無窮多個元組組成,例如R={A,B},dom(A)=dom(B)=N(這里N是所有自然數(shù)的集合),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〉},顯然包括無窮多個元組。
為了避免出現(xiàn)運算結果有無窮多個元組的情況,需要定義一種安全的域關系演算。
設Ω是一個數(shù)據(jù)庫模式,Ω={R₁,…,R_n},而ω={r₁,…,r_n}是Ω上的一個關系數(shù)據(jù)庫,對于由提問元組〈x₁, …, x_k〉及公式組成的域關系演算,若S是中的所有符號的集合, 則令:

即dom(,ω)是出現(xiàn)在關系r₁, …,r_n中所有值與所有中的符號組成的集合。
如果該域關系演算滿足以下條件則稱它(對ω)是安全的: ①若為真, 則每個x_i必屬于dom(,ω)。②若(∃u)(₁₎是中的一個子公式, 則使₁為真的u,其各分量必須都在dom(,ω)中。③若(∀u)(₁₎是中的一個子公式, 則使₁為假的u, 其各分量必須都在dom(,ω)中。 已證明安全的域關系演算運算的結果一定不會有無窮多個元組。
2.元組關系演算
元組關系演算也是由提問元組及公式兩部分組成。提問元組是一個代表元組的變量,例如t。若Ω={R₁,…,R_n}是一個關系數(shù)據(jù)庫模式,每個關系模式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是常數(shù),而θ∈{<,≤,=,≥,>,≠}。
(3)原子合式是公式,原子不等式是公式。
(4)ψ₁、ψ₂是公式, 則ψ₁∧ψ₂,ψ₁∨ψ₂,ψ₁及ψ₁加小括號(ψ₁)都是公式。
(5)ψ是公式,則(∀x)ψ是公式,x是全稱變量,(∀x)表示“對所有x”。
(6)ψ是公式, 則(∃x)ψ是公式,x是存在變量,(∃x)表示“存在著x”。
(7)只有以上形成的是公式。
若ω是Ω上的關系數(shù)據(jù)庫(關系數(shù)據(jù)庫請參看關系數(shù)據(jù)庫條目),則元組關系演算的運算結果是能使公式成立的提問元組的所有可能值。
如果不加什么限制,元組關系演算的運算結果也可能是由無窮多個元組組成,例如R={A,B},dom(A)=dom(B)=N(這里N是所有自然數(shù)的集合),R上的關系r如表1所示。
則以下元組關系演算:提問元組:t公式:R〈t〉的運算的結果是集合{〈x,y〉|x,y∈N,〈x,y〉≠〈1,2〉,〈x,y〉≠〈3,4〉},顯然包括無窮多個元組。
為了避免出現(xiàn)運算結果有無窮多個元組的情況,需要定義一種安全的元組關系演算。
若是一個元組關系演算中的公式, Ω是一個數(shù)據(jù)庫模式,Ω={R₁,…,R_n},而ω={r₁,…,r_n}是Ω的一個關系數(shù)據(jù)庫,而S是中的所有符號的集合,則令:

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

即dom(,ω)是由出現(xiàn)在關系r₁, …,r_n中所有值以及所有中的符號組成的集合。
我們說一個以t為提問元組, 以為公式的元組關系演算(對ω)是安全的是指: ①只要t滿足, t的每個分量就是dom(,ω)的元素。 ②對中的每個形如(∃u)(`)的子公式, 若u適合`, 則u的每個分量都是dom(`,ω)的元素。③對中的每個形如(∀u)(`)的子公式,若u的某個分量不在dom(`,ω)中, 則u就滿足`。 已證明安全的元組關系演算運算的結果一定不會有無窮多個元組。
Codd及Pirotte已證明域關系演算、安全的元組關系演算、關系代數(shù)是等價的。