GK One-Line Question & Answer

A constraint X determines Y where for any two tuples with the same X value they must also have the same Y value (X functionally determines Y)

Changing a fact stored in multiple redundant rows requiring all rows to be updated simultaneously with inconsistency resulting if any update is missed

A normal form where every constraint is a logical consequence of domain constraints and key constraints guaranteeing freedom from all modification anomalies

Given relations R(A,B) and S(B), produces tuples from R[A] that are associated with ALL tuples in S - used for for-all type queries

BCNF requires that for every non-trivial FD X to Y, X must be a superkey (no exceptions) while 3NF allows Y to be a prime attribute as an exception

A set of sound and complete inference rules for FDs: Reflexivity (if Y is subset of X then X determines Y), Augmentation (if X determines Y then XZ determines YZ), and Transitivity (if X determines Y and Y determines Z then X determines Z)

Natural join automatically joins on all common attribute names and eliminates duplicate columns; equi-join requires explicit equality conditions and may keep duplicate columns

In a relation R(X,Y,Z), X multidetermines Y means that for a given X value the set of Y values is independent of the Z values - used to define 4NF

The set of ALL attributes that can be functionally determined by X using the FDs in F - used to test if X is a superkey (if X+ = all attributes)

It ensures that when a relation is decomposed into smaller relations the original relation can be perfectly reconstructed by joining the decomposed relations with no spurious tuples

A constraint where a relation can be losslessly decomposed into n projections and reconstructed by joining them; a relation is in 5NF if every join dependency is implied by the candidate keys

UNION removes duplicate rows from the combined result; UNION ALL keeps all rows including duplicates (and is faster since no deduplication is needed)

Testing whether a decomposition has the lossless join property and whether a set of functional dependencies is preserved by applying FDs to a canonical table (tableau)

Returns all rows from the left table and matching rows from the right table; non-matching right-side columns contain NULL

The set of all permissible/valid values for an attribute defining the data type and any domain constraints

Theta join allows any comparison operator (=, <, >, <=, >=, !=) as the join condition; equi-join is a special case of theta join using only equality (=)

Relational algebra is procedural (specifies how to retrieve data); relational calculus is declarative (specifies what data to retrieve without specifying how) - both are equivalent in expressive power (Codds theorem)

Relation scheme (schema) R(A1,A2,...An) is the structural definition with attribute names and their domains; relation instance r(R) is the actual set of tuples conforming to that schema at a point in time

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