Extrait du cours algèbre et calcul relationnel
LES EXPRESSIONS DE L’ALGÈBRE RELATIONNELLE
À partir des opérations de l’algèbre relationnelle, il est possible de composer un langage d’interrogation de bases de données. Une question peut alors être représentée par un arbre d’opérateurs relationnels. Le paraphrasage en anglais de telles expressions est à la base du langage SQL que nous étudierons dans le chapitre suivant.
6.1. LANGAGE ALGEBRIQUE
En utilisant des expressions d’opérations de l’algèbre relationnelle, il est possible d’élaborer les réponses à la plupart des questions que l’on peut poser à une base de données relationnelle. Plus précisément, les opérations de base de l’algèbre relationnelle constitue un langage complet, c’est-à-dire ayant la puissance de la logique du premier ordre.
Afin d’illustrer, nous exprimons quelques questions sur la base DEGUSTATION . Ces questions peuvent être exprimées comme des expressions d’opérations, ou comme des opérations successives appliquées sur des relations intermédiaires ou de base, générant des relations intermédiaires. Pour des raisons de clarté, nous avons choisi cette deuxième représentation. L’expression peut être obtenue simplement en supprimant les relations intermédiaires notées Ri.
(Q1) Donner les degrés des vins de crus MORGON et de MILLESIME 1978:
R1 = RESTRICT (VINS, CRUS = “MORGON”)
R2 = RESTRICT (VINS, MILLESIME = 1978)
R3 = INTERSECT (R1, R2)RESULTAT = PROJECT (R3, DEGRE)
(Q2) Donner les noms et prénoms des buveurs de MORGON ou CHENAS:
Ri = RESTRICT (VINS, CRU = “MORGON”)
R2 = (VINS, CRUS = “CHENAS”)
R3 = UNION (R1, R2)
R4 = JOIN (R3, ABUS)
R5 = JOIN (R4, BUVEURS)
RESULTAT = PROJECT (R5, NOM, PRENOM)
(Q3) Donner les noms et adresses des buveurs ayant bu plus de 10 bouteilles de Chablis 1976 avec le degré de ce vin:
R1 = RESTRICT (ABUS, QUANTITE>10)
R2 = RESTRICT (VINS, CRU = “CHABLIS”)
R3 = RESTRICT (VINS, MILLESIME = 1976)
R4 = INTERSECT (R2, R3)
R5 = JOIN (R1, R4)
R6 = PROJECT (R5, NB, DEGRE)
R7 = JOIN (R6, BUVEURS)
RESULTAT = PROJECT (R7, NOM, ADRESSE, DEGRE)
(Q4) Donner les noms des buveurs n’ayant bu que du Morgon:
R1 = JOIN(BUVEURS,ABUS,VINS)
R2 = RESTRICT(R1, CRU = “MORGON”)
R3 = PROJECT(R2, NOM)
R4 = RESTRICT(R1, CRU ¹ “MORGON”)
R5 = PROJECT(R1, NOM)
RESULTAT = MINUS(R3 – R5)
6.2 ARBRE ALGEBRIQUE
Une question exprimée sous forme dun programme d’opérations de l’algèbre relationnelle peut être représentée par un arbre relationnel.Les nœuds correspondent aux représentationsgraphiques des opérations indiquées ci-dessuset les arcs aux flots de données entre opérations.
Afin d’illustrer, la question “Noms et Prénoms des buveurs habitant Paris ayant bu du Chablis depuis le 1er janvier 1992” peut être exprimée à l’aide de l’arbre représenté figure 20. Plusieurs arbres équivalents peuvent être déduits d’un arbre donné àl’aide de règles de transformation simples, telles que permutation des jointures et restrictions, permutation des projections et des jointures, regroupement des intersections sur une même relation, etc. Ces transformations sont à la base des techniques d’optimisation de questions qui dépassent le sujet de ce chapitre. La figure 21 donne un arbre équivalent à celui de la figure 20, obtenu par descente de projections et regroupement d’intersections.
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. Restriction, projection et jointure peuvent ainsi être exécutées par des algorithmes àflots de données. Des opérateurs se succédant sur un arbre peuvent donc être exécutés en parallèle par des algorithmes “pipe-line”. Des opérateurs figurant 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 des arbres relationnels sont importantes pour optimiser les questions dans des contextes parallèles.
……
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Algèbre et calcul relationnel (164 KO) (Cours DOC)
