Bases de données & SQL · L2 · Section 2/11

Algèbre relationnelle

Progression

—XP—· —— / —compris

#Algèbre relationnelle

L'algèbre relationnelle est le calcul formel derrière SQL : un petit ensemble d'opérations sur des relations, composables, dont chaque requête est une expression. La maîtriser donne deux pouvoirs : prouver qu'une requête est correcte (elle calcule bien la réponse à la question posée) et la transformer en une expression équivalente plus efficace.

#Prérequis et objectifs

Prérequis : la section Modélisation (relation, attribut, clé) et le vocabulaire ensembliste (union, intersection, différence, produit cartésien).

Nommer et composer les opérateurs : sélection, projection, renommage, union, différence, produit, jointure, division.

Traduire une expression d'algèbre en SQL, et inversement.

Appliquer les règles de réécriture pour réduire les volumes intermédiaires.

#Le cadre formel

Trois propriétés définissent l'algèbre relationnelle, et chacune a une conséquence pratique.

C'est un langage procédural : une expression indique comment construire une nouvelle relation à partir d'une ou plusieurs relations existantes. C'est la différence de nature avec SQL, qui est un langage orienté transformation.
C'est un langage abstrait : les opérations travaillent sur des relations pour définir une nouvelle relation, sans modifier les relations d'origine. Une expression d'algèbre ne détruit rien ; elle produit.
Le résultat de toute opération est une relation : c'est la propriété de fermeture. Elle est ce qui rend la composition possible — π_name(σ_amount>50(R ⋈ S)) n'est possible que parce que σ_amount>50(R ⋈ S) est elle-même une relation.

Cinq opérations sont fondamentales : sélection, projection, produit cartésien, union, différence. Toutes les autres — jointure, intersection, division — s'en déduisent. Savoir laquelle est fondamentale et laquelle est dérivée n'est pas un détail scolastique : c'est ce qui permet de dire qu'une réécriture est légitime.

#Compatibilité envers l'union

Les opérateurs ensemblistes (∪, ∩, −) n'ont de sens que sur des relations compatibles envers l'union. La condition est double :

même degré : les deux relations ont le même nombre d'attributs ;
domaines compatibles, attribut par attribut : le i-ème attribut de l'une a le même domaine que le i-ème attribut de l'autre.

Les noms d'attributs, eux, n'ont pas besoin d'être identiques — mais le résultat porte les noms de la première relation. C'est la question la plus fréquemment posée sur les opérateurs ensemblistes : R ∪ S avec R de degré 3 et S de degré 4 est une erreur, pas une union partielle.

Le produit cartésien, lui, n'exige aucune compatibilité : les schémas peuvent être quelconques. Il produit le degré de R plus le degré de S, et la cardinalité de R multipliée par celle de S. C'est précisément pourquoi on ne l'évalue jamais tel quel sur de grosses relations.

#Les opérateurs de base

Une relation est un ensemble de n-uplets sans doublons ; les opérateurs prennent des relations et retournent des relations.

Sélection σ_condition(R) : garde les lignes qui vérifient la condition. Homologue SQL : WHERE.
Projection π_a,b(R) : garde les colonnes a et b, en éliminant les doublons. Homologue SQL : SELECT a, b (avec DISTINCT pour retrouver la sémantique ensembliste exacte).
Renommage ρ_S(R) : renomme la relation ou ses attributs. Homologue SQL : les alias AS.
Union R ∪ S : les lignes de R et de S, schémas identiques requis. Homologue : UNION.
Différence R − S : les lignes de R absentes de S. Homologue : EXCEPT.
Produit cartésien R × S : toutes les combinaisons de lignes. Homologue : CROSS JOIN.

#Opérateurs dérivés

Ils se définissent à partir des précédents, et c'est leur intérêt : chaque dérivation est une réécriture possible.

