本次lab的目的是練習(xí)Relational Design Theory宝踪。

1. Functional dependencies

1.1 a

What functional dependencies are implied if we know that a set of attributes X is a candidate key for a relation R?
因?yàn)閄是candidate key毁枯，所以X可以推出所有其他attribute底靠。即X --> R - X

1.2 b

What functional dependencies can we infer do not hold by inspection of the following relation?

A   B   C
a   1   x
b   2   y
c   1   z
d   2   x
a   1   y
b   2   z

當(dāng)A = a, a時(shí)雁社，B = 1, 1， C = x, y久脯，所以A推出B保留，而A是不能推出C的帘撰，B也不能推出C，AB不能推出C摧找；
當(dāng)A = b, b時(shí)核行，B = 2, 2牢硅， C = y, z芝雪，和上面結(jié)論一致，沒(méi)有新的結(jié)論绵脯；
當(dāng)A = c, d時(shí)蛆挫，B = 1, 2妙黍， C = z, x悴侵，確認(rèn)A-->B可免。
同理做粤，判斷B-->A？因?yàn)锽= 1, 1, 1時(shí)妇垢，A = a, c, a肉康，所以B不能推出A。
判斷C-->A涨薪？因?yàn)镃 = x, x時(shí)炫乓，A = a, d，所以C不能推出A
判斷C-->B末捣？因?yàn)镃 = x, x時(shí)光督，B = 1, 2塔粒，所以C不能推出B

1.3 c

Suppose that we have a relation schema R(A,B,C) representing a relationship between two entity sets E and F with keys A and B respectively, and suppose that R has (at least) the functional dependencies A → B and B → A. Explain what this tells us about the relationship between E and F.
A-->B說(shuō)明每個(gè)A有一個(gè)B對(duì)應(yīng)，反之船老，也就是說(shuō)A和B是一一對(duì)應(yīng)的，用離散數(shù)學(xué)的術(shù)語(yǔ)說(shuō)是雙射bijection柳畔。

2. Relation and FD exercise1

Consider the relation R(A,B,C,D,E,F,G) and the set of functional dependencies F = { A → B, BC → F, BD → EG, AD → C, D → F, BEG → FA } compute the following:

2.1 A+

根據(jù)上述F薪韩，可以推出的結(jié)論在括號(hào)中顯示：A-->B(AB)，A/B/AB無(wú)法推出任何結(jié)論罗捎，所以A+ = {A, B}

2.2 ACEG+

根據(jù)上述F拉盾，可以推出的結(jié)論在括號(hào)中顯示：A-->B(ABCEG), BC-->F(ABCEFG), BEG-->FA(ABCEFG)，所以ACEG+ = {A, B, C, E, F, G}

2.3 BD+

根據(jù)上述F倒得，可以推出的結(jié)論在括號(hào)中顯示：BD-->EG(BDEG), D-->F(BDEFG), BEG-->FA(ABDEFG), AD-->C(ABCDEFG)夭禽，所以ACEG+ = {A, B, C, D, E, F, G}

3. Relation and FD exercise2

Consider the relation R(A,B,C,D,E) and the set set of functional dependencies F = { A → B, BC → E, ED → A }

3.1 List all of the candidate keys for R.

根據(jù)F讹躯，如果選定A作為candidate key，則B可以被A推導(dǎo)蜀撑，C不可以被推導(dǎo)酷麦，所以candidate key更新為AC，D不可以被推導(dǎo)沃饶，所以candidate key更新為ACD糊肤，E可以被BC推導(dǎo)；
如果選定B作為candidate key业舍，C不可以被推導(dǎo)，所以candidate key更新為BC舷暮，D不可以被推導(dǎo)下面，所以candidate key更新為BCD，E可以被BC推導(dǎo)耗啦，A可以被ED推導(dǎo)机杜；
CD在上述兩中情況下都是candidate key，繼續(xù)思考E：
如果選定E作為candidate key，C不可以被推導(dǎo)会喝，所以candidate key更新為EC肢执，D不可以被推導(dǎo)，所以candidate key更新為ECD兴溜，A可以被ED推導(dǎo)耻陕，B可以被A推導(dǎo)。
綜上膘怕，所有candidate keys是ACD, BCD, CDE

