Databases Notes

Introduction

The database symbol is a cylinder because databases were originally stored on a hard disk of stacked plates.

Question: Why use a database management system (DBMS) instead of a filesystem?

1. Data consistency (schema)
2. Crash recovery
3. Efficient data retrieval
4. Concurrent access to data
5. Physical data independence (ability to change how data is stored without changing application code)

A DBMS allows users to store, query, and update databases in accordance to some data model. Examples of data models include:

1. Relational
2. Key-value
3. Graph
4. Document
5. Vector

DBMS design principles:

1. More specialized databases, driven by application semantics
2. Few primitives (relational operators) which can be composed
3. Data independence; applications should not need to understand how data is stored
4. Declarative programming

Relational Algebra

Early database applications tightly coupled logical and physical layers, which made it difficult to make any changes to the program. To deal with the maintenance overhead, Ted Codd wrote A relational model of data for large shared data banks, which later became the basis of the relational data model.

The key ideas are:

• Data should be stored in simple data structures (relations)
• The DBMS should be responsible for the physical storage of the data
• Data should be accessed through high-level, declarative language, so that the DBMS can optimize it

Terminology:

• A relation is an unordered set of tuples
• A tuple is a set of attribute values
• A primary key uniquely identifies a single tuple in a relation
• A foreign key specifies that an attribute from one relation maps to a tuple in another relation

Relational models can define constraints, such as:

• Table schema is respected
• Primary keys are unique
• The foreign key exists in another table
• Global assertions

There are two different types of data management languages (DMLs):

1. Procedural: the query specifies how to find the desired result (e.g. relational algebra)
2. Declarative: the query only specifies what data is wanted (e.g. SQL)

Relational algebra is based on set algebra. That means that it represents relations as unordered lists with no duplicates. Each operator takes in one relation and outputs a new relation.

SQL

Unlike in relational algebra, SQL assumes that data is stored in a bag, not a set. This means that there can be duplicated rows. This is for efficiency reasons—if we do a union on two very large tables, it is expensive to deduplicate the output.

There are several classes of SQL operations:

1. Selection ($\sigma$)
2. Projection ($\pi$)
3. Aggregation
4. Join
5. Views

GROUP BY rules:

1. Non-aggregated values in SELECT output must appear in GROUP BY clause.
2. Each GROUP BY clause will cause the output to contain one tuple per group.

Types of JOIN:

• Cross join: Cartesian product
• Inner join: every pair that matches, dropping non-matching pairs
• Outer join: every pair that matches, keeping non-matching tuples

Within inner joins, there is:

• Natural join ($R \bowtie S$): match tuples where the shared attributes are equivalent
• Theta or equijoin ($R \bowtie_\theta S$): match tuples using some join predicate defined by $\theta$
• Semi join ($R \ltimes S$): same as theta join, except output relation only contains attributes from $R$
• Anti semijoin ($R \rhd S$): tuples of $R$ that do not match with any tuple of $S$ (not technically an inner join)

Within outer joins, there is:

• Left outer join ($R\, ⟕\, S$): match all combinations of tuples where the shared attributes are equivalent, plus all tuples in $R$ that have no match in $S$
• Right outer join ($R\, ⟖\, S$): the same as left outer join but reversed
• Full outer join ($R\, ⟗\, S$): union of left and right outer joins

For more details about SQL syntax, go to the SQL page.

A view is a (virtual) table that is the result of a SQL query. Typically, user applications are built on top of views rather than the base tables. It is not possible to update a view, which makes it good for security.

Because views may be accessed frequently, it may be impractical to run the query every time. We may want to maintain a materialized view, a cache of the view that is refreshed on updates or periodically.

Schema Design

A good database schema ensures data integrity and has good performance. These goals are typically in conflict with each other.

On one end of the extreme, we have only one spreadsheet with all the data. This has good performance because it is not necessary to perform any joins. But it is difficult to maintain data integrity with respect to updates, insertions, and deletions.

For example, consider the following spreadsheet:

• If we want to update the room number for a particular course, we need to iterate through the entire database to update the fields
• We cannot insert a student that is not enrolled in a course
• If we delete all students enrolled in a course, we lose information about which course is assigned to which room

