關(guān)系代數(shù)（數(shù)據(jù)庫(kù)）關(guān)系代數(shù)是一階邏輯的分支,是閉合于運(yùn)算下的關(guān)系的集合。運(yùn)算作用于一個(gè)或多個(gè)關(guān)系上來(lái)生成一個(gè)關(guān)系。關(guān)系代數(shù)是計(jì)算機(jī)科學(xué)的一部分。在純數(shù)學(xué)中的關(guān)系代數(shù)是有關(guān)于數(shù)理邏輯和集合論的代數(shù)結(jié)構(gòu)介紹關(guān)系代數(shù)在1970年E.F.Codd發(fā)表數(shù)據(jù)的關(guān)系模型之前很少受到注意°Codd曾是皮爾士選集編輯者ArthurWBurks的博士研究生。Codd提議這樣一種代數(shù)作為數(shù)據(jù)庫(kù)查詢語(yǔ)言的基礎(chǔ)。第一個(gè)基于Codd的代數(shù)的查詢語(yǔ)言是ISBL,許多作者都認(rèn)同這個(gè)先驅(qū)的工作展示了一個(gè)使Codd的想法成為有用語(yǔ)言的方式。商務(wù)系統(tǒng)12是追隨ISBL先例的短命工業(yè)級(jí)實(shí)力的關(guān)系DBMS。在1998年ChrisDate和HughDarwen提議了一種叫TutorialD的語(yǔ)言，意圖用于教學(xué)關(guān)系數(shù)據(jù)庫(kù)理論，它的查詢語(yǔ)言也吸取了ISBL的想法。Rel是TutorialD的一個(gè)實(shí)現(xiàn)。即使SQL的查詢語(yǔ)言也松散的基于了關(guān)系代數(shù)，盡管SQL中的操作數(shù)（表）不完全是關(guān)系，很多有用的關(guān)于關(guān)系代數(shù)的理論在SQL對(duì)應(yīng)者中不成立。因?yàn)殛P(guān)系被解釋為某個(gè)謂詞的處延，關(guān)系代數(shù)的每個(gè)運(yùn)算在謂詞演算中都有對(duì)應(yīng)者。例如，自然連接是邏輯AND（九）的對(duì)應(yīng)者。如果關(guān)系R和S分別表示謂詞P1和P2的外延，貝UR和S的自然連接（RXS）是表示謂詞p1Jp2的外延的關(guān)系。認(rèn)識(shí)到Codd的代數(shù)事實(shí)上關(guān)于二階邏輯不完備是很重要的。實(shí)現(xiàn)它會(huì)引起不可逾越的特定計(jì)算困難。為了克服這些困難，他限制操作數(shù)為有限關(guān)系，并提議了對(duì)否定（NOT）和析?。∣R）的有限支持。類似的限制在很多其他基于邏輯的計(jì)算機(jī)語(yǔ)言中也能見到。Codd定義術(shù)語(yǔ)關(guān)系完備性來(lái)稱呼一個(gè)語(yǔ)言除了他提議的限制之外關(guān)于二階邏輯是完備的。在實(shí)踐中這些限制對(duì)他的關(guān)系代數(shù)用于數(shù)據(jù)庫(kù)用途的適用性沒(méi)有不利作用。如同任何代數(shù)，一些運(yùn)算是原始的，而可以通過(guò)原始運(yùn)算來(lái)定義的另一些運(yùn)算是導(dǎo)出的。盡管邏輯中的AND,OR和NOT的選取，某種程度上是任意性的是眾所周知的，Codd對(duì)他的代數(shù)作了類似的任意選取。Codd的代數(shù)的六個(gè)原始運(yùn)算是“選擇”、“投影”、笛卡爾積（也叫做“叉積”或“交叉連接”）、并集、差集和“重命名”。（實(shí)際上，Codd忽略了重命名，而ISBL的發(fā)明者顯著的包括了它）。這六個(gè)運(yùn)算在省略其中任何一個(gè)都要損失表達(dá)能力的意義上是基本的。已經(jīng)依據(jù)這六個(gè)原始運(yùn)算定義了很多其他運(yùn)算。其

