浙江省計(jì)算機(jī)三級(jí)數(shù)據(jù)庫(kù)復(fù)習(xí)資料

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)1） 數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語(yǔ)：數(shù)據(jù)是描述客觀事物的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)接受的各種符號(hào)集合的統(tǒng)稱。表示一個(gè)事物的一組數(shù)據(jù)稱為一個(gè)數(shù)據(jù)元素，數(shù)據(jù)元素是數(shù)據(jù)的基本單位。它可以是一個(gè)不可分割的原子項(xiàng)，也可以由多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)類型是指一個(gè)類型和定義在這個(gè)類型上的操作集合。數(shù)據(jù)結(jié)構(gòu)（data structure）指數(shù)據(jù)元素之間存在的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來(lái)表示，常被稱為數(shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同數(shù)學(xué)特性，數(shù)據(jù)結(jié)構(gòu)可分為三種：線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖，其中樹(shù)結(jié)構(gòu)和圖又稱為非線性結(jié)構(gòu)

2、。P2數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示或?qū)崿F(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系角度觀察數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立與計(jì)算機(jī)的。而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本形式有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)四種算法是一個(gè)有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類型問(wèn)題的操作序列。算法分析主要包含時(shí)間代價(jià)和空間代價(jià)兩個(gè)方面。時(shí)間代價(jià)就是當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法實(shí)現(xiàn)運(yùn)行時(shí)所消耗的時(shí)間，也以某種單位由f(1)增至f(n)，則稱該算法的時(shí)間

3、代價(jià)為f(n)?？臻g代價(jià)就是當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，解決該問(wèn)題的算法實(shí)現(xiàn)運(yùn)行時(shí)所消耗的空間，也以某種單位由g(1)增至g(n)，則稱該算法的空間代價(jià)為g(n)。算法的時(shí)間及空間復(fù)雜性 度量算法的時(shí)間效率算法的時(shí)間效率指算法的執(zhí)行時(shí)間隨問(wèn)題規(guī)模的增長(zhǎng)而增長(zhǎng)的趨勢(shì)，通常采用時(shí)間復(fù)雜度來(lái)度量算法的時(shí)間效率。T(n)=O(f(n) 度量算法的空間效率空間復(fù)雜度指算法在執(zhí)行時(shí)為解決問(wèn)題所需要的額外內(nèi)存空間，不包括輸入數(shù)據(jù)所占用的存儲(chǔ)空間。 S(n)=O(f(n) 2） 基本數(shù)據(jù)結(jié)構(gòu)及其操作：線性表是由n(n=0)個(gè)類型相同的數(shù)據(jù)元素a0,a1,a(n-1)組成的有限序列。P36線性表的邏輯結(jié)

4、構(gòu)：其中，元素ai的數(shù)據(jù)類型可以是整數(shù)、浮點(diǎn)數(shù)、字符或類；n是線性表的元素個(gè)數(shù)，稱為線性長(zhǎng)度。若n=0,則為空表；若n0,ai(0in-1)有且僅有一個(gè)前驅(qū)元素a(i-1),沒(méi)有后繼元素a(i+1),a0沒(méi)有前驅(qū)元素，a(n-1)沒(méi)有后繼元素線性表的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）線性表的順序存儲(chǔ)結(jié)構(gòu)使用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存放次序與它們?cè)诰€性表中的邏輯次序相同，即元素ai與其前驅(qū)a(i-1)及后繼a(i+1)的存儲(chǔ)位置相鄰。順序存儲(chǔ)的線性表也稱為順序表。線性表的鏈?zhǔn)酱鎯?chǔ)是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必

5、須采用附加信息表示數(shù)據(jù)元素之間的順序關(guān)系。插入、刪除操作單鏈表的插入操作： 空表插入/頭插入if(head=null) head=new Node(x,null); /空表插入else Nodeq= new Node(x,null); /頭插入 q.next=head; head=q; 中間插入/尾插入Nodeq= new Node(x,null); q.next=p.next; p.next=q;單鏈表的刪除操作： 頭刪除head = head.next; 中間/尾刪除if (p.next!=null) p.next = p.next.next;雙鏈表的插入操作：q = new DLinkN

