Algèbre relationnelle
Définition
•
•
Algèbre relationnelle
• L’algèbre relationnelle est une collection d’opérations formelles qui
agissent sur des relations et produisent les relations en résultats
• C’est la force du modèle relationnel
• Il y a deux types d’opérations de base :
– Les opérations ensemblistes traditionnelles ( une relation doit être
traité comme un ensemble). Ces opérations sont des opérations
binaires (à partir de deux relations elles en construisent une
troisième) (l’union, l'intersection, la différence et le produit
cartésien)
– Les opérations spécifiques sont les opérations unaires de
projection et restriction qui, à partir d’une relation , en construisent
une autre, et l’opération binaire de jointure
Les opérations ensemblistes
1. Union : opération portant sur deux relations de même schéma R et S consistant à
construire une relation de même schéma T ayant pour tuples ceux appartenant à R ou S
ou aux deux relations.
Notations :
– R S
– UNION (R, S)
Précondition:
Schéma(R) = Schéma(S) = Schéma (T)
Différence
2. Différence : opération portant sur deux relations de même schéma R et S consistant à
construire une relation de même schéma T ayant pour tuples ceux appartenant à R et
n’appartenant pas à S.
Notations :
– R-S
– DIFFERENCE (R, S)
– MINUS (R, S)
Précondition:
Schéma (R)=Schéma(S)= Schéma( T)
Produit cartésien
3. Produit cartésien : opération portant sur deux relations R et S, consistant à construire
une relation T ayant pour schéma la concaténation des schémas des relations opérandes
(R et S) et pour tuples les combinaisons des tuples des relations opérandes.
Notations :
– R S
– PRODUCT (R, S)
Précondition: pas de précondition
Schéma(T)=Schéma(R) union Schéma(S)
Intersection
4. Intersection : opération portant sur deux relations de même schéma R et S consistant à
construire une relation de même schéma T ayant pour tuples ceux appartenant à la fois à
R et S
Notations :
– R S
– INTERSECT(R, S)
– AND (R, S)
• PRECONDITION:
– R et S doivent être de même schéma
• L’opération d’intersection s’obtient
à partir de l’opération de différence :
– R S = R – (R-S)
– R S=S-(S-R)
Les opérations spécifiques
1. Projection: opération sur une relation R (unaire), consistant à composer une relation S en
enlevant à la relation initiale tous les attributs non mentionnés en opérandes (aussi bien
au niveau du schéma que des tuples) et en éliminant les tuples en double qui sont
conservés une seule fois.
Notations : Attributi, Attributj…Attributm : sont les attributs de projection
–
A1, A2…Am
Réstriction ou sélection
2.2. Restriction ou sélection : opération sur une relation R (unaires) produisant une relation
S de même schéma, mais comportant les seuls tuples qui vérifient la condition précisée
en argument.
• Les conditions possibles sont des formules dans le calcul propositionnel constituées de
termes connectés par : Chaque terme est du type :
– <Attribut> <Opérateur> <Attribut> ou <Constante>, Tel que <Opérateur> {=, >,
, <, , },
Notations :
– condition(R)
Ai Valeur {=, >, , <, , }
Jointure
3. Jointure : Opération consistant à rapprocher selon une condition les
tuples de deux relations R et S afin de former une troisième relation T
qui contient tous les tuples obtenus en concaténant un tuple de R et un
tuple de S vérifiant la condition de rapprochement
• Syntaxe : R JOIN S ou R*S ou R S
• La condition de jointure est du type :
– <Attribut1> <opérateur Comparaison> <Attribut2>,
– tel que Attribut1 R et Attribut2 S
• Si <Opérateur> est ‘=‘ alors on parle de l’équi-jointure qui est une
véritable composition de relation au sens mathématique
• Si <Operateur> {>, , <, , }alors on parle de l’inéqui-jointure
Jointure naturelle : Opération consistant à rapprocher selon une condition les
tuples de deux relations R et S afin de former une troisième relation T dont les
attributs sont l’union des attributs de R et S, et dont les tuples sont obtenus en
composant un tuple de R et un tuple de S ayant mêmes valeurs pour les
attributs de même nom.
Notations :
– R S
– JOIN(R, S, Condition)
• PRECONDITION: Au moins un attributs de même nom en commun entre
les deux relations
• Schéma (R JOIN S)=(Schéma(R) Schéma(S)) – (Schéma(R) schéma(S))
Jointure Naturelle exemple
{=, >, , <, , }
Division
Division : Opération consistant à construire le quotient de la relation
R (A1, A2…Ap, Ap+1…An) par la relation S (Ap+1…An) comme la relation Q (A1, A2…Ap)
dont les tuples sont ceux concaténés à tout tuple de S donnent un tuple de R
Notations :
– R S
– DIVISION (R, S)
• L’opération de division s’obtient à partir de l’opération de différence, du produit
cartésien et de la projection:
– R S =R1-R2
– R1= A1, A2…Ap(R)
– R2= A1, A2…Ap((R1 S)-R)
Algèbre relationnelle
L’opération de division s’obtient à partir de l’opération de
différence, du produit cartésien et de la projection:
R1= A1, A2…Ap(R)
R2= A1, A2…Ap((R1 S)-R)
R S =R1-R2
Complément
Complément : Ensemble des tuples du produit cartésien des domaines des attributs d’une
relation R n’appartenant pas à cette relation. Le complément suppose a priori que les
domaines sont finis (sinon on obtient des relations infinies).
Notations :
– R
– -R
• Opération peu utilisée, car elle permet de générer des tuples qui ne sont pas dans la base,
en général très nombreux.
• Si l’on note par Di le produit cartésien des domaines, le complément dune relation R
est obtenu à partir de la différence comme suit :
R= Di -R
Algèbre relationnelle
3.3. Complément
Exemple :
Domaines:
• A={a1, a2, a3}
• B= {b1, b2, b3}
l’opérateur de renommage
opération permettant de renommer, les attributs et les noms des relations
• On renomme les attributs d’une relation
Exemple:
– Soit R (A1,A2,A3)
– R1= (A1:B1, A2,:B2,A3:B3) R : crée une nouvelle relation R1 en renommant tous
les attributs de R
– On peut renommer qu’un sous ensemble des attributs d’une relation:
– Exemple:
• R2 = (A1:B1,A3:C1)R
Jointure externe
Jointure externe (External Join) : opération générant une relation T à partir de deux
relations R et S, par jointure de ces deux relations et ajout de tuples de relations R et S ne
participant pas à la jointure, avec des valeurs nulles pour les attributs de l’autre relation
Notations :
– T=R S, ou T=R S
– T=EXT-JOIN(R, S)
• La jointure externe permet de conserver les tuples « sans correspondant « avec des
valeurs nulles associées quand nécessaire.
• Opération très utile en pratique, en particulier pour composer des vues sans perte
d’informations (ex., on peut joindre des tables CLIENTS et COMMANDES sur un
numéro de client commun, en gardant les clients sans commande et les commandes sans
client associé
• On en distingue deux types :
– La jointure externe droite qui garde seulement les tuples sans correspondant de la
relation droite. Celle-ci est notée , , ou REXT-JOIN
– La jointure externe gauche qui garde seulement les tuples sans correspondant de la
relation gauche. Celle-ci est notée , , ou LEXT-JOIN
Jointure externe
R S R S R S
Algèbre relationnelle
4. Les expressions de l’algèbre relationnelle
• A partir des opérations de l’algèbre relationnelle, il est possible de composer un langage
d’interrogation de bases de données.
• Chaque requête (question) peut être représentée par arbre d’opérateurs relationnels
• Le paraphrasage en anglais de telles expressions est à la base du langage SQL.
4.1. Langage algébrique
• La réponse à la plupart des questions que l’on peut poser à une base de données
relationnelle peut s’élaborer en utilisant des expressions d’opérations de l’algèbre
relationnelle.
Algèbre relationnelle
4.1. Langage algébrique
• Soit le schéma relationnel d’une base de données touristiques (les clés sont soulignées)
Exemple de requêtes
• Ces requêtes peuvent être exprimées comme des expressions d’opérations, ou comme
des opérations successive appliquées sur des relations intermédiaires ou de base,
générant des relations intermédiaires.
Algèbre relationnelle
• (Q1) Donner les noms de station de la région Haute-Normandie et d’altitude > 1000 M
:
– R1 = REGION=" Haute-Normandie" (STATION)
– R2 = ALTITUDE>1000(STATION)
– R3 = R1 R2
– RESULTAT = NOMSTA(R3)
• La requête (Q1) peut simplement s’exprimer comme suit
Algèbre relationnelle
• (Q2) Donner les numéros et noms des hôtels de la station de Paris OU d’Alsace :
– R1 = REGION=" Paris" (STATION)
– R2 = REGION =" Alsace" (STATION)
– R3 = R1 R2 schéma (R3) =schéma( STATION)
– R4 = R3 HÔTEL schéma(R4)= Schéma(R5) union Schéma(Hotel)
NUMSTA
– RESULTAT = NUMHOT,NOMHOT(R4)
Ou tout simplement
Algèbre relationnelle
– (Q3) Donner les noms et adresses des clients ayant réservé plus de 5 places dans
un hôtel de 3 étoiles avec le nom de cet hôtel :
– R1 = NBPERS>5(RESERVER)
– R2 = CATEGORIE =" ***" (HÔTEL)
– R3 = NUMCLI,NUMHOT(R1) // schéma R3 (NUMCLI,NUMHOT)
– R4 = CLIENT R3 // pour chercher le nom du clients schéma(CLIENT) union
– schéma (R3)
– R5 = R2 R3 // pour chercher le nom de l’hotel schéma de R2 union schéma(R3)
– R6 =R4 R5
– RESULTAT = NOMCLI,ADRCLI,NOMHOT(R6)
ou tout simplement
• Q4) Donner le nom des clients n’ayant réservé que dans des hôtels 4 étoiles :
– R1=CLIENT RESERVER HÔTEL
– R2= CATEGORIE =" ****" (R1)
– R3= NOMCLI(R2)
– R4= CATEGORIE " ****" (R1)
– R5= NOMCLI(R4) ,
– RESULTAT= R3-R5 schéma(R3)=Schéma(R5)
Arbre algébrique
• Une question exprimée sous forme d'un programme d'opérations de l'algèbre relationnelle
peut être représentée par un arbre relationnel.
• L'arbre relationnel est un arbre dont les nœuds correspondent aux représentations graphiques
des opérations de l'algèbre relationnelle et les arcs à des relations temporaires ou de base
représentant des flots de données entre opérations.
• Plusieurs arbre équivalents peuvent être déduits d'un arbre donné à l'aide de règles de
transformation simples, telles que la permutation des jointures et restrictions, la permutation
des projections et des jointures, le regroupement des intersections sur une même relation, etc.
• Ces transformations sont à la base des techniques d'optimisation de question
• La composition d'opérations de l'algèbre relationnelle ne nécessite pas toujours d'attendre le
résultat de l'opération précédente pour exécuter l'opération suivante.
• Les opérations de restrictions, jointures et projections peuvent ainsi être exécutées par des
algorithmes à flots de données.
• Les opérateurs qui se succèdent dans un arbre peuvent être exécutés en parallèle par des
algorithmes "pipe-line"
• Les opérateurs figurants sur des branches distinctes d'un arbre peuvent aussi être exécutés en
parallèle de manière indépendante.
• La représentation par arbre algébrique met ainsi en évidence les possibilités de parallélisme et
les enchaînements nécessaires. Ces propriétés sont importantes pour optimiser les questions
dans des contextes parallèles.
Algèbre relationnelle
Exemple :
La question "Noms et Adresses des clients habitant Alger ayant effectué une réservation le
12/05/2008 dans un hôtel de trois étoiles" peut être exprimée à l'aide de l'arbre suivant :