Master Rule Sheet (all rule cards merged)

Every Rule Card from the 84 lessons, grouped by phase, in course order. Use it for revision in the last weeks: read one phase per sitting, and for any line you cannot explain in your own words, open its lesson (the lesson ID links to it).

How to revise with this sheet

1. Cover the rules of a lesson with your hand; say them from its title alone.
2. Check, and mark the lesson's ID on paper if you missed anything.
3. Next day, re-test only the marked IDs (spaced recall).

🧭 Phase 0 · Foundations

0.1.1 Data vs information; plain files and their problems

• Data = raw facts; information = processed data that answers a question.
• File-processing system: each program owns its own files.
• Its problems (RIDIIACS): Redundancy, Inconsistency, Difficult access, Isolation, Integrity, Atomicity, Concurrency, Security.
• Redundancy = same fact stored more than once; inconsistency = copies disagree.
• Atomic = all or nothing; concurrent = at the same time.

0.1.2 What a DBMS is and what it does; its users (end users, application programmers, DBA)

• Database = related data; DBMS = software to define, build, query, update and share it; database system = both.
• DBMS jobs: definition, querying, updating, concurrency control, recovery, security, integrity checks.
• Metadata (data about data) lives in the catalog: the database is self-describing.
• DDL defines structure; DML reads and changes data.
• Users: DBA (access, storage, performance, backup), designers, end users (naive, casual, sophisticated, stand-alone), application programmers.
• Costs of a DBMS: money, training, overhead.

0.1.3 Schema vs instance; three-schema architecture; logical and physical data independence

• Schema = description (intension), rarely changes. Instance = data at a moment (state, extension), changes constantly.
• Three levels: external (many views) → conceptual (one, whole database, what) → internal (one, storage, how).
• Two mappings: external–conceptual and conceptual–internal.
• Physical data independence: internal change, conceptual unchanged. Easier.
• Logical data independence: conceptual change, views/apps unchanged. Harder.

0.1.4 Data models: conceptual vs logical vs physical; where ER and relational fit

• Data model = concepts for describing data structure, connections, rules (and operations).
• Conceptual (ER) → representational/logical (relational) → physical (files, indexes).
• Design process: requirements → conceptual (ER) → logical (tables) → refinement (normalisation) → physical.
• DBMSs implement the relational model; ER diagrams are converted to tables.

0.2.1 Sets: membership, subset, union, intersection, difference, cardinality, power set

• Set = distinct elements, no order; x ∈ A; ∅ has no elements.
• A ⊆ B: every element of A is in B. ∅ ⊆ A; A ⊆ A.
• ∪ or, ∩ and, − in first but not second; A − B ≠ B − A.
• |A ∪ B| = |A| + |B| − |A ∩ B|.
• |P(A)| = 2ⁿ for |A| = n; subsets containing k fixed elements: 2ⁿ⁻ᵏ.

0.2.2 Ordered tuples, Cartesian product and its size; a relation as a set of tuples

• Ordered pair: (a,b) = (c,d) iff a = c and b = d. n-tuple = n ordered components.
• A × B = {(a,b) | a ∈ A, b ∈ B}; |A × B| = |A|·|B|; A × ∅ = ∅.
• A relation on D₁..Dₙ = a subset of D₁ × … × Dₙ: a set of tuples (no duplicates, no row order).
• Number of possible relations = 2^(|D₁|·…·|Dₙ|).

0.2.3 Logic: propositions, AND/OR/NOT, implication, truth tables, quantifiers and their negation

• ∧ both; ∨ at least one; p → q false only for T → F; p → q ≡ ¬p ∨ q.
• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q; ¬(p → q) ≡ p ∧ ¬q.
• ¬∀x P ≡ ∃x ¬P; ¬∃x P ≡ ∀x ¬P; ∀x P ≡ ¬∃x ¬P.
• ∀ pairs with →; ∃ pairs with ∧.
• Empty domain: ∀ true, ∃ false.

0.2.4 Counting toolkit: combinations, inclusion–exclusion

• Product rule: m × n. n! arrangements; 0! = 1.
• C(n, k) = n!/(k!(n − k)!); C(n, k) = C(n, n − k); Σₖ C(n, k) = 2ⁿ.
• Interleavings of m and n ordered steps: C(m + n, m).
• |A ∪ B| = |A| + |B| − |A ∩ B|; three sets: add singles, subtract pairs, add the triple.
• Groups of n attributes containing a fixed group X: 2ⁿ⁻|X|.

🧩 Phase 1 · ER Model

1.1.1 Entity, entity set, attribute, domain

• Entity = distinguishable thing we store data about. Entity type = category (schema); entity set = current collection (instance).
• Attribute = property of an entity; domain (value set) = allowed values.
• Chen: rectangle = entity type; ellipse = attribute.
• Make it an entity if several facts are kept about it or other things link to it.