6、ode(x);q.prev = p.prev;q.next = p;p.prev.next = q;p.prev = q;雙鏈表的刪除操作：p.prev.next = p.next;if (p.next!=null) (p.next).prev = p.prev;3） 數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。數(shù)組邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系：數(shù)組采用的是順序存儲(chǔ)結(jié)構(gòu)，即使用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存放次序與它們?cè)诰€性表中的邏輯次序相同，即元素ai與其前驅(qū)a(i-1)及后繼a(i+1)的存儲(chǔ)位置相鄰。所以數(shù)組的存儲(chǔ)結(jié)構(gòu)表現(xiàn)其存儲(chǔ)結(jié)構(gòu)。4） 棧是一種特殊的線

7、性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。允許操作的一段稱為棧頂，不允許操作的一端稱為棧底。棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒(méi)有元素的棧稱為空棧。棧的插入和刪除只允許在棧頂進(jìn)行，每次入棧即成為當(dāng)前棧頂元素，每次出棧元素總是最后一個(gè)入棧元素，因此棧也稱為后進(jìn)先出表。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)綏?。進(jìn)棧、出棧操作：鏈?zhǔn)綏Ｊ褂脝捂湵砑纯?，不需要使用循環(huán)鏈表或雙鏈表，并且頭結(jié)點(diǎn)的作用不明顯。采用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧。單鏈表的第一個(gè)結(jié)點(diǎn)為站定結(jié)點(diǎn)，設(shè)top指向棧頂結(jié)點(diǎn)，入棧操作是在當(dāng)前棧頂結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；出棧操作是刪除棧頂

8、結(jié)點(diǎn)并返回棧頂元素值，再使top指向新的棧頂結(jié)點(diǎn)。5） 隊(duì)列是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。允許入隊(duì)的一端稱為隊(duì)尾，允許出隊(duì)的一端稱為隊(duì)頭。向隊(duì)列中插入元素的過(guò)程成為入隊(duì)，刪除元素的過(guò)程成為出隊(duì)。沒(méi)有元素的隊(duì)列稱為空隊(duì)列。由于插入和刪除操作分別在隊(duì)尾和隊(duì)頭進(jìn)行，最先入隊(duì)的元素總是最先出隊(duì)，因此隊(duì)列也稱為先進(jìn)先出表。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序隊(duì)列，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)疥?duì)列。循環(huán)隊(duì)列：如果循環(huán)使用順序隊(duì)列的連續(xù)存儲(chǔ)單元，則將順序隊(duì)列設(shè)計(jì)成在邏輯上首尾相接的循環(huán)結(jié)構(gòu)，稱為順序循環(huán)隊(duì)列。進(jìn)隊(duì)、出隊(duì)操作：以不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)鏈?zhǔn)疥?duì)列。設(shè)指針fro

9、nt和rear分別指向隊(duì)頭和隊(duì)尾結(jié)點(diǎn)，入隊(duì)操作將結(jié)點(diǎn)鏈在隊(duì)尾結(jié)點(diǎn)之后，并使front指向新的隊(duì)尾結(jié)點(diǎn)；出隊(duì)操作，當(dāng)隊(duì)列不空時(shí)，取得隊(duì)頭結(jié)點(diǎn)值，刪除該節(jié)點(diǎn)，并使front指向后續(xù)結(jié)點(diǎn)。6） 二叉樹(shù)是n（n=0）個(gè)結(jié)點(diǎn)組成的有限集合，n=0時(shí)稱為空二叉樹(shù)；n0的二叉樹(shù)由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的子二叉樹(shù)構(gòu)成。二叉樹(shù)也是遞歸定義的。二叉樹(shù)的性質(zhì)性質(zhì)1：若根結(jié)點(diǎn)的層次為1，則二叉樹(shù)第i層最多有2i-1（i1）個(gè)結(jié)點(diǎn)。 性質(zhì)2：在高度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)（k0）。 性質(zhì)3：設(shè)一棵二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 性質(zhì)4：一棵具有n個(gè)

