數(shù)據(jù)庫數(shù)據(jù)組織無環(huán)性理論

前言

數(shù)據(jù)庫技術(shù)是在20世紀(jì)60年代末作為數(shù)據(jù)管理的最新技術(shù)登上數(shù)據(jù)處理舞臺的。隨著計算機(jī)應(yīng)用的不斷擴(kuò)大，計算機(jī)硬件快速發(fā)展，數(shù)據(jù)庫技術(shù)也得到了迅速的發(fā)展。數(shù)據(jù)庫技術(shù)和計算機(jī)網(wǎng)絡(luò)技術(shù)已成為當(dāng)今世界計算機(jī)應(yīng)用中兩個最重要的基礎(chǔ)領(lǐng)域。經(jīng)過四十多年的發(fā)展，以數(shù)據(jù)模型的進(jìn)展、變化為主線，出現(xiàn)了以層次模型和網(wǎng)狀模型為代表的層次數(shù)據(jù)庫和網(wǎng)狀數(shù)據(jù)庫的第一代數(shù)據(jù)庫。20世紀(jì)70年代末出現(xiàn)了以關(guān)系數(shù)據(jù)模型為代表的第二代數(shù)據(jù)庫——關(guān)系數(shù)據(jù)庫。關(guān)系數(shù)據(jù)庫應(yīng)用數(shù)學(xué)方法來處理數(shù)據(jù)庫中的數(shù)據(jù)，這也正是關(guān)系模型能夠長盛不衰，成為許多其他類型數(shù)據(jù)庫發(fā)展的基礎(chǔ)，能夠成為第二代數(shù)據(jù)庫典型代表的主要原因。最早提出關(guān)系模式雛形的是美國IBM公司Codd，1970年在美國計算機(jī)學(xué)會會刊CommunicationoftheACM上發(fā)表的題為“A Relational Model of Data for Shared Data Banks”的論文中提出了關(guān)系模型的思想。此后，他又發(fā)表了一系列有價值的論文，確立了關(guān)系數(shù)據(jù)庫理論的框架，正是由于他的貢獻(xiàn)，1980年獲得了圖靈獎。人們在關(guān)系數(shù)據(jù)庫理論方面做了大量的研究工作，隨著關(guān)系數(shù)據(jù)庫理論的不斷完善以及計算機(jī)技術(shù)的不斷發(fā)展，關(guān)系數(shù)據(jù)庫的技術(shù)也日趨成熟。關(guān)系數(shù)據(jù)庫之所以重要，主要是它具有以關(guān)系代數(shù)與邏輯為手段的嚴(yán)格的理論基礎(chǔ)，同時還具有單一的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)獨立性強(qiáng)與操作簡單等優(yōu)點。關(guān)系數(shù)據(jù)庫之后，又出現(xiàn)了面向?qū)ο髷?shù)據(jù)庫系統(tǒng)、分布式數(shù)據(jù)庫系統(tǒng)、并行數(shù)據(jù)庫系統(tǒng)等。但目前運行的數(shù)據(jù)庫系統(tǒng)大部分仍是關(guān)系型的，這說明關(guān)系數(shù)據(jù)庫具有強(qiáng)大的生命力，關(guān)系數(shù)據(jù)庫規(guī)范化和設(shè)計理論的研究仍具有理論和實際意義。自20世紀(jì)70年代Codd及其他一些著名學(xué)者發(fā)表一系列論文開始，開創(chuàng)了關(guān)系數(shù)據(jù)庫及關(guān)系數(shù)據(jù)庫的理論研究的一個時代，這一理論直到80年代初才算基本完成，其標(biāo)志是Ullman1980年發(fā)表了他的專著Principles of Database Sys-terns。這之后，Datc和Maier相繼發(fā)表了相關(guān)專著，促進(jìn)了關(guān)系數(shù)據(jù)庫理論的發(fā)展。關(guān)系數(shù)據(jù)庫理論中最重要的組成部分是數(shù)據(jù)依賴及其相關(guān)性質(zhì)和關(guān)系規(guī)范化理論。迄今為止，這些問題的研究已經(jīng)取得了很多重要成果。數(shù)據(jù)依賴作為對數(shù)據(jù)固有語義的一種描述形式被引入。一些重要的數(shù)據(jù)依賴類型，如FD、WVD、JD等被深入地研究過，若干描述數(shù)據(jù)依賴之間的邏輯蘊(yùn)涵關(guān)系的形式公理系統(tǒng)被提出。

