Relational Databases, Normalisation and SQL

Flat files, keys and relationships

A flat file keeps everything in one table. It is easy to start with and goes wrong in a predictable way: facts get repeated.

Asha's city is stored three times and the price of a keyboard twice. Every repeat is a chance for the copies to disagree:

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE Orders (OrderID INTEGER, Customer TEXT, City TEXT, Product TEXT, Price REAL, Quantity INTEGER)")
db.executemany("INSERT INTO Orders VALUES (?, ?, ?, ?, ?, ?)", [
    (1, "Asha Khan", "Leeds", "Keyboard", 25.0, 1),
    (1, "Asha Khan", "Leeds", "Mouse", 12.5, 2),
    (2, "Ben Ali", "York", "Keyboard", 25.0, 3),
    (3, "Asha Khan", "Leeds", "Monitor", 120.0, 1),
])

# Asha moves to Bradford, but the update only reaches one of her three rows
db.execute("UPDATE Orders SET City = 'Bradford' WHERE OrderID = 1 AND Product = 'Keyboard'")

for row in db.execute("SELECT DISTINCT Customer, City FROM Orders ORDER BY Customer, City"):
    print(row)

The database now says that Asha lives in Bradford and in Leeds. Three kinds of fault come from the repetition:

The relational answer

A relational database splits the data into several tables, each about one thing, and links them with keys.

Relationships between entities

A one to many relationship, one customer has many orders, is made with a foreign key on the many side. A many to many relationship, an order contains many products and a product is on many orders, cannot be held directly. It is split by a link table that has a foreign key to each side, OrderLine, whose primary key is the pair together.

Normalisation

Normalisation is the process of organising the tables to remove the repetition, and with it the three anomalies. It goes in stages, each one a normal form, and each includes the one before.

A phrase that holds all three: every attribute depends on the key, the whole key, and nothing but the key.

Worked example

The flat table above has no repeating groups, once the primary key is the pair OrderID and Product, so it is in 1NF. Now work out what each attribute really depends on.

• Quantity depends on both parts of the key: how many of this product on this order.
• Price depends only on Product. That is a partial dependency.
• Customer and City depend only on OrderID. That is another.

To reach 2NF, move those out into tables of their own. Now the order's facts and the product's facts are each held once.

• City depends on Customer, and Customer depends on OrderID. A fact about a fact is a transitive dependency.

To reach 3NF, give the customer a table of their own, and let the order refer to it with a foreign key. The finished design is four tables:

Asha's city is stored once. Changing it is one update, and every order sees it.

Building it in SQL

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("PRAGMA foreign_keys = ON")
db.executescript('''
CREATE TABLE Customer (CustomerID INTEGER PRIMARY KEY, Name TEXT NOT NULL, City TEXT);
CREATE TABLE Product (ProductID INTEGER PRIMARY KEY, Name TEXT NOT NULL, Price REAL CHECK (Price > 0));
CREATE TABLE CustomerOrder (
    OrderID INTEGER PRIMARY KEY,
    CustomerID INTEGER NOT NULL REFERENCES Customer(CustomerID));
CREATE TABLE OrderLine (
    OrderID INTEGER REFERENCES CustomerOrder(OrderID),
    ProductID INTEGER REFERENCES Product(ProductID),
    Quantity INTEGER NOT NULL,
    PRIMARY KEY (OrderID, ProductID));
''')

db.executemany("INSERT INTO Customer VALUES (?, ?, ?)", [(1, "Asha Khan", "Leeds"), (2, "Ben Ali", "York")])
db.executemany("INSERT INTO Product VALUES (?, ?, ?)", [(1, "Keyboard", 25.0), (2, "Mouse", 12.5), (3, "Monitor", 120.0)])
db.executemany("INSERT INTO CustomerOrder VALUES (?, ?)", [(1, 1), (2, 2), (3, 1)])
db.executemany("INSERT INTO OrderLine VALUES (?, ?, ?)", [(1, 1, 1), (1, 2, 2), (2, 1, 3), (3, 3, 1)])

