Database Management Systems: Normalization and SQL Optimization Lab

Learning Objectives

By the end of this lab, you will be able to:

  • Identify repeating groups, partial dependencies and transitive dependencies in a business spreadsheet.
  • Normalize a table step by step to 1NF, 2NF and 3NF, and explain what BCNF adds.
  • Write CREATE TABLE statements with primary keys, foreign keys and constraints, then load sample data.
  • Answer business questions with JOINs, GROUP BY and subqueries.
  • Read SQLite’s EXPLAIN QUERY PLAN output and use indexes, sargable WHERE clauses, column selection, batching and keyset pagination to make queries faster.

Before You Start

This lab builds on 5.4 Database Management Systems, 5.5 Relational Databases (tables, primary and foreign keys) and 5.6 Introduction to SQL (SELECT, INSERT, UPDATE, DELETE). Those notes explain what a relational database is. This lab is hands-on: you will design one and then make it fast.

Software (free): We use SQLite, a database engine stored in a single file. You can run every statement in any of these:

  • Python (already includes SQLite through the built-in sqlite3 module; no installation needed). The outputs in this note were produced with Python 3.11 and SQLite 3.53.1.
  • The sqlite3 command-line shell from sqlite.org/download.html.
  • DB Browser for SQLite, a free graphical tool.

All names, phone numbers, publishers, prices and orders below are hypothetical teaching data. Book titles and authors are real Nepali literature, used only as product names.

Part A: Normalization, Step by Step

A.1 The Starting Point: An Unnormalized Spreadsheet

Pustak Ghar, a small bookshop in Kathmandu, keeps orders in one spreadsheet. Each order is one row, and the books in it are typed into a single cell.

OrderID OrderDate Customer Phone Area Books (Title, Author, Publisher, City, Qty, Price)
1001 2026-09-01 Sita Shrestha 9841000001 Baneshwor Muna Madan, Devkota, Sagarmatha Books, Kathmandu, 2, 250; Palpasa Cafe, Wagle, Bagmati Press, Lalitpur, 1, 450
1002 2026-09-01 Ram Thapa 9851000002 Patan Karnali Blues, Buddhisagar, Bagmati Press, Lalitpur, 1, 550
1003 2026-09-02 Sita Shrestha 9841000001 Baneshwor Seto Dharti, Neupane, Sagarmatha Books, Kathmandu, 1, 500
1004 2026-09-03 Anita Gurung 9801000003 Thamel Muna Madan, …, 1, 250; Shirishko Phool, Parijat, Sagarmatha Books, Kathmandu, 1, 350; Karnali Blues, …, 1, 550
1005 2026-09-05 Bikash Rai 9861000004 Baneshwor Palpasa Cafe, Wagle, Bagmati Press, Lalitpur, 2, 420

Problems a manager will hit with this sheet:

  • Cannot query easily: “How many copies of Muna Madan did we sell?” requires reading text inside cells.
  • Update anomaly: if Sita changes her phone number, it must be changed in every row she appears in. Miss one and the data disagree.
  • Insertion anomaly: a new book (say Sumnima by B. P. Koirala) cannot be recorded until someone orders it.
  • Deletion anomaly: delete order 1003 (perhaps it was cancelled) and the shop loses its only record that it stocks Seto Dharti at NPR 500.

Normalization is the process of splitting such a table into smaller, related tables so that each fact is stored once. Each “normal form” removes one kind of problem.

A.2 First Normal Form (1NF): One Value per Cell

Rule: every cell holds a single (atomic) value, there are no repeating groups, and each row is uniquely identified by a key.

Fix: give each book in an order its own row.

OrderID BookTitle OrderDate Customer Phone Area Author Publisher PubCity Qty UnitPrice
1001 Muna Madan 2026-09-01 Sita Shrestha 9841000001 Baneshwor Laxmi Prasad Devkota Sagarmatha Books Kathmandu 2 250
1001 Palpasa Cafe 2026-09-01 Sita Shrestha 9841000001 Baneshwor Narayan Wagle Bagmati Press Lalitpur 1 450
1002 Karnali Blues 2026-09-01 Ram Thapa 9851000002 Patan Buddhisagar Bagmati Press Lalitpur 1 550
1003 Seto Dharti 2026-09-02 Sita Shrestha 9841000001 Baneshwor Amar Neupane Sagarmatha Books Kathmandu 1 500
1004 Muna Madan 2026-09-03 Anita Gurung 9801000003 Thamel Laxmi Prasad Devkota Sagarmatha Books Kathmandu 1 250
1004 Shirishko Phool 2026-09-03 Anita Gurung 9801000003 Thamel Parijat Sagarmatha Books Kathmandu 1 350
1004 Karnali Blues 2026-09-03 Anita Gurung 9801000003 Thamel Buddhisagar Bagmati Press Lalitpur 1 550
1005 Palpasa Cafe 2026-09-05 Bikash Rai 9861000004 Baneshwor Narayan Wagle Bagmati Press Lalitpur 2 420

