Quizmaster

Learning objectives

What you will be able to explain

Which level of the memory hierarchy is typically the fastest to access?
Evaluate the following statements about locality:
A relation has 12,000 tuples. Each tuple has 108 bytes payload plus a 12-byte tuple header. Blocks are 1,024 bytes with 24-byte block header. How many blocks are required?
For OLTP-style point updates and single-tuple access, which layout is usually preferable?
Pointer swizzling/unswizzling is used to...
A DBMS uses Steal + No-Force. Which recovery capabilities are required after crashes?

Section 01

Which level of the memory hierarchy is typically the fastest to access? to A relation has 12,000 tuples. Each tuple has 108 bytes payload plus a 12-byte tuple header. Blocks are 1,024 bytes with 24-byte block header. How many blocks are required?

Which level of the memory hierarchy is typically the fastest to access?

Registers are closest to the CPU execution units and therefore have the lowest access latency among the listed options.

Evaluate the following statements about locality:

A/B/D are core cache-locality principles. C is false because temporal locality is one of the primary reasons caches are effective.

A relation has 12,000 tuples. Each tuple has 108 bytes payload plus a 12-byte tuple header. Blocks are 1,024 bytes with 24-byte block header. How many blocks are required?

Path of Calculation: 1. Tuple size = 108 + 12 = 120 bytes. 2. Usable bytes per block = 1024 - 24 = 1000 bytes. 3. Tuples per block = floor(1000 / 120) = 8. 4. Required blocks = 12000 / 8 = 1500. Final answer: 1500.

Section 02

For OLTP-style point updates and single-tuple access, which layout is usually preferable? to A DBMS uses Steal + No-Force. Which recovery capabilities are required after crashes?

For OLTP-style point updates and single-tuple access, which layout is usually preferable?

Row stores keep tuple attributes together, which is favorable for transactional point reads/writes touching many columns of a row.

Pointer swizzling/unswizzling is used to...

Swizzling maps stable on-disk references to fast in-memory pointers, and unswizzling restores durable address form when needed.

A DBMS uses Steal + No-Force. Which recovery capabilities are required after crashes?

Steal allows uncommitted data on disk (needs UNDO). No-Force allows committed data still in memory at crash (needs REDO).

Section 03

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, nodes have private memory but access one common storage system. to Which task belongs to the parser (and not to preprocessing)?

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, nodes have private memory but access one common storage system.

Private per-node memory + shared storage is the defining pattern of Shared Disk systems.

Which is an extreme form of vertical partitioning?

Column stores separate attributes into independent storage segments, which is effectively extreme vertical decomposition.

Which task belongs to the parser (and not to preprocessing)?

The parser performs syntax analysis and grammar-based parsing. Semantic checks and algebraic transformation occur later.

Section 04

Relational algebra equivalences: True or False? to For independent predicates, estimate $|\sigma_{A=10 \land B<50}(R)|$ with $|R|=18,000$ , $V(R,A)=60$ , and selectivity $(B<50)=0.25$ .

Relational algebra equivalences: True or False?

A/B/D are valid. C is invalid because both sides of the union must be filtered:

\sigma_{c1}(R \cup S)=\sigma_{c1}(R) \cup \sigma_{c1}(S)

Estimate $|\sigma_{A=10}(R)|$ for $|R|=24,000$ and $V(R,A)=300$ under uniformity.

Path of Calculation: 1. Equality selectivity estimate:

1 / V(R,A)

. 2. Cardinality:

|R| / V(R,A) = 24000 / 300 = 80

. Final answer: 80.

For independent predicates, estimate $|\sigma_{A=10 \land B<50}(R)|$ with $|R|=18,000$ , $V(R,A)=60$ , and selectivity $(B<50)=0.25$ .

Path of Calculation: 1. Selectivity

(A=10)=1/60

. 2. Combined selectivity

=(1/60) \cdot 0.25 = 1/240

. 3. Result size

=18000 \cdot 1/240 = 75

. Final answer: 75.

Section 05