10、結(jié)點(diǎn)的完全二叉樹(shù)，其高度 。性質(zhì)5：一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)序號(hào)為i（0in）的結(jié)點(diǎn)，有： 若i=0，則i為根結(jié)點(diǎn)，無(wú)父母結(jié)點(diǎn)；若i0，則i的父母結(jié)點(diǎn)序號(hào)為。 若2i+1n，則i的左孩子結(jié)點(diǎn)序號(hào)為2i+1；否則i無(wú)左孩子。 若2i+2n，則i的右孩子結(jié)點(diǎn)序號(hào)為2i+2；否則i無(wú)右孩子。 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1. 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹(shù)跟滿二叉樹(shù)。2. 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷是按照一定規(guī)則和次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。雖然二叉樹(shù)是非線性結(jié)構(gòu)，但遍歷二叉樹(shù)訪問(wèn)結(jié)點(diǎn)的次序是線性的，而且訪問(wèn)的規(guī)則和次序不止一種。二叉樹(shù)的遍歷規(guī)則有孩

11、子優(yōu)先和兄弟優(yōu)先。孩子優(yōu)先：先根次序：訪問(wèn)根結(jié)點(diǎn)，遍歷左子樹(shù)，遍歷右子樹(shù)。中根次序：遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)。后根次序：遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)二叉排序樹(shù)又稱二叉查找樹(shù)，它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（3）左、右子樹(shù)也分別為二叉排序樹(shù)。哈夫曼樹(shù) 定義為帶權(quán)外路徑長(zhǎng)度最短的二叉樹(shù)路徑長(zhǎng)度：從根結(jié)點(diǎn)到所有結(jié)點(diǎn)的路徑長(zhǎng)度之和(a)、(b)、（c）、(d)的路徑長(zhǎng)度為1x2+2x2+3x2=12外路徑長(zhǎng)度：從根結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之

12、和(a)、(b)、（c）、(d)的外路徑長(zhǎng)度為2+3x2+1=9從根到X結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度是X結(jié)點(diǎn)的權(quán)值與從根到X結(jié)點(diǎn)路徑長(zhǎng)度的乘積。所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱為二叉樹(shù)的帶權(quán)外路徑長(zhǎng)度。二叉樹(shù)的帶權(quán)外路徑長(zhǎng)度7） 檢索方法：（P259）順序查找算法描述為：從線性表的一端開(kāi)始，依次將每個(gè)元素的關(guān)鍵字與給定值進(jìn)行比較，若有相等者，則查找成功；否則比較繼續(xù)，直到比較完所有元素，仍未有相等者，則查找不成功，給出結(jié)果信息。平均查找長(zhǎng)度為（n+1）/2,查找一個(gè)元素的平均比較次數(shù)為n，查找失敗需比較n+1次，時(shí)間復(fù)雜度為O(n)。查找成功的平均查找長(zhǎng)度： 查找失敗的平均查找長(zhǎng)度：（P262）二分查找

13、又叫折半查找，時(shí)間復(fù)雜度為O(log2n)。折半查找算法分析8） 排序方法：直接插入排序總的關(guān)鍵碼比較次數(shù)為n2/4，總的記錄移動(dòng)個(gè)數(shù)也約為n2/4；二分法插入排序關(guān)鍵碼比較次數(shù)為O(nlog2n),記錄移動(dòng)個(gè)數(shù)為O(n2)；shell排序法的關(guān)鍵碼比較次數(shù)和記錄移動(dòng)個(gè)數(shù)均為n1.3左右。冒泡排序的最壞時(shí)間復(fù)雜度為O(n2),最好的時(shí)間復(fù)雜度為O(n)，算法的平均時(shí)間復(fù)雜度為O(n2)?？焖倥判虻淖顗臅r(shí)間為O(n2)，平均時(shí)間復(fù)雜度為(nlgn)。插入排序：每趟將一個(gè)元素，按其關(guān)鍵字大小插入到它前面已排序的子序列中，使得插入后的子序列仍是排序的，依此重復(fù)，直到全部元素插入完畢。直接插入排序數(shù)據(jù)