內(nèi)容概要

本書是在作者三十余年來對關(guān)系數(shù)據(jù)庫數(shù)據(jù)組織理論研究的基礎(chǔ)上撰寫的。書中系統(tǒng)論述和分析了數(shù)據(jù)庫數(shù)據(jù)組織理論以及作者提出的若干新的概念、方法、算法。    本書共分12章。主要內(nèi)容包括：基于超圖、線圖的無α環(huán)、無β環(huán)、無γ環(huán)的特性。特別提出了作為本書討論的核心概念——歸并依賴集。在深入研究這個概念的基礎(chǔ)上給出了歸并依賴集的最小歸并依賴集、蘊(yùn)涵左部集、擴(kuò)展左部集、全部對稱左部集等相關(guān)概念，對歸并依賴集的性質(zhì)進(jìn)行系統(tǒng)的研究。關(guān)聯(lián)度、關(guān)聯(lián)集是另一類重要概念。在深入討論中還給出了有、無內(nèi)部沖突，左、右部沖突，弱左、右部沖突，廣義左、右部沖突，集間沖突，集內(nèi)沖突，強(qiáng)左部沖突，強(qiáng)無沖突MVD集，最小廣義特征集等概念。在此基礎(chǔ)上分別討論了在有、無內(nèi)部沖突環(huán)境下的無α環(huán)、無β環(huán)、無γ環(huán)的數(shù)據(jù)庫模式分解。    本書可作為計算機(jī)科學(xué)與技術(shù)學(xué)科、數(shù)據(jù)庫相關(guān)專業(yè)的高年級本科生教材或碩士生選修課教材，也可供從事上述領(lǐng)域研究的博士生、科研人員及工程技術(shù)人員參考。

書籍目錄

