Chapitre 5 Comprendre SQL grâce - lri.frcohen/DOCS/chap5.pdf · Exercice 1 • Quel est le résultat de la requête Q3 suivante en considérant l’instance de la ... SQL par défaut

1Sarah Cohen-Boulakia, Bases de données

1

Département Informatique

Chapitre 5

Comprendre SQL grâce

à l’Algèbre Relationnelle


2


Langage de requêtes pour les BDs

relationnelles (1/2)

• Langage de requêtes : ils permettent de

manipuler et de retrouver des données d’une

base de données

• Le modèle relationnel supporte des requêtes

simples et expressives

• Les langages de requêtes pour les BDs

relationnelles sont fondés sur des bases

formelles solides (logique du premier ordre)


3


Langage de requêtes pour les BDs

relationnelles (2/2)

• Langage de requêtes ≠ langage de

programmation

– Un langage de requêtes n’a pas pour but

d’être utilisé pour faire des traitements ou

calculs complexes

– But : être facile d’utilisation et offrir un

accès efficace aux données


4


Langages de requêtes formels

• 2 langages de requêtes formels existent

(fondement de SQL)

– L’algèbre relationnelle : langage opérationnel,

une requête s’écrit comme une succession

d’opérations effectuées sur des relations

– Calcul relationnel : langage déclaratif, une

requête s’écrit comme la spécification du

résultat attendu (sous forme logique)


5


Préliminaire 1

• Une requête s’applique à des instances

de relations et le résultat d’une requête

est aussi une instance de relation

– Autrement dit : Une requête se pose sur des

tables qui ont un contenu (potentiellement

vide) et renvoie une table avec un contenu

(potentiellement vide)

Requête Q

prenant en

entrée R1 et

R2

R1 : table R2 : tableRésultat de Q

= une table


6


Préliminaire 2

• Le schéma du résultat d’une requête

sera toujours le même, quelque soit le

contenu des relations

– La table résultat d’une requête mettra toujours

en jeu les mêmes attributs (quelque soit le

contenu !)


7


Préliminaire 3

• Les schémas des relations prises en

entrées par une requête sont fixés

– Une requête s’exprime grâce à des noms

d’attributs et de tables

• Mais une requête ne doit jamais

dépendre des instances des relations

– Aucune connaissance du contenu des tables

ne doit être nécessaire pour bien comprendre

la requête


8


Algèbre relationnelle

• Opérateurs de base

– Sélection (), Projection (), Produit cartésien (X),

– Différence (\ ou -) et Union (U)

• Autres opérateurs

– Intersection, jointure, division, renomage: très utiles

aussi !

• Puisque chaque opérateur appliqué à une

relation renvoie une relation, les opérateurs

peuvent être imbriqués (clôture de l’Algèbre

relationnelle)


9


Projection : introduction

• Notation : A1,…,Ap(R) avec r relation et

A1,…,Ap attributs de R

• Supprime les attributs qui sont différents des attributs de la liste de projection (A1,…,Ap)

• Le schéma du résultat contient exactement les champs de la liste de projection (A1,…,Ap)

• NB : L’opérateur de projection élimine les redondances (ce n’est pas le cas en SQL)


10


Projection : exemple

Q1=NumClient, DateRes(Reservation)

ClasseDateRes

1 18/11/2007

2 19/11/2007

Reservation

NumClient

17902567

2780289

NumRes

001

002

DateRes

18/11/2007

19/11/2007

Q1NumClient

17902567

2780289

NB : la projection est un opérateur qui n’agit pas sur

les lignes du résultat mais sur les colonnes (c’est-à-

dire sur le schéma)


11


Projection : Définition formelle

Input

– r une relation de schéma R

– X un ensemble d’attributs tels que X R

Output

Où t(X) est la restriction de t sur les attributs de X

Ensemble des n-uplets de r restreints aux attributs de X

Le schéma de X(r) est X

X(r)={t(X) / t r}


12


Sélection : introduction

• Sélection des n-uplets (lignes) qui

satisfont la condition de sélection

• Le schéma du résultat est identique au

schéma pris en entrée


13


Sélection : exemple

Q2=(DateRes<20-11-2007Classe=2)(Reservation)

ET

Condition de sélection

ClasseDateRes

1 18/11/2007

2 19/11/2007

Réservation

NumClient

17902567

2780289

NumRes

001

002

Q2

2 20/11/2007 2780289003

Classe DateRes

2 19/11/2007

NumClient

2780289

NumRes

002


14


Sélection : Définition formelle

Input

– r une relation de schéma R

– une condition de sélection (définie ci-après)

Output

L’ensemble des n-uplets de la relation r pour

lesquels la condition est vraie

Le schéma de (r) est R

(r)={t / t r et (t)}


15


Définition formelle de la condition Définition récursive