Which rule rewrites selection over cartesian product into an explicit join? to Greedy join ordering on $R,S,T$ : $|R|=1000$ , $|S|=20$ , $|T|=400$ , $sel(R,S)=0.02$ , $sel(S,T)=0.1$ , $sel(R,T)=0.001$ . Which pair is selected first?

Which rule rewrites selection over cartesian product into an explicit join?

Join introduction applies:

\sigma_{R.a=S.b}(R \times S) \rightarrow R \bowtie_{R.a=S.b} S

Match histogram types to their core characteristic.

Equi-width fixes range widths; equi-depth adapts range widths to keep bucket tuple counts similar.

Greedy join ordering on $R,S,T$ : $|R|=1000$ , $|S|=20$ , $|T|=400$ , $sel(R,S)=0.02$ , $sel(S,T)=0.1$ , $sel(R,T)=0.001$ . Which pair is selected first?

Intermediate estimates:

|R \bowtie S|=1000\cdot20\cdot0.02=400

|S \bowtie T|=20\cdot400\cdot0.1=800

|R \bowtie T|=1000\cdot400\cdot0.001=400

. Greedy picks the smallest, so there is a tie between RS and RT.

Section 06

Estimate $|R \bowtie S|$ with $|R|=8,000$ , $|S|=4,000$ , $V(R,K)=500$ , $V(S,K)=200$ . to Evaluate 2PL validity of a lock sequence.

Estimate $|R \bowtie S|$ with $|R|=8,000$ , $|S|=4,000$ , $V(R,K)=500$ , $V(S,K)=200$ .

Path of Calculation: 1. Use

|R \bowtie S| \approx \frac{|R|\cdot|S|}{\max(V(R,K),V(S,K))}

. 2. Numerator:

8000\cdot4000=32,000,000

. 3. Denominator:

\max(500,200)=500

. 4. Result:

32,000,000/500=64,000

. Final answer: 64,000.

What is the defining 2PL rule?

2PL has growing and shrinking phases. Once shrinking starts (first unlock), acquiring new locks violates 2PL.

Evaluate 2PL validity of a lock sequence.

Initial sequence acquires locks before first unlock, so it is valid. Adding a new lock request after unlock violates the 2PL shrinking-phase rule.

Guided checkpoint

$T$ : $Lock_S(A), Read(A), Lock_X(B), Write(B), Unlock(A), Unlock(B)$

Would the initial sequence be 2PL? If $Lock_S(C)$ is requested after $Unlock(A)$ , would it still be 2PL?

Section 07

Which lock mode is compatible with an existing SIX lock (same hierarchy node)? to In 2PC, what forces the coordinator to decide global ABORT?

Which lock mode is compatible with an existing SIX lock (same hierarchy node)?

In the standard MGL compatibility matrix, SIX is only compatible with IS at the same node.

Under Snapshot Isolation, $T_1$ starts at $ST=10$ , $T_2$ commits an update on $X$ at $CT=20$ , and $T_1$ reads $X$ at time 25. Which version does $T_1$ read?

Snapshot Isolation reads from the transaction-start snapshot, not read-time visibility. So updates committed after

ST

are invisible.

In 2PC, what forces the coordinator to decide global ABORT?

2PC requires unanimous YES votes to commit. Any NO (or equivalent failure to promise commit) implies global abort.

Section 08

Why is classic 2PC considered problematic under failures? to ARIES Redo: mark each UPDATE as Redo or Ignore

Why is classic 2PC considered problematic under failures?

Participants can block waiting for a coordinator decision if failures occur in the uncertainty window.

Winners and losers at crash time

A transaction is a winner if it has a commit record before crash. T1 committed at LSN 50, T2 did not.

Guided checkpoint

At crash, log contains:

LSN	Log Record
10	$\langle T1\ BEGIN \rangle$
20	$\langle T2\ BEGIN \rangle$
30	$\langle T1,\ P1,\ a,\ A \rangle$
40	$\langle T2,\ P2,\ b,\ B \rangle$
50	$\langle T1\ COMMIT \rangle$
60	$\langle T2,\ P1,\ c,\ C \rangle$

ARIES Redo: mark each UPDATE as Redo or Ignore

