BUNYIP Example

Given a relation called BUNYIP and its associated minimal FD diagram:

1. Show that {A, C} and {B, C} are candidate keys for BUNYIP

2. Find the highest normal form (HNF) of BUNYIP

3. Propose another minimal cover set for BUNYIP

[Top]

1. Show that {A, C} and {B, C} are candidate keys for BUNYIP

Show that {A, C} is a candidate key for BUNYIP

Let F be the minimal cover set for BUNYIP
F = {A → B,
     B → A,
     A, C → D,
     B, D → E}

Let X be the set {A, C}
Let Y be the set of the attributes in BUNYIP: {A, B, C, D, E}

If X is a superkey of BUNYIP, then X → Y

By decomposition, this is equivalent to saying:
If X is a superkey of BUNYIP, then

     A, C → A
     A, C → B
     A, C → C
     A, C → D
     A, C → E
 
We can apply the FD inference rules to show that each of these FDs
exists in the closure of F (F+) for BUNYIP.

     A, C → A  trivial dependency (reflexivity)

     A, C → B  augmentation of a → b
               a → b is in F

     A, C → C  trivial dependency (reflexivity)

     A, C → D  in F (minimal)

     A, C → E  transitively from A, C → B, D and B, D → E
                A, C → B, D is the union of A, C → B and A, C → D
                B, D → E    is in F (minimal)
    
Therefore, X {A, C} is a superkey of BUNYIP.

X is a candidate key of BUNYIP if we cannot find a proper subset of X,
Xn, such that Xn → Y

The proper subsets of X are

     { }
     {A}
     {C}

The null set cannot be a superkey

Let {A} be the set X1
and {C} be the set X2

To check if a set, Xn, is a superkey for Y, we find
the closure of Xn (Xn+) under F.

To find the closure of X1 under F,
we first place the elements of X1 in a working list
Working list: A
Then we add to the working list all the attributes determined by {A}
We see from F that A → B, so we add B to our working list
Working list: A, B
Then we add to the working list all the attributes determined by {A, B}
We see from F that A → B and B → A,
but both A and B are already in our working list
Working list: A, B
We now stop - and note that our Working List does not contain
every attribute in the relation BUNYIP
Therefore, X1 {A} is not a superkey of BUNYIP and
cannot be a candidate key of BUNYIP

To find the closure of X2 under F,
we first place the elements of X2 in a working list
Working list: C
Then we add to the working list all the attributes determined by {C}
We see from F that C does not determine any attributes (being part
of a determinant is not the same as being a determinant)
Therefore we cannot add any attributes to our working list
Working list: C
We now stop - and note that our Working List does not contain
every attribute in the relation BUNYIP
Therefore, X2 {C} is not a superkey of BUNYIP and
cannot be a candidate key of BUNYIP

We have shown that X {A, C} is a superkey of BUNYIP, and
that there are no non-null proper subsets of X which are candidate keys of BUNYIP

Therefore, {A C} is a candidate key of BUNYIP

Show that {B, C} is a candidate key for BUNYIP

Let F be the minimal FD cover set for BUNYIP
F = {A → B,
     B → A,
     A, C → D,
     B, D → E}

Let X be the set {B, C}
Let Y be the set of the attributes in BUNYIP: {A, B, C, D, E}

If X is a superkey of BUNYIP, then X → Y

By decomposition, this is equivalent to saying:
If X is a superkey of BUNYIP, then

     B, C → A
     B, C → B
     B, C → C
     B, C → D
     B, C → E
 
We can apply the FD inference rules to show that each of these FDs
exists in the closure of F (F+) for BUNYIP.

     B, C → A  augmentation of B → A
               B → A is in F

     B, C → B  trivial dependency (reflexivity)

     B, C → C  trivial dependency (reflexivity)

     B, C → D  pseudo-transitively from A → B and A, C → D

     B, C → E  transitively from B, C → B, D and B, D → E
               B, C → B, D  is the union of B, C → B and B, C → D
               B, D → E    is in F (minimal)
    
Therefore, X {B, C} is a superkey of BUNYIP.

X is a candidate key of BUNYIP if we cannot find a proper subset of X,
Xn, such that Xn → Y

The proper subsets of X are

     { }
     {B}
     {C}

The null set cannot be a superkey

Let {B} be the set X1
and {C} be the set X2

To check if a set, Xn, is a superkey for Y, we find
the closure of Xn (Xn+) under F.

To find the closure of X1 under F,
we first place the elements of X1 in a working list
Working list: B
Then we add to the working list all the attributes determined by {B}
We see from F that B → A, so we add A to our working list
Working list: B, A
Then we add to the working list all the attributes determined by {B, A}
We see from F that B → A and A → B,
but both A and B are already in our working list
Working list: B, A
We now stop - and note that our Working List does not contain
every attribute in the relation BUNYIP
Therefore, X1 {A} is not a superkey of BUNYIP and
cannot be a candidate key of BUNYIP

To find the closure of X2 under F,
we first place the elements of X2 in a working list
Working list: C
Then we add to the working list all the attributes determined by {C}
We see from F that C does not determine any attributes (being part
of a determinant is not the same as being a determinant)
Therefore we cannot add any attributes to our working list
Working list: C
We now stop - and note that our Working List does not contain
every attribute in the relation BUNYIP
Therefore, X2 {C} is not a superkey of BUNYIP and
cannot be a candidate key of BUNYIP

We have shown that X {B, C} is a superkey of BUNYIP, and
that there are no non-null proper subsets of X which are candidate keys of BUNYIP

Therefore, {B C} is a candidate key of BUNYIP