Jointure naturelle : R ⋈ S = σ_{R.k = S.k}(R × S), puis projection des colonnes dupliquées. Homologue : JOIN ... USING (k).
Jointure thêta : R ⋈_θ S = σ_θ(R × S). Homologue : JOIN ... ON θ.
Semi-jointure R ⋉ S : les lignes de R qui ont au moins une correspondance dans S, sans les colonnes de S. Homologue SQL : WHERE EXISTS.
Anti-jointure R ▷ S : les lignes de R sans correspondance dans S. Homologue : WHERE NOT EXISTS.
Division R ÷ S : les lignes de R (privées des attributs de S) complètes vis-à-vis de toutes les lignes de S. La réponse aux questions en « tous les ».

#Jointures : les définitions précises

Jointure thêta R ⋈_P S : la relation qui contient les tuples satisfaisant le prédicat P du produit cartésien de R et S. Le prédicat P est de la forme $R.a_i \,\theta\, S.b_j$ , où $\theta$ est l'un des opérateurs de comparaison : $<$ , $\leq$ , $>$ , $\geq$ , $=$ , $\neq$ . Retenez cette liste : une jointure sur un prédicat qui n'est pas une comparaison entre un attribut de R et un attribut de S n'est pas une thêta-jointure.

Équijointure : le cas particulier où P est l'égalité ( $=$ ).

Jointure naturelle R ∗ S : une équijointure des relations R et S sur tous les attributs communs, en retirant les occurrences multiples d'attributs. Deux conséquences qu'un énoncé d'examen exploite :

elle porte sur tous les attributs de même nom, pas seulement sur celui qu'on avait en tête ; si R(a, b, c) et S(b, c, d), la jointure naturelle joint sur b et c ;
elle ne duplique pas les colonnes de jointure, contrairement à une thêta-jointure d'égalité sur laquelle on projette ensuite.

Jointure externe gauche entre R et S : les tuples de R qui n'ont pas de valeur correspondante dans S parmi les attributs communs sont également inclus dans la relation résultante, les valeurs manquantes de la seconde relation étant mises à nul. La jointure externe droite conserve tous les tuples de la relation de droite ; la jointure externe complète reprend tous les tuples des deux relations et remplit de nuls les attributs absents dans tous les cas de non-correspondance.

Semi-jointure entre R et S : la relation qui contient les tuples de R qui participent à la jointure de R avec S. Le degré du résultat est celui de R : c'est exactement l'opération « filtrer sans projeter », celle que SQL exprime par EXISTS.

#Division : la formule officielle

Soit R définie sur l'ensemble d'attributs A, et S définie sur l'ensemble d'attributs B avec $B \subseteq A$ . On pose $C = A - B$ . La division $R \div S$ est une relation sur les attributs C, constituée de l'ensemble des tuples de R qui correspondent à la combinaison de tous les tuples de S.

La construction se démontre en trois étapes, et c'est cette démonstration qu'un examen peut demander :

$T_1 = \pi_C(R)$ $T_2 = \pi_C\big((S \times T_1) - R\big)$ $T = T_1 - T_2$

Lecture : $T_1$ est l'ensemble des candidats (toutes les valeurs possibles de C présentes dans R). $S \times T_1$ fabrique toutes les combinaisons souhaitées ; on leur retranche celles qui existent réellement dans R. Ce qui reste, $T_2$ , est l'ensemble des candidats qui manquent au moins une valeur de S. Les retrancher de $T_1$ laisse exactement ceux qui couvrent tout S.

Cette structure explique le double NOT EXISTS de SQL : une différence de différences est une double négation.

#Animation : de l'algèbre à SQL

Jointure

⋈ sur clé ↔ JOIN ON o.user_id = u.id

Projection

π_name,amount ↔ SELECT name, amount

Sélection

σ_amount>100 ↔ WHERE amount > 100

Renommage

ρ(u=users, o=orders) ↔ alias SQL

Exemple complet sur le fil rouge du module (users, orders) : « noms des utilisateurs dont une commande dépasse 50 ».

