翻譯大型共享數(shù)據(jù)庫的數(shù)據(jù)關(guān)系模型(精選.)

1、大型共享數(shù)據(jù)庫的數(shù)據(jù)關(guān)系模型E.F.CoddIBM Research Laboratory,SanJose,California未來的數(shù)據(jù)庫使用者一定是和數(shù)據(jù)在機(jī)器中的存儲(chǔ)（即數(shù)據(jù)庫的內(nèi)部模式）相隔離的。而通過提示服務(wù)來提供信息是一個(gè)不太令人滿意的解決方法。當(dāng)數(shù)據(jù)的內(nèi)部模式表示發(fā)生改變， 甚至數(shù)據(jù)內(nèi)部表示的多個(gè)方面發(fā)生改變時(shí)，終端用戶和大多數(shù)應(yīng)用程序的活動(dòng)都不會(huì)受到影響。因此， 查詢、 更新和報(bào)告存儲(chǔ)信息類型的自然增長和變動(dòng)都需要在數(shù)據(jù)表示中表現(xiàn)出來?，F(xiàn)存的不可推斷的、格式化的數(shù)據(jù)系統(tǒng)給用戶提供了樹結(jié)構(gòu)的文件或者更一般的網(wǎng)格模式的數(shù)據(jù)。本文在第一部分討論這些模式的不足之處。并且會(huì)介紹一種基于n

2、 元組關(guān)系的模式， 一種數(shù)據(jù)庫關(guān)系的正式形式和通用數(shù)據(jù)子句的概念。第二部分將討論一些關(guān)系的操作（不是邏輯層面的），并且把這些操作應(yīng)用于用戶模式上解決冗余和一致性問題。1 關(guān)系模式和一般模式1.1 簡介這篇文章是關(guān)于系統(tǒng)的基本關(guān)系原理的應(yīng)用，這個(gè)原理提供了共享大型格式化數(shù)據(jù)庫的方法。除了Childs1的文章有介紹外，用于數(shù)據(jù)庫系統(tǒng)的關(guān)系的主要應(yīng)用還表現(xiàn)在演繹推理型的問-答系統(tǒng)中。Levein 和 Maron2 提供了大量關(guān)于這個(gè)領(lǐng)域的參考資料。 相比之下，這里要解決的問題是一些數(shù)據(jù)獨(dú)立性的問題 應(yīng)用程序和終端活動(dòng)之于數(shù)據(jù)類型增長和數(shù)據(jù)表示變動(dòng)的獨(dú)立性，而數(shù)據(jù)一致性問題即使在非演繹推理型系統(tǒng)中也是

3、很棘手的。在目前流行的非推論性系統(tǒng)中，第一部分要介紹的數(shù)據(jù)的關(guān)系視圖（或叫做模式）在一些方面似乎優(yōu)于圖模式和網(wǎng)格模式3,4。這種模式提供了一種根據(jù)數(shù)據(jù)的自然結(jié)構(gòu)來描述描述數(shù)據(jù)的方式 也就是說，不用為了數(shù)據(jù)的機(jī)器表示而添加其他的將結(jié)構(gòu)。因此，這種模式為高水準(zhǔn)的數(shù)據(jù)語言提供了基礎(chǔ)，而這種數(shù)據(jù)語言機(jī)制一方面可以達(dá)到最大化程序之間的獨(dú)立性，另一方面也可以最大化數(shù)據(jù)的機(jī)器表示和組織之間的獨(dú)立性。關(guān)系模式更高一級(jí)的優(yōu)勢(shì)在于它構(gòu)成了關(guān)系處理可導(dǎo)性、冗余性和一致性的堅(jiān)固基礎(chǔ) 這些將在第二部分討論。另一方面，網(wǎng)絡(luò)模型產(chǎn)生了一些混淆，尤其是把連接的源誤作為關(guān)系的源（見第二部分“連接陷阱”）最后， 關(guān)系視圖允許對(duì)目

4、前格式化數(shù)據(jù)系統(tǒng)的范圍和邏輯限制的更清晰的估算，并且有在單獨(dú)的系統(tǒng)內(nèi)競爭數(shù)據(jù)表示方式的優(yōu)點(diǎn)（從邏輯的觀點(diǎn)）。 更清楚的這個(gè)觀點(diǎn)的示例會(huì)在本文中的不同部分中被闡釋。但是支持關(guān)系模式的系統(tǒng)實(shí)現(xiàn)不會(huì)討論。1.2 目前系統(tǒng)的數(shù)據(jù)相關(guān)性最近發(fā)展的信息系統(tǒng)中數(shù)據(jù)描述表的提供是向數(shù)據(jù)獨(dú)立性目標(biāo)5,6,7 靠近的重要提高。這些表可以使改變數(shù)據(jù)庫中數(shù)據(jù)表示的某些特征變得更容易些。但是，許多數(shù)據(jù)表示特征可以在不邏輯地削弱一些應(yīng)用程序的情況下被改變的功能仍受到相當(dāng)?shù)南拗?。更進(jìn)一步，與用戶交互的數(shù)據(jù)模式仍然有一些散亂的代表性特征，特別是關(guān)于數(shù)據(jù)收集的描述（如個(gè)人名目）。 三個(gè)仍然需要提高的數(shù)據(jù)獨(dú)立性的主要類型是：排序

5、依賴，索引依賴和存取路徑的依賴。在一些系統(tǒng)中這些依賴之間并不是明確分隔的。1.2.1 順序依賴。數(shù)據(jù)庫中的數(shù)據(jù)元素可以有很多種存儲(chǔ)方式，一些是不考慮順序的，一些是允許一個(gè)元素只參與一個(gè)排序，而另外一些允許每個(gè)元素參與多個(gè)排序。 現(xiàn)在讓我們來看看要求或允許數(shù)據(jù)元素存儲(chǔ)在至少一個(gè)總排序的現(xiàn)存系統(tǒng)， 而這種總體排序是與硬件決定的排序地址密切相關(guān)的。這種系統(tǒng)通常允許應(yīng)用程序自己假定文件記錄的表示順序與其在磁盤上的存儲(chǔ)順序是相同的（或者說是存儲(chǔ)排序的子目）。這些運(yùn)用文件存儲(chǔ)順序有利條件的應(yīng)用程序， 如果由于某些原因而變得需要用一個(gè)新排序替換這種順序時(shí)，很可能不能正確運(yùn)行。以指針方式實(shí)現(xiàn)的存儲(chǔ)排序也有相似

6、的問題。我們沒有必要挑選出任何一個(gè)系統(tǒng)作為例子，因?yàn)楝F(xiàn)在上市的所有著名的信息系統(tǒng)在清楚區(qū)別表示順序和存儲(chǔ)順序兩方面都是失敗的。重要的實(shí)現(xiàn)問題必須得到解決來提供這種獨(dú)立性。1.2.2 索引依賴。格式化數(shù)據(jù)的上下文聯(lián)系中，索引通常被看成數(shù)據(jù)表示的一個(gè)純粹的效能導(dǎo)向組件。它傾向于提高對(duì)查詢和更新的響應(yīng)，同時(shí)減慢了對(duì)插入和刪除的響應(yīng)。從信息的觀點(diǎn)來看，索引是數(shù)據(jù)表示的冗余構(gòu)成成分。如果一個(gè)系統(tǒng)王全用索引，并且如果它在變化活動(dòng)形式的數(shù)據(jù)庫環(huán)境中能夠表現(xiàn)的很好，那么不時(shí)地產(chǎn)生和銷毀索引的能力可能是必須的。那么問題產(chǎn)生了：應(yīng)用程序和終端活動(dòng)在索引項(xiàng)來去的時(shí)候仍然能夠不受影響嗎？目前格式化數(shù)據(jù)系統(tǒng)采用很不相同