1.1.2 Attribute types: simple/composite, single/multivalued, stored/derived, NULL-able, key attribute

• Simple vs composite (has parts); single-valued vs multivalued (set of values, double ellipse); stored vs derived (computed, dashed ellipse).
• NULL = no value: not applicable or unknown. Not 0, not "".
• Key attribute: unique for every entity in every possible state; underlined; may be composite; an entity type may have several keys.
• Store dob, derive age.

1.2.1 Relationship, relationship set, degree, roles, relationship attributes

• Relationship = association of entities; relationship type (schema), relationship set (instance) ⊆ E₁ × E₂ × …
• Diamond in Chen notation.
• Degree: unary/recursive (1 type), binary (2), ternary (3).
• Recursive relationships need role names.
• Relationship attributes describe the association (grade on ENROLLS).
• Max size of a binary relationship set = |E₁| × |E₂|.

1.2.2 Cardinality ratios; total vs partial participation; (min,max) notation

• Cardinality ratio (max): 1:1, 1:N, N:1, M:N. Chen: the number next to E = how many E's one partner can have.
• Participation (min): total (double line, every entity ≥ 1) or partial (may be 0).
• (min, max) next to E: each entity of E takes part in min..max relationships; min 0 = partial, min ≥ 1 = total. The "N" sits on the opposite side from Chen notation.
• Sizes: 1:1 ≤ min(a, b); 1:N (A one side) ≤ b; M:N ≤ a·b; total N-side participation in 1:N → exactly b.
• Relationship attributes of 1:1 / 1:N may move to an entity (the N side); M:N cannot.

1.2.3 Weak entity sets, identifying relationship, partial key

• Weak entity type: no key of its own; identified via an owner entity + partial key.
• Key(weak) = key(owner) + partial key (discriminator).
• Identifying relationship: double diamond; weak side total participation (double line); usually 1:N owner:weak.
• Notation: double rectangle (weak), double diamond (identifying), dashed underline (partial key).
• Deleting the owner deletes its weak entities.

1.2.4 Extended ER: specialization, generalization, aggregation

• Subclass IS-A superclass; inherits all attributes and relationships; adds local ones.
• Specialisation = top-down; generalisation = bottom-up; same diagram.
• Disjoint (at most one subclass) vs overlapping (several); total (must be in one, double line) vs partial.
• Aggregation: treat a relationship + its entities as an entity so it can join another relationship.

1.3.1 Modeling practice: English requirements to ER diagram

• Procedure: entities (+keys, weak?), attributes, relationships, ratio both ways, participation both ways, relationship attributes.
• "exactly one" = (1,1); "at most one" = (0,1); "at least one" = total; "may" = partial; "many" = N.
• "numbered within X" → weak entity owned by X.
• "some X are Y with extra facts" → subclass.
• Pair facts on the relationship; movable only for 1:1/1:N.

🔑 Phase 2 · Relational Model & Constraints

2.1.1 Relation, tuple, attribute, domain, degree, cardinality, schema; properties of relations

• Relation = table = set of tuples; attribute = named column; domain = allowed values.
• Degree (arity) = number of attributes (fixed); cardinality = number of tuples (changes).
• Relation schema R(A₁..Aₙ) vs relation state r(R) ⊆ dom(A₁) × … × dom(Aₙ).
• Properties: no duplicate tuples, unordered tuples, named (unordered) attributes, atomic values (1NF).
• Max cardinality = product of domain sizes; t[A] = value of A in t.

2.1.2 NULL: meaning and basic behaviour

• NULL = missing value (unknown, not applicable, or unknown whether it exists); not 0, not ''.
• Arithmetic with NULL → NULL. Comparison with NULL (even NULL = NULL) → UNKNOWN.
• Queries keep rows whose condition is TRUE; FALSE and UNKNOWN rows are dropped.
• Test with "is null", which is never UNKNOWN.
• Identifying attributes (primary key) must not be NULL.

2.2.1 Superkey, candidate key, primary key, alternate key; counting superkeys

• Superkey: no two tuples in any valid state agree on it; all attributes form a superkey; supersets of superkeys are superkeys.
• Candidate key = minimal superkey; may be composite; several may exist.
• Primary key = chosen candidate key, never NULL; others = alternate keys. Prime attribute = in some candidate key.
• Instance disproves, never proves, a key.
• Superkeys with one key of k attributes: 2ⁿ⁻ᵏ. Two keys: 2ⁿ⁻|K₁| + 2ⁿ⁻|K₂| − 2ⁿ⁻|K₁∪K₂|.
• Max candidate keys for n attributes: C(n, ⌊n/2⌋).

2.2.2 Foreign key; referencing vs referenced relations

• FK in R₁ references PK of R₂: every FK value equals some PK value in R₂, or is NULL.
• R₁ referencing (child), R₂ referenced (parent); arrow from FK to PK.
• Names may differ; domains must match.
• Several FKs per relation; self-referencing FKs allowed; an FK may be part of the PK (then it cannot be NULL).
• FK values may repeat; referenced values may be unused.

