GK One-Line Question & Answer

Selection filters rows based on a condition (horizontal subset); projection selects specific columns (vertical subset) potentially eliminating duplicates

A projection that allows arithmetic expressions and renaming in the projection list e.g. pi_name, salary*1.1 AS new_salary (R)

gamma_grouping-attributes, aggregate-function(attribute) (R) - groups tuples by specified attributes and applies aggregate functions (COUNT, SUM, AVG, MAX, MIN) to each group equivalent to SQL GROUP BY

Storing the same fact multiple times in different places causing wasted storage, inconsistency risk, insertion anomalies, and deletion anomalies

A constraint that a foreign key value in a referencing relation must either be NULL or must match an existing primary key value in the referenced relation

The result has r times s tuples (every tuple of R paired with every tuple of S)

R semi-join S returns only the tuples from R that have a matching tuple in S - useful in distributed databases because only tuples from S that match need to be transferred to the site holding R reducing network communication

Given R(A,B) and S(B) the division R / S returns tuples of R[A] that appear paired with every tuple in S - used for queries with for-all semantics such as Find employees who worked on all projects

BCNF eliminates all functional dependency violations; 5NF additionally eliminates join dependency violations that are not implied by candidate keys requiring a lossless decomposition into 3 or more projections

The relational model is founded on mathematical set theory: relations are sets of tuples (no duplicates), operations (union, intersection, difference) follow set semantics and relational algebra is based on set operations

Hierarchical allows only one parent per record (tree); network allows multiple parents (graph structure)

2NF but not 3NF because B to C creates a transitive dependency

A functional dependency of a non-prime attribute on a PROPER SUBSET of a candidate key (occurs only when candidate key is composite); eliminated by achieving 2NF

Transitive dependency DeptID to DeptName violates 3NF; decompose into R1(EmpID,EmpName,DeptID,Salary) and R2(DeptID,DeptName)

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