Quizmaster

Learning objectives

What you will be able to explain

Which memory hierarchy level typically offers the largest capacity in a DBMS deployment?
Temporal and spatial locality: True or False?
A relation has 9,600 tuples. Tuple payload is 116 bytes and tuple header is 12 bytes. Block size is 2,048 bytes with 48-byte block header. How many blocks are required?
For analytical scans touching only a few attributes over many rows, which layout is generally advantageous?
Which policy combination is conceptually simplest for recovery but usually slowest in practice?
In a shared-nothing architecture, what does each node own privately?

Section 01

Which memory hierarchy level typically offers the largest capacity in a DBMS deployment? to A relation has 9,600 tuples. Tuple payload is 116 bytes and tuple header is 12 bytes. Block size is 2,048 bytes with 48-byte block header. How many blocks are required?

Which memory hierarchy level typically offers the largest capacity in a DBMS deployment?

Archive/tertiary storage provides the highest capacity, while registers/cache are much smaller but faster.

Temporal and spatial locality: True or False?

A/B/D are true locality principles. C is false because block/page transfers exploit spatial locality heavily.

A relation has 9,600 tuples. Tuple payload is 116 bytes and tuple header is 12 bytes. Block size is 2,048 bytes with 48-byte block header. How many blocks are required?

Path of Calculation: 1. Tuple size = 116 + 12 = 128 bytes. 2. Usable bytes/block = 2048 - 48 = 2000 bytes. 3. Tuples per block = floor(2000/128) = 15. 4. Blocks = ceil(9600/15) = 640. Final answer: 640.

Section 02

For analytical scans touching only a few attributes over many rows, which layout is generally advantageous? to In a shared-nothing architecture, what does each node own privately?

For analytical scans touching only a few attributes over many rows, which layout is generally advantageous?

Column stores reduce unnecessary I/O for analytical queries that access only a subset of attributes.

Which policy combination is conceptually simplest for recovery but usually slowest in practice?

No-Steal + Force avoids both UNDO and REDO needs conceptually, but forces expensive writes and restrictive buffer behavior.

In a shared-nothing architecture, what does each node own privately?

Shared-nothing means nodes do not share memory or disk; each node owns its compute and storage partition.

Section 03

In a [Select: Round robin / Hash / Range] partitioning scheme, tuples are assigned based on a hash function over a partitioning key. to Which operator is primarily responsible for filtering rows in relational algebra?

In a [Select: Round robin / Hash / Range] partitioning scheme, tuples are assigned based on a hash function over a partitioning key.

Hash partitioning uses a hash of the partitioning key to map tuples to partitions.

What is a key downside of full replication?

Replicas must be kept consistent, so updates become more expensive due to synchronization and propagation.

Which operator is primarily responsible for filtering rows in relational algebra?

Selection (

\sigma

) keeps rows satisfying a predicate; projection (

\pi

) keeps columns.

Section 04

Which processing model tends to materialize the largest intermediate results? to For $|R|=9,000$ , $V(R,A)=45$ , and independent selectivity $(B<20)=0.2$ , estimate $|\sigma_{A=10 \land B<20}(R)|$ .

Which processing model tends to materialize the largest intermediate results?

Operator-at-a-time commonly materializes full intermediate relations between operators.

Estimate $|\sigma_{A=7}(R)|$ for $|R|=30,000$ and $V(R,A)=600$ assuming uniform distribution.

Path of Calculation: 1. Equality selectivity is

1/V(R,A)=1/600

. 2. Result size =

30000/600 = 50

. Final answer: 50.

For $|R|=9,000$ , $V(R,A)=45$ , and independent selectivity $(B<20)=0.2$ , estimate $|\sigma_{A=10 \land B<20}(R)|$ .

Path of Calculation: 1. Selectivity

(A=10)=1/45

. 2. Combined selectivity

=(1/45)\cdot0.2=1/225

. 3. Cardinality

=9000/225=40

. Final answer: 40.

Section 05

Which rewrite is correct for converting selection over product into join? to Given $|R|=1200$ , $|S|=50$ , $|T|=300$ and selectivities $sel(R,S)=0.01$ , $sel(S,T)=0.05$ , $sel(R,T)=0.002$ , which pair is chosen first by greedy (minimum first join cardinality)?

Which rewrite is correct for converting selection over product into join?

Join introduction identifies equi-join predicates over cartesian product and replaces them with an explicit join.

Histogram matching

Equi-width fixes range boundaries by size; equi-depth adapts ranges to keep tuple counts similar.

Given $|R|=1200$ , $|S|=50$ , $|T|=300$ and selectivities $sel(R,S)=0.01$ , $sel(S,T)=0.05$ , $sel(R,T)=0.002$ , which pair is chosen first by greedy (minimum first join cardinality)?

Estimates: RS=1200*50*0.01=600, ST=50*300*0.05=750, RT=1200*300*0.002=720. Greedy picks the smallest first intermediate, so

\{R,S\}

