本次lab的目的是练习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

当A = a, a时，B = 1, 1， C = x, y，所以A推出B保留，而A是不能推出C的，B也不能推出C，AB不能推出C；
当A = b, b时，B = 2, 2， C = y, z，和上面结论一致，没有新的结论；
当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对应，反之，也就是说A和B是一一对应的，用离散数学的术语说是双射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+

根据上述F，可以推出的结论在括号中显示：A-->B(AB)，A/B/AB无法推出任何结论，所以A+ = {A, B}

2.2 ACEG+

根据上述F，可以推出的结论在括号中显示：A-->B(ABCEG), BC-->F(ABCEFG), BEG-->FA(ABCEFG)，所以ACEG+ = {A, B, C, E, F, G}

2.3 BD+

根据上述F，可以推出的结论在括号中显示：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.

根据F，如果选定A作为candidate key，则B可以被A推导，C不可以被推导，所以candidate key更新为AC，D不可以被推导，所以candidate key更新为ACD，E可以被BC推导；
如果选定B作为candidate key，C不可以被推导，所以candidate key更新为BC，D不可以被推导，所以candidate key更新为BCD，E可以被BC推导，A可以被ED推导；
CD在上述两中情况下都是candidate key，继续思考E：
如果选定E作为candidate key，C不可以被推导，所以candidate key更新为EC，D不可以被推导，所以candidate key更新为ECD，A可以被ED推导，B可以被A推导。
综上，所有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
因为-->右侧的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）
二者的区别是BCNF不能接受Y是key的一个attribute。
左边没有super key，而任何一个FD都不是子集关系，所以不是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推出的最多，所以先假设B是candidate key，B-->C(BC), C-->D(BCD), C-->A(ABCD)。candidate key是B。
C不是key却出现在-->左边，所以不是BCNF。
C-->D，C, D都是非key，所以不是3NF。

4.2 B → C, D → A

CA可以被推出，优先思考BD，假设B是candidate key，B-->C(BC)，D不可以被推出，所以更新candidate key为BD，D-->A(ABCD)。candidate key是BD。
因为左边都不是superkey，而左右又不是子集关系，所以不是BCNF；而右边又不是single key attribute，所以也不是3NF。

4.3 ABC → D, D → A

DA可以被推出，优先思考BC，假设BC是candidate key，不能推出任何内容，更新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，二者也不是子集关系，所以不属于BCNF。

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

BDC可以被推出，假设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都可以被推出，假设candidate key是A，A无法推出任何，更新candidate key为AB，AB-->C(ABC), AD-->D(ABCD)；假设candidate key是B，B无法推出任何，更新candidate key为BC，C-->A(ABC), AB-->D(ABCD)；假设candidate key是C，C-->A(AC)，更新candidate key为CD，D-->B(ABCD)；假设candidate key是D，D-->B(BD)，更新candidate key为AD，AB-->C(ABCD)。所以candidate key可能是AB, BC, CD, AD。
因为-->右侧的CDAB都是candidate key中的attribute，所以符合3NF。
如果candidate key是AB，那么C-->A既不是子集关系，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
和上面练习思路一致，这里也都是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，FD变为C-->A, B-->C。C-->A违背了BCNF，拆解出来CA。
剩余BC，FD变为B-->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，FD变为D-->A，违背BCNF，拆解出来DA。
剩余BD，FD为空。
所以最终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，FD为空。
所以最终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，FD变为A-->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，FD变为D-->B，不符合BCNF，拆解出来DB。
剩余CD，FD为空。
所以BCNF为(R1(CA), R2(DB), R3(CD))，但彼此之间没有联系，所以还要加入联系，变成(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.

根据定义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，所以根据定义推出
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

后续还有若干练习，和前面的题目大同小异，不再赘述。