關(guān)系數(shù)據(jù)庫理論(數(shù)據(jù)庫)

時間：2022-12-25 10:30:01 | 來源：信息時代

時間：2022-12-25 10:30:01 來源：信息時代

    關(guān)系數(shù)據(jù)庫理論 : 20世紀(jì)70年代初由Codd開創(chuàng)的、目前研究得最深入、應(yīng)用得最廣泛的一種數(shù)據(jù)庫理論。這種數(shù)據(jù)庫理論中已經(jīng)普及的內(nèi)容是關(guān)系代數(shù)、關(guān)系演算、函數(shù)依賴、鍵、范式、模式分解、規(guī)范化、多值依賴、連接依賴、廣義依賴、泛關(guān)系、無回路數(shù)據(jù)庫等20世紀(jì)70年代及80年代初研究的內(nèi)容。
數(shù)據(jù)庫的一個主要任務(wù)是查詢。關(guān)系代數(shù)及關(guān)系演算(包括元組關(guān)系演算及域關(guān)系演算)是關(guān)系數(shù)據(jù)庫查詢的理論基礎(chǔ)。其中,關(guān)系代數(shù)及元組關(guān)系演算是由Codd在1970年首先提出的。1972年,Codd證明了每個關(guān)系代數(shù)表達(dá)式都可以轉(zhuǎn)化為一個(安全的)元組關(guān)系演算(“安全的”請見關(guān)系演算),但當(dāng)時還不能證明每個元組關(guān)系演算表達(dá)式也都可以轉(zhuǎn)化為一個關(guān)系代數(shù)。1978年,Pirotte總結(jié)了當(dāng)時已有的關(guān)系數(shù)據(jù)庫的各種處置運(yùn)算,又提出了一種域關(guān)系演算,并證明了每個(安全的)元組關(guān)系演算的表達(dá)式都可轉(zhuǎn)化為域關(guān)系演算,而每一個(安全的)域關(guān)系演算的表達(dá)式又都可以轉(zhuǎn)化為一個關(guān)系代數(shù),這樣,再加上Codd已證明的每個關(guān)系代數(shù)表達(dá)式都可以轉(zhuǎn)化為(安全的)元組關(guān)系演算,就證明了關(guān)系代數(shù)⇒(安全的)元組關(guān)系演算⇒(安全的)域關(guān)系演算⇒關(guān)系代數(shù), 于是三者完全等價(jià), 這就奠定了關(guān)系數(shù)據(jù)庫的查詢理論的基礎(chǔ)。
除了等價(jià)性外,人們對這些運(yùn)算的語義必要性也從理論上作了研究。1978年,Beck證明了并、差、串接、投影、選擇是五個必要運(yùn)算,其中任何一個都不能用另外四個來表示,而其他運(yùn)算都能用他們來表示。進(jìn)一步的研究也發(fā)現(xiàn)了這三種關(guān)系運(yùn)算的一些不足之處,例如,不能表示傳遞閉包,而且還揭示了其他缺欠。這些不足之處在90年代后逐步得到了克服,請?jiān)斠娢墨I(xiàn)[1]。
數(shù)據(jù)庫的另一個重要理論問題是數(shù)據(jù)庫的存儲結(jié)構(gòu)。1970年Codd就提出了關(guān)于好的數(shù)據(jù)庫結(jié)構(gòu)的第1范式、第2范式及第3范式的理論,1972年又補(bǔ)充提出Boyce-Codd范式的理論,并且給出了研究范式所需的函數(shù)依賴、鍵、主屬性、非主屬性、部分依賴、傳遞依賴等理論概念。證明了按滿足這些范式的數(shù)據(jù)庫結(jié)構(gòu)來存儲數(shù)據(jù)將不會有冗余弊、插入弊、修改弊及刪除弊。為了將不好的數(shù)據(jù)庫結(jié)構(gòu)轉(zhuǎn)化為好的數(shù)據(jù)庫結(jié)構(gòu),1976年,Bernstein研究出了將任意一個關(guān)系數(shù)據(jù)庫轉(zhuǎn)化為第3范式的無損依賴的分解方法。1979年,Biskup等給出了把任意一個關(guān)系數(shù)據(jù)庫分解為第3范式的無損連接、無損依賴的分解方法。同年,Beeri等還解決了關(guān)系分解等價(jià)性問題。這樣就完全地解決了函數(shù)依賴情況下好的數(shù)據(jù)庫結(jié)構(gòu)設(shè)計(jì)的理論問題。
由于函數(shù)依賴在解決關(guān)系數(shù)據(jù)庫結(jié)構(gòu)優(yōu)劣方面起著重要的作用,所以對它還做了進(jìn)一步深入的理論研究。發(fā)現(xiàn)有時兩個函數(shù)依賴集合雖然表面不同,但實(shí)際起的作用是一樣的,即它們是等價(jià)的。為了嚴(yán)格地在理論上定義等價(jià),首先定義了蘊(yùn)涵。顯然,判定蘊(yùn)涵與等價(jià)是非常重要的任務(wù),1974年,Armstrong提出了一種用公理推導(dǎo)蘊(yùn)涵的方法,給出了一個現(xiàn)在用他的名字命名的Armstrong公理系統(tǒng)。他證明了這個系統(tǒng)是有效的(推導(dǎo)出的都是被蘊(yùn)涵的)、完備的(被蘊(yùn)涵的都能被推導(dǎo)出),特別是其完備性證明是非常巧妙的、完美的。這項(xiàng)理論成果使關(guān)系數(shù)據(jù)庫理論上了一個新臺階。
20世紀(jì)70年代后期,人們發(fā)現(xiàn)除了函數(shù)依賴外,還有其他一些依賴存在。它們也會對數(shù)據(jù)庫存儲的結(jié)構(gòu)的優(yōu)劣有影響。1976～1978年,Zaniolo、Fagin及Delobel分別獨(dú)立地提出了多值依賴及第4范式,指出了多值依賴是函數(shù)依賴的推廣,而對于存在著多值依賴的數(shù)據(jù)庫只有屬于第4范式的數(shù)據(jù)庫結(jié)構(gòu)才沒有弊病。對多值依賴的研究發(fā)現(xiàn),它也存在著蘊(yùn)涵及等價(jià)等問題。受函數(shù)依賴的啟發(fā),在多值依賴?yán)碚撗芯康囊婚_始,Beeri就給出了有效完備的公理系統(tǒng)。而且同時,Beeri(1977年)還發(fā)現(xiàn)多值依賴存在著一種依賴基。依賴基的理論研究加深了人們對多值依賴的認(rèn)識。在實(shí)際問題中,有很多場合中多值依賴并不是對整個關(guān)系模式的,而只是對它的一個子集的。而且在一定意義上說,后者比前者出現(xiàn)得更多,后者被稱為是嵌入的多值依賴。Fagin(1977年)、Delobel(1978年)、Tanaka(1978年)等研究了嵌入的多值依賴的相關(guān)理論問題,取得了很多理論成果。但是,在研究嵌入多值依賴的推導(dǎo)公理系統(tǒng)時卻發(fā)現(xiàn),無論如何也給不出完備的公理系統(tǒng)。1982年,Sagiv及Walecka提出了一種子集依賴,借助子集依賴他們證明了嵌入的多值依賴不存在完備的公理系統(tǒng)。
多值依賴只能反映兩個關(guān)系的無損連接情況,而實(shí)際問題中有很多場合是要考慮三個以上關(guān)系的無損連接情況。于是在1979年,Rissanen提出了連接依賴。同年,Fagin提出了第5范式,證明了一個存在著連接依賴的數(shù)據(jù)庫只有屬于第5范式才能在使用時沒有弊病。對連接依賴的公理系統(tǒng)的研究比較困難。1978年,Fagin等證明了完全連接依賴的公理系統(tǒng)尚不完備,即有些蘊(yùn)涵的連接依賴還不能從公理推出。他們定義了一種增廣完全連接依賴,證明了有一些被連接依賴集合蘊(yùn)涵的連接依賴必須先從依賴集合推出某些增廣連接依賴,然后由這些增廣連接依賴再推出這個連接依賴。而公理系統(tǒng)只能對增廣連接依賴才是完備的(參見連接依賴)。
為了對函數(shù)依賴、多值依賴、嵌入的多值依賴、子集依賴、完全連接依賴、嵌入的連接依賴等這么多種類型的依賴能有一種統(tǒng)一的方法進(jìn)行研究與處理,1980～1981年,Beeri、Vardi、Paredaens、Ullman等人分別獨(dú)立地提出了廣義依賴的概念。廣義依賴分為等值產(chǎn)生依賴及元組產(chǎn)生依賴。它們包括了以上所有類型的依賴并且使很多處理任務(wù)(例如追趕算法、蘊(yùn)涵判定等)有了統(tǒng)一、一致的形式。廣義依賴是現(xiàn)在通用的名稱,1980年,Fagin及Yannakakis等還提出過蘊(yùn)涵依賴及代數(shù)依賴等,也都是為了解決各種依賴的統(tǒng)一及推廣問題。以上這些研究的成功擴(kuò)大了關(guān)系數(shù)據(jù)庫理論的覆蓋面。
各種依賴模式的規(guī)范化都是將不符合范式要求的關(guān)系模式或各種依賴模式進(jìn)行分解,使分解后的關(guān)系模式或各種依賴模式能滿足范式的要求。然而,這樣的分解將使關(guān)系模式或各種依賴模式的個數(shù)增加,這樣用戶使用時感到不便。為了解決這個問題,人們提出了存儲時按分解后的模式存儲,使用時(指查詢、插入、修改、刪除)仍讓用戶想像成是對一個整體關(guān)系的思想,這種想像中的關(guān)系被稱為“泛關(guān)系”?！胺宏P(guān)系”的理論解決了數(shù)據(jù)庫結(jié)構(gòu)沒有弊病與用戶使用方便性之間的矛盾。早在1976年,Bernstein就已經(jīng)意識到了這樣做的好處。他提出了從泛屬性集的觀點(diǎn)出發(fā)進(jìn)行數(shù)據(jù)庫模式的設(shè)計(jì)問題。國際上公認(rèn)他的這個思想意識就是泛關(guān)系研究的開始。不過早期的研究工作進(jìn)展并不大,因?yàn)槿藗兪艿椒宏P(guān)系上的元組也不允許有空值這樣一個默認(rèn)的假設(shè)的束縛。如果把所有屬性看成一個關(guān)系模式不進(jìn)行分解,一般它將是不屬于第3范式(或BC范式)的。因此,它有插入弊。這樣一些元組完全可能在某些屬性上還沒有值。所以去掉泛關(guān)系上的元組也不允許有空值的限制是勢在必行了。1980年,Honeyman、Lander及Yannakakis研究了含空值的泛關(guān)系的理論,提出了全投影、泛例、有效模式、元組的淹沒、關(guān)系的淹沒、代表泛例等全新概念。為了對泛關(guān)系進(jìn)行查詢,人們還提出了窗口函數(shù)的思想。1983年,Sagiv定義了鍵依賴、擴(kuò)展連接及唯一性模式的新概念,并用唯一性模式作為泛關(guān)系查詢的一種窗口。1986年,Maeir等推廣了這個結(jié)果,允許不是鍵依賴的函數(shù)依賴集形成窗口。1982年,Fagin、Mendelzon及Ullman還提出了一種語義結(jié)構(gòu)窗口,這種窗口更適合于泛關(guān)系查詢語義的表達(dá)。關(guān)系數(shù)據(jù)庫理論的發(fā)展也不是一帆風(fēng)順的,泛關(guān)系的有關(guān)理論從它出現(xiàn)那時起就有反對意見。1981～1982年初,W.Kent、Atzeni及Parker都發(fā)表文章認(rèn)為泛關(guān)系作為一種數(shù)據(jù)模型是不合適的。1982年10月,Ullman則著文給予反駁。1983年,Kent又兩次提出對泛關(guān)系的反對意見。同年,Ullman又給予反駁。連關(guān)系數(shù)據(jù)庫理論的創(chuàng)始人Codd也反對泛關(guān)系的思想,1988年,他發(fā)表文章支持早期對泛關(guān)系的那些反對意見。現(xiàn)在,大多數(shù)人還都認(rèn)為泛關(guān)系理論是適宜的。
泛關(guān)系理論解決了用戶使用的方便性與規(guī)范化必須對模式進(jìn)行分解之間的矛盾。但隨著研究的深入,人們發(fā)現(xiàn)有時不論用哪種窗口進(jìn)行對查詢的解釋,都可能出現(xiàn)有二義性。而這種二義性是由于分解后的數(shù)據(jù)庫結(jié)構(gòu)對應(yīng)的超圖有回路引起的。1982年,Fagin、Mendelzon、Ullman等提出了無回路數(shù)據(jù)庫的概念。1983年,明確地把無回路超圖分為α無回路、β無回路及γ無回路,證明了數(shù)據(jù)庫有許多性質(zhì)與它們等價(jià)。1986年,Datri及Moscarini研究了α、β、γ各種無回路數(shù)據(jù)庫的識別方法及設(shè)計(jì)方法。
20世紀(jì)90年代以后,關(guān)系數(shù)據(jù)庫理論更是蓬勃發(fā)展,它逐漸沖出了原有的框架,把以前偶爾研究的類型,局部獲取的思想都發(fā)展成了系統(tǒng)的理論,把以前認(rèn)為特殊的、特異的關(guān)系數(shù)據(jù)庫變成了正常研究的對象。這使關(guān)系數(shù)據(jù)庫理論涉及的范圍進(jìn)一步擴(kuò)大,包括的體系更加豐富?，F(xiàn)在的內(nèi)容已是早期內(nèi)容的十幾倍,甚至是幾十倍。例如,偏序關(guān)系數(shù)據(jù)庫、時態(tài)關(guān)系數(shù)據(jù)庫、空值關(guān)系數(shù)據(jù)庫、概率關(guān)系數(shù)據(jù)庫、對象關(guān)系數(shù)據(jù)庫、Fuzzy關(guān)系數(shù)據(jù)庫、粗糙關(guān)系數(shù)據(jù)庫、動態(tài)關(guān)系數(shù)據(jù)庫等都已形成了系統(tǒng)的理論,這些現(xiàn)在被稱為非經(jīng)典關(guān)系數(shù)據(jù)庫理論,其成果見參考文獻(xiàn)[1]。
進(jìn)入21世紀(jì)后,在關(guān)系數(shù)據(jù)庫理論的指導(dǎo)下,關(guān)系數(shù)據(jù)庫的應(yīng)用范圍有了更加迅猛的增長。而實(shí)踐范圍的擴(kuò)大必將又進(jìn)一步促進(jìn)理論的發(fā)展。關(guān)系數(shù)據(jù)庫理論定將發(fā)展成一門具有獨(dú)立體系、具有寶貴價(jià)值、具有眾多璀璨成果、指導(dǎo)千百萬人實(shí)踐需求的重要學(xué)科。