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

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

Answer:

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

?存儲(chǔ)在數(shù)據(jù)庫(kù)中的數(shù)據(jù)，其邏輯結(jié)構(gòu)可能不同于其物理結(jié)構(gòu)，DBMS

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

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

結(jié)構(gòu)而沒(méi)有邏輯結(jié)構(gòu)。

?DBMS以一種高效的方式訪問(wèn)數(shù)據(jù)，一條數(shù)據(jù)在物理結(jié)構(gòu)上只需存

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

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

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

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

程序員的代碼來(lái)檢查是否滿足約束條件。

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

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

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

Answer:

物理獨(dú)立性是指用戶的應(yīng)用程序與存儲(chǔ)在磁盤(pán)上的數(shù)據(jù)庫(kù)中數(shù)據(jù)是

相互獨(dú)立的。

物理獨(dú)立性使應(yīng)用程序與存儲(chǔ)在磁盤(pán)上的數(shù)據(jù)相分離，應(yīng)用程序不依

賴于物理模式，因此物理模式改變了它們也無(wú)需重寫(xiě)。

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

a.適當(dāng)?shù)闹鞔a是什么？

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

Answer:

a.主碼：

branch:branchname

customer:customername

loan:loannumber

borrower:customername,loannumber

account:accountnumber

depositor:customername,accountnumber

b.外碼：

branch:無(wú)

customer:無(wú)

loan:branchname

borrower:customername,loannumber

account:branchname

depositor:customername,accountnumber

2.10考慮圖2虐所示advisor關(guān)系,advisor的主碼是s_id。假設(shè)

一個(gè)學(xué)生可以有多位指導(dǎo)老師。那么，s_id還是advisor的主碼嗎？

如果不是，advisor的主碼會(huì)是什么呢？

Answer:

不是，若一位學(xué)生有多個(gè)指導(dǎo)老師，那么表中可能有多個(gè)元組有相同

的s_id取值，這違反了主碼唯一的原則。此時(shí)主碼應(yīng)該為(s_id,

i_id).

2.11解釋術(shù)語(yǔ)關(guān)系和關(guān)系模式在意義上的區(qū)別。

Answer:

關(guān)系對(duì)應(yīng)程序設(shè)計(jì)語(yǔ)言中變量的概念，它是一個(gè)存在于物理存儲(chǔ)空

間中的實(shí)體，是真正存放數(shù)據(jù)的地方。關(guān)系模式對(duì)應(yīng)于程序設(shè)計(jì)語(yǔ)

言中類(lèi)型的概念，它僅僅是一種定義，定義了某種類(lèi)型的關(guān)系中應(yīng)

該存放什么屬性。關(guān)系可看作關(guān)系模式的實(shí)例化。

2.12考慮圖2-14所示關(guān)系數(shù)據(jù)庫(kù)。給出關(guān)系代數(shù)表達(dá)式來(lái)表示下列

每一個(gè)查詢：

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

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

住城市。

c.找出為“FirstBankCorporation”工作且掙錢(qián)超過(guò)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ù)庫(kù)。對(duì)于下列每個(gè)查詢，給出一個(gè)關(guān)

系代數(shù)表達(dá)式：

a.找出貸款額度超過(guò)10000美元的所有貸款號(hào)。

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

賬戶。

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

額大于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ù)庫(kù)中引入空值的兩個(gè)原因。

Answer:

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

2.15討論過(guò)程化和非過(guò)程化語(yǔ)言的相對(duì)優(yōu)點(diǎn)。

Answer:

非過(guò)程化語(yǔ)言簡(jiǎn)化了詢問(wèn)，用戶可以不用關(guān)心操作的具體過(guò)程。但同

時(shí)，需要花更多工作來(lái)優(yōu)化詢問(wèn)器，來(lái)快速找到結(jié)果。過(guò)程化語(yǔ)言需

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

很難較快的表達(dá)目標(biāo)結(jié)果，但設(shè)計(jì)好的操作過(guò)程，可能比詢問(wèn)其自動(dòng)

尋找，速度要快。

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

表達(dá)式來(lái)表示下列每一個(gè)查詢：

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

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

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

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

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

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

它位于SmallBankCorporation所位于的每一個(gè)城市。

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所示的關(guān)系數(shù)據(jù)庫(kù)。分別給出下列查詢的關(guān)系代

