Computer Science › Section J · Database systems › Topic J.2
The relational model
The relational model pictures every database as a set of simple tables. Designing those tables well, and knowing how to combine them, is the foundation of almost every business database in use today.
Data as tables
In 1970 Edgar F. Codd, a researcher at IBM, proposed modelling a database as a collection of tables, which he called relations. Each row of a relation is a tuple, describing one thing, such as one pet registered at a veterinary clinic. Each column is an attribute, one property of that thing, such as its name or species, and its values come from a set of allowed values called the attribute's domain. A relation is a set of tuples, so no two rows may be identical and the order of the rows carries no meaning. Columns are identified by name, not position.
Keys
Every relation needs a way to tell its tuples apart. A primary key is an attribute, or a group of attributes, whose value differs in every row. The clinic gives each pet an identifier such as P1, so PetId is the primary key of Pet. A key made of several attributes is a composite key: a Visit relation can use the pair (PetId, VisitDate) if no pet visits twice in one day. A foreign key is an attribute holding the primary key of another relation. Pet has an OwnerId column whose values must match an OwnerId in Owner, and that shared value ties the two tables together.
Relationships between relations
Links between relations come in three shapes. One-to-one: each pet has at most one microchip record, and each record belongs to one pet. One-to-many: an owner can have several pets, but each pet has one owner, so the foreign key goes on the many side, in Pet. Many-to-many: a vet treats many pets and a pet may see many vets. No single foreign key can express that, so a linking relation is needed, with one row per pairing. Here Visit plays that role, recording a PetId and a vet for each appointment. Designers often sketch these shapes first in an entity-relationship diagram.
One big table and its troubles
Suppose the clinic kept everything in one relation, Log(PetId, PetName, Species, OwnerId, OwnerName, Phone, VisitDate, Vet). It has four rows, one per visit: two for Biscuit the dog, one for Mochi and one for Juno. Biscuit's owner, Priya Shah, and her phone number therefore appear twice. An update anomaly: if Priya changes her number, every one of her rows must change, and missing one leaves the table contradicting itself. A deletion anomaly: Juno the rabbit has one visit, so deleting it also deletes the only record of Juno's owner, Lena Okafor. An insertion anomaly: Pepper, a cat who has never visited, cannot be recorded at all without inventing a visit. The cause: one relation mixes facts about owners, pets and visits.
Worked example: splitting the clinic log
Steps: (1) Name each separate subject in Log: owners, pets and visits. (2) Give each its own relation and key: Owner(OwnerId, OwnerName, Phone), Pet(PetId, PetName, Species, OwnerId) and Visit(PetId, VisitDate, Vet). (3) Leave a foreign key wherever two subjects meet: OwnerId in Pet, PetId in Visit. (4) Copy the data across; Priya's number now sits in one row of Owner. (5) Recheck the anomalies: changing a number touches one row; deleting Juno's visit leaves Juno and Lena intact; Pepper can be added to Pet with no visit. (6) Check that nothing was lost: joining the three relations back on their shared keys reproduces the four rows of Log exactly.
Normalisation
Splitting relations to remove redundancy is called normalisation, and theory defines a ladder of normal forms measuring how far it has gone. The first rung, first normal form, requires every cell to hold a single value: a Phone cell holding two numbers breaks it. A well-known summary of the higher rungs is that every non-key attribute should depend on the key, the whole key, and nothing but the key. In Visit(PetId, VisitDate, Vet, PetName), PetName depends on PetId alone, only part of the composite key, so it belongs in Pet. In Pet(PetId, PetName, OwnerId, Phone), Phone depends on OwnerId rather than PetId, so it belongs in Owner.
Lossless and lossy decompositions
Not every split is safe. A clinic rota records which vet works in which room on which day: (Dr Ito, Mon, Room 1), (Dr Vance, Mon, Room 2) and (Dr Vance, Tue, Room 1). Split it into Works(Vet, Day) and Uses(Day, Room), and the link between vet and room vanishes. Rejoining the halves on Day gives five rows, including the false (Dr Ito, Mon, Room 2) and (Dr Vance, Mon, Room 1). A split that can always be rejoined exactly is a lossless decomposition; one that cannot is lossy. A split is guaranteed lossless when the shared attributes form a key of at least one of the new relations, as OwnerId does for Owner in the clinic split.
Selecting rows and projecting columns
Questions are answered by operations that take relations in and give a new relation out. Pet now has five rows, after two new cats were added: Biscuit (dog, owner O1), Mochi (cat, O2), Pepper (cat, O2), Juno (rabbit, O3) and Ziggy (cat, O1). SELECT, written \(\sigma\), keeps the rows that satisfy a condition: \(\sigma_{\text{Species='cat'}}(\text{Pet})\) gives the rows for Mochi, Pepper and Ziggy. PROJECT, written \(\pi\), keeps only the named columns. Because a relation is a set, projection removes duplicate rows, so \(\pi_{\text{Species}}(\text{Pet})\) has three rows, dog, cat and rabbit, though Pet has five. Results are relations, so operations chain.
Joining relations
JOIN, written \(\bowtie\), combines two relations. Each row of the first is paired with each row of the second, and a pair is kept only when the join condition holds. The usual condition matches a foreign key with the key it refers to. Joining Pet and Owner where Pet.OwnerId = Owner.OwnerId pairs every pet with its own owner, giving five rows that carry the columns of both relations. Columns are named by relation, as in Pet.OwnerId, so that same-named columns stay distinct. Other comparisons, such as < or ≠, are allowed, but equality of keys is by far the most common.
Worked example: who owns a cat?
Find the names of owners with at least one cat. Steps: (1) Join Pet and Owner where Pet.OwnerId = Owner.OwnerId. Each of the five pets is paired with its owner, giving five rows. (2) Select the rows where Species = 'cat'. Three remain: Mochi with Tom Reyes, Pepper with Tom Reyes, and Ziggy with Priya Shah. (3) Project OwnerName. Tom appears twice, but projection removes the duplicate, leaving two rows: Priya Shah and Tom Reyes. (4) Check against the data: Lena Okafor owns only Juno, a rabbit, so she is rightly missing. Selecting the cats before joining gives the same answer with fewer rows to pair.
Common mistakes to avoid
Choosing a primary key that can repeat, such as a pet's name; two pets may both be called Biscuit. Putting the foreign key on the wrong side of a one-to-many link: it goes on the many side, so each pet names its owner. Trying to express a many-to-many link without a linking relation. Assuming any split is safe; check that the shared attributes are a key of one part. Forgetting that projection removes duplicate rows. Confusing SELECT, which picks rows, with PROJECT, which picks columns.
Key takeaways
A relation is a set of tuples (rows) described by attributes (columns). A primary key identifies each tuple; a foreign key refers to another relation's key and links the two. Many-to-many relationships need a linking relation. Mixing subjects in one relation causes update, deletion and insertion anomalies; normalisation removes them with lossless splits. SELECT picks rows, PROJECT picks columns and removes duplicates, and JOIN pairs rows that meet a condition.
Flashcards
Flashcard
A table: a set of tuples sharing the same attributes
Test your understanding
Question 1 of 5
In the clinic's Pet(PetId, PetName, Species, OwnerId) relation, which attribute is a foreign key?
Question 2 of 5
In the single Log table, deleting Juno's only visit also erases Lena Okafor's phone number. Which problem is this?
Question 3 of 5
Pet has five rows: three cats, one dog and one rabbit. How many rows does projecting the Species column give?
Question 4 of 5
The rota (Dr Ito, Mon, Room 1), (Dr Vance, Mon, Room 2) is split into (Vet, Day) and (Day, Room). Rejoining on Day gives how many rows?
Question 5 of 5
Which sequence of operations lists the names of owners who have a rabbit?