2.3.1 Domain, key, entity and referential integrity; which operations violate what

• Domain (values in domain), key (unique candidate keys), entity integrity (PK not NULL), referential integrity (FK matches a PK or is NULL).
• Insert: can violate all four. Delete: only referential (deleting a referenced parent). Update non-key: domain. Update PK: all four. Update FK: domain + referential.
• RI breaks by: inserting/updating a child FK, or deleting/updating a referenced parent PK.
• Insert into parent and delete from child are RI-safe.

2.3.2 Referential actions: restrict, cascade, set null; tracing cascading deletes

• Actions on parent delete/PK update: RESTRICT/NO ACTION (reject), CASCADE (delete/update children), SET NULL, SET DEFAULT.
• Cascades follow chains until nothing new refers to a deleted tuple.
• SET NULL changes direct children only; impossible for FKs in the PK or NOT NULL.
• RESTRICT on any affected reference rejects the whole delete.

2.4.1 Mapping strong and weak entities, composite and multivalued attributes

• Strong entity → table of simple attributes; PK = chosen key; composite → components; derived → not stored.
• Weak entity → table with owner PK (FK, cascade) + own attributes; PK = owner PK + partial key; identifying relationship: no table.
• Multivalued attribute → table (owner PK FK, value); PK = both.
• Tables so far = strong + weak + multivalued attributes.

2.4.2 Mapping 1:1, 1:N, M:N with participation; minimum number of tables

• M:N → new table (PK1, PK2 + attributes); PK = both.
• 1:N → FK (1-side PK) in the N-side table + relationship attributes.
• 1:1 → FK in the total-participation side (unique); both total → merge into one table.
• Recursive 1:N/1:1 → FK in same table; recursive M:N → new table.
• Minimum tables: M:N 3, 1:N 2, 1:1 2, 1:1 both total 1; + multivalued + weak + recursive M:N.

2.4.3 Ternary relationships; specialization/generalization mapping

• n-ary relationship → table with all participants' PKs + attributes; entity on a "1" side is left out of the PK.
• Specialisation: A super + sub (sub PK = FK to super); B subs only (needs total, best disjoint); C one table + type (disjoint, NULLs); D one table + flags (overlapping).
• Aggregation → relationship table references the aggregated relationship's PK.
• Checklist: strong, weak, 1:1, 1:N, M:N, multivalued, n-ary, hierarchy, aggregation.

🔎 Phase 3 · Query Languages

3.1.1 Selection, projection, rename; composing operations

• σc(R): rows satisfying c; same degree; 0 ≤ |σ| ≤ |R|; σ commutes and cascades into ∧.
• πL(R): listed columns, duplicates removed; degree = |L|; |π| ≤ |R|, equal if L contains a key.
• πL1(πL2(R)) = πL1(R) if L1 ⊆ L2.
• ρ renames a relation and/or its attributes.
• Nest operators or use ← assignment; evaluate inside out.

3.1.2 Union, intersection, difference; union compatibility

• ∪, ∩, − need union compatibility: same degree, matching domains.
• R ∩ S = R − (R − S); − is not commutative.
• Bounds: ∪ max(r,s)..r+s; ∩ 0..min(r,s); − max(0,r−s)..r.
• English "not" → everyone − those who did.

3.1.3 Cartesian product, theta join, equijoin, natural join

• R × S: degree adds, cardinality multiplies.
• Theta join = σθ(R × S); equijoin uses =, keeps both columns.
• Natural join: equality on all same-named attributes, one copy kept; degree = sum − common.
• No common attributes → ×; all common → ∩.
• |R ⋈ S| ∈ [0, |R|·|S|]; = |R| if join attributes are S's key and a non-NULL FK in R.

3.1.4 Outer joins: left, right, full

• R ⟕ S: join + unmatched R (NULL right). R ⟖ S: join + unmatched S (NULL left). R ⟗ S: both.
• Sizes: ⟕ = matches + unmatched R ≥ |R|; ⟗ = matches + unmatched R + unmatched S.
• R ⟖ S ≡ S ⟕ R (up to column order).
• "X with no Y": σY-col is null(X ⟕ Y) or π(X) − π(Y).

3.1.5 Division and for-all queries

• R(X, Y) ÷ S(Y) = X-values paired in R with every Y-tuple of S.
• = πX(R) − πX((πX(R) × S) − R).
• R ÷ ∅ = πX(R); candidates come only from R.
• |R ÷ S| ≤ ⌊|R|/|S|⌋ for non-empty S.
• Project dividend to (answer, match) and divisor to (match) first.

3.1.6 Equivalent expressions; min/max tuples in a result; extended RA (aggregation)

