Le modèle relationnel et les interrogations en SQL

I. Le modèle relationnel

Une table correspondant au schéma R(A1:X1,A2:X2,…, An:Xn) peut s’interpréter comme un ensemble de n-uplets \$(x_1,\ldots,x_n)\$ où \$x_i\in X_i\$. Autrement dit, c’est un sous-ensemble \$R\subset X_1\times\cdots\times X_n \$. C’est ce qu’on appelle une relation entre les ensembles \$X_1\$,…,\$X_n\$.

Une base de données sera donc représentée par un certain nombre de relations.

Une requête d’interrogation est une action qui prend plusieurs relations, et rend un ensemble de n-uplets, autrement dit une nouvelle relation. Une telle requête peut prendre plusieurs forme :

une caractérisation comme l’ensemble des valeurs \$ \{x_1.a_1,x_2.a_2,\ldots \, | conditions \} \$. On parle souvent dans la littérature de "langage n-uplets",
une construction ensembliste à partir des ensembles définissant les relations, en utilisant des opérations ensemblistes. On parle alors de "calcul relationnel",
une description dans un langage informatique précis, SQL (Structured Query Language).

On va préciser les choses en s’appuyant sur un exemple.

On considère une base de données décrivant les films et réalisateurs, constituée de deux tables :

Realisateurs (idR, nom, prenom, sexe, anN, pays)
Films (idF, titre, type, anR, idR)

II. Langage basé sur les n-uplets

Si on veut connaître les noms et prénoms des réalisateurs français nés avant 1950, on peut énoncer cette requête :

\$ \{ x.nom, x.prenom | Realisateurs(x) \wedge (x.anN < 1950) \wedge (x.pays = France) \} \$

Une requête peut aussi faire intervenir plusieurs relations, ainsi que des quantificateurs.

Ainsi, pour caractériser les réalisateurs qui ont réalisé au moins une comédie :

\$ \{ x.nom, x.prenom | Realisateurs(x) \wedge (\exists y (Films(y) \wedge (y.type = comedie) \wedge (y.idR = x.idR))) \} \$

III. Le calcul relationnel

Chaque relation est un ensemble. On peut donc appliquer à des relations des opérateurs ensemblistes :

union : \$ rel_1 \cup rel_2 \$
produit cartésien : \$ rel_1 \times rel_2 \$
sélection des éléments vérifiant une propriété P :\$ \sigma_P (rel)\$
projection sur un nombre restreint d’attributs : \$ \Pi_{X_1,\ldots,X_p} (rel)\$

A cela il faut rajouter un opérateur spécifique, qui sera particulièrement utile : la jointure.

\$ rel_1 \bowtie _P rel_2\$

Cela décrit l’ensemble des éléments du produit cartésien des deux relations qui vérifient la propriété P. Même si cet opérateur se décrit entièrement avec les précédents, son rôle est tellement important dans le cadre des bases de données pour qu’on lui donne un nom particulier.

Traduire en calcul relationnel les deux requêtes du paragraphe précédent.

A la différence d’une requête en langage de type n-uplet, une expression du calcul relationnel explicite exactement quelles opérations, et dans quel ordre, on doit effectuer pour obtenir le résultat recherché. Plusieurs traductions, correspondant à plusieurs méthodes de calcul peuvent donc être produites pour réaliser la même requête.

IV. Les requêtes d’interrogation dans SQL

Le mot clé pour toutes les requêtes d’interrogation est SELECT. Une requête SELECT rend un ensemble de n-uplets (table). Une requête élémentaire comme

SELECT 1+1, 2+3 ;

rendra une table avec une ligne et deux colonnes de noms "1+1" et "2+3" et de valeurs 2 et 5. Mais, bien sûr, on regardera surtout des requêtes plus pertinentes.

Voici deux exemples de requêtes effectuées sur notre base de films/réalisateurs :

Les noms et prénoms des réalisateurs français nés avant 1950 :