Primary key: the combination (OrderID, BookTitle). In practice titles are not unique, so we will give each book a BookID (a surrogate key). The key becomes (OrderID, BookID).

The table is now in 1NF, but the duplication is worse: Sita’s details appear three times.

A.3 Second Normal Form (2NF): No Partial Dependencies

Rule: the table is in 1NF and every non-key column depends on the whole primary key, not just part of it. (This only matters when the key has two or more columns.)

Ask of each column: “Do I need both OrderID and BookID to know this?”

Column Depends on Type of dependency
OrderDate, Customer, Phone, Area OrderID only Partial
Title, Author, Publisher, PubCity BookID only Partial
Qty, UnitPrice OrderID and BookID Full

Fix: move each partial dependency into its own table.

Orders (key: OrderID)

OrderID OrderDate Customer Phone Area
1001 2026-09-01 Sita Shrestha 9841000001 Baneshwor
1002 2026-09-01 Ram Thapa 9851000002 Patan
1003 2026-09-02 Sita Shrestha 9841000001 Baneshwor
1004 2026-09-03 Anita Gurung 9801000003 Thamel
1005 2026-09-05 Bikash Rai 9861000004 Baneshwor

Books (key: BookID)

BookID Title Author Publisher PubCity ListPrice
1 Muna Madan Laxmi Prasad Devkota Sagarmatha Books Kathmandu 250
2 Shirishko Phool Parijat Sagarmatha Books Kathmandu 350
3 Palpasa Cafe Narayan Wagle Bagmati Press Lalitpur 450
4 Karnali Blues Buddhisagar Bagmati Press Lalitpur 550
5 Seto Dharti Amar Neupane Sagarmatha Books Kathmandu 500
6 Sumnima B. P. Koirala Bagmati Press Lalitpur 300

OrderLines (key: OrderID + BookID)

OrderID BookID Qty UnitPrice
1001 1 2 250
1001 3 1 450
1002 4 1 550
1003 5 1 500
1004 1 1 250
1004 2 1 350
1004 4 1 550
1005 3 2 420

Notice that Sumnima can now be stored before anyone buys it (insertion anomaly fixed).

Design question: Isn’t UnitPrice in OrderLines a duplicate of ListPrice in Books? No. ListPrice is today’s price; UnitPrice is the price actually charged on that order. Order 1005 got Palpasa Cafe at NPR 420 (a discount), and if the list price changes next month, old invoices must not change. These are two different facts.

A.4 Third Normal Form (3NF): No Transitive Dependencies

Rule: the table is in 2NF and no non-key column depends on another non-key column.

Two transitive dependencies remain:

  • In Orders: OrderID → Phone → (Customer, Area). The customer’s name and area depend on who the customer is, not on the order.
  • In Books: BookID → Publisher → PubCity. The city depends on the publisher, not on the book.

Fix: create Customers and Publishers tables and keep only a foreign key.

Customers

CustomerID FullName Phone Area
1 Sita Shrestha 9841000001 Baneshwor
2 Ram Thapa 9851000002 Patan
3 Anita Gurung 9801000003 Thamel
4 Bikash Rai 9861000004 Baneshwor

Publishers

PublisherID Name City
1 Sagarmatha Books Kathmandu
2 Bagmati Press Lalitpur

Orders now holds only OrderID, OrderDate, CustomerID; Books holds BookID, Title, Author, PublisherID, ListPrice; OrderLines is unchanged.

