L’algèbre - HEC UNIL · 2004. 11. 3. · BDA.6.4 L’approche algèbrique n Une algèbre est un...

Bases de Données Relationnelles

L’algèbre relationnelle

BDA.6.2

Langages de manipulation

n Langages formels : base théorique solide

n Langages utilisateurs : version plus ergonomique

n Langages procéduraux : définissent comment dériver le résultat souhaité

n Langages assertionnels (ou déclaratifs) : définissent le résultat souhaité

BDA.6.3

LMD classiques

n Langages formels u langages algèbriques : définissent un ensemble

d’opérateurs de manipulationu langages prédicatifs (calcul) : définissent le résultat

souhaité en utilisant des expressions de logique

n Langages utilisateursu inspirés principalement des langages algèbriques : SQLu inspirés des langage prédicatifs : QBE, QUEL

BDA.6.4

L’approche algèbrique

n Une algèbre est un ensemble d’opérateurs de base, formellement définis, qui peuvent être combinés à souhait pour construire des expressions algèbriques

n Propriété des algèbres : fermeture

Le résultat de tout opérateur est du même type que les opérandes (ce qui est indispensable pour construire des expressions)

n Propriété souhaitée : complétude

Toute manipulation pouvant être souhaitée par les utilisateurs devrait pouvoir être exprimable par une expression algèbrique

BDA.6.5

L’algèbre relationnelle

n Opérandes : relations du modèle relationnel (1NF)

n Fermeture : le résultat de toute opération est une nouvelle relation

n Complétude : permet toute opération sauf les fermetures transitives et les fonctions d'agrégation (min, max, count…)

n Opérations unaires (un seul opérande) :sélection (σ), projection (π), renommage (α)

n Opérations binaires (deux opérandes):produit cartésien (×), jointures (*), union (∪), intersection (∩), différence (−), division (/)

BDA.6.6

Préambule

n Pour chacune de ces 9 opérations, on donne : u l’opérationu la syntaxe (notation)u la sémantique (résultat attendu)u le schémau d’éventuelles remarquesu un exemple

BDA.6.7

Sélection σ

n But : ne retenir que certains tuples dans une relation

Pays nom capitale population surfaceAutriche Vienne 8 83UK Londres 56 244Suisse Berne 7 41

On ne veut que les pays dont la surface est inférieure à 100 :

Petit-pays = σ [surface < 100] Pays

Petit-pays nom capitale population surfaceAutriche Vienne 8 83Suisse Berne 7 41

BDA.6.8

Sélection σ

n Petit-pays = σ [surface < 100] Pays

n Syntaxe : σ [c] Rc : condition de sélection

n condition-élémentaire : attribut opérateur-de-comparaison constante-ou-attributu attribut est un attribut de la relation R u opérateur-de-comparaison : =, ? , <, >, =, =

n condition :u condition-élémentaireu condition ET/OU condition ET ∧ OU ∨uNON condition NON ¬u ( condition )

BDA.6.9

Condition de sélection - Exemples

n σ [ nom=capitale ] Pays

n Pays dont le nom est le même que celui de sa capitale

n σ [ (surface>100 ∧ surface<500) ∨ (population>30 ∧population<300) ] Pays

n Pays dont la surface est comprise entre 100 et 500 ou dont la population est comprise entre 30 et 300

BDA.6.10

Sélection σ

n sémantique : crée une nouvelle relation de population l’ensemble des tuples de R qui satisfont la condition

n schéma (résultat) = schéma (opérande)

n population (résultat) ⊆ population (opérande)

BDA.6.11

Projection π

n But : ne retenir que certains attributs dans une relation

Pays nom capitale population surfaceAutriche Vienne 8 83UK Londres 56 244Suisse Berne 7 41

On ne veut que les attributs nom et capitale :

Capitales = π [nom, capitale] Pays

Capitales nom capitaleAutriche VienneUK LondresSuisse Berne

BDA.6.12

Projection π

n opération unaire

n syntaxe : π [attributs] Ru attributs : liste des attributs de R à conserver dans le résultat

n sémantique : crée une nouvelle relation de population l’ensemble des tuples de R réduits aux seuls attributs de la liste spécifiée

n schéma (résultat) ⊆ schéma (opérande)

n nb tuples (résultat) = nb tuples (opérande)

BDA.6.13

Effet de bord de la projection

n Création et élimination de tuples en doubleuUne projection qui ne conserve aucun identifiant de la relation

peut générer dans le résultat des tuples identiques (à partir detuples différents de l’opérande)

u le résultat ne gardera que les tuples différents (fermeture)

R ( B , C, D)

b c da a ba a c

π [ B , C] R

b c a a

trois tuples deux tuples

BDA.6.14

Expressions

n On veut les capitales des petits pays:u Petit-pays = σ [surface < 100] Pays

u Capitale-petit-pays = π [nom, capitale] Petit-pays

Capitale-petit-pays =