3.2 Is R in third normal form (3NF)?

3NF的要求是：對(duì)所有的FDs X --> Y
（1）要么Y是X的子集
（2）要么X是超鍵（candidate key/ super key）
（3）要么Y是key中的一個(gè)attribute
因?yàn)?->右側(cè)的BEA都是candidate key的attribute召庞，所以符合3NF

3.3 Is R in Boyce-Codd normal form (BCNF)?

通常3NF都符合BCNF篮灼，但個(gè)別的不符合。BCNF的要求是：對(duì)所有的FDs X --> Y
（1）要么Y是X的子集
（2）要么X是超鍵（candidate key/ super key）
二者的區(qū)別是BCNF不能接受Y是key的一個(gè)attribute诅诱。
左邊沒(méi)有super key，而任何一個(gè)FD都不是子集關(guān)系旦袋，所以不是BCNF疤孕。

4. Relation and FD exercise3

Consider a relation R(A,B,C,D). For each of the following sets of functional dependencies, assuming that those are the only dependencies that hold for R, do the following:
a. List all of the candidate keys for R.
b. Show whether R is in Boyce-Codd normal form (BCNF)?
c. Show whether R is in third normal form (3NF)?

4.1 C → D, C → A, B → C

DAC可以被推出，C推出的最多鹉戚，所以先假設(shè)B是candidate key专控，B-->C(BC), C-->D(BCD), C-->A(ABCD)。candidate key是B赢底。
C不是key卻出現(xiàn)在-->左邊柏蘑，所以不是BCNF。
C-->D洽损，C, D都是非key革半，所以不是3NF又官。

4.2 B → C, D → A

CA可以被推出，優(yōu)先思考BD访娶，假設(shè)B是candidate key觉阅，B-->C(BC)，D不可以被推出劫哼，所以更新candidate key為BD割笙，D-->A(ABCD)眯亦。candidate key是BD妻率。
因?yàn)樽筮叾疾皇莝uperkey板祝，而左右又不是子集關(guān)系，所以不是BCNF孤里；而右邊又不是single key attribute橘洞，所以也不是3NF。

4.3 ABC → D, D → A

DA可以被推出虏等，優(yōu)先思考BC适肠，假設(shè)BC是candidate key迂猴，不能推出任何內(nèi)容背伴，更新candidate key為ABC，ABC-->D(ABCD)息尺；更新candidte key為BCD疾掰，D-->A(ABCD)。所以candidate key是ABC或BCD炭懊。
D-->A中的A是key的一部分侮腹，所以被允許稻励，符合3NF愈涩。
D-->A的D不是key履婉，二者也不是子集關(guān)系斟览，所以不屬于BCNF。

4.4 A → B, BC → D, A → C

BDC可以被推出狸棍，假設(shè)candidate key是A味悄，A-->B(AB), A-->C(ABC), BC-->D(ABCD)。所以candidate key是A唐片。
BC-->D左右都是non-key费韭，不符合3NF庭瑰。
BC不是key，不符合BCNF督暂。

4.5 AB → C, AB → D, C → A, D → B

ABCD都可以被推出穷吮，假設(shè)candidate key是A捡鱼，A無(wú)法推出任何，更新candidate key為AB缠诅，AB-->C(ABC), AD-->D(ABCD)乍迄；假設(shè)candidate key是B，B無(wú)法推出任何汉匙，更新candidate key為BC，C-->A(ABC), AB-->D(ABCD)戏自；假設(shè)candidate key是C伤锚，C-->A(AC)屯援，更新candidate key為CD，D-->B(ABCD)弯淘；假設(shè)candidate key是D吉懊，D-->B(BD)，更新candidate key為AD态鳖，AB-->C(ABCD)恶导。所以candidate key可能是AB, BC, CD, AD惨寿。
因?yàn)?->右側(cè)的CDAB都是candidate key中的attribute，所以符合3NF虎韵。
如果candidate key是AB缸废，那么C-->A既不是子集關(guān)系企量，C也不是key亡电，所以不符合BCNF。