數(shù)表達(dá)式：

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設(shè)R=(A,B)且S=(A,C),r(R)和s(S)是關(guān)系。分別給出與下

列域關(guān)系演算表達(dá)式等價(jià)的關(guān)系代數(shù)表達(dá)式：

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設(shè)R=(A,B)且S=(A,C),r(R)和s(S)是關(guān)系。使用特殊常量

null,分別書(shū)寫(xiě)等價(jià)于下列表達(dá)式的元組關(guān)系演算表達(dá)式：

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用實(shí)踐習(xí)題8.6中的函數(shù)依賴計(jì)算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不變

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

8.28證明實(shí)踐習(xí)題8.1中的模式R的如下分解不是無(wú)損分解:

(A,B,C)

(C,D,E)

Answer:

根據(jù)提示，使用關(guān)系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.故該分解不是無(wú)損分解.

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

A-BCD

BC-DE

B-*D

D-A

a.計(jì)算B+.

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

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

釋。

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

e.利用原始的函數(shù)依賴集，給出r的一個(gè)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時(shí)，沒(méi)有新屬性加入result,算法終止。B+=

{A;B;C;D;E)

b.,A-BCD條件

?BCD--BC自反律

?A—BC傳遞律

?BC-DE條件

?A—DE傳遞律

?ABCDfBCDE增補(bǔ)律

?A—ABCD增補(bǔ)律

?A—BCDE傳遞律

?AF-ABCDEF增補(bǔ)律

?AF是超碼超碼定義

c.第一次repeat:F=Fc

?對(duì)于依賴A-BCD,D是無(wú)關(guān)屬性，因?yàn)椋鸄-BC;B-D｝可推出

A—D,將D去掉

?對(duì)于依賴BC-DE,D是無(wú)關(guān)屬性，因?yàn)锽-D可推出BCfD,將D

去掉。C是無(wú)關(guān)屬性，因?yàn)橛蒄可推出B-DE,將C去掉

?對(duì)于依賴BfD,沒(méi)有無(wú)關(guān)屬性

?對(duì)于依賴DfA,沒(méi)有無(wú)關(guān)屬性

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

為BfDE。其他不變

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

d.過(guò)程如下：

對(duì)Fc中的每一個(gè)依賴，生成如下模式：

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

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

沒(méi)有R包含于另一個(gè)R,故得到一個(gè)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)}

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

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

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

8.30列出關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)的三個(gè)目標(biāo)，并解釋為什么要達(dá)到每個(gè)

目標(biāo)。

Answer:

?無(wú)損分解，因?yàn)橐ＷC信息不丟失。

?保持依賴，在檢查依賴關(guān)系時(shí)避免做連接運(yùn)算。

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

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

Answer:

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

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

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

致。

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

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

現(xiàn)實(shí)世界。

?隔離性(isolation):多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，對(duì)于任意一對(duì)事

務(wù)，系統(tǒng)保證在其中一個(gè)事務(wù)看來(lái)，另一個(gè)事務(wù)都執(zhí)行完畢或未開(kāi)

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

免了多個(gè)事務(wù)交叉執(zhí)行可能帶來(lái)的不一致性。

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

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

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

14.15考慮以下兩個(gè)事務(wù)：

Ti3：read(X);

read(B)；

ifA=0thenB:=B+1;

write(B).

Ti4：read(B);

read(A)；

ifB=0thenAi=A+1;

write(A).

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

a.說(shuō)明包括這兩個(gè)事務(wù)的每一個(gè)串行執(zhí)行都保持?jǐn)?shù)據(jù)庫(kù)的一致性。

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

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

Answer:

a.兩個(gè)事務(wù)共有兩個(gè)串行執(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.不行。

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

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

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

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

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

T14的read(B),也無(wú)法實(shí)現(xiàn)非沖突可串行化。因?yàn)閷?duì)于T13,T14

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

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

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

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

封鎖點(diǎn)串行化。

Answer:

給定任意兩個(gè)事務(wù)Ti,Tj,設(shè)其封鎖點(diǎn)為ai,aj,先證明當(dāng)優(yōu)先級(jí)

圖中存在有向邊Ti-Tj時(shí)，必有ai<aj：當(dāng)有向邊Ti,Tj存在