7、的方法來進(jìn)行索引。TDMS7 無條件地提供了所有屬性上的索引。IMS5 目前發(fā)布的版本為用戶提供了為每一文件選擇的權(quán)利：是完全沒有索引（層次序列的組織）和只有主鍵索引（層次化索引序列組織）之間的選擇。沒有一種會(huì)使用戶的應(yīng)用邏輯依賴于無條件提供的索引的存在。但是，IDS8 允許文件設(shè)計(jì)者選擇用于索引的屬性和指定用于與索引通過外加鏈的方式組合成文件結(jié)構(gòu)的屬性。運(yùn)用索引鏈性能的優(yōu)勢(shì)的應(yīng)用程序必須通過名字來引用這些鏈。如果這些鏈后來被刪除，那么這些程序就無法正確運(yùn)行。1.2.3 存取路徑依賴。許多現(xiàn)存格式化數(shù)據(jù)系統(tǒng)為用戶提供了樹結(jié)構(gòu)的文件或者更一般的數(shù)據(jù)網(wǎng)絡(luò)模式。為和這類系統(tǒng)共同工作而發(fā)展的應(yīng)用程序，

8、在樹或網(wǎng)格的結(jié)構(gòu)改變時(shí)，往往會(huì)在邏輯層受到削弱。一個(gè)簡單的例子如下。設(shè)想數(shù)據(jù)庫包含關(guān)于部件和工程的信息。對(duì)于每一個(gè)部件，其部件號(hào)碼、部件名字、部件描述、在手的數(shù)量和訂單上的數(shù)量的信息都被記錄。對(duì)于每一個(gè)工程，其工程編號(hào)、工程名字和工程描述信息被記錄。無論什么時(shí)候，一個(gè)工程要用特定部件時(shí)，用于這個(gè)工程的那種部件的數(shù)量也會(huì)被記錄。假如系統(tǒng)要求用戶或者文件創(chuàng)作者根據(jù)樹結(jié)構(gòu)聲明或者定義數(shù)據(jù)。那么， 任一層次結(jié)構(gòu)都可以用到如上提到的信息上（見結(jié)構(gòu)1 5） 。Stnieture L Pr&jectB 區(qū)uh倒收linat里 to FartsFM/科ddiF FART purt fp&rt

9、hameputd住工程riptinnqu -i j H ty on-hH nd qtiatjti ty-on-orderPROTECT project fproject nam» project description Quantity eommittedS-ttucture 2. Fut出 Stibarditifltjt to ProjectsP?<理褊*F PROJECT project #project nanic project dnriptinnPARTpart，pajt name ptul dnEGripliuu quantity -un-liaiid quanti

10、ty -on-rd?r quantity gmmit詁dStructure 亂 Farta aii<i Projects as PeersCommitmert ItelaLiohatiip Sub ardi naie to ProjectsF0Jfd*F PART pWpwrt riatne p?irt rificription tjriflntity-<H!i'hand quantity yQ PROJECT proieet §project nsmeprojnet df?*ci-ipticiiPARTpartq.LL!iDU ly conmiittedStrq

11、ctiig 4. Parts and Prajecls as Pc&raCiLiuiiLjiienli Rri&llyuHhip &ubuidi iiiiltf to P&rlaIV*cfnwftfjFul4tFPARTpart /part M&gpt山口 qcisntUy nn-hand qu&Hl.iLy -on-<jrderPROJECT project $Hujintitv eonruitvcdG PROJECT projefft #prujccL 口耳in已 project d-rjptionSiruQUUre 5. Partst

12、 Projects, and KaJuLjoiisJiLp 弁 Peers FiTeJtpvswiFFARTpul /P&Tt IhfiLne part 向呂crEpii 由i qufUitity-on-haud quaMity-on-order G PROJECTp皿#project niine j rojdec ripticmH COMMIT put # pro沁t d quantity committed現(xiàn)在考慮打印用于名為“alpha的'工程每個(gè)部件的編號(hào)、部件名和數(shù)目。不考慮可用于面向樹的信息系統(tǒng)可以用于解決這個(gè)問題，我們可以得到以下的發(fā)現(xiàn)。如果程序P是開發(fā)用于解決這

13、個(gè)問題（假設(shè)結(jié)構(gòu)是上面五種結(jié)構(gòu)中的一 種），也就是說 P不會(huì)檢測哪一種結(jié)構(gòu)對(duì)他來說有效，然而這樣的結(jié)果是P至少在其中三個(gè)結(jié)構(gòu)上是失敗的。更具體地，如果P對(duì)結(jié)構(gòu)5行之有效，那么在其他結(jié)構(gòu)上就會(huì)失敗；如果P對(duì)結(jié)構(gòu)3或4行之有效，那么它至少會(huì)在結(jié)構(gòu)1,2,5上是失敗的；如果 P對(duì)結(jié)構(gòu)1或2行之有效，那么它至少會(huì)在結(jié) 構(gòu)3,4,5上是是小的。對(duì)于每一種情況的原因都很簡單。在沒有經(jīng)過檢測來 決定哪種結(jié)構(gòu)是有效的情況下，P會(huì)失敗是因?yàn)樗噲D引用一個(gè)不存在的文件（現(xiàn)可用的系統(tǒng)把這種情況視為error）或者是它沒有引用包含它必需信息的文件。有疑問的讀者應(yīng)該找一些樣例程序來理解這個(gè)簡單的問題。 由于在一般情況下

14、，開發(fā)可以檢測系統(tǒng)允許的所有樹結(jié)構(gòu)的應(yīng)用程序是不實(shí) 際的，而且這種程序在結(jié)構(gòu)需要改變時(shí)也會(huì)失敗。 為用戶提供網(wǎng)格數(shù)據(jù)模式的系統(tǒng)也會(huì)遇到相似的問題。在樹和網(wǎng)格兩種情形下，用戶（或者是用戶的程序）都被要求采用用戶數(shù)據(jù)存取路徑的集合。這 些路徑是否與存儲(chǔ)表示的指針定義的路徑有較近通信是沒有影響的，而在 IDS中這種通信時(shí)極其簡單的，但在TDMS中就正好相反了。不考慮存儲(chǔ)表示來看這種問題，結(jié)果就是，終端活動(dòng)和程序變得依賴于用戶存取路徑的連 續(xù)存在性。對(duì)于這個(gè)問題的一個(gè)解決方案就是采用如下策略：一旦用戶存取路徑被定義了，那么除非所有應(yīng)用這個(gè)路徑的所有程序都廢棄了（finish 了），否則這個(gè)路徑就不會(huì)過

