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. Datalog est un langage de requête et de règles pour les bases de données déductives.

Selon Abiteboul et al., 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 

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

Plus précisément, 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 
Le langage procédural contient les opérations ensemblistes de la théorie des ensembles sur les relations ainsi que des opérations pour fusionner/projeter des relations.

Opérateurs ensemblistes 
Les opérateurs ensemblistes sont l'union, l'intersection, la 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, .

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, .

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, . Par exemple, on peut calculer les personnes inscrits en football mais qui ne sont pas inscrits en cours de piano :

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, .

Opérateurs relationnels

Sélection 
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  et une formule  formée d'une combinaison de comparaisons et de connecteurs logiques.
 Résultat :  satisfait la condition donnée par , dans l'exemple Touristes
 Équivalent SQL : WHERE

Projection 

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  et un ensemble d'attributs  de 
 Résultat : , qui est la Relation  où on ne considère que les attributs de , par exemple  Touristes
 Équivalent SQL : SELECT

Renommage 

Renommage :
 Données : Une relation  et un attribut  de 
 Résultat : , qui est la Relation  avec  renommé 
 Équivalent SQL : AS

Jointure 

Jointure : 
 Données : deux relations  et 
 Résultat : 
 Équivalent SQL : JOIN

Division 

La division prend en entrée deux relations  et .
Ainsi, tout n-uplet  se décompose en deux n-uplets , avec  de schéma  et  de schéma . et retourne la table de schéma  tel que . La division revient à donner “tous les x tels que pour tout y...”

Expressivité 
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 peut être exprimée avec un produit cartésien, suivi d'une sélection, puis une projection.

Optimisation 

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, 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 
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

Voir aussi 

 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 
 RAT, Software Rational Algebra Translator to SQL
  

Théorie des ensembles
Base de données
Modélisation des données