SELECT Realisateurs.nom, Realisateurs.prenom
FROM Realisateurs
WHERE Realisateurs.anN < 1950 AND Realisateurs.pays = "France" ;

Les noms et prénoms des réalisateurs ayant réalisé une comédie :

SELECT Realisateurs.nom, Realisateurs.prenom
FROM Realisateurs, Films
WHERE Realisateurs.idR = Films.idR AND Films.type = "Comedie" ;

Dans ce deuxième exemple, on a réalisé une jointure de deux tables.

On remarquera une différence entre le monde SQL et le monde ensembliste dans lequel on a défini initialement les requêtes. Dans un ensemble, un élément apparait exactement une fois. Dans une table, plusieurs enregistrements peuvent être identiques. Et même si les enregistrements sont tous distincts initialement, rien n’empêche que le résulat d’une requête ait des lignes identiques. Ce sera ainsi le cas de la deuxième requête, où le réalisateur apparaîtra autant de fois qu’il a réalisé de comédies.

Pour obtenir des lignes uniques, il faut rajouter la clause DISTINCT :

SELECT DISTINCT Realisateurs.nom, Realisateurs.prenom
FROM Realisateurs, Films
WHERE Realisateurs.idR = Films.idR AND Films.type = "Comedie" ;

Il faut être conscient que ce simple mot DISTINCT correspond à une opération couteuse au niveau de la machine, car il oblige le SGBD à parcourir toute la table pour trouver et éliminer les doublons. On reviendra plus tard sur ce genre de questions.

La syntaxe de `SELECT`

La forme la plus générale de l’appel à SELECT est

SELECT clause attributs_affiches AS surnoms
FROM table
WHERE condition
GROUP BY  attribut
HAVING condition
ORDER BY attribut  [ASC | DESC]
LIMIT  nombre ;

On peut indiquer ou non la clause UNIQUE, qui élimine les doublons dans les n-uplets affichés.

La clause GROUP BY attributx regroupe les enregistrements par groupe de valeurs de l’attribut attributx. Les attributs affichés doivent être uniques pour chaque groupe, ou bien correspondre à des valeurs agrégées.

Ainsi la commande

SELECT nom, adresse, montant
FROM table
GROUP BY  nom ;

déclenchera une erreur, car en face d’un nom, il y a généralement plusieurs montants. En revanche, on peut calculer la somme de ces montants :

SELECT nom, adresse, SUM(montant) AS montant_total
FROM table
GROUP BY  nom ;

On notera aussi l’usage du AS qui renomme une colonne affichée.

La clause HAVING permet d’imposer une condition portant sur les valeurs agrégées :

SELECT nom, adresse, SUM(montant) AS montant_total
FROM table
GROUP BY  nom
HAVING montant_total > 1000
ORDER BY montant_total ;

La différence entre les clause WHERE et HAVING est que la sélection se fait avant le calcul d’agrégation pour WHERE, et après ce calcul pour HAVING.

Les jointures internes

Les jointures internes permettent de relier deux tables, en prenant tous les couples d’enregistrements qui coincident selon un certain critère :

SELECT t1.att1, t1.att2, t2.att3
FROM table1 AS t1, table2 AS t2
WHERE t1.att4 = t2.att4 ;

ou :

SELECT t1.att1, t1.att2, t2.att3
FROM table1 AS t1,
JOIN table2 AS t2 ON t1.att4 = t2.att4 ;

On aurait encore pu écrire :

SELECT t1.att1, t1.att2, t2.att3
FROM table1 AS t1,
JOIN table2 AS t2 USING (att4) ;

Ces différentes écritures sont équivalentes et donnent lieu au même plan d’exécution sur le SGBD.

Les jointures externes

Lors d’une jointure interne, tous les enregistrements où l’attribut de jointure n’est pas renseigné dans l’une ou l’autre des tables n’apparaîtront pas dans le résultat. Si on veut cependant faire apparître ces enregistrements, on dispose des jointures externes.