15、時(shí)。由于在團(tuán)體總體模式的數(shù)據(jù)庫用戶的存取路徑的數(shù)量最終 可能變得過大，因此這種策略是不實(shí)際的。1.3 數(shù)據(jù)的關(guān)系視圖關(guān)系這個(gè)詞在這里使用的是其被廣泛認(rèn)可的數(shù)學(xué)意義。給定集合S1,S2,S記些集合沒有必要一定是不同的），如果R是一個(gè)滿足如下條件的n元組集合：其每個(gè)元素的第一個(gè)元素來自S1,第二個(gè)元素來自集合S2,以此類推，那么 R就是這n個(gè)集合（S1,S2,Sn上的一個(gè)關(guān)系。我們用 Sj來表示R的第j個(gè)域。正如上面所 定義，R被稱作是n級(jí)的。1級(jí)的關(guān)系通常叫做一元關(guān)系，2級(jí)的被叫做二元關(guān)系，3級(jí)的被叫做三元關(guān)系，而n級(jí)的叫n元關(guān)系。（更簡單地說，R是S1,S2,這nn個(gè)集合的笛卡爾乘積的一個(gè)子集

16、） 說明一下，我們將頻繁地使用關(guān)系的數(shù)組表示，但是必須清楚的是這個(gè)特定表示并 不是用于解釋關(guān)系視圖必須的部分。用于表示 n元關(guān)R的數(shù)組有如下特征：（1） 每一行代表 R的一個(gè)n元組（2） 行的排列順序是無關(guān)緊要的（3） 所有行都是不相同的（4） 列的順序是有意義的 一一列應(yīng)該符合 R定義時(shí)的域的順序 S1,s2,Sn但是注意，排序的域和無序的域下標(biāo)之間的關(guān)系）（5） 每個(gè)列的意義部分是由命名相應(yīng)域來傳達(dá)的圖1中的例子展示了一個(gè)叫做supply 4級(jí)的關(guān)系，這個(gè)關(guān)系顯示的是特定工程的特定供應(yīng)者的特定數(shù)量的零件發(fā)貨過程。supplier112purlproject5575quantitif)172

17、3Fig. 1.A relation of degree 4有人可能會(huì)問：如果列由相應(yīng)域的名字來標(biāo)識(shí)，呢？正如圖2中例子顯示的一樣，兩列可以有相同的頭 于這個(gè)關(guān)系他們有不同的含義。這里描述的關(guān)系叫做圖1那么為什么列的順序會(huì)有影響（表示同樣的域），但是對(duì)component 。 它是一個(gè)三元關(guān)系，其中前兩個(gè)域叫做 part而第三個(gè)域叫做 quantity。 Component （x, y, z） 的意思就是部件x部件y的直接構(gòu)成成分（或者子部件），而需要z個(gè)白X x部件來 組成一個(gè)的y部件。這個(gè)關(guān)系在零件擴(kuò)大問題中有重要作用。part212F0.2, A. relfltir»n wi&l

18、t;h two id«nJ irsl Hnmairift一個(gè)引人注目事實(shí)是， 一些現(xiàn)存的信息系統(tǒng) （主要是基于樹結(jié)構(gòu)文件組織） 不 能夠?yàn)橛袃蓚€(gè)或兩個(gè)以上的相同域的關(guān)系提供有效地?cái)?shù)據(jù)表示。IMS/3605的目前版本就是這種系統(tǒng)的一個(gè)實(shí)例。一個(gè)數(shù)據(jù)庫中的總體數(shù)據(jù)可以看做一個(gè)隨著時(shí)間變化的關(guān)系的集合。這些種類的關(guān)系有各種各樣的級(jí)（或度）。隨著時(shí)間的前進(jìn)，每個(gè) n元關(guān)系都可能經(jīng)歷插入 另外的n元組，刪除現(xiàn)存的 n元組和改變現(xiàn)存任意 n元組的組成部分的操作。但是，在很多商業(yè)、政府和科學(xué)數(shù)據(jù)庫中，一些關(guān)系的度（或作級(jí)別）是相當(dāng) 高的（30級(jí)的關(guān)系也是很常見的）。用戶通常不能記住任何關(guān)系的所有域

19、的順序（例如，關(guān)系supply中定序的提供者、零件、工程和數(shù)量）。因此，我們提出用戶不必處理域排序的關(guān)系，而處理與其非排序域的有同樣效果的關(guān)系的方法。為了達(dá)到這個(gè)目的，關(guān)系中的域必須是在不采用位置時(shí)唯一可確認(rèn)的，至少在某個(gè)給定的關(guān)系中是這樣的。因此，在有兩個(gè)或更多相同域的地方，我們要求對(duì)每一種情況下域名都是合格的不同的角色名（role name）,這些角色名用于識(shí)別給定的關(guān)系中的域所 扮演的角色。例如，在圖 2的component關(guān)系中，第一個(gè)域 part可以用合格角色名sub指示，而第二個(gè)用super,以便用戶能夠處理component關(guān)系和它的域 sub.partsuper.part,qu

20、antity 而不用考慮這些域之間的任何排序?？傊?， 提出多數(shù)用戶應(yīng)該與由隨時(shí)間變化的聯(lián)系集合（而不是關(guān)系）組成的數(shù)據(jù)的關(guān)系模式交互。每個(gè)用戶不必知道除了關(guān)系的名字和其相應(yīng)的域的名字外的其它更多信息（只要有需要就可以采用角色資格）。甚至信息可以是系統(tǒng)（具有安全和隱私約束）根據(jù)用戶的請(qǐng)求以菜單形式提供的。數(shù)據(jù)庫關(guān)系模型的建立通常還有其他很多可供選擇的方法。為了討論更好的方式（或標(biāo)準(zhǔn)形式），我們必須引入另外幾個(gè)概念（活動(dòng)域、主碼、外碼、非單一域）并建立一些與目前在信息系統(tǒng)編程中使用的術(shù)語的鏈接。在本文后面的部分，我們將不再煩惱地去區(qū)別關(guān)系（relation ）和聯(lián)系（relationship ）

21、，而在需要顯示他們不同之處的地方我們會(huì)顯示地指出。下面考慮這樣一個(gè)數(shù)據(jù)庫實(shí)例，該數(shù)據(jù)庫包含關(guān)于部件，工程和供應(yīng)者的一系列關(guān)系。一個(gè)叫part 的關(guān)系被定義在以下的域上：1 ）部件編號(hào)（partnumber ）2 ）部件名稱（partname ）3 ）部件顏色（partcol or）4 ）部件重量（partweight ）5 ）在手的數(shù)量（quantity on hand ）6 ）預(yù)訂的數(shù)量（quantity on order ）可能還有其他的域。事實(shí)上，每個(gè)這樣的域都是一池?cái)?shù)值，這些數(shù)值中的一些或全部可以在任一瞬時(shí)在數(shù)據(jù)庫中表示出來。可以想象，在某些瞬間，所有部件顏色都被顯示出來，但是難以做到