db.execute("UPDATE Customer SET City = 'Bradford' WHERE CustomerID = 1")      # one change
for row in db.execute("SELECT CustomerID, Name, City FROM Customer"):
    print(row)

# referential integrity: an order for a customer that does not exist is refused
try:
    db.execute("INSERT INTO CustomerOrder VALUES (4, 99)")
except sqlite3.IntegrityError as error:
    print("refused:", error)

# a CHECK constraint refuses a price that makes no sense
try:
    db.execute("INSERT INTO Product VALUES (4, 'Faulty', -5)")
except sqlite3.IntegrityError as error:
    print("refused a negative price:", type(error).__name__)

The constraints do the work that the programmer would otherwise have to remember: PRIMARY KEY and NOT NULL for entity integrity, REFERENCES for referential integrity, and CHECK for domain rules.

SQL at A Level: joins, grouping and aggregates

With the data in separate tables, a query puts it back together with a JOIN. JOIN ... ON pairs rows of two tables where the key matches.

The queries below all run against the four table design. The setup is repeated so that the program runs on its own.

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript('''
CREATE TABLE Customer (CustomerID INTEGER PRIMARY KEY, Name TEXT, City TEXT);
CREATE TABLE Product (ProductID INTEGER PRIMARY KEY, Name TEXT, Price REAL);
CREATE TABLE CustomerOrder (OrderID INTEGER PRIMARY KEY, CustomerID INTEGER);
CREATE TABLE OrderLine (OrderID INTEGER, ProductID INTEGER, Quantity INTEGER);
INSERT INTO Customer VALUES (1, 'Asha Khan', 'Leeds'), (2, 'Ben Ali', 'York');
INSERT INTO Product VALUES (1, 'Keyboard', 25.0), (2, 'Mouse', 12.5), (3, 'Monitor', 120.0);
INSERT INTO CustomerOrder VALUES (1, 1), (2, 2), (3, 1);
INSERT INTO OrderLine VALUES (1, 1, 1), (1, 2, 2), (2, 1, 3), (3, 3, 1);
''')

def run(sql):
    print(" ".join(sql.split()))
    for row in db.execute(sql):
        print("    ", row)

run('''SELECT Customer.Name, Product.Name, OrderLine.Quantity
       FROM OrderLine
       JOIN CustomerOrder ON OrderLine.OrderID = CustomerOrder.OrderID
       JOIN Customer ON CustomerOrder.CustomerID = Customer.CustomerID
       JOIN Product ON OrderLine.ProductID = Product.ProductID
       WHERE Customer.City = 'Leeds'
       ORDER BY Product.Name''')

run('''SELECT CustomerOrder.OrderID, SUM(Product.Price * OrderLine.Quantity) AS Total
       FROM CustomerOrder
       JOIN OrderLine ON CustomerOrder.OrderID = OrderLine.OrderID
       JOIN Product ON OrderLine.ProductID = Product.ProductID
       GROUP BY CustomerOrder.OrderID''')

run('''SELECT Customer.Name, SUM(Product.Price * OrderLine.Quantity)
       FROM Customer
       JOIN CustomerOrder ON Customer.CustomerID = CustomerOrder.CustomerID
       JOIN OrderLine ON CustomerOrder.OrderID = OrderLine.OrderID
       JOIN Product ON OrderLine.ProductID = Product.ProductID
       GROUP BY Customer.CustomerID
       HAVING SUM(Product.Price * OrderLine.Quantity) > 100''')

run("SELECT COUNT(*), AVG(Price), MIN(Price), MAX(Price) FROM Product")
run("SELECT Name FROM Product WHERE Price BETWEEN 10 AND 30 AND Name LIKE '%o%'")
run("SELECT Name FROM Customer WHERE CustomerID IN (SELECT CustomerID FROM CustomerOrder WHERE OrderID = 2)")

Changing data safely

UPDATE Product SET Price = Price * 1.1 WHERE Name = 'Keyboard'
DELETE FROM OrderLine WHERE OrderID = 3
INSERT INTO Product (ProductID, Name, Price) VALUES (4, 'Webcam', 39.99)

