Database Systems

Concepts, Design, and Implementation

Executive Summary
Databases are organized collections of data managed by specialized software (DBMS) to provide efficient
storage, retrieval, and integrity. This report surveys core database concepts: its history (from hierarchical
models of the 1960s to Codd's 1970 relational model), types (relational vs. NoSQL categories), and typical
use cases.
We cover database design methodologies (conceptual/logical/physical modeling), entity–relationship (ER)
diagrams, normalization (1NF through BCNF) with trade-offs in denormalization, plus best practices and
common design pitfalls. The relational model (tables of rows and columns) is explained with keys (primary,
foreign, etc.), constraints (entity, referential, domain), and integrity rules.
Relational algebra operations (select, project, join, union, etc.) are introduced with examples, and relational
calculus (tuple/domain) is described as a declarative query framework. We then explore SQL (Data
Definition, Manipulation, Control, and Transactional languages) with schema creation, joins, subqueries,
aggregation, window functions, transactions, and indexing, illustrated by PostgreSQL code snippets.
Finally, we discuss key DBMS features: ACID transactions, concurrency control (locking, MVCC), isolation
levels (from Read Uncommitted to Serializable), recovery/backup, and performance (indexes, query
optimization). Comparisons are provided (e.g. RDBMS vs. NoSQL, normal forms, index types, isolation levels)
to highlight trade-offs. These topics are supported by authoritative sources and examples to give a rigorous,
introductory yet in-depth overview of database systems.

Learning Objectives
After studying this report, the reader will be able to:
● Understand what a database is and why DBMS are needed — including historical evolution and
current database types (relational vs. NoSQL) and their use cases.
● Explain database design steps: conceptual (ER modeling), logical, and physical schema design, and
be able to draw ER diagrams and interpret them.
● Apply normalization theory: define 1NF–BCNF conditions, perform normalization/decomposition,
and reason about denormalization trade-offs.
● Describe relational model theory: table (relation) structure, keys (primary, foreign, etc.), and
integrity constraints (entity, referential, domain).
● Use relational algebra and calculus: list basic RA operators (σ, π, ⋈, ∪, etc.) with examples, and
contrast procedural RA vs. declarative relational calculus.
● Write and explain SQL: covering DDL (CREATE/ALTER tables), DML
(SELECT/INSERT/UPDATE/DELETE), DCL (GRANT/REVOKE), and TCL (BEGIN/COMMIT/ROLLBACK),
including joins, subqueries, aggregation, and window functions, with sample PostgreSQL code.
● Recognize important DBMS features: understand ACID properties, locking/MVCC concurrency,
standard isolation levels, recovery mechanisms, backup strategies, and indexing types, and their
impact on performance.
Each section below develops these objectives in detail, with definitions, examples, and comparisons.
1. Introduction to Databases
A database is a structured repository of data. Kroenke and Auer define it as “a self-describing collection of
integrated records,” meaning that a database contains both data and metadata (the schema describing the
data). A DBMS (Database Management System) is the software that manages the database, handling tasks
such as data storage, retrieval, updates, security, and concurrency. Popular relational DBMS include Oracle,
MySQL, PostgreSQL, and SQL Server; NoSQL systems include MongoDB, Cassandra, DynamoDB, Neo4j, and
others.
Historically, early data storage (pre-1960s) consisted of flat files and physical records. The 1960s saw the
first computerized databases with hierarchical and network models (e.g. IBM's IMS, CODASYL), where
relationships were navigated via pointers. In 1970, E. F. Codd revolutionized the field by proposing the
relational model, organizing data into tables and basing queries on set theory and first-order logic. The mid-
1970s introduced the Entity–Relationship (ER) model (Chen, 1976) for conceptual design. Relational
prototypes (System R, INGRES, Postgres) led to commercial RDBMS in the 1980s. Since the 2000s, “NoSQL”
databases have emerged (e.g. MongoDB, Cassandra) to handle web-scale, schemaless data.
Figure 1. Components of an Entity–Relationship model (entities, attributes, relationships).

ER diagrams are widely used in conceptual design to map real-world entities (e.g. Student, Course) and their
relationships (e.g. “enrolled in”), abstracting away implementation details.
Database types can be broadly categorized:
● Relational databases (RDBMS) — Store data in tables with a fixed schema (columns) and support
SQL queries. They enforce ACID properties (Atomicity, Consistency, Isolation, Durability) for reliable
transactions. Advantages include strong data integrity, standardized SQL, and mature tooling.
Disadvantages include rigid schemas, difficulty scaling horizontally, and potentially higher overhead
for very large unstructured data sets. They are ideal for structured/transactional workloads (banking
systems, ERP, OLTP).
● NoSQL databases — A family of non-relational stores that allow flexible or dynamic schemas.
Categories include document stores (e.g. JSON documents, like MongoDB), key-value stores (simple
get/put by key, e.g. Redis, DynamoDB), wide-column (column-family) stores (e.g. Cassandra,
HBase), and graph databases (e.g. Neo4j, for relationship-heavy data). NoSQL systems often
sacrifice some ACID guarantees (using eventual consistency or BASE semantics) to gain horizontal
scalability and schema flexibility. They excel at handling large volumes of semi-structured or rapidly
changing data (e.g. IoT data, real-time analytics, social network graphs) where strict schema and
transactions are less critical.
● Object-oriented, NewSQL, and others — For completeness, we note object databases and modern
distributed SQL/NewSQL databases, but the focus here is mainly on RDBMS vs. NoSQL.
A comparison is summarized below:

Feature Relational (RDBMS) NoSQL (Document/KV/Graph/Col)

Schema-less or dynamic schema (JSON

Tables (relations) with fixed columns;
Data Model docs, key-value pairs, column families,
normalized schema
graph nodes/edges)

Flexible: can vary per record, easy to

Schema Strict: defined in DDL (tables, types)
evolve
 Feature Relational (RDBMS) NoSQL (Document/KV/Graph/Col)

Varies: JSON queries, map-reduce,

Query Language Standard SQL (SELECT, JOIN, etc.)
custom APIs, etc.

Often BASE: minimal transactions or

Transactions ACID compliance (by default)
eventual consistency

Designed for horizontal scaling across

Scaling Typically vertical or sharded by DB
many nodes

Big data, high-throughput web apps,

OLTP, complex analytics, financial
Use Cases real-time analytics, flexible schema
systems, classic enterprise apps
scenarios

MongoDB, Cassandra, Redis, Neo4j,

Examples Oracle, SQL Server, PostgreSQL, MySQL
HBase

Use Cases: Relational databases power applications needing strong consistency and complex queries
(banking, airline reservations, inventory systems, data warehouses). NoSQL excels for massive-scale or
unstructured data (e.g. user-generated content, recommendation engines, time-series data).
Overall, databases offer advantages like reduced redundancy, improved data integrity, concurrent multi-
user access, and data sharing. However, they also introduce complexity (administration, cost, potential
performance overhead). Understanding these trade-offs guides the choice of the right type for each
application.

2. Database Design
Data modeling proceeds through stages:
● Conceptual design: Capture high-level entities, attributes, and relationships based on requirements.
Use ER diagrams to represent the domain. Entities (e.g. Student, Course) with key attributes, and
relationships (e.g. enrolls), are identified. This “whiteboard” model ignores implementation details.
● Logical design: Translate the conceptual model into tables, columns, and constraints. Normalize the
model (see below) and define keys. In this stage one specifies data types and constraints (domain
constraints, referential links).
● Physical design: Decide how to implement the logical schema in a specific DBMS. Determine storage
formats, indexes, and partitions, and optimize for performance.
This design process is often visualized as:

Conceptual Design → Logical Design → Physical Design → Implementation →

Maintenance

Successive refinement moves from abstract business requirements to a concrete database schema, and then
to deployment and maintenance. ER diagrams are invaluable in the conceptual stage for modeling data
graphically.
Figure 2. ER model elements — entities (rectangles), attributes (ovals), and relationships (diamonds).
ER Diagrams: An ER diagram shows entities (table-like objects), attributes (fields), and relationships
(associations). For example, a “Student” entity with attributes (StudentID, Name) and a “Course” entity,
linked by an “Enrolled” relationship. Weak entities (dependent on a strong entity) and attribute types (multi-
valued, derived) are part of advanced ER modeling.
Normalization: A key best practice is to normalize tables to eliminate redundancy and update anomalies.
The standard normal forms are:
● 1NF (First Normal Form): Eliminate repeating groups and multi-valued attributes; each column holds
atomic values.
● 2NF: In addition to 1NF, remove partial dependencies on a composite key: every non-key attribute
must depend on the whole primary key, not just part of it.
● 3NF: Satisfy 2NF and remove transitive dependencies: non-key attributes should not depend on
other non-key attributes.
● BCNF (Boyce–Codd Normal Form): A stricter version of 3NF: for every non-trivial functional
dependency X → Y, X must be a superkey.
(See the table below for a concise comparison.)

Normal Form Requirement Example Violation

All columns atomic; no repeating groups; A column “PhoneNumbers” storing

1NF
unique rows. multiple numbers.

A table (StudentID, CourseID,

1NF + no partial dependencies on part of a
2NF Instructor) where Instructor depends
composite key.
only on CourseID (not on StudentID).

A table with (StudentID, DeptID,

DeptName) where DeptName
3NF 2NF + no transitive dependencies.
depends on DeptID (non-key → non-
key).

A table with (StudentID, CourseID →

BCNF 3NF + every determinant is a superkey. Instructor) but neither StudentID nor
CourseID alone is a key.

Benefits of normalization include reduced duplicate data and better integrity. However, over-normalization
can lead to many joins and slower reads. Hence denormalization (intentionally relaxing normal form) is
sometimes used for performance (e.g. in data warehouses). Denormalization trades storage space for faster
read queries by pre-joining or duplicating some data.
Design Best Practices and Pitfalls: Good design starts with careful planning and documentation. Common
recommendations include:
● Plan thoroughly: Define main entities, relationships, and constraints before coding. Draw ER
diagrams to clarify requirements.
● Use clear naming conventions: Avoid cryptic or inconsistent names for tables/columns. Meaningful
names improve maintainability.
 ● Enforce integrity: Define primary keys, foreign keys, and necessary constraints (UNIQUE, NOT NULL,
CHECK) to preserve data correctness.
● Normalize appropriately: Apply normalization rules at least to 3NF to eliminate obvious
redundancy. Beware of anomalies from unnormalized designs.
● Document the schema: Keep an updated data dictionary. This prevents confusion for future
developers.
● Avoid redundancy: Don't duplicate data across tables unless denormalization is justified.
● Iterate: Expect to refine the model after initial implementation; use version control for schema
changes.
Common pitfalls to avoid include ignoring normalization (leading to inconsistent duplicates), poor planning
of table structures, redundant records, and lack of documentation. Adhering to solid design principles yields
databases that are easier to implement and maintain over time.

3. The Relational Database Model

The relational model (Codd, 1970) is built on mathematical relations (tables). A relation is a table with rows
(tuples) and columns (attributes). Each row is a unique tuple of values, and each column has a name and a
domain (set of allowed values). Key concepts:
● Relation (table): A set of tuples. E.g. a Students relation has schema (StudentID, Name, Age, Dept)
and contains one row per student.
● Attribute (column): A named field in a relation. E.g. StudentID or Name. Each attribute has a
domain (e.g. integer, text, etc.).
● Tuple (row): One record in a table, an ordered list of attribute values. In Students, one tuple might
be (123, “Alice”, 20, “CS”).
● Schema: The structure of a relation (its name and set of attributes).
● Instance (state): The set of current tuples in a table at a point in time.
● Degree: The number of attributes (columns) in a relation.
● Cardinality: The number of tuples (rows).
Keys and Constraints: A key is an attribute or set of attributes that uniquely identifies a tuple. Common key
types:
● Primary Key: The chosen candidate key for a table; no two rows can have the same PK, and it must
be NOT NULL (entity integrity). E.g. StudentID uniquely identifies students.
● Candidate Key: A minimal set of columns that uniquely identifies a row. A table may have multiple
candidate keys (one becomes the primary key).
● Composite Key: A key consisting of more than one attribute, e.g. (StudentID, CourseID) for an
enrollment table.
● Superkey: Any superset of a candidate key that still uniquely identifies tuples.
● Foreign Key: An attribute (or set) in one table that references the primary key of another table,
enforcing a relationship. E.g. DeptID in Students may be a FK referencing the Departments table.
 ● Referential Integrity: Foreign key values must match existing primary key values in the referenced
table (or be NULL). This prevents orphaned references: you cannot delete a referenced PK row if
dependents exist, and you cannot insert an FK value not present as a PK.
● Domain Constraint: Each attribute's value must come from its domain/type (e.g. an Age column
must be a positive integer).
● Entity Integrity: The primary key cannot be NULL, ensuring each row is identifiable.
● Key Constraint: All values of a key attribute must be unique and non-null.
These constraints are enforced by the DBMS to ensure data validity and prevent anomalies.
Relational Algebra: A foundational formal query language for relational databases, using set-based
operators. Key operators include:
● Selection (σ): Filter rows by a condition. E.g. σₐᴳᵉ > ²⁵(Students) yields all student tuples with Age >
25. (Corresponds to SQL SELECT * FROM Students WHERE Age > 25.)
● Projection (π): Choose columns (attributes). πName,Dept(Students) returns a relation with just the
Name and Dept columns. (SQL: SELECT Name, Dept FROM Students.)
● Cross Product (×): Cartesian product of two relations.
● Union (∪), Intersection (∩), Set Difference (−): Combine or compare relations (must have the same
schema).
● Join (⋈): Combines related tuples from two relations (natural join or using a condition). E.g.
Students ⋈ Enrollments on StudentID matches students with their enrollments. (SQL uses JOIN.)
● Rename (ρ): Rename a relation or its attributes.
For example: given a STUDENT table (SID, S_Name, S_Age, S_State), the expression σ(S_Age > 25)(STUDENT)
filters rows where age is greater than 25. Projection π(S_Name, S_State)(STUDENT) returns only the name
and state columns of each student. Joins combine tables via matching keys.
Relational algebra is procedural: one specifies step-by-step how to obtain results. Its power is equivalent to
SQL's capabilities (RA is “relationally complete”), but SQL is more expressive in practice (e.g. recursion in
SQL:1999 or user-defined functions).
Relational Calculus: A non-procedural (declarative) formal query language, based on predicate calculus.
Queries describe what to retrieve, not how. There are two variants:
● Tuple Relational Calculus (TRC): Variables represent tuples. E.g. { t | t ∈ STUDENT ∧ [Link]
> 25 } describes the set of student tuples with age greater than 25.
● Domain Relational Calculus (DRC): Variables range over attribute domains. E.g. { <n,s> | ∃a
( <a,n,s> ∈ STUDENT ∧ a > 25 ) } yields the name and state of students with age greater
than 25.
Both allow expressing queries declaratively. Codd's Theorem shows that for safe queries, relational calculus
and algebra have the same expressive power. Notably, SQL's syntax and subquery logic are heavily
influenced by relational calculus principles.

