元组关系演算

**元組演算**是埃德加・科德導入的演算，是關係模型的一部分，發展目的是提供宣告式的資料庫查詢語言。資料庫查詢語言 QUEL 和後來的 SQL 中的一些靈感是由元組演算而來。SQL 和原來的關係模型和演算已有許多不同，後來成為實際上的資料庫查詢語言標準，幾乎所有的關係資料庫管理系統中都會用到 SQL 或是其變體。後來 Lacroix 和 Pirotte 提出了接近於一階邏輯的域演算，並證明了這兩種演算和關係代數在表達能力上是等價的。若關係資料庫的查詢語言可以表達一種以上上述的查詢方式，則可稱為具有「關係完備性」。

域關係演算與元組關係演算最大的區別是域關係演算中的變量表示資料庫的表屬性，而元組關係演算的變量表示元組，即資料庫的一行。

## 演算的定義

### 關係資料庫

由於元組關係演算是關係資料庫的查詢語言，因此要定義關係資料庫。

* 關係資料庫：其基本元件是域或數據類型。
* 屬性：域和值的有序對。
* 元組：屬性的有序多重集。
* 關係變量是域和名字的有序對的集合，是關係的表頭。
* 關係是元組的集合。

這些關係概念雖是數學定義，但定義可以大致對應到傳統的資料庫概念。表是一種關係的可視表示法；元組類似於「行」的概念。

假定有一個包含各列名稱（"name", "author", "address" 等）的集合 _C_，再定義「表頭」為 _C_ 的有限子集。定義「關係資料庫模式」為三元組 _S_ = (_D_, _R_, _h_)，這裡的 _D_ 是原子值的域（更詳細的域和原子值的概念參見關係模型），_R_ 是關係名稱的有限集合，而

　
: _h_ : _R_ → 2C

是一個將關係名稱集合 _R_ 的元素對應到表頭的函數（此處是對完全關係模型的簡化，完全關係模型中可能不止一個域，並且表頭不單只是列名的集合，還要將列名映射一個域。） 給定一個域 _D_，可以定義在 _D_ 上的「元組」為偏函數

　
: _t_ : _C_ → _D_

它映射某些列名到 _D_ 中的原子值。例如 (name : "Harry", age : 25)。

在 _D_ 上的所有元組的集合指示為 _T_D。元組 _t_ 定義於的 _C_ 的子集叫做 _t_ 的「域」(不要混淆於模式中的域) 並指示為 _dom_(_t_)。

給定模式 _S_ = (_D_, _R_, _h_) 最後我們定義「關係資料庫」為函數

　
: _db_ : _R_ → 2TD

它映射 _R_ 中的關係名字到 _T_D 的有限子集，使得對於所有 _R_ 中的關係名字和 _db_(_r_) 中的元組 _t_ 有著

　
: _dom_(_t_) = _h_(_r_).

後者要求簡單的聲稱在關係中所有元組都應該包含同樣的列名，也就是在模式中所定義的那些。

### 原子

對於公式構造，我們假定元組變量的一個無限集合 _V_。定義公式要給定一個資料庫模式 _S_ = (_D_, _R_, _h_) 和一個偏函數 _type_ : _V_ -> 2C，它定義指派表頭到某些元組變量的「類型指派」。接著用如下規則定義「原子公式集合」 _A_[_S_,_type_]:

1. 如果 _v_ 和 _w_ 在 _V_ 中，_a_ 在 _type_(_v_) 中而 _b_ 在 _type_(_w_) 中，則公式「_v_._a_ = _w_._b_」在 _A_[_S_,_type_] 中，
2. 如果 _v_ 在 _V_ 中，_a_ 在 _type_(_v_) 中而 _k_ 指示 _D_ 中一個值，則公式「_v_._a_ = _k_」在 _A_[_S_,_type_] 中，
3. 如果 _v_ 在 _V_ 中，_r_ 在 _R_ 中而 _type_(_v_) = _h_(_r_)，則公式「_r_(_v_)」在 _A_[_S_,_type_] 中。

