中山大學數(shù)據(jù)庫系統(tǒng)-數(shù)據(jù)庫理論作業(yè)

1.8列出文件處理系統(tǒng)和DBMS的四個主要區(qū)別。

Answer:

文件處理系統(tǒng)和DBMS的四個主要區(qū)別如下：

?存儲在數(shù)據(jù)庫中的數(shù)據(jù)，其邏輯結構可能不同于其物理結構，DBMS

不僅管理數(shù)據(jù)的物理結構還管理數(shù)據(jù)的邏輯結構，DBMS的使用者只

需知道數(shù)據(jù)的邏輯結構而不需要關心其物理結構。文件系統(tǒng)只有物理

結構而沒有邏輯結構。

?DBMS以一種高效的方式訪問數(shù)據(jù)，一條數(shù)據(jù)在物理結構上只需存

儲一次。文件系統(tǒng)往往不能做到讓不同的程序高效地訪問數(shù)據(jù)，一條

數(shù)據(jù)常常有很多副本，容易出現(xiàn)數(shù)據(jù)冗余。

?使用DBMS時，數(shù)據(jù)的各種約束條件由DBMS檢查，程序員只需在

DDL中聲明所有約束。而使用文件系統(tǒng)時，每插入一條數(shù)據(jù)，都需要

程序員的代碼來檢查是否滿足約束條件。

?DBMS允許多個用戶同時并發(fā)地訪問同一個數(shù)據(jù)庫并保證數(shù)據(jù)的一

致性，文件系統(tǒng)不能很好地處理并發(fā)訪問帶來的問題。

1.9解釋物理數(shù)據(jù)獨立性的概念，以及它在數(shù)據(jù)庫系統(tǒng)中的重要性。

Answer:

物理獨立性是指用戶的應用程序與存儲在磁盤上的數(shù)據(jù)庫中數(shù)據(jù)是

相互獨立的。

物理獨立性使應用程序與存儲在磁盤上的數(shù)據(jù)相分離，應用程序不依

賴于物理模式，因此物理模式改變了它們也無需重寫。

2.9考慮圖2-15所示銀行數(shù)據(jù)庫。

a.適當?shù)闹鞔a是什么？

b.給出你選擇的主碼，確定適當?shù)耐獯a。

Answer:

a.主碼：

branch:branchname

customer:customername

loan:loannumber

borrower:customername,loannumber

account:accountnumber

depositor:customername,accountnumber

b.外碼：

branch:無

customer:無

loan:branchname

borrower:customername,loannumber

account:branchname

depositor:customername,accountnumber

2.10考慮圖2虐所示advisor關系,advisor的主碼是s_id。假設

一個學生可以有多位指導老師。那么，s_id還是advisor的主碼嗎？

如果不是，advisor的主碼會是什么呢？

Answer:

不是，若一位學生有多個指導老師，那么表中可能有多個元組有相同

的s_id取值，這違反了主碼唯一的原則。此時主碼應該為(s_id,

i_id).

2.11解釋術語關系和關系模式在意義上的區(qū)別。

Answer:

關系對應程序設計語言中變量的概念，它是一個存在于物理存儲空

間中的實體，是真正存放數(shù)據(jù)的地方。關系模式對應于程序設計語

言中類型的概念，它僅僅是一種定義，定義了某種類型的關系中應

該存放什么屬性。關系可看作關系模式的實例化。

2.12考慮圖2-14所示關系數(shù)據(jù)庫。給出關系代數(shù)表達式來表示下列

每一個查詢：

a.找出為"FirstBankCorporation”工作的所有員工姓名。

b.找出為"FirstBankCorporationv工作的所有員工的姓名和居

住城市。

c.找出為“FirstBankCorporation”工作且掙錢超過10000美元

的所有員工的姓名、街道地址和居住城市。

Answer:

^persoiuiame(^company->iame="FirstBankCorporation”(，〃°「依))

b.^persorLiiame.city(employee兇

(^companyjiame="FirstBankCorporation"("'°rks)))

person-name,street,city

(companyJiame="FirstBankCorporation"Asalary>10000)

(worksXemployee))

2.13考慮圖2T5所示銀行數(shù)據(jù)庫。對于下列每個查詢，給出一個關

系代數(shù)表達式：

a.找出貸款額度超過10000美元的所有貸款號。

b.找出所有這樣的存款人姓名，他擁有一個存款額大于6000美元的

賬戶。

c.找出所有這樣的存款人姓名，他在“Uptown”支行擁有一個存款

額大于6000美元的賬戶。

Answer:

a.^loaiuiumber^amount>10000(/°即)

b?I"!customer^name^baianco6000(depositorXaccount))

c.ncustomer-name(,^balance>6000人歷a"ch_"“zne="Uptown"(depositorX(ICCOlint))

2.14列出在數(shù)據(jù)庫中引入空值的兩個原因。

Answer:

1、某個元組的某個屬性未知，2、某個元組的某個屬性不存在

2.15討論過程化和非過程化語言的相對優(yōu)點。

Answer:

非過程化語言簡化了詢問，用戶可以不用關心操作的具體過程。但同

時，需要花更多工作來優(yōu)化詢問器，來快速找到結果。過程化語言需

要用戶明確操作的具體過程，用戶的靈活性更高，但也更容易出錯,

很難較快的表達目標結果，但設計好的操作過程，可能比詢問其自動

尋找，速度要快。

6.11考慮圖6-22所示關系數(shù)據(jù)庫，主碼加了下劃線。給出關系代數(shù)

表達式來表示下列每一個查詢：

a.找出FirstBankCorporation的所有員工姓名。

b.找出FirstBankCorporation所有員工的姓名和居住城市。

c.找出FirstBankCorporation所有年收入在10000美元以上

的員工姓名和居住的街道、城市。

d.找出所有居住地與工作的公司在同一城市的員工姓名。

e.假設公司可以位于幾個城市中。找出滿足下面條件的所有公司，

它位于SmallBankCorporation所位于的每一個城市。

Answer:

a.^person_name(.^company_name=rFirstBankCorporation/(W。注S))

b.〃person_name,city(employeeX

(.^company_name=rFirstBankCorporation'

c-^person_name,street,cityX

^(company_name=rFirstBankCorporation'Asa/ary>10000)(worksX

employee))

d.^personname^employee兇worksXcompany)

e。company~

5city(.^companyjiame=fSmallBankCorporation!(cOTJipCiny))))

6.13考慮圖6-22所示的關系數(shù)據(jù)庫。分別給出下列查詢的關系代

數(shù)表達式：

a.找出員工最多的公司。

b.找出工資最少的員工所在公司。

c.找出人均工資比FirstBankCorporation人均工資高的公司。

Answer:

JcompanyjiameGcount-distinctQpersonjiame)(Wor/cs)

>>>

「2—Gmax(num_employees)(<Pcompany_list(company_name>num_employees)^l))

^companyjiame(<Pt3(companyjiame,num_employees)(11)XPt4(rtumemployees)(*2))

gmin(saLary)(woMs)

—companyname

^PcornpcLTiyiiSi^companynameiSaiary^

b.一Gmin(salary)

1X1>

^companyname{pt3{comvanyname，salary)Pt4(<salary')(.^2))

一company_nameGavg(salary)(wovks^

「21^compang_name=『FirstBankCorporation^(^1)

C.

^t3.company_name(<Pt3^companyjiame,avgsalary)(t1)

，.吁右,Pt^(companyname,avgsalary)\^2)J

口，，

t3.avgsalary>t4.avgsalary

6.16設R=(A,B)且S=(A,C),r(R)和s(S)是關系。分別給出與下

列域關系演算表達式等價的關系代數(shù)表達式：

a.{<a>|2b(<a,b>erAb=17)}

b.{<a,b,c>|<a,b>GrA<a,c>￡s}

c.{<a>|3b?a,b>￡r)VVc(3d(<d,c>￡s)

=><a,c>￡s)}

d.{<a>|3c(<a,c>sA3bl,b2(<a,bl>￡r

A<c,b2>

erAbl>b2))}

Answer:

a.〃A9B=I7(T))

b.r兇s

c〃A(r)U(r+%(〃cG)))

d.%((rxs)x(c=r2.AA(r.5>r2.B))(Pr2(r)))

6.18設R=(A,B)且S=(A,C),r(R)和s(S)是關系。使用特殊常量

