BCNF

In the critieria for good DB design, it should not have

redundancy where students taking courses repeats course information
update anomalies where you can update GPA vlaue while leaving others unchanged
insertion anomalies where you cannot add new course unless student takes it
deletion anomalies where deleting all students taking course removes information abot course

Decomposition splits our relation into smaller relations that returns original information when joined. We don't want arbitrary decomposition. We want it to be

lossless so does not produce extraneous information not in original relation when joined
dependency preserving so it is efficient and you don't need to join to perform CRUD operations

Functional Dependencies (FD) define relationships between attributes.

A → B means that there is 1 B for every A.

To get these properties, we must get our database to satisfy certain normal form which are constraints that FD must meet.

1NF is met if attribute values are atomic or indivisible.
2NF is met if all non-prime attributes are fully FD on the primary key(s).
3NF is met if there are no FDs X → Y, Y → Z where X is a key and Y is a non-key.
BCNF is met if there are no FDs X → Y where X is a non-key.

We define the closure of F to be set of all FD, including those that can be inferred.

For example, if we have FDs X → Y and Y -> Z, even if not explicitly stated, Y - Z is logically implied. Redundant FDs are not included in this set.

To compute it, we use Armstrong's axioms.

Reflexitivity: if X is subset of Y, then X → Y
Union: if X → Y and X →Z, then X → YZ
Augmentation: if X → Y, then XZ → YZ
Decomposition: if X → YZ, then X → Y and X → Z
Transitivity: if X → Y and Y → Z, then X → Z
Pseudo-Transitivity: if X → Y and Y → Z, then XY → Z

Closure is important since it helps us get the canonical cover.
This is a set of FD with the following properties.

RHS of every FD is a single attribute
Closure of canonical cover is equivalent to original closure
Set is minimal so removal of any FD violates above property

The algorithm for computing the canonical cover is as follows

Decompose all FD so RHS have a single attribute

ex) if X → Y, Z, replace it with X → Y and X → Z

Remove duplicates
Eliminate all transitive FDs since they are logically implied anyways
ex) if X → Y and Y → Z, eliminate X → Z if it exists
Identify all pseudo-transitive FDs and replace/eliminate them
ex) if X → Y and Y → W replace X Y → W with X → W if it exists,
then eliminate it since it is transitive

Getting the canonical cover is an important step to get the candidate key.

The candidate key(s) is the minimal set of attributes that functionally determines all attributes in relation. In other words, they uniquely identify tuples.

Why do we care about candidate keys?

Remember our goal was to DECOMPOSE the table so it would be lossless and dependency preserving. Candidate keys tell us if it's okay to decompose our original table into multiple tables.

To determine whether given attribute(s) X is a candidate key,
compute closure of X and see if it contains all attributes of relation on RHS.
If X has multiple attributes, make sure no subset of it also has this property.

The algorithm for computing the candidate key is as follows.

Generate an array of all attribute combinations to test
Sort the array by number of attributes in ascending order
Iterate through array and compute the closure
If closure is complete, we only continue for elements of equal length

Note: There are 2^attribute-1 combinations. There are some simplications.

If an attribute is never on the left hand side of a dependency,
it is not in any key, unless it is also never on the right hand side
If an attribute is never on the right hand side of any FD, it is in every key

1) Functional Dependencies 2) Canonical Cover 3) Candidate Key 4) Deriving 3NF/BCNF