原子的例子:

* (_t_.age = _s_.age) — _t_ 有一個 age 屬性而 _s_ 有一個 age 屬性並有相同的值
* (_t_.name = "Codd") — 元組 _t_ 有一個 name 屬性並且它的值是 "Codd"
* Book(_t_) — 元組 _t_ 存在於關係 Book 中。

定義這種原子的形式語義要給定在 _S_ 上的一個資料庫 _db_ 和一個元組變量綁定 _val_ : _V_ -> _T_D，它映射元組變量到在 _S_ 中的域上的元組:

1. 「_v_._a_ = _w_._b_」是真，若且唯若 _val_(_v_)(_a_) = _val_(_w_)(_b_)
2. 「_v_._a_ = _k_」是真，若且唯若 _val_(_v_)(_a_) = _k_
3. 「_r_(_v_)」是真，若且唯若 _val_(_v_) 在 _db_(_r_) 中

### 公式

同一階邏輯一樣，原子可用通過邏輯算子∧(與)、∨(或) 和 ¬(非) 組合成公式，而且我們可以使用存在量詞 (∃) 和全稱量詞 (∀) 來綁定變量。通過如下規則歸納定義「公式集合」 _F_[_S_,_type_]:

1. 所有在 _A_[_S_,_type_] 中原子也在 _F_[_S_,_type_] 中
2. 如果 _f_1 和 _f_2 在 _F_[_S_,_type_] 中，則公式「_f_1 ∧ _f_2」也在 _F_[_S_,_type_] 中
3. 如果 _f_1 和 _f_2 在 _F_[_S_,_type_] 中，則公式「_f_1 ∨ _f_2」也在 _F_[_S_,_type_] 中
4. 如果 _f_ 在 _F_[_S_,_type_] 中，則公式「¬ _f_」也在 _F_[_S_,_type_] 中
5. 如果 _v_ 在 _V_ 中，_H_ 是一個表頭而 _f_ 是在 _F_[_S_,_type_[_v_->_H_]] 中的一個公式，則公式「∃ _v_ : _H_ ( _f_ )」也在 _F_[_S_,_type_] 中，這裡的 _type_[_v_->_H_] 只是除了映射 _v_ 到 _H_ 之外同於 _type_ 的函數。
6. 如果 _v_ 在 _V_ 中，_H_ 是一個表頭而 _f_ 是在 _F_[_S_,_type_[_v_->_H_]] 中的一個公式，則公式「∀ _v_ : _H_ ( _f_ )」也在 _F_[_S_,_type_] 中

公式的例子:

* _t_.name = "C. J. Date" ∨ _t_.name = "H. Darwen"
* Book(_t_) ∨ Magazine(_t_)
* ∀ _t_ : {author, title, subject} ( ¬ ( Book(_t_) ∧ _t_.author = "C. J. Date" ∧ ¬ ( _t_.subject = "relational model")))

注意最後的公式聲稱 C. J. Date 所寫的所有書籍都有關係模型的主題。如果不導致歧義，我們通常省略圓括號。

我們將假定在量詞量化於在模式中的域上所有元組的全集之上。給定在 _S_ 上的資料庫 _db_ 和元組變量綁定 _val_ : _V_ -> _T_D，給出如下公式的形式語義:

1. 「_f_1 ∧ _f_2」為真，若且唯若「_f_1」為真並且「_f_2」為真，
2. 「_f_1 ∨ _f_2」為真，若且唯若「_f_1」為真或者「_f_2」為真，或者二者都為真，
3. 「¬ _f_」為真，若且唯若「_f_」不為真，
4. 「∃ _v_ : _H_ ( _f_ )」為真，若且唯若存在一個 _D_ 上的元組 _t_ 使得 _dom_(_t_) = _H_ 並且公式「_f_」對於 _val_[_v_->_t_] 為真，
5. 「∀ _v_ : _H_ ( _f_ )」為真，若且唯若對於所有 _D_ 上的元組 _t_ 使得 _dom_(_t_) = _H_ 並且公式「_f_」對於 _val_[_v_->_t_] 為真。