中最重要的是交集、除法和自然連接。事實(shí)上ISBL顯著的用自然連接替代了笛卡爾積，它是笛卡爾積的退化情況?？傊?，關(guān)系代數(shù)的運(yùn)算有與域關(guān)系演算或元組關(guān)系演算同樣的表達(dá)能力。但是出于前面介紹中給出的原因，關(guān)系代數(shù)有嚴(yán)格弱于沒(méi)有函數(shù)符號(hào)的一階謂詞演算的表達(dá)能力。關(guān)系代數(shù)實(shí)際上對(duì)應(yīng)于二階邏輯的子集，即沒(méi)有遞歸和否定的Horn子句。集合運(yùn)算盡管六個(gè)基本運(yùn)算中有三個(gè)取自集合論,在它們的關(guān)系代數(shù)對(duì)應(yīng)者中存在額外的約束：對(duì)于并集和差集，涉及到的兩個(gè)關(guān)系必須是“并集相容”的—就是說(shuō),兩個(gè)關(guān)系必須有同樣的屬性集合。因?yàn)榻患梢杂貌罴瘉?lái)定義,交集所涉及的兩個(gè)關(guān)系也必須是并集相容的。笛卡爾積定義得與集合論有所不同，這里的元組是平坦的、無(wú)子元組的。就是說(shuō)，不同于集合論，那里的n元組和m元組的笛卡爾積是2元組，而關(guān)系代數(shù)中它們的笛卡爾積把這個(gè)2元組展平為n+m元組。更形式的說(shuō)，RXS被定義為：R/S={r..S|r-R,srS}此外，對(duì)于要定義的笛卡爾積，涉及的兩個(gè)關(guān)系必須有不相交表頭—就是說(shuō),它們一定不能有公共屬性名字。投影（n）主條目投影（關(guān)系代數(shù)）投影是寫為的一元運(yùn)算，這里的心……r是屬性名字的集合。這種投影的結(jié)果定義為當(dāng)所有在J沖的元組被限制為集合51“廠的時(shí)候所獲得的集合選擇9）主條目選擇（關(guān)系代數(shù)）

的一元運(yùn)算，這里的是由正常選擇的一元運(yùn)算，這里的是由正常選擇中所允許的原子 足一 ■■和邏輯算子■■■'■..（與）、.--（或）和-（非）構(gòu)成的命題公式。這種選擇選出山中使「成立的所有元組。重命名（p）主條目重命名（關(guān)系代數(shù)）重命名是寫為'」比的一元運(yùn)算,這里的結(jié)果同一于山，除了在所有元組中的匚字段被重命名為“字段之外。它被簡(jiǎn)單的用來(lái)重命名關(guān)系的屬性或關(guān)系自身。自然連接3）Name部門雇員X部門DeptNaDeptNaManageNameEmpI■gDeptNaManagememerdmer財(cái)務(wù)財(cái)務(wù)GeorgeHarry3415財(cái)務(wù)George銷售HarrieName部門雇員X部門DeptNaDeptNaManageNameEmpI■gDeptNaManagememerdmer財(cái)務(wù)財(cái)務(wù)GeorgeHarry3415財(cái)務(wù)George銷售HarrieHarrie銷售Sally2241銷售財(cái)務(wù)ttCharle生產(chǎn)George3401財(cái)務(wù)George銷售―)sHarrie八.Harriet2202銷售t34152241雇員EmpIdHarrySallyGeorge3401Harrie2202t連接是關(guān)系復(fù)合的另一種術(shù)語(yǔ)；在范疇論中連接精確的是纖維積自然連接被確證為最重要的算法之一，因?yàn)樗倪壿婣ND的關(guān)系對(duì)應(yīng)者。仔細(xì)注意如果同一個(gè)變量在用AND連結(jié)的兩個(gè)謂詞中出現(xiàn)，則這個(gè)變量表示相同的事物而兩個(gè)出現(xiàn)必須總是由同一個(gè)值來(lái)代換。特別是，自然連接允許組合有外鍵關(guān)聯(lián)的關(guān)系。例如，在上述例子中，外鍵成立于從雇員.DeptName到部門.DeptName雇員和部門的自然連接組合了所有雇員和它們的部門。注意這能