Redo starts at min recLSN = 30. LSN 30 on P1 is skipped because pageLSN(P1)=35 already covers it. LSN 40 is redone since pageLSN(P2)=20<40. LSN 60 is redone since pageLSN(P1)=35<60.

Guided checkpoint

Use the same log as q23. Assume after analysis:

Dirty Page Table	Value
P1 recLSN	30
P2 recLSN	40

Page	pageLSN on disk
P1	35
P2	20

Section 09

ARIES Undo: mark each UPDATE as Undo or Ignore to Which property most strongly characterizes a strictly distributed database (vs tightly-coupled parallel DB)?

ARIES Undo: mark each UPDATE as Undo or Ignore

Undo affects loser transactions only. T1 is committed winner, so LSN 30 is ignored. T2 updates at LSN 60 and 40 are undone in reverse LSN order.

Guided checkpoint

Using q23, winner set is {T1}, loser set is {T2}.

Assuming one CLR per undone UPDATE in q25, how many CLRs are generated?

Two loser UPDATE records are undone (LSN 60 and 40), so two CLRs are generated.

Which property most strongly characterizes a strictly distributed database (vs tightly-coupled parallel DB)?

Distributed databases are typically loosely coupled and may involve autonomous, heterogeneous sites.

Section 10

Which are recognized shared-nothing scaling challenges? (Select all that apply) to What is the distributed DBMS mantra for data placement and execution?

Which are recognized shared-nothing scaling challenges? (Select all that apply)

B/C/D are practical shared-nothing limits at scale. A is mainly a shared-memory coherence issue.

Distributed join transfer cost: Node A has $R$ (10,000 tuples, 100 bytes each), Node B has $S$ (10 tuples, 100 bytes each). Compare (1) broadcasting $S$ to A vs (2) perfect 2-way hash shuffle of both relations (ignore final result transfer).

Path of Calculation: 1. Broadcast

S

10 \cdot 100 = 1,000

bytes. 2. 2-way hash shuffle: - Half of

R

from A to B:

5,000 \cdot 100 = 500,000

bytes. - Half of

S

from B to A:

5 \cdot 100 = 500

bytes. 3. Total shuffle =

500,000 + 500 = 500,500

bytes. Final answer: 1,000 bytes vs 500,500 bytes.

What is the distributed DBMS mantra for data placement and execution?

Data locality minimizes network transfer, which is often the dominant distributed execution cost.

Section 11

Even with high locality, what is the main risk of strong data skew in parallel execution? to Sparse index sizing: A data file has 10,000,000 tuples of 512 bytes each, block size 8192 bytes. Index entry size is 12 bytes. How many blocks for first-level sparse index?

Even with high locality, what is the main risk of strong data skew in parallel execution?

Skew causes uneven work distribution, reducing effective parallelism and extending query tail latency.

Which factors must distributed query optimizers model beyond centralized optimizers? (Select all that apply)

A/B/C are core distributed cost-model dimensions. D is not a defining distributed-specific optimizer concern.

Sparse index sizing: A data file has 10,000,000 tuples of 512 bytes each, block size 8192 bytes. Index entry size is 12 bytes. How many blocks for first-level sparse index?

Path of Calculation: 1. Data blocks = (10,000,000*512)/8192 = 625,000. 2. Sparse index has one entry per data block = 625,000 entries. 3. Entries per index block = floor(8192/12)=682. 4. Index blocks = ceil(625,000/682)=917. Final answer: 917.

Section 12

Using q33 results, how many blocks does a second-level sparse index require? to In extensible hashing, when must the directory global depth be increased?

Using q33 results, how many blocks does a second-level sparse index require?

Path of Calculation: 1. First-level index has 917 blocks. 2. Second-level sparse index needs one entry per first-level block = 917 entries. 3. 682 entries fit per block. 4. ceil(917/682)=2. Final answer: 2.

Which statement is true for a B+ tree index?

B+ trees keep search structure in internal nodes and data entries in leaves; linked leaves make range queries efficient.

In extensible hashing, when must the directory global depth be increased?

