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

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

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

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

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

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

S(SNO,SNAME,SADDR)

零件關(guān)系：

P(PNO,PNAME,COLOR,WEIGHT)

工程項(xiàng)目關(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工程項(xiàng)目使用零件的情況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á)式表示每個(gè)查詢語句。.檢索工程J1的供應(yīng)記錄。JNOJNAMEJCITYBALANCEJ1辦公室工程青島50000J2居家裝修山東50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151SNOPNOJNOPRICEQTYS1P3J155S3P4J1151σJNO=‘J1’

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

(SPJ))σJNO=‘J1’∧PNO=‘P1’（SPJ）3.檢索供應(yīng)零件給工程J1，且零件編號(hào)為P1的供應(yīng)商記錄。4.檢索供應(yīng)零件給工程J1，且零件編號(hào)為P1的供應(yīng)商編號(hào)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.檢索使用了零件編號(hào)為P3或P5零件的工程情況。σPNO=‘P3'∨PNO=‘P5’(SPJ)8.檢索使用了零件編號(hào)為P3或P5零件的工程編號(hào)JNO。πJNO（σPNO=‘P3'∨PNO=‘P5’(SPJ))9.檢索至少使用了編號(hào)為P3和P5

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

(SPJ×SPJ))10.檢索不使用編號(hào)為P3零件的工程編號(hào)JNO和工程名稱JNAME。πJNO,JNAME(J)―πJNO,JNAME(σPNO=‘P3’(S?SPJ?P))11.檢索使用了全部零件的工程名稱JNAME。πJNAME(J?(πJNO,PNO(SPJ)÷πPNO(P))12.檢索使用零件包含編號(hào)為S1的供應(yīng)商所供應(yīng)的全部零件的工程編號(hào)JNO。πJNO,PNO(σSNO=‘S1’(SPJ))÷πPNO(σSNO=‘S1’(SPJ))課后3.12檢索LIU老師所授課程的課程號(hào)、課程名。檢索年齡大于23歲的男學(xué)生的學(xué)號(hào)與姓名。檢索學(xué)號(hào)為S3學(xué)生所學(xué)課程的課程名與任課教師名。檢索至少選修LIU老師所授課程中一門課程的女學(xué)生的姓名。檢索WANG同學(xué)不學(xué)的課程號(hào)。檢索至少選修兩門課程的學(xué)生學(xué)號(hào)。檢索全部學(xué)生都選修的課程的課程號(hào)與學(xué)生學(xué)號(hào)。檢索選修課程包含LIU老師所授課程的學(xué)生學(xué)號(hào)。五、擴(kuò)充的關(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)接時(shí)，把原該舍棄的元組也保留在新關(guān)系中，同時(shí)在這些元組新增加的屬性上填上空值（null），這種操作稱為“外聯(lián)接”操作，用符號(hào)RS表示?？兆址?\0"

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

ii、如果R和S做自然聯(lián)接時(shí)，把S中原該舍棄的元組放到新關(guān)系中，那么這種操作稱為“右外聯(lián)接”操作，用符號(hào):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)成，同時(shí)元組在新增加的屬性上填上空值。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)系演算－－－以域?yàn)樽兞俊?/p>

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

其中t：元組變量；

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

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

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

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

3.運(yùn)算符及優(yōu)先次序?yàn)椋?/p>

i.括號(hào)中運(yùn)算符優(yōu)先級(jí)最高

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

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

iv.邏輯運(yùn)算符：、∧、∨優(yōu)先級(jí)最高4.用元組關(guān)系演算表達(dá)式表示關(guān)系運(yù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在元組演算中的等價(jià)表示形式。

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

∧t[1]=u[1]∧t[2]=u[2])}4.檢索不使用編號(hào)為P3零件的工程編號(hào)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.檢索使用零件包含編號(hào)為S1供應(yīng)商所供應(yīng)的全部零件的工程編號(hào)。如果P1和P2是公式，在元組關(guān)系演算的公式中，存在下列等價(jià)轉(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á)式的定義，

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

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

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

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

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

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

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

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

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

安全運(yùn)算：

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

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

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

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

驗(yàn)證(u)(w(u))為’T’

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

無窮驗(yàn)證

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

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

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

如何花費(fèi)較少的時(shí)間和空間，有效地執(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é)號(hào)和姓名,用關(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））這三個(gè)關(guān)系代數(shù)表達(dá)式是等價(jià)的，但執(zhí)行的效率大不一樣。顯然，求El，E2，E3的大部分時(shí)間是花在聯(lián)接操作上的。

二、代數(shù)表達(dá)式的等價(jià)變換規(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．

選擇對(duì)笛卡兒積的分配律

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

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

選擇對(duì)并的分配律

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

8．選擇對(duì)集合差的分配律

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

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

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

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

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

π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)接運(yùn)算。(3)同時(shí)計(jì)算一連串的選擇和投影操作，以免分開運(yùn)算造成多次掃描文件，節(jié)省操作時(shí)間。(4)如在一個(gè)表達(dá)式中多次出現(xiàn)某個(gè)子表達(dá)式，可先對(duì)該子表達(dá)式進(jìn)行計(jì)算并保存結(jié)果，以免重復(fù)計(jì)算。

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

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

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

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

方法:

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

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

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