Database Systems

A database system is one of the core components of modern computing infrastructure. A Database Management System (DBMS) provides a unified abstraction layer for persistent storage, efficient querying, concurrent access, and consistency guarantees. From traditional relational databases to emerging NoSQL, NewSQL, and vector databases widely used in AI engineering, the evolution of database technology has always been closely aligned with application demands.

These notes cover the core topics in database systems, including the relational model, transaction management, indexing mechanisms, query optimization, NoSQL paradigms, and cutting-edge database applications in AI.

1. DBMS Classification

Type	Data Model	Representative Systems	Typical Use Cases
Relational (RDBMS)	Tables (rows and columns)	MySQL, PostgreSQL, Oracle	OLTP, enterprise apps, finance
Document	JSON/BSON documents	MongoDB, CouchDB	CMS, user profiles, logging
Key-Value	Key-Value pairs	Redis, DynamoDB	Caching, sessions, real-time counters
Column-Family	Column families	Cassandra, HBase	Time-series data, high write throughput
Graph	Nodes and edges	Neo4j, Amazon Neptune	Social networks, knowledge graphs, recommendations
Vector	High-dimensional vectors	Pinecone, Milvus, Weaviate	Semantic search, RAG, recommendation systems

OLTP vs. OLAP

OLTP (Online Transaction Processing): High concurrency, short transactions, primarily row-oriented storage (e.g., MySQL).
OLAP (Online Analytical Processing): Complex aggregate queries, primarily column-oriented storage (e.g., ClickHouse, Snowflake).
The modern trend is HTAP (Hybrid Transactional/Analytical Processing), exemplified by TiDB.

2. The Relational Model and SQL

2.1 Relational Algebra

Relational algebra provides the theoretical foundation for relational databases, defining an algebraic system for operating on relations (tables).

Operation	Symbol	Meaning
Selection	\(\sigma_{\theta}(R)\)	Select tuples from \(R\) that satisfy condition \(\theta\)
Projection	\(\pi_{A_1, A_2, \dots}(R)\)	Extract specified attribute columns from \(R\)
Union	\(R \cup S\)	Union of two relations
Difference	\(R - S\)	Tuples in \(R\) but not in \(S\)
Cartesian Product	\(R \times S\)	Cartesian product of two relations
Natural Join	\(R \bowtie S\)	Equi-join on common attributes with deduplication
Division	\(R \div S\)	Quotient operation, used for "for all" type queries

Example: Find students who have enrolled in every course

\[ \pi_{\text{sid, cid}}(\text{Enrollment}) \div \pi_{\text{cid}}(\text{Course}) \]

2.2 SQL Fundamentals

SQL (Structured Query Language) is divided into three major sub-languages:

DDL (Data Definition Language):

CREATE TABLE Students (
    sid     INT PRIMARY KEY,
    name    VARCHAR(64) NOT NULL,
    gpa     DECIMAL(3,2) CHECK (gpa >= 0 AND gpa <= 4.0),
    dept_id INT REFERENCES Departments(dept_id)
);

DML (Data Manipulation Language):

-- Subquery + aggregation
SELECT dept_id, AVG(gpa) AS avg_gpa
FROM Students
GROUP BY dept_id
HAVING AVG(gpa) > 3.5
ORDER BY avg_gpa DESC;

DCL (Data Control Language):

GRANT SELECT, INSERT ON Students TO role_readonly;
REVOKE INSERT ON Students FROM role_readonly;

3. Transactions and Concurrency Control

3.1 ACID Properties

Property	Meaning	Implementation
Atomicity	A transaction either fully completes or fully rolls back	Undo Log
Consistency	The database satisfies integrity constraints before and after a transaction	Application layer + constraint checks
Isolation	Concurrent transactions do not interfere with each other	Locks / MVCC
Durability	Committed transaction results are never lost	Redo Log + WAL

3.2 Isolation Levels