4. Formal Query Languages: Algebra & Calculus

Relational algebra and calculus underpin modern query languages. Relational Algebra (RA) (see operators
above) is fundamental to query execution: a DBMS typically translates SQL into RA plans for optimization. RA
operators can be combined (e.g. project after select, then join). For instance, the join of Students and
Enrollments can be written as σ([Link] = [Link])(Students × Enroll).
Relational Calculus (RC) is purely declarative — queries define desired properties rather than retrieval steps.
TRC and DRC queries evaluate to relations. The key difference is that in calculus you specify what to find (like
logic formulas with ∃, ∀) without prescribing the retrieval steps. For example, to find student names over 25
in TRC:

{ [Link] | STUDENT(s) ∧ [Link] > 25 }

That reads: “the set of names [Link] where s is a student tuple with age greater than 25.”
In terms of complexity and expressiveness, both RA and RC capture all “relationally computable” queries
(modulo safety): they are equivalent by Codd's theorem. SQL is generally “relationally complete”: anything
expressible in RA/RC can be done in SQL, plus more advanced features. In practice, these formal query
semantics ensure SQL queries can be reasoned about rigorously.

5. SQL: The Standard Query Language

SQL (Structured Query Language) implements relational concepts. It is divided into four sub-languages:

Data Definition Language (DDL)

