Quizmaster

Learning objectives

What you will be able to explain

Who controls which cache layer in the lecture model?
Which statement matches the locality definitions?
What is the disk-latency decomposition used in the storage lecture?
Average read latency in the worked disk example
Elevator setup: fixed per-request time without movement distance
Which page statement is correct?

Section 01

Who controls which cache layer in the lecture model? to What is the disk-latency decomposition used in the storage lecture?

Who controls which cache layer in the lecture model?

The slide distinguishes hardware-controlled CPU caches, OS-controlled file-system cache, and DBMS-controlled buffer cache.

Guided checkpoint

Choose the correct mapping.

Source: 01_Storage.pdf, page 9

Which statement matches the locality definitions?

Temporal locality is reuse over time, while spatial locality is use of nearby data items.

Source: 01_Storage.pdf, page 10

What is the disk-latency decomposition used in the storage lecture?

The access-characteristics slide gives exactly this three-part decomposition.

Source: 01_Storage.pdf, page 39

Section 02

Average read latency in the worked disk example to Which page statement is correct?

Average read latency in the worked disk example

The example sums the three components: 6.46 + 4.17 + 0.13 = 10.76 ms.

Guided checkpoint

Using the slide values seek=6.46 ms, rotational=4.17 ms, transfer=0.13 ms, what is total average latency?

Source: 01_Storage.pdf, page 43

Elevator setup: fixed per-request time without movement distance

Fixed part is 1.00 + 4.17 + 0.13 = 5.30 ms. This is directly from the elevator-algorithm assumptions.

Guided checkpoint

