關聯模型

用於資料庫管理的**關聯模型**（英語：Relational model）是基於謂詞邏輯和集合論的一種資料模型，廣泛被使用於資料庫之中。最早於 1970 年由埃德加・科德提出。

## 模型

關聯模型的基本假定是所有資料都表示為數學上的關聯，就是說 _n_ 個集合的笛卡兒積的一個子集，有關這種資料的推理通過二值（就是說沒有 NULL）的謂詞邏輯來進行，這意味著對每個命題都有兩種可能的賦值：要麼是真要麼是假。資料通過關聯演算和關聯代數的一種方式來操作。關聯模型是採用二維表格結構表達實體類型及實體間聯繫的數據模型.

關聯模型允許設計者通過資料庫規範化的提煉，去建立一個信息的一致性的模型。訪問計劃和其他實現與操作細節由 DBMS 引擎來處理，而不應該反映在邏輯模型中。這與 SQL DBMS 普遍的實踐是對立的，在它們那裡性能調整經常需要改變邏輯模型。

基本的關聯建造塊是域或者叫資料類型。元組是屬性的有序多重集（multiset），屬性是域和值的有序對。關聯變量（relvar）是域和名字的有序對（序偶）的集合，它充當關聯的表頭（header）。關聯是元組的集合。儘管這些關聯概念是數學上的定義的，它們可以寬鬆的映射到傳統資料庫概念上。表是關聯的公認的可視表示；元組類似於_行_的概念。

關聯模型的基本原理是信息原理：所有信息都表示為關聯中的資料值。所以，關聯變量在設計時刻是相互無關聯的；反而，設計者在多個關聯變量中使用相同的域，如果一個屬性依賴於另一個屬性，則通過參照完整性來強制這種依賴性。

## 競爭者

其他模型還有層次模型和網狀模型。使用這些舊體系的一些系統現在仍在一些資料中心中使用，那裡有高資料容量需求或者現存系統複雜得使遷移到採用關聯模型的系統花費巨大；還要注意新的對象資料庫，儘管它們中很多都是 DBMS 構造工具，而不是嚴格的 DBMS。

關聯模型是第一個形式化的資料庫模型。在它被定義之後，非形式化模型被用做描述層次資料庫（層次模型）和網狀資料庫（網狀模型）。層次和網狀資料在關聯資料庫之前就存在了，但是只在關聯模型被定義之後才作為模型來描述，用來建立比較的基礎。

## 歷史

關聯模型是由埃德加・科德博士作為資料的一般模型而發明的，隨後由克里斯托佛・達特和休・達溫（Hugh Darwen）等人維護和開發。在第三次宣言（1995 年）中他們展示了如何向關聯模型擴展上物件導向特徵而不用妥協它的基本原理。

## SQL 標準與關聯模型

SQL 最初作為關聯資料庫的標準語言而提出，而在實際上總是違背它。所以 SQL DBMS 實際上不是真正的 RDBMS，並且當前 ISO SQL 標準不提及關聯模型或者使用關聯術語或概念。

## 實現

已經有很多嘗試去生成埃德加・科德、克里斯多佛・戴特、休・達溫等人開發的關聯資料庫模型的真正實現。但都沒有獲得流行性成功。Rel （頁面存檔備份，存於網際網路檔案館）是其中最新的嘗試之一。SQL 使用概念 "表"、"列" 和 "行" 來替代 "關聯變量"、"屬性" 和 "元組"。

## 爭論

科德自己提議了關聯模型的一個三值邏輯版本，而且四值邏輯版本也被提議了，用來處理缺失信息。但是這些都未被實現，大概是由於顧及到了複雜性。SQL NULL 意圖成為三值邏輯系統的一部分，但是由於在標準和它的實現中的邏輯上的錯誤而沒有達到目標。

## 設計

資料庫規範化通常在設計關聯資料庫時進行，用來增進資料庫設計的邏輯上的一致性和事務處理性能。

有兩種常用的模式圖系統來輔助**關聯模型**的可視表示：實體 - 聯繫模式圖（實體關聯圖），和美國空軍在 ERD 基礎上建立的 IDEF1X 方法中所使用的關聯 IDEF 模式圖。

## 樣例資料庫

一些關聯變量和它們的屬性的一個理想化和非常簡單的例子：

Customer（**Customer ID**, Tax ID, Name, Address, City, State, Zip, Phone）

Order（**Order No**, Customer ID, Invoice No, Date Placed, Date Promised, Terms, Status）

Order Line（**Order No**, **Order Line No**, Product Code, Qty）

Invoice（**Invoice No**, Customer ID, Order No, Date, Status）

Invoice Line（**Invoice No**, **Line No**, Product Code, Qty Shipped）

