Algèbre relationnelle

L'algèbre relationnelle est un langage de requêtes dans des bases de données relationnelles. L'algèbre relationnelle a été inventée en 1970 par Edgar Frank Codd, le directeur de recherche du centre IBM de San José.

Il s'agit de la théorie sous-jacente aux langages de requête des SGBD, comme SQL. Le théorème de Codd dit que l'algèbre relationnelle est équivalente au calcul relationnel (logique du premier ordre sans symbole de fonction). Elle est aussi équivalente à Datalog^¬ (Datalog avec la négation) non récursif^[1]. Datalog est un langage de requête et de règles pour les bases de données déductives.

Selon Abiteboul et al.^[2], l'algèbre relationnelle est conceptuellement un langage "procédural" : en effet, les requêtes sont des suites d'opérations qui construisent la réponse. Cela s'oppose aux langages conceptuellement "déclaratifs" comme le calcul relationnel et Datalog.

Modèle relationnel modifier

Article détaillé : Modèle relationnel.

Dans le modèle relationnel, les données sont stockées dans des tables, aussi appelées relations. Voici un exemple de relation :


Clé	Nom	Email
1	Alice	alice@wikipedia.fr
2	Bob	bob@wikipedia.fr
3	Carole	carole@wikimedia.fr

Plus précisément^[3], une relation (au sens du modèle de Codd) est constituée :

d'un schéma, c'est-à-dire l'ensemble des noms des champs (ici Clé, Nom, Email), et des types correspondants (dans l'exemple respectivement, un nombre entier, puis deux chaînes de caractères).
d'une extension, c'est-à-dire le contenu de la table, qui est un ensemble de n-uplets dont l'ordre n'a pas d'importance.

Définition modifier

Le langage procédural contient les opérations ensemblistes de la théorie des ensembles^[4] sur les relations ainsi que des opérations pour fusionner/projeter des relations.

Opérateurs ensemblistes modifier

Les opérateurs ensemblistes sont l'union, l'intersection, la différence et le produit cartésien.

Union modifier

L'union de deux relations sur le même schéma est la relation sur ce schéma contenant exactement l'union des enregistrements de ces deux relations. Formellement, $R\cup S=\{t:t\in R\ ou\ t\in S\}\,$ .

*Employés de Renault*
Nom	ID	Département
Harry	3415	Finance
Sally	2241	Vente
George	3401	Finance

*Employés de Citroën*
Nom	ID	Département
Bertrand	0808	Vente
Donald	0007	Vente

*Employés de Renault* U *Employés de Citroën*
Nom	ID	Département
Harry	3415	Finance
Sally	2241	Vente
George	3401	Finance
Bertrand	0808	Vente
Donald	0007	Vente

Intersection modifier

L'intersection de deux relations sur le même schéma est la relation sur ce schéma contenant exactement les enregistrements qui apparaissent dans les deux relations. Formellement, $R\cap S=\{t:t\in R\ et\ t\in S\}\,$ .

*Personnes inscrits en football*
Nom	ID
Harry	3415
Sally	2241
George	3401

*Personnes inscrits en cours de piano*
Nom	ID
Harry	3415
Bertrand	2
George	3401
Yoda	1000

*Personnes inscrits en football* ∩ *Personnes inscrits en cours de piano*
Nom	ID
Harry	3415
George	3401

Différence modifier

La différence de deux relations sur le même schéma est la relation sur ce schéma contenant exactement les enregistrements qui apparaissent dans la première relation mais pas dans la deuxième. Formellement, $R-S=\{t:t\in R\ et\ t\not \in S\}\,$ . Par exemple, on peut calculer les personnes inscrits en football mais qui ne sont pas inscrits en cours de piano :

*Personnes inscrits en football*
Nom	ID
Harry	3415
Sally	2241
George	3401

*Personnes inscrits en cours de piano*
Nom	ID
Harry	3415
Bertrand	2
George	3401
Yoda	1000

*Personnes inscrits en football* - *Personnes inscrits en cours de piano*
Nom	ID
Sally	2241

Produit cartésien modifier

Avec le produit cartésien de deux relations, on recopie chaque tuple de la première relation pour chacun des tuples de la deuxième. Formellement, $R\times S=\{(r,s):r\in R\ et\ s\in S\}$ .

*Personnes*
Nom	ID
Harry	3415
Sally	2241

*Cadeaux*
Type	Prix
livre	10
gâteau	20
ordinateur	300

*Personnes* - *Cadeaux*
Nom	ID	Type	Prix
Harry	3415	livre	10
Harry	3415	gâteau	20
Harry	3415	ordinateur	300
Sally	2241	livre	10
Sally	2241	gâteau	20
Sally	2241	ordinateur	300

Opérateurs relationnels modifier

Sélection modifier

La sélection (ou restriction) consiste à ne retenir que les enregistrements vérifiant une condition donnée. Dans l'exemple plus bas, on ne garde que les touristes dont la ville est Paris.

Données : Une relation $R\,$ et une formule $F\,$ formée d'une combinaison de comparaisons et de connecteurs logiques.
Résultat : $\sigma _{F}(R)=\{r\in R:r\,$ satisfait la condition donnée par $F\}\,$ , dans l'exemple $\sigma _{Ville='Paris'}(\,$ Touristes $)\,$
Équivalent SQL : WHERE

*Touristes*
idTouriste	NomT	Ville	Sport
1	Marc	Paris	Ski
2	Jean	Toulouse	Tennis
3	Franc	Marseille	Football
4	Thomas	Lyon	Voile
5	Max	Paris	Golf

*Sélection des touristes où Ville vaut Paris*
idTouriste	NomT	Ville	Sport
1	Marc	Paris	Ski
5	Max	Paris	Golf

Projection modifier