Given seek time = 1 ms + (#tracks/4000) ms, average rotational latency = 4.17 ms, transfer time = 0.13 ms, compute the fixed time excluding the #tracks/4000 term.

Source: 01_Storage.pdf, page 58

Which page statement is correct?

The slide defines fixed-size pages with header/data sections and unique PageID.

Source: 02_Data_Layouts.pdf, page 10

Section 03

In slotted-page layout, how is tupleID represented? to How is PAX characterized in the lecture?

In slotted-page layout, how is tupleID represented?

The slotted-page structure slide shows tupleID as pageID plus slotID.

Source: 02_Data_Layouts.pdf, page 11

What is a key downside of pure column layout (DSM)?

The DSM slide explicitly states that column layout requires tuple reconstruction.

Source: 02_Data_Layouts.pdf, page 31

How is PAX characterized in the lecture?

PAX combines NSM across pages with DSM organization inside a page.

Source: 02_Data_Layouts.pdf, page 43

Section 04

Which NSM/DSM/PAX comparison row is correct? to How does the lecture classify CLOCK replacement?

Which NSM/DSM/PAX comparison row is correct?

The comparison table lists inter-record spatial locality as No/Yes/Yes for NSM/DSM/PAX.

Source: 02_Data_Layouts.pdf, page 45

Which buffer granularity is commonly used in DBMS buffering?

The granularity slide highlights blocks/pages as the common practical unit.

Source: 03_Caching.pdf, page 16

How does the lecture classify CLOCK replacement?

CLOCK is presented as a commonly implemented, efficient approximation to LRU.

Source: 03_Caching.pdf, pages 20 and 25

Section 05

Which LRU-vs-FIFO statement is correct? to In PostgreSQL buffer-manager architecture, what is the buffer table?

Which LRU-vs-FIFO statement is correct?

The slide contrasts FIFO simplicity with LRU's recency tracking and associated maintenance cost.

Source: 03_Caching.pdf, page 22

In CLOCK victim search, what happens on reference bit = 1?

CLOCK gives a second chance by clearing 1 to 0 and continuing; eviction occurs at bit 0.

Source: 03_Caching.pdf, page 26

In PostgreSQL buffer-manager architecture, what is the buffer table?

The implementation slide describes the buffer table as a hash table for fast page lookup by tag/content id.

Source: 03_Caching.pdf, page 32

Section 06

When is an index usually preferable to a scan? to Which statement best matches sparse indexes in the lecture?

When is an index usually preferable to a scan?

The slide shows index-vs-scan depends on result size/selectivity; few qualifying tuples favor indexes.

Source: 04_Indexing 1.pdf, page 8

What defines a dense index?

Dense index means one index entry per tuple/record.

Source: 04_Indexing 1.pdf, pages 12 and 14

Which statement best matches sparse indexes in the lecture?

Sparse indexes are strict subsets, often one entry per block, and useful for sorted records.

Source: 04_Indexing 1.pdf, page 16

Section 07

What is true for a secondary index on sequential files? to Which structural B-tree property is emphasized?

What is true for a secondary index on sequential files?

The secondary-index slide states it does not determine data order and can only be dense.

Source: 04_Indexing 1.pdf, page 23

During data updates, which index-maintenance statement is correct?

The data-manipulation slide makes this dense-vs-sparse update distinction explicit.

Source: 04_Indexing 1.pdf, page 24

Which structural B-tree property is emphasized?

B-trees are described as always balanced with equal root-to-leaf path length.

Source: 05_Indexing 2.pdf, page 12

Section 08

How are B-tree nodes sized relative to capacity? to If deletion causes too few keys in a B-tree node, what is the standard fix order?

How are B-tree nodes sized relative to capacity?

The B-tree design slide states blocks are between half used and fully full.

Source: 05_Indexing 2.pdf, page 12

What can happen when insertion reaches a full root?

Insertion may propagate splits up to root; splitting root creates a new root and raises height.

Source: 05_Indexing 2.pdf, page 29

If deletion causes too few keys in a B-tree node, what is the standard fix order?

The delete slide describes steal-first when possible, otherwise merge with recursive maintenance.

Source: 05_Indexing 2.pdf, page 35

Section 09

What is the key bulk-loading idea for large B-tree construction? to Which collision-handling families are explicitly listed?

What is the key bulk-loading idea for large B-tree construction?

Bulk loading is motivated as sorting key-pointer pairs and exploiting order, rather than naive iterative insertion.

Source: 05_Indexing 2.pdf, page 47

Hash-table indexing: what range does h(K) map to?

The basic principle defines hash output as integer bucket id between 0 and B-1.

Source: 06_Indexing 3_hash_tables.pdf, page 8

Which collision-handling families are explicitly listed?

The collision slide names separate chaining and open addressing as core approaches.

Source: 06_Indexing 3_hash_tables.pdf, page 9

Section 10

Why are dynamic resizing mechanisms needed in hash tables? to Which statement distinguishes linear hashing from extensible hashing in the slides?

Why are dynamic resizing mechanisms needed in hash tables?

The dynamic-resizing slide motivates this exactly and notes full-table rehash as computationally expensive.

Source: 06_Indexing 3_hash_tables.pdf, page 11

Which dynamic hash-table variants are covered in this lecture?

The static-vs-dynamic overview explicitly lists extensible and linear hashing.

Source: 06_Indexing 3_hash_tables.pdf, page 20

Which statement distinguishes linear hashing from extensible hashing in the slides?

The linear-hash slide emphasizes linear bucket growth and explicitly states no bucket directory compared to extensible hashing.

Source: 06_Indexing 3_hash_tables.pdf, page 31

Section 11

kNN strategy in multidimensional space: which sequence matches the slide? to Bitmap index definition: what does one bitmap vector represent?

kNN strategy in multidimensional space: which sequence matches the slide?

The kNN slide gives this two-phase iterative range-query strategy in multidimensional space.

Source: 07_1_Multidimensional Indexing.pdf, page 56

Which set contains only index families shown on the multidimensional overview slide?

This index-family list appears directly on the overview slide.

Source: 07_1_Multidimensional Indexing.pdf, page 63

Bitmap index definition: what does one bitmap vector represent?

The lecture defines bitmap indexes as one-dimensional vectors per value indicating whether each row has that value.

Source: 07_1_Multidimensional Indexing.pdf, page 92

Section 12

How are partial-match queries executed with bitmap indexes (as shown)? to What is the core Grid File idea (part 2 slides)?

How are partial-match queries executed with bitmap indexes (as shown)?

The query slide states partial match uses bitmap AND then retrieval where result bits are 1.

Source: 07_1_Multidimensional Indexing.pdf, page 94

According to the bitmap-query slide, which operation is associated with point queries?

The slide explicitly maps point queries to counting bits followed by block retrieval.

Source: 07_1_Multidimensional Indexing.pdf, page 94

What is the core Grid File idea (part 2 slides)?

Grid files are introduced exactly via per-dimension stripes overlaid as a multidimensional grid.

Source: 07_2_multidimensional indexing_pt2.pdf, page 2

Section 13

Given a query point in a grid file, what does the search procedure do? to R-tree point query: how are overlapping subregions handled?

Given a query point in a grid file, what does the search procedure do?

The search slide gives this per-dimension position lookup and bucket determination, with overflow blocks permitted.

Source: 07_2_multidimensional indexing_pt2.pdf, page 3

Which statement about kd-trees is correct?

The kd-tree definition explicitly states BST generalization and alternating attributes through levels.

Source: 07_2_multidimensional indexing_pt2.pdf, page 20

R-tree point query: how are overlapping subregions handled?

The operations slide states that containment in multiple subregions requires descent through all overlaps.

Source: 07_2_multidimensional indexing_pt2.pdf, page 40

Section 14

Nearest-neighbor simple strategy in these slides starts by... to The lecture separates processing models into which three dimensions?

Nearest-neighbor simple strategy in these slides starts by...

The nearest-neighbor slide presents this range-search conversion and refinement workflow.

Source: 07_2_multidimensional indexing_pt2.pdf, page 49

How are logical and physical operators related?

The basic execution slide explicitly gives hash join vs sort-merge join as alternative physical implementations.

Source: 08_Query Execution.pdf, page 5

The lecture separates processing models into which three dimensions?

These three axes are listed together on the processing-model slide.

Source: 08_Query Execution.pdf, page 10

Section 15

Iterator (Volcano) model: which function returns the next tuple or NotFound? to What is morsel-driven parallelism in this lecture?

Iterator (Volcano) model: which function returns the next tuple or NotFound?

The iterator-model slide defines Open, GetNext, Close; GetNext fetches/computes next record and returns NotFound at end.

Source: 08_Query Execution.pdf, page 14

What tradeoff is highlighted for the fully materialized (operator-at-a-time) model?

The slide calls materialization a two-edged sword: code/cache benefits versus heavy intermediate materialization costs.

Source: 08_Query Execution.pdf, page 22

What is morsel-driven parallelism in this lecture?

The morsel-driven slide describes chunked work units dynamically assigned via task queue at runtime.

Source: 08_Query Execution.pdf, page 62

Section 16

Which task belongs to the parser stage? to How is output cardinality estimated from selectivity?

Which task belongs to the parser stage?

The parser slide assigns parse-tree conversion and syntax correctness checks to parsing.

Source: 09_Query_Optimization.pdf, page 8

Which task belongs to preprocessing?

Preprocessing is described as semantic checking, including relation, attribute, and type correctness.

Source: 09_Query_Optimization.pdf, page 11

How is output cardinality estimated from selectivity?

The slide defines output cardinality as input cardinality multiplied by selectivity (filter factor).

Source: 09_Query_Optimization.pdf, page 26

Section 17

For selection A != c, which common heuristic is shown? to Disjunction example from page 32: better estimate

For selection A != c, which common heuristic is shown?

The selection heuristics slide gives this inequality estimate under uniformity assumptions.

Source: 09_Query_Optimization.pdf, page 28

How is conjunction selectivity estimated in the basic heuristic model?

The lecture states conjunction selectivity is multiplied under an explicit and strong independence assumption.

Source: 09_Query_Optimization.pdf, page 29

Disjunction example from page 32: better estimate

Using n * (1 - (1 - m1/n)(1 - m2/n)) gives 3466 in the worked example.

Guided checkpoint

In the slide example with n=10000, m1=200 and m2=3333 for a disjunction, what is the better estimate using the independence-based formula?

Source: 09_Query_Optimization.pdf, page 32

Section 18

Join-cardinality worked example from the slides to What is the Selinger-style enhancement over plain dynamic programming?

Join-cardinality worked example from the slides

The slide computes T(R join S join U) = 400000 and uses value-set preservation for non-join attributes in the derivation.

Guided checkpoint

For the example R(A,B) join S(B,C) join U(C,D) with T(R)=1000, T(S)=2000, T(U)=5000, V(R,B)=20, V(S,B)=50, V(S,C)=100, V(U,C)=500, what total cardinality is shown?

Source: 09_Query_Optimization.pdf, page 35

Unknown selectivity case: derive cardinality bounds

From page 28: sel(b!=37)=19/20=0.95. From disjunction model: sel=0.95+p-0.95p. So T(S)=420000*(0.95+p-0.95p)=399000+21000p. With p in [0,1], bounds are [399000,420000]. Sources: 09_Query_Optimization.pdf, pages 28, 31, 32.

Guided checkpoint

Assume T(R)=420000 and V(R,b)=20. For sigma_(b!=37 OR d<80)(R), let p=sel(d<80) be unknown. Using slide heuristics and OR independence form, compute lower and upper bounds for T(S).

What is the Selinger-style enhancement over plain dynamic programming?

Selinger-style optimization extends DP by retaining interesting orders beyond just the minimal-cost partial plan.

Source: 09_Query_Optimization.pdf, page 49

Section 19

Serializable schedule means... to What does basic 2PL guarantee, and what can still happen?

Serializable schedule means...

The serializability definition is equivalence of results to a serial schedule, not prohibition of interleaving.

Source: 10_Concurrency Control.pdf, page 24

When is a schedule conflict-serializable?

The lecture states conflict-serializable iff the precedence graph has no cycles.

Source: 10_Concurrency Control.pdf, page 36

What does basic 2PL guarantee, and what can still happen?

The 2PL slide explicitly says all 2PL schedules are serializable, while deadlocks may still occur.

Source: 10_Concurrency Control.pdf, page 47

Section 20

Strict 2PL differs from basic 2PL mainly by... to READ COMMITTED permits which phenomena according to the slide?

Strict 2PL differs from basic 2PL mainly by...

Strict 2PL keeps exclusive locks until commit/abort acknowledgement and ensures recoverable schedules.

Source: 10_Concurrency Control.pdf, page 53

Which intention-lock compatibility fact is shown in the example?

The compatibility matrix example explicitly states IS and IX are compatible.

Source: 10_Concurrency Control.pdf, page 58

READ COMMITTED permits which phenomena according to the slide?

The isolation-level slide says READ COMMITTED disallows dirty reads, but allows fuzzy reads and phantoms.

Source: 10_Concurrency Control.pdf, page 70

Section 21

Steal / No-Steal and Force / No-Force: which pairing is correct? to Write-ahead logging (WAL): which rule is essential?

Steal / No-Steal and Force / No-Force: which pairing is correct?

Policy definitions: No-Steal blocks uncommitted dirty-page write-out; Force requires transaction updates reflected on disk at commit. Sources: 11_Recovery.pdf, pages 7 and 8.

Which recovery-method pairing is shown in the overview?

The recovery overview slide explicitly maps these policy combinations to shadow paging and WAL.

Source: 11_Recovery.pdf, page 10

Write-ahead logging (WAL): which rule is essential?

WAL enforces log-before-data for atomicity; commit also requires transaction log records to be durable.

Source: 11_Recovery.pdf, page 16

Section 22

What is the three-pass recovery order? to How is speedup defined in the parallel DB lecture?

What is the three-pass recovery order?

The lecture sequence is Analysis pass, then Redo pass, then Undo pass.

Source: 11_Recovery.pdf, page 24

Undo phase details: which statement matches the slide?

Undo reads log backwards for loser transactions and may produce new log records while undoing actions.

Source: 11_Recovery.pdf, page 28

How is speedup defined in the parallel DB lecture?

Speedup is defined as sequential runtime divided by parallel runtime on p nodes; linear speedup is ideal.

Source: 12_Parallel_DBs_and_Big_data.pdf, page 7

Section 23

What characterizes a homogeneous distributed database? to Replication vs fragmentation: which statement is correct?

What characterizes a homogeneous distributed database?

The architecture slide defines homogeneous systems exactly this way.

Source: 12_Parallel_DBs_and_Big_data.pdf, page 15

Which mapping of query parallelism to workload focus is correct?

The lecture explicitly maps inter-query parallelism to transactional workloads and intra-query parallelism to analytical workloads.

Source: 12_Parallel_DBs_and_Big_data.pdf, page 24

Replication vs fragmentation: which statement is correct?

The distribution-challenges slide defines both and explicitly states they can be combined.

Source: 12_Parallel_DBs_and_Big_data.pdf, page 31

Section 24

Horizontal vs vertical partitioning: pick the correct statement to I/O operations on bitmap indexes: size and block footprint

Horizontal vs vertical partitioning: pick the correct statement

Horizontal partitioning uses tuple slices with each tuple in exactly one partition; vertical partitioning uses attribute slices and requires key-based reconstruction. Sources: 12_Parallel_DBs_and_Big_data.pdf, pages 34 and 36.

Match all ACID properties to their definitions

Correct mapping: Atomicity -> all-or-nothing execution of a transaction. Consistency -> a transaction maps a consistent DB state to another consistent state (integrity constraints preserved). Isolation -> each transaction executes as if it were alone in the system. Durability -> effects of committed transactions remain in the DB even after failures. Source: 10_Concurrency Control.pdf, page 8.

Guided checkpoint

Match each ACID property to the correct definition from the lecture.

I/O operations on bitmap indexes: size and block footprint

Step 1 (bitmap size in bits): each distinct value gets one bitmap, and each bitmap has one bit per tuple. So size(attribute) = N * V(attribute), with N=200,000,000 tuples. - storeID: 200,000,000 * 1000 = 200,000,000,000 bits - productID: 200,000,000 * 50 = 10,000,000,000 bits - timestamp: 200,000,000 * 150,000,000 = 30,000,000,000,000,000 bits = 3 * 10^16 bits Step 2 (bits per block): 4096 bytes * 8 = 32,768 bits/block. Step 3 (blocks for one bitmap): ceil(200,000,000 / 32,768) = ceil(6103.515625) = 6104 blocks. (ceil is required because partially filled bitmap blocks still occupy a full block.) Step 4 (total blocks per attribute; bitmaps do not share blocks): - storeID: 6104 * 1000 = 6,104,000 blocks - productID: 6104 * 50 = 305,200 blocks - timestamp: 6104 * 150,000,000 = 915,600,000,000 blocks This follows the lecture bitmap-index model (bit vector per value and bitmap query processing). Sources: 07_1_Multidimensional Indexing.pdf, pages 92 and 94.

Guided checkpoint

Assume a fact table with 200,000,000 tuples and bitmap indexes on storeID (1000 distinct values), productID (50 distinct values), and timestamp (150,000,000 distinct values). Page size is 4096 bytes, and two bitmaps cannot share a block.

Compute: (1) total bitmap size per attribute in bits, and (2) total number of 4KB blocks per attribute.

Section 25

Compressed bitmap index size (RLE) for clustered productID

For RLE, each bitmap stores two integer arrays: values[] and runLengths[], with 4 bytes per int. Given structure: - 48 middle bitmaps, each with 3 runs -> 3 ints in values[] and 3 ints in runLengths[] - 2 endpoint bitmaps, each with 2 runs -> 2 ints in values[] and 2 ints in runLengths[] Values-array bytes: - Middle bitmaps: 48 * 3 * 4 = 576 bytes - Endpoint bitmaps: 2 * 2 * 4 = 16 bytes - Total values bytes = 592 bytes RunLength-array bytes: same structure -> 592 bytes. Total compressed size = 592 + 592 = 1184 bytes. (Equivalent compact form: 2 * ((48*3 + 2*2) * 4) = 1184.)

Guided checkpoint

Assume the table is clustered on productID and bitmap runs are encoded with two int arrays per bitmap: values[] and runLengths[], where each int is 4 bytes.

Given 48 middle bitmaps with 3 ints in each array and 2 endpoint bitmaps with 2 ints in each array, compute total compressed size in bytes.

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