If a full bucket has local depth < global depth, split can be handled without directory doubling. Directory expansion is required when local depth == global depth.

Knowledge check

Turn understanding into recall.

The quiz now follows the same concepts in scored form. You can return to this lesson from the quiz whenever a gap appears.

Start the quiz →Back to course

What you will be able to explain

Which level of the memory hierarchy is typically the fastest to access? to A relation has 12,000 tuples. Each tuple has 108 bytes payload plus a 12-byte tuple header. Blocks are 1,024 bytes with 24-byte block header. How many blocks are required?

Which level of the memory hierarchy is typically the fastest to access?

Evaluate the following statements about locality:

A relation has 12,000 tuples. Each tuple has 108 bytes payload plus a 12-byte tuple header. Blocks are 1,024 bytes with 24-byte block header. How many blocks are required?

For OLTP-style point updates and single-tuple access, which layout is usually preferable? to A DBMS uses Steal + No-Force. Which recovery capabilities are required after crashes?

For OLTP-style point updates and single-tuple access, which layout is usually preferable?

Pointer swizzling/unswizzling is used to...

A DBMS uses Steal + No-Force. Which recovery capabilities are required after crashes?

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, nodes have private memory but access one common storage system. to Which task belongs to the parser (and not to preprocessing)?

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, nodes have private memory but access one common storage system.

Which is an extreme form of vertical partitioning?

Which task belongs to the parser (and not to preprocessing)?

Relational algebra equivalences: True or False? to For independent predicates, estimate ∣σA=10∧B<50(R)∣|\sigma_{A=10 \land B<50}(R)|∣σA=10∧B<50​(R)∣ with ∣R∣=18,000|R|=18,000∣R∣=18,000, V(R,A)=60V(R,A)=60V(R,A)=60, and selectivity(B<50)=0.25(B<50)=0.25(B<50)=0.25.

Relational algebra equivalences: True or False?

Estimate ∣σA=10(R)∣|\sigma_{A=10}(R)|∣σA=10​(R)∣ for ∣R∣=24,000|R|=24,000∣R∣=24,000 and V(R,A)=300V(R,A)=300V(R,A)=300 under uniformity.

For independent predicates, estimate ∣σA=10∧B<50(R)∣|\sigma_{A=10 \land B<50}(R)|∣σA=10∧B<50​(R)∣ with ∣R∣=18,000|R|=18,000∣R∣=18,000, V(R,A)=60V(R,A)=60V(R,A)=60, and selectivity(B<50)=0.25(B<50)=0.25(B<50)=0.25.

Which rule rewrites selection over cartesian product into an explicit join?

Match histogram types to their core characteristic.

Greedy join ordering on R,S,TR,S,TR,S,T: ∣R∣=1000|R|=1000∣R∣=1000, ∣S∣=20|S|=20∣S∣=20, ∣T∣=400|T|=400∣T∣=400, sel(R,S)=0.02sel(R,S)=0.02sel(R,S)=0.02, sel(S,T)=0.1sel(S,T)=0.1sel(S,T)=0.1, sel(R,T)=0.001sel(R,T)=0.001sel(R,T)=0.001. Which pair is selected first?

Estimate ∣R⋈S∣|R \bowtie S|∣R⋈S∣ with ∣R∣=8,000|R|=8,000∣R∣=8,000, ∣S∣=4,000|S|=4,000∣S∣=4,000, V(R,K)=500V(R,K)=500V(R,K)=500, V(S,K)=200V(S,K)=200V(S,K)=200. to Evaluate 2PL validity of a lock sequence.

Estimate ∣R⋈S∣|R \bowtie S|∣R⋈S∣ with ∣R∣=8,000|R|=8,000∣R∣=8,000, ∣S∣=4,000|S|=4,000∣S∣=4,000, V(R,K)=500V(R,K)=500V(R,K)=500, V(S,K)=200V(S,K)=200V(S,K)=200.

What is the defining 2PL rule?

Evaluate 2PL validity of a lock sequence.

Which lock mode is compatible with an existing SIX lock (same hierarchy node)? to In 2PC, what forces the coordinator to decide global ABORT?