4.6 A → BCD

可以直接看出candidate key是A恕汇。
既符合3NF瘾英，也符合BCNF。

5. Non-trivial FDs exercise1

Specify the non-trivial functional dependencies for each of the relations in the following Teams-Players-Fans schema and then show whether the overall schema is in BCNF.

Team(name(key), captain)
Player(name(key), teamPlayedFor)
Fan(name(key), address)
TeamColours(teamName(key), colour(key))
FavouriteColours(fanName(key), colour(key))
FavouritePlayers(fanName(key), playerName(key))
FavouriteTeams(fanName(key), teamName(key))

Functional dependencies:
Team: name → captain
Player: name → teamPlayedFor
Fan: name → address
TeamColours: no non-trivial fds
FavouriteColours: no non-trivial fds
FavouritePlayers: no non-trivial fds
FavouriteTeams: no non-trivial fds
non-trivial FDs就是找非子集的dependency但惶，如果只有兩個(gè)variable，都是key阳啥，那么都是trivial的察迟。以上都屬于superkey推出non-key，所以都是BCNF喊废。

6. Non-trivial FDs exercise2

Specify the non-trivial functional dependencies for each of the relations in the following Trucks-Shipments-Stores schema and then show whether the overall schema is in BCNF.

Warehouse(warehouse#(key), address)
Source(trip(key), warehouse(key))
Trip(trip#(key), date, truck)
Truck(truck#(key), maxvol, maxwt)
Shipment(shipment#(key), volume, weight, trip, store)
Store(store#(key), storename, address)

Functional dependencies:
Warehouse ... warehouse# → address
Source ... no non-trivial fds
Trip ... trip# → date,truck
Truck ... truck# → maxvol,maxwt
Shipment ... shipment# → volume,weight,trip,store
Store ... store# → storename,address
和上面練習(xí)思路一致污筷，這里也都是BCNF乍赫。

7. BCNF & 3NF decomposition

For each of the sets of dependencies in question 4:
(1) if R is not already in 3NF, decompose it into a set of 3NF relations;
(2) if R is not already in BCNF, decompose it into a set of BCNF relations

7.1 C → D, C → A, B → C

candidate key是B雷厂，不是BCNF，不是3NF
（1）decompose to BCNF
C-->D違背了BCNF诈皿，拆解出來(lái)CD像棘。
剩余ABC，F(xiàn)D變?yōu)镃-->A, B-->C截歉。C-->A違背了BCNF瘪松，拆解出來(lái)CA。
剩余BC性宏，F(xiàn)D變?yōu)锽-->C状飞，符合BCNF。
所以最終BCNF為(R1(CD), R2(CA), R3(BC))
（2）decompose to 3NF
minimal cover: C-->D, C-->A, B-->C
key: B
F' = C-->DA, B-->C
CDA(KEY = C), BC(KEY = B)

7.2 B → C, D → A

candidate key是BD酵使，不是BCNF口渔，不是3NF
（1）decompose to BCNF
B-->C違背BCNF穿撮，拆解出來(lái)BC悦穿。
剩余ABD，F(xiàn)D變?yōu)镈-->A礁扮，違背BCNF瞬沦，拆解出來(lái)DA。
剩余BD逛钻，F(xiàn)D為空。
所以最終BCNF為(R1(BC), R2(DA), R3(BD))
（2）decompose to 3NF
minimal cover無(wú)法合并曙痘，所以3NF是BC(KEY = B), DA(KEY = A), BD(KEY = BD)

7.3 ABC → D, D → A

candidate key是ABC/BCD屡江，不是BCNF赛不，是3NF
（1）decompose to BCNF
D-->A違背BCNF踢故，拆解出來(lái)DA惹苗。
剩余BCD桩蓉，F(xiàn)D為空劳闹。
所以最終BCNF為(R1(DA), R2(BCD))

7.4 A → B, BC → D, A → C

candidate key是A本涕，不是BCNF，不是3NF
（1）decompose to BCNF
BC-->D違背BCNF样漆，拆解出BCD晦闰。
剩余ABC呻右，F(xiàn)D變?yōu)锳-->B, A-->C，都符合BCNF骗奖。
所以最終BCNF為(R1(BCD), R2(AB), R3(AC))
（2）decompose to 3NF
minimal cover和FDs一致醒串，所以3NF是AB(KEY = A), BCD(KEY = BC), AC(KEY = A)

7.5 AB → C, AB → D, C → A, D → B

candidate key是AB, BC, CD, AD芜赌，不是BCNF，是3NF
（1）decompose to BCNF
C-->A違背BCNF膘壶，拆解出來(lái)CA
剩余BCD颓芭，F(xiàn)D變?yōu)镈-->B柬赐，不符合BCNF，拆解出來(lái)DB州藕。
剩余CD床玻，F(xiàn)D為空。
所以BCNF為(R1(CA), R2(DB), R3(CD))贫堰，但彼此之間沒(méi)有聯(lián)系严嗜，所以還要加入聯(lián)系洲敢，變成(R1(CA), R2(DB), R3(CD), R4(ABC), R5(ABD))