π [nom, capitale] σ [surface < 100] Pays

(Parties grise et beige à enlever)

nom capitale population surface

Irlande Dublin 3 70Autriche Vienne 8 83

UK Londres 56 244Suisse Berne 7 41

BDA.6.15

Expressions - exemples

Surface-petit-pays =

π [nom, surface] σ [surface < 100] Pays

OU σ [surface < 100] π [nom, surface] Pays

Capitale-petit-pays =

π [nom, capitale] σ [surface < 100] Pays

MAIS σ [surface < 100] π [nom, capitale] Pays ERREUR !

π [nom, capitale] σ [surface < 100] π [nom, capitale, surface] Pays OK

BDA.6.16

Renommage α

n but : résoudre des problèmes de compatibilité entre noms d’attributs de deux relations opérandes d’une opération binaire

n opération unairen syntaxe : α [nom_attribut1 -> nouveau_nom1, …] R

n sémantique : les tuples de R avec un (des) nouveau nom d'attribut

n schéma de α [n1–>m1, …, ni–>mi] R : le même schéma que R avec les attributs n1, … ni renommés en m1, … mi

n précondition : les nouveaux noms n’existent pas déjà dans Rn exemple : R2 = α [B–>C] R1

R1 A Ba by zb b

R2 A Ca by zb b

BDA.6.17

Produit cartésien ×

n but : construire toutes les combinaisons de tuples de deux relations (en général, en vue d’une sélection)

n syntaxe : R × S

n exemple : R × S A Ba b a ba bb cb cb cc b c bc b

C D Ec d eb a ba a cc d eb a ba a cc d eb a ba a c

n x m tuples

A Ba bb cc b

C D Ec d eb a ba a c

R S

m tuplesn tuples

BDA.6.18

Produit cartésien ×

n opération binaire

n sémantique : chaque tuple de R est combiné avec chaque tuple de S

n schéma : schéma (R × S) = schéma(R) ∪ schéma(S)

n précondition : R et S n’ont pas d’attributs de même nom (sinon, renommage des attributs avant de faire le produit)

BDA.6.19

Jointure naturelle ou *

n but : créer toutes les combinaisons significatives entre tuples de deux relationsu significatif = ont la même valeur pour tous les attributs de

même nom

n précondition : les deux relations ont au moins un attribut de même nom

n exemple :

R A Ba bb cc b

S B C Db c da a bd a c

Aac

B C Db c db c d

R * S

BDA.6.20

Jointure naturelle ou *

n opération binaire

n syntaxe : R * S

n sémantique : combine certains tuples

n schéma : schéma (R * S) = schéma (R) ∪ schéma (S)u les attributs de même nom n’apparaissent qu’une seule fois

n la combinaison exige l’égalité des valeurs de tous les attributs de même nom de R et de Su si R et S n’ont pas d’attributs de même nom la jointure peut

être dynamiquement remplacée par un produit cartésien

BDA.6.21

Jointure naturelle - Exemple

n Pays (nom, capitale, population, surface, continent)

LangueParlée (langue, pays, %population)

n Pour chaque langue, dans quels continents est-elle parlée ?

n π [langue, continent] ( LangueParlée * α [nom –> pays] Pays )

BDA.6.22

R A Ba bb cc b

S C D Eb c db a bc a c

R * [B ? C ] S

A B C D Ea b c a cb c b c db c b a bc b c a c

Theta jointure [c] ou *[c]

n but : créer toutes les combinaisons significatives entre tuples de deux relations u significatif = selon un critère de combinaison explicitement

défini en paramètre de l’opération (c)

n précondition : les deux relations n’ont pas d’attribut de même nom

n exemple : R * [B ? C] S

BDA.6.23

Theta-jointure

n opération binaire

n syntaxe : R *[c] Su c : condition de jointure

n condition-élémentaire : attribut1 opérateur-de-comparaison attribut2u attribut1 est un attribut de la relation Ru attribut2 est un attribut de la relation S (ou vice-versa)u opérateur-de-comparaison : =, ? , <, >, =, =

n condition :u condition-élémentaireu condition ET/OU condition ET ∧ OU ∨

u NON condition NON ¬u ( condition )

BDA.6.24

Theta-jointure (suite)

n sémantique : combine les tuples qui satisfont la condition

n schéma (R *[c] S) = schéma (R) ∪ schéma (S)

n Exemple :Pays (nom, capitale, population, surface, continent)LangueParlée (langue, pays, %population)

Pour chaque langue, dans quels continents est-elle parlée ?

π [langue, continent] ( LangueParlée *[nom = pays] Pays )

BDA.6.25

Jointures : opérateurs dérivés

n R ( A, B, C )

n S (C, D, E )

n R*S = π [A, B, C, D, E] σ [CC=C] ((α [C–>CC] R) x S)

n Même chose pour la theta-jointure

BDA.6.26

Union ∪

n opération binaire

n syntaxe : R ∪ S

n sémantique : réunit dans une même relation les tuples de R et ceux de S

