Database Fundamentals¶
Every application you use - from the banking app on your phone to the search engine returning this page - depends on a database. But databases did not spring into existence fully formed. They evolved over decades, shaped by real engineering failures, shifting hardware constraints, and a few landmark academic papers. Understanding that evolution gives you a vocabulary and mental model that makes every subsequent guide in this course easier to absorb.
The Evolution of Data Management¶
Before databases existed, programs stored data in flat files - plain text or binary files on disk, each structured however the programmer saw fit. A payroll system might write employee records as fixed-width lines in a .dat file. A different department's inventory system used a different format. There was no standard way to query, update, or relate data across systems. If the file format changed, every program that read it broke.
This worked when computers served one department and ran one program at a time. It fell apart the moment organizations needed to share data across applications. The problems were predictable: data duplication across files led to inconsistencies, concurrent access caused corruption, and there was no mechanism for enforcing data integrity. If two programs tried to update the same file simultaneously, the result depended on timing - a problem known as a race condition.
Hierarchical Model: IMS¶
In 1966, IBM and North American Aviation (now part of Boeing) built IMS (Information Management System) to manage the bill of materials for the Saturn V rocket. IMS organized data as a tree - parent records owned child records, which owned grandchild records, and so on. Navigating from a rocket stage to its components to their suppliers meant walking down the tree.
The hierarchical model was fast for the access patterns it was designed for. If your queries always started at the root and walked downward, IMS performed well. But if you needed to query across branches - "show me all suppliers who provide parts to more than one stage" - you were stuck writing complex application code to traverse multiple trees and correlate the results.
Network Model: CODASYL¶
The CODASYL (Conference on Data Systems Languages) committee proposed the network model in 1969 to address the hierarchical model's rigidity. Instead of trees, data was organized as a graph: records could have multiple parent-child relationships through sets (essentially pointers linking record types). A supplier record could be linked to multiple part records across different assemblies.
This was more flexible than IMS, but the programmer had to navigate the graph manually - following pointers from record to record. Queries were imperative: "start at this record, follow this set, move to the next member." If the data relationships changed, the navigation code changed too. The database and the application were tightly coupled.
The Relational Revolution: Codd¶
In June 1970, Edgar F. Codd, a researcher at IBM's San Jose lab, published "A Relational Model of Data for Large Shared Data Banks" in Communications of the ACM. The paper proposed something radical: separate the logical organization of data from its physical storage. Data would be organized into relations (tables), and users would declare what data they wanted, not how to navigate to it.
This was the birth of the relational model, and it changed everything. Instead of writing imperative navigation code, you would write declarative queries. The database system would figure out the optimal access path. This separation meant that the physical storage could change - indexes added or removed, data reorganized on disk - without breaking application code.
IBM was slow to commercialize Codd's ideas (IMS was a cash cow), but two Berkeley researchers, Michael Stonebraker and Eugene Wong, built Ingres in the mid-1970s.
Larry Ellison read Codd's papers and built what became Oracle. IBM eventually shipped System R, which evolved into DB2. The SQL language emerged from System R and was standardized in 1986.
Object-Oriented and Object-Relational Databases¶
In the late 1980s and 1990s, as object-oriented programming gained traction, some argued that the "impedance mismatch" between objects in code and tables in databases required a new approach. Object-oriented databases (OODBs) like GemStone, ObjectStore, and Versant stored objects directly, preserving inheritance and encapsulation.
OODBs never displaced relational systems in the mainstream. The relational model's mathematical foundation, mature tooling, and the practical effectiveness of object-relational mapping (ORM) layers proved "good enough." The ORM approach - mapping objects to rows through libraries like Hibernate (Java), SQLAlchemy (Python), and ActiveRecord (Ruby) - became the standard way to bridge the gap.
However, the object-oriented movement influenced relational databases in lasting ways. PostgreSQL added support for user-defined types, table inheritance, and eventually JSON/JSONB columns - blurring the line between relational and object storage. MySQL 5.7 added a native JSON type. SQL Server added XML and JSON support. The relational model absorbed the useful ideas and kept its position.
The NoSQL Movement¶
By the mid-2000s, web-scale companies hit walls that traditional RDBMS systems were not built for. Google published the Bigtable paper (2006). Amazon published the Dynamo paper (2007). These systems sacrificed some relational guarantees - joins, rigid schemas, multi-row transactions - in exchange for horizontal scalability and availability across distributed clusters.
The term NoSQL (sometimes backronymed as "Not Only SQL") became an umbrella for a diverse set of systems: document stores like MongoDB, key-value stores like Redis, wide-column stores like Apache Cassandra, and graph databases like Neo4j. Each traded away different relational features to optimize for specific access patterns or scale requirements.
Today, the industry has largely moved past the "NoSQL vs. SQL" debate. Most organizations practice polyglot persistence - using whichever database best fits each workload. A single application might use PostgreSQL for transactional data, Redis for caching and session state, and Elasticsearch for full-text search.
graph LR
A[Flat Files<br>1950s-60s] --> B[Hierarchical<br>IMS 1966]
B --> C[Network<br>CODASYL 1969]
C --> D[Relational<br>Codd 1970]
D --> E[Object-Oriented<br>1980s-90s]
D --> F[Object-Relational<br>1990s-2000s]
D --> G[NoSQL<br>2000s-2010s]
G --> H[Polyglot<br>Persistence]
F --> HThe Relational Model¶
The relational model is the foundation for MySQL, PostgreSQL, Oracle, SQL Server, SQLite, and every other RDBMS. Even if you work primarily with NoSQL systems, understanding relational concepts gives you a baseline for evaluating trade-offs.
Tables, Rows, and Columns¶
A table (or relation in formal terminology) is a structured collection of data about a single entity type. An employees table stores data about employees. An orders table stores data about orders.
Each row (or tuple) represents one instance of that entity - one employee, one order. Each column (or attribute) represents one property of that entity - name, hire date, salary, order total.
CREATE TABLE employees (
employee_id INT PRIMARY KEY,
first_name VARCHAR(50) NOT NULL,
last_name VARCHAR(50) NOT NULL,
department_id INT,
hire_date DATE NOT NULL,
salary DECIMAL(10,2)
);
Every column has a data type that constrains what values it can hold. INT stores integers. VARCHAR(50) stores variable-length strings up to 50 characters. DATE stores calendar dates. DECIMAL(10,2) stores numbers with up to 10 digits and 2 decimal places. Choosing the right data type matters for storage efficiency, query performance, and data integrity.
Keys¶
A primary key uniquely identifies each row in a table. No two rows can share the same primary key value, and the value cannot be NULL. In the example above, employee_id is the primary key.
A foreign key is a column (or set of columns) in one table that references the primary key of another table. It establishes a relationship between the two tables and enforces referential integrity - the database refuses to insert a row with a foreign key value that does not exist in the referenced table.
CREATE TABLE departments (
department_id INT PRIMARY KEY,
department_name VARCHAR(100) NOT NULL
);
-- The foreign key links employees to departments
ALTER TABLE employees
ADD CONSTRAINT fk_department
FOREIGN KEY (department_id) REFERENCES departments(department_id);
A composite key uses multiple columns together as the primary key. An enrollments table might use (student_id, course_id) as its composite primary key - neither column alone identifies a unique enrollment, but together they do.
A candidate key is any column or combination of columns that could serve as the primary key. An employees table might have both employee_id (a surrogate key) and email (a natural key) as candidate keys. You pick one as the primary key; the others can be enforced with UNIQUE constraints.
Relationships¶
Tables relate to each other through three patterns:
One-to-many is the most common. One department has many employees. The "many" side holds the foreign key: employees.department_id references departments.department_id.
Many-to-many uses a junction table (also called a join table or associative table). Students enroll in many courses; courses have many students. The enrollments table holds foreign keys to both students and courses.
CREATE TABLE enrollments (
student_id INT REFERENCES students(student_id),
course_id INT REFERENCES courses(course_id),
enrolled_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (student_id, course_id)
);
One-to-one is less common. A users table and a user_profiles table might have a one-to-one relationship where each user has exactly one profile. This is often done to separate frequently accessed columns from rarely accessed ones, or to isolate sensitive data (like billing information) into a table with different access controls.
ACID Properties¶
When you transfer money between bank accounts, you need guarantees. The transfer should either complete fully or not happen at all. The account balances should remain consistent. Concurrent transfers should not corrupt each other. And once confirmed, the transfer should survive a power failure.
These guarantees have a name: ACID. Every transaction in a relational database is expected to satisfy all four properties.
Atomicity¶
Atomicity means a transaction is all-or-nothing. If a transaction contains five SQL statements and the third one fails, the first two are rolled back. The database never reflects a partial transaction.
Consider a bank transfer:
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 500 WHERE account_id = 1001;
UPDATE accounts SET balance = balance + 500 WHERE account_id = 1002;
COMMIT;
If the system crashes after the first UPDATE but before the COMMIT, atomicity guarantees the first debit is rolled back. The $500 does not vanish.
Consistency¶
Consistency means a transaction brings the database from one valid state to another. It cannot violate constraints - primary keys, foreign keys, check constraints, unique constraints, or any rules defined in the schema. If a transaction would leave the database in an invalid state, the database rejects it.
For example, if a CHECK constraint requires balance >= 0, a withdrawal that would push the balance below zero is rejected - even if the SQL is syntactically correct.
ALTER TABLE accounts ADD CONSTRAINT positive_balance CHECK (balance >= 0);
-- This transaction is rejected because it violates the CHECK constraint
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 10000 WHERE account_id = 1001;
-- ERROR: new row for relation "accounts" violates check constraint "positive_balance"
ROLLBACK;
Isolation¶
Isolation determines how concurrent transactions interact. Without isolation, two simultaneous transactions could read and write the same rows, producing results that neither transaction intended.
SQL defines four isolation levels, each trading correctness for performance:
| Isolation Level | Dirty Reads | Non-Repeatable Reads | Phantom Reads |
|---|---|---|---|
| Read Uncommitted | Possible | Possible | Possible |
| Read Committed | Prevented | Possible | Possible |
| Repeatable Read | Prevented | Prevented | Possible |
| Serializable | Prevented | Prevented | Prevented |
A dirty read sees data from another transaction that has not yet committed (and might be rolled back). A non-repeatable read means re-reading a row within the same transaction returns different values because another transaction modified and committed it in between. A phantom read means a query returns different rows on re-execution because another transaction inserted or deleted matching rows.
Most production databases default to Read Committed (PostgreSQL, Oracle) or Repeatable Read (MySQL/InnoDB). Serializable provides the strongest guarantees but reduces concurrency.
Isolation is not free
Higher isolation levels reduce concurrency. Serializable isolation can cause transactions to wait or abort due to conflicts. Choose the lowest isolation level that provides the correctness guarantees your application requires. Most OLTP workloads run fine at Read Committed.
Durability¶
Durability means that once a transaction is committed, the data persists even if the system crashes, loses power, or the operating system panics. Databases achieve this through write-ahead logging (WAL) - changes are written to a sequential log on durable storage before being applied to the actual data files. On recovery, the database replays the log to reconstruct any committed transactions that had not yet been flushed to the data files.
WAL is everywhere
Write-ahead logging is not unique to databases. Journaling filesystems like ext4 and XFS use the same principle. The idea is ancient in computing terms: write your intentions to a sequential log before modifying the actual data structure. If you crash, replay the log.
CAP Theorem¶
In 2000, Eric Brewer proposed the CAP theorem (formally proved by Gilbert and Lynch in 2002), which states that a distributed data system can provide at most two of three guarantees simultaneously:
- Consistency - every read receives the most recent write (all nodes see the same data at the same time)
- Availability - every request receives a response (no timeouts, even if some nodes are down)
- Partition tolerance - the system continues to operate despite network partitions between nodes
Since network partitions are inevitable in distributed systems (cables get cut, switches fail, cloud availability zones lose connectivity), the practical choice is between CP (consistency + partition tolerance) and AP (availability + partition tolerance).
CAP Consistency is not ACID Consistency
These are different definitions of "consistency." ACID consistency means a transaction does not violate database constraints. CAP consistency (also called linearizability) means all nodes in a distributed system agree on the current value of every piece of data at any given moment. A single-node PostgreSQL instance provides ACID consistency but the CAP theorem does not apply to it because it is not distributed.
Real-World CAP Trade-offs¶
CP systems prioritize consistency over availability. If a network partition occurs, the system refuses to serve requests on the side that cannot confirm it has the latest data, rather than risk returning stale results.
- etcd and ZooKeeper - coordination services that use consensus protocols (Raft, ZAB) to ensure all reads return the latest write. During a partition, the minority side becomes unavailable.
- HBase - a wide-column store built on HDFS that provides strong consistency for row-level operations.
- Traditional RDBMS clusters with synchronous replication behave as CP systems.
AP systems prioritize availability over consistency. During a partition, all nodes continue serving requests, but some may return stale data.
- Cassandra - a wide-column store designed for write-heavy workloads across multiple data centers. With tunable consistency levels, Cassandra defaults to eventual consistency but can be configured for stronger guarantees per query.
- DynamoDB - Amazon's managed key-value and document store, designed from the Dynamo paper's principles. Eventually consistent reads are the default; strongly consistent reads are available at higher cost.
- CouchDB - a document store designed around eventual consistency and multi-master replication.
In practice, CAP is a spectrum, not a strict three-way partition. Systems like Cassandra offer tunable consistency - you can request QUORUM reads (a majority of replicas must agree) to get stronger guarantees at the cost of higher latency and reduced availability during partitions.
| System | CAP Category | Consistency Model | Use Case |
|---|---|---|---|
| PostgreSQL (single node) | N/A (not distributed) | Strong (ACID) | Transactional workloads |
| etcd / ZooKeeper | CP | Linearizable | Cluster coordination, config |
| Cassandra | AP (tunable) | Eventual to strong | Write-heavy, multi-DC |
| DynamoDB | AP (tunable) | Eventual or strong | Managed key-value at scale |
| MongoDB (replica set) | CP | Linearizable (with majority reads) | Document storage |
| CockroachDB | CP | Serializable | Distributed SQL |
Storage Engine Landscape¶
The storage engine is the component that actually writes data to disk, reads it back, manages indexes, and handles concurrency. The same database server can sometimes use different storage engines for different tables.
B-Trees and B+ Trees¶
The B-tree (and its variant the B+ tree) is the dominant index structure in relational databases. It keeps data sorted and allows searches, insertions, and deletions in O(log n) time. B+ trees store all data in leaf nodes and link them together, making range scans efficient - you find the starting leaf and follow pointers to traverse sequential values.
Almost every RDBMS uses B+ trees for its primary index structure: InnoDB, PostgreSQL, Oracle, SQL Server, and SQLite. The Database Design guide covers index internals in depth.
InnoDB (MySQL)¶
InnoDB is the default storage engine for MySQL and MariaDB. It is a clustered index engine: the table data is physically stored in primary key order within a B+ tree. Secondary indexes store a copy of the primary key value and require a lookup back to the clustered index to retrieve the full row.
Key characteristics:
- Full ACID compliance with row-level locking
- Multi-version concurrency control (MVCC) for non-locking reads
- Write-ahead logging (the redo log) for crash recovery
- The buffer pool caches data and index pages in memory
- Doublewrite buffer prevents torn pages on crash
- Foreign key support
MyISAM (MySQL - Legacy)¶
MyISAM was the default MySQL engine before version 5.5. It uses table-level locking, has no transaction support, and does not enforce foreign keys. MyISAM stores data in a heap file (rows in insertion order) with separate B-tree index files.
MyISAM still exists but is rarely appropriate for new applications. It appears in legacy systems and in MySQL's system tablespace for internal tables (though MySQL 8.0 moved those to InnoDB as well).
MyISAM is not crash-safe
If MySQL crashes while MyISAM is writing data, the table can become corrupted and require repair with myisamchk or REPAIR TABLE. InnoDB's write-ahead log and doublewrite buffer prevent this class of failure. If you encounter MyISAM tables in a legacy system, migrating them to InnoDB is almost always worthwhile.
PostgreSQL's Heap Storage¶
PostgreSQL uses a heap-based storage engine. Table rows are stored in an unordered heap, and all indexes (including the primary key index) are secondary indexes that point to the row's physical location via a tuple identifier (TID - a page number and offset).
Key characteristics:
- MVCC implemented through tuple versioning - old row versions coexist with new ones in the heap
- VACUUM reclaims space from dead tuples left by updates and deletes
- TOAST (The Oversized-Attribute Storage Technique) transparently compresses and out-of-line stores large values
- All indexes are equal - there is no clustered index by default (though
CLUSTERcan reorder the heap once)
LSM-Trees¶
Log-Structured Merge-trees (LSM-trees) optimize for write-heavy workloads. Instead of updating data in place (as B-trees do), LSM-trees write everything sequentially to an in-memory buffer (the memtable), then flush it as sorted immutable files (called SSTables or sorted string tables) to disk. Background processes periodically merge and compact these files.
LSM-trees power:
- RocksDB (developed by Facebook, used as an embedded engine in many systems)
- Cassandra (each node's local storage)
- LevelDB (Google's original implementation)
- MyRocks (an LSM-tree storage engine for MySQL, based on RocksDB)
The trade-off: LSM-trees have faster writes and better space efficiency for write-heavy workloads, but reads can be slower because they may need to check multiple SSTables. Bloom filters are used to skip SSTables that definitely do not contain the requested key.
| Property | B+ Tree (InnoDB, PostgreSQL) | LSM-Tree (RocksDB, Cassandra) |
|---|---|---|
| Write pattern | Random I/O (update in place) | Sequential I/O (append-only) |
| Read pattern | Single lookup (O(log n)) | May check multiple files |
| Write throughput | Moderate | High |
| Read latency | Low and predictable | Higher, varies with compaction |
| Space amplification | Lower (one copy of data) | Higher (multiple copies during compaction) |
| Best for | Read-heavy, OLTP | Write-heavy, time-series, logs |
RDBMS vs. NoSQL: A Decision Framework¶
The choice between a relational database and a NoSQL system is not about which technology is "better." It is about which set of trade-offs fits your workload, consistency requirements, and operational constraints.
When to Choose an RDBMS¶
Relational databases are the right default when:
- Your data has clear relationships. Orders have line items. Customers have addresses. Products belong to categories. The relational model expresses these naturally with foreign keys and joins.
- You need ACID transactions across multiple entities. Transferring funds, placing orders with inventory checks, updating a user and their permissions in one atomic operation - these require multi-statement transactions with rollback.
- Your schema is relatively stable. If you know your entities and their attributes up front and they change slowly, a defined schema protects data quality and enables the optimizer to generate efficient query plans.
- You need ad-hoc queries. SQL is expressive enough to answer questions you did not anticipate when designing the schema. Business intelligence, reporting, and analytics workflows depend on this flexibility.
- Your data fits on a single server (or a small cluster). Most applications never outgrow what a single well-provisioned PostgreSQL or MySQL instance can handle. Vertical scaling is simpler than distributed systems.
When to Choose NoSQL¶
NoSQL systems earn their keep when:
- Your data is semi-structured or schema-less. Product catalogs where each item has different attributes. User-generated content with varying fields. Configuration data that evolves rapidly. Document stores handle this naturally.
- You need horizontal scalability for write-heavy workloads. Time-series data, event logs, IoT sensor data, clickstream analytics - workloads that generate millions of writes per second across distributed nodes.
- Your access patterns are known and narrow. Key-value stores excel when you always look up data by a known key. If 95% of your queries are "get user profile by user_id," a key-value or document store may serve that pattern with lower latency than a relational join.
- Availability trumps consistency. If your system must remain responsive even during network partitions (a global CDN, a shopping cart that should never return an error), an AP system like Cassandra or DynamoDB may be appropriate.
- You need specialized data models. Graph databases for social networks and recommendation engines. Time-series databases for metrics and monitoring. Search engines for full-text queries. These are purpose-built tools, not general-purpose replacements for an RDBMS.
The Hybrid Approach¶
Most production architectures use both. A common pattern:
- PostgreSQL or MySQL as the system of record for transactional data
- Redis as a caching layer and for session storage
- Elasticsearch or OpenSearch for search and log analytics
- A message queue (Kafka, RabbitMQ) for decoupling writes between systems
Start relational, add NoSQL when you have evidence
If you are starting a new project and are unsure which database to use, start with PostgreSQL or MySQL. They are well-documented, widely supported, and handle most workloads. Add specialized NoSQL systems later when you have concrete evidence that a specific workload needs different trade-offs - not because you anticipate scaling problems that may never materialize.
Putting It All Together¶
Further Reading¶
- A Relational Model of Data for Large Shared Data Banks - E.F. Codd (1970) - the paper that started the relational revolution
- Designing Data-Intensive Applications - Martin Kleppmann - the best modern overview of database internals, distributed systems, and data engineering trade-offs
- Use The Index, Luke - Markus Winand - a practical guide to SQL indexing and B-tree internals
- CAP Twelve Years Later: How the "Rules" Have Changed - Eric Brewer - Brewer's own retrospective on the CAP theorem
- MySQL InnoDB Storage Engine Documentation - official reference for InnoDB internals
- PostgreSQL Documentation - Chapter 70: Database Physical Storage - how PostgreSQL organizes data on disk
Next: SQL Essentials | Back to Index