Advanced Databases

Laws, Formulas, Symbols, and Worked Examples

Generated on 2026-01-02

How to use this sheet

● Memorize symbols first (what each letter means).

● Re-solve the worked examples without looking at the steps.

● Do the practice questions at the end focusing only on formulas and case studies.

● Arabic explanation is heavier for understanding: ‫رتكأ يبرعلا حرشلا‬.

Note: This is a learning/cheat-sheet style document, not a copy of lecture slides.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 1

 1) Relational Model & SQL/Relational Algebra Rules

Type compatibility (Union/Intersection/Difference)

Rule: R and S must have the same degree (same number of attributes) and corresponding
attributes must have the same domains (types).
AR: ‫( ةدمعألا ددع سفن مزال‬degree) ‫( بيترتلا سفنب دومع لك عون سفنو‬domains).
Example: If R(A:int,B:text) and S(A:int,B:text) → compatible. If S(A:int,C:text) but C is text
too, still compatible only if positions match intended meaning.

Common algebra equivalences (optimizer “laws”)

● Commutative: R ∪ S = S ∪ R, R ∩ S = S ∩ R, R ⋈ S = S ⋈ R (natural/inner join).

● Associative: (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T) (join order can change).

● Selection push-down: σ_c(R ⋈ S) = (σ_c(R)) ⋈ S if c uses only attributes of R.

● Projection push-down: π_X(R ⋈ S) can be pushed to keep only needed attributes (careful:
must keep join attributes).
● Replace × + σ with join: σ_joinCond(R × S) = R ⋈_joinCond S.

AR (‫)ناحتمالل مهم‬: ‫نيسحتلا يف ةيبهذلا ةدعاقلا‬: ‫ـلا لّزن‬SELECT ‫ـلا و‬PROJECT ‫ناشع يردب‬
‫ للقت‬intermediate results.

Worked example (rewrite)

Query: get employees in Dept=10 and join with Department table.
Start: σ_{Dept=10}(Employee ⋈ Department)

Rewrite (push selection): (σ_{Dept=10}(Employee)) ⋈ Department

Why: fewer Employee tuples enter the join → fewer I/Os.

AR: ‫نّوجن نيدعبو لوألا رتلفنب‬، ‫رتلفن مث نّوجن ام لدب‬.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 2

 2) Functional Dependencies & Normalization

Symbols
Symbol Meaning (EN) Meaning (AR)
X→Y Functional dependency: X determines Y ‫يفيظو دامتعا‬: X ‫ ددحي‬Y
X⁺ Attribute closure of X under FDs ‫ تافصلا قالغإ‬X ‫ـلا مادختساب‬FDs
K Key (candidate key) of relation R ‫ةقالعلل )حشرم( حاتفم‬
SK Superkey ‫)دئاز نوكي دق( قئاف حاتفم‬

Armstrong Axioms (FD inference laws)

● Reflexivity: if Y ⊆ X then X → Y

● Augmentation: if X → Y then XZ → YZ

● Transitivity: if X → Y and Y → Z then X → Z

● Useful derived rules: Union (X→Y and X→Z ⇒ X→YZ), Decomposition (X→YZ ⇒ X→Y and
X→Z), Pseudotransitivity (X→Y and WY→Z ⇒ WX→Z).
AR: ‫ـلا قاقتشا دعاوق يد‬FDs، ‫ جتنتسا وأ تبثِا“ لاؤس يجييب اًبلاغ‬FD”.

Attribute Closure X⁺ (formula/algorithm)

Goal: compute all attributes functionally determined by X using FDs F.
● Start: X⁺ = X

● Repeat: if (A → B) in F and A ⊆ X⁺ then add B to X⁺

● Stop when X⁺ stops changing

Worked example: R(A,B,C,D), F = { A→B, B→C, AC→D }. Compute A⁺.

Step 1: A⁺ = {A}. Apply A→B ⇒ {A,B}. Then B→C ⇒ {A,B,C}. Now AC→D: since A and C are in
closure ⇒ add D ⇒ {A,B,C,D}.
Answer: A⁺ = {A,B,C,D} so A is a key.
AR: ‫ـب أدبن‬A، ‫ـلا نم هيلع ردقن يللا دوزن‬FDs ‫فقن ام دحل‬.

Keys and Superkeys

● Superkey: X is a superkey if X⁺ contains all attributes of R.

● Candidate key: a minimal superkey (no attribute can be removed).

● Primary key: chosen candidate key.

Worked example: R(A,B,C,D), F={A→B, B→C}. Find candidate keys.

A⁺ = {A,B,C}. Missing D ⇒ A is not a key. If D has no FD, then AD⁺ = {A,D,B,C} = all ⇒ AD is
a key. Minimal? remove A gives D⁺={D} no; remove D gives A⁺ missing D. So AD is
candidate key.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 3

 AR: ‫ هيف ول‬attribute “‫ يز ”هدحول فقاو‬D، ‫حاتفملل هفيضت مزال اًبلاغ‬.

Normal Forms (rules)

● 1NF: atomic values (no lists/repeating groups).

● 2NF: 1NF + no partial dependency of non-key on part of a composite key.

● 3NF: 2NF + no transitive dependency (non-key depends on non-key).

● BCNF: for every nontrivial FD X→Y, X is a superkey.

Lossless-join test (two-way decomposition)

Decompose R into R1 and R2. The decomposition is lossless if: (R1 ∩ R2) → R1 OR (R1 ∩ R2)
→ R2 (under F⁺).
AR: ‫ـلا ول‬intersection ‫ ىقبي لماكلاب نيلودجلا نم ةدحاو ددحي‬Lossless.

Worked example (lossless)

R(A,B,C), F={A→B}. Decompose into R1(A,B) and R2(A,C). Intersection = {A}. Since A→B, we
have A→R1. Therefore lossless.
AR: A ‫ ددحي‬R1، ‫ عايض شيفم نذإ‬tuples ‫ـلا دنع‬join.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 4

 3) Storage, File Organization, and Indexing Formulas

