關係代數 (資料庫)

"這裡的關係代數不同於奧古斯都·德·摩根在1860年為代數邏輯提供的關係代數"關係代數是一階邏輯的分支，是閉合於運算下的關係的集合。運算作用於一個或多個關係上來生成一個關係。關係代數是計算機科學的一部分。在純數學中的關係代數是有關於數理邏輯和集合論的代數結構。介紹.關係代數在1970年E.F. Codd發表資料的關係模型之前很少受到注意。Codd曾是皮爾士選集編輯者Arthur W. Burks的博士研究生。Codd提議這樣一種代數作為資料庫查詢語言的基礎。第一個基於Codd的代數的查詢語言是ISBL，許多作者都認同這個先驅的工作展示了一個使Codd的想法成為有用語言的方式。商務系統12是追隨ISBL先例的短命工業級實力的關係DBMS。在1998年Chris Date和Hugh Darwen提議了一種叫Tutorial D的語言，意圖用於教學關係資料庫理論，它的查詢語言也吸取了ISBL的想法。Rel是Tutorial D的一個實現。即使SQL的查詢語言也鬆散的基於了關係代數，儘管SQL中的運算元不完全是關係，很多有用的關於關係代數的理論在SQL對應者中不成立。因為關係被解釋為某個謂詞的外延，關係代數的每個運算在謂詞演算中都有對應者。例如，自然連線是邏輯AND是表示謂詞"p1" formula_1 "p2"的外延的關係。認識到Codd的代數事實上關於一階邏輯不完備是很重要的。實現它會引起不可逾越的特定計算困難。為了克服這些困難，他限制運算元為有限關係，並提議了對否定的有限支援。類似的限制在很多其他基於邏輯的計算機語言中也能見到。Codd定義術語關係完備性來稱呼一個語言除了他提議的限制之外關於一階邏輯是完備的。在實踐中這些限制對他的關係代數用於資料庫用途的適用性沒有不利作用。原始運算.如同任何代數，一些運算是原始的，而可以透過原始運算來定義的另一些運算是匯出的。儘管邏輯中的AND, OR和NOT的選取，某種程度上是任意性的是眾所周知的，Codd對他的代數作了類似的任意選取。Codd的代數的六個原始運算是“選擇”、“投影”、笛卡爾積。這六個運算在省略其中任何一個都要損失表達能力的意義上是基本的。已經依據這六個原始運算定義了很多其他運算。其中最重要的是交集、除法和自然連線。事實上ISBL顯著的用自然連線替代了笛卡爾積，它是笛卡爾積的退化情況。總之，關係代數的運算有與域關係演算或元組關係演算同樣的表達能力。但是出於前面介紹中給出的原因，關係代數有嚴格弱於沒有函式符號的一階謂詞演算的表達能力。關係代數實際上對應於一階邏輯的子集，即沒有遞迴和否定的Horn子句。集合運算.儘管六個基本運算中有三個取自集合論，在它們的關係代數對應者中存在額外的約束：對於並集和差集，涉及到的兩個關係必須是“並集相容”的—就是說，兩個關係必須有同樣的屬性集合。因為交集可以用差集來定義，交集所涉及的兩個關係也必須是並集相容的。笛卡爾積定義得與集合論有所不同，這裡的元組是平坦的、無子元組的。就是說，不同於集合論，那裡的"n"元組和"m"元組的笛卡爾積是2元組，而關係代數中它們的笛卡爾積把這個2元組展平為"n"+"m"元組。更形式的說，"R" × "S"被定義為："R" formula_4 "S" = {"r" formula_5 "s"| "r" formula_6 "R", "s" formula_6 "S"}此外，對於要定義的笛卡爾積，涉及的兩個關係必須有不相交表頭—就是說，它們一定不能有公共屬性名字。投影 (π).投影是寫為formula_8的一元運算，這裡的formula_9是屬性名字的集合。這種投影的結果定義為當所有在formula_10中的元組被限制為集合formula_11的時候所獲得的集合。選擇 (σ).廣義選擇是寫為formula_12的一元運算，這裡的formula_13是由正常選擇中所允許的原子和邏輯運算元formula_1構成的命題公式。這種選擇選出formula_10中使formula_13成立的所有元組。重新命名 (ρ).重新命名是寫為formula_19的一元運算，這裡的結果同一於formula_10，除了在所有元組中的formula_21欄位被重新命名為formula_22欄位之外。它被簡單的用來重新命名關係的屬性或關係自身。連線和類似連線的運算.自然連線 (⋈).自然連線是寫為 ("R" ⋈ "S")的二元運算，這裡的"R"和"S"是關係。自然連線的結果是在"R"和"S"中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格“僱員”和“部門”和它們的自然連線：連線是關係複合的另一種術語；在範疇論中連線精確的是纖維積。自然連線被確證為最重要的演算法之一，因為它是邏輯AND的關係對應者。仔細注意如果同一個變數在用AND連結的兩個謂詞中出現，則這個變量表示相同的事物而兩個出現必須總是由同一個值來代換。特別是，自然連線允許組合有外來鍵關聯的關係。例如，在上述例子中，外來鍵成立於從"僱員"."DeptName"到"部門"."DeptName"，"僱員"和"部門"的自然連線組合了所有僱員和它們的部門。注意這能工作因為外來鍵在相同名字的屬性之間保持。如果不是這樣，外來鍵成立於從"部門"."manager"到"Emp"."emp-number"，則我們必須在採用自然連線之前必須重新命名這些列。這種自然連線有時叫做相等連線。更形式的說，自然連線的語義定義為："R" formula_2"S" = { "t" formula_5 "s" : "t" formula_6 "R", "s" formula_6 "S", fun ("t" formula_5 "s") }這裡的fun("r")是對於二元關係"r"為真的謂詞，當且僅當"r"是函式二元關係。通常要求"R"和"S"必須至少有一個公共屬性，但是如果省略了這個約束則在那種特殊情況下自然連線就完全變成上面定義的笛卡爾積。自然連線可以用Codd的原始運算模擬如下。假定"b1...,bm"是公共於"R"和"S"的公共屬性名字，"a1...,an"是唯一於"R"的屬性名字而"c1...,ck"是唯一於"S"的屬性名字。進一步假定屬性名字 "d1...,dm"不在"R"和"S"二者中。第一步我們可以重新命名"S"中的公共屬性名字：: "S' ":= ρ"d1"/"b1"(...ρ"dm"/"bm"("S")...)，接著我們採用笛卡爾積並選擇要連線的元組：: "T" := σ"b1"="d1"(...σ"bm"="dm"("R" × "S')...) "，最後我們採用一個投影來去掉重新命名的屬性：: "U" := π"a1...,an,b1...,bm,c1...,ck"("T")θ-連線和相等連線.考慮分別列出車模和船模的價格的表“車”和“船”。假設一個顧客要購買一個車模和一個船模，但不想為船花費比車更多的錢。在關係上的θ-連線"CarPrice" ≥ "BoatPrice"生成所有可能選項的一個表。如果我們要組合來自兩個關係的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的連線運算元才方便，這就是θ-連線。θ-連線是寫為formula_28或formula_29的二元運算元，這裡的"a"和"b"是屬性名字，θ是在集合{, ≥}中的二元關係，"v"是值常量，而"R"和"S"是關係。這個運算的結果由在"R"和"S"中滿足關係θ的元素的所有組合構成。只有"S"和"R"的表頭是不相交的，即不包含公共屬性的情況下，θ-連線的結果才是有定義的。這個運算可以用基本運算模擬如下："R" formula_2θ "S" = σθ("R" × "S")在運算元θ是等號運算元 (=)的時候這個連線也相等連線。但是要注意，支援自然連線和重新命名的計算機語言可以不需要θ-連線，因為它可以透過對自然連線的選擇來完成。半連線 (⋉)(⋊).半連線是類似於自然連線的寫為"R" ⋉ "S"的連線，這裡的"R"和"S"是關係。半連線的結果只是在"S"中有在公共屬性名字上相等的元組所有的"R"中的元組。例如下面的例子是“僱員”和“部門”和它們的半連線的表：更形式的說半連線的語義定義如下："R" formula_31 "S" = { "t" : "t" formula_6 "R", "s" formula_6 "S", fun ("t" formula_5 "s") }這裡的fun("r")定義同於自然連線。半連線可以被使用自然連線模擬如下。假定"a1...,an"是"R"的屬性名字，則："R" formula_31 "S" = formula_36"a1"..,"an"因為我們可以透過基本運算模擬自然連線因此也就可以模擬半連線。反連線 (▷).反連線是類似於自然連線的寫為"R" ▷ "S"的連線，這裡的"R"和"S"是關係。反連線的結果是在"S"中沒有在公共屬性名字上相等的元組的"R"中的那些元組。例如“僱員”和“部門”和它們的反連線的表：反連線形式定義為："R" formula_38 "S" = { "t" : "t" formula_6 "R" formula_1 formula_41"s" formula_6 "S" : fun ("t" formula_5 "s") }或"R" formula_38 "S" = { "t" : "t" formula_6 "R"，"S"中沒有"s"滿足fun ("t" formula_5 "s") }這裡的fun("r")定義同於自然連線。反連線還可以定義為半連線的補集："R" formula_38 "S" = "R" - "R" formula_31 "S"為此反連線有時叫做反半連線，反連線運算元有時寫為其上有橫槓的半連線符號。除法 (÷).除法是寫為"R" ÷ "S"的二元關係。其結果由"R"中元組到唯一於"R"的屬性名字的限制構成，並且它們與"S"中的元組的所有組合都存在於"R"中。例如下面的“完成”和“DB專案”和它們的除法：如果“DB專案”包含資料庫專案的所有任務，則這個除法的結果精確的包含已經完成了資料庫專案的所有學生。更形式的說除法的語義定義如下："R" ÷ "S" = { "t"["a1...,an"] : t formula_6 "R" formula_50 formula_51"s" formula_6 "S" ( ("t"["a1...,an"] formula_5 "s") formula_6 "R") }這裡的{"a1...,an"}是唯一於"R"的屬性名字的集合而"t"["a1...,an"]是"t"到這個集合的限制。通常要求在"S"的表頭中的屬性名字是"R"的表頭的屬性名字的子集，否則運算的結果永遠為空。除法可以用基本運算模擬如下。我們假定"a1...,an"是唯一於"R"的屬性名字而"b1...,bm"是"S"的屬性名字。在第一步中我們投影"R"於它的唯一屬性上，並接著構造它們與"S"的元組的所有組合："T" := π"a1...,an"("R") × "S"在上面例子中，T將是表示所有學生與所有給定任務的組合的表。所以Eugene在T中將有兩行Eugene -&gt; Database1和Eugene -&gt; Database2。在下個步驟中，我們從這個關係中減去"R":"U" := "T" - "R"注意在"U"的都是"R"中沒有出現的可能的組合。所以如果現在做到唯一於"R"的屬性名字的投影，則我們有了"R"中元組的限制，它們與"S"的元組的所有組合都未出現在"R"中："V" := π"a1...,an"("U")剩下的就是投影"R"到唯一於它的屬性名字並減去"V":"W" := π"a1...,an"("R") - "V"外連線.儘管連線的結果是由組合兩個運算元的匹配元組而形成的元組組成，外連線由這些元組加上透過向一個運算元的未匹配元組擴充套件上另一個運算元的每個屬性的“填充”值而形成的元組組成。本節定義的運算假定“空”值"ω"的存在性，我們不定義它並把它用做填充值。不應當假定它為資料庫語言SQL所定義的NULL，也不應該假定"ω"為一個標號而非一個值，也不應該假定它介入了有爭議的三值邏輯。定義三個外連線：左外連線、右外連線和全外連線。左外連線 (⟕).左外連線寫成"R" ⟕ "S"，其中"R"與"S"為關係。左外連線的結果包含"R"中所有元組，對每個元組，若在"S"中有在公共屬性名字上相等的元組，則正常連線，若在"S"中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為NULL。formula_55右外連線 (⟖).右外連線寫成"R" ⟖ "S"，其中"R"與"S"為關係。右外連線的結果包含"S"中所有元組，對每個元組，若在"R"中有在公共屬性名字上相等的元組，則正常連線，若在"R"中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為NULL。formula_56全外連線 (⟗).全外連線寫成"R" ⟗ "S"，其中"R"與"S"為關係。全外連線的結果包含"R"與"S"中所有元組，對每個元組，若在另一關係上中有在公共屬性名字上相等的元組，則正常連線，若在另一關係上中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為NULL。"R" ⟗ "S" = ("R" ⟕ "S") ∪ ("R" ⟖ "S")域計算的運算.聚集運算.多數資料庫包括五個聚集函式。這些運算是Sum、Count、Average、Maximum和Minimum。在關係代數中被寫為Exp1,Exp2,Exp3...Gfunc1,func2,func3...。關係代數的限制.儘管關係代數對於大多數用途都足夠強大了，有一些在關係上的簡單而自然的運算不能用關係代數表達。二元關係的傳遞閉包就是其中之一。給定一個域"D"，設二元關係"R"是"D"x"D"的子集。"R"的傳遞閉包"R+"是包含"R"的滿足如下條件的"D"x"D"的子集：formula_51x formula_51y formula_59z((x,y) formula_6 R formula_50 (y,z) formula_6 R formula_63 (x,z) formula_6 R)可以證明沒有關係代數表示式"E"("R")接受"R"作為變數引數而生成"R"+。證明基於如下事實，給定一個關係表示式"E"，對它聲稱"E"("R") = "R"+，這裡的"R"是變數，我們總是可以找到"R"的一個例項r(和一個對應的域d)使得"E"(r) ≠ r+。有用於查詢最佳化的代數性質.查詢可以表示為一個樹，這裡的主要目標是把表示式樹變換成等價的表示式樹，使得在樹中的子表示式生成的關係的平均大小比最佳化前更小。次要目標是在一個單一查詢中，或在要同時求值多於一個查詢的時候的所有這些查詢中，嘗試形成公共子表示式。在次要目標背後的原理是計算公共子表示式一次就夠了，其結果可以用於包含這個子表示式的所有查詢中。我們提出可用於這種變換的一組規則。選擇.關於選擇運算的規則在查詢最佳化中扮演了最重要的角色。選擇是可非常有效的減少在它的運算元中的行數的運算，所以如果我們設法把在表示式樹中選擇向著葉子方向移動，內部關係的大小將被縮小。基本選擇性質.選擇是冪等性的。分解有複雜條件的選擇.其條件是更簡單條件的合取的選擇等價於針對這些單獨條件的一序列選擇，而其條件是析取的選擇等價於選擇的並集。可以使用這些恆等式來合併多個選擇為更少的需要求值的選擇，或分解它們使得其成員選擇可以被移動或單獨最佳化。選擇和叉積.叉積對於計算是最耗費的運算元。如果輸入關係有formula_69和formula_70行，結果將包含formula_71行。所以在應用叉積運算元之前盡最大可能減少兩個運算元的大小是非常重要的。這可以有效的完成，如果叉積跟隨著選擇運算元，比如formula_72(formula_10 × formula_74)。這是最合適考慮連線定義的情況。如果叉積不跟隨著選擇運算，我們可以嘗試使用其他規則從表示式樹更高層壓下一個選擇。在上節情況下我們使用對複雜條件的分解規則把條件formula_75分解為條件formula_76、formula_77和formula_78，使得formula_75 = formula_76 formula_50 formula_77 formula_50 formula_78，而formula_76只包含來自formula_10的屬性，formula_77只包含來自formula_74的屬性，formula_78包含formula_75的包含來自formula_10和formula_74二者的屬性的那些部分。注意formula_76、formula_77或formula_78可能為空，則下列規則成立：formula_96選擇和集合運算.選擇在差集、交集和並集運算元上是分配性的。使用下列三個規則在表示式樹中把壓入下面的集合運算中。注意，在差集和交集運算元的情況下有可能在變換之後只把選擇運算元應用於某一個運算元。在如下情況下這是有意義的，運算元之一很小，而計算選擇的花費超過了使用更小關係作為運算元的利益。選擇和投影.選擇與投影是交換性的，當且僅當在選擇條件中引用的欄位是在投影中的欄位的子集。在投影之前進行選擇可能有用，如果運算元是叉積或連線。在其他情況下，如果選擇條件計算相對破費，把選擇從投影中移動出來可能減少要測試的元組的數目。formula_100這裡的formula_101中的欄位formula_102投影.基本投影性質.投影是冪等性的，所以一系列投影等價於最外投影。formula_103這裡的formula_104投影和集合運算.投影在並集上是分配性的。重新命名.基本重新命名性質.對一個變數的連續的重新命名可以縮減為一個單一的重新命名。沒有公共變數的重新命名運算可以任意相互重新排序，這可以導致能縮減的重新命名毗連起來。重新命名和集合運算.重新命名關於差集、並集和交集是分配性的。