時(shí)，表明Ti,Tj先后讀/寫(xiě)同一個(gè)數(shù)據(jù)項(xiàng)，且Ti先于門(mén)，在封鎖

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

間只能由一個(gè)事務(wù)持有，則Ti先獲得鎖，Ti在其封鎖點(diǎn)ai后釋放

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

對(duì)于任意N個(gè)事務(wù)，不存在兩個(gè)封鎖點(diǎn)相同的事務(wù)，不妨令al

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

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

拓?fù)渑判颉?/p>

15.2考慮下面兩個(gè)事務(wù)：

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

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

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

協(xié)議。這兩個(gè)事務(wù)會(huì)引起死鎖嗎？

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.當(dāng)調(diào)度如下時(shí)，這兩個(gè)事務(wù)會(huì)引起死鎖。

T34T35

lock-S(A)

lock-S(B)

Read(B)

read(A)

lock-X(B)

lock-X(A)

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

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

Answer:

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

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

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

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

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

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

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

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

Answer:

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

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

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

集，即會(huì)導(dǎo)致并發(fā)度的下降。

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

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

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

?樹(shù)上的第二次以及以后的封鎖申請(qǐng)僅當(dāng)被申請(qǐng)結(jié)點(diǎn)的父結(jié)點(diǎn)上有鎖

時(shí)才能

發(fā)出。

?數(shù)據(jù)項(xiàng)解鎖可在任何時(shí)候進(jìn)行。

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

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

Answer:

對(duì)于兩棵樹(shù)：

執(zhí)行如下調(diào)度:

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)

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

15.24如果通過(guò)死鎖避免機(jī)制避免了死鎖后，餓死仍有可能嗎？解

釋你的答案。

Answer:

仍然有可能會(huì)餓死，通過(guò)死鎖恢復(fù)，在回滾的時(shí)候需要選擇犧牲

者，這就可能導(dǎo)致餓死。而死鎖預(yù)防也可能導(dǎo)致餓死，原因是一樣

的。

16.18考慮圖16-5中的日志。假設(shè)恰好在CTOabort》日志記錄寫(xiě)

出之前系統(tǒng)崩潰。請(qǐng)解釋在系統(tǒng)恢復(fù)時(shí)會(huì)發(fā)生什么。

Answer:

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

在重做階段：

,找到最后一個(gè)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.

在撤銷(xiāo)階段：

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

?<T2;A;500;400>,撤銷(xiāo)，A=500,寫(xiě)入日志：<T2;A;500>.

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

日志<T2abort>.

?<T0;B;2000;2050>,撤銷(xiāo)，B=2000,寫(xiě)入日志：<T0;B;

2000>.

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

undo-list為空，結(jié)束.

恢復(fù)完畢后：A=500;B=2000;C=600.

10.17列出下列存儲(chǔ)關(guān)系數(shù)據(jù)庫(kù)的每個(gè)策略的兩個(gè)優(yōu)點(diǎn)和兩個(gè)缺

占-

J、、、?

a.在一個(gè)文件中存儲(chǔ)一個(gè)關(guān)系。

b.在一個(gè)文件中存儲(chǔ)多個(gè)關(guān)系（甚至是整個(gè)數(shù)據(jù)庫(kù)）。

Answer:

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

易。同時(shí)使得數(shù)據(jù)庫(kù)的結(jié)構(gòu)簡(jiǎn)單明了。

缺點(diǎn)：限制了數(shù)據(jù)庫(kù)使用更復(fù)雜但性能好的結(jié)構(gòu)提高性能。此

外，因?yàn)?S的文件系統(tǒng)本身讀取存儲(chǔ)也很耗時(shí)，更限制了性能

b優(yōu)點(diǎn)：可以使用復(fù)雜的存儲(chǔ)結(jié)構(gòu)來(lái)提高數(shù)據(jù)庫(kù)的性能。

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

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

要使用一個(gè)溢出塊？

Answer:

因?yàn)閴K已經(jīng)是可以從磁盤(pán)讀取的最小空間，無(wú)法使用更小的單位。

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

織中去，會(huì)導(dǎo)致性能的降低，一點(diǎn)點(diǎn)的空間成本無(wú)疑比性能的下降

更劃算。

11.3用下面的關(guān)鍵碼值集合建立一個(gè)B+樹(shù)

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

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

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

a.4b.6c.8

Answer:

a.

IIIIIIIIII

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