Ainsi, considérons les deux tables

prenom	age
Paul	35
Pierre	21
Jacques	79
Marc	2

prenom	age
Marie	35
Anne	79
Claire	35
Julie	3

la requete

SELECT H.prenom AS ph, F.prenom AS pf
FROM H, F
JOIN F on H.age = F.age

rendra :

ph	pf
Paul	Marie
Paul	Claire
Jacques	Anne

Paul

Marie

Paul

Claire

Jacques

Anne

alors que

SELECT H.prenom AS ph, F.prenom AS pf
FROM H, F
LEFT JOIN F on H.age = F.age

rendra :

ph	pf
Paul	Marie
Paul	Claire
Pierre
Jacques	Anne
Marc

Paul

Marie

Paul

Claire

Pierre

Jacques

Anne

Marc

SELECT H.prenom AS ph, F. prenom AS pf
FROM H
FULL OUTER JOIN F on H.age = F.age

rendra :

ph	pf
Paul	Marie
Paul	Claire
Pierre
Jacques	Anne
Marc
	Julie

Paul

Marie

Paul

Claire

Pierre

Jacques

Anne

Marc

Julie

Sous-requêtes, requêtes imbriquées

On peut utliser le résultat d’une requête à l’intérieur d’une autre.

Requête imbriquée rendant un seul résultat

SELECT *
FROM `table`
WHERE `nom_colonne` = (
    SELECT `valeur`
    FROM `table2`
    LIMIT 1
)

Ici la requête interne rend un résultat unique ; on peut donc faire un test d’égalité.

Requête imbriquée qui retourne une colonne

Une requête imbriquée peut également retourner une colonne entière.

Dans ce cas, la commande IN permet de filtrer dans la requête externe les lignes qui possèdent une des valeurs retournées par la requête interne.

SELECT *
FROM `table`
WHERE `nom_colonne` IN (
    SELECT `colonne`
    FROM `table2`
    WHERE une_condition
)

La clause `WITH`

La clause WITH permet de découper une requête compliquée en parties plus simples. C’est une autre façon de fabriquer des requêtes imbriquées.

La syntaxe est :

WITH nom1 AS (requete1), nom2 AS (requete2)
requete_utilisant_les noms_définis

Voici un exemple où on commence par définir successivement deux tables regional_sales et top_regions, puis on effectue une requête utilisant la table top_regions.

WITH regional_sales AS (
        SELECT region, SUM(amount) AS total_sales
        FROM orders
        GROUP BY region
     ), top_regions AS (
        SELECT region
        FROM regional_sales
        WHERE total_sales > (SELECT SUM(total_sales)/10 FROM regional_sales)
     )
SELECT region,
       product,
       SUM(quantity) AS product_units,
       SUM(amount) AS product_sales
FROM orders
WHERE region IN (SELECT region FROM top_regions)
GROUP BY region, product;

La recherche de motifs

On trouvera une documentation de Postgresql

Par défaut SQL est assez pauvre en matière d’expressions régulières.

Il propose un prédicat LIKE (ou NOT LIKE), permettant de comparer une expression à un motif. Le motif est une chaîne de caractères normaux avec deux caractères spéciaux :

% qui signifie "un nombre quelconque de caractères"
_ qui signifie "exactement un caractère"

Il existe aussi ILIKE, qui fait la même chose que LIKE, mais qui est insensible à la casse. Il est implémenté dans Postgresql, mais pas dans SQLite.

Une extension de SQL, implémentée dans Postgresql, implémente les expressions régulières POSIX (celles qui sont reconnues par la commande egrep de unix). On a alors les prédicats

