第三章 關(guān)系運算2(實例講解)

數(shù)據(jù)庫實用教程（第三版）

第三章關(guān)系運算習(xí)題及實例講解各種運算總結(jié)：

關(guān)系代數(shù)運算有五個基本操作，另三個非基本運算可以由這5個基本運算組合而成。由σ和×組合而成由π、-和×組合而成四、關(guān)系代數(shù)表達(dá)式及其應(yīng)用實例

工程項目零件供應(yīng)數(shù)據(jù)庫PROJECTY有四個關(guān)系模式有四個：

供應(yīng)商關(guān)系：

S(SNO,SNAME,SADDR)

零件關(guān)系：

P(PNO,PNAME,COLOR,WEIGHT)

工程項目關(guān)系：J(JNO,JNAME,JCITY,BALANCE)

供應(yīng)情況關(guān)系：SPJ(SNO,PNO,JNO,PRICE,QTY)SNOSNAMESADDRS1喜多上海浦東S2多樂士北京房山S3天奴廣州汕頭PNOPNAMECOLORWEIGHTP1螺絲銀色0.5P2門扣紅色5P3門鎖紅色20P4開關(guān)白色2P5水龍頭藍(lán)色50JNOJNAMEJCITYBALANCEJ1辦公室工程青島50000J2居家裝修山東50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151J∞SPJSNOSNAMESADDRS1喜多上海浦東S2多樂士北京房山S3天奴廣州汕頭PNOPNAMECOLORWEIGHTP1螺絲銀色0.5P2門扣紅色5P3門鎖紅色20P4開關(guān)白色2P5水龍頭藍(lán)色50JNOJNAMEJCITYBALANCEJ1辦公室工程青島50000J2居家裝修山東50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151工程項目使用零件的情況SNOPNOJNOPRICEQTYJNAMEJCITYBALANCES1P3J155辦公室工程青島50000S3P4J1151辦公室工程青島50000S1P5J2102居家裝修山東50000S∞SPJ∞PSNOSNAMESADDRS1喜多上海浦東S2多樂士北京房山S3天奴廣州汕頭PNOPNAMECOLORWEIGHTP1螺絲銀色0.5P2門扣紅色5P3門鎖紅色20P4開關(guān)白色2P5水龍頭藍(lán)色50JNOJNAMEJCITYBALANCEJ1辦公室工程青島50000J2居家裝修山東50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151S∞SPJ∞PSNOSNAMESADDRPNOJNOPRICEQTYPNAMECOLORWEIGHTS1喜多上海浦東P3J155門鎖紅色20S3天奴廣州汕頭P4J1151開關(guān)白色2S1喜多上海浦東P5J2102水龍頭藍(lán)色50試用關(guān)系代數(shù)表達(dá)式表示每個查詢語句。.檢索工程J1的供應(yīng)記錄。JNOJNAMEJCITYBALANCEJ1辦公室工程青島50000J2居家裝修山東50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151SNOPNOJNOPRICEQTYS1P3J155S3P4J1151σJNO=‘J1’

(SPJ)2.檢索供應(yīng)零件給工程J1的供應(yīng)商編號SNO與零件編號PNO。πSN0,PN0(σJNO=‘J1’

(SPJ))σJNO=‘J1’∧PNO=‘P1’（SPJ）3.檢索供應(yīng)零件給工程J1，且零件編號為P1的供應(yīng)商記錄。4.檢索供應(yīng)零件給工程J1，且零件編號為P1的供應(yīng)商編號SNO。πSNO（σJNO=‘J1’∧PNO=‘P1’（SPJ））SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J11515.檢索供應(yīng)零件給工程J1,且零件顏色為紅色的供應(yīng)情況。πSNAME,SADDR(σJNO=‘J1'∧COLOR=‘紅色’(S?SPJ?P))6.檢索供應(yīng)零件給工程J1,且零件顏色為紅色的供應(yīng)商名稱和地址。σJNO=‘J1'∧COLOR=‘紅色’(S?SPJ?P)7.檢索使用了零件編號為P3或P5零件的工程情況。σPNO=‘P3'∨PNO=‘P5’(SPJ)8.檢索使用了零件編號為P3或P5零件的工程編號JNO。πJNO（σPNO=‘P3'∨PNO=‘P5’(SPJ))9.檢索至少使用了編號為P3和P5

