Learning objectives
What you will be able to explain
- True or False: Caching moves important data from lower tiers to higher tiers.
- True or False: Spatial locality means recently used data are likely to be reused soon.
- True or False: Temporal locality means data close to each other are likely to be used together.
- True or False: The cache-hit-ratio formula shown is nb_hits / (nb_hits + nb_misses).
- True or False: In x86, a 32-bit address space can represent 2^32 addresses.
- True or False: Virtual memory is always smaller than physical memory.
Section 01
True or False: Caching moves important data from lower tiers to higher tiers. to True or False: Temporal locality means data close to each other are likely to be used together.
01
True or False: Caching moves important data from lower tiers to higher tiers.
Source: 01_Storage.pdf, page 9.
02
True or False: Spatial locality means recently used data are likely to be reused soon.
Source: 01_Storage.pdf, page 10.
03
True or False: Temporal locality means data close to each other are likely to be used together.
Source: 01_Storage.pdf, page 10.
Section 02
True or False: The cache-hit-ratio formula shown is nb_hits / (nb_hits + nb_misses). to True or False: Virtual memory is always smaller than physical memory.
01
True or False: The cache-hit-ratio formula shown is nb_hits / (nb_hits + nb_misses).
Source: 01_Storage.pdf, page 10.
02
True or False: In x86, a 32-bit address space can represent 2^32 addresses.
Source: 01_Storage.pdf, page 20.
03
True or False: Virtual memory is always smaller than physical memory.
Source: 01_Storage.pdf, page 20.
Section 03
True or False: Magnetic hard disks are described with three main components: disk assembly, head assembly, and disk controller. to True or False: PageID is optional and not assigned to every page.
01
True or False: Magnetic hard disks are described with three main components: disk assembly, head assembly, and disk controller.
Source: 01_Storage.pdf, page 23.
02
True or False: Pages are fixed-sized blocks with a header and a data portion.
Source: 02_Data_Layouts.pdf, page 10.
03
True or False: PageID is optional and not assigned to every page.
Source: 02_Data_Layouts.pdf, page 10.
Section 04
True or False: In a slotted-page structure, tupleID is represented as pageID + slotID. to True or False: DSM (Decomposition Storage Model) corresponds to column layout.
01
True or False: In a slotted-page structure, tupleID is represented as pageID + slotID.
Source: 02_Data_Layouts.pdf, page 11.
02
True or False: NSM (N-ary Storage Model) corresponds to row layout.
Source: 02_Data_Layouts.pdf, page 29.
03
True or False: DSM (Decomposition Storage Model) corresponds to column layout.
Source: 02_Data_Layouts.pdf, page 31.
Section 05
True or False: Column layout removes tuple reconstruction requirements entirely. to True or False: Record-level replacement is commonly used because replacement/reloading is cheap.
01
True or False: Column layout removes tuple reconstruction requirements entirely.
Source: 02_Data_Layouts.pdf, page 31.
02
True or False: PAX is presented as NSM across pages and DSM within pages.
Source: 02_Data_Layouts.pdf, page 43.
03
True or False: Record-level replacement is commonly used because replacement/reloading is cheap.
Source: 03_Caching.pdf, page 16.
Section 06
True or False: Blocks/pages are a common granularity for buffers. to True or False: The slides claim one eviction policy is optimal for every workload.
01
True or False: Blocks/pages are a common granularity for buffers.
Source: 03_Caching.pdf, page 16.
02
True or False: The eviction policies listed include FIFO, LRU, LFU, and CLOCK.
Source: 03_Caching.pdf, page 20.
03
True or False: The slides claim one eviction policy is optimal for every workload.
Source: 03_Caching.pdf, page 20.
Section 07
True or False: FIFO directly considers recency and frequency of accesses. to True or False: CLOCK is introduced as an approximation of LRU with less overhead.
01
True or False: FIFO directly considers recency and frequency of accesses.
Source: 03_Caching.pdf, page 22.
02
True or False: LRU considers access recency but has maintenance overhead.
Source: 03_Caching.pdf, page 22.
03
True or False: CLOCK is introduced as an approximation of LRU with less overhead.
Source: 03_Caching.pdf, page 25.
Section 08
True or False: In CLOCK eviction search, when a page has bit=1, it is set to 0 and scanning continues. to True or False: A sparse index is often one entry per block and is useful when records are sorted.
01
True or False: In CLOCK eviction search, when a page has bit=1, it is set to 0 and scanning continues.
Source: 03_Caching.pdf, page 26.
02
True or False: A dense index means one index entry per block.
Source: 04_Indexing 1.pdf, pages 12 and 14.
03
True or False: A sparse index is often one entry per block and is useful when records are sorted.
Source: 04_Indexing 1.pdf, pages 12 and 16.
Section 09
True or False: In a clustered/primary index, index-entry order matches data-entry order. to True or False: The secondary index in these slides is described as dense (not sparse).
01
True or False: In a clustered/primary index, index-entry order matches data-entry order.
Source: 04_Indexing 1.pdf, pages 12 and 22.
02
True or False: A secondary index determines the physical order of records in the data file.
Source: 04_Indexing 1.pdf, page 23.
03
True or False: The secondary index in these slides is described as dense (not sparse).
Source: 04_Indexing 1.pdf, page 23.
Section 10
True or False: Data changes may require index-file updates. to True or False: A B-tree is a multi-level index with a variable number of levels.
01
True or False: Data changes may require index-file updates.
Source: 04_Indexing 1.pdf, page 24.
02
True or False: For dense indexes, maintenance is always needed when relevant data changes.
Source: 04_Indexing 1.pdf, page 24.
03
True or False: A B-tree is a multi-level index with a variable number of levels.
Source: 05_Indexing 2.pdf, page 12.
Section 11
True or False: In B-trees, root-to-leaf path lengths may vary arbitrarily. to True or False: If the root splits during insertion, tree height increases by one.
01
True or False: In B-trees, root-to-leaf path lengths may vary arbitrarily.
Source: 05_Indexing 2.pdf, page 12.
02
True or False: B-trees are designed for block-wise access.
Source: 05_Indexing 2.pdf, page 12.
03
True or False: If the root splits during insertion, tree height increases by one.
Source: 05_Indexing 2.pdf, page 29.
Section 12
True or False: B+-tree deletion never steals from siblings; it always merges immediately. to True or False: Bulk loading for large data sets is improved by sorting key-pointer pairs first.
01
True or False: B+-tree deletion never steals from siblings; it always merges immediately.
Source: 05_Indexing 2.pdf, page 35.
02
True or False: B-tree search I/O cost corresponds to the tree height.
Source: 05_Indexing 2.pdf, page 46.
03
True or False: Bulk loading for large data sets is improved by sorting key-pointer pairs first.
Source: 05_Indexing 2.pdf, page 47.
Section 13
True or False: B-tree insertion worst-case cost is independent of tree height. to True or False: The basic hash-function output range is 0 to B-1.
01
True or False: B-tree insertion worst-case cost is independent of tree height.
Source: 05_Indexing 2.pdf, page 34.
02
True or False: Hash indexes are based on sorted ordering of keys, like B-trees.
Source: 06_Indexing 3_hash_tables.pdf, page 7.
03
True or False: The basic hash-function output range is 0 to B-1.
Source: 06_Indexing 3_hash_tables.pdf, page 8.
Section 14
True or False: A collision can occur when two different keys map to the same hash value. to True or False: Overflow blocks are used as a collision-handling mechanism in secondary-storage hash tables.
01
True or False: A collision can occur when two different keys map to the same hash value.
Source: 06_Indexing 3_hash_tables.pdf, page 9.
02
True or False: Dynamic resizing is motivated because full rehashing can be expensive.
Source: 06_Indexing 3_hash_tables.pdf, page 11.
03
True or False: Overflow blocks are used as a collision-handling mechanism in secondary-storage hash tables.
Source: 06_Indexing 3_hash_tables.pdf, page 13.
Section 15
True or False: Static hash tables inherently support efficient range queries. to True or False: Linear hashing always requires a directory like extensible hashing.
01
True or False: Static hash tables inherently support efficient range queries.
Source: 06_Indexing 3_hash_tables.pdf, page 18.
02
True or False: Dynamic hash tables allow the number of buckets B to vary.
Source: 06_Indexing 3_hash_tables.pdf, page 20.
03
True or False: Linear hashing always requires a directory like extensible hashing.
Source: 06_Indexing 3_hash_tables.pdf, page 31.
Section 16
True or False: The multidimensional-indexing lecture notes that disks are fundamentally one-dimensional. to True or False: The slides state data partitioning and space partitioning are identical in all cases.
01
True or False: The multidimensional-indexing lecture notes that disks are fundamentally one-dimensional.
Source: 07_1_Multidimensional Indexing.pdf, page 30.
02
True or False: The partitioning example contrasts data partitioning and space partitioning.
Source: 07_1_Multidimensional Indexing.pdf, page 40.
03
True or False: The slides state data partitioning and space partitioning are identical in all cases.
Source: 07_1_Multidimensional Indexing.pdf, page 40.
Section 17
True or False: For multidimensional kNN, iterative range queries are suggested. to True or False: Bitmap indexes are introduced in the multidimensional-indexing lecture sequence.
01
True or False: For multidimensional kNN, iterative range queries are suggested.
Source: 07_1_Multidimensional Indexing.pdf, page 56.
02
True or False: The index-family overview includes grid file, partitioned hashing, kd-tree, quad-tree, and R-tree.
Source: 07_1_Multidimensional Indexing.pdf, page 63.
03
True or False: Bitmap indexes are introduced in the multidimensional-indexing lecture sequence.
Source: 07_1_Multidimensional Indexing.pdf, page 90.
Section 18
True or False: For bitmap partial-match queries, applying AND across relevant bitmaps is shown. to True or False: In grid files, stripe counts and widths must be identical for every dimension.
01
True or False: For bitmap partial-match queries, applying AND across relevant bitmaps is shown.
Source: 07_1_Multidimensional Indexing.pdf, page 94.
02
True or False: Grid files partition each dimension into stripes and overlay a multidimensional grid.
Source: 07_2_multidimensional indexing_pt2.pdf, page 2.
03
True or False: In grid files, stripe counts and widths must be identical for every dimension.
Source: 07_2_multidimensional indexing_pt2.pdf, page 2.
Section 19
True or False: Each region maps to a hashtable bucket, and overflow blocks are allowed. to True or False: kd-tree attributes are fixed to the same attribute at every level.
01
True or False: Each region maps to a hashtable bucket, and overflow blocks are allowed.
Source: 07_2_multidimensional indexing_pt2.pdf, page 3.
02
True or False: kd-trees are presented as a generalization of binary search trees to k dimensions.
Source: 07_2_multidimensional indexing_pt2.pdf, page 20.
03
True or False: kd-tree attributes are fixed to the same attribute at every level.
Source: 07_2_multidimensional indexing_pt2.pdf, page 20.
Section 20
True or False: For R-tree point queries, overlapping matching subregions may all need recursive descent. to True or False: The dynamic Hilbert R-tree idea includes B-tree-like insertion on Hilbert values while storing MBR information.
01
True or False: For R-tree point queries, overlapping matching subregions may all need recursive descent.
Source: 07_2_multidimensional indexing_pt2.pdf, page 40.
02
True or False: A simple nearest-neighbor strategy is to transform into range queries and expand as needed.
Source: 07_2_multidimensional indexing_pt2.pdf, page 49.
03
True or False: The dynamic Hilbert R-tree idea includes B-tree-like insertion on Hilbert values while storing MBR information.
Source: 07_2_multidimensional indexing_pt2.pdf, page 62.
Section 21
True or False: Query plans are discussed in terms of logical operators and physical operators. to True or False: A processing model defines how a DBMS executes a given query plan.
01
True or False: Query plans are discussed in terms of logical operators and physical operators.
Source: 08_Query Execution.pdf, page 5.
02
True or False: Hash Join and Sort-Merge Join are shown as alternative physical implementations.
Source: 08_Query Execution.pdf, page 5.
03
True or False: A processing model defines how a DBMS executes a given query plan.
Source: 08_Query Execution.pdf, page 10.
Section 22
True or False: Intra-operator granularity is one of the processing-model dimensions listed. to True or False: Morsel-driven parallelism uses dynamic runtime dispatch of morsels via a task queue.
01
True or False: Intra-operator granularity is one of the processing-model dimensions listed.
Source: 08_Query Execution.pdf, page 10.
02
True or False: In the consume phase description, pipeline breakers can stop after their own consume behavior.
Source: 08_Query Execution.pdf, page 40.
03
True or False: Morsel-driven parallelism uses dynamic runtime dispatch of morsels via a task queue.
Source: 08_Query Execution.pdf, page 62.
Section 23
True or False: Morsel-driven execution forbids runtime redistribution of work across threads. to True or False: Preprocessing includes translating parse trees to query expression trees and semantic checks.
01
True or False: Morsel-driven execution forbids runtime redistribution of work across threads.
Source: 08_Query Execution.pdf, page 62.
02
True or False: The parser stage is responsible for converting query text into a parse tree and checking syntax.
Source: 09_Query_Optimization.pdf, page 8.
03
True or False: Preprocessing includes translating parse trees to query expression trees and semantic checks.
Source: 09_Query_Optimization.pdf, pages 10 and 11.
Section 24
True or False: Output cardinality is modeled as input cardinality multiplied by selectivity. to True or False: Join-cardinality estimation shown uses max distinct-value counts in denominator for join attributes.
01
True or False: Output cardinality is modeled as input cardinality multiplied by selectivity.
Source: 09_Query_Optimization.pdf, page 26.
02
True or False: For conjunction predicates, selectivities are combined by multiplication under independence.
Source: 09_Query_Optimization.pdf, page 29.
03
True or False: Join-cardinality estimation shown uses max distinct-value counts in denominator for join attributes.
Source: 09_Query_Optimization.pdf, page 36.
Section 25
True or False: T(R), V(R,A), and B(R) are highlighted statistics for estimation. to True or False: Selinger-style optimization is associated with left-deep plans and dynamic programming.
01
True or False: T(R), V(R,A), and B(R) are highlighted statistics for estimation.
Source: 09_Query_Optimization.pdf, page 40.
02
True or False: Complete enumeration ignores physical operator choices.
Source: 09_Query_Optimization.pdf, page 46.
03
True or False: Selinger-style optimization is associated with left-deep plans and dynamic programming.
Source: 09_Query_Optimization.pdf, page 80.
Section 26
True or False: Interesting orders are irrelevant once the locally cheapest partial plan is found. to True or False: Conflict-serializable means the precedence graph is cycle-free.
01
True or False: Interesting orders are irrelevant once the locally cheapest partial plan is found.
Source: 09_Query_Optimization.pdf, page 65.
02
True or False: A schedule is serializable if its result is equivalent to a serial execution result.
Source: 10_Concurrency Control.pdf, page 24.
03
True or False: Conflict-serializable means the precedence graph is cycle-free.
Source: 10_Concurrency Control.pdf, page 36.
Section 27
True or False: 2PL guarantees serializability. to True or False: Strict 2PL releases exclusive locks only after commit/abort acknowledgment.
01
True or False: 2PL guarantees serializability.
Source: 10_Concurrency Control.pdf, page 47.
02
True or False: 2PL guarantees deadlock freedom.
Source: 10_Concurrency Control.pdf, pages 47 and 50.
03
True or False: Strict 2PL releases exclusive locks only after commit/abort acknowledgment.
Source: 10_Concurrency Control.pdf, page 53.
Section 28
True or False: Strict 2PL still allows deadlocks to occur. to True or False: IS and IX are incompatible according to the compatibility table shown.
01
True or False: Strict 2PL still allows deadlocks to occur.
Source: 10_Concurrency Control.pdf, page 53.
02
True or False: Intention locks are used to support hierarchical locking at different granularities.
Source: 10_Concurrency Control.pdf, page 56.
03
True or False: IS and IX are incompatible according to the compatibility table shown.
Source: 10_Concurrency Control.pdf, page 58.
Section 29
True or False: Deadlock detection can be based on cycles in a waits-for graph. to True or False: The recovery lecture distinguishes transaction, media, and system failures.
01
True or False: Deadlock detection can be based on cycles in a waits-for graph.
Source: 10_Concurrency Control.pdf, page 66.
02
True or False: READ COMMITTED disallows dirty reads but still allows fuzzy reads and phantoms.
Source: 10_Concurrency Control.pdf, page 70.
03
True or False: The recovery lecture distinguishes transaction, media, and system failures.
Source: 11_Recovery.pdf, page 5.
Section 30
True or False: NO-STEAL allows uncommitted dirty pages to be flushed to disk. to True or False: The overview pairs shadow paging with FORCE + NO-STEAL.
01
True or False: NO-STEAL allows uncommitted dirty pages to be flushed to disk.
Source: 11_Recovery.pdf, pages 7 and 8.
02
True or False: FORCE requires a transaction's updates to be on disk by commit.
Source: 11_Recovery.pdf, page 7.
03
True or False: The overview pairs shadow paging with FORCE + NO-STEAL.
Source: 11_Recovery.pdf, page 10.
Section 31
True or False: WAL requires forcing log records before writing corresponding data pages. to True or False: Undo pass scans the log forward from the beginning only.
01
True or False: WAL requires forcing log records before writing corresponding data pages.
Source: 11_Recovery.pdf, page 16.
02
True or False: The three-pass recovery order is Analysis, Redo, Undo.
Source: 11_Recovery.pdf, page 24.
03
True or False: Undo pass scans the log forward from the beginning only.
Source: 11_Recovery.pdf, page 28.
Section 32
True or False: Speedup is defined as sequential runtime divided by parallel runtime on p nodes. to True or False: In homogeneous distributed databases, all sites have identical software and cooperate.
01
True or False: Speedup is defined as sequential runtime divided by parallel runtime on p nodes.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 7.
02
True or False: Linear speedup means doubling nodes doubles speed (halves runtime).
Source: 12_Parallel_DBs_and_Big_data.pdf, page 7.
03
True or False: In homogeneous distributed databases, all sites have identical software and cooperate.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 15.
Section 33
True or False: Inter-query parallelism is highlighted as important for OLTP scenarios. to True or False: Replication and fragmentation are mutually exclusive and cannot be combined.
01
True or False: Inter-query parallelism is highlighted as important for OLTP scenarios.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 24.
02
True or False: Intra-query parallelism includes data parallelism and pipeline parallelism.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 24.
03
True or False: Replication and fragmentation are mutually exclusive and cannot be combined.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 31.
Section 34
True or False: Vertical partitioning is noted to appear in extreme form in column stores.
01
True or False: Vertical partitioning is noted to appear in extreme form in column stores.
Source: 12_Parallel_DBs_and_Big_data.pdf, page 36.
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.