14、序列已排序（最好情況）的時(shí)間復(fù)雜度為O（n）數(shù)據(jù)序列反序排列（最壞情況）的時(shí)間復(fù)雜度為O（n的平方）數(shù)據(jù)序列隨機(jī)排列的時(shí)間復(fù)雜度為O（n的平方）折半插入排序希爾排序交換排序冒泡排序的基本思想是：比較相鄰兩個(gè)元素的關(guān)鍵字值，如果反序，則交換。若按升序排序，每趟將被掃描的數(shù)據(jù)序列中的最大元素交換到最后位置，就像氣泡從水里冒出來(lái)一樣?？焖倥判蚴且环N分區(qū)交換排序算法?？焖倥判虻幕舅枷胧?在數(shù)據(jù)序列中選擇一個(gè)值作為比較的基準(zhǔn)值，每趟從數(shù)據(jù)序列的兩端開(kāi)始交替進(jìn)行，將小于基準(zhǔn)值的元素交換到序列前端，見(jiàn)大于基準(zhǔn)值的元素交換到序列后端，介于兩者之間的位置則成為基準(zhǔn)值的最終位置。同時(shí)，序列被劃分成兩個(gè)子序列，再

15、用同樣的方法分別對(duì)兩個(gè)子序列進(jìn)行排序，直到子序列的長(zhǎng)度為1，則完成排序。選擇排序直接選擇排序的基本思想是：第一趟從n個(gè)元素的數(shù)據(jù)序列中選出關(guān)鍵字最?。ɑ蜃畲螅┑脑夭⒎诺阶钋埃ɑ蜃詈螅┪恢茫乱惶嗽?gòu)膎-1個(gè)元素中選出最?。ù螅┑脑夭⒎诺酱吻埃ê螅┪恢?。以此類推，經(jīng)過(guò)n-1趟完成排序堆排序（1）創(chuàng)建最小堆（2）堆排序歸并排序數(shù)據(jù)庫(kù)系統(tǒng) 1） 數(shù)據(jù)庫(kù)的基本概念：信息是經(jīng)過(guò)加工處理并對(duì)人類社會(huì)實(shí)踐和生產(chǎn)活動(dòng)產(chǎn)生決策影響的數(shù)據(jù)。數(shù)據(jù)是人們用于記錄事物情況的物理符號(hào)。為了描述客觀事物而用到的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的符號(hào)都可以看作是數(shù)據(jù)。數(shù)據(jù)處理是指將數(shù)據(jù)轉(zhuǎn)換成信息的過(guò)程。

16、它包括對(duì)數(shù)據(jù)的收集、存儲(chǔ)、分類、計(jì)算、加工、檢索和傳輸?shù)纫幌盗谢顒?dòng)。數(shù)據(jù)庫(kù)系統(tǒng)的組成與結(jié)構(gòu)數(shù)據(jù)庫(kù)系統(tǒng)是由計(jì)算機(jī)系統(tǒng)、數(shù)據(jù)庫(kù)及其描述機(jī)構(gòu)、數(shù)據(jù)庫(kù)管理系統(tǒng)和有關(guān)人員組成。考察數(shù)據(jù)庫(kù)系統(tǒng)的結(jié)構(gòu)可以有多種不同的層次或不同的角度。從數(shù)據(jù)管理系統(tǒng)的角度看，數(shù)據(jù)庫(kù)通常采用三級(jí)模式結(jié)構(gòu)，這是數(shù)據(jù)庫(kù)管理系統(tǒng)的內(nèi)部結(jié)構(gòu)；從數(shù)據(jù)庫(kù)最終用戶的角度看，數(shù)據(jù)庫(kù)系統(tǒng)的結(jié)構(gòu)可分為集中式結(jié)構(gòu)、分布式結(jié)構(gòu)、客戶/服務(wù)器結(jié)構(gòu)、并型結(jié)構(gòu)，這是數(shù)據(jù)庫(kù)系統(tǒng)的外部的體系結(jié)構(gòu)。這里主要介紹數(shù)據(jù)庫(kù) 系統(tǒng)的內(nèi)部結(jié)構(gòu)當(dāng)前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)采用的三級(jí)模式結(jié)構(gòu)。數(shù)據(jù)庫(kù)系統(tǒng)三級(jí)模式結(jié)構(gòu)的概念和原理及其數(shù)據(jù)獨(dú)立性它包括外模式、模式和內(nèi)模式 。模式：是整個(gè)數(shù)