Commands to define or alter schema, for example:

CREATE TABLE employees (

emp_id SERIAL PRIMARY KEY,
first_name TEXT NOT NULL,
last_name TEXT,
dept_id INT,
hire_date DATE
);

This creates a new table with a primary key, column types, and constraints. ALTER and DROP are also DDL
commands.

Data Manipulation Language (DML)

Commands to query and modify data: SELECT, INSERT, UPDATE, DELETE. For example:

INSERT INTO employees (first_name, last_name, dept_id)

VALUES ('Alice', 'Smith', 10),
('Bob', 'Jones', 20);

SELECT e.first_name, [Link]

FROM employees AS e
JOIN departments AS d ON e.dept_id = d.dept_id
WHERE e.hire_date >= '2023-01-01';

This SELECT uses an INNER JOIN between employees and departments. Other join types (LEFT, RIGHT,
FULL) retrieve unmatched rows as needed. Subqueries can also be used, e.g.:
 SELECT name FROM employees
WHERE dept_id = (
SELECT dept_id FROM departments WHERE name = 'Sales'
);

Data Control Language (DCL)

Commands like GRANT and REVOKE manage permissions and security.

Transaction Control Language (TCL)

Commands to manage transactions:

BEGIN;
UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 12345;
UPDATE accounts SET balance = balance + 100.00 WHERE acctnum = 7534;
COMMIT;