• σ cascades, commutes, distributes over ∪ ∩ −; push σ below ⋈ if it uses one side.
• π distributes over ∪ only.
• Bounds: ∪ max..sum; ∩ 0..min; − max(0,r−s)..r; × = r·s; ⋈ 0..r·s; ⟕ ≥ r; ÷ ≤ ⌊r/s⌋.
• Max A = πA(R) − πR1.A(σR1.A < R2.A(ρR1(R) × ρR2(R))); use > for min.
• Extended: γ aggregation (COUNT SUM AVG MIN MAX with grouping), generalised projection, outer joins.
• Basic set: σ, π, ∪, −, ×, ρ.

3.2.1 TRC syntax, tuple variables, free vs bound variables

• TRC query: { t | P(t) }; t is the only free variable.
• Atoms: t ∈ R; t.A op s.B; t.A op c.
• ∃s ∈ R (P) ≡ ∃s (s ∈ R ∧ P); ∀s ∈ R (P) ≡ ∀s (s ∈ R ⇒ P).
• Bound = introduced by a quantifier; free = otherwise.
• σ ↔ condition; π ↔ t.A target or t.A = s.A; ∪ ↔ ∨; − ↔ ∧ ¬.

3.2.2 Exists and for-all queries; translating between TRC and RA

• Join: ∃ per extra relation with matching conditions.
• None: ¬∃.
• All: ∀c ∈ D (cond ⇒ ∃ match) ≡ ¬∃c ∈ D (cond ∧ ¬∃ match).
• Wrong forms: ∀ with ∧ (too strong), ∃ with ⇒ (vacuously true).

3.2.3 Safe vs unsafe expressions; relational completeness

• dom(P) = constants in P + values in the relations P mentions.
• Safe: all result values in dom(P); the result variable is range-restricted in every branch; ¬ does not restrict.
• Relationally complete = expresses all basic RA.
• Codd: basic RA ≡ safe TRC ≡ safe DRC. None of them does aggregation or unbounded recursion.
• DRC: variables over values; TRC: variables over tuples.

3.3.1 SQL DDL: CREATE TABLE, data types, constraints, ON DELETE/ON UPDATE

• CREATE TABLE with types (INT, DECIMAL(p,s), CHAR(n), VARCHAR(n), DATE …).
• PRIMARY KEY = UNIQUE + NOT NULL, one per table; UNIQUE allows many NULLs.
• FOREIGN KEY … REFERENCES … ON DELETE/UPDATE CASCADE | SET NULL | SET DEFAULT | RESTRICT | NO ACTION (default).
• CHECK rejects only FALSE; DEFAULT fills omitted columns.
• ALTER TABLE ADD/DROP column/constraint; DROP TABLE removes schema + rows.

3.3.2 SQL DML: INSERT, UPDATE, DELETE

• INSERT INTO T [(cols)] VALUES (…) | SELECT …; missing columns get DEFAULT/NULL.
• UPDATE T SET … [WHERE …]: right-hand sides use old values; all qualifying rows change together.
• DELETE FROM T [WHERE …]: rows only; FK actions fire.
• No WHERE = all rows. DROP removes schema; DELETE does not.

3.3.3 SELECT–FROM–WHERE, DISTINCT, aliases, LIKE, BETWEEN, ORDER BY; bags vs sets

• SELECT [DISTINCT] list FROM tables WHERE cond ORDER BY … ≈ π(σ(×)) with bags.
• Order: FROM → WHERE → SELECT → DISTINCT → ORDER BY.
• SQL keeps duplicates; DISTINCT removes them.
• BETWEEN inclusive; IN list; LIKE with % (any, incl. empty) and _ (one char).
• Aliases needed for self-joins; ORDER BY ASC default, applied last.

3.3.4 NULL in SQL: three-valued logic, IS NULL, comparisons

• AND: F dominates; OR: T dominates; else U. NOT U = U.
• WHERE/HAVING keep only TRUE; CHECK rejects only FALSE.
• Test NULL with IS NULL / IS NOT NULL; = NULL is always UNKNOWN.
• x NOT IN (…, NULL) is never TRUE.
• DISTINCT/GROUP BY treat NULLs as one value; ORDER BY NULL position is system-dependent.

3.3.5 Aggregates, GROUP BY, HAVING; COUNT(*) vs COUNT(col); NULL handling

• COUNT(*) counts rows; COUNT(col), SUM, AVG, MIN, MAX ignore NULL; AVG = SUM/COUNT(col).
• Empty input: COUNT 0, others NULL; no GROUP BY → exactly one row.
• GROUP BY: one row per group; SELECT only grouping columns + aggregates; NULLs form one group.
• WHERE filters rows (no aggregates); HAVING filters groups.
• Order: FROM → WHERE → GROUP BY → HAVING → SELECT → DISTINCT → ORDER BY.

3.3.6 Joins in SQL: INNER, NATURAL, LEFT/RIGHT/FULL OUTER