22、的是把所有可能存在的部件的重量、部件名字和部件編號(hào)都顯示出來。我們稱在某個(gè)時(shí)刻表現(xiàn)出來的值的集合為在那個(gè)時(shí)刻的活動(dòng)域（ active domain ） 。通常， 一個(gè)給定關(guān)系的一個(gè)域（或者域的組合）有一組唯一識(shí)別該關(guān)系的每一元素（ n 元組）的值。這樣的一個(gè)域（或組合）被叫做主碼（primary key ） 。在上面的例子中，部件號(hào)可能是一個(gè)主碼，而部件顏色可能就不是了。主碼是非冗余的，如果他滿足它是一個(gè)簡單域（非組合的）或者一個(gè)組合，而對(duì)于組合的情況，在唯一識(shí)別每一元素時(shí)參與到這個(gè)組合中的簡單域沒有一個(gè)是多余的（也就是組合中的所有的簡單域共同構(gòu)成一個(gè)唯一識(shí)別關(guān)系元素的碼）。一個(gè)關(guān)系可以有多個(gè)

23、非冗余的主碼。 如果上面所說的部件的名字都互不相同，那么就成了這種情況的一個(gè)實(shí)例。無論什么時(shí)候，只要一個(gè)關(guān)系有兩個(gè)或者更多非冗的主碼，它們中的任意一個(gè)都可以選作這個(gè)關(guān)系的主碼。一個(gè)普遍的要求就是，關(guān)系當(dāng)中的元素交叉引用同一關(guān)系的其他元素或者引用一個(gè)不同關(guān)系的元素。碼提供了一種用于表示這種交叉引用的面向用戶的方式（但不是唯一的方式）。如果一個(gè)域（或者域組合）不是關(guān)系R 的主碼，但是它的元素是某個(gè)關(guān)系S 的主碼值（排除S 和 R 是同一關(guān)系的可能），那么我們就把關(guān)系R 的這個(gè)域（或者域組合）叫做外碼。在圖1supply 關(guān)系中，supplier 、 part、 project是主碼，而這三個(gè)域中每

24、一個(gè)都被單獨(dú)看作是一個(gè)外碼。在前面的工作中已經(jīng)顯現(xiàn)出一個(gè)很強(qiáng)的趨勢(shì)，即把一個(gè)數(shù)據(jù)庫中的數(shù)據(jù)看成由兩個(gè)部分組成，一個(gè)部分由實(shí)體描述組成（如supplier 的描述） ，而另一個(gè)部分由不同實(shí)體間或者實(shí)體類型間的關(guān)系組成（如 supply 關(guān)系） 。 當(dāng)一個(gè)關(guān)系有任何其他關(guān)系的外碼時(shí)，要維持這種區(qū)別是困難的。在用戶的關(guān)系模式中，做出這樣的區(qū)別似乎是沒有益處的（但是，當(dāng)把關(guān)系概念用于用戶聯(lián)系集的機(jī)器表示時(shí)，這種區(qū)分可能有些益處）。到目前為止，我們已經(jīng)討論了一系列定義在簡單域上的關(guān)系的例子，而那些簡單域的元素是原子的（非組合的）值。非原子值會(huì)在關(guān)系框架中討論。因此，一些 域可以把關(guān)系當(dāng)做元素。相應(yīng)地，這

25、些關(guān)系可以被定義在非簡單域等等。例如，關(guān)系employee定義的其中一個(gè)域可以是salary history （薪水歷史）。Salary history域中的一個(gè)元素是一個(gè)定義在date域和salary域上的二元關(guān)系。 Salary history域就是這種二元關(guān)系的一個(gè)集合。在數(shù)據(jù)庫中任意瞬間都會(huì)有與employee （員工）數(shù)量相同的salary history關(guān)系實(shí)例。相比之下，employee關(guān)系就只有一個(gè)實(shí)例。在表示數(shù)據(jù)庫的術(shù)語中屬性和重復(fù)組分別在簡單域和非簡單域中是大致相似的?，F(xiàn) 在術(shù)語中的多混淆之處是由于沒能把類型和實(shí)例（如在“record中）區(qū)別開和把數(shù)據(jù)的用戶模式的組成和它們

26、相應(yīng)的機(jī)器表示區(qū)別開（再次以“record為例）。1.4標(biāo)準(zhǔn)形式一種所有域都是簡單域的關(guān)系能夠用如上討論過的二維的齊次列數(shù)組來表示其存儲(chǔ) 形式。一些更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)對(duì)一個(gè)有一個(gè)或多個(gè)非簡單域的關(guān)系是必要的。由 于這個(gè)原因（其他的將在下面舉例），消除非簡單域的潛力似乎值得投資。事實(shí)上， 有一種簡單的消除過程，而我們把這個(gè)過程叫做標(biāo)準(zhǔn)化。例如，考慮圖3 （a）顯示的關(guān)系集合。Job history和children是employee關(guān)系的非 簡單域。Salary history是job history的一個(gè)非簡單域。圖 3 （a）中的樹展示了各個(gè) 非簡單域之間相互關(guān)系。jobhistorychi

27、ldrenI ,salaryhistoryemployeebirthdate, jobhistory, children)jqbhi3terF 09bdn%fvtlhistory)aalttryhlfttorysalary)children (childnantet birthyear)圖 3 (a)Fia. 3(a). Unnormslijed setj電bhisLQry' (ma洲"向曲為 title) saJtryhistory' (rrum#, ytfbdate, sdlorydaU. sslary) children* 4險(xiǎn) childnamet birth

28、year)圖 3 (b)Fig. 2(b). Normiiliaed set標(biāo)準(zhǔn)化按如下程序進(jìn)行。從關(guān)系的樹頂端開始，記住它的主碼，并且通過插入主碼域或者域組合來擴(kuò)展每個(gè)直屬的下層關(guān)系。每個(gè)擴(kuò)展關(guān)系的主碼由從父關(guān)系（即上 一層的關(guān)系）拷貝下來主碼在進(jìn)行擴(kuò)大前的主碼構(gòu)成。現(xiàn)在，從父關(guān)系中化掉所有 非簡單域，刪除樹的頂節(jié)點(diǎn)，并且在留下的子樹上重復(fù)同樣的操作程序。圖3 （a）中標(biāo)準(zhǔn)化關(guān)系集合的結(jié)果就是圖3 （b）中的集合。每個(gè)關(guān)系的主碼都用斜體表示以顯示這些碼值是如何通過標(biāo)準(zhǔn)化來擴(kuò)展的。如果要使得如上所述的標(biāo)準(zhǔn)化是可用的，那么關(guān)系集合的非標(biāo)準(zhǔn)化必須滿足如下條件：（1 ）非簡單域之間的相互關(guān)系圖是一個(gè)