[Top]

2. Find the Highest Normal Form (HNF) of BUNYIP

F = {A → B,
     B → A,
     A, C → D,
     B, D → E}

The candidate keys of BUNYIP are {A, C} and {B, C}

The prime attributes of BUNYIP are {A, B, C}
The non-prime attributes of BUNYIP are {D, E}


Is BUNYIP in 1NF?

Yes, it is a proper relation


Is BUNYIP in 2NF?

Is each non-prime attribute fully functionally dependent (ffd)
on each candidate key?
A non-prime attribute is ffd on a candidate key iff it is
not dependent on any proper subset of the candidate key

The null set, Ø, cannot be a determinant

The non-null proper subsets of {A, C} are
  {A} and {C}

Is either of the non-prime attributes, D and E, dependent on either of
the non-null proper subsets of {A, C}? 

We can check to see if D or E is dependent on {A} by finding
the closure of {A} ({A}+) under F.

First, we place the elements of {A} in a working list
Working list: A
Then we add to the working list all the attributes determined by {A}
We see from F that A → B, so we add B to our working list
Working list: A, B
Then we add to the working list all the attributes determined by {A, B}
We see from F that A → B and B → A,
but both A and B are already in our working list
Working list: A, B
We now stop - and note that our Working List does not contain
either the attribute D or the attribute E
Therefore, {A} does not determine D, and {A} does not determine E
A !→ D     A !→ E

We can check to see if either D or E is dependent on {C} by finding
the closure of {C} ({C}+) under F

First, we place the elemments of {C} in a working list
Working list: C
Then we add to the working list all the attributes determined by {C}
We see from F that C does not determine any attributes (being part
of a determinant is not the same as being a determinant)
Therefore we cannot add any attributes to our working list
Working list: C
We now stop - and note that our Working List does not contain
either the attribute D or the attribute E
Therefore, {C} does not determine D, and {C} does not determine E
C !→ D     C !→ E

We have shown that D is not dependent on either of the non-null proper
subsets of {A, C}, therefore D is fully functionally dependent
on the candidate key {A, C}

We have shown that E is not dependent on either of the non-null proper
subsets of {A, C}, therefore E is fully functionally dependent
on the candidate key {A, C}


The non-null proper subsets of {B, C} - the other candidate key - are
  {B} and {C}

Is either of the non-prime attributes, D and E, dependent on either of
the non-null proper subsets of {B, C}?

We can check to see if either D or E is dependent on {B} by finding
the closure of {B} ({B}+) under F

First, we place the elements of {B} in a working list
Working list: B
Then we add to the working list all the attributes determined by {B}
We see from F that B → A, so we add A to our working list
Working list: B, A
Then we add to the working list all the attributes determined by {B, A}
We see from F that B → A and A → B,
but both A and B are already in our working list
Working list: B, A
We now stop - and note that our Working List does not contain
either the attribute D or the attribute E
Therefore, {B} does not determine E, and {B} does not determine E
B !→ D     B !→ E

We have already shown above that {C} does not determine either D or E

We have shown that D is not dependent on either of the non-null proper
subsets of {B, C}, therefore D is fully functionally dependent
on the candidate key {B, C}

We have shown that E is not dependent on either of the non-null proper
subsets of {b, c}, therefore e is fully functionally dependent
on the candidate key {B, C}


We have shown that both non-prime attributes, D and E,
are fully functionally dependent on both candidate keys {A, C} and {B, C}

Therefore BUNYIP is in 2NF


Is BUNYIP in 3NF?

Are there any functional dependencies in the minimal cover set
which have a non-prome attribute in their LHS?

Yes
B, D → E
where D is non-prime

Therefore, BUNYIP is not in 3NF

Therefore, the HNF of BUNYIP is 2NF

If you are upset by my decision as to the HNF of BUNYIP because you are using the "no transitive dependencies" and you get 3NF as the HNF, please remember that "no  transitive  dependencies" is just a memory jogger.

You can't find any transitive dependencies, so BUNYIP must be in 3NF??

You insist that you can use Connolly and Begg's definitions and choose a *good* primary key so that BUNYIP goes from 2NF to 3NF??

Let us look back to when I was demonstrating that {A, C} and {B, C} are the candidate keys of BUNYIP.

I found that:

  A, C → E  transitively from A, C → B, D and B, D → E
            A, C → B, D is the union of A, C → B and A, C → D
            B, D → E    is in F (minimal)

  B, C → E  transitively from B, C → B, D and B, D → E
            B, C → B, D  is the union of B, C → B and B, C → D
            B, D → E    is in F (minimal)
    

So there are transitive dependencies. No matter which candidate key you chose to be the primary key, there will be a non-key attribute which is transitively dependent on the primary key.

Perhaps you are upset by my decision as to the HNF of BUNYIP because you assert that BUNYIP must be in 1NF,
either
     because it is so horrible - look at all those arrows crossing boxes on the FD diagram
or
     because of the partial dependencies.

Firstly, relations can be in a higher normal form than you feel they ought to be.      :-(

Secondly, what partial dependencies are those?
You should use the normal forms definitions to find the highest normal form of a given relation.
You should not use intuitive guesses as to what you think the English words in the memory joggers (should) *mean*.

[Top]

3. Propose another minimal cover set for BUNYIP

F = {A → B,
     B → A,
     A, C → D,
     B, D → E}

We observw that A → B and B → A
We can therefore substitute A for B, and B for A, in F
to create an alternate minimal cover set:

F′ = {B → A,
      A → B,
      B, C → D,
      A, D → E}

[Top]