Databases

Learning Objectives

  • Define what a database and a Database Management System (DBMS) are.
  • Distinguish between Relational (SQL) and Non-Relational (NoSQL) database paradigms, including CAP theorem principles.
  • Understand core relational concepts like Primary, Foreign, and Composite Keys, and common database constraints.
  • Explain the ACID properties (Atomicity, Consistency, Isolation, Durability) and the role of transaction logs.
  • Describe the process and goals of database normalization (1NF, 2NF, 3NF).
  • Understand the basics of SQL querying (SELECT, INSERT, UPDATE, DELETE, JOIN).
  • Explain how indexing works using B-Trees and its impact on performance.

A comprehensive guide to Database Management Systems, SQL vs. NoSQL paradigms, relational algebra, ACID properties, Normalization (1NF, 2NF, 3NF), and Indexing.

Database

A Database is an organized collection of structured or unstructured data, typically stored electronically in a computer system. It is managed by a Database Management System (DBMS), which acts as the software interface allowing users and applications to securely create, read, update, and delete (CRUD) the data.

Schema

A Schema is the logical structure or blueprint of a database. It defines how data is organized, what tables exist, the fields within those tables, and the relationships between them.

Query

A Query is a precise request for information or for an action to be performed on data within a database, typically written in a standardized query language like SQL.

1. Types of Databases: SQL vs. NoSQL

The two primary paradigms for storing data are Relational (SQL) and Non-Relational (NoSQL). Choosing between them depends entirely on the structure of your data and how it needs to scale.

1.1 Relational Databases (SQL)

Data is stored in highly structured Tables (Relations) consisting of rows (records) and columns (attributes). Tables are strictly linked together using Primary and Foreign Keys to form complex relationships. Examples: MySQL, PostgreSQL, Oracle, Microsoft SQL Server.

  • Rigid Schema: You must define exactly what data type (integer, string, date) goes into each column before inserting any data. If you want to add a new attribute (like "MiddleName") later, you must alter the entire table structure.

  • ACID Compliance: Guarantees strong data integrity and absolute reliability for complex, multi-step transactions (like financial bank transfers).

  • Vertical Scaling (Scale-Up): Primarily scales by increasing the horsepower of a single server (buying a bigger, more expensive server with more RAM/CPU). Distributing a relational database across many servers is complex.

1.2 Non-Relational Databases (NoSQL)

Data is stored in flexible formats, often as JSON-like documents, key-value pairs, wide-columns, or graph nodes, rather than strict tables. Examples: MongoDB (Document), Redis (Key-Value), Cassandra (Wide-Column), Neo4j (Graph).

  • Dynamic Schema: Schema-less design. You can insert varied data structures into the same collection without altering the database. One user document might have a "phone_number" field, while another does not.

  • Horizontal Scaling (Scale-Out): Designed from the ground up to scale horizontally by adding cheaper, commodity servers to distribute the load across a massive cluster. Perfect for massive, unstructured Big Data and real-time web apps.

  • BASE Properties: Often trades strict ACID consistency for higher availability and performance (Basically Available, Soft state, Eventual consistency).

The CAP Theorem

Consistency means reads reflect the latest successful write under the model being discussed; availability means each request to a non-failed node receives a response; partition tolerance concerns continued operation despite lost or delayed network messages. During a partition, a distributed service cannot guarantee both linearizable consistency and availability for every operation. “Choose two” is shorthand, not a literal guarantee for every system in all conditions.

2. Core Relational Concepts

Relational databases rely on specific keys and constraints to mathematically organize and link data across multiple tables.

Key Types:

  • Primary Key (PK): A column (or combination of columns) that uniquely identifies every single row in a table. It must be unique and cannot be NULL. (e.g., A StudentID, a SocialSecurityNumber, or an auto-incrementing integer ID).

  • Foreign Key (FK): A column in one table that specifically references the Primary Key of another table. This creates the relational link between the tables, enforcing referential integrity. (e.g., An Orders table has a CustomerID column linking back to the Customers table).

  • Composite Key: A Primary Key that consists of two or more columns combined to create a unique identifier (often used in linking tables for Many-to-Many relationships).