• Base : Soient 2 attributs A et B (non

nécesairement différents), et a Dom(A)

peut prendre les formes suivantes

A =B, A < B, A=a, A < a (on utilisera aussi >, ≤, ≥ et ≠)

• Si 1 et 2 sont deux conditions alors

(1), ¬1 (négation), 1 2 (et) et 1 2 (ou)

sont des conditions de sélection


16


Exemples de conditions

• DateRes ≥ 20-11-2007

• Classe = 2

• Nom = ‘Payen’

• (DateRes = 20-11-2007

DateRes = 21-11-2007)

Classe = 2

• NumClient = NumSS


17


Exercice 1

• Quel est le résultat de la requête Q3

suivante en considérant l’instance de la

relation R ci-dessous ?

NumEns Nom Prénom

1 Voisin Jean

2 Benzaken Claudine

3 Jean

Enseignant

Forest

Q3 =Nom(Prénom = ‘Jean’ (Enseignant) )


18


Correction (Exercice 1)


suivante en considérant l’instance de la

relation R ci-dessous ?

NumEns Nom Prénom

1 Voisin Jean

2 Benzaken Claudine

3 Jean

Enseignant

Forest

Q3 =Nom(Prénom = ‘Jean’ (Enseignant) )

Nom

Voisin

Q3

Forest


19


Produit cartésien : Introduction

• Opérateur binaire (prend deux relations entre entrée : r1 et r2)

• Chacun des n-uplets de r1 est combiné avec chacun des n-uplets de r2

• Le schéma du résultat a l’union des attributs des relations

• NB : Si les deux relations ont un attribut de même nom, on renomme cet attribut


20


Produit cartésien : Exemple

R1 x R2A B

a1 b1

a2 b2

R1

A D

a2 d2

a2

a3

R2

d3

d4

C

c1

c2 R1.A B C R2.A D

a1 b1 c1 a2 d2

a1 b1 c1 a2 d3

a1 b1 c1 a3 d4

a2 b2 c2 a2 d2

a2

a2

b2

b2

c2

c2

a2

a3

d3

d4

Renommage


21


Produit cartésien : Définition formelle

Input

– r, s deux relations de schéma R et S

Output

r x s = {t / t(R) r et t(S) s}

La restriction du produit aux attribut de R est r et

celle aux attributs de S est s

r x s a pour schéma R+S

NB : R+S est l’union disjointe de R et S

{R.A / AR } U {S.B / B S}


22


SQL par défaut fait un produit cartésien !

SELECT Nom,

Prenom,

Reservation.NumRes,

DateRes

FROM Reservation,

Client

WHERE DateRes <

‘2007-11-19’

NumSS Nom Prénom

17902567 Payen Olivier

2780289 Payen Judith

29005579 Quoti Mathilde

Client

Classe DateRes

1 18/11/2007

2 19/11/2007

Reservation

NumClient

17902567

2780289

NumRes

1

2

Nom Prenom DateRes

Payen Olivier 18/11/2007

Payen Judith 18/11/2007

Quoti Mathilde 18/11/2007

1

1

1

NumRes

Ces deux lignes mélangent des informations qui n’ont

rien à voir !!


23


Jointure naturelle : Introduction

• Opération binaire fondamentale (optimisation) !

• Utilise R1 et R2 qui ont des attributs communs

(appelons-les X)

• Le schéma du résultat est

– similaire au schéma du produit cartésien

– modulo que les attributs X n’apparaissent qu’une fois

• Au niveau des lignes : on combine les lignes de

R1 avec les lignes de R2 qui ont même valeur

pour les attributs X


24


Jointure naturelle : Exemple

R1 R2A B

a1 b1

a2 b2

R1

A D

a2 d2

a2

a3

R2

d3

d4

C

c1

c2

A B C D

a2 b2 c2 d2

a2 b2 c2 d3

R1 R2Équivaut à

R1.A = R2.A


25


Jointure naturelle : Définition formelle

• Input

– r et s de schéma R et S

• Output

r s = {t / t(R) r et t(S) s}

r s = R union S (r x s)

Avec R S = {B1, …, Bp}

: t(R.B1)= t(S.B1) … t(R.Bp)= t(S.Bp)


26


Phi (ou théta) Jointure

• Cas particulier de jointure avec condition

est une condition de sélection

R1 R2

A D

3 2

2

1

R2

3

4

A D E B C

3

3

2

2

2

3

1

9

1

7

2

7

1

2

1

E B

1 7

9 2

R1

C

1

R1 R2

2

R2.A > R1.C


27


Union, Intersection, Différence :

Introduction

• Tous ces opérateurs prennent en entrée 2 relations qui doivent avoir le même schéma

• Union (R1 R2) : ensemble de n-uplets qui sont dans R1 ou dans R2

