本次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?
因為X是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時，B = 1, 1， C = x, y，所以A推出B保留，而A是不能推出C的，B也不能推出C，AB不能推出C；
當(dāng)A = b, b時，B = 2, 2， C = y, z，和上面結(jié)論一致，沒有新的結(jié)論；
當(dāng)A = c, d時，B = 1, 2， C = z, x，確認A-->B。
同理，判斷B-->A？因為B= 1, 1, 1時，A = a, c, a，所以B不能推出A。
判斷C-->A？因為C = x, x時，A = a, d，所以C不能推出A
判斷C-->B？因為C = x, x時，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說明每個A有一個B對應(yīng)，反之，也就是說A和B是一一對應(yīng)的，用離散數(shù)學(xué)的術(shù)語說是雙射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é)論在括號中顯示：A-->B(AB)，A/B/AB無法推出任何結(jié)論，所以A+ = {A, B}

2.2 ACEG+

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

2.3 BD+

根據(jù)上述F，可以推出的結(jié)論在括號中顯示：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的要求是：對所有的FDs X --> Y
（1）要么Y是X的子集
（2）要么X是超鍵（candidate key/ super key）
（3）要么Y是key中的一個attribute
因為-->右側(cè)的BEA都是candidate key的attribute，所以符合3NF

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

通常3NF都符合BCNF，但個別的不符合。BCNF的要求是：對所有的FDs X --> Y
（1）要么Y是X的子集
（2）要么X是超鍵（candidate key/ super key）
二者的區(qū)別是BCNF不能接受Y是key的一個attribute。
左邊沒有super key，而任何一個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。
因為左邊都不是superkey，而左右又不是子集關(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無法推出任何，更新candidate key為AB，AB-->C(ABC), AD-->D(ABCD)；假設(shè)candidate key是B，B無法推出任何，更新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。
因為-->右側(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，如果只有兩個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，拆解出來CD。
剩余ABC，F(xiàn)D變?yōu)镃-->A, B-->C。C-->A違背了BCNF，拆解出來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，拆解出來BC。
剩余ABD，F(xiàn)D變?yōu)镈-->A，違背BCNF，拆解出來DA。
剩余BD，F(xiàn)D為空。
所以最終BCNF為(R1(BC), R2(DA), R3(BD))
（2）decompose to 3NF
minimal cover無法合并，所以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，拆解出來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，拆解出來CA
剩余BCD，F(xiàn)D變?yōu)镈-->B，不符合BCNF，拆解出來DB。
剩余CD，F(xiàn)D為空。
所以BCNF為(R1(CA), R2(DB), R3(CD))，但彼此之間沒有聯(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í)，和前面的題目大同小異，不再贅述。