Always use parameters, never joined text, when a value comes from a user. You saw this at GCSE as a defence against SQL injection, and it is still the rule: db.execute("SELECT ... WHERE Name = ?", (name,)).

Transactions and ACID

Moving £30 from one account to another takes two updates: take it from one, add it to the other. If the program stops between the two, £30 has disappeared. A transaction is a group of operations treated as one unit, that either all happen or none do.

The four properties a database guarantees are ACID:

commit() makes the transaction permanent. rollback() undoes everything since it began.

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE Account (ID INTEGER PRIMARY KEY, Owner TEXT, Balance REAL CHECK (Balance >= 0))")
db.executemany("INSERT INTO Account VALUES (?, ?, ?)", [(1, "Asha", 100.0), (2, "Ben", 50.0)])
db.commit()

def balances():
    return [row[0] for row in db.execute("SELECT Balance FROM Account ORDER BY ID")]

def transfer(source, target, amount):
    try:
        db.execute("UPDATE Account SET Balance = Balance + ? WHERE ID = ?", (amount, target))
        db.execute("UPDATE Account SET Balance = Balance - ? WHERE ID = ?", (amount, source))
        db.commit()
        return "committed"
    except sqlite3.IntegrityError:
        db.rollback()
        return "rolled back"

print(transfer(1, 2, 30), balances())
print(transfer(1, 2, 500), balances())

In the second transfer, the first statement, crediting Ben with £500, succeeded. The second statement, taking £500 from Asha, was refused by the CHECK, because she only has £70. Without a transaction Ben would now hold £550 that came from nowhere. The rollback undid the credit, and the balances are as they were.

Concurrency and locking

When two users change the same record at once, one change can overwrite the other. The database prevents it with record locking: the first transaction to touch a record locks it, and others wait. Two transactions each waiting for a lock that the other holds are in deadlock, and the database resolves it by rolling one back.

Indexes

An index is a separate sorted structure on a column, usually a tree, which lets the database find rows by that column without reading the whole table. It makes reads faster and writes slower, because every insert must update the index, and it costs storage. Primary keys are indexed automatically, and you add an index to a column you search often.

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE Person (ID INTEGER PRIMARY KEY, Surname TEXT)")
db.executemany("INSERT INTO Person (Surname) VALUES (?)", [("Khan",), ("Ali",), ("Smith",), ("Khan",)])
db.execute("CREATE INDEX idx_surname ON Person (Surname)")
print(db.execute("SELECT COUNT(*) FROM Person WHERE Surname = 'Khan'").fetchone()[0])

Key terms you must be able to define

Flat file

A database held as a single table, which tends to repeat data.

Relational database

A database of several tables, each about one entity, linked by keys.

Primary key

An attribute, or set of attributes, whose value is unique for every record in a table.

Foreign key

An attribute in one table that holds the primary key of a record in another table.

Referential integrity

The rule that every foreign key value must match an existing primary key value.

Normalisation

Organising the tables of a database to remove repeated data and the anomalies it causes.

Partial dependency

An attribute that depends on only part of a composite primary key.

Transitive dependency

A non key attribute that depends on another non key attribute rather than directly on the key.

Transaction

A group of database operations that is treated as a single unit.

ACID

The four properties of a reliable transaction: atomicity, consistency, isolation and durability.

Index

A data structure on a column that lets the database find records quickly without reading the whole table.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Database questions are about structure first and syntax second, so get the design right before writing a query.

• Name the key of every table, and mark each foreign key and what it refers to
• For normalisation, say which rule each change satisfies, and which dependency was removed
• Join tables on matching keys, and put the aggregate condition in HAVING, not in WHERE
• Define each part of ACID in a sentence, and tie it to the example in the question
• Describe an index as a trade: faster searching, slower writing and more storage

Mistakes that cost marks here

SELECT Customer.Name, SUM(CustomerOrder.Total)
FROM Customer
JOIN CustomerOrder ON Customer.CustomerID = CustomerOrder.CustomerID
GROUP BY Customer.CustomerID
HAVING SUM(CustomerOrder.Total) > 100