(Or ROLLBACK to abort.) The example above transfers $100 between accounts in one atomic transaction.

Aggregation and Window Functions

SQL supports GROUP BY aggregations and advanced analytic functions. Example:

SELECT department,
COUNT(*) AS num_emp,
AVG(salary) AS avg_sal
FROM employees
GROUP BY department;

Window functions operate over partitions without collapsing rows. For example:

SELECT first_name, dept_id, salary,

RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS dept_rank
FROM employees;

This computes each employee's rank by salary within their department.

Indexes
SQL provides DDL for indexes to speed up queries, e.g.:

CREATE INDEX idx_emp_dept ON employees(dept_id);

CREATE INDEX idx_emp_name ON employees(first_name, last_name);

The database automatically uses indexes to optimize data access. Different index types exist (see the Index
Types table in Section 6).

Sample Query Walkthrough

Consider the following SQL query:

SELECT [Link], o.order_date, [Link]

FROM customers AS e
 JOIN orders AS o ON e.customer_id = o.customer_id
WHERE [Link] > 100
ORDER BY o.order_date DESC;

● Step 1 (FROM/JOIN): Combine customers and orders where IDs match.

● Step 2 (WHERE): Filter joined rows to those with amount > 100.
● Step 3 (SELECT): Project only [Link], o.order_date, [Link].
● Step 4 (ORDER BY): Sort results by order_date, descending.
A DBMS execution planner will translate this into an optimized plan (possibly using an index on
[Link] or customer_id) to retrieve rows efficiently.

