[Tut/Lab Sessions]   [Tut/Lab Sessions Schedule] [Course Information]   [COMP2400/6240 Home]
Coloured Line

Tutorial 4

Solution Notes

Coloured Line

Coloured Line

Questions

Coloured Line

Candidate Keys and Highest Normal Form #1

Below are five relations and their associated minimal FD diagrams.

For each relation:

  1. Write the minimal FD list which corresponds to the given minimal FD diagram.

  2. Find the candidate key(s) of the relation.

  3. List the prime and non-prime attribute(s) of the relation.

  4. Determine the highest normal form (1NF, 2NF, 3NF, BCNF) of the relation.


First Relation

WORKSTATION FD Diagram


  1.   Model-id → Weight
  Model-id, Serial-no → Lab-no
  Model-id, Serial-no → Condition
  Lab-no → Model-id
    
  2.   {Model-id, Serial-no}
  {Lab-no, Serial-no}
      
  3.   prime: {Model-id, Serial-no, Lab-no}
  non-prime: {Weight, Condition}
      
  4.   1NF
    
  Not 2NF due to the FD
     Model-id → Weight
  Weight (non-prime) is dependent on part of
  (a proper subset of) the candidate key {Model-id, Serial-no}

Q. 

But what if I chose {Lab-no, Serial-no} as the primary key?

A. 

The HNF of a relation does not depend upon which candidate key you choose as the primary key. You cannot change the HNF of a relation by choosing a different primary key.

If you do have  {Lab-no, Serial-no}  as the primary key, then  Weight  is still partially dependent on the primary key because 

     Lab-no → Model-id
     Model-id → Weight
     ∴ Lab-no → Weight (transitivity)

Second Relation

BUNYIP FD Diagram


  1.   A → B
  B → A
  A, C → D
  B, D → E
      
  2.   {A, C}
  {B, C}

    Q. 

    Is {A, B, C} another candidate key?

    A. 

    No. {A, B, C} is a superkey for BUNYIP.

    		 

  3.   prime: {A, B, C}
  non-prime: {D, E}
  
  4.   2NF
     
  Neither D nor E is determined by a proper subset
  of a candidate key
     
  Not 3NF due to the FD
     B, D → E
  which is an FD with a non-prime attribute in its LHS

  {B, D} is not a superkey

See also BUNYIP Example


Third Relation

SUBURB (Suburb-name, State, Population, Postcode)

SUBURB FD Diagram


  1.   Suburb-name, State → Population   
  Suburb-name, State → Postcode
  Postcode → State    

  2.   {Suburb-name, State}
  {Suburb-name, Postcode}

    Q. 

    Is {Suburb-name, State, Postcode} another candidate key?

    A. 

    No. {Suburb-name, State, Postcode} is a superkey for SUBURB.

    		 

  3.   prime:  {Suburb-name, State, Postcode}
  non-prime: {Population}
     
  4. 
  The relation is in at least 1NF.
  Carol says it is a relation and, unless we can see the data in
  the tuples, we cannot show this to be incorrect.

  The relation is in at least 2NF.
  The non-prime attribute {Population} is fully functionally dependent on both candidate keys.
	  
  The relation is in at least 3NF.
  There is only one non-prime attribute.

  Not BCNF due to the FD
    Postcode → State
  which is an FD where a prime attribute is not fully functionally
  determined by the key of which it is not a part

Fourth Relation

ENROLMENT FD Diagram


  1.   Unit-no -> Unit-name
  Unit-name -> Unit-no
  Unit-name -> Level 
      
  2.   {Student-id, Unit-no}
  {Student-id, Unit-name}
      
  3.   prime: {Student-id, Unit-no, Unit-name}
  non-prime: {Level}
      
  4.   1NF
    
  Not 2NF due to the FD
     Unit-name -> Level
  Level (non-prime) is dependent on part of
  (a proper subset of) a candidate key
      
  5.   Unit-no -> Unit-name
  Unit-name -> Unit-no
  Unit-name -> Level

Fifth Relation

OFFICE FD Diagram


  1.   Room-no -> Floorspace
  Room-no -> No-of-windows
  Room-no -> Decor
  Room-no -> Staff-id
      
  2.   {Room-no}
      
  3.   prime: {Room-no}
  non-prime: {Floorspace, Staff-id, No-of-windows, Decor}
      
  4.   BCNF

  Every determinant in the minimal FD list is a candidate key