29、樹集合。（2）沒有主碼是由非簡單域構(gòu)成的作者不知道哪個(gè)應(yīng)用是不嚴(yán)格滿足以上這些條件的。那這類標(biāo)準(zhǔn)化的更進(jìn)一步的操作就可進(jìn)行了。這些在本文中不會(huì)討論。當(dāng)所有關(guān)系都以標(biāo)準(zhǔn)形式出現(xiàn)時(shí)，變得可行的數(shù)組表示的簡單性不僅有利于存儲(chǔ)的目的，而且有利于廣泛采用不同數(shù)據(jù)表示的系統(tǒng)之間的大量數(shù)據(jù)的通信。這種通信形式是數(shù)組表示的一個(gè)相稱的壓縮版本，并且有如下有利條件：（1 ）沒有指針（值地址或值替換）（2）避免了所有對(duì)哈希選址方式的依賴性（3 ）不包含索引和有序列表如果用戶的關(guān)系模式以標(biāo)準(zhǔn)形式建立，那么數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)的名字可以是一種更簡單的形式，反之亦然。一個(gè)通用的名字有如下形式：R （g）.r.d其中 R 是關(guān)系

30、名字；g 是同輩標(biāo)識(shí)符（可選的）；r 是角色名（可選的）；d 是域名。由于 g 只有在當(dāng)一個(gè)給定的關(guān)系中多個(gè)同輩存在時(shí)才需要，而且 r 只有在當(dāng)關(guān)系R 有兩個(gè)或更多名為d 的域時(shí)才需要，所以簡單形式R.d 通常是恰當(dāng)?shù)摹?.5 一些語言方面如上所述，數(shù)據(jù)關(guān)系模式的采用使基于實(shí)用謂詞演算的通用數(shù)據(jù)子語言的發(fā)展成為可能。如果關(guān)系結(jié)合是標(biāo)準(zhǔn)形式的，那么一階謂詞演算就足夠了。這種語言為所有其它提議的數(shù)據(jù)語言提供了語言影響力的一個(gè)衡量標(biāo)準(zhǔn)，并且它自己也是嵌入（有適當(dāng)?shù)木浞ㄐ薷模┰谠S多其它主流語言（編程，面向命令的或面向問題的）中的一種強(qiáng)勢(shì)的候選者。雖然詳細(xì)地描述這樣一種語言不是本文的目的，但是它顯著的特

31、征有如下幾點(diǎn)。我們用 R 標(biāo)記數(shù)據(jù)子語言，用H 標(biāo)記主語言。R 允許關(guān)系及他們的域的聲明。每一個(gè)關(guān)系的聲明都為這個(gè)關(guān)系確定了它的主鍵。聲明過的關(guān)系被添加到系統(tǒng)資料庫，從而被任何擁有合適權(quán)限的使用者群體的一員使用。H 允許支持聲明，這些聲明可能沒那么永久性的表明了這些關(guān)系在存儲(chǔ)時(shí)時(shí)如何表示的。R 允許定義數(shù)據(jù)庫中的任何數(shù)據(jù)子集的檢索。這樣的一個(gè)檢索請(qǐng)求之后能發(fā)生的動(dòng)作受制于安全限制條件。數(shù)據(jù)子語言的普適性是由它的描述能力決定的（而非它的計(jì)算能力）， 在一個(gè)大型數(shù)據(jù)庫中，每一個(gè)數(shù)據(jù)子集都擁有大量的可能的（而且合理的）描述。即使我們假設(shè)（正如我們所做的）系統(tǒng)有權(quán)使用的、確定搜索數(shù)據(jù)合格性的功能子程序

32、的有限集合只有一個(gè)。因此，能夠應(yīng)用于集規(guī)范資格表達(dá)式的集合的必須擁有對(duì)應(yīng)用謂詞演算的格式規(guī)范的公式集合的描述能力。眾多周知，為了維護(hù)這種描述能力，不必要表示（無論選擇的是什么語法）選中的謂詞演算的所有公式。比如，那些以前束規(guī)范格式的就夠了。在搜索體驗(yàn)行業(yè)的合格性或其他方面可能要用到算術(shù)函數(shù)。這些函數(shù)用H 語言定義，用R 語言調(diào)用。這樣指定的一個(gè)集合可能僅用于查詢，或者用于可能發(fā)生的變化。插入采用向已聲明的關(guān)系中加入新的元素的形式實(shí)現(xiàn)，同時(shí)不考慮在機(jī)器中表示的順序。刪除對(duì)公共組都有效（而不是個(gè)人用戶或子組），刪除以從已聲明的關(guān)系中移除元素的形式實(shí)現(xiàn)。如果指定關(guān)系之間的刪除和更新依賴性已經(jīng)用R 語

33、言聲明，那么一些刪除和更新可能會(huì)由其他的刪除和更新引發(fā)產(chǎn)生。用這種視圖看數(shù)據(jù)，對(duì)查詢數(shù)據(jù)的語言有一個(gè)重大的影響，這個(gè)影響就是數(shù)據(jù)元素和集合的命名。這其中的一些方面已經(jīng)在上一節(jié)討論過。使用通常的網(wǎng)絡(luò)視圖，用戶常常為創(chuàng)造和使用更多的而不是完全有必要的關(guān)系名稱所累。因?yàn)槊Q適合路徑（或路徑類型）有關(guān)，而不是和關(guān)系有關(guān)。一旦用戶意識(shí)到存儲(chǔ)了某個(gè)特定的關(guān)系，他會(huì)希望使用他的已知參數(shù)和未知參數(shù)的任意組合來利用這個(gè)關(guān)系，因?yàn)樾畔ⅲㄈ缰槟吕尸敺澹┦谴嬖诘?。這是一個(gè)系統(tǒng)特征，我們叫做（邏輯上）關(guān)系的對(duì)稱利用。當(dāng)然，性能上的對(duì)稱性是不可能的。為了支持一個(gè)二元關(guān)系的對(duì)稱性利用，需要兩條直接路徑。對(duì)于一個(gè)n 元的關(guān)系

34、，被命名和控制的路徑數(shù)量是n 的階乘。同樣，如果采取這樣的關(guān)系視圖：每一個(gè)n元關(guān)系必須被用戶以只包含2 元關(guān)系的一張網(wǎng)狀表達(dá)式表示出來（比如，參見Feldman LsEAP 系統(tǒng)），那么必須創(chuàng)造2n-1 個(gè)名稱而不僅僅是1.2 節(jié)描述的n+1個(gè)擁有直接n 元標(biāo)記的名稱。例如，圖片1 這的 4 元關(guān)系 supply ，它以 n 元標(biāo)記初始化了 5 個(gè)名稱，用如下形式表示P （supplier, & （part, R （project, quantity）以網(wǎng)狀二元標(biāo)記，包含7 個(gè)名稱。這種表示方式的進(jìn)一步的缺點(diǎn)是它的不對(duì)稱性。盡管這種不對(duì)稱性不會(huì)禁止對(duì)稱性利用，它肯定會(huì)使用戶的一些詢問操

35、作很不方便表示（比如，對(duì)于跟給定的使用 Q 和 R 寫的項(xiàng)目相關(guān)的那些部分和數(shù)量的查詢）。1.6 可表達(dá)的、已命名的而且已存儲(chǔ)的關(guān)系有兩個(gè)關(guān)系集合跟資料庫有關(guān)：命名集和可表達(dá)集。命名集市用戶群能夠通過一個(gè)簡單名字（或標(biāo)識(shí)）識(shí)別的所有關(guān)系的集合。當(dāng)恰當(dāng)授權(quán)的用戶聲明R 時(shí)，關(guān)系 R 擁有了命名集的成員資格。當(dāng)恰當(dāng)授權(quán)的用戶取消R 的聲明時(shí)，它失去了成員資格。可表達(dá)集是能夠用數(shù)據(jù)語言中的表達(dá)式表示的所有關(guān)系的集合。這些表達(dá)式是由名字集中關(guān)系的簡單名字組建起來的。階段的名稱、角色和域、邏輯連接詞、謂詞演算的量詞以及某些常量關(guān)系符號(hào)，如= ，> 。名字集是可表達(dá)集的一個(gè)子集 通常是一個(gè)很小的子集

