Relational databases and keys

Flat files against relational databases, and every kind of key: primary, composite, foreign and secondary, with indexes and how records are found.

A11.2Databases and big dataA level55 min

At GCSE (F7.2) you met tables, records, fields, primary keys and foreign keys. At A level the vocabulary is more exact, there are more kinds of key, and you need to say how a database finds a record quickly. This lesson turns the entity descriptions of the last lesson into a relational database.

Flat files and relational databases

A flat file database holds all the data in one table, often a single file such as a CSV. Every run record repeats the robot's name, colour and team:

A relational database stores the data in several tables, one for each entity, and links them through keys. The name comes from the mathematical word for a table, a relation.

A flat file is fine for a small list with one purpose, such as one robot's sensor log. Once the data describes several related things and is shared and changed, a relational database is the better choice.

The vocabulary

Keys

• A candidate key is any attribute, or minimal set of attributes, that could identify each record uniquely.
• The primary key is the candidate key chosen to identify records. Its value must be unique and must never be empty (null). The DBMS enforces both.
• A composite primary key (or compound key) is a primary key made of two or more attributes, where no one attribute is unique on its own but the combination is. A robot makes several attempts, so neither RobotID nor AttemptNo identifies an attempt, but (RobotID, AttemptNo) does.
• A foreign key is an attribute in one table that holds the primary key of a record in another table. It is how a relationship is built: TeamID in Robot links each robot to its team.
• A secondary key is an attribute, other than the primary key, that is indexed so records can be searched for or sorted by it quickly. A robot's Name is a good secondary key: people look robots up by name, although two robots could share one.

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE attempts (robot_id INTEGER, attempt INTEGER, cm REAL, PRIMARY KEY (robot_id, attempt))")
db.execute("INSERT INTO attempts VALUES (1, 1, 42.0)")
db.execute("INSERT INTO attempts VALUES (1, 2, 45.5)")    # same robot, new attempt: fine
db.execute("INSERT INTO attempts VALUES (2, 1, 38.0)")    # same attempt number, new robot: fine
try:
    db.execute("INSERT INTO attempts VALUES (1, 2, 44.0)")
except sqlite3.IntegrityError as e:
    print("refused:", e)
print(db.execute("SELECT * FROM attempts").fetchall())

Run this in the simulator

CREATE TABLE builds a table (you met it at GCSE in F7.5, and lesson A11.4 covers it fully). The DBMS refuses the fourth record because the pair (1, 2) already exists, even though 1 and 2 each appear more than once on their own.

Indexes

To find the records where task = 'wall', a database with no help must read every record: a full table scan, O(n). An index is a separate structure that holds the values of one attribute in order, each with the location of its record, so the DBMS can go straight to the matching records. Most DBMSs keep indexes as balanced trees, which makes a lookup about O(log n). The primary key is indexed automatically; an index on any other attribute makes it a secondary key.

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE runs (run_id INTEGER PRIMARY KEY, task TEXT, cm REAL)")

def plan(sql):
    for row in db.execute("EXPLAIN QUERY PLAN " + sql):
        print("  ", row[-1])

print("find by primary key:")
plan("SELECT * FROM runs WHERE run_id = 3")
print("find by task, no index:")
plan("SELECT * FROM runs WHERE task = 'wall'")

db.execute("CREATE INDEX idx_runs_task ON runs (task)")
print("find by task, with an index:")
plan("SELECT * FROM runs WHERE task = 'wall'")

Run this in the simulator

EXPLAIN QUERY PLAN shows how SQLite will run a query: SCAN reads every record, SEARCH ... USING INDEX jumps to them. An index is not free. It takes storage, and every INSERT, UPDATE and DELETE must update the index as well as the table. So index the attributes that are searched or sorted often, not every attribute.

How records are found in a file

Underneath, a database is records in files, and there are four classic ways to organise a file of records:

A hash function turns a key into an address. Two keys can give the same address, a collision, so the file needs a rule for where the second record goes:

SLOTS = 7
table = [None] * SLOTS

for robot_id in [15, 22, 31, 8]:
    address = robot_id % SLOTS
    while table[address] is not None:          # collision: try the next slot
        address = (address + 1) % SLOTS
    table[address] = robot_id
    print("robot", robot_id, "stored at", address)

print(table)

Run this in the simulator

15, 22 and 8 all hash to address 1, so 22 and 8 move on to the next free slots. This is linear probing. You will meet hash tables as a data structure in module A3.

Task: a composite key

A robot may make several attempts at a task, numbered from 1 for each robot. The list attempts holds records (robot_id, attempt, cm): two whole numbers and a float.

1. Create a table attempts with the fields robot_id, attempt and cm, and the composite primary key (robot_id, attempt).
2. Insert every record, in order. For each one print added robot <robot_id> attempt <attempt>, or, if the database refuses it with sqlite3.IntegrityError, print rejected robot <robot_id> attempt <attempt>: already logged.
3. Use SELECT COUNT(*) to print the number of records now in the table as records: <n>.

Seven lines in all. The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import sqlite3

attempts = [(1, 1, 42.0), (1, 2, 45.5), (2, 1, 38.0), (1, 2, 44.0), (3, 1, 76.5), (2, 1, 39.0)]
db = sqlite3.connect(":memory:")

Challenges

1. The Booking table has the key (StudentID, RobotID, SessionDate). Could a student book two robots on the same day? Could they book the same robot twice on one day?
2. Store 1,000 random run records, then time SELECT by task with and without an index. How big must the table be before the index shows?
3. A car park system looks up a car by its registration. Which file organisation would you choose, and why?