null,分別書寫等價于下列表達式的元組關系演算表達式：

a.rMZs

b.rMs

c.rJxis

Answer:

a.

{t\Br&R,BseSM^]=s[A]At[A]=r[A\At[B]=r[B]AZ[C]=s[C])

v35GS(「土eR,(r[A]=s[A]At[A]=r[A]At[C]=s[C]At[B]=null))

b.

{，舊rcR,mseS,(耳A]=s[A]At[A]=r[A]^t[B]=r[B]^t[C]=5[C])

v35eS(^3reR,(r[A]=s[A]A"A]=r[A]At[C]=s[C]At[B]=null))

v3reeS,(r[A]=s[A]Ar[A]=r[A]At[B]=s[3]Ar[C]=null))

}

c.

{?|3reR,3seS,(r[A]=s[A]At[A]=r[A]At[B]=r[B]At[C]=s[C])

v3reH(-dsGS,(r[A]=s[A]At[A]=r[A]At[B]=r[B]AS[C]=null))

}

8.26用Armstrong公理證明分解律的正確有效性。

Answer:

由自反律，3Y-*3;又由a-*By和By—B,由傳遞率可

知，a-*3；同理有a->y0

8.27用實踐習題8.6中的函數(shù)依賴計算B+.

Answer:

第一次repeat:result={B}

?A—BC:由于A&result,result不變

,CD-E:由于CD&result,result不變

?B-*D:由于B￡result,result變?yōu)閧B,D}

?EA:由于E@result,result不變

第二次repeat:result={B,D}

?AfBC:由于A&result,result不變

?CD-*E:由于CD&result,result不變

?B-*D:由于Bcresult,result不變

?EfA:由于E&result,result不變

沒有新屬性加入result,算法終止。B+=result={B,D}。

8.28證明實踐習題8.1中的模式R的如下分解不是無損分解:

(A,B,C)

(C,D,E)

Answer:

根據(jù)提示，使用關系r如下表:

ABCDE

alb\cldlel

a262cle2

RI=(A,B,C),R2=(C,D,E):

a.nRl(r):

ABC

alblcl

a2b2cl

b.0R2(r)

CDE

cldiel

cl龍e2

c.nRl(r)xnR2(r):

ABCDE

alblcldlel

alblclo2或

a2b2cldlel

a262cle2

很明顯，nRl(r)xnR2(r)Wr.故該分解不是無損分解.

8.29考慮如下關系模式r(A,B,C,D,E,F)上的函數(shù)依賴集F：

A-BCD

BC-DE

B-*D

D-A

a.計算B+.

b.(使用Armstrong公理)證明AF是超碼。

c.計算上述函數(shù)依賴集F的正則覆蓋；給出你的推導的步驟并解

釋。

d.基于正則覆蓋，給出r的一個3NF分解。

e.利用原始的函數(shù)依賴集，給出r的一個BCNF分解。

f.你能否利用正則覆蓋得到與上面的r相同的BCNF分解？

Answer:

a.第一次repeat:result={B}

,A-BCD:由于A&result,result不變.

?BCfDE:由于BC&result,result不變.

?B-*D:由于Bcresult,result變?yōu)閧B;D}.

?DfA:由于Dcresult,result變?yōu)閧A;B;D}

第二次repeat:result={A;B;D}

?AfBCD:由于A￡result,result變?yōu)閧A;B;C;D}

BCfDE:由于BCGresult,result變?yōu)閧A;B;C;D;E).

?BfD:由于Bqresult,result不變.

?DfA:由于Dqresult,result不變.

第三次repeat時，沒有新屬性加入result,算法終止。B+=

{A;B;C;D;E)

b.,A-BCD條件

?BCD--BC自反律

?A—BC傳遞律

?BC-DE條件

?A—DE傳遞律

?ABCDfBCDE增補律

?A—ABCD增補律

?A—BCDE傳遞律

?AF-ABCDEF增補律

?AF是超碼超碼定義

c.第一次repeat:F=Fc

?對于依賴A-BCD,D是無關屬性，因為｛A-BC;B-D｝可推出

A—D,將D去掉

?對于依賴BC-DE,D是無關屬性，因為B-D可推出BCfD,將D

去掉。C是無關屬性，因為由F可推出B-DE,將C去掉

