FD環(huán)境下無β環(huán)數(shù)據(jù)庫模式研究.pdf

1、隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的發(fā)展，大規(guī)模數(shù)據(jù)庫在各種信息系統(tǒng)中的應(yīng)用日益廣泛，數(shù)據(jù)庫的設(shè)計(jì)與查詢成為信息系統(tǒng)設(shè)計(jì)中的關(guān)鍵技術(shù)。無環(huán)數(shù)據(jù)庫具有許多優(yōu)良的特性，不存在許多在有環(huán)數(shù)據(jù)庫模式下出現(xiàn)的數(shù)據(jù)異常，無環(huán)數(shù)據(jù)庫理論的研究不僅具有理論價(jià)值，而且能指導(dǎo)數(shù)據(jù)庫設(shè)計(jì)實(shí)踐，是數(shù)據(jù)庫理論與應(yīng)用研究中一個(gè)重要分支。對于數(shù)據(jù)庫模式中的無環(huán)性，存在不同的級別，無α環(huán)數(shù)據(jù)庫消除了許多有α環(huán)數(shù)據(jù)庫出現(xiàn)的不良現(xiàn)象，而無β環(huán)除具有無α環(huán)所具有的優(yōu)良特性外，還具有子圖的

2、無環(huán)形，因此無β環(huán)數(shù)據(jù)庫有效地消除了子模式的數(shù)據(jù)異常。 本文主要研究函數(shù)依賴集無內(nèi)部沖突條件下數(shù)據(jù)庫分解為滿足無β環(huán)，無損鏈接，保持函數(shù)依賴和3NF的條件和分解算法，并且對算法進(jìn)行了證明和分析。這些結(jié)論能夠在不同的條件下指導(dǎo)數(shù)據(jù)庫的設(shè)計(jì)，避免各種問題的出現(xiàn)導(dǎo)致設(shè)計(jì)失敗。主要內(nèi)容如下1.關(guān)于FD環(huán)境下數(shù)據(jù)庫模式分解滿足PEK且無α環(huán)問題的研究。通過分析在FD集F的最小歸并依賴集的性質(zhì)和特征，提出了初等歸并依賴集和初等最小歸并依賴集

3、的概念，并定義了初等最小規(guī)并依賴集的弱左部沖突和弱右部沖突，PEX(保持FD，無損連接且滿足EKNF)等概念。討論了數(shù)據(jù)庫模式分解為EKNF的無α環(huán)判定問題，給出了在初等最小D有弱左部或弱有部沖突時(shí)滿足PEK的分解是有α環(huán)的結(jié)論，在此基礎(chǔ)上給出了分解算法、正確性證明和分析。 2.關(guān)于FD環(huán)境下數(shù)據(jù)庫模式分解滿足PS且無α環(huán)問題的研究。通過分析在FD集F的最小歸并依賴集D存在弱左部或弱右部沖突時(shí)所具有的性質(zhì)和特征，提出了PS（保持

4、FD，無損連接且滿足SNF)、條件T等概念。在此基礎(chǔ)上討論了數(shù)據(jù)庫模式分解為SNF的無α環(huán)問題，給出了滿足PS（保持FD，無損連接且滿足SNF)且無α環(huán)分解的充要條件和算法，對算法的正確性、可終止性進(jìn)行了證明，并對算法的時(shí)間復(fù)雜度給出了分析。 3.歸并依賴集全部擴(kuò)展左部屬性的求解。在FD環(huán)境下無環(huán)數(shù)據(jù)庫模式的研究過程中，各種沖突的討論需要涉及歸并依賴集的擴(kuò)展左部集。提出一種多項(xiàng)式時(shí)間算法求解所有歸并依賴的擴(kuò)展左部集中的屬性，給出

5、了算法的正確性、可終止性證明，并對算法的時(shí)間復(fù)雜度給出了分析。 4.FD集無內(nèi)部沖突條件下滿足P3及無β環(huán)數(shù)據(jù)庫模式分解問題的研究。通過分析在FD集F的最小歸并依賴集D無弱左部沖突、弱右部沖突、時(shí)相鄰歸并依賴所具有的性質(zhì)和特征，提出了左部集沖突、蘊(yùn)含集間沖突和主歸并依賴沖突等概念，在此基礎(chǔ)上證明了在FD集F無內(nèi)部沖突，且最小歸并依賴集D中存在弱左，右部沖突、左部集沖突、蘊(yùn)含集間沖突和主歸并依賴沖突時(shí)模式分解為滿足P3為有β環(huán)的結(jié)