零件的工程編號JNO。π3（σ3=8∧2=‘P3'∧7=‘P5'

(SPJ×SPJ))10.檢索不使用編號為P3零件的工程編號JNO和工程名稱JNAME。πJNO,JNAME(J)―πJNO,JNAME(σPNO=‘P3’(S?SPJ?P))11.檢索使用了全部零件的工程名稱JNAME。πJNAME(J?(πJNO,PNO(SPJ)÷πPNO(P))12.檢索使用零件包含編號為S1的供應(yīng)商所供應(yīng)的全部零件的工程編號JNO。πJNO,PNO(σSNO=‘S1’(SPJ))÷πPNO(σSNO=‘S1’(SPJ))課后3.12檢索LIU老師所授課程的課程號、課程名。檢索年齡大于23歲的男學(xué)生的學(xué)號與姓名。檢索學(xué)號為S3學(xué)生所學(xué)課程的課程名與任課教師名。檢索至少選修LIU老師所授課程中一門課程的女學(xué)生的姓名。檢索WANG同學(xué)不學(xué)的課程號。檢索至少選修兩門課程的學(xué)生學(xué)號。檢索全部學(xué)生都選修的課程的課程號與學(xué)生學(xué)號。檢索選修課程包含LIU老師所授課程的學(xué)生學(xué)號。五、擴充的關(guān)系代數(shù)操作1.外聯(lián)接（outerjoin）

R

?

S≡πi1,...im(σR.A1=S.A1∧...∧R.AK=S.AK(R×S))在R和S做自然聯(lián)接時，把原該舍棄的元組也保留在新關(guān)系中，同時在這些元組新增加的屬性上填上空值（null），這種操作稱為“外聯(lián)接”操作，用符號RS表示。空字符串"\0"

i、如果R和S做自然聯(lián)接時，把R中原該舍棄的元組放到新關(guān)系中，那么這種操作稱為“左外聯(lián)接”操作，用符號:RS表示。

ii、如果R和S做自然聯(lián)接時，把S中原該舍棄的元組放到新關(guān)系中，那么這種操作稱為“右外聯(lián)接”操作，用符號:RS表示。ABCabcbbfcadBCDbcdbceadbefgABCDabcdabcecadbbbfnullnullefg關(guān)系R關(guān)系SABCDabcdabcecadbbbfnullABCDabcdabcecadbnullefg2.外部并（outerunion）

如果R和S的關(guān)系模式不同，構(gòu)成的新關(guān)系屬性有R和S的所有屬性組成（公共屬性只取一次），新關(guān)系的元組由屬于R或?qū)儆赟的元組構(gòu)成，同時元組在新增加的屬性上填上空值。ABCDabcnullbbfnullcadnullnullbcdnullbcenulladbnullefg3.半聯(lián)接（semijoin）關(guān)系R和S的半聯(lián)接操作記為R?S:

R和S的自然聯(lián)接在關(guān)系R的屬性集上的投影即：R?S≡πR（R?S）關(guān)系R關(guān)系SR?SR

?SS

?RABCDabcdabcedbcddbcecadbABCabcdbccadBCDbcdbceadbBCDbcdbceadbABCabcdbcbbfcad§4關(guān)系演算

以數(shù)理邏輯中的謂詞演算為基礎(chǔ)，用公式表示關(guān)系演算的條件。關(guān)系演算按所用到的變量不同可分為：元組關(guān)系演算－－－以元組為變量；域關(guān)系演算－－－以域為變量。