• JOIN … ON (inner), USING (cols), NATURAL JOIN (all common names), LEFT/RIGHT/FULL OUTER JOIN, CROSS JOIN.
• ON conditions decide matching (outer rows still kept); WHERE filters afterwards (drops padded rows).
• After LEFT JOIN, count with COUNT(right.col).
• "No match": LEFT JOIN … WHERE right.key IS NULL.

3.3.7 UNION / INTERSECT / EXCEPT and their ALL variants

• UNION / INTERSECT / EXCEPT: set semantics (duplicates removed); need union compatibility.
• ALL: UNION m + n; INTERSECT min(m, n); EXCEPT max(0, m − n).
• Set operators treat NULL rows as equal to each other.
• Oracle's MINUS = EXCEPT.

3.3.8 Nested subqueries: IN, ANY/SOME, ALL, EXISTS, scalar subqueries

• IN: equals some value; NOT IN: differs from all, and no NULL present.
• op ANY: true for some value (empty → FALSE); op ALL: true for every value (empty → TRUE).
• > ANY ≈ > MIN; > ALL ≈ > MAX; = ANY ≡ IN; <> ALL ≡ NOT IN.
• NULL in the subquery: NOT IN and ALL can never be TRUE.
• EXISTS: at least one row; never UNKNOWN.
• Scalar subquery: one value; many rows → error; none → NULL.

3.3.9 Correlated subqueries; for-all in SQL; tracing a query on a table instance

• Correlated subquery references an outer column; evaluated per outer row.
• Some: EXISTS; none: NOT EXISTS; all: NOT EXISTS (… AND NOT EXISTS (…)).
• COUNT alternative: HAVING COUNT(DISTINCT x) = (SELECT COUNT(*) …); differs when the "all" set is empty.
• Trace with a table: outer row | inner result | condition | kept.
• NULL rows: comparisons inside COUNT give 0 matches.

3.3.10 Views and WITH

• View = stored query (virtual table); always current; used for security, simplicity, logical independence.
• Materialised view = stored rows, needs refresh.
• Updatable views: one table, no aggregates/GROUP BY/DISTINCT, key + required columns present.
• WITH CHECK OPTION: changes must keep rows visible.
• WITH name AS (…): temporary named result for one statement.

3.4.1 Translation drill: the same query in RA, TRC and SQL

• Filter: σ/π ↔ condition ↔ WHERE (+ DISTINCT).
• Some: ⋈ ↔ ∃ ↔ JOIN/EXISTS/IN.
• None: − ↔ ¬∃ ↔ NOT EXISTS/NOT IN/EXCEPT/LEFT JOIN IS NULL.
• All: ÷ ↔ ∀⇒∃ ↔ double NOT EXISTS/COUNT match.
• Max: self-product difference ↔ ¬∃ bigger ↔ MAX/>= ALL.
• Negate the existence, not the condition.

🧪 Phase 4 · FDs & Normalization

4.1.1 Why normalize: redundancy and insertion/deletion/update anomalies

• Redundancy = one fact stored in many rows.
• Update anomaly: copies must all change. Insertion anomaly: a fact needs an unrelated fact (key part would be NULL). Deletion anomaly: deleting one fact loses others.
• Cause: one table mixes facts determined by different attribute sets.
• Fix: split so each table's facts depend on its own key, without creating spurious tuples.

4.2.1 FD definition; trivial vs non-trivial; checking whether an FD holds on an instance

• X → Y: tuples agreeing on X agree on Y, in every valid state.
• Instance check: group by X; any group with two Y-values → FD fails. Instances disprove, never prove.
• Trivial: Y ⊆ X; non-trivial: Y ⊄ X; completely non-trivial: X ∩ Y = ∅.
• Superkey K ⇔ K → R.

4.2.2 Armstrong's axioms and derived rules

• Axioms: reflexivity (Y ⊆ X ⇒ X → Y), augmentation (X → Y ⇒ XZ → YZ), transitivity.
• Sound and complete.
• Derived: union, decomposition, pseudotransitivity (X → Y, WY → Z ⇒ WX → Z), composition.
• Never: split the left side, reverse, cancel.

4.2.3 Attribute closure; all candidate keys; prime vs non-prime; counting superkeys

• X⁺: start with X; add R for each L → R with L ⊆ result; repeat until no change.
• F ⊨ X → Y ⇔ Y ⊆ X⁺; X superkey ⇔ X⁺ = R.
• Keys: never-on-right attributes are in every key; only-on-right attributes in none; grow from the must-have set, smallest first, skip supersets of found keys.
• Prime = in some candidate key; non-prime = in none.
• Count superkeys with inclusion–exclusion over the keys.

4.2.4 Closure of an FD set; membership test; equivalence of FD sets