Common Database Constraints:

  • UNIQUE: Ensures all values in a column are different.
  • NOT NULL: Ensures a column cannot have a NULL value.
  • CHECK: Ensures values in a column satisfy a specific condition.
  • DEFAULT: Provides a default value for a column when none is specified.

Transaction

A Transaction is a logical unit of work that contains one or more SQL statements (e.g., deducting money from Account A, and adding it to Account B).

3. The ACID Properties

Database systems use ACID as a framework for reliable transaction processing. The guarantees a particular system provides depend on its implementation, configured durability, and selected isolation level.

  • Atomicity ("All or Nothing"): A transaction is treated as one unit: its intended updates are committed together or discarded together if the transaction is rolled back or aborted.

  • Consistency: A successful transaction must preserve the database constraints and application invariants actually enforced by constraints, triggers, or application logic. A DBMS cannot infer every business rule automatically.

  • Isolation: Isolation controls how concurrent transactions interact. Its guarantees depend on the selected isolation level: serializable execution is equivalent to some serial order, while weaker levels can permit specified anomalies.

  • Durability: After a commit is acknowledged, committed changes should survive failures under the database's configured durability guarantees. Many systems use transaction logs or equivalent recovery mechanisms; the actual guarantee depends on the DBMS and storage configuration.

Related database updates share a transaction outcome

Before the transaction, project P-104 has inspection_count = 2 and inspection I-053 is absent. While pending, this transaction sees count = 3 and the inserted row. Rollback discards both writes, returning to count = 2 with I-053 absent; commit retains both, leaving count = 3 with I-053 present. These are illustrative logical states: concurrent visibility depends on the DBMS and isolation level, and durability depends on configured guarantees.

A four-column state comparison shows an inspection row and project count before a transaction, while writes are pending, after rollback, and after commit. Both related writes are discarded together on rollback or retained together on commit.

Normalization

Normalization is the systematic process of organizing data in a relational database to reduce data redundancy (duplicate data) and improve data integrity. It involves breaking large, messy tables into smaller, tightly-related tables and defining relationships between them.

The Normalization Process

  1. First Normal Form (1NF): Define attributes so each value is atomic for the application's chosen domain; do not store repeating groups or lists as one value. A phone-number list, for example, may need a related table keyed to its owner.
  2. Identify dependencies and keys: Record the functional dependencies implied by the business rules. Determine the candidate keys; a prime attribute belongs to at least one candidate key.
  3. Second Normal Form (2NF): The relation must be in 1NF, and no non-prime attribute may depend on a proper subset of any candidate key. This issue can occur with composite candidate keys. Decompose partial dependencies and retain the determinant in the related relation.
  4. Third Normal Form (3NF): For every nontrivial functional dependency X→AX → A (one attribute on the right), either XX is a superkey or AA is prime. “No transitive dependency” is an introductory shorthand; the superkey-or-prime test is the general criterion. If decomposition is needed, standard synthesis from a minimal cover can produce a lossless, dependency-preserving 3NF design; recheck the resulting relations and dependencies.
Normalize Relations Through Third Normal Form

Test atomic values, key dependencies, and the formal 3NF condition; decompose and recheck when required.

Start from complete, consistent, agreed business rules and functional dependencies, not sample rows alone. Defer normalization if those requirements remain unresolved. A prime attribute belongs to at least one candidate key. The general 3NF test checks every nontrivial functional dependency X→A: X is a superkey or A is prime. When synthesis is needed, the standard minimal-cover 3NF synthesis yields a lossless-join, dependency-preserving decomposition; verify the assumptions and resulting relation schemas.