Isolation Level	Dirty Read	Non-repeatable Read	Phantom Read	Performance
Read Uncommitted	Possible	Possible	Possible	Highest
Read Committed	Impossible	Possible	Possible	High
Repeatable Read	Impossible	Impossible	Possible	Medium
Serializable	Impossible	Impossible	Impossible	Lowest

MySQL's Special Behavior

MySQL InnoDB largely prevents phantom reads at the Repeatable Read level through Next-Key Locking, which diverges from the SQL standard's definition.

3.3 MVCC (Multi-Version Concurrency Control)

The core idea of MVCC is to maintain multiple versions of each data item: read operations access snapshot versions while write operations create new versions, thereby achieving non-blocking reads alongside writes.

Each row implicitly contains a trx_id (creating transaction ID) and a roll_pointer (rollback pointer)
Read operations determine visibility based on a consistent read view
PostgreSQL implements MVCC using xmin/xmax, with garbage collection performed by VACUUM

4. Indexing

4.1 B+ Tree Index

The B+ tree is the most widely used index structure in relational databases, with the following characteristics:

All data is stored in leaf nodes, which are linked together in a linked list
Tree height is typically 3-4 levels, supporting \(O(\log_B N)\) lookups
Supports range queries (sequential scan of the leaf node linked list)
Node size is typically aligned with disk pages (4KB/16KB)

B+ Tree vs. B Tree: Internal nodes of a B+ tree store only keys (no data pointers), resulting in higher fan-out and shorter trees.

4.2 Hash Index

Maps keys to buckets via a hash function
Supports only equality queries, not range queries
Average time complexity \(O(1)\), but susceptible to hash collisions
Widely used in MySQL's Memory engine and within Redis

4.3 Other Index Types

Index Type	Use Case	Example
Full-text Index	Text search	Elasticsearch inverted index
Spatial Index (R-tree)	Geospatial queries	PostGIS
Bitmap Index	Analytical queries on low-cardinality columns	Oracle Data Warehouse
Vector Index (HNSW/IVF)	Approximate nearest neighbor search	Milvus, pgvector

5. Query Optimization

5.1 Query Processing Pipeline

SQL Query → Parser → Logical Plan → Optimizer → Physical Plan → Execution Engine

5.2 Cost Estimation

The optimizer estimates the cost of different execution plans using statistics:

Selectivity: \(\text{sel}(\sigma_{A=v}(R)) = \frac{1}{V(A, R)}\), where \(V(A, R)\) is the number of distinct values of attribute \(A\)
Join cost models: - Nested Loop Join: \(O(|R| \cdot |S|)\) - Sort-Merge Join: \(O(|R| \log |R| + |S| \log |S|)\) - Hash Join: \(O(|R| + |S|)\) (average)

5.3 Common Optimization Strategies

Predicate Pushdown: Filter unnecessary rows as early as possible
Projection Pushdown: Discard unnecessary columns as early as possible
Join Order Optimization: Select the join order with minimum cost (NP-hard; typically solved via dynamic programming or greedy heuristics)
Index Scan vs. Full Table Scan: Decide whether to use an index based on selectivity

6. NoSQL Databases

6.1 The CAP Theorem

A distributed system cannot simultaneously satisfy all three of the following properties (at most two):

C (Consistency): All nodes see the same data at the same time
A (Availability): Every request receives a (non-error) response
P (Partition Tolerance): The system continues to operate despite network partitions

System	Choice	Characteristics
Traditional RDBMS	CA	Single-node deployment; network partitions not considered
MongoDB, HBase	CP	Sacrifice availability during partitions
Cassandra, DynamoDB	AP	Sacrifice consistency during partitions (eventual consistency)

6.2 Representative Systems

MongoDB (Document Database):

Stores data in BSON format with flexible schemas
Supports rich query syntax and aggregation pipelines
Horizontal scaling via Sharding + Replica Sets

Redis (Key-Value Store):

In-memory database supporting multiple data structures (String, Hash, List, Set, Sorted Set)
Persistence: RDB snapshots + AOF logging
Common uses: caching, distributed locks, message queues

