Relations, tuples, domains and Codd's rules

The relational model describes a database as a collection of relations. A relation is a table in the mathematical sense: a set of tuples (rows) over a fixed list of named attributes (columns), and every value of an attribute comes from that attribute’s domain, the set of values it may take. The number of attributes is the relation’s degree; the number of tuples it holds at a moment is its cardinality. Because a relation is a set, its tuples have no order and no tuple appears twice. An SQL table is close to this, but not the same: it may hold the same row twice unless a key forbids it, it promises no row order without ORDER BY, and it uses NULL for values that are missing. This lesson pins down each term, runs the differences in SQLite, and ends with Codd’s rules, the checklist he published for what “relational” was meant to mean.

A relation, defined

E. F. Codd, who proposed the model in 1970, used the word “relation” in its mathematical sense, and defined it like this:

Given sets S₁, S₂, …, Sₙ (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S₁, its second element from S₂, and so on.

A footnote in his paper says it more briefly: R is a subset of the Cartesian product S₁ × S₂ × … × Sₙ. The sets Sⱼ are the domains, and n is the degree: a relation of degree 1 is unary, 2 binary, 3 ternary.

Codd also suggested that users should not have to remember which column comes first. If each column has a name, the role it plays, then a tuple can be read as a set of attribute–value pairs and the order of the columns stops mattering. Most books, and this track, use that named form. Here are the terms, each with its everyday SQL word and its value in the example below:

• Relation (SQL: table): a set of tuples over one schema, such as student.
• Tuple (row): one element of the set, such as (101, Asha, BTech, 2).
• Attribute (column): a named role that every tuple fills, such as programme.
• Domain (a type plus constraints): the set of values an attribute may take, such as BTech, MSc or PhD.
• Degree (the number of columns): the number of attributes, 4 here.
• Cardinality (the number of rows): the number of tuples right now, 3 here.

The first lesson of this track separated a database’s schema from its instance, and a single relation has the same two sides. The relation schema, also called the intension, is the name and the list of attributes with their domains: student(roll_no, name, programme, year). It changes only when the design changes. The relation instance, or extension, is the set of tuples stored at one moment; Codd spoke of “time-varying relations”, because every insert, update and delete gives the relation a new instance. Degree belongs to the schema and cardinality to the instance, which is why the cardinality of student can be 3 this morning and 3,000 next term while its degree stays 4.

A domain is more than a data type. “Text” is a type; “BTech, MSc or PhD” is a domain, a precise set of allowed values. SQL approximates domains with a type plus constraints, such as CHECK (programme IN ('BTech', 'MSc', 'PhD')), and PostgreSQL also has CREATE DOMAIN for a named type with its own checks; the lesson on integrity constraints uses both.

Atomic values and first normal form

Codd’s paper calls a domain simple when its values are atomic, such as numbers and strings, and nonsimple when its values are themselves relations, such as a whole salary history stored inside one employee’s tuple. He proposed removing nonsimple domains by moving each nested relation into a relation of its own, keyed by the parent’s key. A relation whose domains are all simple is in what is now called first normal form (1NF).

“Atomic” is a decision about how the data is used, not a property of the data. A date has a day, a month and a year, yet it is atomic in a design that never asks for its parts; a phone number is atomic until someone needs its country code. Modern engines also let you store structured values on purpose. PostgreSQL columns can be arrays, and both PostgreSQL and SQLite handle JSON (SQLite keeps it as text and has JSON functions built in). These are useful for data that is read and written as a unit, but the database cannot easily enforce a key or a foreign key on the parts inside them. PostgreSQL’s own documentation warns that “arrays are not sets” and that searching for array elements “can be a sign of database misdesign”, suggesting a separate table with one row per element instead.

SQL tables are bags of rows

A relation cannot contain the same tuple twice: a set either contains an element or it does not. An SQL table without a key has no such rule. It is a bag, also called a multiset, and so is the result of a query unless you ask for DISTINCT. Here a table of enrolments holds one row twice:

-- A table without a key is a bag: it can hold the same row twice.
CREATE TABLE enrolment (roll_no INTEGER, course TEXT);
INSERT INTO enrolment VALUES
  (101, 'DBMS'),
  (101, 'DBMS'),
  (102, 'DBMS'),
  (102, 'OS');

SELECT count(*) AS rows_stored FROM enrolment;

-- DISTINCT returns the set of different rows.
SELECT DISTINCT roll_no, course FROM enrolment;

-- Projection keeps one output row per stored row in SQL...
SELECT course FROM enrolment;

-- ...and becomes the relational projection only with DISTINCT.
SELECT DISTINCT course FROM enrolment;

┌─────────────┐
│ rows_stored │
├─────────────┤
│ 4           │
└─────────────┘
┌─────────┬────────┐
│ roll_no │ course │
├─────────┼────────┤
│ 101     │ DBMS   │
│ 102     │ DBMS   │
│ 102     │ OS     │
└─────────┴────────┘
┌────────┐
│ course │
├────────┤
│ DBMS   │
│ DBMS   │
│ DBMS   │
│ OS     │
└────────┘
┌────────┐
│ course │
├────────┤
│ DBMS   │
│ OS     │
└────────┘

Four rows are stored although only three different facts exist. SELECT DISTINCT returns the set of different rows, which is what the relational model would hold. The last two queries show the same gap in a projection. In relational algebra, projecting enrolment onto course gives the set {DBMS, OS}; SQL keeps one output row per stored row and reaches the relational answer only with DISTINCT.

SQL chose bags for practical reasons. Removing duplicates needs a sort or a hash of every result, which costs time on large results, and some questions need the copies: adding up payments must count two equal payments twice. The two behaviours stay visible in the language as UNION, which removes duplicates, and UNION ALL, which keeps them. One detail about DISTINCT matters later: PostgreSQL’s documentation says that when it compares rows, “null values are considered equal”.

A key is what turns a table back into a set. Declare one, and the second copy is refused:

-- With a primary key the table is a set: a second copy is refused.
CREATE TABLE enrolment (
  roll_no INTEGER NOT NULL,
  course  TEXT    NOT NULL,
  PRIMARY KEY (roll_no, course)
);
INSERT INTO enrolment VALUES (101, 'DBMS');
INSERT INTO enrolment VALUES (101, 'DBMS');
INSERT INTO enrolment VALUES (101, 'OS');

SELECT roll_no, course FROM enrolment ORDER BY course;

┌─────────┬────────┐
│ roll_no │ course │
├─────────┼────────┤
│ 101     │ DBMS   │
│ 101     │ OS     │
└─────────┴────────┘

Runtime error near line 8: UNIQUE constraint failed: enrolment.roll_no, enrolment.course

The message names both columns of the key, because it is the pair (roll_no, course) that must not repeat; the same student can still take a second course. PostgreSQL behaves the same way, and if you try to add a primary key to a table that already holds copies, the ALTER TABLE fails because it cannot build the unique index the key needs. That is why every base table should have a primary key, and the next lesson is about choosing it.

Row order is not part of the data

The tuples of a relation have no order, and SQL gives no promise either. PostgreSQL’s documentation says that without ORDER BY “the rows will be returned in an unspecified order”, that the order depends on the scan and join plans and on the order on disk, and that it “must not be relied on”. SQLite’s documentation is just as plain: it “makes no guarantees about the order of results” when a query has no ORDER BY. The same query can return the same rows in a different order the moment the engine finds another way to read them:

CREATE TABLE city (name TEXT, state TEXT, orders INTEGER);
INSERT INTO city VALUES
  ('Pune', 'MH', 74),
  ('Agra', 'UP', 22),
  ('Kochi', 'KL', 21),
  ('Bhopal', 'MP', 24);

-- No ORDER BY: SQLite happens to return the rows in the order it stored them.
SELECT name FROM city;

-- An index that holds every column the query needs changes the order.
CREATE INDEX city_by_name ON city (name);
SELECT name FROM city;

-- SQLite can reverse unordered results on purpose, to expose code that relies on them.
PRAGMA reverse_unordered_selects = ON;
SELECT name FROM city;

-- The only order you can count on is the one you ask for.
SELECT name FROM city ORDER BY orders DESC, name;

┌────────┐
│  name  │
├────────┤
│ Pune   │
│ Agra   │
│ Kochi  │
│ Bhopal │
└────────┘
┌────────┐
│  name  │
├────────┤
│ Agra   │
│ Bhopal │
│ Kochi  │
│ Pune   │
└────────┘
┌────────┐
│  name  │
├────────┤
│ Pune   │
│ Kochi  │
│ Bhopal │
│ Agra   │
└────────┘
┌────────┐
│  name  │
├────────┤
│ Pune   │
│ Bhopal │
│ Agra   │
│ Kochi  │
└────────┘

The first query returned the rows in the order they were inserted, which is how SQLite happened to store them. After the index city_by_name was created, the same query returned them alphabetically: the index holds every column the query needs, so SQLite read the index instead of the table, and an index is kept in key order. The pragma reverse_unordered_selects makes SQLite return many unordered results backwards; its documentation describes it as a way to find programs that wrongly depend on an order they were never promised, and running a test suite once with it switched on is a cheap check. Only the last query, with its ORDER BY, has an order you can count on.

PostgreSQL shows the same effect after an UPDATE. Its documentation explains that an update does not immediately remove the old version of a row, because other transactions may still need to see it; the change is written as a new row version. In a small table that new version is usually stored after the others, so a plain SELECT returns the updated row last. Nothing about the data has changed, only where it sits.

Two habits follow. Write ORDER BY whenever the order matters, and end it with a unique column, as in ORDER BY name, roll_no, so that ties come back the same way every time. And name the columns in INSERT and SELECT instead of relying on the column order that SQL keeps for SELECT *: in the model, an attribute is known by its name, not by its position.

NULL marks a missing value

NULL is not a value from any domain. It is a marker that says a value is missing. Codd’s third rule, quoted in full in the last section, asks that such markers be distinct from the empty string, from a string of blanks and from zero, and that they cover both missing and inapplicable information, for every data type. His 1979 paper on extending the model set out how nulls behave under a three-valued logic of true, false and unknown, and in 1986 he argued that a value that applies but is missing and a value that does not apply at all should be marked differently.

SQL has a single NULL for every case, and in a real table it hides at least three different situations:

• The value exists but is unknown: a student has a guardian, but nobody wrote down the number.
• The value does not apply: an adult student has no guardian to call.
• The value does not exist yet: the form has not been filled in, or the exam has not been sat.

The table cannot tell these apart, and SQL’s rules treat all three the same way:

-- guardian_phone is NULL for three different reasons, which the table cannot tell apart:
-- 103 is an adult (does not apply), 104 has not filled in the form yet (not known yet),
-- 105 has a guardian whose number nobody wrote down (exists, unknown).
CREATE TABLE student (roll_no INTEGER PRIMARY KEY, name TEXT NOT NULL, guardian_phone TEXT);
INSERT INTO student VALUES
  (101, 'Asha',   '555-0101'),
  (102, 'Bilal',  '555-0101'),
  (103, 'Chitra', NULL),
  (104, 'Dev',    NULL),
  (105, 'Esha',   NULL);

-- A comparison with NULL is unknown, so "= NULL" matches no row at all.
SELECT count(*) AS equals_null FROM student WHERE guardian_phone = NULL;
SELECT count(*) AS is_null     FROM student WHERE guardian_phone IS NULL;

-- count(*) counts rows; count(column) skips NULLs.
SELECT count(*) AS students, count(guardian_phone) AS phones_known FROM student;

-- DISTINCT treats the three NULLs as one "value", as it treats the two equal numbers.
SELECT DISTINCT quote(guardian_phone) AS guardian_phone FROM student;

┌─────────────┐
│ equals_null │
├─────────────┤
│ 0           │
└─────────────┘
┌─────────┐
│ is_null │
├─────────┤
│ 3       │
└─────────┘
┌──────────┬──────────────┐
│ students │ phones_known │
├──────────┼──────────────┤
│ 5        │ 2            │
└──────────┴──────────────┘
┌────────────────┐
│ guardian_phone │
├────────────────┤
│ '555-0101'     │
│ NULL           │
└────────────────┘

guardian_phone = NULL matched no row, because a comparison with NULL is neither true nor false. PostgreSQL’s documentation explains that ordinary comparison operators “yield null (signifying ‘unknown’)” when an input is null, and WHERE keeps only the rows for which its condition is true. IS NULL found all three students, count(*) counted five rows while count(guardian_phone) counted the two known numbers, and DISTINCT put the three NULLs into one group. That last result shows the inconsistency at the heart of SQL’s NULL: for = two NULLs are not equal, while for DISTINCT and GROUP BY they are the same. The lesson on NULL and three-valued logic in the SQL track works through the truth tables.

When a column may be NULL, decide what NULL means for that column and write it down. When the reasons must be told apart, store the reason itself (a status column with values such as not_applicable and not_collected), or move the optional fact into a table of its own, where a missing row simply means “no value” and nothing has to be NULL.

Primary keys and NULL: SQLite’s documented quirk

Codd’s articles state two integrity rules for every relational database. The first, entity integrity, says that no component of a primary key may be null: a key exists to tell tuples apart, and an unknown value cannot do that. PostgreSQL enforces it. Its documentation says a primary key requires values that are “both unique and not null”, so integer PRIMARY KEY accepts the same data as integer UNIQUE NOT NULL.

SQLite documents an exception. Because of a bug in early versions that many existing databases came to depend on, a PRIMARY KEY column in SQLite accepts NULLs unless the column is an INTEGER PRIMARY KEY, the table is STRICT or WITHOUT ROWID, or the column is declared NOT NULL:

-- SQLite keeps an old quirk: a PRIMARY KEY column that is not INTEGER PRIMARY KEY accepts NULLs.
CREATE TABLE course (code TEXT PRIMARY KEY, title TEXT);
INSERT INTO course VALUES (NULL, 'Databases'), (NULL, 'Operating systems');
SELECT quote(code) AS code, title FROM course;

-- INTEGER PRIMARY KEY is the rowid: a NULL becomes the next whole number.
CREATE TABLE room (room_no INTEGER PRIMARY KEY, block TEXT);
INSERT INTO room VALUES (NULL, 'A'), (NULL, 'B');
SELECT room_no, block FROM room;

-- NOT NULL, or a STRICT table, restores entity integrity.
CREATE TABLE course_nn (code TEXT NOT NULL PRIMARY KEY, title TEXT);
INSERT INTO course_nn VALUES (NULL, 'Databases');
CREATE TABLE course_strict (code TEXT PRIMARY KEY, title TEXT) STRICT;
INSERT INTO course_strict VALUES (NULL, 'Databases');
SELECT count(*) AS rows_kept FROM course_nn, course_strict;

┌──────┬───────────────────┐
│ code │       title       │
├──────┼───────────────────┤
│ NULL │ Databases         │
│ NULL │ Operating systems │
└──────┴───────────────────┘
┌─────────┬───────┐
│ room_no │ block │
├─────────┼───────┤
│ 1       │ A     │
│ 2       │ B     │
└─────────┴───────┘
┌───────────┐
│ rows_kept │
├───────────┤
│ 0         │
└───────────┘

Runtime error near line 13: NOT NULL constraint failed: course_nn.code
Runtime error near line 15: NOT NULL constraint failed: course_strict.code

The course table took two rows whose key is NULL: for uniqueness SQLite treats each NULL as different from every other value, so neither insert broke the key. An INTEGER PRIMARY KEY is a name for the row’s built-in rowid, so a NULL there is replaced by the next whole number instead. Both fixes, NOT NULL on the column and a STRICT table, refused the NULL, which is why rows_kept is 0. In SQLite, write NOT NULL on every column of a primary key, or use STRICT tables, and you get the behaviour that PostgreSQL and the relational model expect.

Codd’s rules: what “relational” was meant to mean

By the mid-1980s many vendors sold their products as relational. In two Computerworld articles in 1985, Codd set out a test: a foundation rule, numbered 0, and twelve more, thirteen rules in all. The second article adds that a fully relational system must also support nine structural, eighteen manipulative and three integrity rules of the model. Read the rules today as a checklist of properties and as history, not as a certificate that a product passes:

• Rule 0, foundation: The system manages its databases entirely through its relational capabilities.
• Rule 1, information: All information, even table and column names, is held as values in tables.
• Rule 2, guaranteed access: Every value can be reached by a table name, a primary key value and a column name.
• Rule 3, systematic nulls: Nulls represent missing and inapplicable information, apart from empty strings and zero, for every type.
• Rule 4, online catalog: The description of the database is stored like ordinary data and queried with the same language.
• Rule 5, comprehensive language: One language covers data definition, views, data manipulation, integrity constraints, authorisation and transactions.
• Rule 6, view updating: Every view that is updatable in theory can be updated by the system.
• Rule 7, high-level changes: Insert, update and delete work on whole sets of rows, not one record at a time.
• Rule 8, physical data independence: Programs keep working when storage structures or access methods change.
• Rule 9, logical data independence: Programs keep working when tables change in ways that preserve their information.
• Rule 10, integrity independence: Integrity constraints are defined in the language and stored in the catalog, not in programs.
• Rule 11, distribution independence: Programs keep working when the data is distributed or redistributed.
• Rule 12, nonsubversion: A low-level, record-at-a-time interface cannot bypass the integrity rules.

Several rules can be tried out in a few lines of SQL:

CREATE TABLE student (roll_no INTEGER PRIMARY KEY, name TEXT NOT NULL, programme TEXT, year INTEGER);
INSERT INTO student VALUES (101, 'Asha', 'BTech', 2), (102, 'Bilal', 'MSc', 1), (103, 'Chitra', 'BTech', 3);

-- Rule 2, guaranteed access: table name + primary key value + column name reach one value.
SELECT name FROM student WHERE roll_no = 102;

-- Rule 4, the catalog: the table's own description is a table you query with SQL.
SELECT name, type, "notnull", pk FROM pragma_table_info('student');

-- Rule 8, physical data independence: a new index changes how rows are found, not the answer.
SELECT name FROM student WHERE programme = 'BTech' ORDER BY roll_no;
CREATE INDEX student_by_programme ON student (programme);
SELECT name FROM student WHERE programme = 'BTech' ORDER BY roll_no;

┌───────┐
│ name  │
├───────┤
│ Bilal │
└───────┘
┌───────────┬─────────┬─────────┬────┐
│   name    │  type   │ notnull │ pk │
├───────────┼─────────┼─────────┼────┤
│ roll_no   │ INTEGER │ 0       │ 1  │
│ name      │ TEXT    │ 1       │ 0  │
│ programme │ TEXT    │ 0       │ 0  │
│ year      │ INTEGER │ 0       │ 0  │
└───────────┴─────────┴─────────┴────┘
┌────────┐
│  name  │
├────────┤
│ Asha   │
│ Chitra │
└────────┘
┌────────┐
│  name  │
├────────┤
│ Asha   │
│ Chitra │
└────────┘

The first query reached one value with a table name, a key value and a column name, which is rule 2. The second read the table’s own description as rows, which is rule 4; the first lesson of this track showed the whole catalog. The last two queries returned the same names before and after an index was created: the index changed how SQLite finds the rows, not the answer, which is rule 8.

Other rules are kept only in part by today’s SQL databases. Duplicate rows and the single NULL depart from the model behind rules 1 and 3. View updating, rule 6, is limited in practice: PostgreSQL updates a view automatically only when it is simple, with exactly one table in its FROM list and no DISTINCT, GROUP BY or aggregates, and needs triggers for the rest. And an SQLite connection that never switches foreign keys on can store rows that break a foreign key the schema declares, which is the kind of gap rules 10 and 12 were written against; the lesson on integrity constraints shows it happening.

Interview questions

How is a relation in the relational model different from a table in SQL?

A relation is a set of tuples over named attributes. As a set it never contains the same tuple twice and its tuples have no order; every value comes from the attribute’s domain, and the model has no NULL in a domain. An SQL table is a bag: it may store identical rows unless a primary key or a UNIQUE constraint forbids them, and query results keep duplicates unless you write DISTINCT. SQL promises no row order without ORDER BY either, but it does keep a column order, which SELECT * and INSERT without a column list rely on. Finally SQL uses one NULL marker for missing values, with three-valued logic in comparisons. Declaring a key on every table and naming columns explicitly brings SQL tables close to relations.

What are the degree and the cardinality of a relation, and which one changes when you insert a row?

The degree is the number of attributes in the relation’s schema, and the cardinality is the number of tuples in its current instance. A relation student(roll_no, name, programme, year) has degree 4 whether it holds 3 tuples or 3,000. Inserting a row changes the instance, so the cardinality grows by one and the degree stays the same. The degree changes only when the schema changes, for example when ALTER TABLE adds a column.

Key takeaways

• A relation is a set of tuples over a schema; each attribute takes its values from a domain. Degree counts attributes, cardinality counts tuples.
• The schema (intension) is stable; the instance (extension) changes with every insert, update and delete.
• First normal form means atomic values in every attribute. Arrays and JSON are allowed by modern engines, but keys and foreign keys cannot reach inside them easily.
• SQL tables and query results are bags. A primary key or UNIQUE constraint makes a table a set; DISTINCT makes a result one.
• Neither the model nor SQL orders rows. Use ORDER BY with a unique tie-breaker whenever order matters.
• NULL marks a missing value for several reasons at once; decide and document what it means for each column.
• Entity integrity forbids NULL in a primary key. PostgreSQL enforces it; SQLite needs NOT NULL or a STRICT table.
• Codd’s thirteen rules (0 to 12) are a checklist of what “relational” meant, and today’s SQL systems meet some of them only in part.