is chosen.

Section 06

For relation sizes $|R|=6000$ , $|S|=9000$ and join attribute distinct counts $V(R,K)=300$ , $V(S,K)=500$ , estimate $|R\bowtie S|$ . to Transaction $T_1$ holds IX on table $R$ . Transaction $T_2$ requests S on table $R$ . Should it be granted?

For relation sizes $|R|=6000$ , $|S|=9000$ and join attribute distinct counts $V(R,K)=300$ , $V(S,K)=500$ , estimate $|R\bowtie S|$ .

Use

|R\bowtie S|\approx\frac{|R||S|}{\max(V(R,K),V(S,K))}=\frac{6000\cdot9000}{500}=108,000

2PL validation

After the first unlock, transaction is in shrinking phase and cannot acquire new locks. So this violates 2PL.

Guided checkpoint

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

Transaction $T_1$ holds IX on table $R$ . Transaction $T_2$ requests S on table $R$ . Should it be granted?

IX and S are incompatible at the same hierarchy node in standard multiple-granularity locking.

Section 07

Under Snapshot Isolation, which version does a transaction read? to Which failure mode is specific to distributed systems and not a typical single-node failure class?

Under Snapshot Isolation, which version does a transaction read?

SI gives each transaction a stable start-time snapshot, so reads are from start timestamp visibility.

In 2PC, when does the coordinator choose COMMIT?

2PC requires unanimous YES to preserve atomic commitment.

Which failure mode is specific to distributed systems and not a typical single-node failure class?

Network partition splits connectivity between healthy nodes, a distributed-specific failure mode.

Section 08

Crash log classification to ARIES undo decisions

Crash log classification

T2 has COMMIT record before crash and is winner. T1 has no commit/abort and is loser.

Guided checkpoint

LSN	Log Record
100	$\langle T1\ BEGIN\rangle$
110	$\langle T2\ BEGIN\rangle$
120	$\langle T1, P3, 10, 20\rangle$
130	$\langle T2, P5, 5, 7\rangle$
140	$\langle T2\ COMMIT\rangle$

ARIES redo decisions

Redo starts at min recLSN=120. LSN120 on P3 is ignored because pageLSN 125 >=120. LSN130 on P5 is redone because pageLSN 100 <130.

Guided checkpoint

Use q22 log with DPT and pageLSN state below.

Dirty Page Table	Value
P3 recLSN	120
P5 recLSN	130

Page	pageLSN
P3	125
P5	100

ARIES undo decisions

Undo pass reverts only loser updates. T1 is loser -> undo LSN120. T2 is winner -> ignore LSN130.

Guided checkpoint

From q22, losers={T1}, winners={T2}.

Section 09

If each undone UPDATE in q24 generates one CLR, how many CLRs are produced? to What best describes the 'Data Locality first' principle?

If each undone UPDATE in q24 generates one CLR, how many CLRs are produced?

Only one loser UPDATE (LSN120) is undone, so exactly one CLR is generated.

Distributed query plans usually extend physical algebra with which extra operators?

send/receive explicitly model inter-site data movement, a core distributed optimization concern.

What best describes the 'Data Locality first' principle?

Network transfer is expensive; locality-aware plans reduce shuffle and improve scalability.

Section 10

Which factors are distributed query optimizer concerns beyond centralized optimization? (Select all that apply) to For the q29 scenario, how many second-level sparse index blocks are required?

Which factors are distributed query optimizer concerns beyond centralized optimization? (Select all that apply)

Distributed optimization must account for communication and topology variability in addition to local compute costs.

Sparse index sizing: 8,000,000 tuples, tuple size 256 bytes, block size 4096 bytes, index entry size 16 bytes. How many first-level sparse index blocks?

Path of Calculation: 1. Data blocks = (8,000,000*256)/4096 = 500,000. 2. Sparse index entries = 500,000. 3. Entries/index block = floor(4096/16)=256. 4. Index blocks = ceil(500,000/256)=1,954. Final answer: 1,954.

For the q29 scenario, how many second-level sparse index blocks are required?

With first-level blocks = 1,954, second-level entries = 1,954. 256 entries/block => ceil(1954/256)=8 blocks.

Section 11

In extensible hashing, if an overflowing bucket has local depth < global depth, what happens first? to Which statement about B+ trees is correct?

In extensible hashing, if an overflowing bucket has local depth < global depth, what happens first?

When local depth is smaller, split can be handled by redistributing directory pointers without global directory doubling.

Which statement about B+ trees is correct?

Linked leaves provide ordered traversal for ranges, while internal nodes guide search by separator keys.

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 memory hierarchy level typically offers the largest capacity in a DBMS deployment? to A relation has 9,600 tuples. Tuple payload is 116 bytes and tuple header is 12 bytes. Block size is 2,048 bytes with 48-byte block header. How many blocks are required?

Which memory hierarchy level typically offers the largest capacity in a DBMS deployment?

Temporal and spatial locality: True or False?