36、。由于名稱集合中的某些關(guān)系可能是集合中其它關(guān)系的時(shí)間無關(guān)的組合，將名稱集和定義這些時(shí)間無關(guān)的限制條件的語句的集合聯(lián)系起來考慮很有用。我們將推遲討論這個(gè)，直到我們介紹了對(duì)關(guān)系的幾種操作（參看第二節(jié)）。為用戶設(shè)計(jì)一個(gè)支持關(guān)系模型的數(shù)據(jù)系統(tǒng)時(shí)，設(shè)計(jì)者所面臨的主要問題之一是確定支持存儲(chǔ)表示所用的集合。理想情況下，允許的數(shù)據(jù)表現(xiàn)形式的多樣性應(yīng)該正好足夠覆蓋性能安裝總集合要求的范圍。太大的范圍導(dǎo)致不必要的存儲(chǔ)開銷和連續(xù)的對(duì)當(dāng)先結(jié)構(gòu)描述的重新解釋。對(duì)于任意選定的存儲(chǔ)表示集合，數(shù)據(jù)系統(tǒng)必須提供把用關(guān)系模型的數(shù)據(jù)語言表達(dá)的用戶需求轉(zhuǎn)換成相應(yīng)且有效的當(dāng)前存儲(chǔ)表示的方法。對(duì)于高層數(shù)據(jù)語言，這好似一個(gè)具有挑戰(zhàn)性的設(shè)計(jì)

37、問題。不過，隨著更多的用戶擁有了對(duì)大型資料庫的訪問權(quán)限，這就變成了一個(gè)必須解決的問題。同時(shí)，也能為從個(gè)人用戶到數(shù)據(jù)系統(tǒng)提供有效的響應(yīng)和吞吐量。2 冗余和兼容2.1 對(duì)關(guān)系的操作由于關(guān)系是集合，所有普通的集合操作也都適用于關(guān)系。不過，結(jié)果可能不是一個(gè)關(guān)系，比如，一個(gè)二元關(guān)系和三元關(guān)系的連接不是一個(gè)關(guān)系。下面討論的操作是專門針對(duì)關(guān)系的。介紹這些關(guān)系是因?yàn)樗鼈冊(cè)趶钠渌P(guān)系中派生出關(guān)系上扮演重要角色。它們主要應(yīng)用在非推理的信息系統(tǒng)中，這種系統(tǒng)不提供邏輯推理服務(wù)，盡管當(dāng)類似的服務(wù)被添加后不一定會(huì)損害它們的適用性。大多數(shù)用戶不會(huì)直接關(guān)心這些操 作。然而，信息系統(tǒng)設(shè)計(jì)人員和與資料庫控制相關(guān)的人員應(yīng)該徹底熟悉

38、它們。2.1.1 置換。 一個(gè)二元關(guān)系有一個(gè)具有兩列的數(shù)組表示。將這兩個(gè)列換位得到逆關(guān)系。更一般的，如果一個(gè)置換被應(yīng)用于一個(gè)n 元關(guān)系的列，由此產(chǎn)生的列被稱作給定序列的排列。例如，圖 1 中有關(guān)系supply 的 4！ =24 種排列，如果我們包括不改變列順序的恒等排列。2.1.2 投影。假設(shè)我們從一個(gè)關(guān)系中選出特定的某些列(剔除其它的列)，然后從結(jié)果中刪除數(shù)組中的任何行重復(fù)。最終的數(shù)組表示了一個(gè)叫做給定關(guān)系的投影的關(guān)系。選擇算子 兀被用來獲取任何所需的排列、投影或兩個(gè)操作的組合。因此，如果L是K個(gè)標(biāo)記的列表 L = i1, i2,；,Rk是一個(gè)n元關(guān)系(n>=k)，那么兀1(R) 一個(gè)

39、k元關(guān)系，這個(gè)關(guān)系的第j列是R的第ij歹U (j=1,2,),k同時(shí)結(jié)果的行中的冗余也將移除?？紤]圖1 中的關(guān)系supply ，圖 4 展示了這個(gè)關(guān)系的置換投影。注意，在這個(gè)特殊的情況下，投影比產(chǎn)生該投影的關(guān)系的n 元組要少。2.1.3 連接。 假設(shè)給定兩個(gè)二元關(guān)系，它們有一部門共同域。在什么情況下我們可以結(jié)合這兩個(gè)關(guān)系，以形成一個(gè)三元關(guān)系，其中保留了所給關(guān)系的所有信息？圖5中的例子顯示了兩個(gè)可以進(jìn)行無信息損失連接的兩個(gè)關(guān)系R,S,圖6顯示了 R和S的連接。如果存在一個(gè)三元關(guān)系 U,滿足 m2 ( U ) = R且 或3 (U) = S., 則二元關(guān)系R和S則是可連接的。任意這樣的三元關(guān)系都叫

40、做R和S的連接。如果R,S是二元關(guān)系且 茂(R)=m(S ,則R和S是可連接的。自然連接是肯定 存在的一個(gè)連接，定義為R*S = (a, b, c):R(a, b) A S(b, c)其中，如果(a,b)是R的一個(gè)成員且和S(b,c)相似，則R(a,b)的值是真。即n12 (R*S) = R 且加3 (R*S) = S.注意，圖6中顯示的連接是圖5中的R和S的自然連接，圖7顯示了；另一個(gè)連 接。word.II浦魏 ppEy)(projectsupplier)51521472Fin. 4 A permuted projeetiou of the relation in Figure 1Rpari

41、)S (part project)111 121122221Fig. 5.Two joinaWe relationsR*S (suppler part project)1111 122 11212221FiQk 6. The fl&luhU join of R 科：山 H from Eigure 5)U (supplierp“£pr&jcC)112211221Fto» 7, Another jiiin of R with S (from Figure 5)檢查這些關(guān)系展示了域 part (連接操作發(fā)生的域)中的一個(gè)元素(元素1), 該元素有性質(zhì)：它擁有在R和

42、S中不止一個(gè)關(guān)系。正是這個(gè)元素引起了連接的多元化。在連接域里這樣的元素叫做有關(guān)R和S連接的歧義點(diǎn)。如果 加1 (R )或R是一個(gè)函數(shù)，在R和S的連接中不會(huì)出現(xiàn)歧義點(diǎn)。在這種情況下，R和S的自然連接就是 R和S的連接。注意反復(fù)的限定"和S”是必需的，應(yīng)為 S可能和S可連接(R和S同樣)，而且這個(gè)連接應(yīng)該完全 分開考慮。在圖5中，關(guān)系R,戒1 (R ) , S,戒1 (S )都不是一個(gè)函數(shù)。R和S連接中的歧義點(diǎn)有時(shí)可以用其它關(guān)系消除。假設(shè)我們被給定，或者可以從R,S中產(chǎn)生一個(gè)關(guān)系 T,關(guān)系在域project和supplier上擁有以下性質(zhì)：(1)水T)=吸俗),才±(T)=(3