7.6 A → BCD

candidate key是A，是BCNF睦优，是3NF

8. Case1

Consider (yet another) banking application that contains information about accounts, branches and customers. Each account is held at a specific branch, but a customer may hold more than one account and an account may have more than one associated customer.
Consider an unnormalised relation containing all of the attributes that are relevant to this application:

acct# - unique account indentifier
branch# - unique branch identifier
tfn - unique customer identifier (tax file number)
kind - type of account (savings, cheque, ...)
balance - amount of money in account
city - city where branch is located
name - customer's name
i.e. consider the relation R(acct#, branch#, tfn, kind, balance, city, name)

Based on the above description:

8.1 Devise a suitable set of functional dependencies among these attributes.

根據(jù)定義acct# --> kind, balance汗盘；branch#-->city隐孽；tfn-->name

8.2 Using these functional dependencies, decompose R into a set of BCNF relations.

Account(acct#(key), kind, balance, branch)
Branch(branch#(key), city)
Customer(tfn(key), name)
CustAcc(customer(key), account(key))

8.3 State whether the new relations are also in 3NF.

They fit in 3NF.

9. Case2

Consider a schema representing projects within a company, containing the following information:
pNum - project's unique identifying number
pName - name of project
eNum - employee's unique identifying number
eName - name of employee
jobClass - type of job that employee has on this project
payRate - hourly rate, dependent on the kind of job being done
hours - total hours worked in this job by this employee
This schema started out life as a large spreadsheet and now the company wants to put it into a database system.

As a spreadsheet, its schema is: R(pNum, pName, eNum, eName, jobClass, payRate, hours)

Based on the above description:

9.1 Devise a suitable set of functional dependencies among these attributes.

primary key是unique菱阵，所以根據(jù)定義推出
pNum → pName
eNum → eName
jobClass → payRate
pNum,eNum → jobClass,payRate,hours

9.2 Using these functional dependencies, decompose R into a set of BCNF relations.

pNum → pName is a dependency on part of the key
to fix: decompose to R1(pNum,eNum,eName,jobClass,payRate,hours) and R2(pNum,pName)
eNum → eName is a dependency on part of the key
to fix: decompose to R1(pNum,eNum,jobClass,payRate,hours) and R2(pNum,pName) and R3(eNum,eName)
jobClass → payRate is a dependency on a non-key attribute
to fix: decompose to R1(pNum,eNum,jobClass,hours) and R2(pNum,pName) and R3(eNum,eName) and R4(jobClass,payRate)

pNum → pName
eNum → eName
jobClass → payRate
pNum,eNum → jobClass,hours

Project(pNum, pName)
Employee(eNum, eName)
AwardRates(jobClass, payRate)
Assignment(pNum, eNum, jobClass, hours)

9.3 State whether the new relations are also in 3NF.

The new schema is not in 3NF because we have lost the dependency: pNum,eNum → payRate

后續(xù)還有若干練習(xí)，和前面的題目大同小異嫡锌，不再贅述。