A relation has 9,600 tuples. Tuple payload is 116 bytes and tuple header is 12 bytes. Block size is 2,048 bytes with 48-byte block header. How many blocks are required?

For analytical scans touching only a few attributes over many rows, which layout is generally advantageous? to In a shared-nothing architecture, what does each node own privately?

For analytical scans touching only a few attributes over many rows, which layout is generally advantageous?

Which policy combination is conceptually simplest for recovery but usually slowest in practice?

In a shared-nothing architecture, what does each node own privately?

In a [Select: Round robin / Hash / Range] partitioning scheme, tuples are assigned based on a hash function over a partitioning key. to Which operator is primarily responsible for filtering rows in relational algebra?

In a [Select: Round robin / Hash / Range] partitioning scheme, tuples are assigned based on a hash function over a partitioning key.

What is a key downside of full replication?

Which operator is primarily responsible for filtering rows in relational algebra?

Which processing model tends to materialize the largest intermediate results? to For ∣R∣=9,000|R|=9,000∣R∣=9,000, V(R,A)=45V(R,A)=45V(R,A)=45, and independent selectivity(B<20)=0.2(B<20)=0.2(B<20)=0.2, estimate ∣σA=10∧B<20(R)∣|\sigma_{A=10 \land B<20}(R)|∣σA=10∧B<20​(R)∣.

Which processing model tends to materialize the largest intermediate results?

Estimate ∣σA=7(R)∣|\sigma_{A=7}(R)|∣σA=7​(R)∣ for ∣R∣=30,000|R|=30,000∣R∣=30,000 and V(R,A)=600V(R,A)=600V(R,A)=600 assuming uniform distribution.

For ∣R∣=9,000|R|=9,000∣R∣=9,000, V(R,A)=45V(R,A)=45V(R,A)=45, and independent selectivity(B<20)=0.2(B<20)=0.2(B<20)=0.2, estimate ∣σA=10∧B<20(R)∣|\sigma_{A=10 \land B<20}(R)|∣σA=10∧B<20​(R)∣.

Which rewrite is correct for converting selection over product into join?

Histogram matching

For relation sizes ∣R∣=6000|R|=6000∣R∣=6000, ∣S∣=9000|S|=9000∣S∣=9000 and join attribute distinct counts V(R,K)=300V(R,K)=300V(R,K)=300, V(S,K)=500V(S,K)=500V(S,K)=500, estimate ∣R⋈S∣|R\bowtie S|∣R⋈S∣.

2PL validation

Transaction T1T_1T1​ holds IX on table RRR. Transaction T2T_2T2​ requests S on table RRR. Should it be granted?

Under Snapshot Isolation, which version does a transaction read? to Which failure mode is specific to distributed systems and not a typical single-node failure class?

Under Snapshot Isolation, which version does a transaction read?

In 2PC, when does the coordinator choose COMMIT?

Which failure mode is specific to distributed systems and not a typical single-node failure class?

Crash log classification to ARIES undo decisions

Crash log classification

ARIES redo decisions

ARIES undo decisions

If each undone UPDATE in q24 generates one CLR, how many CLRs are produced? to What best describes the 'Data Locality first' principle?

If each undone UPDATE in q24 generates one CLR, how many CLRs are produced?

Distributed query plans usually extend physical algebra with which extra operators?

What best describes the 'Data Locality first' principle?

Which factors are distributed query optimizer concerns beyond centralized optimization? (Select all that apply) to For the q29 scenario, how many second-level sparse index blocks are required?

Which factors are distributed query optimizer concerns beyond centralized optimization? (Select all that apply)

Sparse index sizing: 8,000,000 tuples, tuple size 256 bytes, block size 4096 bytes, index entry size 16 bytes. How many first-level sparse index blocks?

For the q29 scenario, how many second-level sparse index blocks are required?

In extensible hashing, if an overflowing bucket has local depth < global depth, what happens first? to Which statement about B+ trees is correct?

In extensible hashing, if an overflowing bucket has local depth < global depth, what happens first?

Which statement about B+ trees is correct?

Turn understanding into recall.

Which processing model tends to materialize the largest intermediate results? to For $|R|=9,000$ , $V(R,A)=45$ , and independent selectivity $(B<20)=0.2$ , estimate $|\sigma_{A=10 \land B<20}(R)|$ .

Estimate $|\sigma_{A=7}(R)|$ for $|R|=30,000$ and $V(R,A)=600$ assuming uniform distribution.

For $|R|=9,000$ , $V(R,A)=45$ , and independent selectivity $(B<20)=0.2$ , estimate $|\sigma_{A=10 \land B<20}(R)|$ .

For relation sizes $|R|=6000$ , $|S|=9000$ and join attribute distinct counts $V(R,K)=300$ , $V(S,K)=500$ , estimate $|R\bowtie S|$ .

Transaction $T_1$ holds IX on table $R$ . Transaction $T_2$ requests S on table $R$ . Should it be granted?