Formula sheet

Every formula from every topic. Type to filter.

🧱 ER Model, Relational Model & Keys

Super keys with one candidate key of size k (n attributes)
2^(n − k)
Super keys with two candidate keys K1, K2
2^(n−|K1|) + 2^(n−|K2|) − 2^(n−|K1 ∪ K2|)
Maximum candidate keys in n attributes
C(n, ⌊n/2⌋) (all keys of the middle size)
Tables for a binary relationship
M:N → 3 tables; 1:N → 2 tables; 1:1 → 2 tables (1 if both total)
Key of a relationship table
M:N: both keys; 1:N: the key of the N side; 1:1: either key

🔣 Relational Algebra & Calculus

Union
max(m, n) ≤ |R ∪ S| ≤ m + n
Intersection
0 ≤ |R ∩ S| ≤ min(m, n)
Difference
max(0, m − n) ≤ |R − S| ≤ m
Cross product
|R × S| = m · n (columns add up)
Natural join
0 ≤ |R ⋈ S| ≤ m · n; with join column a key of S: ≤ m
Division
R ÷ S = π_A(R) − π_A((π_A(R) × S) − R)
Theta join
R ⋈_θ S = σ_θ(R × S)

🗄️ SQL

Evaluation order
FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY
COUNT(*) vs COUNT(col)
COUNT(*) counts all rows; COUNT(col) skips NULLs
Empty set
COUNT = 0; SUM / AVG / MIN / MAX = NULL; x > ALL(∅) = true; x > ANY(∅) = false
Three-valued logic
F∧U = F, T∧U = U, T∨U = T, F∨U = U, ¬U = U
Row counts of joins
cross join = m · n; inner join ≤ m · n; left outer ≥ m
Division in SQL
NOT EXISTS (… WHERE NOT EXISTS (…))

🔗 Functional Dependencies

X → Y holds iff
Y ⊆ X⁺
Super key
X⁺ = all attributes
Candidate key
a super key none of whose proper subsets is a super key
Union rule
X → Y and X → Z ⟹ X → YZ
Decomposition rule
X → YZ ⟹ X → Y and X → Z
Pseudo-transitivity
X → Y and WY → Z ⟹ WX → Z
Equivalence
F ≡ G iff F covers G and G covers F

🧩 Normal Forms & Decomposition

2NF violation
part of a candidate key → non-prime attribute
3NF condition
for X → A: X is a super key OR A is prime
BCNF condition
for X → A: X is a super key
Binary lossless test
(R1 ∩ R2) → (R1 − R2) or (R1 ∩ R2) → (R2 − R1) is in F⁺
Dependency preservation test
Z = X; Z = Z ∪ (closure(Z ∩ Ri) ∩ Ri) until stable; Y ⊆ Z
Guarantees
BCNF: lossless, maybe not DP. 3NF synthesis: lossless and DP
Hierarchy
BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF

🔀 Transactions & Concurrency Control

Conflict pairs
RW, WR, WW on the same item by different transactions
Conflict serializable
precedence graph has no cycle
Serial orders of n transactions
n! (for counting equivalent serial schedules use topological orders)
Schedule hierarchy
strict ⊂ cascadeless ⊂ recoverable; conflict SR ⊂ view SR
Timestamp read rule
abort if TS(Ti) < WTS(X) else RTS = max(RTS, TS(Ti))
Timestamp write rule
abort if TS(Ti) < RTS(X) or TS(Ti) < WTS(X) (ignore the latter with Thomas); else WTS = TS(Ti)
Lock compatibility
S–S yes; S–X, X–S, X–X no

🌲 File Organisation & Indexing

Blocking factor
bfr = ⌊B / R⌋
File blocks
b = ⌈r / bfr⌉
Binary search on a sorted file
⌈log₂ b⌉ block accesses
Sparse (primary) index entries
one per data block = b
Index entries per block
⌊B / (K + P)⌋
B+ tree order p (internal)
largest p with p·P + (p − 1)·K ≤ B
B+ tree leaf
largest p_leaf with p_leaf·(K + P_rec) + P_next ≤ B
Min keys
internal: ⌈p/2⌉ − 1 per node; leaf: ⌈(p − 1)/2⌉