關(guān)系數(shù)據(jù)庫 關(guān)系演算

關(guān)系數(shù)據(jù)庫關(guān)系演算第一頁，共七十一頁，2022年，8月28日第一節(jié)關(guān)系代數(shù)關(guān)系1.定義：令為D1，D2，Dn的笛卡爾集。若,則稱r是D上的n元關(guān)系。例：

第二頁，共七十一頁，2022年，8月28日2.元組與分量：t表示關(guān)系中某一行，

表示這一行中的某一項(xiàng)數(shù)據(jù)。3.屬性名：對(duì)一列的命名，D1,D2,..,Dn稱為屬性的域。第三頁，共七十一頁，2022年，8月28日二.關(guān)系的集合運(yùn)算1.條件：列名相同，列數(shù)相同。每列有相同的域。2.并集：取兩關(guān)系中的所有行。例1：設(shè)R,S為如下內(nèi)容，求RS。

第四頁，共七十一頁，2022年，8月28日S：R：RS：RS：

ABC123323131ABC123321ABC123323131321ABC123第五頁，共七十一頁，2022年，8月28日3.交集：RS取關(guān)系中相同的行。如上例所示。差集：R-S取在R中且不在S中的行。例2：根據(jù)例1求R-S：得：5.交集可由差集表示：RS=R-（R-S））

ABC323131第六頁，共七十一頁，2022年，8月28日三.關(guān)系的專門運(yùn)算笛卡爾積：RS：.模式組成：由兩關(guān)系所有屬性組成，包括相同的。.元組構(gòu)成：兩關(guān)系所有元組的配對(duì)。例3.求RSABD123231ABC123323131第七頁，共七十一頁，2022年，8月28日例3的結(jié)果：

R.AR.BCS.AS.BD123123123231323123323231131123131231第八頁，共七十一頁，2022年，8月28日2.選擇運(yùn)算：（r).模式不變，滿足條件的元組。條件的構(gòu)成：比較條件：屬性與常數(shù)，屬性與屬性比較。邏輯條件：AND()，OR()，NOT().第九頁，共七十一頁，2022年，8月28日例4求下列選擇。

ABC123131ABC123第十頁，共七十一頁，2022年，8月28日3.投影：新模式為：R(A1，A2，…，An)選取新模式下的元組。例5.例6.BC2331

A1第十一頁，共七十一頁，2022年，8月28日請(qǐng)問：若要選取中R的

第一列和S的第一列，應(yīng)如何寫關(guān)系代數(shù)式。

第十二頁，共七十一頁，2022年，8月28日4.換名改變屬性或關(guān)系的名字例如：將R的屬性改為C,D,E.得：CDE123323131第十三頁，共七十一頁，2022年，8月28日5.條件連接：RS說明：模式由R，S所有屬性構(gòu)成。元組由滿足條件的元組構(gòu)成。條件：出現(xiàn)在兩關(guān)系中的屬性相比較組成。例如：R.A=S.A或加上邏輯運(yùn)算(AND)。例7.RS，其中：為R.A=S.AANDR.B>S.B。第十四頁，共七十一頁，2022年，8月28日例7的計(jì)算結(jié)果：

條件連接可由笛卡爾積表示，請(qǐng)寫出來。RS=R.AR.BR.CS.AS.BS.D131123第十五頁，共七十一頁，2022年，8月28日6.自然連接RS模式構(gòu)成：由兩模式中去掉重復(fù)屬性后的屬性組成。元組構(gòu)成：相同屬性下相等值連接而成。例8：計(jì)算RP.R:P:ABC123323131ABD124223132第十六頁，共七十一頁，2022年，8月28日例8的結(jié)果：

請(qǐng)問：若對(duì)P進(jìn)行換名再進(jìn)行自然連接，結(jié)果如何？ABCD12341312第十七頁，共七十一頁，2022年，8月28日7.除法：要求：S的屬性是R屬性的子集。計(jì)算方法：求R的原像：求所有原像包含S的x的集合。

第十八頁，共七十一頁，2022年，8月28日例9求R:S:

注意：如何求ABC123323131ABC123323C3第十九頁，共七十一頁，2022年，8月28日關(guān)系運(yùn)算的獨(dú)立性交集的不獨(dú)立性：條件連接：自然連接：RS=除法：

第二十頁，共七十一頁，2022年，8月28日除法舉例：以例9為例：S：

（圖一）(圖二）一-RABC123323C31ABC123121323321ABC121321第二十一頁，共七十一頁，2022年，8月28日四.關(guān)系代數(shù)舉例1.2.RR設(shè)關(guān)系：XS（XH，XM，SZYX，XB）XK（XH，KH，CJ）KC（KH，KM，KKXY）求下列查詢：第二十二頁，共七十一頁，2022年，8月28日。

求學(xué)號(hào)為“200201234”的學(xué)生。求信息學(xué)院學(xué)生所選課的課號(hào)，課名。求還沒有選任何課的學(xué)生學(xué)號(hào)。求同時(shí)選了兩門課以上的學(xué)生。求每門課都及格了的學(xué)生。求選了信息學(xué)院所開所有課程的學(xué)生學(xué)號(hào)。第二十三頁，共七十一頁，2022年，8月28日答案1XH=“200201234”(XS)2.3.第二十四頁，共七十一頁，2022年，8月28日答案24.

5.6.第二十五頁，共七十一頁，2022年，8月28日五.運(yùn)算樹滿足如下條件的樹稱為運(yùn)算樹：葉子結(jié)點(diǎn)為關(guān)系。其他結(jié)點(diǎn)為運(yùn)算符。例：與代數(shù)式等價(jià)的運(yùn)算樹是：第二十六頁，共七十一頁，2022年，8月28日一棵運(yùn)算數(shù)

第二十七頁，共七十一頁，2022年，8月28日擴(kuò)展的關(guān)系運(yùn)算外連接：在自然連接基礎(chǔ)上添加未被連接上的元組。ABC232123ABD124323ABCD1234232NULL32NULL3第二十八頁，共七十一頁，2022年，8月28日第二節(jié)元組謂詞演算一：謂詞與集合1命題：有確定真假值的語句。謂詞：表示論域個(gè)體性質(zhì)或關(guān)系的符號(hào)。變?cè)罕硎菊撚騻€(gè)體的變量謂詞集合：使得謂詞為真的個(gè)體集合。如：X>Y,X是素?cái)?shù)。5.約束變?cè)c自由變?cè)喝纾旱诙彭?，共七十一頁?022年，8月28日一個(gè)例子設(shè)：P表示：x是z學(xué)院的學(xué)生，c表示學(xué)生選了y這門課。第三十頁，共七十一頁，2022年，8月28日二.原子公式的構(gòu)成元組變?cè)簊,t,x,y或加下標(biāo)t1。關(guān)系謂詞：R（t),P(x),等。算術(shù)比較謂詞：s[I]與t[j]的比較。如：s[2]>t[4].第三十一頁，共七十一頁，2022年，8月28日三.合式公式的組成：1.原子公式是合式公式。邏輯運(yùn)算引入：量詞引入：元組演算的基本形式：其中：t為自由元組變?cè)?，為合式公式。第三十二頁，共七十一頁?022年，8月28日四.元組演算舉例交集：并集：差集`：笛卡爾積：第三十三頁，共七十一頁，2022年，8月28日應(yīng)用舉例：(見上節(jié)）

求學(xué)號(hào)為“200201234”的學(xué)生。2.求信息學(xué)院學(xué)生所選課的課號(hào)，課名。3.求還沒有選任何課的學(xué)生學(xué)號(hào)。4.求同時(shí)選了兩門課以上的學(xué)生。5.求每門課都及格了的學(xué)生。6.求選了信息學(xué)院所開所有課程的學(xué)生學(xué)號(hào)。第三十四頁，共七十一頁，2022年，8月28日答案1.3.4.6.第三十五頁，共七十一頁，2022年，8月28日五.元組演算規(guī)則由元組演算所產(chǎn)生的關(guān)系必須是有限關(guān)系。如：是無效的。第三十六頁，共七十一頁，2022年，8月28日第三節(jié)域謂詞演算一：基本概念：域變量：用來表示域的變量域演算：由域變量謂詞構(gòu)成的邏輯公式。演算格式：第三十七頁，共七十一頁，2022年，8月28日二.基本公式域變量關(guān)系謂詞：算術(shù)比較謂詞：如x>y,x=8等。第三十八頁，共七十一頁，2022年，8月28日三.域演算合式公式基本公式是合式公式。用組成的公式。引入組成的公式。例如：R(x,y,z),是合式公式。不是合式公式。第三十九頁，共七十一頁，2022年，8月28日域演算的一般方法：定義域變量。選擇關(guān)系。確定約束變量。第四十頁，共七十一頁，2022年，8月28日描述關(guān)系代數(shù)：.1.2.3.第四十一頁，共七十一頁，2022年，8月28日描述2笛卡爾積：選擇投影第四十二頁，共七十一頁，2022年，8月28日五.應(yīng)用舉例1.2.第四十三頁，共七十一頁，2022年，8月28日六.請(qǐng)說出下列描述的含義1.第四十四頁，共七十一頁，2022年，8月28日續(xù)2.第四十五頁，共七十一頁，2022年，8月28日第四節(jié)數(shù)據(jù)邏輯DATALOG一演算規(guī)則：1.比較謂詞2.關(guān)系謂詞導(dǎo)出關(guān)系謂詞，基本關(guān)系謂詞3.域變量與啞元4.規(guī)則：規(guī)則頭規(guī)則體5.查詢：由一組規(guī)則組成。第四十六頁，共七十一頁，2022年，8月28日對(duì)規(guī)則的說明：規(guī)則頭：只能是導(dǎo)出關(guān)系謂詞。規(guī)則體：原子謂詞原子謂詞的否定用(and)連接以上兩類謂詞。例如：T(x,y,z)S(x,y,z)ANDx>1R(x,y)NOTQ(x,y)第四十七頁，共七十一頁，2022年，8月28日規(guī)則的語義變量的作用域是一條規(guī)則。關(guān)系謂詞的作用域是一個(gè)查詢（全局的)每一個(gè)導(dǎo)出關(guān)系謂詞都對(duì)應(yīng)一個(gè)需要求解的關(guān)系，關(guān)系由所有滿足規(guī)則體的元組構(gòu)成。例10T(x,y,z)S(x,y,z)ANDx>1T:S:ABD123231ABD231第四十八頁，共七十一頁，2022年，8月28日又一例例10.T(x,y)S(x,y,-)R:T(x,y)R(x,z,y)請(qǐng)問：T的值是多少？S:ABC123323131ABD123231第四十九頁，共七十一頁，2022年，8月28日二.邏輯公式的轉(zhuǎn)化1.非內(nèi)置否定的轉(zhuǎn)化：NOT（AANDB）=NOTAANDNOTBOR條件的轉(zhuǎn)化：AORB轉(zhuǎn)化為兩條規(guī)則。如：T(x)S(x,y,z)and(x=1orx=2)變?yōu)門(x)S(x,y,z)andx=1T(x)S(x,y,z)andx=2第五十頁，共七十一頁，2022年，8月28日三規(guī)則的安全性條件作用：排除無限關(guān)系。安全條件：在規(guī)則中所出現(xiàn)的變量必須在規(guī)則體中非否定的關(guān)系謂詞中出現(xiàn)。如：Q(x,y)R(x)andy>0P(x,y)notS(x,y,z)andz=1Q(x,y)R(x)第五十一頁，共七十一頁，2022年，8月28日四規(guī)則的求解建立各關(guān)系的笛卡爾積一致性檢查。若規(guī)則體為真，將元組加入導(dǎo)出關(guān)系中。例12設(shè)R={<1,2>,<5,3>,<3,3>},S={<2,2>,<3,4>}求規(guī)則Q(x,y)R(x,z)andS(z,y)andx>1andnotS(x,y).第五十二頁，共七十一頁，2022年，8月28日求解過程RS一致性X>1NOTS(x,y)(1,2)(2,2)tf(1,2)(3,4)f(5,3)(2,2)f(5,3)(3,4)ttt(3,3)(2,2)f(3,3)(3,4)???第五十三頁，共七十一頁，2022年，8月28日五描述關(guān)系代數(shù)并集：交集：差集：第五十四頁，共七十一頁，2022年，8月28日續(xù)笛卡爾集：Q(x,y,s,t)R(x,y)andS(s,t)投影：Q(x,y)R(x,y,z)自然連接：設(shè)R(A,B),S(B,C)Q(x,y,z)R(x,y)andS(y,z)其它的運(yùn)算請(qǐng)同學(xué)自己考慮。第五十五頁，共七十一頁，2022年，8月28日Datalog的應(yīng)用求信息和會(huì)計(jì)學(xué)院的學(xué)生求選了數(shù)據(jù)庫的學(xué)生學(xué)號(hào)SJK(x)XK(x,y,-)andKC(y,z,-)andz=“數(shù)據(jù)庫“

第五十六頁，共七十一頁，2022年，8月28日六遞歸查詢遞歸查詢：在規(guī)則中，導(dǎo)出關(guān)系謂詞在規(guī)則頭和規(guī)則體中同時(shí)出現(xiàn)。如：Q(x,y)R(x,y)andQ(y,z)2.關(guān)系代數(shù)的不動(dòng)點(diǎn)設(shè)：y=f(x)是關(guān)于x的代數(shù)式子，若有r使得r=f(r)成立，則稱r為該關(guān)系式的不動(dòng)點(diǎn)。第五十七頁，共七十一頁，2022年，8月28日3.最小不動(dòng)點(diǎn)在所有不動(dòng)點(diǎn)中行數(shù)最小的關(guān)系稱為最小不動(dòng)點(diǎn)。例：求下列式子的不動(dòng)點(diǎn)：f(r)=Sr設(shè)s={<1,2>,<1,3>}，r與s同模式。則：r0=,r1=s是不動(dòng)點(diǎn)。

第五十八頁，共七十一頁，2022年，8月28日4.遞歸查詢的解遞歸查詢的解是其代數(shù)方程的最小不動(dòng)點(diǎn)。求解方法：1).令r0=2).計(jì)算f(),3).若成立，則算法結(jié)束否則，繼續(xù)迭代。

第五十九頁，共七十一頁，2022年，8月28日5.求不動(dòng)點(diǎn)舉例其中：Q={<1,2>,<2,1>},可見：是還有{<1,2>,<2,1>,<1,1>,<2,2>},還有嗎？

第六十頁，共七十一頁，2022年，8月28日6.算法舉例設(shè)S:AB13求：Q(x,y)S(x,y)24Q(x,y)Q(x,z)andS(z,y)32f(Q)=(計(jì)算最小不動(dòng)點(diǎn)第六十一頁，共七十一頁，2022年，8月28日計(jì)算最小不動(dòng)點(diǎn)q0:CBq1:CBq2:CBq3=q21313132424243232321212343414第六十二頁，共七十一頁，2022年，8月28日一個(gè)問題若第二條規(guī)則改為：Q(x,y)Q(x,z)andS(t,y）andz>t結(jié)果呢？q0:CBq1:CBq2:CBq3=q2?131313212121323232令s:AB*13*1313113321331132？第六十三頁，共七十一頁，2022年，8月28日這是一個(gè)對(duì)選手排序的問題請(qǐng)用DATALOG求出比指定選手積分高的選手編號(hào)。(2號(hào)選手)編號(hào)積分130223343415第六十四頁，共七十一頁，2022年，8月28日方法一設(shè)：JF(BH,JF)gf(x)jf(s,t)ands=“2”andjf(x,y)andy>t

方法二

第六十五頁，共七十一頁，2022年，8月28日方法三R(x,y,s,t)j