Neo4j (Graph Database):

Property graph model: both nodes and edges can have properties
Cypher query language: MATCH (a:Person)-[:KNOWS]->(b:Person) RETURN a, b
Excels at multi-hop relationship queries for social networks, recommendations, and fraud detection

7. NewSQL and Distributed Databases

NewSQL aims to achieve NoSQL-level horizontal scalability while preserving SQL compatibility and ACID transactions.

System	Architecture	Storage Engine
Google Spanner	Globally distributed, TrueTime	Colossus
CockroachDB	Open-source Spanner-inspired	RocksDB
TiDB	MySQL protocol compatible	TiKV (Raft + RocksDB)
YugabyteDB	PostgreSQL protocol compatible	DocDB

Core Technologies:

Raft/Paxos Consensus Protocols: Ensure distributed consistency
Distributed Transactions: Two-phase commit (2PC) or the Percolator model
Automatic Sharding and Load Balancing: Data is sharded by range or hash

8. Database Applications in AI Engineering

8.1 Vector Databases

Vector databases are purpose-built for storing and retrieving high-dimensional vectors and serve as core components of RAG (Retrieval-Augmented Generation) systems.

Workflow:

Text is converted to vectors via an embedding model (e.g., text-embedding-3-small)
Vectors are stored in the database and indexed
At query time, similarity is computed between the query vector and stored vectors (cosine distance, Euclidean distance)
The Top-K most similar results are returned

Major Vector Index Algorithms:

Algorithm	Principle	Characteristics
HNSW	Hierarchical Navigable Small World graph	High accuracy, high memory consumption
IVF	Inverted File Index + clustering	Tunable accuracy-speed tradeoff
PQ (Product Quantization)	Vector compression	Memory-efficient, lossy precision
ScaNN	Google's hybrid quantization scheme	Production-grade performance

8.2 Feature Stores

Feature stores provide a unified feature management layer for ML pipelines:

Offline features: Batch-computed, stored in data warehouses (e.g., BigQuery)
Online features: Low-latency serving, stored in Redis/DynamoDB
Feature consistency: Ensuring training and inference use identical feature transformation logic
Representative systems: Feast, Tecton, Hopsworks

8.3 The Convergence of Databases and LLMs

Text-to-SQL: LLMs translate natural language into SQL queries
Knowledge Graph + RAG: Hybrid retrieval combining structured knowledge with unstructured text
Semantic Caching: Cache LLM responses based on vector similarity to reduce redundant computation

9. Common Engineering Trade-offs in Database Work

The core of database engineering is not just "knowing SQL." It is knowing how to trade off consistency, latency, cost, scalability, and maintenance complexity.

Trade-off	One End	Other End	Typical Question
Consistency vs latency	stronger consistency	lower latency	must a read immediately observe the newest write?
Normalization vs ease of query	higher normalization	redundancy / pre-aggregation	how should join complexity be balanced against update cost?
Transactionality vs throughput	strict ACID	higher concurrency	is a cross-entity transaction truly necessary?
Single-node simplicity vs distributed scaling	vertical scaling	sharding / replication	when is it worth paying distributed-system complexity?
General-purpose DB vs specialized stores	one system	mixed storage stack	is it worth splitting search, cache, and vector retrieval into separate components?

These trade-offs also explain why database issues often flow back into System Design and Distributed Systems. Many so-called "database bottlenecks" are really symptoms of unclear system boundaries and access patterns.

Relations to Other Topics

See System Design for how database selection enters capacity planning, caching, and service-boundary design
See Distributed Systems for replication, consistency, sharding, and transaction behavior in multi-node settings
See Cloud Services for managed databases, object storage, and cloud-native data infrastructure
See Full-Stack Development for how the application layer reaches databases through ORM, migrations, and APIs

References

Ramakrishnan & Gehrke, Database Management Systems
Silberschatz et al., Database System Concepts
Kleppmann, Designing Data-Intensive Applications
CMU 15-445/645: Database Systems