~ : sensible à la casse, compare deux expressions et retourne True si la première est contenue dans la deuxième
~* : insensible à la casse, compare deux expressions et retourne True si la première est contenue dans la deuxième
!~ : sensible à la casse, compare deux expressions et retourne False si la première est contenue dans la deuxième
!~* : insensible à la casse, compare deux expressions et retourne False si la première est contenue dans la deuxième

Le traitement des dates

Les dates sous unix, sont comptées en secondes à partir du 1er janvier 1970 :

$ date
sam. 16 janv. 2021 17:43:47 CET

$ date +%s
1610815445

Les fonctions de traitement et les modes de stockage des dates dépendent du SGBD utilisé.

La documentation de sqlite
La documentation de Postgresql sur les types et sur les opérateurs de date

Comment le SGBD interprète-t-il les requêtes ?

Une commande SQL décrit ce qu’on attend, et le SGBD se charge de définir un plan d’exécution qu’il va suivre pour effectuer cette requête. Considérons une requête

SELECT ... FROM ... WHERE ...

En utilisant le mot clé EXPLAIN, on peut ainsi demander à PostgreSQL d’afficher le plan d’exécution associé :

EXPLAIN SELECT ... FROM ... WHERE ...

On peut aussi indiquer EXPLAIN ANALYSE. Dans ce cas, le SGBD exécute aussi la commande et affiche le temps d’exécution (faire attention que les commandes sont effectuées, et qu’on peut donc ainsi modifier ou détruire des données).

Algorithmes de jointure

On veut faire une jointure de deux relations R et S suivant une colonne.

L’algorithme le plus naïf est de faire deux boucles imbriquées qui parcourent les deux relations R et S, de longueurs \$m\$ et \$n\$ :

algorithm nested_loop_join :
    for each tuple r in R do
        for each tuple s in S do
            if r and s satisfy the join condition then
                yield tuple <r,s>

La complexité est en \$ mn\$.

Une autre façon est de fabriquer des tables de hachage pour chacune des deux colonnes utilisée, puis de comparer les hachages. Ici ce qui prends le plus de temps est la fabrications des tables de hachage. On arrive à une complexité en \$ n \log n + m\log m \$.

Si on a deux tables de grandes tailles, la jointure par hachage est plus efficace ; en revanche, si l’une des tables est de petite taille, les boucles imbriquées sont plus performantes.

En utilisant la base PostgreSQL chinook2 sur data, regarder les plans d’exécution pour les requêtes suivantes :


-- Jointure implicite

select c.First_Name,
    c.Last_Name,
    i.Invoice_Id,
    i.Invoice_Date,
    i.Billing_Country
from customer c, invoice i
where i.Customer_Id=c.Customer_Id
    and c.Country='Brazil';

-- Jointure explicite

select c.First_Name,
    c.Last_Name,
    i.Invoice_Id,
    i.Invoice_Date,
    i.Billing_Country
from customer c
    join invoice i
        on i.Customer_Id=c.Customer_Id
where c.Country='Brazil';

-- requetes imbriquees

select c.First_Name,
    c.Last_Name,
    i.Invoice_Id,
    i.Invoice_Date,
    i.Billing_Country
from (select * from customer where Country='Brazil') c
    join invoice i
        on i.Customer_Id=c.Customer_Id ;


-- jointure avec une petite table

select * from track t
	join media_type mt
		on t.media_type_id = mt.media_type_id
where mt.name = 'AAC audio file' ;

Le modèle relationnel et les interrogations en SQL

I. Le modèle relationnel

II. Langage basé sur les n-uplets

III. Le calcul relationnel

IV. Les requêtes d’interrogation dans SQL

La syntaxe de SELECT

Les jointures internes

Les jointures externes

Sous-requêtes, requêtes imbriquées

Requête imbriquée rendant un seul résultat

Requête imbriquée qui retourne une colonne

La clause WITH

La recherche de motifs

Le traitement des dates

Comment le SGBD interprète-t-il les requêtes ?

Algorithmes de jointure

La syntaxe de `SELECT`

La clause `WITH`