一、元組關(guān)系演算形式：{t∣(t)}

其中t：元組變量；

：公式，公式有原子公式及運算符組成。1.原子公式有下列三種形式：①R（t）：

R是關(guān)系名，t是元組變量。②t[i]θu[j]:t和u是元組變量，θ是算術(shù)比較運算符。③t[i]θC或Cθu[i]：

t和u是元組變量，c是常量。

2.約束變量和自由變量在一個公式中，如果一個元組變量的前面沒有存在量詞ョ或全稱量詞的符號定義，稱之為自由元組變量，否則稱為約束元組變量。

3.運算符及優(yōu)先次序為：

i.括號中運算符優(yōu)先級最高

ii.算術(shù)比較運算符最高；

iii.量詞：存在量詞ョ全稱量詞

iv.邏輯運算符：、∧、∨優(yōu)先級最高4.用元組關(guān)系演算表達(dá)式表示關(guān)系運算并:R∪S{t|R（t）∨S(t)}差:R-S{t|R（t）∧S(t)}笛卡兒積:R×S

{t|(u)(v)(R(u)∧S(v)∧t[1]=u[1]∧…∧t[r]=u[r]∧t[r+1]=v[1]∧…∧t[r+s]=v[s])}

投影:πi1,i2,…ik(R)

{t|(u)|R(u)∧t[l]=u[i1]∧…∧t[iK]=u[iK]}}選擇:σF（R）

{t|R(t)∧F’}

F’是F在元組演算中的等價表示形式。

6.實例:用元組表達(dá)式形式表示下列查詢例:用元組表達(dá)式形式表示下列查詢：1.檢索供應(yīng)零件給工程J1，且零件編號為P1的供應(yīng)商編號SNO。{t|(u)(SPJ(u)∧u[2]=‘P1’∧u[3]=‘J1’∧t[l]=u[1])}2.檢索使用了編號為P3零件的工程編號和名稱。{t|(u)(v)(J(u)∧SPJ(v)∧v[2]=‘P3’∧u[l]=v[3]∧t[l]=u[1]∧t[2]=u[2])}{t|(u)(v)(SPJ(u)∧SPJ(v)∧u[3]=v[3]∧u[2]=‘P3’∧v[2]=‘P5’∧t[l]=u[3])}3.檢索至少使用了編號為P3和P5零件的工程編號JNO。{t|(u)(v)(J(u)∧SPJ(v)∧((u[l]=v[3])v[2]≠’P3’)

∧t[1]=u[1]∧t[2]=u[2])}4.檢索不使用編號為P3零件的工程編號JNO和工程名稱SNAME。5.檢索使用了全部零件的工程名稱JNAME。{t|(u)(v)(w)(J(u)∧P(v)∧SPJ(w)∧u[l]=w[3]∧v[1]=w[2]∧t[1]=u[2])}{t|(u)(SPJ(u)∧(v)(SPJ(v)∧(v[1]=‘S1’(w)(SPJ(w)

∧w[3]=u[3]∧w[2]=v[2])))∧t[l]=u[3])}6.檢索使用零件包含編號為S1供應(yīng)商所供應(yīng)的全部零件的工程編號。如果P1和P2是公式，在元組關(guān)系演算的公式中，存在下列等價轉(zhuǎn)換規(guī)則：