La projection permet de ne garder que certains attributs. Dans l'exemple ci-dessous, on ne garde que les attributs NomT et Ville de la relation Touristes.

Données : Une relation $R\,$ et un ensemble d'attributs $A\,$ de $R\,$
Résultat : $\pi _{A}(R)\,$ , qui est la Relation $R\,$ où on ne considère que les attributs de $A\,$ , par exemple $\pi _{NomT,Ville}(\,$ Touristes $)\,$
Équivalent SQL : SELECT

*Touristes*
idTouriste	NomT	Ville	Sport
1	Marc	Paris	Ski
2	Jean	Toulouse	Tennis
3	Franc	Marseille	Football
4	Thomas	Lyon	Voile
5	Max	Paris	Golf

*Projection de la relation Touristes sur les attributs NomT et Ville*
NomT	Ville
Marc	Paris
Jean	Toulouse
Franc	Marseille
Thomas	Lyon
Max	Paris

Renommage modifier

Renommage :

Données : Une relation $R\,$ et un attribut $b\,$ de $R\,$
Résultat : $\rho _{a/b}(R)\,$ , qui est la Relation $R\,$ avec $b\,$ renommé $a\,$
Équivalent SQL : AS

Jointure modifier

Jointure :

Données : deux relations $R\,$ et $S$
Résultat : $R\bowtie S=\{(a,b,c):(a,b)\in R\ et\ (b,c)\in S\}\,$
Équivalent SQL : JOIN

*Touristes*
idTouriste	NomT	Ville	Sport
1	Marc	Paris	Ski
2	Jean	Toulouse	Tennis
3	Franc	Marseille	Football
4	Thomas	Lyon	Voile
5	Max	Paris	Golf

*Destinations*
idTouriste	VilleD
1	Cannes
2	Ibiza
4	Tokyo

*Touristes ⋈ Destinations*
idTouriste	NomT	Ville	Sport	VilleD
1	Marc	Paris	Ski	Cannes
2	Jean	Toulouse	Tennis	Ibiza
4	Thomas	Lyon	Voile	Tokyo

Division modifier

La division prend en entrée deux relations $R(x_{1},...,x_{m},y_{1},...,y_{p})\,$ et $S(y_{1},...,y_{p})\,$ . Ainsi, tout n-uplet $r\in R\,$ se décompose en deux n-uplets $r=(t,s)\,$ , avec $t=(t_{1},...,t_{m})\,$ de schéma $X=\{x_{1},...,x_{m}\}\,$ et $s=(s_{1},...,s_{p})\,$ de schéma $y=\{y_{1},...,y_{p}\}\,$ . et retourne la table de schéma $X\,$ tel que $R/S=\{t:\forall s\in S,\ (t,s)\in R\}\,$ . La division revient à donner “tous les x tels que pour tout y...”

Expressivité modifier

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

L'algèbre SPC (sélection, projection et produit cartésien) correspond au calcul conjonctif (calcul relationnel sans disjonction et sans négation) : c'est une des versions du théorème de Codd. L'algèbre SPCU- (l'algèbre SPC avec en plus l'union et la différence) correspond au calcul relationnel en entier : c'est une autre version du théorème de Codd. L'équijointure^[Quoi ?] peut être exprimée avec un produit cartésien, suivi d'une sélection, puis une projection.

Optimisation modifier

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Voici des règles de réécriture pour transformer une expression de l'algèbre relationnelle en une autre expression équivalente.

Implémentation modifier

Cependant, les bases de données relationnelles ne fonctionnent pas tout à fait selon les règles ensemblistes de l'algèbre relationnelle. En effet, si l'on ne définit pas de clé primaire, il est possible d'insérer plusieurs lignes identiques dans une table, ce qui d'un point de vue ensembliste n'a pas de sens : un élément fait partie ou ne fait pas partie d'un ensemble. Si l'on veut appliquer strictement les règles des ensembles, il faut vérifier à chaque ajout dans une table que les lignes introduites ne sont pas déjà présentes.

Objets précis du modèle modifier

Il s'agit ici de déterminer des Domaines (i.e., type atomique) :

Numérique : entier ou réel (SQL : Int, Float, etc.) ;
Chaîne de caractères (SQL : Char(20), VarChar(32), etc.) ;
Date (SQL : DATE, TIME, YEAR, etc.) ;
Type énuméré.

Notes et références modifier

↑ (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., 1995, 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 10
↑ (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., 1995, 685 p. (ISBN 978-0-201-53771-0, lire en ligne), Part B - Basics: Relational QueryLanguages - p. 35
↑ « Apprendre les bases de données et SQL », sur Developpez.com (consulté le 19 mai 2019)
↑ (ro) « Aide mémoire sur les bases de données et SQL2 », sur scritube.com (consulté le 19 avril 2023).

Voir aussi modifier

Sur les autres projets Wikimedia :

algèbre relationnelle, sur le Wiktionnaire
Algèbre relationnelle, sur Wikiversity

Liens externes modifier

RAT, Software Rational Algebra Translator to SQL
(fr) Laurent Audibert, « Bases de données relationnelles », sur developpez.com

[1] (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., 1995, 685 p. (ISBN 978-0-201-53771-0, lire en ligne), p. 10

[2] (en) Foundations of Databases : The Logical Level, Addison-Wesley Longman Publishing Co., Inc., 1995, 685 p. (ISBN 978-0-201-53771-0, lire en ligne), Part B - Basics: Relational QueryLanguages - p. 35

[3] « Apprendre les bases de données et SQL », sur Developpez.com (consulté le 19 mai 2019)

[4] (ro) « Aide mémoire sur les bases de données et SQL2 », sur scritube.com (consulté le 19 avril 2023).

[1]

[2]

[3]

[4]