17、據(jù)庫(kù)當(dāng)中所有實(shí)體和關(guān)系的集合，是所有用戶的公共數(shù)據(jù)視圖，與應(yīng)用無(wú)關(guān)。每個(gè)數(shù)據(jù)庫(kù)中只有一個(gè)模式，也稱邏輯模式。外模式：是模式的一個(gè)子集，或是模式的一個(gè)局部表現(xiàn)形態(tài)。內(nèi)模式：也叫存儲(chǔ)模式，是對(duì)模式的數(shù)據(jù)及數(shù)據(jù)的定義內(nèi)容進(jìn)行組織、存儲(chǔ)的表達(dá)形式，在什么地方存儲(chǔ)、如何存儲(chǔ)是內(nèi)模式要解決的內(nèi)容根據(jù)各類人員與數(shù)據(jù)庫(kù)的不同關(guān)系，可把視圖（所謂視圖是指觀察、認(rèn)識(shí)和理解數(shù)據(jù)的范圍、角度和方法）分為三種： 對(duì)應(yīng)于用戶的外部視圖 對(duì)應(yīng)于應(yīng)用程序員的概念視圖 對(duì)應(yīng)于系統(tǒng)程序員的內(nèi)部視圖2） 數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)模型：常見(jiàn)的數(shù)據(jù)模型：層次數(shù)據(jù)模型、網(wǎng)狀數(shù)據(jù)模型、關(guān)系數(shù)據(jù)模型。層次：通過(guò)樹(shù)形結(jié)構(gòu)表示實(shí)體及聯(lián)系。如描述學(xué)校管理

18、機(jī)構(gòu)。每個(gè)結(jié)點(diǎn)表示一個(gè)實(shí)體（型），箭頭表示實(shí)體（型）間的聯(lián)系（由父到子）。層次數(shù)據(jù)模型主要特點(diǎn)：有且僅有一個(gè)根結(jié)點(diǎn)；每個(gè)非根結(jié)點(diǎn)有且僅有一個(gè)父(直接上層)結(jié)點(diǎn)。它最適合表示實(shí)體的一對(duì)多聯(lián)系。網(wǎng)狀：通過(guò)網(wǎng)狀結(jié)構(gòu)表示實(shí)體及聯(lián)系?！熬W(wǎng)”中每個(gè)結(jié)點(diǎn)表示一個(gè)實(shí)體(型)，結(jié)點(diǎn)之間箭頭表示實(shí)體(型)間的聯(lián)系。網(wǎng)狀數(shù)據(jù)模型主要特點(diǎn)：網(wǎng)狀數(shù)據(jù)模型可能有多個(gè)根結(jié)點(diǎn)，某些非根結(jié)點(diǎn)可能有多個(gè)父結(jié)點(diǎn)，適合表示實(shí)體的多對(duì)多聯(lián)系。層次與網(wǎng)狀模型優(yōu)缺點(diǎn):優(yōu)點(diǎn):能直觀、形象地描述實(shí)體及其聯(lián)系，易于被人們所理解和掌握 。缺點(diǎn):數(shù)據(jù)結(jié)構(gòu)較復(fù)雜，存儲(chǔ)數(shù)據(jù)需要更多的鏈接指針；在檢索數(shù)據(jù)時(shí)，需要考慮數(shù)據(jù)的存儲(chǔ)路徑；在插入或刪除數(shù)據(jù)時(shí)，涉

