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

前言

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

內(nèi)容概要

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

書(shū)籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

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

---