P1∧P2┐(┐P1∨┐P2)P1∨P2┐(┐P1∧┐P2）

(s)(P1(s))┐(s)(┐P1(s))(s)(P1(s))┐(s)(┐P1(s))P1P2┐P1∨P2

二、域關(guān)系演算域演算表達(dá)式的定義類似于元組演算表達(dá)式的定義，

所不同的是公式中用域變量代替元組變量的每一個分量，域變量的變化范圍是某個值域而不是一個關(guān)系。

1、域演算表達(dá)式：一般形式:{t1t2…tk∣P(t1,t2,…,tk)｝

其中t1、t2、…、tk分別是元組變量t的各個分量的域變量，

P是域演算公式。①原子公式有下列兩種形式：

i．R（t1…tk）：R是K元關(guān)系，每個ti是域變量或常量。

ii．xθy,其中x,y是域變量或常量，但至少有一個是域變量，θ是算術(shù)比較運算符。②域關(guān)系演算的公式中也可使用∧、∨、和=>等邏輯運算符也可用(x)和（x）形成新的公式，但變量x是域變量，不是元組變量。自由域變量、約束域變量等概念和元組演算中一樣。2.元組表達(dá)式到域表達(dá)式的轉(zhuǎn)換規(guī)則：①對于k元的元組變量t,引入k個域變量t1,t2,…,tk,

在公式中t用t1,t2,…,tk替換，元組分量t[i]用ti替換。②對于每個量詞(u)或（u），若u是m元的元組變量，則引入m個新的域變量u1,u2,…,um。在量詞的轄域內(nèi)，u用u1u2…um替換，u[i]用ui替換，

(u)用(u1)…(um)替換，

(u）用（u1）…(um)替換。3.舉例

安全運算：

不產(chǎn)生無限關(guān)系和無窮次驗證的運算稱為安全運算，相應(yīng)的表達(dá)式稱為是安全表達(dá)式。所采用的措施稱為安全約束。安全約束集DOM():

公式中的常量和中所出現(xiàn)關(guān)系的所有屬性值組成的集合。三、關(guān)系運算的安全性和等價性

1.關(guān)系運算的安全性

{t|R(t)}無限關(guān)系

驗證(u)(w(u))為’T’

或（u）(w(u))為’F’

無窮驗證

2.關(guān)系運算的等價性并、差、笛卡兒積、投影和選擇是關(guān)系代數(shù)最基本的操作，并構(gòu)成了關(guān)系代數(shù)運算的最小完備集?？梢宰C明，在這個基本上，關(guān)系代數(shù)、安全的元組關(guān)系演算、安全的域關(guān)系演算在關(guān)系的表達(dá)和操作能力上是等價的。

§5查詢優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化問題:

在關(guān)系代數(shù)表達(dá)式中需要指出若干關(guān)系的操作步驟。系統(tǒng)應(yīng)該以什么樣的操作順序，才能做到既省時間，又省空間，而且效率也比較高呢？

如何花費較少的時間和空間，有效地執(zhí)行笛卡兒積操作.

一、查詢優(yōu)化的總目標(biāo)選擇有效的策略，求得給定關(guān)系代數(shù)表達(dá)式的值，達(dá)到提高DBMS系統(tǒng)效率的目標(biāo)。例:學(xué)生數(shù)據(jù)庫：S(SNO,SNAME,SEX,SDEPT)C(CNO,CNAME,TEACHER,CDEPT)SC(SNO,CNO,GRADE)檢索選修C2課程的學(xué)生的學(xué)號和姓名,用關(guān)系代數(shù)表達(dá)式表示：

E1=πSNAME（σS.SNO=SC.SNO∧SC.CNO=‘C2’（S×SC））

E2=πSNAME（σSC.CNO=‘C2’（S?SC）

E3=πSNAME

（S?σSC.CNO=‘C2’（SC））這三個關(guān)系代數(shù)表達(dá)式是等價的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時間是花在聯(lián)接操作上的。

二、代數(shù)表達(dá)式的等價變換規(guī)則

1、

聯(lián)接和笛卡兒積的交換律

E1

E2≡E2E1E1E2≡E2E1E1×E2≡E2×E1?

F?

F??2．聯(lián)接和笛卡兒積的結(jié)合律

（E1E2）E3≡E1（E2E3）（E1E2）E3≡E1（E2E3）

（E1×E2）

×

E3≡E1×（E2×E3）?

F1?

F1?

F2?

F2????

3.投影的串接設(shè)L1，L2，…，Ln為屬性集，并且L1L2…Ln，成立：

πL1（πL2（…（πLn（E））…））≡πL1（E）4．

選擇的串接

σF1（σF2（E））≡σF1∧F2（E）由于F1∧F2=F2∧F1，選擇的交換律也成立：

σF1（σF2（E））≡σF2（σF1（E））

5．

選擇和投影操作的交換

πL（σF（E））≡σF（πL（E））要求條件F只涉及到L中的屬性,如果F還涉及到不在L中的屬性集L1：

πL（σF（E））≡πL（σF（πL∪L1（E）））6．

選擇對笛卡兒積的分配律

σF（E1×E2）≡σF（E1）×E2σF（E1×E2）≡σF1（E1）×σF2（E2）

σF（E1×E2）≡σF2（σF1（E1）×E2）7.

選擇對并的分配律

σF（E1∪E2）≡σF1（E1）∪σF2（E2）

8．選擇對集合差的分配律

σF（E1－E2）≡σF（E1）－σF（E2）

9．選擇對自然聯(lián)接的分配律

σF（E1?E2）≡σF（E1）?

σF（E2）10．投影對笛卡兒積的分配律

πL1∪L2（E1×E2）≡πL1（E1）×πL2（E2）11．投影對并的分配律

πL（E1∪E2）≡πL（E1）∪πL（E2）12．選擇與聯(lián)接操作的結(jié)合

σF1（E1E2）≡E1

E2

13．并和交的交換律

E1∪E2≡E2∪E1E1∩E2≡E2∩E114．并和交的結(jié)合律

（E1∪E2）∪E3≡E1∪（E2∪E3）（E1∩E2）∩E3≡E1∩（E2∩E3）?

F2?F2∧F2

三、優(yōu)化的一般策略

(1--6)(1)在關(guān)系代數(shù)表達(dá)式中盡可能早地執(zhí)行選擇操作。(2)把笛卡兒積和其后的選擇操作合并成F聯(lián)接運算。(3)同時計算一連串的選擇和投影操作，以免分開運算造成多次掃描文件，節(jié)省操作時間。(4)如在一個表達(dá)式中多次出現(xiàn)某個子表達(dá)式，可先對該子表達(dá)式進(jìn)行計算并保存結(jié)果，以免重復(fù)計算。

(5)適當(dāng)?shù)貙﹃P(guān)系文件進(jìn)行預(yù)處理。

(6)在計算表達(dá)式前應(yīng)先估計一下怎么計算合算。

三、關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入：一個關(guān)系代數(shù)表達(dá)式的語法樹。

輸出：計算表達(dá)式的一個優(yōu)化序列。

方法:

依次執(zhí)行下面每一步。①使用等價變換規(guī)則⑷把每個形為σF1∧…∧Fn（E）的子表達(dá)式轉(zhuǎn)換成選擇串接形式：σF1（…σFn（E））…）②對每個選擇操作，使用規(guī)則⑷～⑼，盡可能把選擇操作移近樹的葉端（即盡可能早地執(zhí)行選擇操作）。③對每個投影操作，使用規(guī)則(3)，(5)，(10)和(11)，盡可能把

投影操作移近樹的葉端。④使用規(guī)則⑶～⑸，把選擇和投影合并成單個選擇、單個投影或一個選擇后跟一個投影。⑤將上述步驟得到的語法樹的內(nèi)結(jié)點分組。分組原則：

a、每個二元運算(×、∪、－)結(jié)點與其直接祖先(不超過別的二元運算結(jié)點）的一元運算結(jié)點(σ或π)分為一組。如果它的子孫結(jié)點一直到葉都是一元運算符(σ或π),則也并入該組。b、如果二元運算是笛卡兒積，而且后面不是與它組合成等值聯(lián)接的選擇時，則不能將選擇與這個二元運算組成同一組。⑥生成一個程序，每一組結(jié)點的計算是程序中的一步，各步的順序是任意的只要保證任