GK One-Line Question & Answer

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

Some FDs in the original relation cannot be enforced by checking just one decomposed relation - they would require joining multiple decomposed relations to verify making constraint enforcement expensive

AD+ = ADE only: start with A,D, apply D to E getting ADE. Cannot reach B or C without them already in the closure. AD does NOT determine all attributes, so AD is NOT a candidate key.

X to Y where Y is a subset of X - it always holds in any relation (by reflexivity) because a set of attributes always determines its own subset providing no real constraint on data

If X to Y and X to Z then X to YZ (you can combine right-hand sides when the left-hand side is the same)

A theorem stating that the binary decomposition of R into R1 and R2 is lossless if and only if (R1 intersect R2) multidetermines (R1-R2) OR (R1 intersect R2) multidetermines (R2-R1) holds as an MVD in R

E+ = EABCD by E to A to BC to D and CD to E (already have E): E determines all attributes in the relation

Armstrongs axioms are both sound (only derive valid FDs) and complete (can derive ALL valid FDs) meaning F+ computed by Armstrong axioms exactly equals the set of all FDs logically implied by F

Satisfied by an instance: this specific relation instance happens to have X to Y hold (extensional). Implied by a set F: X to Y holds in EVERY possible instance that satisfies F (intensional) - a much stronger condition capturing the semantics of the schema