43、)牙/內(nèi)一即解&#) A 8納力3(4)正出/)1布(S3，)A ")% S(ptj)3s(T(j)八 R® 6)這樣我們可能形成 R,S,T的三路連接，也就是一個(gè)三從關(guān)系，如下：= E,才物)=以 f(0) = T.這樣的一個(gè)連接被叫做循環(huán)三路連接以和線性三路連接區(qū)別開來，后者將會(huì)是一個(gè)四元關(guān)系 V,如下：r12(V) = K, (F) = St (F) = 7.盡管可能存在不止一個(gè)循環(huán)三路連接(參看圖8, 9),這種情況可能發(fā)生的環(huán)境比2元關(guān)系的多元性要發(fā)生該情況的環(huán)境要有更嚴(yán)格的限制Fig-. S. Binary relation with撲 T O'

44、 #dd1ed2de2ee2plurality of cyclic 3-joinaFig. - Two cyoLic 3-joins ofthe relations in Fiffure 8具體來說，關(guān)系 R,S,T必須處理關(guān)于 R和S連接(假設(shè)是點(diǎn) x) , S和T 的連接(假設(shè)是y)和T和R的連接(假設(shè)是z)的歧義點(diǎn)。而且，更進(jìn)一步， y必須是x在S下的一個(gè)關(guān)系，z是y在T下的一個(gè)關(guān)系，x是z在R下的一 個(gè)關(guān)系。注意在圖 8中，點(diǎn)x=a;y=d;z=2有這個(gè)屬性。3個(gè)2元關(guān)系R,S,T的自然線性三路連接如下：R*5*T = & M 外 孫Ji b) A S他A T(ct d)其中，

45、因?yàn)槭?元自然連接，等號(hào)左邊不用圓括號(hào)。為了獲取循環(huán)副本，我們引入操作符號(hào)r,它可以通過將一個(gè) n元關(guān)系的首位相連產(chǎn)生一個(gè) n-1元的 關(guān)系。因此，如果 R是一個(gè)n元關(guān)系(n>=2 ) , R產(chǎn)生的環(huán)由下面的公示定 義：¥（/?） = | （的 丁 曲, ,（的,他,-* f%）人的=4,我們現(xiàn)在可以用下面的表達(dá)式表不R,S,T的自然循環(huán)三路連接:CR.SW）.線性概念，循環(huán) S-連接和n元關(guān)系的連接的自然副本的擴(kuò)展很明顯。然 而，考慮到一些進(jìn)行連接的關(guān)系不一定是二元的，所以可能需要一些額外的描述?？紤]關(guān)系R （r元），S （s元）的情況，在它們的 p個(gè)域上連接兩個(gè)關(guān)系。 簡單

46、的說，假設(shè)這p個(gè)域是R的r個(gè)域中白最后p個(gè)域和S的s個(gè)域中的前p 個(gè)域。如果不是這樣，我們可以總是采用適當(dāng)?shù)呐帕惺顾@樣。現(xiàn)在，取得 R 的前r-p個(gè)域的笛卡爾乘積， 并且叫這個(gè)新的域?yàn)?A。取得R的后p個(gè)域的笛 卡爾乘積，并稱之為 B。取得S的后s-p個(gè)域的笛卡爾乘積，并稱之為C。我們可以把R看作是在域 A.B上的二元函數(shù)。類似的，我們可以把S看作是域B,C上的二元關(guān)系。線性和循環(huán) S-連接的概念現(xiàn)在成為可以直接接受的了?？?以對(duì)線性的和各種元的 n個(gè)關(guān)系的循環(huán)n元連接也采用這種方法。2.1.4 組成。讀者很可能對(duì)應(yīng)用在函數(shù)上的組成概念非常熟悉。我們將會(huì)討論這個(gè) 概念的概括而且首先把它應(yīng)用到

47、二元關(guān)系上。我們對(duì)組成和可組合型的定義是直接基于以上給出的聯(lián)合和可聯(lián)合性的定義上的。假設(shè)我們被給予兩個(gè)關(guān)系 R,So T是R和S的組合，如果存在一個(gè) R和S的連接且滿足丫 =o因此，當(dāng)且僅當(dāng)兩個(gè)關(guān)系是可連接的時(shí)，它們是可組合的。然而，存在多于一個(gè)的 R和S的連接并不意味著存在多余一個(gè) 的R和S的組合。與R與S的自然連接相應(yīng)的是 S伴隨R的自然組成，定義為：R?S = 13 （R*S）將關(guān)系R和S從表5中提取出來看，他們的天然組成由表 10展示，而另個(gè)組成由表11展示（與表7展示的連接相區(qū)別）R+S （jrt-qfeci1111 22 13 J表10. S伴隨R的天然組成（由表 5所得）T(pr

48、ey retsuppHar)1221表11. S伴隨R的另一個(gè)組成（由表 5所得）當(dāng)存在2個(gè)或更多的連接時(shí)，不同白組成數(shù)量可能少至1個(gè)也可能多至與不同連接數(shù)目相同。表 12展示了一個(gè)有許多連接關(guān)系但是只有一個(gè)組成的2個(gè)關(guān)系的例子。注意到在由 S組成R時(shí)，點(diǎn)c的不確定性丟失了，因?yàn)橥ㄟ^ 點(diǎn)a,b,d,e造成了確定性的關(guān)聯(lián)。1 bbf2 C0f3 c。片4 dd%5 paf表12.多個(gè)連接，只有一個(gè)組成多對(duì)非必須二元(可能是多維的)的關(guān)系的組成的擴(kuò)展與這種關(guān)系成對(duì)連 接的情況如出一轍。對(duì)于關(guān)系組合了解的缺乏導(dǎo)致許多系統(tǒng)設(shè)計(jì)員陷入了一種我們稱為連接陷阱的困境。這種陷阱可能被依照以下舉例描述。假設(shè)每個(gè)

49、供應(yīng)商的描述與供應(yīng)商供應(yīng)的每一部分的描述相關(guān)聯(lián)，并且每一部分的描述近似地與使用這些部分的工程描述相關(guān)聯(lián)。通常，現(xiàn)在就可以得出一個(gè)錯(cuò)誤的結(jié)論：換句話說，如果所有可能的通道通過供應(yīng)商在工程中供應(yīng)的部分來遵循供應(yīng)商，就可以得到一個(gè)該供應(yīng)商供應(yīng)的所有工程的有效集。這樣一個(gè)結(jié)論只有在非常特殊的情況下才是正確的，即是目標(biāo)的工程和供應(yīng)商關(guān)系實(shí)際上是另兩個(gè)關(guān)系的自然組成 而我們通常必須加上一個(gè)詞對(duì)于所有時(shí)間”，因?yàn)檫@通常是在跟蹤控制技術(shù)的要求中暗示到的。*別的作者傾向于忽略組成而不是自然組成，于是把這一特別的組成看做那個(gè)組成”看，舉個(gè)例子，Kelley 的"General TopoOgy"