工作因?yàn)橥怄I在相同名字的屬性之間保持。如果不是這樣，外鍵成立于從部門.manager到Emp.emp-number則我們必須在采用自然連接之前必須重命名這些列。這種自然連接有時(shí)叫做相等連接(參見0-連接)。更形式的說(shuō)，自然連接的語(yǔ)義定義為：Ri；iS={tI、..s:t-R,slS,fun(t〔..s)}這里的fun(r)是對(duì)于二元關(guān)系r為真的謂詞,當(dāng)且僅當(dāng)r是函數(shù)二元關(guān)系。通常要求R和S必須至少有一個(gè)公共屬性，但是如果省略了這個(gè)約束則在那種特殊情況下自然連接就完全變成上面定義的笛卡爾積。自然連接可以用Codd的原始運(yùn)算模擬如下。假定b,...,b是公共于R和STOC\o"1-5"\h\z1 m的公共屬性名字，a,...,a是唯一于R的屬性名字而c,...,c是唯一于S1 n 1 k的屬性名字。進(jìn)一步假定屬性名字d,...,d不在R和S二者中。第一步我們1 . m可以重命名S中的公共屬性名字：：S'：二p(...p(S)...)，接著我們_ d1/b1 dm/bm .、 、米用笛卡爾積并選擇要連接的元組：：T：二o(...o(RXS')...)，最- b1=d1 bm=dm后我們米用一個(gè)投影來(lái)去掉重命名的屬性：：U：=n (T)。a1,...,an,b1,...,bm,c1,...,cke-連接和相等連接考慮分別列出車模和船模的價(jià)格的表“車”和“船”。假設(shè)一個(gè)顧客要購(gòu)買一個(gè)車模和一個(gè)船模，但不想為船花費(fèi)比車更多的錢。在關(guān)系上的0-連接CarPrice三BoatPrice生成所有可能選項(xiàng)的一個(gè)表。車船CarModCarPri車船CarModCarPriBoatModBoatPrielceelceCarA20'000Boat110'000CarB30'000Boat240'000CarC50'000Boat360'000elceelceCarA20'000Boat110'000CarB30'000Boat110'000CarC50'000Boat110'000CarC50'000Boat240'000車I''I船( '' / '1CarModCarPriBoatModBoatPri如果我們要組合來(lái)自兩個(gè)關(guān)系的元組，而組合條件不是簡(jiǎn)單的共享屬性上的相等,則有一種更一般形式的連接算子才方便，這就是0-連接(或theta-連接)。0-連接是寫為“"丄或討"/的二元算子，這里的a和b是屬性名字，0是在集合{<,W,=,>,$}中的二元關(guān)系,v是值常量，而R和S是關(guān)系。這個(gè)運(yùn)算的結(jié)果由在R和S中滿足關(guān)系0的元素的所有組合構(gòu)成。只有

S和R的表頭是不相交的，即不包含公共屬性的情況下，0-連接的結(jié)果才是有定義的。這個(gè)運(yùn)算可以用基本運(yùn)算模擬如下：R*S=a(RXS)在算子0是等號(hào)算子(=)的時(shí)候這個(gè)連接也相等連接。但是要注意，支持自然連接和重命名的計(jì)算機(jī)語(yǔ)言可以不需要0-連接，因?yàn)樗梢酝ㄟ^(guò)對(duì)自然連接(在沒(méi)有公共屬性的時(shí)候的它退化為笛卡爾積)的選擇來(lái)完成。半連接(x)a)半連接是類似于自然連接的寫為RxS的連接，這里的R和S是關(guān)系。⑵半連接的結(jié)果只是在S中有在公共屬性名字上相等的元組所有的R中的元組。例如下面的例子是“雇員”和“部門”和它們的半連接的表：雇員部門雇員x部門NameEmpIDeptNamDeptNamManageNameEmpIDeptNamdeerdeHarry3415財(cái)務(wù)銷售HarrieSally2241銷售Sally2241銷售tHarrie2202生產(chǎn)George3401財(cái)務(wù)生產(chǎn)CharletHarrie生產(chǎn)st2202更形式的說(shuō)半連接的語(yǔ)義定義如下：R(xS={t:t-R,slS,fun(t■.S)}這里的fun(r)定義同于自然連接。半連接可以被使用自然連接模擬如下。假定a,...,a是R的屬性名字，則:1 nR(xS= (RMS)al,..,an因?yàn)槲覀兛梢酝ㄟ^(guò)基本運(yùn)算模擬自然連接因此也就可以模擬半連接。反連接(>)

反連接是類似于自然連接的寫為R>S的連接，這里的R和S是關(guān)系。［3反連接的結(jié)果是在S中沒(méi)有在公共屬性名字上相等的元組的R中的那些元組。例如“雇員”和“部門”和它們的反連接的表：雇員部門雇員>部門NameEmpIDeptNamDeptNamManageNameEmpIDeptNamdeerdeHarry3415財(cái)務(wù)銷售HarrietHarry3415財(cái)務(wù)Sally2241銷售生產(chǎn)CharlesGeorg3401財(cái)務(wù)George3401財(cái)務(wù)eHarrie銷售t2202反連接形式定義為：Ri''S={t:t：〒R??「.一J|s：〒S:fun(t〔..s)}或R:-S={t:t-R，S中沒(méi)有s滿足fun(tI..s)}這里的fun(r)定義同于自然連接。反連接還可以定義為半連接的補(bǔ)集：R:.S=R-R(XS為此反連接有時(shí)叫做反半連接，反連接算子有時(shí)寫為其上有橫杠的半連接符號(hào)除法(-)除法是寫為R三S的二元關(guān)系。其結(jié)果由R中元組到唯一于R的屬性名字(就是說(shuō)只在R表頭中而不在S表頭中的屬性)的限制構(gòu)成，并且它們與S中的元組的所有組合都存在于R中。例如下面的“完成”和“DB項(xiàng)目”和它們的除法：完成DB項(xiàng)目完成三完成DB項(xiàng)目完成三DB項(xiàng)目StudentTaskTaskStudentFredDatabase1Database1FredFredDatabase2Database2SaraFredCompiler1EugeneDatabase1EugeneCompiler1SaraDatabase1SaraDatabase2如果“DB項(xiàng)目”包含數(shù)據(jù)庫(kù)項(xiàng)目的所有任務(wù)，則這個(gè)除法的結(jié)果精確的包含已經(jīng)完成了數(shù)據(jù)庫(kù)項(xiàng)目的所有學(xué)生。更形式的說(shuō)除法的語(yǔ)義定義如下：R三S={t[a,...,a]:t匚Rr.ks匚S((t[a,...,a].一is)匚R)}TOC\o"1-5"\h\z1 n 1 n這里的{a,...,a}是唯一于R的屬性名字的集合而t[a,...,a]是t到這1 n 1 n個(gè)集合的限制。通常要求在S的表頭中的屬性名字是R的表頭的屬性名字的子集，否則運(yùn)算的結(jié)果永遠(yuǎn)為空。除法可以用基本運(yùn)算模擬如下。我們假定a,...,a是唯一于R的屬性名字而1 nb,...,b是S的屬性名字。在第一步中我們投影R于它的唯一屬性上，并接1著構(gòu)造它們與S的元組的所有組合：T：=n (R)XSa1,...,an在上面例子中，T將是表示所有學(xué)生(因?yàn)镾tudent是“完成”表的唯一鍵/屬性)與所有給定任務(wù)的組合的表。所以Eugene在T中將有兩行Eugene->Database1和Eugene->Database2。在下個(gè)步驟中，我們從這個(gè)關(guān)系中減去R:U:=T-R注意在U的都是R中沒(méi)有出現(xiàn)的可能的組合。所以如果現(xiàn)在做到唯一于R的屬性名字的投影，則我們有了R中元組的限制，它們與S的元組的所有組合未都出現(xiàn)在R中：V:=n (U)a1,...,an剩下的就是投影R到唯一于它的屬性名字并減去V:

W:=n1 (R)-Va1,...,an外連接主條目：外連接盡管連接(或內(nèi)連接)的結(jié)果是由組合兩個(gè)操作數(shù)的匹配元組而形成的元組組成，外連接由這些元組加上通過(guò)向一個(gè)操作數(shù)的未匹配元組擴(kuò)展上另一個(gè)操作數(shù)的每個(gè)屬性的“填充”值而形成的元組組成。本節(jié)定義的運(yùn)算假定“空”值3的存在性，我們不定義它并把它用做填充值。不應(yīng)當(dāng)假定它為數(shù)據(jù)庫(kù)語(yǔ)言SQL所定義的NULL，也不應(yīng)該假定3為一個(gè)標(biāo)號(hào)而非一個(gè)值，也不應(yīng)該假定它介入了有爭(zhēng)議的三值邏輯。定義三個(gè)外連接：左外連接、右外連接和全外連接。(有時(shí)省略“外”字)左外連接佃)左外連接寫成R惻S，其中R與S為關(guān)系。［4］左外連接的結(jié)果包含R中所有元組，對(duì)每個(gè)元組，若在S中有在公共屬性名字上相等的元組，則正常連接，若在S中沒(méi)有在公共屬性名字上相等的元組，則依舊保留此元組，并將對(duì)應(yīng)其他列設(shè)為NULL。(ReS)U f嗎…沖(ReS))x{3…a)})右外連接佃)右外連接寫成R惻S，其中R與S為關(guān)系。［5］右外連接的結(jié)果包含S中所有元組，對(duì)每個(gè)元組，若在R中有在公共屬性名字上相等的元組，則正常連接，若在R中沒(méi)有在公共屬性名字上相等的元組，則依舊保留此元組，并將對(duì)應(yīng)其他列設(shè)為NULL?！鰞碨)U((S—7T叫叫宀(ExS))x{3…w)})全外連接他)全外連接寫成R惻S，其中R與S為關(guān)系。［6］全外連接的結(jié)果包含R與S中所有元組，對(duì)每個(gè)元組，若在另一關(guān)系上中有在公共屬性名字上相等的元組，則正常連接，若在另一關(guān)系上中沒(méi)有在公共屬性名字上相等的元組，則依舊保留此元組，并將對(duì)應(yīng)其他列設(shè)為NULL。