Which lock mode is compatible with an existing SIX lock (same hierarchy node)?

Under Snapshot Isolation, T1T_1T1​ starts at ST=10ST=10ST=10, T2T_2T2​ commits an update on XXX at CT=20CT=20CT=20, and T1T_1T1​ reads XXX at time 25. Which version does T1T_1T1​ read?

In 2PC, what forces the coordinator to decide global ABORT?

Why is classic 2PC considered problematic under failures? to ARIES Redo: mark each UPDATE as Redo or Ignore

Why is classic 2PC considered problematic under failures?

Winners and losers at crash time

ARIES Redo: mark each UPDATE as Redo or Ignore

ARIES Undo: mark each UPDATE as Undo or Ignore to Which property most strongly characterizes a strictly distributed database (vs tightly-coupled parallel DB)?

ARIES Undo: mark each UPDATE as Undo or Ignore

Assuming one CLR per undone UPDATE in q25, how many CLRs are generated?

Which property most strongly characterizes a strictly distributed database (vs tightly-coupled parallel DB)?

Which are recognized shared-nothing scaling challenges? (Select all that apply) to What is the distributed DBMS mantra for data placement and execution?

Which are recognized shared-nothing scaling challenges? (Select all that apply)

Distributed join transfer cost: Node A has RRR (10,000 tuples, 100 bytes each), Node B has SSS (10 tuples, 100 bytes each). Compare (1) broadcasting SSS to A vs (2) perfect 2-way hash shuffle of both relations (ignore final result transfer).

What is the distributed DBMS mantra for data placement and execution?

Even with high locality, what is the main risk of strong data skew in parallel execution? to Sparse index sizing: A data file has 10,000,000 tuples of 512 bytes each, block size 8192 bytes. Index entry size is 12 bytes. How many blocks for first-level sparse index?

Even with high locality, what is the main risk of strong data skew in parallel execution?

Which factors must distributed query optimizers model beyond centralized optimizers? (Select all that apply)

Sparse index sizing: A data file has 10,000,000 tuples of 512 bytes each, block size 8192 bytes. Index entry size is 12 bytes. How many blocks for first-level sparse index?

Using q33 results, how many blocks does a second-level sparse index require? to In extensible hashing, when must the directory global depth be increased?

Using q33 results, how many blocks does a second-level sparse index require?

Which statement is true for a B+ tree index?

In extensible hashing, when must the directory global depth be increased?

Turn understanding into recall.

Relational algebra equivalences: True or False? to For independent predicates, estimate $|\sigma_{A=10 \land B<50}(R)|$ with $|R|=18,000$ , $V(R,A)=60$ , and selectivity $(B<50)=0.25$ .

Estimate $|\sigma_{A=10}(R)|$ for $|R|=24,000$ and $V(R,A)=300$ under uniformity.

For independent predicates, estimate $|\sigma_{A=10 \land B<50}(R)|$ with $|R|=18,000$ , $V(R,A)=60$ , and selectivity $(B<50)=0.25$ .

Greedy join ordering on $R,S,T$ : $|R|=1000$ , $|S|=20$ , $|T|=400$ , $sel(R,S)=0.02$ , $sel(S,T)=0.1$ , $sel(R,T)=0.001$ . Which pair is selected first?

Estimate $|R \bowtie S|$ with $|R|=8,000$ , $|S|=4,000$ , $V(R,K)=500$ , $V(S,K)=200$ . to Evaluate 2PL validity of a lock sequence.

Estimate $|R \bowtie S|$ with $|R|=8,000$ , $|S|=4,000$ , $V(R,K)=500$ , $V(S,K)=200$ .

Under Snapshot Isolation, $T_1$ starts at $ST=10$ , $T_2$ commits an update on $X$ at $CT=20$ , and $T_1$ reads $X$ at time 25. Which version does $T_1$ read?

Distributed join transfer cost: Node A has $R$ (10,000 tuples, 100 bytes each), Node B has $S$ (10 tuples, 100 bytes each). Compare (1) broadcasting $S$ to A vs (2) perfect 2-way hash shuffle of both relations (ignore final result transfer).