### 查詢

最後給定一個模式 _S_ = (_D_, _R_, _h_) 我們定義查詢表達式為:

　
: { _v_ : _H_ | _f_(_v_) }

這裡的 _v_ 是元組變量，_H_ 是一個表頭而 _f_(_v_) 是 _F_[_S_,_type_] 中的公式，其中 _type_ = { (_v_, _H_) } 並帶有 _v_ 做它的唯一自由變量。對 _S_ 上給定資料庫 _db_ 的這種查詢的結果是在 _D_ 上帶有 _dom_(_t_) = _H_ 的使得 _f_ 對於 _db_ 為真並且 _val_ = { (_v_, _t_) } 的所有元組 _t_ 的集合。

查詢表達式的例子:

* { _t_ : {name} | ∃ _s_ : {name, wage} ( Employee(_s_) ∧ _s_.wage = 50.000 ∧ _t_.name = _s_.name ) }
* { _t_ : {supplier, article} | ∃ _s_ : {s#, sname} ( Supplier(_s_) ∧ _s_.sname = _t_.supplier ∧ ∃ _p_ : {p#, pname} ( Product(_p_) ∧ _p_.pname = _t_.article ∧ ∃ _a_ : {s#, p#} ( Supplies(_a_) ∧ _s_.s# = _a_.s# ∧ _a_.p# = _p_.p# ) }

## 演算的語義和語法限制

### 域獨立查詢

由於量詞的語義使得它們量化在模式中域上所有元組上，如果假定了另一個模式則對一個特定資料庫的一個查詢可能返回不同結果。例如考慮兩個模式 _S1_ = ( _D1_, _R_, _h_ ) 和 _S2_ = ( _D2_, _R_, _h_ )，帶有域 _D1_ = { 1 }, _D2_ = {1, 2}，關係名字 _R_ = { "r1" } 和表頭 _h_ = { ("r1", {"a"}) }。兩個模式有一個公共實例:

　
: _db_ = { ( "r1", { ("a", 1) } ) }

如果我們考慮如下查詢表達式

　
: { _t_ : {a} | _t_.a = _t_.a }

在它在 _db_ 上的結果要麼是在 _S1_ 下的 {(a : 1) } 要麼是在 _S2_ 下的 {(a : 1), (a : 2) }。如果我們採用域為無限集合，則查詢的結果也會是無限的，這是很明顯的。要解決這些問題我們將把我們的注意力限制於「域獨立」的那些查詢，就是說，對一個資料庫的查詢在它的所有模式下都返回同樣的結果。

這些查詢的一個有價值的性質是如果我們假定元組變量取值於所謂的這個資料庫「活躍域」上的元組，它是在資料庫或在查詢表達式中的至少一個元組中出現的域的子集，則查詢表達式的語言不變。事實上，在很多元組演算的定義中，量詞語義就是這麼定義的，這使得定義的所有查詢都是域獨立的。

### 安全查詢

一個查詢是安全的，如果它只有有限的解，並且解集依賴於資料庫里的數據，而不是數據的定義域（數據類型）。安全的查詢才能用關係代數表達。

為了限制查詢表達式使得它們只表示域獨立的查詢，通常介入一個語法概念「安全查詢」。要確定一個查詢是否為安全的，我們要從查詢導出兩種類型的信息。首先是變量 - 列對 _t_._a_ 是否綁定到一個關係或一個常量的列上，其次是兩個變量 - 列對是否直接或間接的相等 (指示為 _t_._v_ == _s_._w_)。

為了推導綁定性，我們介入如下推理規則:

1. 在「_v_._a_ = _w_._b_」中沒有變量 - 列對被綁定
2. 在「_v_._a_ = _k_」中變量 - 列對 _v_._a_ 被綁定
3. 在「_r_(_v_)」中所有的對 _v_._a_ 被綁定於 _type_(_v_) 中的 _a_，
4. 在「_f_1 ∧ _f_2」 中所有的點對都被綁定於要麼 _f_1 中要麼 _f_2 中，
5. 在「_f_1 ∨ _f_2」中所有的點對都被綁定於 _f_1 和 _f_2 二者中，
6. 在「¬ _f_」中沒有點對被綁定，
7. 在「∃ _v_ : _H_ ( _f_ )」中對 _w_._a_ 被綁定，如果它被綁定在 _f_ 中並且 _w_ <> _v_，
8. 在「∀ _v_ : _H_ ( _f_ )」中對 _w_._a_ 被綁定，如果它在 _f_ 中被綁定並且 _w_ <> _v_。

為了推導相等性，我們介入下列推理規則 (位於常用的等價性推理規則：自反性、對稱性和傳遞性之後):

1. 在「_v_._a_ = _w_._b_」中 _v_._a_ == _w_._b_ 成立，
2. 在「_v_._a_ = _k_」中沒有點對相等，
3. 在「_r_(_v_)」中沒有點對相等，
4. 在「_f_1 ∧ _f_2」中 _v_._a_ == _w_._b_ 成立，如果它要麼在 _f_1 中要麼在 _f_2 中成立，
5. 在公式「_f_1 ∨ _f_2」中 _v_._a_ == _w_._b_ 成立，如果它在 _f_1 和在 _f_2 二者中都成立，
6. 「¬ _f_」沒有點對相等，
7. 在「∃ _v_ : _H_ ( _f_ )」中 _w_._a_ == _x_._b_ 成立，如果它在 _f_ 中成立並且 _w_<>_v_ 並且 _x_<>_v_，
8. 在「∀ _v_ : _H_ ( _f_ )」中 _w_._a_ == _x_._b_ 成立，如果它在 _f_ 中成立並且 _w_<>_v_ 並且 _x_<>_v_。

我們接著聲稱一個查詢表達式 {v : H | f (v) } 是安全的，如果

* 對於所有 _H_ 中的列名 _a_，我們可以得出 _v_._a_ 等於一個 _f_ 中的綁定對，
* 對於形如「∀ _w_ : _G_ ( _g_ )」的所有 _f_ 的子表達式，我們可以得出對於所有 _G_ 中的列名 _a_ 我們可以得出 _w_._a_ 等於一個 _g_ 中的綁定對，
* 對於形如「∃ _w_ : _G_ ( _g_ )」的所有 _f_ 的子表達式，我們可以得出對於所有 _G_ 中的列名 _a_ 我們可以得出 _w_._a_ 等於一個 _g_ 中綁定對。

安全查詢表達式的限制不限制表達能力，因為所有能被表達出來的域獨立查詢都可以用安全查詢表達式表達。這可以做如下證明，對於模式 _S_ = (_D_, _R_, _h_)，給定在這個查詢表示式中常量的集合 _K_，元組變量 _v_ 和表頭 _H_，我們可以為所有的對 _v_._a_ 構造一個安全公式，它帶有 _a_ 在 _H_ 中並聲稱其值在活躍域中。例如，假定 _K_={1,2}、_R_={"r"} 和 _h_ = {("r", {"a,"b"}) } 則 _v_.b 對應的安全公式為:

　
: _v_.b = 1 ∨ _v_.b = 2 ∨ ∃ _w_ ( r(w) ∧ ( _v_.b = _w_.a ∨ _v_.b = _w_.b ) )

接著通過在這個表達式中用到地方對所有變量 _v_ 和它的類型中的列名 _a_ 增加這個公式，可以用這個公式來把任何不安全的查詢表達式重寫為等價的安全查詢表達式。這有效的使得所有變量都取值於活躍域之上，如果表達的查詢是域獨立的，象已經解說的那樣不改變語義。

## 相關條目

* 關係代數 \_(資料庫)
* 關係演算
  * 域關係演算

## 參考資料

* Edgar F. Codd: A Relational Model of Data for Large Shared Data Banks. _Communications of the ACM_, 13(6):377–387, 1970.