Product（**Product Code**, Product Description）

在這個設計中我們有六個關聯變量：Customer, Product, Order, Order Line, Invoice, 和 Invoice Line. 粗體字有下劃線的屬性是_候選鍵 (碼)_。非粗體字有下劃線的屬性是_外鍵 (碼)_。

通常任意選擇一個候選鍵 (碼) 叫做主鍵 (碼) 並且優先於其他候選鍵（碼），它們也就被叫做可選鍵 (碼)。

_候選鍵（碼）_ 是強制元組不重複的唯一性標識符；否則關聯就違背了集合的基本定義而成為是叫做包的東西了。鍵 (碼) 可以是複合的，就是說可以由多個屬性組合而成。下面是我們的例子顧客關聯變量的一個表格化描述；關聯可以被認為是歸結到一個關聯變量的值。

## 集合理論公式

關聯模型中的基本概念是_關聯名字_和_屬性名字_。我們通常把他們表示為如「Person」和「name」這樣的字符串，並且我們通常使用變量 _r_、_s_、_t_、…… 和 _a_、_b_、_c_ 來涉及它們。另一個基本概念_原子值_的集合包含著如數值和字符串這樣的值。

我們的第一個定義關注_元組_的概念，它是表格中行或記錄的概念的形式化。

　
: **定義** _元組_是從一組屬性名字到一組原子值的偏函數。

　
: **定義** _表頭_是屬性名字的有限集合。

　
: **定義**元組 _t_ 在屬性的有限集合 _A_ 上的_投影_是 _t_[_A_] = { (_a_, _v_) : (_a_, _v_) ∈ _t_, _a_ ∈ _A_ }。

下一個定義定義了_關聯_，它是關聯模型中對表格內容的形式化。

　
: **定義** _關聯_是帶有表頭 _H_ 和表體 _B_ 的一個元組（_H_, _B_），表體是都有域 _H_ 的元組的集合。

這種關聯緊密的對應於在一階邏輯中通常叫做謂詞外延的東西，除了我們這裡用屬性名字標識在謂詞中的位置之外。在關聯模型中資料庫模式是由一組關聯名字，與這些名字相關聯的表頭，和在資料庫模式的每個實例上保持的約束構成的。

　
: **定義**在表頭 _H_ 上的_關聯全集'**U**_**是有表頭 _H_ 的關聯的非空集合。**

　
: **定義** _關聯模式_（_H_, _C_）由表頭 _H_ 和對有表頭 _H_ 的所有關聯 _R_ 定義的謂詞 _C_(_R_) 構成。

　
: **定義** 如果關聯有表頭 _H_ 並滿足 _C_ 則它滿足關聯模式（_H_, _C_）。

### 鍵（碼）約束和函數依賴

最簡單和最重要的一類關聯約束是_鍵（碼）約束_。它告訴我們在特定關聯模式的所有實例中元組可以通過它特定屬性的值來標識。

　
: **定義** _超鍵（碼）_ 被寫為屬性名字的有限集合。

　
: **定義**超鍵（碼）_K_ 在關聯（_H_, _B_）中保持，條件是 _K_ ⊆ _H_ 並且在 _B_ 中沒有兩個不同的元組 _t1_ 和 _t2_ 使 _t1_[_K_] = _t2_[_K_]。

　
: **定義**超鍵（碼）在表頭 _H_ 之上的關聯全集 _U_ 中保持，條件是它在 _U_ 中的所有關聯中保持。

　
: **定義**超鍵（碼）_K_ 保持為在 _H_ 之上的關聯全集 _U_ 的一個_候選鍵 (碼)_，條件是它保持為 _U_ 的超鍵（碼）並且沒有 _K_ 的真子集也保持為 _U_ 的超鍵（碼）。

　
: **定義** _函數依賴_（簡寫為 FD）被寫為 _X_->_Y_，_X_ 和 _Y_ 是屬性名字的有限集合。

　
: **定義**函數依賴 _X_->_Y_ 在關聯（_H_, _B_）中保持，條件是 _X_ 和 _Y_ 是 _H_ 的子集並且對於在 _B_ 中所有的元組 _t1_ 和 _t2_ 使得如果 _t1_[_X_] = _t2_[_X_] 則 't1_[_Y_] =_ t2_[_Y_]。_

　
: **定義**函數依賴 _X_->_Y_ 在表頭 _H_ 之上的關聯全集 _U_ 中保持，條件是它在 _U_ 中的所有關聯中保持。

　
: **定義**函數依賴在表頭 _H_ 下是_不證自明的_，條件是它在 _H_ 下的所有關聯全集中保持。

　
: **定理** FD _X_->_Y_ 在表頭 _H_ 下是不證自明的，若且唯若 _Y_ ⊆ _X_ ⊆ _H_。

　
: **定理**超鍵（碼）_K_ 在 _H_ 之上的關聯全集 _U_ 中保持，若且唯若 _K_ ⊆ _H_ 並且 _K_->_H_ 在 _U_ 中保持。

　
: **定義（Armstrong 規則）** 設 _S_ 是 FD 的集合，則 _S_ 在表頭 _H_ 下的_閉包_寫為 _S_+，它是 _S_ 的符合如下規律的最小超集:

　
: (自反律) 如果 _Y_ ⊆ _X_ ⊆ _H_，則 _X_->_Y_ 在 _S_+ 中。

　
: (傳遞律) 如果 _X_->_Y_ 在 _S_+ 中並且 _Y_->_Z_ 在 _S_+ 中，則 _X_->_Z_ 在 _S_+ 中。

　
: (增廣律) 如果 _X_->_Y_ 在 _S_+ 中並且 _Z_ ⊆ _H_，則 _X_∪_Z_ -> _Y_∪_Z_ 在 _S_+ 中。

　
: **定理** Armstrong 規則是可靠的和完備的，就是說給定一個表頭 _H_ 和只包含 _H_ 的子集的 FD 集合 _S_，則 FD _X_->_Y_ 在 _S_+ 中，若且唯若在它在 _H_ 之上的其中所有的 _S_ 中的 FD 都保持的所有的關聯全集中保持。

　
: **定義**如果 _X_ 是屬性的有限集合併且 _S_ 是 FD 的有限集合，則 _X_ 在 _S_ 下的_補集_寫為 _X_+，它是符合如下規律的 _X_ 的最小超集：

　
: 如果 _Y_->_Z_ 在 _S_ 中並且 _Y_ ⊆ _X_+ 則 _Z_ ⊆ _X_+。