texttext

1π_name( σ_amount>50( users ⋈ orders ) )

sqlsql

1select distinct u.name2from users u3join orders o on o.user_id = u.id4where o.amount > 50;

Sur le fil rouge du module, Alice a des commandes de 40 et 60, Bob de 15,5, 90 et 12 : chacun des deux possède une commande supérieure à 50, le résultat attendu est donc deux lignes, Alice et Bob. Le distinct matérialise l'élimination de doublons de la projection, qu'un utilisateur ait une ou dix commandes qualifiantes.

#Règles de réécriture et optimisation

Le moteur réécrit vos requêtes en s'appuyant sur des équivalences. Les connaître explique pourquoi deux requêtes d'apparence différente donnent le même plan :

Cascaded selections : σ_c1(σ_c2(R)) ≡ σ_{c1 ∧ c2}(R). Deux WHERE imbriqués valent un seul.
Commutativité de la sélection et de la projection : π_A(σ_c(R)) ≡ σ_c(π_A(R)) si A contient les attributs testés par c.
Pousser les sélections vers les feuilles : σ_c(R ⋈ S) ≡ σ_c(R) ⋈ S si c ne porte que sur R. Réduire R avant la jointure réduit le produit intermédiaire : c'est la règle qui justifie « filtrer tôt » des sections SELECT et Plans d'exécution.
Jointure plutôt que produit : R ⋈ S ≡ σ_θ(R × S) mais aucune base n'évalue jamais le produit complet quand une jointure est exprimable.

Ces règles sont la raison d'être des index : pousser σ vers les feuilles ne sert que si l'évaluation de σ elle-même est accélérée.

#Écrire la division en SQL : la double négation

Question : « clients ayant commandé tous les produits de la catégorie X ». La division s'écrit :

texttext

1π_clientId,produitId(Commandes) ÷ π_produitId(σ_categorie='X'(Produits))

SQL n'a pas d'opérateur ÷ ; l'écriture idiomatique est le double NOT EXISTS :

sqlsql