[Top]

Coloured Line

Candidate Keys and Normal Forms #2

Below are six relations, each with its associated minimal FD list.

For each relation, state:

  1. its candidate key(s)

  2. its highest normal form (1NF, 2NF, 3NF, or BCNF)


Use the COMP2400/6240 convention for designating candidate keys.



  1.       R1 (A, B, C)

      A → B
      C → B
      
    1.   CK: {A, C}
	    
    2.   HNF: 1NF

  Not in 2NF because the non-prime attribute B is
  not fully functionally dependent on the candidate key {A, C}

  B is fully functionally dependent on {A} 
  B is fully functionally dependent on {C}
  B is partially dependent on {A, C} 
	    

  2.       R2 (D, E, F, G)

      D → E
      E → F
      
    1.   CK: {D, G}
	    
    2.   HNF: 1NF
		  
  Not in 2NF because the non-prime attribute is E is
  not fully functionally dependent on the candidate key {D, G}
              

  3.       R3 (H, I, J)

      H → I
      H → J
      I → H
      
    1.   CK: {H}
      {I}
	    
    2.   HNF: BCNF
		  
  Every determinant in the minimal FD list is a candidate key

    Q. 

    But what about "no transitive dependencies"? There is a transitive dependency, so the highest normal form must be 2NF.

    A. 

    If you use the memory jogger "no transitive dependencies", you need to use a special definition of "transitive dependency" which is more restricted than the definition from the FD Inference Rules. This is that special definition:

    transitive functional dependency  If X → Z and Z → Y and Z is not a candidate key or a component of a candidate key, then X → Y transitively (or Y is transitively dependent on X via Z)

    For R3, I → H and H → J, so there is a transitive dependency I → J using the definition from the FD Inference Rules.
    However, H is a candidate key, so there is not a transitive dependency using the special definition which you need for "no transitive dependencies".

    		 

  4.       R4 (K, L, M, N)

      K, L → M
      K, L → N
      M → L
      
    1.   CK: {K, L}
      {K, M}

  Demonstrating that {K, M} is a candidate key for R4
	    
    2.   HNF: 3NF
		  
  Not BCNF because the prime attribute L in not fully functionally
  dependent on the candidate key {K, M} of which L is not a part
	    

  5.       R5 (t, a, n, g, o)

      t → a
      t → n
      t → g
      t → o
      n → t
      
    1.   CK: {t}
      {n}
	  
    2.   HNF: BCNF

  Every determinant in the minimal FD list is a candidate key

  A proper relation (1NF)
  No multi-attribute keys (2NF)
  No FDs between non-prime attributes (3NF)
  Keys are disjoint - they do not overlap (BCNF)

    Q. 

    Why can't I have 1 mark for the following answer?
    The BCNF bit is correct.

         CK: {t, n}
  
     HNF: BCNF

    A. 

    If {t, n} is the candidate key, then the relation is not in BCNF because neither of the determinants in the minimal FD list - neither {t} nor {n} - is a candidate key.

    That is, the highest normal form which you have given is not consistent with the candidate key which you have nominated.
    So you cannot have 1 mark.

    		 

  6.       R6 (x, y, z)

      The minimal FD list is empty
      
    1.   CK: {x, y, z}

  Because each tuple in a relation is unique,
  a relation always has at least one superkey:
  the set of all the attributes in the relation.
  If this superkey is minimal, then
  this superkey is also the candidate key.
	       
  Can we remove any attributes from {x, y, z} and
  still functionally determine all the attributes
  in R6?
  No - therefore {x, y, z} is the candidate key.

      NB: 

      R6 has one candidate key with three attributes.
      R6 does not have three candidate keys.

      		 

    2.   HNF: BCNF

  Is "every determinant a key"?
  The minimal FD list is empty, so this memory jogger is unhelpful.

  There are no non-prime attributes, so the relation is in
  at least 3NF.
  There is only one candidate key, so the relation is
  also in BCNF.

  Is each prime attribute fully functionally dependent on
  each candidate key of which it is not a part?
  There is only one candidate key, ∴ this constraint
  is irrelevant.
	  
  Is there a prime attribute which is functionally dependent
  upon a proper subset of a candidate key of which it is not
  a part?
  No - there is only one candidate key.

      Q. 

      But what about the following partial dependencies? 

           x, y, z → x
     x, y, z → y
     x, y, z → z

      A. 

      These are trivial FDs.

      "no partial dependencies" is just a memory jogger.

      A full definition is:
      "A relation schema R is in second normal form (2NF) if every nonprime attribute A in R is not partially dependent on any key of R."  [EN5:365]

      x, y, and z  are not nonprime - they are prime because they are subsets of the candidate key  {x, y, z}.

