En informatique, plus précisément en théorie des 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é.
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, c'est-à-dire la logique du premier ordre, mais sans les symboles 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 .
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 : +Clé[email protected]@[email protected] 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). Chacun des n-uplets s'appelle un enregistrement.
Définition Le langage procédural de l'algèbre relationnel 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, l'union des relations et est .
+ 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 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 et est .
+ 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 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 et est . 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 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 et est .
+ 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
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
+ 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
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
+ 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
Le renommage consiste à renommer un attribut d'une table. Données : Une relation et un attribut de Résultat : , qui est la Relation avec renommé Équivalent SQL : AS
Jointure
La 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 ). Données : deux relations et Résultat : É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
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...”
Théorèmes de Codd
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 ). 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 ).
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
Catégorie:Théorie des ensembles Catégorie:Base de données Catégorie:Modélisation des données