Intro to Database Systems

This session outlines the structure, expectations, and administrative details for Carnegie Mellon University's 15-445/645 Introduction to Database Systems course. It details grading policies, assignments, and semester schedule.

Traces Ted Codd's 1970 revolution over navigational CODASYL databases—why separating logical relational algebra from physical access paths made modern query optimizers possible.

Moves far beyond SELECT-FROM-WHERE into modern declarative SQL-99+: window functions, recursive CTEs, lateral joins, and aggregation edge cases.

Why mmap() in a DBMS is a catastrophic trap, how NVMe/SSD block geometry dictates page layout, and how slotted pages and heap files store variable-length tuples.

Compares page-oriented B+Tree storage (PostgreSQL) against append-only Log-Structured Merge Trees (RocksDB, LevelDB, Cassandra), compaction strategies, and Bloom filters.

Deconstructs NSM row stores vs. DSM columnar formats (Parquet/ORC) and shows how dictionary, run-length, and bit-packing compression allow late-materialization query execution directly on compressed data.

Explains why databases bypass OS page caches via O_DIRECT, manage page pin counts and latches, and prevent sequential-scan pollution using LRU-K and Clock policies.

Cache-conscious engineering walkthrough of open-addressing probe schemes (Robin Hood, Cuckoo) and disk-friendly dynamic hashing (Extendible and Linear Hashing).

This lecture dissects the architecture and operational mechanics of B+Tree indexes, focusing on their efficacy in database systems for efficient data retrieval and storage organization.

The session explores methods for managing concurrent access to database indexes, including various locking protocols and their implications for performance and consistency.

This lecture examines fundamental sorting and aggregation algorithms critical for optimizing database query processing, including external sorting and hash-based aggregation techniques.

The session delves into various join algorithms used in relational databases, such as nested-loop join, hash join, and sort-merge join, evaluating their performance characteristics.

This lecture initiates a two-part series on query execution, covering the foundational concepts of how database systems process and evaluate SQL queries.

Continuing the discussion on query execution, this part explores advanced strategies and implementation details that database management systems employ to fulfill query requests efficiently.

This lecture focuses on the sophisticated mechanisms of query planning and optimization, including cost-based optimization and heuristic approaches to generate optimal execution plans.

This lecture introduces the theoretical underpinnings of concurrency control in database systems, emphasizing serializability, atomicity, and the ACID properties.

The session rigorously details the Two-Phase Locking (2PL) protocol, a cornerstone mechanism for ensuring serializability and maintaining consistency in concurrent database transactions.

This lecture explores Timestamp Ordering (TO) as an alternative concurrency control protocol, analyzing its mechanisms for ensuring transaction serializability through temporal stamps.

The lecture examines Multi-Version Concurrency Control (MVCC) techniques, which enhance parallelism and reduce contention by allowing transactions to read older versions of data.

This session covers the critical role of database logging in ensuring durability and atomicity, detailing write-ahead logging (WAL) and log record structures.

The lecture elaborates on database recovery mechanisms, outlining how systems restore consistency and data integrity after failures using logs and checkpoints.

This introductory lecture surveys the fundamental concepts and architectures of distributed database systems, addressing challenges like data distribution and consistency in a partitioned environment.