n schéma(R ∪ S) = schéma(R) = schéma(S)

n précondition : schéma(R) = schéma(S)

n Exemple :

R1 A Ba bb by z

R2 A Bu vy z

R1 ∪ R2 A Ba bb by zu v

BDA.6.27

Union (suite)

n Effet de bord : des tuples en double peuvent être créés.

n Ils sont automatiquement supprimés du résultat.

BDA.6.28

Intersection ∩

n opération binaire

n syntaxe : R ∩ S

n sémantique : sélectionne les tuples qui sont à la fois dans R et S

n schéma (R ∩ S) = schéma (R) = schéma (S)

n précondition : schéma (R) = schéma (S)

n Exemple :

R1 A Ba by zb b

R2 A Bu vy z

R1 ∩ R2 A By z

BDA.6.29

Différence -

n opération binaire

n syntaxe : R − S

n sémantique : sélectionne les tuples de R qui ne sont pas dans S

n schéma (R − S) = schéma (R) = schéma (S)

n précondition : schéma (R) = schéma (S)

n Exemple :

R1 A Ba by zb b

R2 A Bu vy z

R1 − R2 A Ba bb b

BDA.6.30

Intersection : opérateur dérivé

n R ∩ S = R - (R - S)

R S populations

R-S

R∩S

BDA.6.31

La division /

n But : traiter les requêtes du genre «les … tels que TOUS les …»

n Soient R(A1, …, An) et V(A1, …, Am) avec n>m et A1, …, Am des attributs de même nomdans R et V

n R/V = les tuples de R réduits aux attributs Am+1, …, Antels qu'ils existent dans R concaténés à tous les

tuples de V

n R/V = { <am+1, am+2, …, an> / ∀<a1, a2, …, am> ∈V ∃<a1, a2, …, am ,am+1, am+2, …, an> ∈R }

BDA.6.32

La division - exemples

R A B C1 1 11 2 01 2 11 3 02 1 12 3 33 1 13 2 03 2 1

V B C1 1 2 0

R/V A13

V’ B C1 1

R/V’ A123

V’’ B C3 5

R/V’’ A/

BDA.6.33

Exemple de division

R/V : Etudiants ayant tous les prérequis

PierreFrancoisETUDIANT

R/V

SIAnnie

SIFrançois

BDAnnie

MathAnnie

ProgPierre

BDPierre

ProgFrancois

BDFrancoisCOURSETUDIANT

Prog

BD

COURS

R : Obtenu V : Prérequis

BDA.6.34

Division - opérateur dérivé

n R(A1, …, An) et V(A1, …, Am) avec n>m

n R / V = π[Am+1, …, An)] R -

π[Am+1, …, An)] ( ( (π[A1, …, Am)]R) x V ) - R )

BDA.6.35

Propriétés des opérateurs

n R ∩ S = S ∩ R (commutativité)

n R * S = S * R

n …

n σ [p1] (σ [p2] R) = σ [p2] (σ [p1] R) = σ [p2 ∧ p1] R

n σ [p] (π [a] R) = π [a] (σ [p] R) si attributs(p) ⊆ a

n …

Utilité : optimisation des expressionsu faire les sélections et projections le plus tôt possible

pour réduire le volume des relations opérandes

BDA.6.36

Optimiseur de requêtes

1) Traduction enexpression algébrique

2) Optimisation de l'expression algébrique

3) Exécution des opérations de l'algèbre

Base de données

SELECT …FROM …WHERE ...

SGBD

BDA.6.37

Exemples de requêtes algébriques

n Soient les relations suivantes :

Journal (code-j, titre, prix, type, périodicité)

Dépôt (no-dépôt, nom-dépôt, adresse)

Livraison (no-dépôt, code-j, date-liv, quantité-livrée)

BDA.6.38

Répondre aux requêtes suivantes :

n Quel est le prix des journaux ?

π [titre, prix] Journal

n Donnez tous les renseignements connus sur les journaux hebdomadaires

σ [périodicité = "hebdomadaire"] Journal

BDA.6.39

Répondre aux requêtes suivantes (2)

n Donnez les codes des journaux livrés aux dépots de Bienne

π [code-j] ( σ [adresse = "Bienne"] Dépôt * Livraison)

Dépôt (no-dépôt, nom-dépôt, adresse)

Livraison (no-dépôt , code-j, date-liv, quantité-livrée)

Bienne

?

BDA.6.40

n Donnez les numéros des dépots qui reçoivent plusieurs journaux

Répondre aux requêtes suivantes (3)

π [no-dépôt] (α [ no-dépôt -> dépôt2 , code-j -> code2] Livraison

* [code-j ≠ code2 ∧ no-dépôt=dépôt2] π [no-dépôt, code-j] Livraison )

Livraison (no-dépôt , code-j, date-liv, quantité-livrée)

Livraison (no-dépôt , code-j, date-liv, quantité-livrée)?

= ?