COMP3311 24T2 Week 09
Relational Design Theory 		Database Systems

Notation: in the relational schemas below, primary key attributes are underlined (e.g. pk), foreign key attributes are shown in italic font (e.g. fk) and primary key attributes that are also foreign keys are underlined and in italic font (e.g. pk+fk).

Example: 
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.

  1. Functional dependencies.

    1. What functional dependencies are implied if we know that a set of attributes X is a candidate key for a relation R?

    2. 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

    3. 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.

  2. 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:

    1. A+

    2. ACEG+

    3. BD+

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

    1. List all of the candidate keys for R.

    2. Is R in third normal form (3NF)?

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

  4. 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:

    1. List all of the candidate keys for R.

    2. Show whether R is in Boyce-Codd normal form (BCNF)?

    3. Show whether R is in third normal form (3NF)?

    1. C → D,   C → A,   B → C

    2. B → C,   D → A
    3. ABC → D,   D → A
    4. A → B,   BC → D,   A → C
    5. AB → C,   AB → D,   C → A,   D → B
    6. A → BCD

  5. 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)

  6. 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)

  7. 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

    1. C → D,   C → A,   B → C

    2. B → C,   D → A

    3. ABC → D,   D → A

    4. A → B,   BC → D,   A → C

    5. AB → C,   AB → D,   C → A,   D → B

    6. A → BCD

  8. 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:

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

    2. Using these functional dependencies, decompose R into a set of 3NF relations.

    3. State whether the new relations are also in BCNF.

  9. 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:

    1. Devise a suitable set of functional dependencies among these attributes.
    2. Using these functional dependencies, decompose R into a set of BCNF relations.
    3. State whether the new relations are also in 3NF.

  10. Real estate agents conduct visits to rental properties

    • need to record which property, who went, when, results
    • each property is assigned a unique code (P#, e.g. PG4)
    • each staff member has a staff number (S#, e.g. SG43)
    • staff members use company cars to conduct visits
    • a visit occurs at a specific time on a given day
    • notes are made on the state of the property after each visit
    The company stores all of the associated data in a spreadsheet.

    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.

  11. Consider a company supplying temporary employees to hotels:

    • the company has contracts with different hotels
    • it may have several contracts with a given hotel
    • contracts are identified by a code (e.g. C12345)
    • staff work at different hotels as needed
    • staff have tax file #'s (TFN, e.g. T123)
    • hotels have Aus business #'s (ABN, e.g. H234)
    Describe any functional dependencies that exist in this data. The table of sample data below below may give some ideas: 
    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.

  12. 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?

  13. Compute a minimal cover for:

    F   =   { B → A,  D → A,  AB → D }

  14. Using the functional dependencies you produced in Q10, convert the real-estate inspection spreadsheet (single table), into a BCNF relational schema.

  15. 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.

  16. Using the functional dependencies you produced in Q10, convert the real-estate inspection spreadsheet (single table), into a 3NF relational schema.

  17. 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.