Performance Tips
Use indexes on columns used in JOINs, WHERE, and ORDER BY clauses. Avoid SELECT * on large tables.
Analyze query plans (EXPLAIN ANALYZE in PostgreSQL) to spot slow scans. Denormalize or cache results
judiciously for heavy read workloads.

6. Important DBMS Features

ACID Transactions: A DBMS ensures reliable transactions using the ACID properties: Atomicity (all-or-
nothing), Consistency (maintaining integrity rules), Isolation (transactions don't interfere incorrectly), and
Durability (committed data survives crashes). For example, the two UPDATEs in a funds transfer are atomic:
both succeed or both roll back.
Concurrency Control: To support multiple simultaneous users, a DBMS employs locking and/or multi-
versioning:
● Locking: Traditional DBMS use locks (table-level, row-level) to prevent conflicting operations. Shared
locks allow concurrent reads; exclusive locks prevent conflicts on writes.
● MVCC (Multi-Version Concurrency Control): PostgreSQL (and others) use MVCC to avoid most
read–write conflicts. When a transaction updates a row, the old version is kept for any transactions
that have already read it, so reads do not block writes and vice versa. Only when committing does
the DBMS make the new version visible. This yields good concurrency and snapshot isolation —
readers always see a consistent snapshot from their transaction's start time.
Isolation Levels: ANSI SQL defines four levels. They control phenomena like dirty reads, non-repeatable
reads, and phantom reads. (PostgreSQL implements three levels internally: Read Uncommitted ≈ Read
Committed, Repeatable Read, and Serializable.) The table below compares them:

Non-repeatable Serialization
Isolation Level Dirty Reads? Phantom Reads?
Reads? Anomaly?

Read Uncommitted Allowed Possible Possible Possible

Read Committed Not allowed Possible Possible Possible

Allowed (not in
Repeatable Read Not allowed Not allowed Possible
PostgreSQL)

Serializable Not allowed Not allowed Not allowed Not allowed

PostgreSQL's default is Read Committed. At this level, each query in a transaction sees a snapshot of data
committed before that query began. Repeatable Read provides a transaction-wide snapshot (so re-reading
yields the same rows). Serializable is the strictest level: it ensures transactions appear as if executed in some
serial order.
Recovery and Backup: A DBMS uses logging (e.g. PostgreSQL's Write-Ahead Log, WAL) to recover from
crashes. On restart, the log replays committed transactions and undoes partial ones. Regular backups (e.g.
pg_dump or file-system snapshots) enable full restoration. Most systems support point-in-time recovery via
logs.
Indexing: To speed up access, a DBMS offers various index types. PostgreSQL provides B-tree, Hash, GiST,
SP-GiST, GIN, and BRIN (plus Bloom as an extension). Each suits different data:

Index Type Description Typical Use Case

Balanced-tree index. Handles equality General-purpose indexing for

B-tree (default) and range queries (=, <, >, BETWEEN, columns used in WHERE, ORDER
prefix LIKE). BY, join keys.

Indexing columns with only

Hash-based index (PostgreSQL 10+,
Hash equality comparisons. (Limited
equality only).
use; B-tree often covers this.)

Spatial/geometric types (PostGIS),

GiST (Generalized Framework for custom index strategies
text search (with extensions), any
Search Tree) (e.g. 2D range, nearest-neighbor).
data with range queries.

SP-GiST (Space- Supports non-balanced structures Spatial data (points), prefix

partitioned GiST) (quadtrees, k-d trees, tries). searches, text search via tries.

Multi-valued fields: arrays, JSONB

GIN (Generalized Inverted index; each row value maps to
keys, full-text search (word →
Inverted Index) multiple index entries.
documents).

Extremely large tables with

BRIN (Block Range Summarizes ranges of pages; very small
naturally ordered data
Index) index.
(timestamps, IDs).

When many columns need

Probabilistic bitmaps; multi-column,
Bloom (extension) indexing with moderate false
space-efficient.
positives (rare use case).

A B-tree index is the go-to choice for most use cases; GIN/GiST are for specialized queries, and BRIN is for
very large append-only logs. (Use the USING clause in CREATE INDEX to specify the type.)
Query Optimization: Modern DBMS use a cost-based query planner. They estimate costs (based on table
statistics and hardware parameters) for various execution plans (join orders, index usage) and pick the
cheapest plan. For example, PostgreSQL assigns “page cost” values to sequential vs. random reads and uses
statistics (histograms, table cardinality) to estimate selectivity. Good practices include updating statistics
(ANALYZE), using indexed columns, and writing queries that allow index usage. The EXPLAIN command in
PostgreSQL shows the chosen plan; a DBA can tune parameters or add indexes if, say, an expensive
sequential scan is used.
In summary, a DBMS provides much more than simple file storage: it enforces integrity rules, manages
concurrent transactions, and optimizes query execution. Understanding these features — ACID,
locking/MVCC, isolation, logging, and indexing — is key to using and tuning database systems effectively.