50、.2.1.5限制。一個(gè)關(guān)系的子集還是一個(gè)關(guān)系。關(guān)系S可能對(duì)關(guān)系R操作從而形成一個(gè)R的子集的一種途徑是通過S對(duì)R進(jìn)行限制操作。這個(gè)操作是函數(shù)對(duì)子集的域的限制的一般化，它的定義如下。設(shè)L,M為等長目錄列表，L=ii,i2, ;ik, M=ji, j2, kj其中kWR的維數(shù)且 kWS的維數(shù)。則L,M對(duì)由S對(duì)R的限制Rl|mS表示R的最小子集R',立(R') =m(S)。這個(gè)操作只有當(dāng)相等可以對(duì)于h=1,2,k應(yīng)用到 m(R)的成員和 加(R)之間才被定義。表13中R,S,R這3個(gè)關(guān)系滿足等式 R' = R3) |(1,2) Sos <p j) R' a p j

51、)&K1鼻AqB2aAbB2bB表13.限制舉例 我們現(xiàn)在立足于考慮這些操作在關(guān)系上的應(yīng)用。2.2 冗余一個(gè)指定關(guān)系集的冗余必須可以與存儲(chǔ)陳述集的冗余相區(qū)別。在這里我們主要關(guān)心的是前者。首先，我們需要一個(gè)關(guān)于關(guān)系的可導(dǎo)出性的精確概念。假設(shè)0是關(guān)系上的一個(gè)操作集合， 而且每個(gè)操作都有對(duì)每個(gè)操作數(shù)產(chǎn)生一個(gè)唯一關(guān)系的性質(zhì)(因此自然連接是合理的，但是連接是不合理的)。如果一個(gè)關(guān)系R 在所有情況下存在一個(gè)集合 0的操作序列，使R從S的一個(gè)成員中產(chǎn)生，則R對(duì)一個(gè)關(guān)系集合 S0可導(dǎo)。在所有情況下”這一描述是現(xiàn)在時(shí)的，因?yàn)槲覀冋谔幚黼S時(shí)間變化的關(guān)系，而且我們的興趣在于保持一段關(guān)鍵時(shí)期的可導(dǎo)性。對(duì)于非

52、推理性系統(tǒng)上的指定關(guān)系，似乎一個(gè)恰當(dāng)?shù)募?01包含了一下操作：投影，自然連接，束縛和限制。排列是不相干的且自然成分需要被包含，因?yàn)樵谶M(jìn)行連接然后投影的情況下是可行的。對(duì)于表示的存儲(chǔ)集來說，一個(gè)恰當(dāng)?shù)膶?duì)2集合的操作會(huì)包含排列和更多的關(guān)于子集合和合并關(guān)系的操作，并且排列和關(guān)聯(lián)它們的元素。2.2.1 強(qiáng)冗余。如果一個(gè)關(guān)系集包含了最少一個(gè)關(guān)系，這個(gè)關(guān)系控制了一個(gè)不同于其他關(guān)系集投影的投影，我們就稱這個(gè)關(guān)系集是強(qiáng)冗余的。以下兩個(gè)例子是為了解釋為什么強(qiáng)冗余性是這樣定義的，和證明它的實(shí)際作用。在第一個(gè)關(guān)系系列的例子中包含了下面這個(gè)關(guān)系：Employee( serial #, name, manager#,

53、 managername)其中 serial# 是主鍵而manager# 是外鍵。讓我們用 來指定有效域，并假設(shè)對(duì)于所有時(shí)間t 滿足： t( manager# ) ? t( serial# )且 t( managername ) ? t( name)這種情況下的冗余就很明顯了：域managername 就是不必要的。要證明這個(gè)是我們?cè)谥岸x的強(qiáng)冗余，我們發(fā)現(xiàn)7134 (employee) = 12 (employee) 斗質(zhì)(employee)。在第二個(gè)關(guān)系系列的例子中包含了一個(gè)描述供應(yīng)商的關(guān)系S， S 的主鍵為s#, 一個(gè)關(guān)系描述部門的關(guān)系D, D的主鍵為d#, 一個(gè)描述工程的關(guān)系J, J

54、的主鍵為j#,以及一下關(guān)系：P (s#, d#,), Q(s#,j#,，)R(d#,j#,)其中表示除了 s#, d#, j#的其他域。讓我們假設(shè)接下來一個(gè)情況C,已知C保持時(shí)間的圖理性：供應(yīng)商s當(dāng)且僅當(dāng)他提供的工程J (關(guān)系Q)是部門d可以被分配到的工程時(shí)(關(guān)系R), s才將這個(gè)部門d (關(guān)系P)提供出來。然 后，我們就可以寫出這個(gè)等式并因此展示出一個(gè)強(qiáng)冗余：E2(P) = 12 (Q)? 21 (R)強(qiáng)冗余存在于指定關(guān)系系列的一個(gè)重要原因是用戶方便性。對(duì)此一個(gè)特別的情況是指定關(guān)系集特征關(guān)系的保持，從而從名字上涉及到它們的舊程序可以繼續(xù)正確運(yùn)行。關(guān)于指定集強(qiáng)冗余存在性的知識(shí)使一個(gè)系統(tǒng)或者數(shù)據(jù)

55、庫管理員得以在選擇展示形式上有更多自由行，從而在處理當(dāng)前流量時(shí)更高效。如果一個(gè)指定集的強(qiáng)冗余直接被存儲(chǔ)集的強(qiáng)冗余影響(或者如果其他強(qiáng)冗余被引入這一存儲(chǔ)集)，那么一般來說，將會(huì)在一些查詢的時(shí)間和裝載中央處理器時(shí)間突然變化的同時(shí)，消耗更多存儲(chǔ)空間和更新時(shí)間。2.2.2 弱冗余。第二種類型的冗余可能存在。與強(qiáng)冗余相反，它不是用一個(gè)等式來描述的。如果一個(gè)關(guān)系系列包含了一個(gè)關(guān)系，這個(gè)關(guān)系包含一個(gè)無法區(qū)別于其他成員的工程，但是這個(gè)關(guān)系對(duì)于任何時(shí)候都是一個(gè)該集合關(guān)系中其他投影連接的投影，那么這一關(guān)系系列就是弱冗余的。我們可以用第二個(gè)強(qiáng)冗余的例子(前面提到的)來展示一個(gè)弱冗余，并且假設(shè)現(xiàn)在狀態(tài) C并不能在所有時(shí)間下保持穩(wěn)定。關(guān)系兀12 ( P),兀12 ( Q) , 7112(R)是復(fù)雜關(guān)系，在潛在的任兩個(gè)關(guān)系連接的同時(shí)觀點(diǎn)模糊的可能性時(shí)不時(shí)產(chǎn)生。 在這種情況下，沒有一個(gè)關(guān)系可以區(qū)分于另外兩個(gè)。但是，在他們之間確實(shí)存在約束，因?yàn)槊恳粋€(gè)關(guān)系都是這3 個(gè)關(guān)系循環(huán)鏈接的投