GK One-Line Question & Answer

3NF decomposition always guarantees both lossless join AND dependency preservation; BCNF decomposition guarantees lossless join but may NOT preserve all functional dependencies

4NF addresses multivalued dependencies (MVDs): a relation is in 4NF if for every non-trivial MVD X multidetermines Y, X is a superkey. MVDs create redundancy even in BCNF relations with independent multi-valued facts

The smallest equivalent set Fc of FDs where all FDs have single attribute RHS, no FD is redundant, and no attribute in any LHS is redundant

A, B, and C are all candidate keys (since each determines all others via transitivity forming an equivalence class)

An algorithm that: (1) finds minimal cover Fc, (2) creates one relation for each FD in Fc (LHS union RHS), (3) adds a relation for any candidate key if none of the created relations contains one, (4) removes redundant relations

The union of functional dependencies derivable from the projected FDs on each decomposed relation is equivalent to the original set of FDs - meaning all original constraints can be checked locally without joins

Denormalization is the intentional introduction of redundancy by reversing normalization justified when the performance cost of joins in read-heavy workloads significantly outweighs the storage and update overhead

The inability to insert a valid piece of information without also inserting other possibly unknown information - e.g. cannot add a new department unless at least one employee in that department exists

FDs: CourseID to InstructorID and InstructorID to CourseID; candidate keys: StudentID,CourseID and StudentID,InstructorID; CourseID to InstructorID violates BCNF since CourseID is not a superkey yet 3NF holds because InstructorID is a prime attribute

Deleting a row to remove one piece of information inadvertently destroys other valid information stored in the same row - e.g. deleting the last employee in a department also deletes all information about that department

F can derive all FDs in G AND G can derive all FDs in F - meaning they generate the same closure F+ = G+

An attribute that is a member of at least one candidate key of the relation

BCNF and all higher normal forms

For each course instructors and textbooks are independent; 4NF requires decomposing into R1(CourseID,InstructorID) and R2(CourseID,TextbookID) to eliminate the cartesian product redundancy

A non-prime attribute Y depending on another non-prime attribute Z which in turn depends on the key X: X to Z to Y where Z is not a superkey - e.g. EmpID to DeptID to DeptName

Decomposition algorithm: find a violating FD X to Y (X not a superkey), decompose into R1(X union Y) and R2(R-Y+X), recursively apply until all relations are in BCNF

X to Y where Y is NOT a subset of X - i.e. Y contains at least one attribute not already in X making the FD actually informative

Fc = A to B, B to A, A to C (since B to C is redundant: B to A to C is derivable so B to C can be removed)

It guarantees that when decomposed relations are joined back together the result is exactly the original relation with no spurious tuples and no missing tuples

If X multidetermines Y in relation R(X,Y,Z) where Z=R-X-Y then X multidetermines Z also holds; also every FD X to Y implies X multidetermines Y

X to Y holds in every relation that satisfies all FDs in F - equivalently X to Y is derivable from F using Armstrong axioms

No: candidate key is A (A+ = ABCD). FD BC to D: BC is not a superkey and D is not a prime attribute. This violates 3NF. The relation is in 2NF (PK is single attribute so no partial dependencies) but NOT in 3NF

The prime attribute exception allows 3NF to always guarantee a dependency-preserving decomposition even when BCNF cannot; it permits FDs where the RHS is a prime attribute even if the LHS is not a superkey - trading some redundancy for dependency preservation

A directed graph where nodes are attributes and directed edges represent FDs (X to Y is an edge from each attribute in X to each attribute in Y); used to identify transitive chains, key derivations, and find canonical covers

A binary decomposition of R into R1 and R2 is lossless if and only if (R1 intersect R2) determines (R1 minus R2) OR (R1 intersect R2) determines (R2 minus R1) holds in F

Augmentation and Transitivity: X to Y gives XZ to YZ; X to Z gives X to XZ (by reflexivity and augmentation); then XZ to YZ by augmentation gives X to YZ by transitivity

A+ = ABCDE (A to B to C, A to D to E, so A determines all)

AB, BC, and BD (compute closures: AB+ = ABCD, BC+ = ABCD, BD+ = ABCD; check minimality: no proper subset works for each)

If X to YZ then X to Y and X to Z (you can split the right-hand side - derived from Reflexivity and Transitivity)

Yes: X to YZ (given), so X to Y (decomposition), then X to XY (augmentation), XY to W (given), X to W by transitivity

An attribute A in the LHS of an FD X to Y such that removing A still preserves the equivalence: (F minus FD) union ((X-A) to Y) is equivalent to F

If X to Y and WY to Z then WX to Z (a generalization of transitivity where the intermediate attribute set Y is augmented with W on both sides)

Yes: E to A (given), A to BC (given), B to D (given); E to A to B to D, so E to D by transitivity chain

X multidetermines Y is trivial if Y is a subset of X or X union Y equals the entire attribute set of the relation (trivial MVDs always hold and convey no information)

If X multidetermines Y in relation R(X,Y,Z) where Z=R-X-Y then X multidetermines Z also holds; also every FD X to Y implies X multidetermines Y

Fc = A to B, B to C (A to C is redundant since it is derivable; both remaining FDs are necessary and have no redundant attributes)

The set of ALL functional dependencies that can be logically derived from F using Armstrongs axioms - the complete set of FDs that hold in every relation satisfying F

F covers G (G is a subset of F+) if every FD X to Y in G can be derived from F - tested by checking if Y is a subset of X+ computed under F for each FD in G

X to Y is a full FD if removing any attribute from X breaks the FD (Y no longer depends on X); partial if Y still depends on some proper subset of X

No other FDs are specified; the composite key is the only determinant of quantity placing the relation in BCNF assuming no other FDs exist