Super keys from multiple candidate keys:
Use inclusion-exclusion principle.

Cartesian product result size:
|R × S| = |R| × |S| tuples; attributes = degree(R) + degree(S)

Natural join result size:
0 ≤ |R ⋈ S| ≤ |R| × |S|
= |R| × |S| only when join attribute matches all tuples
= 0 when no tuples share a join attribute value

Join size estimate (uniform distribution):
|R ⋈_{A=B} S| ≈ |R| × |S| / max(V(A,R), V(B,S))
where V = number of distinct values

X is a super key iff: X+ = all attributes of R

FD A→B holds in F iff: B ⊆ A+ (computed under F)

Armstrong’s Axioms:
Reflexivity: Y ⊆ X → X→Y
Augmentation: X→Y → XZ→YZ
Transitivity: X→Y, Y→Z → X→Z
Union: X→Y, X→Z → X→YZ
Decomposition: X→YZ → X→Y and X→Z

Lossless decomposition test (R → R1, R2):
(R1 ∩ R2) → R1 ∈ F+   OR   (R1 ∩ R2) → R2 ∈ F+
i.e., common attributes form a key for R1 or R2

BCNF vs 3NF violation pattern:
Relation violates BCNF but satisfies 3NF when:
∃ non-trivial X→A where X is NOT a super key AND A IS a prime attribute

Number of tables in 3NF decomposition:
One table per FD in canonical cover + one table for a candidate key (if not already covered)

Canonical Cover F_c:
Minimal set of FDs equivalent to F; no extraneous attributes or redundant FDs

Leaf node capacity n_leaf (max keys per leaf):
n_leaf × (K + P_data) + P_next ≤ B
n_leaf = ⌊(B – P_next) / (K + P_data)⌋

Min/Max keys in nodes:
Non-root internal: min ⌈n/2⌉-1 keys, max n-1 keys
Non-root leaf: min ⌈n_leaf/2⌉ keys, max n_leaf keys
Root: min 1 key

Min/Max keys in B+ tree of height h (order n):
Max keys = (n-1) × (1 + n + n² + … + n^(h-1)) + n^h × n_leaf
Min keys (height h, h ≥ 1): 2 × ⌈n/2⌉^(h-1) × ⌈n_leaf/2⌉

Min leaves for N records:
Min leaf nodes = ⌈N / n_leaf⌉

Disk accesses for point query (B+ tree height = h):
= h + 1 (h for tree traversal + 1 for data block)

Join cost (b_R, b_S = blocks; n_R = tuples in R; M = memory buffers):
Tuple nested loop: b_R + n_R × b_S
Block nested loop: b_R + ⌈b_R/(M-2)⌉ × b_S
Merge join (pre-sorted): b_R + b_S
Hash join: 3(b_R + b_S) [assumes partition fits in M-2 pages]

Sort cost (external merge sort):
Passes = 1 + ⌈log_{M-1}(⌈b_r/M⌉)⌉
Total I/Os = 2 × b_r × passes

Precedence graph:
Edge Ti → Tj if Ti has conflicting operation before Tj’s on same item
Acyclic graph → conflict serializable; cyclic → not conflict serializable

2PL lock compatibility:
S+S: compatible (grant both) | S+X: incompatible | X+X: incompatible

Timestamp ordering:
Read(Ti, Q): abort if TS(Ti) < W-timestamp(Q)
Write(Ti, Q): abort if TS(Ti) < R-timestamp(Q)
              ignore (Thomas Write Rule) if TS(Ti) < W-timestamp(Q)