Chapter 6 - The Relational Model

All modern web applications rely on databases, which provide durable storage and fast access to data.

The structure of a database is fundamental to the design of a web application. A poor structure makes the queries that access the data more complex, and therefore a potential source of errors. It also causes performance problems when accessing the data.

This chapter introduces the concepts used to structure relational databases, explaining what is at stake and what the goals are.

A note on naming: the tables and columns in this book keep their original French names (for example auteurs for authors, nom for name, prenom for first name, annee for year), because they match the code of the online example projects. Their meaning is given the first time they appear.

Structuring data

All web applications follow the same process: collect raw data, structure it so that it can be used, and finally provide knowledge about it.

Raw data is provided by users when they fill in forms. Take our example application for managing images. When a user wants to add an image, the application asks them to enter the name of the image, its orientation (portrait or landscape) and the date it was created. The user enters this data, but it does not mean much yet because it is still raw.

Once raw data has been entered, the application must structure it so that it can be used. The goal of structuring is to validate the format of the data and make it consistent. In our example, the application checks that the orientation is either 'portrait' or 'landscape' and that the date was entered correctly, then groups all the data together to form a complete and consistent description of an image.

Once validated and structured, the data becomes usable, which makes it possible to derive knowledge from it. With our image management application, as soon as several images have been stored in the database, it becomes possible to search for some of them, for example those in 'portrait' orientation created before 1900.

Setting up a database requires defining a high-quality structure for the data. By high-quality, we mean that knowledge can be expressed easily and computed quickly, and that the data needed to establish it takes up as little space as possible.

While there are several ways to structure data (lists, arrays, trees, graphs, etc.), relational databases have chosen to use only tables containing elementary values (booleans, numbers, character strings, etc.). These tables are called the tables of the database. This choice is motivated by the simplicity of the structure and the ease of manipulating the data. Indeed, once the structure of the tables has been defined, the data can be accessed easily and quickly.

Tables

Structuring a relational database means defining the tables it contains. A table represents a coherent concept of the application and has a name corresponding to that concept. For example, for an image management application, you can define a table of images, a table of authors, etc.

A table contains a finite set of columns. Each column has a name and a basic type (boolean, number, character string of bounded length, date, etc.). It is important to note that a column cannot contain a complex value (no lists, arrays, trees, etc.). The columns of a table represent the attributes of the concept the table represents. For example, in the table of authors, you can define the columns nom (last name) and prenom (first name), both of type character string of at most 30 characters (the choice of 30 is arbitrary here; it seems enough to us to enter every possible last name and first name). These two columns (last name, first name) define what an author is.

A row of a table represents a unique entity. For example, in the table of authors, each row represents an author. Two rows cannot be identical, because that would mean storing the same entity twice.

Finally, to tell each entity apart, a table must define one or more columns that serve as a key to distinguish the entities from one another. The column or columns that serve as the key are called the table's primary key. If no key can be found among the existing columns, a simple solution is to add a new column that will serve as the key (often named id).

The table of authors of our example application is shown in Table 6.1. You can see that this table has three columns, one of which is the primary key (the id column). We added this column because neither the first name nor the last name can serve as a key in this table (some people share the same first name, others the same last name, and there are even people with exactly the same name). In the example, three entities are stored in the table. Each of these entities has a different id.

Table 6.1: The authors table with three entities.

Associations between tables

The concepts handled by a web application are often associated with one another. In our image management application, each image is associated with an author, and each author is associated with several images.

The structure of a database must represent these associations. To do this, we use foreign keys, which define links between two tables.

Defining foreign keys is an important part of structuring a database. The most important and most difficult question is where to place the foreign keys (in which tables?). To answer it, it is better to consider the multiplicity of an association rather than its meaning. There are two multiplicities to consider: the one-to-many multiplicity (written 1-*) and the many-to-many multiplicity (written *-*).

An association of multiplicity 1-* between a table A and a table B (written A 1-* B) is an association in which an entity of table A is associated with several entities of table B, but an entity of table B can be associated with only one entity of table A. In our image management application, an author can be associated with several images, but an image can be associated with only one author. We therefore have the association Authors 1-* Images.

In the case of a 1-* association, the foreign key is placed in the table whose entities each point to a single entity of the other table (the "many" side). In our example, the foreign key is therefore placed in the table of images. Thanks to the foreign key, each entity of the table of images references an entity of the table of authors. Several entities of the table of images can therefore reference the same entity of the table of authors (an author can thus be associated with several images). Table 6.2 shows the table of images and illustrates the association between an author and several images. The auteur (author) column of the table of images is a foreign key that references the primary key "id" of the table of authors. Thanks to this foreign key, you can find the author associated with an image. For example, you can see that "Robert Doisneau" is the author of the image named "Le baiser de l'hôtel de ville" (The Kiss by the Hôtel de Ville).