?對于依賴BfD,沒有無關屬性

?對于依賴DfA,沒有無關屬性

第二次repeat:Fc={AfBC;BfE;BfD;D-*A},將BfE;BfD合并

為BfDE。其他不變

第三次repeat:Fc不變，F(xiàn)c={A-*BC;B-*DE;D-*A),算法結束。

d.過程如下：

對Fc中的每一個依賴，生成如下模式：

R1(A,B,C),R2(B,D,E),R3(A,D)

Ri中沒有包含候選碼的，又已知AF為候選碼，增加一個R4(A,F)

沒有R包含于另一個R,故得到一個3NF分解為：

R1(A,B,C),R2(B,D,E),R3(A,D),R4(A,F)

e.result={r(A,B,C,D,E,F)}

A—BCD,但A不是r的超碼，result={rl(A,B,C,D),r2(A,

E,F)}

AfE,但A不是r2的超碼，result={rl(A,B,C,D),r2(A,

E),r3(A,F)}

所有關系都已經(jīng)是BCNF,故算法終止。

f.可以。一組函數(shù)依賴和它的正則覆蓋有相同的閉包，而BCNF

分解使用的也是閉包，所以得出的分解結果是相同的。

8.30列出關系數(shù)據(jù)庫設計的三個目標，并解釋為什么要達到每個

目標。

Answer:

?無損分解，因為要保證信息不丟失。

?保持依賴，在檢查依賴關系時避免做連接運算。

?最小信息冗余，節(jié)省存儲空間，易于保持數(shù)據(jù)的一致性。

14.12列出ACID特性，解釋每一特性的用途。

Answer:

?原子性(atomicity):事物是不可分割的。事務的所有操作要么

全部執(zhí)行，要么全部不執(zhí)行。事務執(zhí)行的過程中數(shù)據(jù)庫可能會出現(xiàn)

暫時性地不一致地現(xiàn)象，原子性避免了部分執(zhí)行的事務導致的不一

致。

,一致性(consistency):隔離執(zhí)行事務時，事務的操作能保持數(shù)

據(jù)庫的一致性。一致性保證了數(shù)據(jù)庫在執(zhí)行事務后仍然能真實反映

現(xiàn)實世界。

?隔離性(isolation):多個事務并發(fā)執(zhí)行時，對于任意一對事

務，系統(tǒng)保證在其中一個事務看來，另一個事務都執(zhí)行完畢或未開

始，即每個事務都不知道系統(tǒng)中還有其他事務并發(fā)執(zhí)行。隔離性避

免了多個事務交叉執(zhí)行可能帶來的不一致性。

?持久性(durability):一個事務成功執(zhí)行后，即使系統(tǒng)出現(xiàn)了故

障，該事務對數(shù)據(jù)庫的影響也應該是永久的。持久性保證成功執(zhí)行

的事務在任何情況下都能夠起作用。

14.15考慮以下兩個事務：

Ti3：read(X);

read(B)；

ifA=0thenB:=B+1;

write(B).

Ti4：read(B);

read(A)；

ifB=0thenAi=A+1;

write(A).

設一致性需求為A=0VB=0,初值是A=B=0o

a.說明包括這兩個事務的每一個串行執(zhí)行都保持數(shù)據(jù)庫的一致性。

b.給出T13和T14的一次并發(fā)執(zhí)行，執(zhí)行產(chǎn)生不可串行化調度。

c.存在產(chǎn)生可串行化調度的T13和T14的并發(fā)執(zhí)行嗎？

Answer:

a.兩個事務共有兩個串行執(zhí)行：T13T14andT14T13.

Case1:

AB

initially00

afterT1301

afterT1401

滿足一致性：A=0VB=0三TVF=T

Case2:

AB

initially00

afterT1310

afterT1410

滿足一致性：/=0三FVT二T

b.

TiT2

read(A)

read(B)

read(A)

read(B)

ifA=0thenB=B+1

ifB=0thenA=A+1

write(A)

write(B)

T13T14

read(i4)

read(B)

read(A)

read(B)

ifA=0thenB=B+1

ifB=0thenA=A+1

write(A)

write(B)

c.不行。

假設并發(fā)執(zhí)行的第一條語句是T13的read(A),那么T14的最后一

