| COMP3311 24T2 |
Week 09 Relational Design Theory |
Database Systems |
|
Notation: in the relational schemas below,
primary key attributes are underlined
(e.g. Student(id, name, degreeCode) Degree(code, name, requirements) Subject(code, name, syllabus) Marks(studentId, subjectCode, teachingTerm, mark) In their respective relations, the student id, the degree code and the subject code are primary keys. In the Student relation, the degree code is a foreign key. In the Marks relation, the three attributes student id, subject code and teaching term together form the primary key; the first two (student id and subject code) are also foreign keys. |
Functional dependencies.
What functional dependencies are implied if we know that a set of attributes X is a candidate key for a relation R?
Answer:
X functionally determines all of the other attributes (i.e. X → R-X)
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 |
Answer:
The tuples (a,1,x) and (a,1,y) ensure that
A → C
and
B → C
and
AB → C
do not hold.
The tuples (a,1,x) and (d,2,x) ensure that
C → B
and
C → A
do not hold.
The tuples (a,1,x) and (c,1,z) ensure that
B → A
and
B → C
do not hold.
Note that C → A
is not disproved by (a,1,x) and (a,1,y) or (b,2,y) and (b,2,z).
For other combinations of ABC there is only one instance
in the relation and so we cannot infer anything about dependency.
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.
Answer:
The A → B tells us that every A value in R has exactly one corresponding B value, and similarly B → A tells us that every B value has exactly one corresponding A value. In other words, the relationship must be 1:1.
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:
A+
Answer:
Derivation of A+ ...ACEG+
Answer:
Derivation of ACEG+
given {A,C,E,G}
... using A → B gives {A,B,C,E,G}
... using BC → F gives {A,B,C,E,F,G}
... no more
ACEG+ = {A,B,C,E,F,G}
BD+
Answer:
Derivation of BD+
given {B,D}
... using BD → EG gives {B,D,E,G}
... using BEG → FA gives {A,B,D,E,F,G}
... using AD → C gives {A,B,C,D,E,F,G}
... no more
BD+ = {A,B,C,D,E,F,G}
Consider the relation R(A,B,C,D,E) and the set set of functional dependencies F = { A → B, BC → E, ED → A }
List all of the candidate keys for R.
Answer:
A candidate key is any set X, such that X+ = R and there is no Y subset of X such that Y+ = R.
In this case, the candidate keys are CDE, ACD, BCD.
Is R in third normal form (3NF)?
Answer:
Yes, because the right hand sides of all dependencies (i.e. B, E, A) are parts of keys.
Is R in Boyce-Codd normal form (BCNF)?
Answer:
No, because none of the left hand sides (i.e. A, BC, ED) contains a key.
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:
List all of the candidate keys for R.
Show whether R is in Boyce-Codd normal form (BCNF)?
Show whether R is in third normal form (3NF)?
C → D, C → A, B → C
Answer:
Answer:
Answer:
Answer:
Answer:
Answer:
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, captain) Player(name, teamPlayedFor) Fan(name, address) TeamColours(teamName, colour) FavouriteColours(fanName, colour) FavouritePlayers(fanName, playerName) FavouriteTeams(fanName, teamName)
Answer:
Functional dependencies:
For each relation, every non-trivial fd has a left hand side which is a super key ⇒ each relation is in BCNF and the whole schema is in BCNF.
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#, address) Source(trip, warehouse) Trip(trip#, date, truck) Truck(truck#, maxvol, maxwt) Shipment(shipment#, volume, weight, trip, store) Store(store#, storename, address)
Answer:
Functional dependencies:
For each relation, every non-trivial fd has a left hand side which is a super key ⇒ each relation is in BCNF and the whole schema is in BCNF.
This just goes to show that ER design generally leads to well-structured relational designs.
For each of the sets of dependencies in question 4:
if R is not already in 3NF, decompose it into a set of 3NF relations
if R is not already in BCNF, decompose it into a set of BCNF relations
C → D, C → A, B → C
Answer:
B → C, D → A
Answer:
ABC → D, D → A
Answer:
A → B, BC → D, A → C
Answer:
AB → C, AB → D, C → A, D → B
Answer:
A → BCD
Answer:
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:
i.e. consider the relation R(acct#, branch#, tfn, kind, balance, city, name)
Based on the above description:
Devise a suitable set of functional dependencies among these attributes.
Answer:
acct# → kind, balance, branch#
branch# → city
tfn → name
These all come from the semantics of the problem (e.g. each account has exactly one type and balance, and is held at a specific branch).
Using these functional dependencies, decompose R into a set of 3NF relations.
Answer:
Computing the minimal cover for the above FDs produces the same set of FDs. In other words, they were already a minimal cover.
In this case, the 3NF decomposition from applying the above three fds produces a BCNF decomposition as well. This is the simplest and most natural decomposition of the problem.
Account(acct#, kind, balance, branch) Branch(branch#, city) Customer(tfn, name) CustAcc(customer, account)
The first three relations come directly from the dependencies; the last relation comes from the final check for a relation with a candidate key for R in the 3NF algorithm.
State whether the new relations are also in BCNF.
Answer:
The first three tables are in BCNF, since they have single-attribute primary keys and no FDs that don't involve the primary key. The final table has two attributes, but both are part of the primary key, so it is also in BCNF. So, the schema is in BCNF.
Consider a schema representing projects within a company, containing the following information:
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:
Answer:
pNum → pName
eNum → eName
jobClass → payRate
pNum,eNum → jobClass,payRate,hours
The above implies that pNum,eNum is a key for this relation (these attributes determine all of the others).
Based on semantics given in the descriptions and on some further assumptions, such as:
Answer:
Following the BCNF decomposition algorithm ...
The relevant functional dependencies are now:
pNum → pName
eNum → eName
jobClass → payRate
pNum,eNum → jobClass,hours
With these dependencies there are no violations of BCNF, so the schema is now in BCNF, and we could rename the relations as:
Project(pNum, pName) Employee(eNum, eName) AwardRates(jobClass, payRate) Assignment(pNum, eNum, jobClass, hours)
Answer:
The new schema is not in 3NF because we have lost the dependency: pNum,eNum → payRate
Real estate agents conduct visits to rental properties
Describe any functional dependencies that exist in this data. The table of sample data below below may give some ideas:
P# | When | Address | Notes | S# | Name | CarReg ----+-------------+------------+---------------+------+-------+------- PG4 | 03/06 15:15 | 55 High St | Bathroom leak | SG44 | Rob | ABK754 PG1 | 04/06 11:10 | 47 High St | All ok | SG44 | Rob | ABK754 PG4 | 03/07 12:30 | 55 High St | All ok | SG43 | Dave | ATS123 PG1 | 05/07 15:00 | 47 High St | Broken window | SG44 | Rob | ABK754 PG2 | 13/07 12:00 | 12 High St | All ok | SG42 | Peter | ATS123 PG1 | 10/08 09:00 | 47 High St | Window fixed | SG42 | Peter | ATS123 PG3 | 11/08 14:00 | 99 High St | All ok | SG41 | John | AAA001 PG4 | 13/08 10:00 | 55 High St | All ok | SG44 | Rob | ABK754 PG3 | 05/09 11:15 | 99 High St | Bathroom leak | SG42 | Peter | ATS123
State assumptions used in determining the functional dependencies.
Answer:
Other dependencies are possible (e.g. M → S), but they appear less plausible, given the semantics of the application.
Consider a company supplying temporary employees to hotels:
Contract | TFN | Name | Hrs | ABN | Hotel ---------+------+------------+-----+------+------------- C12345 | T311 | John Smith | 12 | H765 | Four Seasons C18765 | T255 | Brad Green | 12 | H234 | Crown Plaza C12345 | T311 | John Smith | 12 | H765 | Four Seasons C12345 | T255 | Brad Green | 10 | H765 | Four Seasons C14422 | T311 | John Smith | 6 | H222 | Sheraton C14422 | T888 | Will Smith | 9 | H222 | Sheraton C18477 | T123 | Clair Bell | 15 | H222 | Sheraton
State assumptions used in determining the functional dependencies.
Answer:
Describe any functional dependencies that exist in this data.
Other potential dependencies that do not apply:
What functional dependencies exist in the following table:
A | B | C | D -----+-----+-----+----- 1 | a | 6 | x 2 | b | 7 | y 3 | c | 7 | z 4 | d | 6 | x 5 | a | 6 | y 6 | b | 7 | z 7 | c | 7 | x 8 | d | 6 | y
How is this case different to the previous two?
Answer:
Since A has a different value in every tuple, it determines all other attributes:
A → B, A → C, A → D or A → BCD
Also, A in combination with any other subset of attributes determines all the others.
Similar reasoning could be applied to the combination BCD, since it's unique over all tuples.
It also appears that B → C, but not C → B.
This case is different to the previous two because there are no application semantics to draw on to determine reasonableness of choice of FDs. All you can do is look for counter-examples to eliminate certain potential dependencies. Example: since (C=6,B=a) and (C=6,B=d) we can eliminate C → B.
Compute a minimal cover for:
F = { B → A, D → A, AB → D }
Answer:
Steps in converting to a minimal cover:
B → A, D → A, AB → D is already in canonical form.
The only possible redundant attributes are A or B in AB → D.
We can prove that A is redundant as follows:
B → A ⇒ BB → AB ⇒ B → AB
AB → D + B → AB ⇒ B → D
Since we have AB → D and B → D, A is redundant.
The above elimination leaves: B → A, D → A, B → D
But D → A, B → D ⇒ B → A
So, the minimal cover is: B → D, D → A
Using the functional dependencies you produced in Q10, convert the real-estate inspection spreadsheet (single table), into a BCNF relational schema.
Answer:
FDs: P → A, PW → NS, S → MC (reduced from the 5 FDs given above)
Consider the schema R and set of fds F
R = ABCDEFGH
F = { ABH → C, A → DE, BGH → F, F → ADH, BH → GE }
Produce a BCNF decomposition of R.
Answer:
This is just one of many possible decompositions. Variations occur because of choice of candidate key (although not in this example) and choice of non-BCNF FD to resolve at each step.
Using the functional dependencies you produced in Q10, convert the real-estate inspection spreadsheet (single table), into a 3NF relational schema.
Answer:
FDs: P → A, PW → N, PW → S, S → M, S → C
This looks like a minimal cover; no redunant attributes; no redundant FDs.
3NF is constructed directly from the minimal cover, after combinining dependencies with a common right hand side.
Fc = P → A, PW → NS, S → MC
Gives the following tables (with table keys in bold):
PA PWNS SMC
Since PW is a key for the whole schema, and since a table contains this key, the 3NF decompostion is complete:
3NF = PA PWNS SMC
Consider the schema R and set of fds F
R = ABCDEFGH
F = { ABH → C, A → D, C → E,
BGH → F, F → AD, E → F, BH → E }
Fc = { BH → C, A → D, C → E,
F → A, E → F, BH → E }
Produce a 3NF decomposition of R.
Answer:
3NF is constructed directly from the minimal cover, after combinining dependencies with a common right hand side where possible.
Fc = BH → CE, A → D, C → E, F → A, E → F
Gives the following tables (with table keys in bold):
BHCE AD CE FA EF
A key for R is BHG; G must be included because it appears in no functional dependency.
Since no table contains the whole key for R, we must add a table containing just the key, giving:
3NF = BHCE AD CE FA EF BGH