1-- c : clients, p : produits de la catégorie X, cp : commandes2select c.id, c.name3from clients c4where not exists (              -- il ne reste aucun produit de X...5  select 1 from produits_x p6  where not exists (            -- ...que ce client n'ait pas commandé7    select 1 from commandes cp8    where cp.client_id = c.id and cp.produit_id = p.id9  )10);

Lecture : le client convient s'il n'existe pas de produit de X qu'il n'a pas commandé. Double négation = quantificateur universel, exactement la sémantique de la division.

#Exercice : traduire dans les deux sens

Traduisez en algèbre : « montants totaux par utilisateur, uniquement pour les utilisateurs nommés Alice ou Bob » sur users(u.id, u.name) et orders(o.id, o.user_id, o.amount).
Traduisez en SQL : π_name( users − ( users ⋈ π_user_id(orders) ) ).

Correction

Agréger d'abord sur orders, restreindre aux bons utilisateurs, joindre, projeter :

texttext

1γ_user_id; sum(amount)->total( orders ) ⋈ σ_name∈{Alice,Bob}( users )

puis π_name,total. En SQL :

sqlsql

1select u.name, sum(o.amount) as total2from users u3join orders o on o.user_id = u.id4where u.name in ('Alice', 'Bob')5group by u.name;6-- Attendu sur le jeu fil rouge : 2 lignes, Alice 100.0, Bob 117.5

users ⋈ π_user_id(orders) sont les utilisateurs avec commandes ; la différence soustrait ces lignes : il reste les utilisateurs sans aucune commande, et la projection en donne les noms.

sqlsql

1select u.name2from users u3where not exists (select 1 from orders o where o.user_id = u.id);4-- Attendu sur le jeu fil rouge : 1 ligne, Charlie

#Exercice : questions en « tous les » (type examen)

Deux énoncés d'examen réels, qui tombent tous les deux sur la division.

Énoncé 1 — la compagnie maritime. Base : NAVIRE(numero, nom, type, capacite, date_fabrication), CAPITAINE(numero, nom, salaire), TRAVERSEE(numero, capitaine, navire, ville_depart, ville_arrive, heure_depart, heure_arrive). Les clés primaires sont soulignées en sujet (numero pour chaque table). Écrire en algèbre relationnelle : « les capitaines effectuant toutes les traversées au départ de NICE ».

Énoncé 2 — l'hôtel. Base : HOTEL(nom, nomPropriétaire, ville, catégorie, wifi, restaurant), CHAMBRE(identifiantChambre, numéro, surface, nombreCouchage, minibar, nomHôtel), EQUIPE_SERVICE(numéro, nbrPersonnes, corpsDeMétier, nomHôtel), INTERVENTION(numéro, identifiantChambre, numéroEquipeService, raisonIntervention, date, heureDébut, heureFin), RESERVATION(numéro, nomClient, dateDébut, dateFin, identifiantChambre). Écrire en algèbre : « la liste des équipes d'intervention qui sont intervenues au moins une fois dans toutes les chambres ».

Correction détaillée

Énoncé 1. Le mot « toutes » impose la division. Il faut d'abord ramener la question à deux relations dont l'une est incluse dans l'autre.

Étape 1, isoler les traversées au départ de NICE et le capitaine qui les effectue :

texttext

1R = π_capitaine, numero ( σ_ville_depart='NICE' ( TRAVERSEE ) )

Étape 2, la relation S des valeurs à couvrir : les numéros des traversées au départ de NICE.

texttext

1S = π_numero ( σ_ville_depart='NICE' ( TRAVERSEE ) )

Étape 3, la division :

texttext

1π_capitaine ( R ÷ S )

La division rend l'ensemble des capitaines qui couvrent toutes les traversées de S. La projection finale évite les doublons si un capitaine apparaît sur plusieurs lignes.

Variante posée dans le même sujet : « les capitaines effectuant toutes les traversées au départ de NICE et dont le nom est différent de 'De Maria' ». La division se compose avec une sélection ; l'ordre importe peu ici, mais la sélection doit porter sur CAPITAINE, pas sur TRAVERSEE :

texttext

1π_nom ( CAPITAINE ⋈ ( π_capitaine,numero ( σ_ville_depart='NICE' ( TRAVERSEE ) ) ÷ π_numero ( σ_ville_depart='NICE' ( TRAVERSEE ) ) ) )

puis sélection sur le nom. En pratique on écrit plutôt la sélection du nom en premier, pour réduire les volumes avant la division — c'est une réécriture légitime.

Énoncé 2. Même patron, avec deux jointures préalables car l'information est dispersée sur trois tables.

Étape 1, réduire les chambres à leur identifiant et les interventions à la paire (équipe, chambre) :

texttext

1S = π_identifiantChambre ( CHAMBRE )2I = π_numeroEquipeService, identifiantChambre ( INTERVENTION )

Étape 2, diviser :

texttext

1π_numeroEquipeService ( I ÷ S )

Le résultat est l'ensemble des équipes qui couvrent toutes les chambres. Notez que la division porte sur la relation des interventions, pas sur EQUIPE_SERVICE : c'est le piège du sujet. Une équipe qui n'est jamais intervenue n'apparaît nulle part dans INTERVENTION et ne peut donc pas être dans le résultat — ce qui est bien la réponse attendue (« intervenues au moins une fois dans toutes les chambres »).

La même chose en SQL (double négation, cf. la section Division) :

sqlsql

1-- Énoncé 22select e.numero3from EQUIPE_SERVICE e4where not exists (5  select 1 from CHAMBRE c6  where not exists (7    select 1 from INTERVENTION i8    where i.numeroEquipeService = e.numero9      and i.identifiantChambre = c.identifiantChambre10  )11);