條指令write(A)肯定在其之下。雖然可以通過不斷的調度可以把第

一條語句read(A)與T14的其他指令交換，但由于T14的最后一條

指令與其沖突，所以無法把T14的所有指令向上串行化，也無法把

T13的所有指令向上串行化。同理，若并發(fā)執(zhí)行的第一條語句是

T14的read(B),也無法實現(xiàn)非沖突可串行化。因為對于T13,T14

的任意并發(fā)執(zhí)行，任意調度都無法與串行調度沖突等價，也即使任

意調度都是非沖突串行化的。所以不存在可以產(chǎn)生可串行化調度的

T13和T14的并發(fā)執(zhí)行。

15.1證明兩階段封鎖協(xié)議保證沖突可串行化，并且事務可以根據(jù)其

封鎖點串行化。

Answer:

給定任意兩個事務Ti,Tj,設其封鎖點為ai,aj,先證明當優(yōu)先級

圖中存在有向邊Ti-Tj時，必有ai<aj：當有向邊Ti,Tj存在

時，表明Ti,Tj先后讀/寫同一個數(shù)據(jù)項，且Ti先于門，在封鎖

協(xié)議中，讀取數(shù)據(jù)需要獲得鎖，且同一個數(shù)據(jù)項的數(shù)據(jù)鎖在同一時

間只能由一個事務持有，則Ti先獲得鎖，Ti在其封鎖點ai后釋放

鎖，之后Tj才能獲得鎖，aj在Tj獲得鎖之后，所以有ai<aj。

對于任意N個事務，不存在兩個封鎖點相同的事務，不妨令al

<-<an,則對于優(yōu)先級圖中任意邊Ti-Tj,都有i<j,即優(yōu)先

圖中無環(huán)，所以是沖突可串行化的，且T1,…，Tn是一個優(yōu)先圖的

拓撲排序。

15.2考慮下面兩個事務：

T34：read(A)；read(B)；ifA=0thenB:=B+1；write(B).

T35：read(B)；read(A)；ifB=0thenA:=A+1；write(A).

給事務T34與T35增加加鎖、解鎖命令，使它們遵從兩階段封鎖

協(xié)議。這兩個事務會引起死鎖嗎？

Answer:

a.T34:

lock-S(A)

read(A)

lock-X(B)

read(B)

ifA=0

thenB:=B+1

write(B)

unlock(A)

unlock(B)

T35:

lock-S(B)

read(B)

lock-X(A)

read(A)

ifB=0

thenA:=A+1

write(A)

unlock(B)

unlock(A)

b.當調度如下時，這兩個事務會引起死鎖。

T34T35

lock-S(A)

lock-S(B)

Read(B)

read(A)

lock-X(B)

lock-X(A)

15.3強兩階段封鎖協(xié)議帶來什么好處？它與其他形式的兩階段封

鎖協(xié)議相比有何異同？

Answer:

強兩階段封鎖協(xié)議要求事務提交之前不得釋放任何鎖。而普通

的兩階段封鎖協(xié)議只要求事務在增長階段可以獲得鎖但不能釋放鎖,

在釋放階段可以釋放鎖但不能獲得鎖，嚴格兩階段封鎖協(xié)議則只要求

排他鎖必須在事務提交之后才能釋放。

強兩階段封鎖協(xié)議的好處在于事務若寫入一個數(shù)據(jù)，則在它提交

之前沒有其他事務可以讀它寫入的數(shù)據(jù)，避免了級聯(lián)回滾。在強兩

階段封鎖條件下，事務可以按其提交的順序串行化。

15.20嚴格兩階段封鎖協(xié)議帶來什么好處？會產(chǎn)生哪些弊端?

Answer:

嚴格兩階段封鎖協(xié)議避免了級聯(lián)回滾，減小了回滾帶來的性能影

響。但由于兩階段封鎖協(xié)議中事務釋放排他鎖的時間推遲到事務提交

之后，則可獲得的調度集是普通兩階段封鎖協(xié)議可獲得的調度集的子

集，即會導致并發(fā)度的下降。

15.22考慮樹形協(xié)議的一個變種，它稱為森林協(xié)議。數(shù)據(jù)庫按有根樹

的森林的方式組織。每個事務必須遵從以下規(guī)則：