19、及到調(diào)整鏈接指針。關(guān)系關(guān)系模型與層次模型和網(wǎng)狀模型相比有著本質(zhì)的差別，它是用二維表格來(lái)表示實(shí)體及其相互之間的聯(lián)系。一個(gè)關(guān)系就是沒(méi)有重復(fù)行和重復(fù)列的二維表，二維表的每一行在關(guān)系中稱為元組，每一列在關(guān)系中稱為屬性。學(xué)生關(guān)系的每一行代表一個(gè)學(xué)生的記錄，每一列代表學(xué)生記錄的一個(gè)字段。屬性個(gè)數(shù)（n）稱為關(guān)系的元。關(guān)系、關(guān)系模式、關(guān)系數(shù)據(jù)庫(kù)模式、關(guān)系數(shù)據(jù)庫(kù)的定義（關(guān)系、元組、屬性、域、關(guān)鍵字、數(shù)據(jù)項(xiàng)）關(guān)系：n 關(guān)系的描述稱為關(guān)系模式，可以表示為R(U,D,DOM,F) R為關(guān)系名，U為屬性名集合，D為域集合，DOM為屬性向域的映像集合，F(xiàn)為屬性間的依賴關(guān)系集合n 關(guān)系模式是型，關(guān)系是值n 例：學(xué)生選修課成