Symbols
Symbol Meaning
B Block size (bytes)
R Record size (bytes)
r Number of records
bfr Blocking factor = number of records per block
b Number of data blocks
K Key size (bytes)
P Pointer size (bytes)
RI Index entry size (bytes)
bfr_i Index blocking factor
b_i Number of index blocks

Blocking factor and number of blocks

Formula: bfr = ⌊B / R⌋ (unspanned). b = ⌈r / bfr⌉
AR: bfr ‫كولب يف لخدي لجس ماك ينعي‬. b ‫فلملل نيجاتحم كولب ماك ينعي‬.
Worked example: B=2048, R=180, r=60,000
bfr = floor(2048/180) = 11. b = ceil(60000/11) = 5455.

Index entry size and index blocks

Formulas: RI = K + P. bfr_i = ⌊B / RI⌋. b_i = ⌈(#entries) / bfr_i⌉.
AR: ‫ـلا مجح‬entry = ‫ حاتفم‬+ pointer. ‫ ماك بسحن مث‬entry ‫سرهف كولب يف‬، ‫ددع نيدعبو‬
‫سرهفلا تاكولب‬.
Worked example: K=10 bytes, P=8 bytes, primary sparse index on ordered file
RI=18 bytes. bfr_i=floor(2048/18)=113. #entries≈b=5455. b_i=ceil(5455/113)=49.

Search cost formulas (I/O in blocks)

● Linear search (unordered file): average ≈ b/2, worst = b

● Binary search (ordered file): ≈ ⌈log2(b)⌉ + 1

● Hash (equality): average ≈ 1 (plus overflow handling)

● Binary search on index: ⌈log2(b_i)⌉ + 1 (then +1 for data block if needed)

AR: ‫يجييب لاؤس رتكأ‬: ‫ ةنراقم‬cost ‫( نيب‬ordered vs primary index vs hashing).

Worked example (cost comparison)

Advanced Databases – Laws & Formulas (with Worked Examples) Page 5

 Using the above: b=5455, b_i=49.
Binary search on ordered file cost ≈ ceil(log2(5455)) + 1 = 14.
Binary search on primary index cost ≈ ceil(log2(49)) + 1 (index blocks) + 1 (data) ≈ 7.
AR: ‫ هنأل ثحبلا ةحاسم للقي سرهفلا‬b_i ‫ نم رغصأ‬b.

Dense vs Sparse rules

● Primary index on ordered key field is usually sparse (1 entry per data block).

● Clustering index on ordered non-key is often sparse/nondense (1 entry per distinct value,
points to first block of that value).
● Secondary index is usually dense (because the file is not ordered on that attribute).

AR: secondary ‫ اًبلاغ‬dense، primary ‫ اًبلاغ‬sparse. ‫ريتك لأستتب يد‬.

B-tree / B+tree key formulas (high level)

Let p be the maximum number of pointers (fanout) in an internal node.
● Max keys per internal node = p - 1

● Min pointers (non-root) ≈ ceil(p/2); min keys ≈ ceil(p/2) - 1

● Height h approx: h ≈ ceil(log_p(N)) where N is number of leaf pages/entries (rough

intuition)
● B+ tree stores record pointers at leaves; leaves often linked → fast range scans.

AR: ‫ةركف مهأ‬: ‫ ةرجشلا‬balanced، ‫ىوتسملا سفن قاروألا لك‬. B+ ‫قاروألا يف تانايبلا طحي‬
‫طقف‬.

Worked mini-example (B+ tree idea)

If leaf nodes are linked, scanning keys from 100 to 200 visits consecutive leaves without
going back up the tree.
AR: ‫جنيرلا‬: ‫ برقأل لزنت‬leaf ‫ ىلع يشمت مث‬linked list.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 6

 4) Query Processing Algorithms – Cost Cheat Sheet

