Databases

Structure and normalisation

Key terms

• Entity: something data is stored about, becoming a table
• Attribute: a property of an entity, becoming a field
• Record or tuple: one row
• Primary key: an attribute uniquely identifying each record
• Composite key: a primary key made of two or more attributes together
• Foreign key: an attribute in one table that is the primary key of another, creating the link
• Secondary key: an additional indexed field used for searching

Relationships

• One to one: rare, and usually a sign the tables should be merged
• One to many: the most common. The foreign key goes on the many side
• Many to many: cannot be implemented directly and must be resolved with a linking table holding foreign keys to both

Normalisation

First normal form (1NF). No repeating groups, and every field holds a single atomic value. Each record is uniquely identifiable.

Second normal form (2NF). In 1NF, and every non key attribute depends on the whole primary key, not just part of a composite key.

Third normal form (3NF). In 2NF, and no non key attribute depends on another non key attribute. There are no transitive dependencies.

The usual summary: every non key attribute depends on the key, the whole key, and nothing but the key.

Why normalise

• Removes redundancy, so the same fact is stored once
• Removes update anomalies, where changing a fact in one place leaves other copies wrong
• Removes insertion anomalies, where a record cannot be added without unrelated data
• Removes deletion anomalies, where deleting a record destroys unrelated information
• Reduces storage and improves data consistency

The cost is more tables and therefore more joins, which can slow complex queries. This is why some analytical systems deliberately denormalise for read performance.

SQL, indexing and transactions

Querying

SELECT Name, Grade
FROM Students
WHERE Year = 11 AND Grade >= 7
ORDER BY Grade DESC;

SELECT Students.Name, Courses.Title
FROM Students
INNER JOIN Enrolments ON Students.ID = Enrolments.StudentID
INNER JOIN Courses ON Enrolments.CourseID = Courses.ID
WHERE Courses.Title LIKE 'Comp%';

SELECT Year, COUNT(*) AS Total, AVG(Grade) AS MeanGrade
FROM Students
GROUP BY Year
HAVING COUNT(*) > 5;

Modifying

INSERT INTO Students (Name, Year, Grade) VALUES ('Aisha', 11, 8);

UPDATE Students SET Grade = 9 WHERE Name = 'Aisha';

DELETE FROM Students WHERE Year = 13;

CREATE TABLE Courses (
    ID      INTEGER PRIMARY KEY,
    Title   VARCHAR(60) NOT NULL,
    Credits INTEGER
);

ALTER TABLE Courses ADD Department VARCHAR(40);

Indexing

An index is a separate structure mapping the values of a field to the locations of matching records.

• Searches and sorts on that field become far faster, since the whole table need not be scanned
• Every insert, update and delete becomes slower, because the index must also be maintained
• The index consumes additional storage

Index fields that are searched frequently. Do not index fields that are written far more often than they are read.

Transactions and ACID

A transaction is a group of operations treated as a single indivisible unit.

• Atomicity. All operations succeed or none do. A transfer that debits one account must not fail after the debit but before the credit.
• Consistency. The database moves from one valid state to another, with all rules and constraints satisfied.
• Isolation. Concurrent transactions do not interfere. The result matches some sequential ordering of them.
• Durability. Once committed, changes survive a crash or power failure, guaranteed by writing to non volatile storage.

Concurrency control

• Record locking prevents two users modifying the same record simultaneously, but can produce deadlock where each transaction waits for a record the other holds
• Timestamp ordering gives each transaction a timestamp and resolves conflicts by ordering, avoiding deadlock at the cost of restarting some transactions
• Serialisation ensures the outcome of concurrent transactions matches some sequential execution of them

Key terms you must be able to define

Entity

Something that data is stored about, implemented as a table.

Primary key

An attribute or set of attributes uniquely identifying each record in a table.

Foreign key

An attribute in one table that is the primary key of another, forming the link between them.

Composite key

A primary key made up of two or more attributes together.

Normalisation

Organising data to remove redundancy and eliminate update, insertion and deletion anomalies.

Third normal form

A table in second normal form with no non key attribute depending on another non key attribute.

Transitive dependency

A non key attribute depending on another non key attribute rather than directly on the key.

Linking table

A table resolving a many to many relationship by holding foreign keys to both entities.

Index

A structure mapping field values to record locations, speeding searches at the cost of slower writes.

Transaction

A group of database operations treated as a single indivisible unit.

ACID

Atomicity, Consistency, Isolation and Durability, the guarantees a reliable transaction system provides.

Deadlock

A state where two transactions each hold a lock the other needs, so neither can proceed.

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

• Apply 1NF, 2NF and 3NF to an actual table rather than reciting the definitions
• Name the anomalies removed by normalisation: update, insertion and deletion
• Resolve a many to many relationship with a correctly described linking table
• Write SQL with joins, aggregate functions and GROUP BY, not just SELECT and WHERE
• Explain each ACID property with a concrete failure it prevents
• State the cost of indexing as well as the benefit

Mistakes that cost marks here