關聯模型

用於資料庫管理的關聯模型（英語：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中沒有兩個不同的元組t₁和t₂使t₁[K] = t₂[K]。

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

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

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

定義函數依賴 X->Y在關聯（H, B）中保持，條件是X和Y是H的子集並且對於在B中所有的元組t₁和t₂使得如果t₁[X] = t₂[X]則't₁[Y] = t₂[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

S⁺ = T⁺
沒有T的真子集U使S⁺ = U⁺，
如果X->Y在T中則Y是單元素（singleton）集合併且
如果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.

外部連結[編輯]

參見[編輯]

關聯的不同歷史版本的元組式控制（英語：Tuple-versioning）