R惻S=（R惻S）U（R惻S）域計(jì)算的運(yùn)算聚集運(yùn)算多數(shù)數(shù)據(jù)庫(kù)包括五個(gè)聚集函數(shù)。這些運(yùn)算是Sum、Count、Average、Maximum和Minimum。在關(guān)系代數(shù)中被寫為 G (關(guān)系)。必須指定要用的函數(shù)，而表達(dá)式是可選的。假定有一個(gè)叫Account的表有兩列，分別是Branch_Name和Balance，并希望找到有最高結(jié)余的分部的名字，我們可以寫G(Account)。要找到最高余額我們可以簡(jiǎn)單的寫B(tài)ranch_NameMax(Balance)G (Account)。Max(Balance)關(guān)系代數(shù)的限制盡管關(guān)系代數(shù)對(duì)于大多數(shù)用途都足夠強(qiáng)大了，有一些在關(guān)系上的簡(jiǎn)單而自然的運(yùn)算不能用關(guān)系代數(shù)表達(dá)。二元關(guān)系的傳遞閉包就是其中之一。給定一個(gè)域D，設(shè)二元關(guān)系R是DxD的子集。R的傳遞閉包R+是包含R的滿足如下條件的DxD的子集：PxVyJz((x,y)lR+Q(y,z)lR+—(x,z)匚R+)可以證明沒(méi)有關(guān)系代數(shù)表達(dá)式E(R)接受R作為變量參數(shù)而生成R+。證明基于如下事實(shí)，給定一個(gè)關(guān)系表達(dá)式E,對(duì)它聲稱E(R)=R+,這里的R是變量，我們總是可以找到R的一個(gè)實(shí)例r(和一個(gè)對(duì)應(yīng)的域d)使得E(r)工r+o銅有用于查詢優(yōu)化的代數(shù)性質(zhì)查詢可以表示為一個(gè)樹，這里的?內(nèi)部節(jié)點(diǎn)是算子，?葉子是關(guān)系，?子樹是子表達(dá)式主要目標(biāo)是把表達(dá)式樹變換成等價(jià)的表達(dá)式樹，使得在樹中的子表達(dá)式生成的關(guān)系的平均大小比優(yōu)化前更小。次要目標(biāo)是在一個(gè)單一查詢中，或在要同時(shí)求值多于一個(gè)查詢的時(shí)候的所有這些查詢中，嘗試形成公共子表達(dá)式。在次要目標(biāo)背后的原理是計(jì)算公共子表達(dá)式一次就夠了，其結(jié)果可以用于包含這個(gè)子表達(dá)式的所有查詢中。我們提出可用于這種變換的一組規(guī)則。