• Intersection (R1 R2) ensemble de n-uplets qui sont dans R1 et dans R2

• Différence (R1 \ R2 ou R1 – R2) : ensemble de n-uplets qui sont dans R1 mais pas dans R2


28



Exemples

A B

a1 b1

a2 b2

a3

R1

b3

A B

a1 b1

a2

a3

R2

b3

A B

a1 b1

a2

a3

b2

R1 R2

b4

b3

a2

a3

b3

b4

A B

a1 b1

R1 R2

A B

a2 b2

R1 \ R2

a3 b3

Les n-uplets de R1

union ceux de R2

Pas de doublon

Les n-uplets

à la fois

dans R1 et

dans R2Les n-uplets

de R1 mais

qui ne sont

pas dans R2


29



Définitions formelles

Input

– r, s deux relations de même schéma R

Output

r s = { t / t r ou t s }

r s = { t / t r et t s }

r \ s = { t / t r et t s }

de schéma R


30


Exercice 2


suivante en considérant les instances des

relations ci-dessous ?

Q4 =(A,B(C ≠ c1 (R1) )) R2

A B

a1 b1

a2 b2

a3

R1

b3

A B

a2 b2

a2

a3

R2

b3

b4

C

c1

c2

c3


31


Correction (Exercice 2) 1/3


suivante en considérant l’instance des


Q4 =A,B(C ≠ c1 (R1) ) R2

A B

a1 b1

a2 b2

a3

R1

b3

A B

a2 b2

a2

a3

R2

b3

b4

C

c1

c2

c3


32






Q4 =A,B(C ≠ c1 (R1) ) R2

A B

a1 b1

a2 b2

a3

R1

b3

A B

a2 b2

a2

a3

R2

b3

b4

C

c1

c2

c3


33






Q4 =(A,B(C ≠ c1 (R1) )) R2

A B

a1 b1

a2 b2

a3

R1

b3

A B

a2 b2

a2

a3

R2

b3

b4

C

c1

c2

c3

A B

a2 b2

Q4


34


Propriétés algébriques

• L’union et l’intersection sont commutatifs et associatifs– r s = s r, r (s1 s2) = (r s1) s2

– De même pour

• Le produit cartésien est associatif et commutatif*

• La jointure est associative et commutative*

• D’autres propriétés peuvent être énoncées : monotonie de certains opérateurs, fermeture etc.

*si on considère un ordre sur les colonnes


35


Exemple d’équivalences• Les relations d’équivalence de l’algèbres sont des

égalités entre des formules

• Elles sont à la base des optimisations de requêtes !

• Exercice – Sachant que les schémas de R et S sont les mêmes et si

X R, trouvez un contre exemple aux égalités qui sont fausses et démontrez celles qui sont justes

•X (r s) = X (r) X (s)

•X(r – s) = X (r) -X (s)

•X(r s) = X (r) X (s)


36


Exemple d’équivalences (correction)

• Exercice

– Sachant que R = S (schémas) et X R, trouvez un contre exemple aux égalités qui sont fausses et démontrez celles qui sont justes

•X (r s) = X (r) X (s) NON

•X(r – s) = X (r) -X (s) NON

•X(r s) = X (r) X (s) OUI !


37


Non Distributivité de l’intersection

•X (r s) = X (r) X (s) NON

Contre exemple

A B

a b

A B

a b’

r s A (r s) =

A (r) A (s) = {a}


38


Non Distributivité de la différence

•X (r - s) = X (r) -X (s) NON

Contre exemple

A B

a b

A B

a b’

r s A (r - s) = {a}

A (r) -A (s) =


39


Distributivité de l’union : Démonstration

X (r s) = X (r) X (s)

On se ramène aux définitions

Rappel : X(r)={t(X) / t r} ; tX(r) t’ r et t’(X)=t

t X (r s) t’, t’ (r s) et t’(X)=t // par définition de la projection

t’ ((t’ r) ou (t’s)) et t’(X)=t // par définition de l’union

t’ ((t’ r) et t’(X)=t) ou ((t’s) et t’(X)=t) // distrib. de « et » sur « ou »

( t’, t’ r et t’(X)=t) ou ( t’, t’s et t’(X)=t) // distributivité de

t X (r) ou t X (s) // par définition de la projection

t (X (r) X (s)) // par définition de l’union


40


Conclusion

• L’algèbre relationnelle est définie de façon

très rigoureuse et offre un langage de

requêtes à la fois simple et puissant

• L’algèbre relationnelle est à la base

– De SQL

– Des plans de requêtes utilisés par les SGBD

pour optimiser les requêtes

Documents

Chapitre 5 Comprendre SQL grâce - lri.frcohen/DOCS/chap5.pdf · Exercice 1 • Quel est le résultat de la requête Q3 suivante en considérant l’instance de la ... SQL par défaut