Normalize Relations Through Third Normal FormTest atomic values, key dependencies, and the formal 3NF condition; decompose and recheck when required.. Start from complete, consistent, agreed business rules and functional dependencies, not sample rows alone. Defer normalization if those requirements remain unresolved. A prime attribute belongs to at least one candidate key. The general 3NF test checks every nontrivial functional dependency X→A: X is a superkey or A is prime. When synthesis is needed, the standard minimal-cover 3NF synthesis yields a lossless-join, dependency-preserving decomposition; verify the assumptions and resulting relation schemas.. Start normalization → List attributes, value domains, business rules, and FDs; List attributes, value domains, business rules, and FDs → Are the rules and FDs complete, consistent, and agreed?; Are the rules and FDs complete, consistent, and agreed? — Yes → Are values atomic for the chosen domain?; Are the rules and FDs complete, consistent, and agreed? — No → Defer: clarify unresolved rules or FDs; Are values atomic for the chosen domain? — Yes → Determine candidate keys; mark prime attributes; Are values atomic for the chosen domain? — No → Separate repeating or multivalued facts into keyed relations; Separate repeating or multivalued facts into keyed relations → List attributes, value domains, business rules, and FDs; Determine candidate keys; mark prime attributes → Any partial dependency to a non-prime attribute?; Any partial dependency to a non-prime attribute? — Yes → Decompose the partial dependency; retain its determinant; Any partial dependency to a non-prime attribute? — No → Does each functional dependency meet the 3NF test?; Decompose the partial dependency; retain its determinant → List attributes, value domains, business rules, and FDs; Does each functional dependency meet the 3NF test? — Yes → Keep the relations that already satisfy 3NF; Does each functional dependency meet the 3NF test? — No → Apply minimal-cover 3NF synthesis; include a key relation if needed; Keep the relations that already satisfy 3NF → Do the relations and decomposition checks pass?; Apply minimal-cover 3NF synthesis; include a key relation if needed → Do the relations and decomposition checks pass?; Do the relations and decomposition checks pass? — Yes → Accept the verified 3NF design; Do the relations and decomposition checks pass? — No → Correct the failed check or decomposition; then recheck; Correct the failed check or decomposition; then recheck → List attributes, value domains, business rules, and FDs

Start normalization → List attributes, value domains, business rules, and FDs; List attributes, value domains, business rules, and FDs → Are the rules and FDs complete, consistent, and agreed?; Are the rules and FDs complete, consistent, and agreed? — Yes → Are values atomic for the chosen domain?; Are the rules and FDs complete, consistent, and agreed? — No → Defer: clarify unresolved rules or FDs; Are values atomic for the chosen domain? — Yes → Determine candidate keys; mark prime attributes; Are values atomic for the chosen domain? — No → Separate repeating or multivalued facts into keyed relations; Separate repeating or multivalued facts into keyed relations → List attributes, value domains, business rules, and FDs; Determine candidate keys; mark prime attributes → Any partial dependency to a non-prime attribute?; Any partial dependency to a non-prime attribute? — Yes → Decompose the partial dependency; retain its determinant; Any partial dependency to a non-prime attribute? — No → Does each functional dependency meet the 3NF test?; Decompose the partial dependency; retain its determinant → List attributes, value domains, business rules, and FDs; Does each functional dependency meet the 3NF test? — Yes → Keep the relations that already satisfy 3NF; Does each functional dependency meet the 3NF test? — No → Apply minimal-cover 3NF synthesis; include a key relation if needed; Keep the relations that already satisfy 3NF → Do the relations and decomposition checks pass?; Apply minimal-cover 3NF synthesis; include a key relation if needed → Do the relations and decomposition checks pass?; Do the relations and decomposition checks pass? — Yes → Accept the verified 3NF design; Do the relations and decomposition checks pass? — No → Correct the failed check or decomposition; then recheck; Correct the failed check or decomposition; then recheck → List attributes, value domains, business rules, and FDs

  • Start normalization: terminator
  • List attributes, value domains, business rules, and FDs: process
  • Are the rules and FDs complete, consistent, and agreed?: decision
  • Defer: clarify unresolved rules or FDs: terminator
  • Are values atomic for the chosen domain?: decision
  • Separate repeating or multivalued facts into keyed relations: process
  • Determine candidate keys; mark prime attributes: process
  • Any partial dependency to a non-prime attribute?: decision. A partial dependency is from a proper subset of any candidate key to a non-prime attribute.
  • Decompose the partial dependency; retain its determinant: process
  • Does each functional dependency meet the 3NF test?: decision. For each nontrivial X→A, X must be a superkey or A must be prime.
  • Keep the relations that already satisfy 3NF: process
  • Apply minimal-cover 3NF synthesis; include a key relation if needed: process
  • Do the relations and decomposition checks pass?: decision. All relations satisfy 3NF, the decomposition is lossless-join, and it preserves dependencies.
  • Correct the failed check or decomposition; then recheck: process. If the business rules or FDs cannot be resolved, the input check routes to Defer.
  • Accept the verified 3NF design: terminator