Selection (σ) with/without index

● Full scan: cost ≈ b

● Using primary index: cost ≈ ⌈log2(b_i)⌉ + 1 (+ blocks containing qualifying records)

● Using hash index: equality lookup ≈ 1 (plus overflow)

AR: ‫ رايتخا‬access path (scan vs index) ‫ةفلكتلا يف ايندلا بلقيب‬.

Join cost formulas (common exam patterns)

Assume we join R and S. Let b_R = blocks(R), b_S = blocks(S), r_R = tuples(R). Let M be
available buffer pages.
● Tuple nested-loop join (TNLJ): cost ≈ b_R + r_R * b_S (very expensive).

● Block nested-loop join (BNLJ): cost ≈ b_R + ceil(b_R / (M-2)) * b_S.

● Sort-merge join: cost ≈ sort(R) + sort(S) + (b_R + b_S) for merge.

● Hash join (simple cost model): cost ≈ 3*(b_R + b_S) (partition + build/probe), varies by
implementation.
AR: ‫يجييب دحاو رتكأ‬: BNLJ formula ‫ اهيف نأل‬M-2 buffers.

Worked example (BNLJ)

Given b_R=1000 blocks, b_S=500 blocks, M=52 buffers. Compute BNLJ cost using R as outer.
BNLJ cost = b_R + ceil(b_R/(M-2))*b_S = 1000 + ceil(1000/50)*500 = 1000 + 20*500 =
11000 I/Os.

AR: ‫( لّمحن ةرم لك‬M-2) ‫ نم تاكولب‬R، ‫ حسمن‬S ‫ةلماك ةرم‬.

External sort (two-phase multiway merge – simplified)

Let b = number of blocks to sort, M = buffer pages. Number of initial runs ≈ ceil(b/M). Each
merge pass can merge up to (M-1) runs.
Rough cost model: each pass reads+writes the file once ⇒ 2b I/Os per pass. Total ≈ 2b*(1 +
#mergePasses).
AR: ‫ـلا ددع كلأسي اًبلاغ ناحتمالا‬passes ‫ ةيبيرقتلا ةفلكتلا وأ‬2b per pass.

Worked example (external sort passes)

Sort b=1000 blocks with M=101 buffers. Runs=ceil(1000/101)=10. Merge capacity=100
runs per pass ⇒ need 1 merge pass. Total passes = 1(initial) + 1(merge) = 2. Cost ≈ 2b*2 =
4000 I/Os.
AR: ‫ـلا ددع ول‬runs ‫( نم لقأ‬M-1)، ‫ ىقبي‬Pass ‫ـلل ةيافك دحاو‬merge.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 7

 5) Query Optimization Statistics & Estimation

Selectivity and cardinality estimation

Symbols: N = #tuples, s = selectivity (0..1), |out| = output cardinality
Formula: |out| ≈ s * N
AR: selectivity ‫طرشلا يّدعته يللا فوفصلا ةبسن ينعي‬.
Worked example: Table has N=1,000,000 rows. Predicate selectivity s=0.02. Output ≈ 0.02 *
1,000,000 = 20,000 rows.

Heuristic rewrite checklist (memorize)

● Break conjunctive selection into a cascade: σ_{c1 AND c2}(R) = σ_{c1}(σ_{c2}(R))

● Push selections and projections down the tree as early as possible

● Replace × + σ with join

● Reorder joins (commutativity/associativity) to join the most selective relations first

● Choose access paths: index scan vs full scan based on selectivity and clustering

AR: ‫”ناحتمالا نيناوق“ يد‬: ‫ لاؤس كلاج ول‬optimization، ‫ بتكا‬2-3 ‫صالخو مهنم دعاوق‬.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 8

 6) Transactions, Concurrency, and Recovery – Rules & Tests

ACID quick laws

● Atomicity: all operations commit or none (rollback)

