Introduction to Computer Science: Harvard CS50 · Course book
Chapter 9: Storing and Querying Data
Chapter 8 ended with a problem: storing an application's data in a Python list loses it on every restart, and storing it in a file becomes awkward as soon as many people use the application at once or the data needs searching and updating. The standard answer is a database, software designed to store large amounts of structured data safely and to answer questions about it quickly. This chapter introduces relational databases and the language used to talk to them, SQL, shows how tables are linked together, explains what makes lookups fast, and connects a database to a Python web application.
From spreadsheets to databases
Many people first store data in a spreadsheet: rows for records, columns for fields. A spreadsheet works well for a few hundred rows viewed by one person. It struggles with millions of rows, with many programs reading and writing at the same moment, and with questions that combine several sheets.
A relational database keeps the familiar shape, data in tables of rows and columns, but adds rules and a language. Each table has a fixed set of columns, each with a type, so a column declared as an integer can only hold integers. The database enforces these rules, guards against corruption if the power fails mid-write, and lets many users work at once without trampling each other's changes. SQLite, the database used in this chapter, stores a whole database in a single file and is built into countless phones and browsers. Larger systems such as PostgreSQL and MySQL run as servers used by many applications at once, but they speak almost the same language.
| SQLite type | Holds | Example |
|---|---|---|
| INTEGER | Whole numbers | 2018 |
| REAL | Numbers with a decimal point | 4.5 |
| TEXT | Characters | 'Ada Lovelace' |
| BLOB | Raw binary data, such as an image | (bytes of a file) |
| NUMERIC | Values such as dates, stored in the most suitable form | '2018-10-01' |
Asking questions with SQL
SQL, Structured Query Language, is how programs talk to relational databases. Most of what applications need fits four operations, often remembered as CRUD: create, read, update and delete.
CREATE TABLE books (
id INTEGER PRIMARY KEY,
title TEXT NOT NULL,
year INTEGER,
rating REAL
);
INSERT INTO books (title, year, rating) VALUES ('Patterns of Light', 2016, 4.2);
SELECT title, year FROM books WHERE year >= 2015 ORDER BY year;
UPDATE books SET rating = 4.4 WHERE id = 1;
DELETE FROM books WHERE rating < 2;
CREATE TABLE defines the columns and their types. INSERT adds a row. SELECT reads rows: the columns named after SELECT are returned, WHERE filters which rows, ORDER BY sorts them and LIMIT caps how many come back. UPDATE changes existing rows and DELETE removes them. Note that UPDATE and DELETE without a WHERE clause affect every row in the table, a mistake worth guarding against.
SQL can also summarise. Suppose the table holds five books with ratings 4.2, 3.8, 4.6, 3.1 and 4.3.
- SELECT COUNT(*) FROM books returns 5.
- SELECT AVG(rating) FROM books returns (4.2 + 3.8 + 4.6 + 3.1 + 4.3) ÷ 5 = 20.0 ÷ 5 = 4.0.
- SELECT MAX(rating) FROM books returns 4.6.
- SELECT COUNT(*) FROM books WHERE rating > 4 returns 3.
Pattern matching uses LIKE with a percent sign as a wildcard: WHERE title LIKE 'The%' finds titles beginning with "The". GROUP BY gathers rows that share a value, so SELECT year, COUNT(*) FROM books GROUP BY year counts the books published in each year.
Some values are simply unknown. A book whose year has not been recorded holds the special value NULL, meaning "no value", which is different from 0 or an empty string. Comparisons with NULL behave unusually: WHERE year = NULL matches nothing, and the correct test is WHERE year IS NULL. Marking a column NOT NULL when it is created, as with title above, makes the database refuse any row that leaves it empty, catching mistakes at the moment they happen. Constraints such as UNIQUE, which forbids two rows from sharing a value, work the same way: rules declared once are enforced on every change, by every program that uses the database.
You can experiment with all of this directly. SQLite comes with a command-line program: running sqlite3 books.db opens or creates the file books.db, and any SQL typed at its prompt runs at once and prints the results. Commands such as .schema, which shows how each table was created, help you find your way around an unfamiliar database before writing any code against it.
Linking tables together
Suppose each book has an author, and some authors have written many books. Storing the author's name and details in every book row would repeat them again and again, and correcting a misspelled name would mean changing many rows. The relational approach is to give authors their own table and link to it.
Each table has a primary key, a column, usually id, whose value uniquely identifies each row. A foreign key is a column in one table holding primary keys from another, here books.author_id. To combine the tables, a query joins them:
SELECT books.title, authors.name
FROM books
JOIN authors ON books.author_id = authors.id
WHERE authors.name = 'Mira Osei';
This returns "Patterns of Light" and "Northern Lines". Splitting data into linked tables like this, so that each fact is stored once, is called normalisation. It saves space and, more importantly, prevents the inconsistencies that arise when the same fact is stored in several places and only some copies are updated.
Making queries fast
To answer SELECT * FROM books WHERE title = 'Quiet Rivers', a database with no help must examine every row: a linear search, as in Chapter 1. For a table of a million rows that means a million comparisons.
An index solves this. CREATE INDEX title_index ON books (title) builds a separate structure, a kind of balanced tree, that keeps titles in sorted order with pointers to their rows. A lookup then descends the tree, taking roughly log₂ of the number of rows: about 20 steps for a million rows instead of a million. Primary keys are indexed automatically.
Prefixing a query with EXPLAIN QUERY PLAN asks SQLite to describe how it will run the query, revealing whether it will scan the whole table or use an index. Checking this is the first step when a query is slow.
Indexes are not free. They take extra storage, and every INSERT, UPDATE or DELETE must update every index on the table too. A sensible rule is to index the columns that queries search or join on frequently, and not others.
Speed matters in another way when many users act at once. Imagine two visitors liking the same post at the same instant. If the application reads the count, adds one and writes it back as three separate steps, both may read 10 and both write 11, losing one like. This is a race condition. Databases prevent it with transactions, groups of statements that are carried out as a single, indivisible unit, or by doing the arithmetic inside one statement, such as UPDATE posts SET likes = likes + 1 WHERE id = 7.
Using a database from Python
A Flask application sends SQL to the database and receives rows back as Python data. With a helper library, a query looks like this:
rows = db.execute("SELECT title FROM books WHERE year = ?", year)
for row in rows:
print(row["title"])
The question mark is a placeholder. The library fills it in with the value of year, taking care that the value is treated purely as data. This matters a great deal. If the program instead built the SQL by pasting user input directly into the text of the query, a visitor could type input that changes the meaning of the query itself. Always passing user input through placeholders, never by building query text by hand, closes that door entirely, and it is one of the most important habits in web programming.
The registration application of Chapter 8 can now keep its data properly: each submission becomes an INSERT into a registrants table, the list of registrants is a SELECT passed to a template, and the data survives restarts and is shared by every visitor.
Check your understanding
- Give two ways in which a database improves on a spreadsheet for a busy web application.
- What do the four CRUD operations correspond to in SQL? (Answer: INSERT, SELECT, UPDATE and DELETE.)
- Ratings are 3.0, 4.0, 5.0 and 4.0. What does AVG(rating) return? (Answer: 16 ÷ 4 = 4.0.)
- Why is UPDATE books SET rating = 0 dangerous?
- What is a foreign key, and why store an author's id instead of their name in each book row?
- About how many steps does an indexed lookup need in a table of 4 million rows? (Answer: about 22, since 2 to the power 22 is about 4.2 million.)
- Why should user input always be passed to a query through placeholders?
This course book is available to read online only at tech-academy.chrysolites.org.