Table 6.2: The Images table with four entities.

An association of multiplicity *-* between a table A and a table B (written A *-* B) is an association in which an entity of table A is associated with several entities of table B, and an entity of table B is associated with several entities of table A. In our example, an image album can be associated with several images, and an image can be associated with several image albums (images are referenced, not copied). We therefore have the association Image-Albums *-* Images.

To define a *-* association in a database, you must add a new table that represents the association between the two associated tables, then place two foreign keys in this new table (one to each of the two associated tables). For our example, the table of image albums is shown in Table 6.3. It contains two image albums (Must-See and Black and White).

Table 6.3: The table of image albums with two entities.

The table representing the association between image albums and images is shown in Table 6.4. This table contains two columns, which are two foreign keys (one to the image albums and the other to the images). The entities of this table express the associations between image albums and images. You can see that the image album Must-See is associated with images 2 and 4. The image album Black and White is associated with images 1, 2 and 3.

Table 6.4: The table representing the "*-*" association between image albums and images.

Optimization

Structuring a database does not stop at defining the tables and their associations. The database must also be optimized to be as efficient as possible. One important point is to reduce data redundancy as much as possible. A piece of data is said to be redundant if it is replicated several times in the database. This causes efficiency problems (in space and access time), but also integrity problems, because you must make sure that redundant data stays consistent, especially when it is modified.

Let's go back to the table of images, adding an orientation column whose type is a character string of at most 10 characters (see Table 6.5). You can see that the orientation data is redundant, because the information is repeated for every entity. Here, the structure of the database cannot guarantee data integrity. Indeed, nothing prevents invalid values from being put in the orientation column (any character string). This can cause integrity problems.

Table 6.5: The table of images with the orientation.

This database can be optimized by creating a new table (the table of orientations) containing all the possible orientations (see Table 6.6).

Table 6.6: The table of orientations.

Thanks to this table, the orientations of the images can be specified more precisely in the table of images. More precisely, this is an association Orientations 1-* Images. This association can be set up by making the orientation column of the Images table a foreign key to the primary key of the Orientations table (see Table 6.7). This optimization saves space but, above all, it guarantees that the orientation can only be portrait or landscape, as defined in the Orientations table.

Table 6.7: The table of images optimized to store orientations.

Formalization

The principles for structuring databases are defined formally, with a theoretical foundation drawn from mathematics. In this section we give more rigorous definitions of the concepts presented in the previous sections.

From a formal point of view, a database stores data as relations. The term relation is used here in its mathematical sense: given domains D₁, D₂, ..., D_n, R is a relation over these n domains if it is a finite set of tuples belonging to the Cartesian product of the domains (D₁ X D₂ ... X D_n). A relation is therefore a finite subset of the Cartesian product of the domains.

For example, the data contained in the table of images is formally defined by the Cartesian product (id X nom X annee). An element of the relation is the tuple (1, 'Charles Baudelaire', 1863).

Relations are abstract concepts. To present them easily, we give them a name and represent each of their domains by a name and a type: this is called a relational schema.

The relational schema auteur(id, prenom(char(30)), nom(char(30))) represents the structure of the auteurs (authors) relation. It defines three attributes: id, prenom and nom.

The concept of relational schema makes it possible to define formally the concept of primary key, which is a set of attributes that uniquely identifies each tuple of the relation. In other words, knowing the key lets you identify the corresponding tuple.

Taking the relation of authors as an example, you can see that neither the attribute prenom nor the attribute nom satisfies the uniqueness constraint. Indeed, two authors may well have the same last name and/or the same first name. You could then consider that the attributes id and prenom form a primary key, but this would not satisfy the minimality constraint, because the attribute prenom could be removed without violating the uniqueness constraint. For the relation of images, only the attribute id can be the primary key.

The concept of foreign key is also defined formally thanks to the concept of relational schema. It creates a link between two relations.

Taking the relation of images as an example, you can see that the attribute orientation is a foreign key to the relation of orientations. Likewise, the attribute auteur is a foreign key to the relation of authors. Note that the type of the orientation attribute is a simple integer (as is the type of the auteur attribute). Nevertheless, its possible values are constrained by the existence of a matching primary key in the relation of orientations (and likewise for authors).

The definitions we have just presented formally define the fundamental concepts of relational databases. We will now define functional dependencies, which help explain the goals of database optimization.