屬性集合的補集可以用來計算特定的依賴是否在 FD 集合的閉包中。

　
: **定理**給定表頭 _H_ 和只包含 _H_ 的子集的 FD 的集合 _S_，_X_->_Y_ 保持在 _S_+ 中，若且唯若 _Y_ ⊆ _X_+。

　
: **算法（從 FD 推導候選鍵（碼）)**

```
      **INPUT:**只包含表头_H_的子集的FD的集合_S_
      **OUTPUT:**在_H_之上的其中所有的_S_中的FD都保持的所有的关系全集中
                保持为候选键（码）的超键（码）的集合_C_
      **begin**
        _C_ := ∅;          // 找到的候选键（码）
        _Q_ := { _H_ };      // 包含候选键的超键（码）
        **while** _Q_ <> ∅ **do**
          设_K_是来自_Q_的某个元素;
          _Q_ := _Q_ - { _K_ };  
          _minimal_ := **true**;
          **for each** _X->Y_ **in** _S_ **do** 
            _K'_ := (_K_ - _Y_) ∪ _X_;   // 推导新超键（码）
            **if** _K'_ ⊂ _K_
            **then**
              _minimal_ := **false**;
              _Q_ := _Q_ ∪ { _K'_ };
            **fi**
          **od**
          **if** _minimal_ **and**没有_K_的子集在_C_中
          **then**
            从_C_中去除_K_的所有超集;
            _C_ := _C_ ∪ { _K_ };
          **fi**
        **od**
      **end**
```

　
: **定義**給定表頭 _H_ 和只包含 _H_ 的子集的 FD 的集合 _S_，_S_ 的_不可簡約覆蓋_是符合如下規律的 FD 的集合 _T_

1. _S_+ = _T_+
2. 沒有 _T_ 的真子集 _U_ 使 _S_+ = _U_+，
3. 如果 _X_->_Y_ 在 _T_ 中則 _Y_ 是單元素（singleton）集合併且
4. 如果 _X_->_Y_ 在 _T_ 中並且 _Z_ 是 _X_ 的真子集則 _Z_->_Y_ 不在 _S_+ 中。

## 引用

* Codd, E. F. (1970). "A relational model of data for large shared data banks". _Communications of the ACM_, , Vol. 13, No. 6, pp. 377-387. Retrieved from https://web.archive.org/web/20070612235326/http://www.acm.org/classics/nov95/toc.html Sept. 4, 2004.
* Date, C. J., Darwen, H. (2000). "Foundation for Future Database Systems: The Third Manifesto", 2nd Edn. Addison-Wesley.
* Date, Christopher J. (2003). "Introduction to Database Systems". 8th ed.

## 外部連結

* 關聯式模型
* A Relational Model of Data for Large Shared Data Banks
* DMoz category
* Relational Model （頁面存檔備份，存於網際網路檔案館）

## 參見

* 關聯的不同歷史版本的元組式控制