Skip to content
Information Systems

The relational model: keys, constraints and relational algebra

Relations, tuples and domains, existence of a key proved, integrity constraints and foreign keys, selection, projection and join, the cardinality of a join proved, from algebra to SQL.

4 min read 0 comments

In 1970 Edgar Codd, an IBM researcher, proposed representing data as simple tables and querying them with mathematical operations, instead of navigating among pointers as in the systems of the time. The relational model is still the basis of almost every information system. In this lesson we look at relations and keys with the proof that every relation has at least one, integrity constraints, relational algebra with selection, projection and join, the proof of the bounds on the size of a join, and the link with SQL.

Relations, tuples and attributes

A relation is a table with a name, named columns (the attributes) and rows (the tuples). Mathematically it is a set of tuples: the order of rows does not matter and no two rows are equal. Each attribute takes values in a domain (integers, dates, strings), and each cell contains a single atomic value. The relation’s schema is the name with the attributes, Student(number, first_name, surname, birth); the instance is the content at a given moment.

Keys

A superkey is a set of attributes that never takes the same value in two different tuples. A key is a minimal superkey: removing any attribute it is no longer a superkey.

Theorem. Every relation has at least one key.

Proof. The set of all attributes is a superkey: two tuples with all values equal would be the same tuple, and a relation is a set, so it has no duplicates. If this superkey is not minimal, remove an attribute that leaves it a superkey, and repeat. There are finitely many attributes, so the procedure terminates, and the set it reaches is a superkey from which nothing can be removed: a key. ∎

Among the keys one is chosen as primary key, on which null values are not allowed. An artificial code (a sequential number) is often used even when a natural key exists, because it is more stable and more compact.

Integrity constraints

The model does not accept just any data: constraints express the rules of the real world and the DBMS enforces them.

  • Domain and tuple constraints: the mark is between 18 and 30, the end date does not precede the start date.
  • Key constraint: no duplicates on the primary key, no null values.
  • Referential integrity: a foreign key must refer to an existing tuple. Every exam refers to a student present in the Student table. When the student is deleted, the DBMS can refuse the deletion, delete their exams too (cascade) or set the reference to null, according to how the constraint was declared.

Relational algebra

Queries are built with operators that take relations and return relations, and can therefore be composed:

  • selection \sigma_{cond}(R): the tuples satisfying a condition, i.e. a subset of the rows;
  • projection \pi_{A,B}(R): only some columns, eliminating the resulting duplicates;
  • union, difference, intersection of relations with the same schema;
  • renaming of attributes;
  • natural join R \bowtie S: combines the tuples of the two relations that have equal values on the common attributes.
Natural join of two relations
R and S share attribute B. The result contains one tuple for each pair of tuples of R and S with the same value of B: tuple a2 b2 has no match in S and disappears, while each tuple with b1 combines with both tuples of S with b1.

Theorem. The natural join of R and S has a number of tuples between 0 and |R|\cdot|S|. If the common attributes contain a key of S, the result has at most |R| tuples; if moreover there is a referential integrity constraint from R to S on those attributes, it has exactly |R|.

Proof. Every tuple of the result comes from a pair of tuples, one of R and one of S, and the possible pairs are |R|\cdot|S|: this is the maximum, reached when all have the same value on the common attributes. The minimum 0 occurs when no value matches. If the common attributes contain a key of S, for every tuple of R there is at most one tuple of S with those values, so every tuple of R contributes at most one tuple to the result. With the referential constraint that tuple of S always exists, and the contribution is exactly one. ∎

It is the most common case: joining exams (with the foreign key) to students (with the key) gives one row per exam, enriched with the student’s data. Knowing this helps to understand when a query returns “too many rows”: usually the join was on attributes that are not a key.

From algebra to SQL

SQL, the language of all relational DBMSs (lesson on SQL), is a declarative language built on these operations: one says what is wanted, not how to get it.

SELECT s.surname, e.mark
FROM Student s JOIN Exam e ON s.number = e.number
WHERE e.mark >= 28;

corresponds to \pi_{surname,\,mark}(\sigma_{mark \ge 28}(Student \bowtie Exam)). The DBMS translates the request into an algebra expression and optimises it with algebraic equivalences: for instance it performs the selection before the join, so that fewer tuples are joined. This independence between the question and the way of answering it, made possible by the model’s mathematical basis, is the main reason for its success.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x