• F⁺ = all FDs implied by F.
• Membership: X → Y ∈ F⁺ ⇔ Y ⊆ X⁺.
• G covers F ⇔ every FD of F is implied by G (closures under G).
• F ≡ G ⇔ each covers the other ⇔ F⁺ = G⁺.
• |F⁺| = Σ over X of 2^|X⁺|.

4.2.5 Minimal (canonical) cover

• Minimal cover: equivalent; single-attribute right sides; no extraneous left attributes; no redundant FDs.
• Steps: split RHS → remove extraneous LHS attributes (A ∈ X⁺ under current set) → remove redundant FDs (A ∈ X⁺ under the others).
• Not unique; canonical cover groups same left sides.

4.3.1 Lossless-join decomposition: binary test and chase (table) method

• Lossless (non-additive): ⋈ of projections = r for every legal r (no spurious tuples).
• Binary: lossless ⇔ (R₁ ∩ R₂)⁺ ⊇ R₁ or ⊇ R₂. Empty intersection → lossy.
• Chase: rows = pieces, a's for owned attributes, apply FDs to equate; lossless ⇔ some row all a's.
• A lossless split of a lossless piece keeps the whole decomposition lossless.

4.3.2 Dependency preservation

• Fᵢ = FDs of F⁺ within Rᵢ. Preserving ⇔ (∪ Fᵢ)⁺ = F⁺.
• Quick: every FD inside some piece → preserving.
• Test X → Y: result = X; repeat result ∪= ((result ∩ Rᵢ)⁺ ∩ Rᵢ) over pieces; preserved ⇔ Y ⊆ result.
• Lossless and preserving are independent; lossless mandatory, preserving desirable.

4.4.1 1NF

• 1NF: atomic values, one value per cell; no sets, lists, repeating groups, nested tables.
• Fix multivalued attributes with a separate table (owner key, value).
• Atomicity depends on how values are used.
• BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF.

4.4.2 2NF (partial dependency)

• Partial dependency: proper subset of a candidate key → non-prime attribute.
• 2NF: 1NF + no partial dependency of any non-prime attribute on any candidate key.
• Single-attribute keys or all-prime attributes → automatically 2NF.
• Fix: move the partially dependent attributes out with the key part they depend on.

4.4.3 3NF (transitive dependency + formal condition)

• Transitive: key → B → C with B not a superkey, C non-prime.
• 3NF: for every non-trivial X → A, X is a superkey or A is prime.
• 3NF ⊂ 2NF.
• Highest-NF walk: superkey → OK; prime RHS → 3NF OK; part of key → 2NF violation; else 3NF violation.

4.4.4 BCNF; 3NF vs BCNF trade-off

• BCNF: every non-trivial X → A has X a superkey.
• BCNF ⊂ 3NF; the gap = FDs with non-superkey X and prime A (needs overlapping composite keys).
• Two-attribute relations are always BCNF.
• 3NF: lossless + preserving always possible. BCNF: lossless always, preserving not always.

4.4.5 Drill: highest normal form of a given relation

• Procedure: keys → prime set → split FDs → classify each (superkey / prime RHS / partial / transitive) → lowest level wins.
• Partial dependency on a non-prime → 1NF. Transitive only → 2NF. Only prime-RHS non-superkey FDs → 3NF. All left sides superkeys → BCNF.
• All attributes prime → at least 3NF.

4.4.6 Algorithms: 3NF synthesis, BCNF decomposition

• 3NF synthesis: minimal cover → one table per left side (X + its right sides) → add a key table if none contains a key → drop subset tables. Lossless + preserving + 3NF.
• BCNF decomposition: pick violating X → Y; split into XY and R − (Y − X); recurse with projected F⁺. Lossless + BCNF; may lose FDs; not unique.

4.4.7 Multivalued dependencies and 4NF

• X →→ Y: Y-values for an X-value independent of the rest (swap-closure).
• Complementation: X →→ Y ⇒ X →→ R − X − Y. Every FD is an MVD.
• Trivial MVD: Y ⊆ X or X ∪ Y = R.
• 4NF: every non-trivial MVD has a superkey left side; 4NF ⊂ BCNF.
• Lossless binary split ⇔ R₁ ∩ R₂ →→ R₁ (or R₂).

🌳 Phase 5 · Storage & Indexing

5.1.1 Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned

• Cost unit = block access (seek + rotational latency + transfer); avg latency = half a rotation.
• bfr = ⌊B / R⌋ (unspanned); b = ⌈r / bfr⌉.
• Spanned: b = ⌈r·R / B⌉, no waste; needed when R > B.
• Block pointer P vs record pointer Pr.

5.2.1 File organization: heap, sorted, hashed; cost of search/insert/delete

• log₂ b = power of 2 giving b; use ⌈log₂ b⌉ for whole steps.
• Heap: search b/2 avg (exists), b (missing or non-key); insert ~1.
• Sorted: ⌈log₂ b⌉ on the ordering field only; insert/delete ~b/2.
• Hashed: ~1 for equality on the hash field (+ overflow); no help for ranges.