前言第1章  基本知識  1.1  關(guān)系模型和關(guān)系模式    1.1.1  函數(shù)依賴及相關(guān)理論概念    1.1.2  多值依賴及相關(guān)理論概念  1.2  候選關(guān)鍵字    1.2.1  候選關(guān)鍵字約束    1.2.2  求關(guān)系模式的一個候選關(guān)鍵字    1.2.3  求全部候選關(guān)鍵字一一替換法  1.3  邏輯蘊(yùn)涵和覆蓋    1.3.1  邏輯蘊(yùn)涵    1.3.2  覆蓋與等價  1.4  范式與規(guī)范化  1.5  聯(lián)接依賴的性質(zhì)和判定問題    1.5.1  聯(lián)接依賴的概念    1.5.2  全生成元組器    1.5.3  聯(lián)接依賴的種類和聯(lián)接表    1.5.4  聯(lián)接依賴性質(zhì)的判定  1.6  符號表和追蹤算法    1.6.1  符號表    1.6.2  追蹤算法  1.7  小結(jié)第2章  數(shù)據(jù)庫模式環(huán)的種類與特性  2.1  無環(huán)數(shù)據(jù)庫的良好的特性  2.2  超圖和線圖    2.2.1  超圖及與超圖相關(guān)概念    2.2.2  無環(huán)的超圖和線圖的概念    2.2.3  無α環(huán)的判定——Graham算法    2.2.4  化簡一致超圖的性質(zhì)    2.2.5  聯(lián)接樹順序表達(dá)式    2.2.6  FD超圖  2.3  超圖中各種環(huán)的定義及關(guān)系    2.3.1  超圖中各種環(huán)的定義    2.3.2  超圖中各種環(huán)的關(guān)系  2.4  超圖有α環(huán)的特性  2.5  超圖有β環(huán)的特性  2.6  超圖有γ環(huán)的特性  2.7  小結(jié)第3章  函數(shù)依賴集F有內(nèi)部沖突的判定  3.1  FD集F的歸并依賴集的相關(guān)概念  3.2  FD集F的歸并依賴集的求解算法  3.3  FD集F的最小歸并依賴集的求解算法  3.4  二元組集合閉包B+求解算法  3.5  函數(shù)依賴集F有內(nèi)部沖突的判定  3.6  歸并FD超圖表示及構(gòu)造    3.6.1  歸并準(zhǔn)路與準(zhǔn)環(huán)    3.6.2  超圖構(gòu)造算法  3.7  歸并FD超圖存在內(nèi)部沖突的條件和算法    3.7.1  歸并FD超圖存在內(nèi)部沖突的條件    3.7.2  歸并FD超圖存在內(nèi)部沖突的檢測算法  3.8  小結(jié)第4章  無內(nèi)部沖突環(huán)境下的無α環(huán)分解  4.1  歸并依賴集存在弱左、右部沖突判定  4.2  最小歸并依賴集的關(guān)聯(lián)度  4.3  無內(nèi)部沖突滿足P3的無α環(huán)分解條件  4.4  無內(nèi)部沖突滿足P3的無α環(huán)分解算法  4.5  冗余屬性的確定  4.6  無內(nèi)部沖突滿足PEK無α環(huán)分解    4.6.1  初等關(guān)鍵字范式的相關(guān)概念    4.6.2  滿足初等關(guān)鍵字范式的分解    4.6.3  滿足PEK無α環(huán)分解  4.7  無內(nèi)部沖突滿足Ps的無α環(huán)分解    4.7.1  簡單范式及相關(guān)概念    4.7.2  滿足簡單范式的分解    4.7.3  滿足P3的無α環(huán)分解  4.8  小結(jié)第5章  有內(nèi)部沖突的廣義左、右部沖突的性質(zhì)和判定  5.1  歸并依賴集的對稱左部屬性集  5.2  有內(nèi)部沖突的廣義左、右部沖突的性質(zhì)    5.2.1  有內(nèi)部沖突的廣義左部沖突的性質(zhì)    5.2.2  有內(nèi)部沖突的廣義右部沖突的性質(zhì)  5.3  有內(nèi)部沖突的廣義左、右部沖突判定算法  5.4  小結(jié)第6章  F有內(nèi)部沖突滿足無α環(huán)分解  6.1  有內(nèi)部沖突滿足P3的無α環(huán)分解條件  6.2  F有內(nèi)部沖突滿足P3的無α環(huán)分解算法  6.3  小結(jié)第7章  多值依賴環(huán)境下的無α環(huán)分解  7.1  滿足無損聯(lián)接和4NF的分解    7.1.1  保證無損聯(lián)接和4NF分解的有關(guān)定理    7.1.2  產(chǎn)生4NF分解的思想和算法  7.2  MVD集M無沖突的判定    7.2.1  無α環(huán)聯(lián)接依賴與無沖突多值依賴集的等價性    7.2.2  MVD集M沖突判定算法  7.3  混合依賴集環(huán)境下的數(shù)據(jù)庫模式無α環(huán)分解問題    7.3.1  混合依賴集D的生成多值依賴集    7.3.2  混合依賴集環(huán)境下的數(shù)據(jù)庫模式無α環(huán)分解  7.4  關(guān)系數(shù)據(jù)庫模式環(huán)境的判定和泛分解問題的討論    7.4.1  數(shù)據(jù)依賴環(huán)境的判定    7.4.2  關(guān)系數(shù)據(jù)庫模式的泛分解算法  7.5  小結(jié)第8章  歸并依賴集左部集分析  8.1  歸并依賴集左部屬性集分析及求解算法    8.1.1  一個歸并依賴的擴(kuò)展左部集求法    8.1.2  歸并依賴集的左部聯(lián)合集的求解算法    8.1.3  蘊(yùn)涵左部集的求解  8.2  FD集F的歸并依賴集集間聯(lián)系與沖突    8.2.1  歸并依賴集集間沖突    8.2.2  歸并依賴集集內(nèi)沖突    8.2.3  歸并依賴集強(qiáng)左部沖突和幾個沖突的區(qū)別  8.3  小結(jié)第9章  無內(nèi)部沖突環(huán)境下的無β環(huán)分解  9.l  基于線圖的無β環(huán)判定    9.1.1  線圖是三角化的相關(guān)問題    9.1.2  線圖是β環(huán)判定算法  9.2  無內(nèi)部沖突滿足P3的無犀環(huán)分解條件    9.2.1  無弱左部沖突、弱右部沖突D中任意兩個歸并依賴間的關(guān)系    9.2.2  無內(nèi)部沖突滿足P3的無β環(huán)分解條件  9.3  F無內(nèi)部沖突滿足P3的無β環(huán)分解算法    9.3.1  主歸并依賴沖突判定算法    9.3.2  無內(nèi)部沖突滿足P3的無β環(huán)分解算法  9.4  無內(nèi)部沖突滿足PBC-的無β環(huán)分解問題  9.5  有內(nèi)部沖突滿足P3的無β環(huán)分解    9.5.1  環(huán)沖突及弱廣義、歸并廣義左部沖突的判定算法    9.5.2  有內(nèi)部沖突的滿足P3無β環(huán)分解存在條件    9.5.3  有內(nèi)部沖突的滿足P3無β環(huán)分解算法  9.6  小結(jié)第10章  MVD無內(nèi)部沖突環(huán)境下的無β環(huán)分解  10.1  MVD無沖突滿足無β環(huán)數(shù)據(jù)庫模式分解    10.1.1  無廖環(huán)且滿足P4-的分解條件    10.1.2  MVD集的化簡與等價    10.1.3  嚴(yán)格無沖突的算法  10.2  混合依賴環(huán)境下滿足P4-無β環(huán)數(shù)據(jù)庫模式研究    10.2.1  混合依賴集的表示及化簡    10.2.2  混合依賴環(huán)境下滿足P4-且無β環(huán)分解的條件    10.2.3  混合依賴環(huán)境下的分解算法  10.3  小結(jié)第11章  無丫環(huán)無損聯(lián)接的4NF數(shù)據(jù)庫模式R分解  11.1  MVD環(huán)境下7環(huán)數(shù)據(jù)庫模式的存在性  11.2  基于強(qiáng)無沖突MVD集的數(shù)據(jù)庫模式的特性    11.2.1  基于Nα-Decomposition強(qiáng)無沖突MVD集分解特性    11.2.2  強(qiáng)無沖突MVD集數(shù)據(jù)庫模式分解線圖的特性  11.3  無γ環(huán)的數(shù)據(jù)庫模式的特性    11.3.1  無γ環(huán)的數(shù)據(jù)庫模式的線圖特性    11.3.2  無γ環(huán)的數(shù)據(jù)庫模式的聯(lián)接樹的特性  11.4  MVD環(huán)境下產(chǎn)生無γ環(huán)數(shù)據(jù)庫模式的條件  11.5  強(qiáng)無沖突的覆蓋存在性    11.5.1  化簡全依賴集的邏輯等價性    11.5.2  強(qiáng)無沖突的覆蓋存在的條件  11.6  無γ環(huán)無損聯(lián)接的4NF數(shù)據(jù)庫模式尺分解    11.6.1  無γ環(huán)模式判定    11.6.2  化簡全依賴集無沖突判定    11.6.3  強(qiáng)無沖突覆蓋的判定和滿足無γ環(huán)P4-分解算法  11.7  小結(jié)第12章  最小廣義特征集與無γ環(huán)分解的相關(guān)性  12.1  最小廣義特征集    12.1.1  最小廣義特征集和廣義特征集的區(qū)別    12.1.2  無沖突MVD集M和FD集F蘊(yùn)涵關(guān)系  12.2  最小廣義特征集和MVD相交性理論    12.2.1  最小廣義特征集和分割的關(guān)系    12.2.2  最小廣義特征集和MVD相交性關(guān)系  12.3  無沖突的最小廣義特征集    12.3.1  無沖突的最小廣義特征集特性    12.3.2  無γ環(huán)的滿足BCNF的數(shù)據(jù)庫模式分解  12.4  最小覆蓋和最小廣義特征集    12.4.1  最小覆蓋和相容性的關(guān)系    12.4.2  最小覆蓋和最小廣義特征集的關(guān)系  12.5  滿足無γ環(huán)的BCNF數(shù)據(jù)庫模式的分解算法    12.5.1  歸并依賴集的可不分裂集生成算法    12.5.2  歸并依賴集D的相容集的相關(guān)算法    12.5.3  滿足無γ環(huán)的BCNF數(shù)據(jù)庫模式的相關(guān)算法  12.6  小結(jié)參考文獻(xiàn)

