Ouvrir le menu principal
Page d'aide sur l'homonymie Pour les articles homonymes, voir Algèbre (homonymie).

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

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 langage conceptuellement "déclaratif" comme le calcul relationnel et Datalog.

Modèle relationnelModifier

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 Edgar edgar@wikipedia.fr
2 Frank frank@wikipedia.fr
3 Bob bob@wikimedia.fr

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

  1. 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, respectivement, un nombre entier, puis deux chaînes de caractères).
  2. 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éfinitionModifier

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 ensemblistesModifier

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

UnionModifier

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

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

IntersectionModifier

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

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érenceModifier

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 :

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ésienModifier

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

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 relationnelsModifier

SélectionModifier

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

ProjectionModifier

  • 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

RebaptiserModifier

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

JointureModifier

  • Jointure :
    • 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

DivisionModifier

  • Division : elle 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éModifier

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.

OptimisationModifier

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

ImplémentationModifier

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èleModifier

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érencesModifier

  1. Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., (ISBN 9780201537710, lire en ligne), p. 10
  2. (en) Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., (ISBN 9780201537710, lire en ligne), Part B - Basics: Relational Query Languages - p. 35
  3. « Apprendre les bases de données et SQL », sur Developpez.com (consulté le 19 mai 2019)
  4. http://www.scritube.com/limba/franceza/Aide-mmoire-sur-les-bases-de-d21481108.php

Voir aussiModifier

Sur les autres projets Wikimedia :

Liens externesModifier