erDiagram
    CUSTOMERS ||--o{ ORDERS : places
    ORDERS ||--|{ ORDER_LINES : contains
    BOOKS ||--o{ ORDER_LINES : "sold in"
    PUBLISHERS ||--o{ BOOKS : publishes

Figure: The 3NF design — five tables, each fact stored once.

A memory aid used by many teachers: every non-key column must depend on “the key (1NF), the whole key (2NF), and nothing but the key (3NF).”

A.5 A Note on BCNF

Boyce–Codd Normal Form (BCNF) is a slightly stricter version of 3NF: for every dependency X → Y in the table, X must be a candidate key. Most 3NF tables are already in BCNF. The difference appears only when a table has overlapping candidate keys.

Example: Pustak Ghar’s delivery roster RiderShift(Area, Day, Rider) with two business rules: each area has one rider per day, and each rider works in only one area.

  • Candidate keys: (Area, Day) and (Rider, Day).
  • Dependency Rider → Area holds, but Rider alone is not a candidate key.

The table is in 3NF (because Area is part of a candidate key) but not in BCNF. The anomaly: if a rider moves to a new area, several rows must be updated. The BCNF fix splits it into RiderArea(Rider, Area) and RiderShift(Rider, Day). For ICT 110, knowing that BCNF exists and why is enough; 3NF is the practical target for business databases.

Part B: Build the Database in SQLite

B.1 Create the Tables

PRAGMA foreign_keys = ON;  -- SQLite enforces foreign keys only when this is on

CREATE TABLE customers (
    customer_id INTEGER PRIMARY KEY,
    full_name   TEXT NOT NULL,
    phone       TEXT NOT NULL UNIQUE,
    area        TEXT NOT NULL
);

CREATE TABLE publishers (
    publisher_id INTEGER PRIMARY KEY,
    name         TEXT NOT NULL UNIQUE,
    city         TEXT NOT NULL
);

CREATE TABLE books (
    book_id      INTEGER PRIMARY KEY,
    title        TEXT NOT NULL,
    author       TEXT NOT NULL,
    publisher_id INTEGER NOT NULL REFERENCES publishers(publisher_id),
    list_price   INTEGER NOT NULL CHECK (list_price > 0)
);

CREATE TABLE orders (
    order_id    INTEGER PRIMARY KEY,
    order_date  TEXT NOT NULL,             -- ISO format YYYY-MM-DD sorts correctly
    customer_id INTEGER NOT NULL REFERENCES customers(customer_id)
);

CREATE TABLE order_lines (
    order_id   INTEGER NOT NULL REFERENCES orders(order_id),
    book_id    INTEGER NOT NULL REFERENCES books(book_id),
    quantity   INTEGER NOT NULL CHECK (quantity > 0),
    unit_price INTEGER NOT NULL CHECK (unit_price > 0),
    PRIMARY KEY (order_id, book_id)
);

Prices are stored as whole rupees in INTEGER columns, which avoids rounding problems with decimal money.

B.2 Insert the Sample Data

INSERT INTO customers VALUES
  (1, 'Sita Shrestha', '9841000001', 'Baneshwor'),
  (2, 'Ram Thapa',     '9851000002', 'Patan'),
  (3, 'Anita Gurung',  '9801000003', 'Thamel'),
  (4, 'Bikash Rai',    '9861000004', 'Baneshwor');

INSERT INTO publishers VALUES
  (1, 'Sagarmatha Books', 'Kathmandu'),
  (2, 'Bagmati Press',    'Lalitpur');

INSERT INTO books VALUES
  (1, 'Muna Madan',      'Laxmi Prasad Devkota', 1, 250),
  (2, 'Shirishko Phool', 'Parijat',              1, 350),
  (3, 'Palpasa Cafe',    'Narayan Wagle',        2, 450),
  (4, 'Karnali Blues',   'Buddhisagar',          2, 550),
  (5, 'Seto Dharti',     'Amar Neupane',         1, 500),
  (6, 'Sumnima',         'B. P. Koirala',        2, 300);

INSERT INTO orders VALUES
  (1001, '2026-09-01', 1),
  (1002, '2026-09-01', 2),
  (1003, '2026-09-02', 1),
  (1004, '2026-09-03', 3),
  (1005, '2026-09-05', 4);

INSERT INTO order_lines VALUES
  (1001, 1, 2, 250), (1001, 3, 1, 450),
  (1002, 4, 1, 550),
  (1003, 5, 1, 500),
  (1004, 1, 1, 250), (1004, 2, 1, 350), (1004, 4, 1, 550),
  (1005, 3, 2, 420);

Test the foreign key: INSERT INTO orders VALUES (1006, '2026-09-06', 99); fails with FOREIGN KEY constraint failed, because customer 99 does not exist. This is the database protecting referential integrity for you.

B.3 Queries: JOIN, GROUP BY and Subqueries

Q1. Total value of each order (three-table JOIN + GROUP BY)

SELECT o.order_id, o.order_date, c.full_name,
       SUM(ol.quantity * ol.unit_price) AS order_total
FROM orders AS o
JOIN customers AS c    ON c.customer_id = o.customer_id
JOIN order_lines AS ol ON ol.order_id = o.order_id
GROUP BY o.order_id, o.order_date, c.full_name
ORDER BY o.order_id;
order_id order_date full_name order_total
1001 2026-09-01 Sita Shrestha 950
1002 2026-09-01 Ram Thapa 550
1003 2026-09-02 Sita Shrestha 500
1004 2026-09-03 Anita Gurung 1150
1005 2026-09-05 Bikash Rai 840

Q2. Books never ordered (subquery with NOT IN)

SELECT b.title
FROM books AS b
WHERE b.book_id NOT IN (SELECT book_id FROM order_lines);

Result: Sumnima. (Normalization made this question possible: in the original sheet, an unsold book did not exist.)

Q3. Orders above the average order value (subquery in WHERE)

WITH order_totals AS (
    SELECT order_id, SUM(quantity * unit_price) AS total
    FROM order_lines
    GROUP BY order_id
)
SELECT order_id, total
FROM order_totals
WHERE total > (SELECT AVG(total) FROM order_totals)
ORDER BY total DESC;

The average order value is NPR 798.0, so the result is 1004 (1150), 1001 (950) and 1005 (840). WITH ... AS (a common table expression) simply names a subquery so it can be reused.

Part C: SQL Optimization

Five orders are too few to show performance differences, so this part generates a realistic-sized hypothetical dataset: 5,000 customers, 500 books, 100,000 orders and 200,237 order lines. Run the script below in Python; it uses only the standard library.

import random, sqlite3, time

random.seed(42)
con = sqlite3.connect(":memory:")
con.executescript("""
CREATE TABLE customers (customer_id INTEGER PRIMARY KEY, full_name TEXT NOT NULL,
                        phone TEXT NOT NULL UNIQUE, area TEXT NOT NULL);
CREATE TABLE books (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, list_price INTEGER NOT NULL);
CREATE TABLE orders (order_id INTEGER PRIMARY KEY, order_date TEXT NOT NULL,
                     customer_id INTEGER NOT NULL REFERENCES customers(customer_id));
CREATE TABLE order_lines (order_id INTEGER NOT NULL REFERENCES orders(order_id),
                          book_id INTEGER NOT NULL REFERENCES books(book_id),
                          quantity INTEGER NOT NULL, unit_price INTEGER NOT NULL,
                          PRIMARY KEY (order_id, book_id));
""")
areas = ["Baneshwor", "Patan", "Thamel", "Koteshwor", "Kalanki", "Bhaktapur"]
con.executemany("INSERT INTO customers VALUES (?, ?, ?, ?)",
                [(i, f"Customer {i}", f"98{i:08d}", random.choice(areas)) for i in range(1, 5001)])
con.executemany("INSERT INTO books VALUES (?, ?, ?)",
                [(i, f"Book {i}", random.randrange(200, 1500, 10)) for i in range(1, 501)])
orders, lines = [], []
for oid in range(1, 100001):
    orders.append((oid, random.randrange(0, 730), random.randint(1, 5000)))
    for bid in random.sample(range(1, 501), random.randint(1, 3)):
        lines.append((oid, bid, random.randint(1, 3), random.randrange(200, 1500, 10)))
con.executemany("INSERT INTO orders VALUES (?, date('2025-01-01', '+' || ? || ' days'), ?)", orders)
con.executemany("INSERT INTO order_lines VALUES (?, ?, ?, ?)", lines)

def plan(sql, params=()):
    return "\n".join(row[3] for row in con.execute("EXPLAIN QUERY PLAN " + sql, params))

def timed(sql, params=(), reps=50):
    t0 = time.perf_counter()
    for _ in range(reps):
        con.execute(sql, params).fetchall()
    return (time.perf_counter() - t0) / reps * 1000  # milliseconds per run

Then run each experiment below by calling print(plan(...)) and print(timed(...)).

How to read EXPLAIN QUERY PLAN. Put EXPLAIN QUERY PLAN in front of a query and SQLite describes its strategy without running it. According to the SQLite documentation, SCAN means a full-table scan (every row is read), while SEARCH means only a subset of rows is visited, usually through an index. USING COVERING INDEX means the answer comes from the index alone, without touching the table, and USE TEMP B-TREE FOR ORDER BY means SQLite had to sort the rows itself. (The sqlite3 shell draws the same lines as a tree under a QUERY PLAN heading. SQLite warns that the exact wording can change between versions.)

About the timings: the milliseconds below were measured on one laptop with the data held in memory. Your numbers will differ; the plans and the size of the gap are what matter.

C.1 Indexes: The Biggest Single Win

A customer opens “My orders”. The query:

SELECT order_id, order_date FROM orders WHERE customer_id = 42;
Step EXPLAIN QUERY PLAN Time per run
Before index SCAN orders 6.446 ms
Add index CREATE INDEX idx_orders_customer ON orders(customer_id);  
After index SEARCH orders USING INDEX idx_orders_customer (customer_id=?) 0.029 ms

Without the index, SQLite read all 100,000 orders to find this customer’s 24. With it, SQLite jumps straight to them, like using the index at the back of a textbook instead of reading every page.

When indexes help:

  • Columns used in WHERE, JOIN ... ON and ORDER BY, especially foreign keys such as orders.customer_id.
  • Columns with many distinct values (customer ID, phone number, date).

When indexes hurt or don’t help:

  • Every index slows down writes. Each INSERT, UPDATE or DELETE must also update every index. In a test inserting 200,000 rows, the table with no secondary indexes took 0.42 s; the same insert with four indexes took 2.13 s.
  • Indexes take disk space.
  • Tiny tables, or columns with very few distinct values (for example a yes/no column), rarely benefit.
  • An index is useless if the query is written so the database cannot use it (see C.3).

SQLite creates some indexes automatically: the PRIMARY KEY and every UNIQUE column (such as customers.phone) get one. You saw this as sqlite_autoindex_... in the plans.

C.2 Avoid SELECT *

With idx_orders_customer in place, compare:

Query Plan
SELECT * FROM orders WHERE customer_id = 42 SEARCH orders USING INDEX idx_orders_customer (customer_id=?)
SELECT order_id FROM orders WHERE customer_id = 42 SEARCH orders USING COVERING INDEX idx_orders_customer (customer_id=?)

Asking only for the columns you need let SQLite answer from the index alone (covering index). SELECT * also sends unneeded data over the network, breaks application code when someone adds a column, and hides what the query really depends on.

C.3 Write Sargable WHERE Clauses

A condition is sargable (Search ARGument-able) when the database can use an index to evaluate it. The commonest mistake is wrapping the indexed column in a function. After CREATE INDEX idx_orders_date ON orders(order_date);, count September 2026 orders two ways:

Version Plan Rows Time
WHERE strftime('%Y-%m', order_date) = '2026-09' SCAN orders USING COVERING INDEX idx_orders_date 4085 44.872 ms
WHERE order_date >= '2026-09-01' AND order_date < '2026-10-01' SEARCH orders USING COVERING INDEX idx_orders_date (order_date>? AND order_date<?) 4085 0.163 ms

Both return the same 4,085 rows. In the first, SQLite must compute strftime for every one of the 100,000 entries (SCAN). In the second, the column is left “bare”, so SQLite jumps to the start of September and stops at the end (SEARCH).

The same idea applies to text: WHERE phone LIKE '%00042' (leading wildcard) gave SCAN customers USING COVERING INDEX sqlite_autoindex_customers_1, while WHERE phone = '9800000042' gave SEARCH ... (phone=?). Other non-sargable patterns: WHERE price * 1.13 > 1000 (do the arithmetic on the constant: price > 1000 / 1.13) and WHERE UPPER(full_name) = 'RAM THAPA'. If you truly must filter on an expression, SQLite, PostgreSQL and MySQL 8 can build an index on that expression, but rewriting the condition is usually simpler.

C.4 Composite Indexes for Filter + Sort

“Show customer 42’s five most recent orders”:

SELECT order_id, order_date FROM orders
WHERE customer_id = 42 ORDER BY order_date DESC LIMIT 5;
Index available Plan
orders(customer_id) only SEARCH orders USING INDEX idx_orders_customer (customer_id=?) then USE TEMP B-TREE FOR ORDER BY
orders(customer_id, order_date) SEARCH orders USING COVERING INDEX idx_orders_customer_date (customer_id=?)

The two-column index stores each customer’s orders already sorted by date, so the separate sort disappears. Column order matters: put the column tested with = first, then the range or sort column.

C.5 The N+1 Query Problem

Application code often does this: fetch a list (1 query), then loop and run one more query per item (N queries).

recent = con.execute("SELECT order_id FROM orders WHERE order_date >= '2026-12-25' ORDER BY order_id").fetchall()
totals = {}
for (oid,) in recent:                       # one extra query per order
    totals[oid] = con.execute(
        "SELECT SUM(quantity*unit_price) FROM order_lines WHERE order_id = ?", (oid,)
    ).fetchone()[0]

For the 919 orders placed from 25 December 2026, this sent 920 queries to the database. One JOIN with GROUP BY returns exactly the same totals in 1 query:

SELECT o.order_id, SUM(ol.quantity * ol.unit_price) AS total
FROM orders AS o
JOIN order_lines AS ol ON ol.order_id = o.order_id
WHERE o.order_date >= '2026-12-25'
GROUP BY o.order_id;

With an in-process database like SQLite each query is cheap, but on a server database (MySQL, PostgreSQL) every query is a network round trip, so N+1 is a common reason web pages become slow.

C.6 LIMIT and Pagination

Showing page 4,501 of the order list (20 per page) with OFFSET:

Method Query Plan Time
OFFSET ... ORDER BY order_id LIMIT 20 OFFSET 90000 SCAN orders 1.116 ms
Keyset (seek) ... WHERE order_id > 90000 ORDER BY order_id LIMIT 20 SEARCH orders USING INTEGER PRIMARY KEY (rowid>?) 0.017 ms

Both return the same 20 rows. OFFSET must step past 90,000 rows and throw them away, so deep pages get slower and slower. Keyset pagination remembers the last ID shown and asks for the next 20 after it. Always use LIMIT when a user only needs the first screen of results.

C.7 Optimization Checklist

  1. Run EXPLAIN QUERY PLAN (SQLite) or EXPLAIN (MySQL, PostgreSQL) before and after every change.
  2. Index foreign keys and frequent WHERE / ORDER BY columns, but not everything.
  3. Keep indexed columns bare in WHERE; rewrite functions into ranges.
  4. Select only the columns you need.
  5. Replace loops of queries with one JOIN.
  6. Paginate with LIMIT, preferably keyset style.

Part D: Lab Tasks

Use the small bookshop database from Part B for tasks 1–4 and the large generated database from Part C for tasks 5–6. Expected results are given so you can check yourself.

# Task Expected result
1 Revenue and number of orders per customer, highest revenue first Sita Shrestha 2 orders, 1450; Anita Gurung 1, 1150; Bikash Rai 1, 840; Ram Thapa 1, 550
2 Copies sold per title, most first (ties alphabetical) Muna Madan 3; Palpasa Cafe 3; Karnali Blues 2; Seto Dharti 1; Shirishko Phool 1
3 Revenue by publisher Bagmati Press 2390; Sagarmatha Books 1600 (total 3990)
4 Order lines sold below list price (join order_lines to books) One row: order 1005, Palpasa Cafe, list 450, charged 420
5 Show the plan for SELECT * FROM orders WHERE customer_id = 42 before and after adding an index SCAN orders → SEARCH orders USING INDEX ... (customer_id=?); the query returns 24 rows
6 Rewrite a non-sargable “orders in September 2026” filter and compare plans SCAN ... → SEARCH ... (order_date>? AND order_date<?); both versions count 4085 orders
Model SQL for tasks 1–4 ```sql -- Task 1 SELECT c.full_name, COUNT(DISTINCT o.order_id) AS orders, SUM(ol.quantity * ol.unit_price) AS revenue FROM customers AS c JOIN orders AS o ON o.customer_id = c.customer_id JOIN order_lines AS ol ON ol.order_id = o.order_id GROUP BY c.customer_id, c.full_name ORDER BY revenue DESC; -- Task 2 SELECT b.title, SUM(ol.quantity) AS copies_sold FROM books AS b JOIN order_lines AS ol ON ol.book_id = b.book_id GROUP BY b.book_id, b.title ORDER BY copies_sold DESC, b.title; -- Task 3 SELECT p.name AS publisher, SUM(ol.quantity * ol.unit_price) AS revenue FROM publishers AS p JOIN books AS b ON b.publisher_id = p.publisher_id JOIN order_lines AS ol ON ol.book_id = b.book_id GROUP BY p.publisher_id, p.name ORDER BY revenue DESC; -- Task 4 SELECT ol.order_id, b.title, b.list_price, ol.unit_price FROM order_lines AS ol JOIN books AS b ON b.book_id = ol.book_id WHERE ol.unit_price < b.list_price; ``` Note `COUNT(DISTINCT o.order_id)` in Task 1: without `DISTINCT`, Sita's order 1001 would be counted twice because it has two order lines.

Summary

Normalization removes duplication in steps: 1NF makes every cell atomic, 2NF removes columns that depend on only part of a composite key, and 3NF removes columns that depend on other non-key columns; BCNF tightens 3NF for tables with overlapping candidate keys. The result for Pustak Ghar is five related tables joined by primary and foreign keys. Once the design is right, performance comes from helping the database find rows without reading everything: indexes on the right columns, sargable conditions, selecting only needed columns, one JOIN instead of many small queries, and LIMIT with keyset pagination. EXPLAIN QUERY PLAN shows whether each change worked: SCAN means every row was read, SEARCH means an index narrowed the work.

Key Takeaways

  • Unnormalized sheets cause update, insertion and deletion anomalies.
  • 1NF = atomic values; 2NF = no partial dependency; 3NF = no transitive dependency.
  • Keep historical facts (price charged) separate from current facts (list price).
  • Indexes speed up reads but slow down writes; index foreign keys and frequent filters.
  • Functions on indexed columns and leading-wildcard LIKE turn a SEARCH into a SCAN.
  • N+1 query loops and deep OFFSET pages are common, avoidable slowdowns.

Discussion Questions

  1. A manager says, “Spreadsheets are simpler; why do we need five tables?” How would you answer using the anomalies from this lab?
  2. Daraz-style marketplaces show “Orders” pages with filters and many pages. Which techniques from Part C would matter most for such a page, and why?
  3. Should Pustak Ghar index every column “just in case”? Explain the trade-off.

Exam-Style Questions with Model Answers

1. Define 2NF and give an example of a partial dependency. (4 marks)

Model answer A table is in 2NF if it is in 1NF and every non-key attribute depends on the whole primary key. A partial dependency exists when a non-key attribute depends on only part of a composite key. Example: in `OrderLines(OrderID, BookID, Qty, OrderDate)`, `OrderDate` depends only on `OrderID`, so it should move to the `Orders` table.

2. Explain the difference between 3NF and BCNF with an example. (6 marks)

Model answer 3NF forbids non-key attributes from depending on other non-key attributes (transitive dependencies). BCNF requires that the determinant of every functional dependency is a candidate key. A table can be in 3NF but not BCNF when a non-key determinant determines part of a candidate key. Example: `RiderShift(Area, Day, Rider)` where each rider serves one area: Rider → Area holds but Rider is not a candidate key. Splitting into `RiderArea(Rider, Area)` and `RiderShift(Rider, Day)` achieves BCNF.

3. What is an index? State two advantages and two disadvantages. (5 marks)

Model answer An index is a separate, sorted data structure that lets the DBMS locate rows matching a condition without scanning the whole table, similar to a book's index. Advantages: much faster `WHERE`, `JOIN` and `ORDER BY` on indexed columns; can answer some queries from the index alone (covering index). Disadvantages: slower `INSERT`/`UPDATE`/`DELETE` because every index must be maintained; extra storage; little benefit for small tables or low-variety columns.

4. Why is WHERE strftime('%Y', order_date) = '2026' slow, and how would you rewrite it? (4 marks)

Model answer Wrapping the indexed column in a function makes the condition non-sargable: the DBMS must compute the function for every row, so it scans the table or index (`SCAN`) instead of seeking. Rewrite as a range on the bare column: `WHERE order_date >= '2026-01-01' AND order_date < '2027-01-01'`, which can use an index on `order_date` (`SEARCH`).

5. What is the N+1 query problem? How is it solved? (4 marks)

Model answer The application runs one query to fetch a list of N records and then one additional query per record to fetch related data, giving N+1 round trips. It is solved by fetching the related data in a single query with a JOIN (and `GROUP BY` if totals are needed) or with one `WHERE ... IN (...)` query. In this lab, 920 queries were replaced by one.

References