Bad design, functional dependencies and closure

This is the first week of the normalization section. The most reliable points after the midterm come from here, because most of the questions are mechanical: compute a closure, find a key, derive an FD. The three skills on this page are the basis of the next two weeks (normal forms, decomposition):

1. Explaining why one big table causes problems with anomalies.
2. Understanding what a functional dependency means and checking whether it holds in the sample data.
3. Finding superkeys and candidate keys with attribute closure.

Bad design: everything in one table

In the university database we use all semester, takes, student, course and department are separate tables. Imagine you merged them into one “wide” table:

CREATE TABLE wide AS
SELECT t.stu_id, s.name AS stu_name, t.course_id, c.title, c.credits,
       c.dept_name AS course_dept, d.building, t.grade
FROM takes t JOIN student s ON s.stu_id = t.stu_id
             JOIN course c ON c.course_id = t.course_id
             JOIN department d ON d.dept_name = c.dept_name;

The result is 14 rows (I am not showing the stu_name and credits columns to save space):

Writing queries became easier, but the table is open to three kinds of errors:

The root cause: the table squeezes independent facts (the name of a course, the building of a department, a student’s grade) into the same row. The way to express these facts formally is a functional dependency.

Functional dependency

Let $X$ and $Y$ be sets of attributes of the schema $R$. $X \to Y$ means: any two rows with the same $X$ values also have the same $Y$ values. It is read ”$X$ determines $Y$”.

Real-world rules for the wide table:

• $\text{stu\_id} \to \text{stu\_name}$
• $\text{course\_id} \to \text{title, credits, course\_dept}$
• $\text{course\_dept} \to \text{building}$
• $\text{stu\_id, course\_id} \to \text{grade}$

From these FDs, {stu_id, course_id} comes out as the only candidate key of the table (you will see below how to find it).

Checking on sample data

A single pair is enough to violate an FD: two rows with the same left side and a different right side. With SQL you find it by grouping:

-- does building -> course_dept hold?
SELECT building FROM wide
GROUP BY building
HAVING COUNT(DISTINCT course_dept) > 1;

Galata

Galata matches both CS and EE: $\text{building} \to \text{course\_dept}$ is violated. When you run the same query for course_id/title or course_dept/building, the result is empty, so these FDs hold in this instance. For credits -> course_dept the query returns the values 3 and 4 (4-credit courses are in both CS and MATH).

PITFALL · sample data is not proof. If the query returned empty, it means the FD is not violated in these rows, not that it is valid in the schema. A row that arrives tomorrow can break it. An FD is a design decision (a real-world rule); data can only refute it.

Trivial dependency

If $Y \subseteq X$, then $X \to Y$ is true in every relation: $AB \to A$, $\{\text{stu\_id, grade}\} \to \text{stu\_id}$. They carry no information. If the exam says “list the non-trivial FDs”, do not write these.

Armstrong’s axioms

Other FDs can be derived from a given set of FDs $F$. The set of everything that can be derived is called the closure of F and is written $F^+$. Three basic rules are enough (sound and complete):

Practical rules derived from these:

Worked example. Given $F = \{A \to B,\ B \to C,\ CD \to E\}$, derive $AD \to E$.

1. A -> B, B -> C           transitivity     A -> C
2. A -> C, add D            augmentation     AD -> CD
3. AD -> CD, CD -> E        transitivity     AD -> E

PITFALL · you cannot split the left side. The decomposition rule holds only for the right side. From $AB \to C$ you do not get $A \to C$. When you see “decomposition”, remember that you are splitting the right side.

Since $F^+$ is usually very large, it is not listed by hand. In practice the real tool is the closure of an attribute set.

Attribute closure

$X^+$: the set of all attributes that $X$ determines under $F$. The algorithm:

result := X
repeat:
    for each  L -> M  in F:
        if L ⊆ result then  result := result ∪ M
until there is no change

Worked example. $R(A,B,C,D,E,G)$, $F = \{A \to B,\ AC \to D,\ B \to E,\ DE \to G\}$.

{A}+    : A
          A -> B     AB
          B -> E     ABE
          (no C for AC -> D, no D for DE -> G)  →  {A,B,E}

{A,C}+  : AC
          A -> B     ABC
          AC -> D    ABCD
          B -> E     ABCDE
          DE -> G    ABCDEG   →  the whole schema

Closure answers three questions at once:

1. Can $X \to Y$ be derived? Yes if $Y \subseteq X^+$. $\{A\}^+ = \{A,B,E\}$, so $A \to D$ cannot be derived but $A \to E$ can.
2. Is $X$ a superkey? Yes if $X^+ = R$. AC is a superkey.
3. Is $X$ a candidate key? Yes if it is a superkey and none of its proper subsets is a superkey. $\{A\}^+$ and $\{C\}^+ = \{C\}$ do not give the schema, so AC is a candidate key.

Finding all candidate keys

Brute force means $2^n$ subsets. In the exam the quick way is this observation:

• An attribute that appears on the right side of no FD cannot be derived from anything else, so it must be in every key.
• An attribute that appears only on the right side (never on the left) is in no minimal key.
• First take the closure of the “mandatory” set. If it is not enough, add one attribute at a time, then two. Skip the supersets of a key you have found.

Worked example. $R(A,B,C,D,E)$, $F = \{AB \to C,\ C \to D,\ D \to E,\ E \to A\}$.

Never on a right side: B          → B is in every key
{B}+ = {B}                         → not enough
{A,B}+: AB -> C, C -> D, D -> E          = ABCDE   key
{B,C}+: C -> D, D -> E, E -> A, AB -> C  = ABCDE   key
{B,D}+: D -> E, E -> A, AB -> C          = ABCDE   key
{B,E}+: E -> A, AB -> C, C -> D          = ABCDE   key

Four candidate keys: AB, BC, BD, BE. You do not need to try the 3-sets, since all of them contain one of these.

An example with a cycle: $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ C \to A\}$. D is on no right side, $\{D\}^+ = \{D\}$. Any one of A, B or C completes the cycle: the keys are AD, BD, CD.

TIP · the number of superkeys. If there is a single candidate key with $k$ attributes, the number of superkeys in a schema with $n$ attributes is $2^{n-k}$ (the key plus any subset of the rest). $R(A,B,C,D)$ with key A: $2^3 = 8$ superkeys. If there are several keys, be careful not to double count their intersections.

Back to the wide table, write it with letters: S = stu_id, N = stu_name, C = course_id, T = title, K = credits, D = course_dept, B = building, G = grade. $F = \{S \to N,\ C \to TKD,\ D \to B,\ SC \to G\}$. S and C are on no right side, and $\{S,C\}^+$ gives everything: the only candidate key is {stu_id, course_id}. $\{C\}^+ = \{C,T,K,D,B\}$: only a part of the key determines this many attributes. Next week we will give this a name: partial dependency.

Common mistakes