In the relation of authors, we have id -> nom, because you know an author's last name once you know their identifier. On the other hand, the functional dependency nom -> prenom does not hold, because knowing an author's last name does not tell you their first name. Note that functional dependencies are transitive (if X -> Y and Y -> Z, then X -> Z).

From a formal point of view, optimizing a database aims to satisfy constraints specified in what are called normal forms. Here we are interested in the first three normal forms of databases. They formally lay the foundations of a high-quality data structure.

The relations we presented for our example application are in third normal form. They are well formed in the sense that all values are elementary, all relations have at least one primary key, and all attributes functionally depend on a primary key.

SQL

The structure of a relational database can be described using the SQL language (Structured Query Language). SQL is a standard language, but each database management system (DBMS) may have its own variations. Here we use the syntax of Postgres, a free and open-source DBMS.

Before creating tables, you must start by creating a database. Note that a database management system can host several databases, each identified by a name. Code 6.1 shows the SQL command that creates the database named application_image.

CREATE DATABASE application_image;

Code 6.1: Creating a database in SQL.

Once the database has been created, tables can be created. A table is created by giving its name, its attributes and their types. The SQL types are CHAR for a fixed-length character string, VARCHAR for a character string of bounded length, TEXT for a character string, DEC for a decimal, INT for an integer, REAL for a binary floating-point number, BOOLEAN for true or false, and DATE for a date.

Code 6.2 shows the SQL command that creates the auteurs table. You can see that the attributes prenom and nom are of type VARCHAR(100) and that the attribute prenom cannot be empty.

CREATE TABLE auteurs (
    prenom VARCHAR(100) NOT NULL,
    nom VARCHAR(100)
);

Code 6.2: Creating a table in SQL.

Postgres also offers the SERIAL type, which creates an integer attribute that is automatically incremented each time a new row is inserted into the table. This type is very handy for creating primary keys. Code 6.3 shows the SQL command that creates the auteurs table with a primary key of type SERIAL.

CREATE TABLE auteurs (
    id SERIAL PRIMARY KEY,
    prenom VARCHAR(100) NOT NULL,
    nom VARCHAR(100)
);

Code 6.3: Creating a table in SQL with the SERIAL type.

A table with a foreign key must be created after the table targeted by the foreign key. The SQL command must specify that the attribute is a foreign key and that it references a key of another table. Code 6.4 shows the SQL command that creates the images table with a primary key and a foreign key to the auteurs table (attribute id).

CREATE TABLE images (
    id SERIAL PRIMARY KEY,
    nom VARCHAR(100) NOT NULL,
    annee DATE,
    orientation VARCHAR(10),
    auteur_id int references auteurs(id)
);

Code 6.4: Creating a table in SQL with a foreign key.

Once the tables are created, rows can be inserted into the database. Code 6.5 shows the insertion of three authors and four images.

INSERT INTO auteurs (prenom, nom) VALUES ('Etienne', 'Carjat');
INSERT INTO auteurs (prenom, nom) VALUES ('Robert', 'Doisneau');
INSERT INTO auteurs (prenom, nom) VALUES ('Yann', 'Arthus-Bertrand');
INSERT INTO images (nom, annee, orientation, auteur_id) VALUES ('Charles Baudelaire', '1863-01-01', 'portrait', 1);
INSERT INTO images (nom, annee, orientation, auteur_id) VALUES ('Le baiser de l hotel de ville', '1950-01-01', 'landscape', 2);
INSERT INTO images (nom, annee, orientation, auteur_id) VALUES ('Les freres', '1936-01-01', 'portrait', 2);
INSERT INTO images (nom, annee, orientation, auteur_id) VALUES ('Coeur de Voh', '1992-01-01', 'landscape', 3);

Code 6.5: Inserting entities into tables in SQL.

To modify an entity in a table, use the SQL UPDATE command, giving the name of the table, the new values of the columns (SET) and a filter to select the entities to modify (WHERE). For example, Code 6.6 is an SQL command that changes the year of the 4th image to the new value '1950-02-03'.

UPDATE images SET annee = '1950-02-03' WHERE id=4;

Code 6.6: Modifying an entity of a table in SQL.

Finally, to delete an entity, use the SQL DELETE command. The DROP TABLE and DROP DATABASE commands delete an entire table or even an entire database. For example, Code 6.7 shows several commands that delete an entity, two tables and then the database.

DELETE FROM images WHERE id=4;
DROP TABLE images;
DROP TABLE auteurs;
DROP DATABASE application_image;

Code 6.7: Deleting an entity, a table and a database in SQL.

Practice

Review questions

Exercise 1 - Sports competitions

Project - Image wall