Dans la précédente section nous avons défini la notion mathématique de modèle relationnel. Maintenant nous savons comment les données peuvent être stockées en utilisant un modèle de données relationnel mais ne savons que faire pour retrouver quelque chose dans la base. Par exemple quelqu'un peut demander les noms de tous les fournisseurs qui vendent la pièce 'vis' (Screw). Deux sortes de notations pour exprimer les opérations sur les relations ont pour cela été définies :
L'Algèbre Relationnelle qui est une notation algébrique, où les requêtes sont exprimées en appliquant des opérateurs spécialisés pour les relations.
Le Calcul Relationnel qui est une notation logique, où les requêtes sont exprimées par la formulation de restrictions logiques que les tuples doivent satisfaire dans la réponse.
E.F. Codd mit au point l'algèbre relationnelle en 1972. Il consiste en un ensemble d'opérations sur les relations :
SELECT (σ) extrait des tuples d'une relation qui satisfait une restriction donnée. Soit R une table qui contient un attribut A. σA=a(R) = {t ∈ R ∣ t(A) = a} où t dénote un tuple de R et t(A) dénote la valeur de l'attribut A du tuple t.
PROJECT (π) : extrait des attributs (colonnes) d'une relation. Soit une relation R qui contient un attribut X. πX(R) = {t(X) ∣ t ∈ R}, où t(X) dénote la valeur de l'attribut X du tuple t.
PRODUCT (×) : construit le produit cartésien de deux relations. Soit R une table d'arité (nombre d'attributs) k1, soit S une table d'arité k2. R × S est l'ensemble de tous les k1 + k2-tuples dont le premier k1 composant d'un tuple dans R et dont le dernier k2 composant d'un tuple dans S.
UNION (∪): construit l'union (dans le sens que la théorie des ensembles donne à ce terme) de deux tables. Avec deux tables R et S (de la même arité), l'union R ∪ S est l'ensemble des tuples qui sont dans R, ou dans S, ou dans les deux tables.
INTERSECT (∩): construit l'intersection (dans le sens que la théorie des ensembles donne à ce terme) de deux tables. Avec deux tables R et S, l'intersection R ∪ S est l'ensemble des tuples qui sont dans R et dans S. Nous devons avoir R et S de même arité.
DIFFERENCE (− or ∖): construit un ensemble de deux tables différentes. Soit R et S qui sont de nouveau deux tables de même arité. La différence R - S est l'ensemble des tuples présents dans R mais pas dans S.
JOIN (∏): connecte deux tables avec leurs attributs communs Soit R une table avec les attributs A,B et C et soit S une table avec les attributs C,D et E. C est un attribut commun.. R ∏ S = πR.A,R.B,R.C,S.D,S.E(σR.C=S.C(R × S)).
Que faisons nous ici ? Nous calculons tout d'abord le produit cartésien R × S. Ensuite nous sélectionnons les tuples dont les valeurs pour l'attribut C sont égales (σR.C = S.C). Nous obtenons une table qui contient l'attribut C deux fois et corrigeons ceci en écartant la colonne dupliquée.
Exemple 2-2. Une jointure interne
Examinons le cas d'une jointure. Voici les contenus de deux tables R et S :
R A | B | C S C | D | E
---+---+--- ---+---+---
1 | 2 | 3 3 | a | b
4 | 5 | 6 6 | c | d
7 | 8 | 9
|
Calculons tout d'abord le produit cartésien R × S. Nous obtenons :
R x S A | B | R.C | S.C | D | E
---+---+-----+-----+---+---
1 | 2 | 3 | 3 | a | b
1 | 2 | 3 | 6 | c | d
4 | 5 | 6 | 3 | a | b
4 | 5 | 6 | 6 | c | d
7 | 8 | 9 | 3 | a | b
7 | 8 | 9 | 6 | c | d
|
Après la sélection σR.C=S.C(R × S) nous obtenons :
A | B | R.C | S.C | D | E
---+---+-----+-----+---+---
1 | 2 | 3 | 3 | a | b
4 | 5 | 6 | 6 | c | d
|
Pour supprimer les colonnes en double S.C nous les trions par l'opération suivante : πR.A,R.B,R.C,S.D,S.E(σR.C=S.C(R × S)) et obtenons :
A | B | C | D | E
---+---+---+---+---
1 | 2 | 3 | a | b
4 | 5 | 6 | c | d
|
DIVIDE (÷): Soit R une table avec les attributs A, B, C, et D et soit S une table avec les attributs C et D. Nous définissons la division comme : R ÷ S = {t ∣ ∀ ts ∈ S ∃ tr ∈ R tel que tr(A,B)=t∧tr(C,D)=ts} où tr(x,y) dénote un tuple un de table R qui consiste en les composants x et y. Notez que le tuple t contient seulement les composants A et B de la relation R.
R A | B | C | D S C | D
---+---+---+--- ---+---
a | b | c | d c | d
a | b | e | f e | f
b | c | e | f
e | d | c | d
e | d | e | f
a | b | d | e
|
A | B
---+---
a | b
e | d
|
Pour une description plus détaillée et une définition de l'algèbre relationnelle voir : Principles of Database and Knowledge (Jeffrey D. Ullman, Computer Science Press , 1988) ou An Introduction to Database Systems (C. J. Date, 1994, Addison-Wesley.)
Exemple 2-3. Une requête utilisant l'algèbre relationnelle
Rappelons que nous avons formulé tous ces opérateurs relationnels pour pouvoir retrouver des données dans la base. Tâchons de déterminer les noms des fournisseurs qui vendent la pièce Screw. La réponse peut être obtenue en utilisant l'algèbre relationnelle :
πSUPPLIER.SNAME(σPART.PNAME='Screw'(SUPPLIER ∏ SELLS ∏ PART))
|
Nous appelons cette opération une requête. Si nous l'évaluons (appliquons) à nos tables d'exemples, nous obtiendrons le résultat suivant :
SNAME
-------
Smith
Adams
|
Le calcul relationnel est basé sur la logique de premier ordre. Il existe deux variantes du calcul relationnel :
Le calcul relationnel de domaine (DRC), où les variables tiennent lieu d'attributs de tuples.
Le calcul relationnel de tuple (TRC), où les variables tiennent lieu de tuples.
Nous parlerons du calcul relationnel de tuple seulement parce qu'il est l'un des fondements de la plupart des langages relationnels. Pour plus de détails voir : An Introduction to Database Systems (C. J. Date, 1994, Addison-Wesley) et Principles of Database and Knowledge (Jeffrey D. Ullman, Computer Science Press , 1988).
Les requêtes utilisées en TRC (Tuple Relational Calculus) ont la forme suivante : x(A) ∣ F(x) où x est un tuple variable, A est un ensemble d'attributs et F une formule. La relation résultante consiste en tous les tuples t(A) qui satisfont F(t).
Si nous voulons répondre à la question de l'exemple utilisant TRC nous formulerons la requête suivante :
{x(SNAME) ∣ x ∈ SUPPLIER ∧ \nonumber
∃ y ∈ SELLS ∃ z ∈ PART (y(SNO)=x(SNO) ∧ \nonumber
z(PNO)=y(PNO) ∧ \nonumber
z(PNAME)='Screw')} \nonumber
|
L'algèbre relationnelle et le calcul relationnel ont la même puissance d'expression; donc toutes les requêtes qui peuvent être formulées en utilisant l'un peuvent aussi l'être grâce à l'autre. Ce fut vérifié en premier par E.F. Codd en 1972. La preuve est fondée sur un algorithme (appelé "algorithme de réduction de Codd") par lequel une expression arbitraire du calcul relationnel peut être réduite à une expression au sens équivalent de l'algèbre relationnelle.
Certains déclarèrent que les langages basés sur le calcul relationnel sont de "haut niveau" ou "plus déclaratifs" que les langages basés sur l'algèbre relationnelle parce que ce dernier spécifie (partiellement) l'ordre des opérations tandis que le calcul laisse le compileur ou l'interpréteur déterminer l'ordre d'évaluation le plus efficace.