Voir la source de Algèbre relationnelle

{{Voir homonymes|Algèbre (homonymie)}}
En [[informatique]], plus précisément en théorie des [[Base de données relationnelle|bases de données relationnelles]], l''''algèbre relationnelle''' est un langage de requêtes, inventé en [[1970]] par [[Edgar Frank Codd]], directeur de recherche du centre [[IBM]] de [[San José (Californie)|San José]].

Il s'agit de la théorie sous-jacente aux [[Langage de requête|langages de requête]] des [[Système de gestion de base de données|SGBD]], comme [[Structured Query Language|SQL]]. Le [[théorème de Codd]] dit que l'algèbre relationnelle est équivalente au calcul relationnel, c'est-à-dire la [[Calcul des prédicats|logique du premier ordre]], mais sans les symboles de [[Fonction (mathématiques)|fonction]].

Elle est aussi équivalente à Datalog<sup>¬</sup> ([[Datalog]] avec la négation) non [[Récursivité|récursif]]<ref>{{Ouvrage|langue=en|titre=Foundations of Databases|sous-titre=The Logical Level|éditeur=Addison-Wesley Longman Publishing Co., Inc.|année=1995|pages totales=685|isbn=978-0-201-53771-0|lire en ligne=https://dl.acm.org/citation.cfm?id=551350|consulté le=2019-05-19|passage=p. 10}}</ref>. '''Datalog''' est un langage de requête et de règles pour les {{Lien|langue=en|fr=bases de données déductives|trad=Deductive_database}}.

Selon [[Serge Abiteboul|Abiteboul]] et al.<ref>{{Ouvrage|langue=en|titre=Foundations of Databases|sous-titre=The Logical Level|éditeur=Addison-Wesley Longman Publishing Co., Inc.|année=1995|pages totales=685|isbn=978-0-201-53771-0|lire en ligne=https://dl.acm.org/citation.cfm?id=551350|consulté le=2019-05-19|passage=Part B - Basics: Relational QueryLanguages - p. 35}}</ref>, l'algèbre relationnelle est conceptuellement un [[Programmation procédurale|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 "[[Programmation déclarative|déclaratifs]]" comme le calcul relationnel et Datalog.

== Modèle relationnel ==
{{Article détaillé|Modèle relationnel}}
Dans le [[modèle relationnel]], les données sont stockées dans des [[Table (base de données)|tables]], aussi appelées relations. Voici un exemple de relation :
{| class="wikitable"
|+
!Clé
!Nom
!Email
|-
|1
|Alice
|alice@wikipedia.fr
|-
|2
|Bob
|bob@wikipedia.fr
|-
|3
|Carole
|carole@wikimedia.fr
|}
Plus précisément<ref>{{Lien web|langue=fr|titre=Apprendre les bases de données et SQL|url=http://sgbd.developpez.com/tutoriels/cours-complet-bdd-sql/|site=Developpez.com|consulté le=2019-05-19}}</ref>, une relation (au sens du modèle de [[Edgar Frank Codd|Codd]]) est constituée :

# d'un [[Schéma conceptuel|schéma]], c'est-à-dire l'ensemble des noms des champs (ici Clé, Nom, Email), et des [[Type (informatique)|types]] correspondants (dans l'exemple respectivement, un [[Entier naturel|nombre entier]], puis deux [[Chaîne de caractères|chaînes de caractères]]).
# d'une extension, c'est-à-dire le contenu de la table, qui est un ensemble de [[Uplet|n-uplets]] (dont l'ordre n'a pas d'importance). Chacun des n-uplets s'appelle un enregistrement.

== Définition ==
Le [[Programmation procédurale|langage procédural]] de l'algèbre relationnel contient les opérations ensemblistes de la [[théorie des ensembles]]<ref>{{lien web |langue=ro |titre=Aide mémoire sur les bases de données et SQL2<!-- Vérifiez ce titre --> |url=http://www.scritube.com/limba/franceza/Aide-mmoire-sur-les-bases-de-d21481108.php |site=scritube.com |consulté le=19-04-2023}}.</ref> sur les relations ainsi que des opérations pour fusionner/projeter des relations.

=== Opérateurs ensemblistes ===
Les opérateurs ensemblistes sont l'[[Union (mathématiques)|union]], l'[[Intersection (mathématiques)|intersection]], la [[Algèbre des parties d'un ensemble#Différence|différence]] et le [[produit cartésien]].

==== Union ====
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, l'union des relations <math>R</math> et <math>S</math> est  <math>R \cup S=\{t: t \in R \ ou \ t \in S\}\,</math>.{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''Employés de Renault''
 |-
 ! Nom   !! ID !! Département
 |-
 | Harry  || 3415  || Finance
 |-
 | Sally  || 2241  || Vente
 |-
 | George || 3401  || Finance
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Employés de Citroën''
 |-
 ! Nom   !! ID !! Département
 |-
 | Bertrand  || 0808  || Vente
 |-
 | Donald  || 0007  || Vente
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+  ''Employés de Renault''&nbsp;U &nbsp;''Employés de Citroën''
 |-
 ! Nom   !! ID !! Département
 |-
 | Harry  || 3415  || Finance
 |-
 | Sally  || 2241  || Vente
 |-
 | George || 3401  || Finance
 |-
 | Bertrand  || 0808  || Vente
 |-
 | Donald  || 0007  || Vente
|}
{{col-end}}

==== Intersection ====
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, l'intersection des relations <math>R</math> et <math>S</math> est  <math>R \cap S=\{t: t \in R \ et \ t \in S\}\,</math>.
{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''Personnes inscrits en football''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | Sally  || 2241  
 |-
 | George || 3401  
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Personnes inscrits en cours de piano''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | Bertrand  || 2  
 |-
 | George || 3401  
 |-
 | Yoda || 1000
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+  ''Personnes inscrits en football''&nbsp;∩ &nbsp;''Personnes inscrits en cours de piano''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | George || 3401 
|}
{{col-end}}

==== Différence ====
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, la différence des relations <math>R</math> et <math>S</math> est <math>R-S=\{t: t \in R \ et \ t \not\in S\}\,</math>. Par exemple, on peut calculer les personnes inscrits en football mais qui ne sont pas inscrits en cours de piano :{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''Personnes inscrits en football''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | Sally  || 2241  
 |-
 | George || 3401  
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Personnes inscrits en cours de piano''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | Bertrand  || 2  
 |-
 | George || 3401  
 |-
 | Yoda || 1000
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+  ''Personnes inscrits en football''&nbsp;- &nbsp;''Personnes inscrits en cours de piano''
 |-
 ! Nom   !! ID 
 |-
 | Sally  || 2241 
|}
{{col-end}}

==== Produit cartésien ====
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, le produit cartésien des relations <math>R</math> et <math>S</math> est <math>R \times S=\{(r,s) : r \in R \ et \ s \in S \}</math>.<br />

{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''Personnes''
 |-
 ! Nom   !! ID 
 |-
 | Harry  || 3415  
 |-
 | Sally  || 2241  
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Cadeaux''
 |-
 ! Type   !! Prix 
 |-
 | livre  || 10  
 |-
 | gâteau  || 20  
 |-
 | ordinateur || 300  
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+  ''Personnes''&nbsp;- &nbsp;''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  
 |-
|}
{{col-end}}

=== Opérateurs relationnels ===

==== Sélection ====
La ''[[Sélection (informatique)|sélection]]'' (ou restriction{{Référence nécessaire|date=octobre 2024}}) 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 <math>R\,</math> et une formule <math>F\,</math> formée d'une combinaison de comparaisons et de connecteurs logiques.
* Résultat : <math>\sigma_{F}( R ) = \{ r \in R : r\,</math> satisfait la condition donnée par <math>F \}\,</math>, dans l'exemple <math>\sigma_{Ville = 'Paris'}(\,</math>Touristes<math>)\,</math>
* Équivalent SQL : '''WHERE'''
{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''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
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Sélection des touristes où Ville vaut Paris''
 |-
 ! idTouriste   !! NomT !! Ville !! Sport
 |-
 | 1  || Marc  || Paris || Ski
 |-
 | 5  || Max  || Paris || Golf
|}
{{col-end}}

==== Projection ====

''La [[Projection (algèbre relationnelle)|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 <math>R\,</math> et un ensemble d'attributs <math>A\,</math> de <math>R\,</math>
* Résultat : <math>\pi_{A}( R )\,</math>, qui est la Relation <math>R\,</math> où on ne considère que les attributs de <math>A\,</math>, par exemple  <math>\pi_{NomT, Ville}(\,</math>Touristes<math>)\,</math>
* Équivalent SQL : '''SELECT'''
{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''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
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Projection de la relation Touristes sur les attributs NomT et Ville''
 |-
 ! NomT !! Ville
 |-
 | Marc  || Paris
 |-
 | Jean  || Toulouse
 |-
 | Franc  || Marseille
 |-
 | Thomas  || Lyon
 |-
 | Max  || Paris
|}
{{col-end}}

==== Renommage ====

''Le renommage'' consiste à renommer un attribut d'une table.
* Données : Une relation <math>R\,</math> et un attribut <math>b\,</math> de <math>R\,</math>
* Résultat : <math>\rho_{a/b}(R)\,</math>, qui est la Relation <math>R\,</math> avec <math>b\,</math> renommé <math>a\,</math>
* Équivalent SQL : '''AS'''

==== Jointure ====

''La [[Jointure (informatique)|jointure]]'' de deux relations consiste à regrouper les deux tables, comme un produit cartésien, mais en identifiant les attributs communs. La jointure peut s'exprimer à l'aide d'un produit cartésien, d'une sélection et d'une projection (cf. Définition 14.35 dans <ref name=":0">{{Ouvrage|auteur1=Pierre Le Barbenchon, Sophie Pinchinat, François Schwarzentruber|titre=Logique : fondements et applications|éditeur=Dunod|année=2021|pages totales=286|isbn=978-2-10-082158-7}}</ref>).
* Données : deux relations <math>R\,</math> et <math>S</math>
* Résultat : <math>R \bowtie S=\{(a,b,c):(a,b)\in R  \ et \ (b,c) \in S  \}\,</math>
* Équivalent SQL : '''JOIN'''
{{col-begin|width=auto; margin:0.5em auto}}
{{col-break}}
{| class="wikitable"
 |+           ''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
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Destinations''
 |-
 ! idTouriste !! VilleD
 |-
 | 1  || Cannes
 |-
 | 2  || Ibiza
 |-
 | 4  || Tokyo
|}
{{col-break|gap=2em}}
{| class="wikitable"
 |+           ''Touristes ⋈ Destinations''
 |-
 ! idTouriste   !! NomT !! Ville !! Sport !! VilleD
 |-
 | 1  || Marc  || Paris || Ski || Cannes
 |-
 | 2  || Jean  || Toulouse || Tennis || Ibiza
 |-
 | 4  || Thomas  || Lyon || Voile || Tokyo
|}
{{col-end}}

==== Division ====

La ''[[division]]'' prend en entrée deux relations <math>R(x_1, ..., x_m, y_1, ..., y_p)\,</math> et <math>S(y_1,...,y_p)\,</math>.
Ainsi, tout n-uplet <math>r \in R \,</math> se décompose en deux n-uplets <math>r=(t,s)\,</math>, avec <math>t=(t_1, ..., t_m)\,</math> de schéma <math>X=\{x_1, ..., x_m\}\,</math> et <math>s=(s_1, ..., s_p)\,</math> de schéma <math>y=\{y_1, ..., y_p\}\,</math>. et retourne la table de schéma <math>X\,</math> tel que <math>R/S=\{t: \forall s \in S, \ (t,s) \in R\}\,</math>. La division revient à donner “tous les x tels que pour tout y...”

== Théorèmes de Codd ==
{{Section vide ou incomplète}}
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]] (section 14.4.1 dans <ref name=":0" />). 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]] (section 14.4.2 dans <ref name=":0" />).

== Optimisation ==
{{Section vide ou incomplète}}
Voici des règles de réécriture pour transformer une expression de l'algèbre relationnelle en une autre expression équivalente.

== Implémentation ==
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 (base de données)|table]], ce qui d'un point de vue [[Ensemble|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 (base de données)|table]] que les lignes introduites ne sont pas déjà présentes.

=== Objets précis du modèle ===
Il s'agit ici de déterminer des Domaines (i.e., type atomique) :
* Numérique : entier ou réel ([[Structured Query Language|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 ==
{{Références}}

== Voir aussi ==
{{Autres projets
|wiktionary=algèbre relationnelle
|wikiversity=Algèbre relationnelle}}
* [[Système de gestion de base de données]]
* [[Algèbre]]
* [[Théorie des ensembles]] 
* [[Base de données]]
* [[Base de données relationnelle]]

=== Liens externes ===
* [http://www.slinfo.una.ac.cr/rat/rat.html RAT, Software Rational Algebra Translator to SQL]
* {{fr}} {{Lien web|url=http://laurent-audibert.developpez.com/Cours-BD/|auteur=Laurent Audibert|site=developpez.com|titre=Bases de données relationnelles}}

{{Portail|Bases de données|mathématiques}}

[[Catégorie:Théorie des ensembles]]
[[Catégorie:Base de données]]
[[Catégorie:Modélisation des données]]