5.3.1 What an index is; index entries; dense vs sparse

• Index entry = ⟨key, pointer⟩; index sorted by key.
• bfrᵢ = ⌊B/(K + P)⌋; bᵢ = ⌈entries/bfrᵢ⌉; cost = ⌈log₂ bᵢ⌉ + 1.
• Dense: entry per search-key value (per record for a key); any file.
• Sparse: entry per block (anchor); data must be sorted on that field.

5.3.2 Primary, clustering, secondary indexes; counting index blocks and block accesses

• Primary: ordering key; sparse; entries = b.
• Clustering: ordering non-key; sparse; entries = distinct values (pointer to first block).
• Secondary: non-ordering field; dense; key → entries = r; non-key → indirection block (+1 access).
• At most one primary or clustering; many secondary.
• Cost = ⌈log₂ bᵢ⌉ + 1 (+1 for indirection).

5.3.3 Multilevel indexes; fan-out; logarithm primer

• log_b x: power of b giving x; ⌈log_b x⌉ = smallest k with bᵏ ≥ x; log_b x = log₂ x / log₂ b.
• Multilevel: level 1 = base index; each higher level = sparse primary index on the one below; stop at one block.
• fo = bfrᵢ; t = ⌈log_fo r₁⌉; cost = t + 1.
• Static multilevel indexes are costly to update → B-trees.

5.4.1 Tree primer: node, root, leaf, height, search tree, balanced tree

• Root, parent, child, sibling, leaf, internal node, subtree; level of root = 1; height = number of levels.
• m-ary tree with h levels: max (m^h − 1)/(m − 1) nodes; m^(h−1) leaves.
• m-way search tree: ≤ m − 1 sorted keys, ≤ m children, keys split children's ranges.
• Balanced = all leaves at the same level; height ≈ log_m n; one node = one block.

5.5.1 B-tree structure and order (order conventions and the GATE trap)

• B-tree order p (max children): ≤ p − 1 keys; non-root internal ≥ ⌈p/2⌉ children; root ≥ 2 children unless leaf; all leaves same level.
• Each key appears once, with a record pointer.
• Node size: p·P + (p − 1)(K + Pr) ≤ B.
• Conventions: max children p; min keys d (d..2d keys); min degree t (t−1..2t−1 keys).

5.5.2 B-tree search and insertion with node splits

• Search: compare in node, stop if found, else follow the matching child; ≤ height accesses.
• Insert into a leaf; on overflow (p keys) split, median moves up; cascade; root split → height + 1.
• Trace format: level-by-level brackets; count every node split.

5.5.3 B-tree deletion basics; min/max keys; height bounds