[Top]

Coloured Line

Functional Dependencies

 STUDENTID COURSECODE       YEAR        SEM       MARK GRADE
---------- ---------- ---------- ---------- ---------- ------
   2010001 COMP1100         2005          1         67 CR
   2010001 COMP1110         2005          2
   2010001 COMP2400         2005          2
   2010001 MATH1003         2005          1         81 HD
   2010035 MATH1003         2004          1         55 P
   2010035 COMP1100         2004          1         61 CR
   2010035 COMP1110         2004          2         58 P
   2010035 COMP2400         2005          2
   2010035 INFS2004         2005          2
   2010035 BUSN1001         2004          1         66 CR
   2010018 MATH1003         2004          1         79 D
   2010052 BUSN1001         2003          2         44 N
   2010052 COMP1100         2003          1            NCN
   2010052 BUSN1001         2005          1         53 P
   2010052 COMP1100         2005          1         67 CR
   2010069 COMP1100         2002          1         78 D
   2010069 COMP3100         2004          3         70 D
   2010069 COMP2400         2004          2         76 D

Below are seven functional dependencies (FDs) among the attributes/columns in the table above.

For each FD:

  1. State whether the FD is Consistent or Inconsistent with the sample data in the table.

  2. If the FD is Consistent, briefly explain the semantics of the FD.

    If the FD is Inconsistent, give one example of the inconsistency.


  1. STUDENTID → COURSECODE

    1. Inconsistent

    2. In the first row, {STUDENTID} takes the value {2010001}
      and {COURSECODE} takes the value {COMP1100}

      In the second row, {STUDENTID} takes the value {2010001}
      and {COURSECODE} takes the value {COMP1110}


  2. COURSECODE → SEM

    1. Inconsistent

    2. In the tenth row, {COURSECODE} takes the value {BUSN1001}
      and {SEM} takes the value {1}

      In the twelve row, {COURSECODE} takes the value {BUSN1001}
      and {SEM} takes the value {2}


  3. MARK → GRADE

    1. Consistent

    2. Only one Grade is associated with each Mark.
      OR
      Your Mark determines your Grade.


  4. COURSECODE, YEAR → MARK

    1. Inconsistent

    3. In the fifth row, {COURSECODE, YEAR} takes the value {MATH1003, 2004}
      and {MARK} takes the value {55}

      In the eleventh row, {COURSECODE, YEAR} takes the value {MATH1003, 2004}
      and {MARK} takes the value {79}


  5. STUDENTID, YEAR → GRADE

    1. Inconsistent

    2. In the third row, {STUDENTID, YEAR} takes the value {2010001, 2005}
      and {GRADE} takes the value { }

      In the fourth row, {STUDENTID, YEAR} takes the value {2010001, 2005}
      and  GRADE takes the value {HD}

      OR

      In the first row, {STUDENTID, YEAR} takes the value {2010001, 2005}
      and {GRADE} takes the value {CR}

      In the fourth row, {STUDENTID, YEAR} takes the value {2010001, 2005}
      and  GRADE takes the value {HD}

    It does not matter whether you think that  GRADE  is blank in the third row, or you think that  GRADE  is  null  in the third row.
    Both a blank and a  null  are different from  HD  (and from  CR).


  6. STUDENTID, COURSECODE, YEAR, SEM → MARK

    1. Consistent

    2. Each time a student takes a particular course, s/he receives one Mark.


  7. STUDENTID, COURSECODE, YEAR, SEM → GRADE

    1. Consistent

    2. Each time a student takes a particular course, s/he receives one Grade.


[Top]

Coloured Line

Carol Edmondson   <carol@cs.anu.edu.au>
URL: http://computer/student/comp2400.2006/tutlabs/tut4/SolnNotes.shtml
Last modified: Saturday, 23-Sep-2006 17:43:16 EST