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

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

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

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

4、構(gòu)：其中，元素ai的數(shù)據(jù)類型可以是整數(shù)、浮點數(shù)、字符或類；n是線性表的元素個數(shù)，稱為線性長度。若n=0,則為空表；若n0,ai(0in-1)有且僅有一個前驅(qū)元素a(i-1),沒有后繼元素a(i+1),a0沒有前驅(qū)元素，a(n-1)沒有后繼元素線性表的存儲結(jié)構(gòu)（順序存儲、鏈?zhǔn)酱鎯Γ┚€性表的順序存儲結(jié)構(gòu)使用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存放次序與它們在線性表中的邏輯次序相同，即元素ai與其前驅(qū)a(i-1)及后繼a(i+1)的存儲位置相鄰。順序存儲的線性表也稱為順序表。線性表的鏈?zhǔn)酱鎯κ怯萌舾傻刂贩稚⒌拇鎯卧鎯?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)與存儲結(jié)構(gòu)的關(guān)系：數(shù)組采用的是順序存儲結(jié)構(gòu)，即使用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存放次序與它們在線性表中的邏輯次序相同，即元素ai與其前驅(qū)a(i-1)及后繼a(i+1)的存儲位置相鄰。所以數(shù)組的存儲結(jié)構(gòu)表現(xiàn)其存儲結(jié)構(gòu)。4） 棧是一種特殊的線

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

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

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

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

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

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

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

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

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

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

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

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

19、及到調(diào)整鏈接指針。關(guān)系關(guān)系模型與層次模型和網(wǎng)狀模型相比有著本質(zhì)的差別，它是用二維表格來表示實體及其相互之間的聯(lián)系。一個關(guān)系就是沒有重復(fù)行和重復(fù)列的二維表，二維表的每一行在關(guān)系中稱為元組，每一列在關(guān)系中稱為屬性。學(xué)生關(guān)系的每一行代表一個學(xué)生的記錄，每一列代表學(xué)生記錄的一個字段。屬性個數(shù)（n）稱為關(guān)系的元。關(guān)系、關(guān)系模式、關(guān)系數(shù)據(jù)庫模式、關(guān)系數(shù)據(jù)庫的定義（關(guān)系、元組、屬性、域、關(guān)鍵字、數(shù)據(jù)項）關(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、績登記表，定義關(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é)生選修課成績登記表，定義關(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ù)庫：n 關(guān)系數(shù)據(jù)庫基

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

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

23、與或?qū)ｉT的關(guān)系運算符%廣義笛卡爾積選擇投影連接除比較運算符=大于等于大于小于等于小于等于不等于1.選擇（selection）:對關(guān)系而言，選擇是從行的角度取關(guān)系的子集 公式表示:RF或F(R)=t|tR F(t)=True 公式的含義：R中使布爾函數(shù)為真的元組集，F(xiàn)為布爾函數(shù)，即限定條件 F的基本形式為：x1y1x2y2,其中為比較運算符，為邏輯運算符，x1,y1是屬性名或常量，屬性名也可用序號表示例： 5=IS(student) 或 student5=ISSage19(student) 或 studentSage192.投影（projection）:對關(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)屬性都來自相同的域），并的結(jié)果與R、S也是同類關(guān)系n R和S 具有相同的目n 相應(yīng)的屬性取自同一個域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)的屬性取自同一個域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，其中每一個元素(d1，d2，dn)稱作一個n元組（n-tuple）或簡稱元組，它的每個元素di取自對應(yīng)的集合Di。 元組中的每一個值di稱作一個分量（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 公式的含義：從兩個關(guān)系的笛卡爾積中選取屬性間滿足一定條件的元組 4） 關(guān)系數(shù)據(jù)庫基本概念：函數(shù)依賴的基本概念定義1 對于R中屬性X的任何一個具體值，Y僅有唯一的具體值與之對應(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，所以