● Consistency: constraints preserved from one consistent state to another

● Isolation: concurrency should behave as if serial (depending on isolation level)

● Durability: committed changes persist after crash

AR: Atomicity=‫شالباي هلكاي‬. Isolation=‫رثؤم لخادت شيفم‬. Durability=‫ دعب‬commit ‫شم‬

‫حوريب‬.

Schedule properties (definitions)

● Recoverable: if Tj reads from Ti then Ti must commit before Tj commits.

● Cascadeless: transactions read only committed data (no dirty reads).

● Strict: no transaction reads/writes X until the last writer of X commits/aborts.

AR: Strict ⊂ Cascadeless ⊂ Recoverable (strict ‫)ىوقأ‬.

Conflict-serializability test (precedence graph)

● Build a graph with one node per transaction.

● Add edge Ti → Tj if an operation of Ti conflicts with an operation of Tj on same item and Ti

happens first.
● If graph is acyclic ⇒ schedule is conflict-serializable.

Worked example: Schedule: r1(X), w1(X), r2(X), w2(X). Conflicts: w1(X) before r2(X) and
w2(X) ⇒ edge T1→T2 only. Acyclic ⇒ serial order T1 then T2.
AR: ‫ هيف ول‬cycle ‫ شم ىقبي‬serializable.

Locking laws
Shared lock (S) for read, Exclusive lock (X) for write. Compatibility: S with S is OK, anything
with X conflicts.

S X
S ✓ ✗
X ✗ ✗
AR: S ‫ عم‬S ‫عفني‬. ‫ عم ةجاح يأ‬X ‫ال‬.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 9

 7) Practice Questions (Formulas & Case Studies)
Solve without looking at the worked examples. Answers are at the end.
● Given B=4096 bytes, R=240 bytes, r=120,000. Compute bfr and b.

● Index entry: key=12 bytes, pointer=8 bytes, B=2048. Compute RI and bfr_i.

● Primary sparse index: file has b=8000 data blocks, bfr_i=100. Compute b_i.

● Cost: b=8000 ordered file. Approx binary search cost?

● Cost: b_i=80 index blocks. Binary search index + fetch data block cost?

● Join: b_R=2000, b_S=400, M=42. Compute BNLJ cost (R outer).

● Selection selectivity: N=2,500,000, s=0.004. Estimate output cardinality.

● FD closure: R(A,B,C,D,E), F={A→BC, C→D, D→E}. Compute A⁺.

● Find candidate key: R(A,B,C,D), F={A→B, C→D}. (Hint: what attributes are never on RHS?)

● Lossless test: R(A,B,C), F={A→B}. Decompose into R1(A,B) and R2(B,C). Is it lossless?
Why?
● Schedule serializability: r1(X), w2(X), w1(X). Build precedence edges.

● True/False: Secondary index on non-ordering attribute is typically dense. Explain.

● Which is better for range queries: hash or B+tree? Explain in one sentence.

● Given b=1000, M=101 buffers. How many initial runs? How many merge passes? Total
passes?
● Explain in one line why pushing selections down reduces cost.

Answer Key (short)

● 1) bfr=floor(4096/240)=17; b=ceil(120000/17)=7059.

● 2) RI=12+8=20; bfr_i=floor(2048/20)=102.

● 3) b_i=ceil(8000/100)=80.

● 4) ceil(log2(8000))+1 = 13+1 = 14.

● 5) ceil(log2(80))+1+1(data) = 7+2=9 (if counting +1 index fetch +1 data).

● 6) 2000 + ceil(2000/(42-2))*400 = 2000 + ceil(2000/40)*400 = 2000 + 50*400 = 22000.

● 7) |out|≈0.004*2,500,000=10,000.

● 8) A⁺={A,B,C,D,E}.

● 9) Attributes not on RHS: A and C → candidate key AC (check AC⁺ = all).

● 10) Intersection = {B}. Need B→R1 or B→R2. We have A→B only, so not lossless.

● 11) Conflicts: w2(X) before w1(X) ⇒ T2→T1; r1(X) before w2(X) ⇒ T1→T2. Cycle ⇒ not
conflict-serializable.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 10

● 12) True (usually dense) because file not ordered on that attribute.

● 13) B+tree, because sorted keys and linked leaves make range scans efficient.

● 14) runs=ceil(1000/101)=10; merge capacity=100 ⇒ 1 merge pass; total passes=2.

● 15) It reduces the number of tuples entering expensive ops like joins, shrinking
intermediate results.

Advanced Databases – Laws & Formulas (with Worked Examples) Page 11