20、績(jī)登記表，定義關(guān)系模式SC如下：SC（sno,cno,grade,N(6),N(3),(sno,N(6),(cno,N(3),(grade,N(3),(sno,cno)grade）關(guān)系模式：n 關(guān)系的描述稱為關(guān)系模式，可以表示為R(U,D,DOM,F) R為關(guān)系名，U為屬性名集合，D為域集合，DOM為屬性向域的映像集合，F(xiàn)為屬性間的依賴關(guān)系集合n 關(guān)系模式是型，關(guān)系是值n 例：學(xué)生選修課成績(jī)登記表，定義關(guān)系模式SC如下：SC（sno,cno,grade,N(6),N(3),(sno,N(6),(cno,N(3),(grade,N(3),(sno,cno)grade）關(guān)系數(shù)據(jù)庫(kù)：n 關(guān)系數(shù)據(jù)庫(kù)基

21、本概念 關(guān)系數(shù)據(jù)庫(kù)就是一些相關(guān)的二維表和其他數(shù)據(jù)庫(kù)對(duì)象的集合。關(guān)系數(shù)據(jù)庫(kù)中的所有信息都存儲(chǔ)在二維表格中；一個(gè)關(guān)系數(shù)據(jù)庫(kù)可能包含多個(gè)表；除了這種二維表外，關(guān)系數(shù)據(jù)庫(kù)還包含一些其他對(duì)象，如視圖等。1關(guān)系一個(gè)關(guān)系就是一張二維表，通常將一個(gè)沒(méi)有重復(fù)行、重復(fù)列的二維表看成一個(gè)關(guān)系，每個(gè)關(guān)系都有一個(gè)關(guān)系名。2元組二維表的每一行在關(guān)系中稱為元組(Tuple)。一行描述了現(xiàn)實(shí)世界中的一個(gè)實(shí)體，或者描述了不同實(shí)體間的一種聯(lián)系。3屬性二維表的每一列在關(guān)系中稱為屬性(Attribute)，每個(gè)屬性都有一個(gè)屬性名，各個(gè)屬性的取值稱為屬性值。每個(gè)屬性有一定的取值范圍，稱為值域。4關(guān)鍵字關(guān)系中能惟一區(qū)分、確定不同元組的屬

22、性或?qū)傩越M合，稱為該關(guān)系的一個(gè)關(guān)鍵字。關(guān)鍵字又稱為鍵或碼(Key)。 碼候選碼能唯一標(biāo)示一個(gè)元組的屬性組主碼多個(gè)候選碼中的主要應(yīng)用屬性組，其中的每個(gè)屬性都稱為主屬性，不屬于任何候選碼的屬性稱為非碼屬性合成碼碼含有多個(gè)屬性外碼不是當(dāng)前關(guān)系的碼，但是其他關(guān)系中的主碼全碼所有屬性共同組成關(guān)系模式的候選碼5域（集合）域是一組具有相同數(shù)據(jù)類型的值的集合。 6.主屬性和非主屬性 定義5 設(shè)Ai是關(guān)系模式R的一個(gè)屬性，若Ai屬于R的某個(gè)候選關(guān)鍵屬性，稱Ai是R的主屬性，否則，稱Ai為非主屬性。3） 關(guān)系運(yùn)算：選擇、投影、集合并運(yùn)算、集合差運(yùn)算、笛卡兒積、連接 運(yùn)算符含義運(yùn)算符含義集合運(yùn)算符并差交邏輯運(yùn)算符非

23、與或?qū)ｉT的關(guān)系運(yùn)算符%廣義笛卡爾積選擇投影連接除比較運(yùn)算符=大于等于大于小于等于小于等于不等于1.選擇（selection）:對(duì)關(guān)系而言，選擇是從行的角度取關(guān)系的子集 公式表示:RF或F(R)=t|tR F(t)=True 公式的含義：R中使布爾函數(shù)為真的元組集，F(xiàn)為布爾函數(shù)，即限定條件 F的基本形式為：x1y1x2y2,其中為比較運(yùn)算符，為邏輯運(yùn)算符，x1,y1是屬性名或常量，屬性名也可用序號(hào)表示例： 5=IS(student) 或 student5=ISSage19(student) 或 studentSage192.投影（projection）:對(duì)關(guān)系而言，投影是從列的角度取關(guān)系的子集

24、公式表示:RA或A(R)=tA|tR 公式的含義：包含A中各屬性組的元組集 投影之后不僅取消了某些屬性列，而且還可能取消某些元組例：Sname,Sdept(student)或 studentSname,Sdept2,5(student)或 student2,5 3.集合并（union） R S=t|t R t S R、S為同類關(guān)系（關(guān)系的度相同，且相應(yīng)屬性都來(lái)自相同的域），并的結(jié)果與R、S也是同類關(guān)系n R和S 具有相同的目n 相應(yīng)的屬性取自同一個(gè)域n R - S 仍為n目關(guān)系，由屬于R而不屬于S的所有元組組成 R -S = t|tRtS 4.集合差（difference） R S=t|t R

25、 t S= t|t R t S R、S為同類關(guān)系，差的結(jié)果與R、S也是同類關(guān)系n R和S 具有相同的目n 相應(yīng)的屬性取自同一個(gè)域n R - S 仍為n目關(guān)系，由屬于R而不屬于S的所有元組組成 R -S = t|tRtS 5笛卡爾積給定一組域D1,D2，.，Dn，這些域可以完全不同，也可以部分或全部相同，D1、D2、Dn的笛卡爾積為：D1D2Dn= (d1，d2，dn)|diDi，i=1，2，n，其中每一個(gè)元素(d1，d2，dn)稱作一個(gè)n元組（n-tuple）或簡(jiǎn)稱元組，它的每個(gè)元素di取自對(duì)應(yīng)的集合Di。 元組中的每一個(gè)值di稱作一個(gè)分量（component） 若di為有限集，其基數(shù)為mi(

26、i=1,2,3n),則D1D2Dn的基數(shù)為m=mi例如，設(shè)A=1，2，B=a，b，則AB=(1，a)，(1，b)，(2，a)，(2，b)。6.連接（join）: 公式表示:R F S或RFS=trts|trR ts S F(tr,ts)=True或表示為：R A B S或RFS=trts|trR ts S trAtsB)=True 公式的含義：從兩個(gè)關(guān)系的笛卡爾積中選取屬性間滿足一定條件的元組 4） 關(guān)系數(shù)據(jù)庫(kù)基本概念：函數(shù)依賴的基本概念定義1 對(duì)于R中屬性X的任何一個(gè)具體值，Y僅有唯一的具體值與之對(duì)應(yīng)，則稱R的屬性Y函數(shù)依賴于屬性X。記為：XY，X稱為決定因素。完全函數(shù)依賴、部分函數(shù)依賴定義2 在R中，如果屬性集Y函數(shù)依賴于屬性集X，且不函數(shù)依賴于X的任意真子集，則稱Y完全函數(shù)依賴于X，記做： X Y， 否則，稱Y部分函數(shù)依賴于X，記做：X Y 。例：關(guān)系SC(Sno,Cno,Grade)中，由于Sno Grade, Cno Grade，所以