章節(jié)摘錄

插圖：第2章 數(shù)據(jù)庫模式環(huán)的種類與特性從關(guān)系數(shù)據(jù)庫問世以來，數(shù)據(jù)庫中模式分解的問題一直是關(guān)系數(shù)據(jù)庫研究人員的重點問題，即在相應(yīng)的條件下，得到品質(zhì)優(yōu)良的模式分解。多年來，許多研究者的研究成果表明：對于純FD環(huán)境下的數(shù)據(jù)庫模式分解都可以得到同時滿足無損聯(lián)接性、保持函數(shù)依賴性、3NF或BCNF這三個特性的數(shù)據(jù)庫模式分解。2.1 無環(huán)數(shù)據(jù)庫的良好的特性自從Beeri，F(xiàn)agin等提出的無α環(huán)數(shù)據(jù)庫模式以來，許多研究人員的成果表明無α環(huán)數(shù)據(jù)庫模式是一個重要的級別，它可以從許多不同的角度來定義和表示，而每一種表示方式都對應(yīng)了一些良好的特性。許多在有。環(huán)數(shù)據(jù)庫模式中出現(xiàn)的不良的異?，F(xiàn)象，在無。環(huán)數(shù)據(jù)庫模式中是不存在的。而且許多在有α環(huán)模式中要解決的問題是不存在多項式時間的解決算法的，是NP完全的問題。在無α環(huán)模式中卻存在著多項式時間的解決算法，比如說總體一致性問題。另外，對于無。環(huán)數(shù)據(jù)庫模式，在查詢時無論對于時間性還是空間性都存在一個較佳的查詢路徑，這尤其表現(xiàn)在當(dāng)需要幾個關(guān)系模式的聯(lián)接來完成一個查詢時。上述幾點充分說明了無α環(huán)數(shù)據(jù)模式的設(shè)計具有重要意義。經(jīng)研究表明，無環(huán)數(shù)據(jù)庫模式能夠充分體現(xiàn)客觀現(xiàn)實世界。因而，人們把模式分解的無α環(huán)特性作為數(shù)據(jù)庫模式分解的一種優(yōu)良特性。

編輯推薦

《數(shù)據(jù)庫數(shù)據(jù)組織無環(huán)性理論》可作為計算機(jī)科學(xué)與技術(shù)學(xué)科、數(shù)據(jù)庫相關(guān)專業(yè)的高年級本科生教材或碩士生選修課教材，也可供從事上述領(lǐng)域研究的博士生、科研人員及工程技術(shù)人員參考。

圖書封面

評論、評分、閱讀與下載

---

    數(shù)據(jù)庫數(shù)據(jù)組織無環(huán)性理論 PDF格式下載

---