• Delete internal key → swap with predecessor/successor in a leaf. Leaf underflow → borrow (rotate through parent) or merge (with parent's separator). Root emptied → height − 1.
• Max keys (height h) = p^h − 1. Min keys = 2⌈p/2⌉^(h−1) − 1.
• h_min = ⌈log_p(n + 1)⌉; h_max = 1 + ⌊log_⌈p/2⌉((n + 1)/2)⌋.

5.6.1 B+ tree: internal vs leaf nodes, leaf chaining, range queries

• Internal: ≤ p children, ≤ p − 1 keys, no record pointers; non-root ≥ ⌈p/2⌉ children.
• Leaves: ≤ p_leaf ⟨key, Pr⟩ entries + next pointer; non-root ≥ ⌈p_leaf/2⌉ entries; all keys here, sorted.
• Search always reaches a leaf (cost = height).
• Range: descend to the low key, then follow leaf links.
• Leaf level = dense index; internal levels = sparse multilevel index.

5.6.2 B+ tree order from block size, key size and pointer size

• Internal: p·P + (p − 1)K ≤ B. Leaf: p_leaf(K + Pr) + P ≤ B.
• Max records with h levels: p^(h−1)·p_leaf. Min: 2⌈p/2⌉^(h−2)⌈p_leaf/2⌉.
• B+ internal order > B-tree order for the same sizes.
• Check the question's definition of "order".

5.6.3 B+ tree insertion and deletion traces; height and capacity; B vs B+

• Insert into leaf; leaf overflow → split (left keeps ⌈(p_leaf+1)/2⌉), copy right's first key up; internal overflow → split, move middle key up; root split → height + 1.
• Delete from leaf; underflow → borrow (update separator) or merge (remove separator); separators may be stale.
• B vs B+: record pointers everywhere vs leaves only; lower vs higher fan-out; awkward vs easy ranges; median up vs copy up.

🔀 Phase 6 · Transactions & Concurrency

6.1.1 Transaction basics: read/write, commit/abort, ACID, transaction states

• Transaction = one logical unit of work: read(X), write(X), ending in commit or abort.
• Atomicity (recovery: undo), Consistency (programmer + constraints), Isolation (concurrency control), Durability (recovery: redo).
• States: active → partially committed → committed; active/partially committed → failed → aborted; committed/aborted = terminated.

6.2.1 Concurrency problems: lost update, dirty read, unrepeatable read, phantom

• Lost update: R1(X) R2(X) W1(X) W2(X).
• Dirty read: read uncommitted data (W1 R2 … A1).
• Unrepeatable read: R1(X) W2(X) C2 R1(X).
• Phantom: re-run query sees inserted/deleted rows; needs predicate/range locks.
• Isolation levels: RU allows dirty; RC stops dirty; RR stops unrepeatable; SERIALIZABLE stops phantoms.

6.3.1 Schedules: serial vs concurrent; counting possible schedules

• Schedule: interleaving that keeps each transaction's order; complete = all end in C/A.
• Serial schedules: n! for n transactions.
• Total schedules: (Σnᵢ)! / Πnᵢ!; non-serial = total − n!.

6.4.1 Directed graph primer: cycles, topological order

• Directed graph: vertices, edges u → v; path; cycle; DAG = acyclic.
• Topological order exists ⇔ acyclic.
• Algorithm: repeatedly take a vertex with no incoming edge (among remaining).
• Several choices → several orders; no edges → n! orders.

6.4.2 Conflict serializability: conflicting ops, precedence graph, equivalent serial orders

• Conflict: different transactions, same item, ≥ 1 write (RW, WR, WW).
• Conflict equivalent: same order for every conflicting pair.
• Precedence graph: Ti → Tj when Ti's conflicting op is first. CS ⇔ acyclic; serial orders = topological orders.
• Count conflict-equivalent schedules by fixing conflicting pairs and counting free interleavings.

6.4.3 View serializability; blind writes; relation to conflict serializability

• View equivalent: same initial reads, same reads-from, same final writes, for every item.
• VS = view equivalent to some serial schedule. CS ⊂ VS.
• VS but not CS ⇒ blind write (write without prior read). No blind writes ⇒ VS = CS.
• Test: CS? → VS. Not CS and no blind write → not VS. Else check the three conditions against candidate serial orders.

6.5.1 Recoverable, cascadeless and strict schedules; how they nest

• Tj reads from Ti: Tj reads X last written by Ti.
• Recoverable: reader commits after writer commits.
• Cascadeless: reads only committed data (read after the writer's commit).
• Strict: no read or write of X until its last writer commits/aborts.
• Strict ⊂ cascadeless ⊂ recoverable; serial is strict; independent of serializability.

6.6.1 Shared/exclusive locks; compatibility matrix

• S lock to read (shared), X lock to write (exclusive).
• Compatibility: only S–S compatible.
• Lock manager grants compatible requests, else the requester waits; upgrade S → X waits for other S holders.
• Locking needs a release rule (2PL) to guarantee serializability.

6.6.2 Two-phase locking: growing/shrinking, lock point, guarantees

• 2PL: growing (acquire only) then shrinking (release only); lock point = last acquisition.
• 2PL ⇒ conflict serializable; serial order = order of lock points.
• 2PL does not prevent deadlocks or cascading rollbacks; 2PL schedules ⊊ CS schedules.
• Upgrades count as acquisitions.

6.6.3 Strict, rigorous and conservative 2PL

• Strict 2PL: X locks held to commit/abort → strict schedules.
• Rigorous 2PL: all locks held to commit → serial order = commit order.
• Conservative 2PL: lock everything before starting → deadlock-free; needs predeclaration.
• All give conflict serializability; only conservative avoids deadlock.

6.6.4 Deadlocks: wait-for graph, wait-die, wound-wait, starvation

• Deadlock ⇔ cycle in the wait-for graph (Ti → Tj: Ti waits for Tj); detect, pick a victim, abort.
• Smaller TS = older. Wait-die: old waits, young dies. Wound-wait: old wounds young, young waits.
• Restart with the original TS → no starvation.
• Other: timeouts, no-waiting, global lock ordering.

6.7.1 Timestamp ordering protocol; Thomas write rule

• TS(Ti) at start; RTS(X), WTS(X) per item.
• read(X): abort if TS < WTS(X); else RTS = max(RTS, TS).
• write(X): abort if TS < RTS(X); abort if TS < WTS(X) (Thomas: ignore); else WTS = TS.
• Basic TO: CS, deadlock-free, starvation possible, not necessarily recoverable. Thomas: VS schedules allowed.

6.8.1 Multiple granularity, validation-based protocol, log-based recovery

• Multiple granularity: IS, IX, S, SIX, X; lock root-down, release bottom-up; IS/IX compatible; IX vs S incompatible.
• Optimistic: read → validate → write; order = validation order; good for rare conflicts.
• Log records + WAL. Deferred update: redo only. Immediate update: undo + redo.
• Checkpoint: committed before → nothing; committed after → redo; uncommitted → undo (old values).