The Goal of Normalization

The goal is to reduce redundancy and prevent insertion, update, and deletion anomalies while preserving the meaning of the data. Each relation should be assessed against all candidate keys and functional dependencies; a primary key is one chosen candidate key, not necessarily the only one.

5. Structured Query Language (SQL)

SQL is the standard programming language used to communicate with, manage, and query Relational Databases.

  • SELECT (Read): Retrieves data from a database. (e.g., SELECT FirstName, LastName FROM Users WHERE Age > 18 ORDER BY LastName;)

  • INSERT (Create): Adds new rows (records) into a table.

  • UPDATE (Update): Modifies existing data within specific rows based on a WHERE condition.

  • DELETE (Delete): Removes specific rows from a table based on a WHERE condition.

  • JOIN: The most powerful feature of SQL. It dynamically combines rows from two or more separate tables based on a related column (usually Primary/Foreign keys) to return a unified dataset.

Primary and foreign keys connect project and inspection rows

The sample tables show a one-to-many relation: each inspection's ProjectID references an existing project key, and the join matches rows on that value. Project P-104 joins to inspections I-031 (Reviewed) and I-044 (Pending); P-208 joins to I-052 (Reviewed). The result has one row per matching inspection. All names and IDs are illustrative, not actual project records.

A project table marks ProjectID as its primary key; an inspection table marks ProjectID as a foreign key referencing it; a labeled join produces one result row per matching inspection.

Interact with the simulation below to see how basic SQL SELECT queries filter the data returned from a table.

SQL Queries

SQL> SELECT * FROM Employees;

Result Set: Employees Table

IDNameDeptSalary
1AliceHR$55,000
2BobIT$75,000
3CharlieIT$82,000
4DianaSales$60,000
4 row(s) returned

6. Indexing and Performance

An index is an auxiliary data structure, often a B-tree, that can accelerate queries whose search or ordering conditions match the index. Indexes use storage and add maintenance work when relevant rows or key values change. The query planner decides whether an index is useful for a particular query.

How Indexing Works

Without a useful index, a query may require a table scan that examines many rows. A suitable B-tree index lets the database navigate ordered keys to locate candidate rows, but the query planner may still choose a scan. Actual cost depends on table size, data distribution, selectivity, statistics, and the database system.

The Trade-off: Indexes consume storage and must be maintained when relevant rows or indexed key values change; ordinary inserts and updates do not rebuild the entire index from scratch. Creating unnecessary indexes can add write and maintenance cost.

A B-tree index narrows a key search

The root separators are I-040 and I-070. A search for I-053 follows the middle range, I-040 ≤ key < I-070, to the candidate row; keys below I-040 follow the lower range, and keys at or above I-070 follow the upper range. The values and page arrangement are illustrative, not PostgreSQL's physical page layout or a benchmark. The query planner may select another plan; index maintenance and storage are part of the trade-off.

A schematic B-tree has ordered separator keys in a root node and three leaf pages. A highlighted route for inspection I-053 follows the middle range to a candidate row location.
Key Takeaways
  • Relational databases use defined relations and support expressive queries and joins; transaction guarantees depend on the DBMS, enforced constraints, isolation level, and durability configuration.
  • Document and key-value databases can support flexible data models and scale-out designs; suitability and scaling depend on the specific system, workload, and consistency requirements.
  • During a network partition, CAP describes a trade-off between strong consistency and availability for affected operations; “choose two” is only shorthand.
  • Primary keys guarantee row uniqueness within a single table.
  • Foreign keys mathematically link tables together, preventing orphan records (referential integrity).
  • ACID describes transaction properties; the guarantees depend on the DBMS, its settings, and its isolation level.
  • Normalization organizes schemas to reduce data redundancy and prevent anomalies during database modifications.
  • 1NF requires values atomic for the chosen domain. 2NF excludes partial dependencies of non-prime attributes on candidate keys. 3NF requires each nontrivial dependency to have a superkey determinant or a prime dependent attribute.
  • SQL provides standardized commands (SELECT, INSERT, UPDATE, JOIN) to query and manipulate relational data.
  • A suitable index can reduce lookup work, but the query planner chooses whether to use it; indexes add storage and write-maintenance costs.

References