The alternative is to decompose the schema into multiple relations, or normalizing the data. This reduces redundancy, which is good for data integrity. However, we will typically need more joins, leading to a decrease in performance.

There are multiple levels of normalization:

Storage Manager

Layers of a DBMS:

1. Storage manager: handles reading and writing raw pages to and from the physical disk
2. Buffer pool manager: manages an in-memory cache of pages
3. Access methods: organize and access data on disk
4. Operator execution: implements relational operators that consume and produce tuples via the access methods
5. Query planning: parses, optimizes, and compiles a query into a plan of operators to execute

DBMSs try to ensure that consecutive blocks are stored on consecutive disk blocks. On magnetic hard disks, doing random access costs seek time and rotational latency. While this is less significant for SSDs, there may be I/O controller overheads.

Files, Pages, and Tuples

The DBMS stores the database in a file on disk, typically in a proprietary binary format. The storage manager is responsible for managing a database's files. It organizes the files as a collection of pages, which is a fixed-size block of data with an offset into the file. Each page contains data such as tuples.

There are three different notions of pages in a DBMS:

1. Hardware page, the atomic unit of I/O to a disk (4 KB)
2. OS page, the software abstraction of a hardware page (4 KB)
3. Database page, set by the DBMS (4-16 KB)

Large database pages are good for large sequential writes, but it is more complicated to ensure atomicity. Additionally, more data needs to be loaded into RAM for small reads and writes.

The Operating System

Traditional file I/O operations involve system calls to read from or write to a file. Memory mapping (mmap) allows a file to be accessed directly through virtual memory addresses.

Many DBMSs avoid using memory-mapped files because they require fine-grained control over I/O operations. In general, DBMSs know more about their workloads and can better optimize file fetches and flushes than the OS. Sometimes, the OS can even get in the way, like in the case of double-buffering.

However, most modern operating systems do use the file system API exposed by the operating system. Early DBMS systems used custom file systems on raw storage, but this had portability issues when switching to different hardware, and the performance benefit was minimal (5-10%).

File Organization

There are several ways to manage pages in files on disk:

• Heap file organization
• Sequential or sorted file organization (ISAM)
• Tree file organization
• Hashing file organization

A heap file is a collection of pages with tuples that are stored in random order. A page directory tracks the physical location of pages for a database file, and also records metadata about available space.

Every page contains a header of metadata about the page's contents, including page size, checksum, DBMS version, transaction visibility, and compression information.

One naive way to lay out tuples on a page is by directly placing them in a fixed array of slots. However, this requires that each tuple be a fixed size. It also makes deletions difficult.

The most common layout scheme for a page is called slotted pages. The slot array maps slots to the tuples' starting position offsets. The header keeps track of the number of used slots, and the offset of the last slot used. Each tuple has a fixed slot entry.

Some benefits of the slotted pages are:

• During deletion, the slot array can be easily modified to hide the deletion
• Slots can be heterogeneous sizes
• Compaction can be delayed.

The DBMS also needs a way to keep track of individual tuples. This is commonly the page id and the offset into the page.

Tuples also have a header to specify things like the null value bitmap. Having a null value bitmap allows us to save space, since we don't need to store the null value. For example, a tuple with the value {101, 13, null} would have the null value bitmap 001, allowing us to only allocate 101 and 13 on the disk.

The schema is typically not stored in the tuple header.

Buffer Pool Manager

The buffer pool is a region of RAM managed by the DBMS. It is organized as an array of fixed-sized pages, where each array entry is called a frame. When the DBMS requests a page to be loaded from disk, a copy of the page is placed in a frame.

The database wants to carefully control when dirty pages are written back to disk. It wants to use the RAM as a write-back cache for disk, not as a write-through cache.

The page table keeps track of pages that are currently in memory, and it also keeps additional metadata about the dirty flag and the reference count. The DBMS cannot evict pages from the buffer pool if the reference count is non-zero. The DBMS should probably also write back the page to disk before eviction if the page is dirty.

The page table is usually a fixed-sized map protected with latches to ensure thread-safe access.