選擇關(guān)于選擇運(yùn)算的規(guī)則在查詢優(yōu)化中扮演了最重要的角色。選擇是可非常有效的減少在它的操作數(shù)中的行數(shù)的運(yùn)算，所以如果我們?cè)O(shè)法把在表達(dá)式樹中選擇向著葉子方向移動(dòng)，（子表達(dá)式產(chǎn)生的）內(nèi)部關(guān)系的大小將被縮小?；具x擇性質(zhì)選擇是幕等性的（多次應(yīng)用同一個(gè)選擇有同樣效果）,和交換性的（應(yīng)用選擇的次序在最終結(jié)果中沒(méi)有影響）。rJ仁二廠廠事出；=2廠分解有復(fù)雜條件的選擇其條件是更簡(jiǎn)單條件的合取的選擇等價(jià)于針對(duì)這些單獨(dú)條件的一序列選擇，而其條件是析取的選擇等價(jià)于選擇的并集?？梢允褂眠@些恒等式來(lái)合并多個(gè)選擇為更少的需要求值的選擇，或分解它們使得其成員選擇可以被移動(dòng)或單獨(dú)優(yōu)化。r川二廠心"i圧；二圧；'7.'.仕二廠JJd廠;丿￡；選擇和叉積叉積對(duì)于計(jì)算是最耗費(fèi)的算子。如果輸入關(guān)系有工和 行，結(jié)果將包含行。所以在應(yīng)用叉積算子之前盡最大可能減少兩個(gè)操作數(shù)的大小是非常重要的。這可以有效的完成，如果叉積跟隨著選擇算子，比如（山X）。這是最合適考慮連接定義的情況。如果叉積不跟隨著選擇運(yùn)算，我們可以嘗試使用其他規(guī)則從表達(dá)式樹更高層壓下一個(gè)選擇。在上節(jié)情況下我們使用對(duì)復(fù)雜條件的分解規(guī)則把條件.1分解為條件療、｛‘和，使得.1= ，而打只包含來(lái)自的屬性，（■只包含來(lái)自「的屬性，門包含.1的包含來(lái)自山和廠二者的屬性的那些部分。注意庁、、‘或可能為空，則下列規(guī)則成立：璟RXF)=勵(lì)心XP)= X%(P))

選擇和集合運(yùn)算選擇在差集、交集和并集算子上是分配性的。使用下列三個(gè)規(guī)則在表達(dá)式樹中把壓入下面的集合運(yùn)算中。注意，在差集和交集算子的情況下有可能在變換之后只把選擇算子應(yīng)用于某一個(gè)操作數(shù)。在如下情況下這是有意義的，操作數(shù)之一很小,而計(jì)算選擇的花費(fèi)超過(guò)了使用更小關(guān)系作為操作數(shù)的利益。m =r訂兒/'：="IL3.選擇和投影選擇與投影是交換性的，當(dāng)且僅當(dāng)在選擇條件中引用的字段是在投影中的字段的子集。在投影之前進(jìn)行選擇可能有用，如果操作數(shù)是叉積或連接。在其他情況下，如果選擇條件計(jì)算相對(duì)破費(fèi)，把選擇從投影中移動(dòng)出來(lái)可能減少要測(cè)試的元組的數(shù)目(因?yàn)橥队翱赡艹陕暩俚脑M，因?yàn)樗宄捎谌∠侄螌?dǎo)