?每棵樹上的首次封鎖可以在任何數(shù)據(jù)項上進行。

?樹上的第二次以及以后的封鎖申請僅當被申請結點的父結點上有鎖

時才能

發(fā)出。

?數(shù)據(jù)項解鎖可在任何時候進行。

?事務釋放數(shù)據(jù)項后不能再次封鎖該數(shù)據(jù)項。

證明森林協(xié)議不保證可串行性。

Answer:

對于兩棵樹：

執(zhí)行如下調度:

T1T2

Lock(nl)

Lock(n3)

Write(n3)

Unlock(n3)

Lock(n2)

Lock(n5)

Write(n5)

Unlock(n5)

Lock(n5)

Read(n5)

Unlock(n5)

Unlock(nl)

Lock(n3)

Read(n3)

Unlock(n3)

Unlock(n2)

顯然這樣的調度滿足森林協(xié)議但是不是可串行化的。

15.24如果通過死鎖避免機制避免了死鎖后，餓死仍有可能嗎？解

釋你的答案。

Answer:

仍然有可能會餓死，通過死鎖恢復，在回滾的時候需要選擇犧牲

者，這就可能導致餓死。而死鎖預防也可能導致餓死，原因是一樣

的。

16.18考慮圖16-5中的日志。假設恰好在CTOabort》日志記錄寫

出之前系統(tǒng)崩潰。請解釋在系統(tǒng)恢復時會發(fā)生什么。

Answer:

假定在<T0abort>之前發(fā)生崩潰，按照課本16.4的恢復算法：

在重做階段：

,找到最后一個checkpoint,初始化undo-list={TO;T1).

?從上到下掃描日志：CH;C;700;600>,重做，C=600.

?<T1commit>,將T1從undoTist中刪除，undo-list={TO}.

?<T2start>,將T2加入undoTist,undo-1ist={TO;T2}.

?<T2;A;500;400>,重做，A=400.

?<T0;B;2000>,重做，B=2000.

在撤銷階段：

?從后往前掃描日志：<T0;B;2000>為redo-only,忽略.

?<T2;A;500;400>,撤銷，A=500,寫入日志：<T2;A;500>.

?<T2start>,將T2從undoTist中刪除，undo-1ist={T0},寫入

日志<T2abort>.

?<T0;B;2000;2050>,撤銷，B=2000,寫入日志：<T0;B;

2000>.

?<T0start>,將TO從undoTist刪除，寫入日志《T0abort>,

undo-list為空，結束.

恢復完畢后：A=500;B=2000;C=600.

10.17列出下列存儲關系數(shù)據(jù)庫的每個策略的兩個優(yōu)點和兩個缺

占-

J、、、?

a.在一個文件中存儲一個關系。

b.在一個文件中存儲多個關系（甚至是整個數(shù)據(jù)庫）。

Answer:

a優(yōu)點：直接使用0S提供的文件系統(tǒng)，使數(shù)據(jù)庫的設計變得容

易。同時使得數(shù)據(jù)庫的結構簡單明了。

缺點：限制了數(shù)據(jù)庫使用更復雜但性能好的結構提高性能。此

外，因為0S的文件系統(tǒng)本身讀取存儲也很耗時，更限制了性能

b優(yōu)點：可以使用復雜的存儲結構來提高數(shù)據(jù)庫的性能。

缺點：增加了數(shù)據(jù)庫的復雜性。增加數(shù)據(jù)庫的大小。

10.18在順序文件組織中，為什么即使當前只有一條溢出記錄，也

要使用一個溢出塊？

Answer:

因為塊已經(jīng)是可以從磁盤讀取的最小空間，無法使用更小的單位。

而若不使用溢出塊，采用別的方法將溢出塊的數(shù)據(jù)放入順序文件組

織中去，會導致性能的降低，一點點的空間成本無疑比性能的下降

更劃算。

11.3用下面的關鍵碼值集合建立一個B+樹

(2,3,5,7,11,17,19,23,29,31)

假設樹初始值為空，值按上升順序加入。根據(jù)一個節(jié)點所能容納指

針數(shù)的下列情況分別構造8+樹：

a.4b.6c.8

Answer:

a.

IIIIIIIIII

I2||3||5||7||口口|