Cours BdD v2

Algèbre relationnelle

L'algèbre relationnelle...

fournit un point de vue mathématique sur les requêtes SQL ;
est utilisée à des fins d'optimisation de requêtes ;
est à l'origine des bases de données relationnelles.

Définitions

"Mathématisation" d'une base de données...

Base de données : ensemble (fini) de tables.

Table : ensemble (fini) de relations.

Ligne ou rangée : n-uplet d'attributs.

Attribut : (type, valeur) + header (nom, storage_class) [SQLite], ou
valeur + header (nom, type) [PostgreSQL & cie] ;
Exemple : ("Vitesse", réel, 55.1)

Schéma : ensemble des headers (nom, type [SQLite: storage_class]).

Opérateurs sur les attributs

Opérations usuelles entre entiers, réels, booléens... ; p.ex. :

$\text{nom}_1 + \text{nom}_2$
$\text{nom}_1 ≤ \text{nom}_2$
$\neg \text{nom}_1$
$\text{nom}_1 \vee \text{nom}_2 \vee \text{nom}_3$
$\log(\text{nom}_1)$
...

$o(\text{nom_1},\text{nom_2},\dots)$ réalise l'opération ligne par ligne.

Utilisation :

résultats de requêtes : "SELECT" ;
filtres sur les tables : "WHERE".

Exemples

Nom vol	Heure départ	Heure arrivée
AF1952	10:20	14:25
EZS1392	20:45	21:50
TO3566	17:15	19:05

$$\longrightarrow$$

HA - HD
04:05
01:05
01:50

A	B	C
1	2	3
2	1	3
3	1	6

$$\longrightarrow$$

$(A < B) \vee (C > 5)$
TRUE
FALSE
TRUE

Opérateurs sur les tables

Fonctions prenant en paramètre une ou plusieurs tables, et renvoyant toujours une table (éventuellement vide). Exemple :

Prénom	DDN	Numéro
Pauline	25/10/1991	1
Matthieu	15/12/1990	2
Vincent	15/03/1985	3
Amandine	10/06/1982	4

Numéro	Points
1	150
3	170
5	140
7	160

$$\Downarrow$$

Prénom	DDN	Numéro	Points
Pauline	25/10/1991	1	150
Vincent	15/03/1985	3	170

Opérateurs intra-tables

Projection

Restriction sur les colonnes :
$\pi[C_1,\dots,C_k](T)$ ne garde que les colonnes $C_1$ à $C_k$ de la table $T$.

Exemple : $\pi[\text{nom},\text{capitale}](\text{Pays})$

nom	capitale	population	surface
Autriche	Vienne	8	83
UK	Londres	56	244
Suisse	Berne	7	41

Équivalent SQL : SELECT

Sélection

Filtre sur les rangées :
$\sigma[C](T)$ ne garde que les rangées de $T$ vérifiant la condition $C$.

Exemple : $\sigma[\text{surface} < 100](\text{Pays})$

nom	capitale	population	surface
Autriche	Vienne	8	83
UK	Londres	56	244
Suisse	Berne	7	41

Équivalent SQL : WHERE

Exercice

Requête = $\pi_{\text{nss},\text{nom}}(\sigma_{\text{age} < 30 \vee \text{prenom='Solange'}}(\text{Personnes}))$

nss	nom	prénom	âge
12	Aymard	Serge	45
18	Aymard	Hélène	28
45	Fenouil	Solange	35

Personnes

nss	nom
18	Aymard
45	Fenouil

Résultat

Renommage (d'attribut)

Nécessaire si conflit avec des attributs d'autres tables.
Syntaxe : $\alpha[$nom_attribut : nouveau_nom$](T)$

Exemple :
$\alpha[$nom : nom_pays$](\pi[\text{nom},\text{capitale}](\sigma[\text{surface} < 100](\text{Pays})))$

nom_pays	capitale	population	surface
Autriche	Vienne	8	83
UK	Londres	56	244
Suisse	Berne	7	41

Équivalent SQL : AS

Agrégation

Opérateur sur une (voire plusieurs) colonne.

Retourne en général un scalaire (1 ligne 1 colonne).

Exemples :

AVG[nom1 x nom2](T) : moyenne d'un produit ;
SUM[nom1](T) : somme ;
MAX[nom1 + nom2](T) : maximum d'une somme,
...

où $T$ est une table pouvant résulter d'une opération complexe.

Exercices

Quelle opération transforme la table ?

A	B	C
1	2	3
2	3	3
3	1	1
4	5	1

$$\Rightarrow$$

Z	B	C
2	3	3
3	1	1

$\alpha[A:Z](\sigma[B=C](T))$

A	B	C
1	2	3
2	1	4
3	4	2
4	3	1

$$\Rightarrow$$

A	C
1	3
3	2

$\pi[A,C](\sigma[A < B](T))$

Opérateurs inter-tables

Opérations ensemblistes

Soient deux tables $T_1(A_1,\dots,A_n), T_2(A_1,\dots,A_n)$.
On note $\mathcal T$ l'espace des n-uplets d'attributs.

Union : $T_1 \cup T_2 = \{ t \in \mathcal T / t \in T_1 \mbox{ ou } t \in T_2 \}$
Intersection : $T_1 \cap T_2 = \{ t \in \mathcal T / t \in T_1 \mbox{ et } t \in T_2 \}$
Différence : $T_1 \backslash T_2 = \{ t \in \mathcal T / t \in T_1 \mbox{ et } t \notin T_2 \}$.

Mots-clés SQL : UNION, INTERSECT, EXCEPT.

A	B
a	b
y	z
b	b

$T_1$

Exemple/exercice

A	B
u	v
y	z

$T_2$

Produit cartésien

Soient deux tables $T_1(A_1,\dots,A_n), T_2(B_1,\dots,B_m)$.

Définition :
$T_1 \times T_2 = \{ t = (t_1, t_2) / t_1 \in \mathcal T_1, t_2 \in \mathcal T_2 \}$.
Les lignes de $T_1$ sont concaténées avec celles de $T_2$.

Équivalent SQL : SELECT ... FROM T1, T2.

A	B
a	b
y	c
b	b

$T_1$

Exemple/exercice :

C	D	E
c	v	y
b	z	u

$T_2$

Jointure

Soient deux tables $T_1(A_1,\dots,A_n), T_2(B_1,\dots,B_m)$.
Soit une condition $\mathcal C$ portant sur les valeurs d'attributs.

Définition :
$T_1 \underset{\mathcal C}{\bowtie} T_2 = \{ t = (t_1, t_2) / t_1 \in \mathcal T_1, t_2 \in \mathcal T_2, \mathcal C(t_1,t_2) \}$.
On ne retient que les lignes concaténées qui vérifient $\mathcal C$.
Notation alternative : $\bowtie[\mathcal C](T_1,T_2)$.

Exemple/exercice :

A	B
1	1
2	2
3	3

$T_1$

C	D	E
1	2	3
2	3	4

$T_2$

$\mathcal C \equiv A \neq C$ ?
$\mathcal C \equiv B = D$ ?
$\mathcal C \equiv A > C$ ?

Illustration

cinema=> select * from role;

idfilm | idacteur |   nomrole
-------+----------+--------------
     2 |        5 | Ripley
     5 |       11 | Sean Archer
     5 |       12 | Castor Troy
     6 |       14 | Ichabod Crane
    17 |       11 | Vincent Vega

cinema=> select * from artiste;

idartiste |    nom    |  prenom
----------+-----------+----------
        3 | Hitchcock | Alfred
        5 | Weaver    | Sigourney
       10 | Woo       | John
       11 | Travolta  | John
       14 | Depp      | Johnny

Jointure sur "idacteur = idartiste" :

cinema=> select * from artiste join role on idartiste=idacteur;

idartiste |   nom    |  prenom   | idfilm | idacteur |   nomrole
----------+----------+-----------+--------+----------+--------------
        5 | Weaver   | Sigourney |      2 |        5 | Ripley
       11 | Travolta | John      |     17 |       11 | Vincent Vega
       11 | Travolta | John      |      5 |       11 | Sean Archer
       14 | Depp     | Johnny    |      6 |       14 | Ichabod Crane

Exercice

ENO	ENOM	PROF	DNO
10	Joe	Ingénieur	3
20	Jack	Technicien	2
30	Jim	Vendeur	1
40	Lucy	Ingénieur	3

Employés (E)

DNO	DNOM	VILLE
1	Commercial	New York
2	Production	Houston
3	Développement	Boston

Départements (D)

Obtenir les numéros des employés travaillant à Boston.

$\pi_{\text{ENO}}(\sigma_{\text{VILLE='Boston'} \wedge \text{E_DNO=D_DNO}}(E \times D))$, ou
$\pi_{\text{ENO}}\left(E \underset{\text{E_DNO=D_DNO}}{\bowtie} \sigma_{\text{VILLE='Boston'}}(D)\right)$

Division

Soient $T_1(A_1,\dots,A_n), T_2(A_{i_1},\dots,A_{i_k})$ avec $i_j \in [ 1,n ]$.

Définition ($T_2 \subset T_1$) :
$T_1 \div T_2$ = sous-ensemble (maximal) de $T_1$ noté $T'_1$ vérifiant $T'_1 \times T_2 \subset T_1$= Sous-ensemble de $T_1$ qui concaténé à tout $T_2$ donne un sous-ensemble de $T_1$.

Exemple/exercice :

A	B	C	D
a	b	c	d
a	b	e	f
g	h	c	d
i	j	k	l

$T_1$

C	D
c	d
e	f

$T_2$

$T_1 \div T_2 =$ ?

Exemple (venant d'ici)

VILLE_ETP	RAYON_ETP
PARIS	boisson
PARIS	frais
PARIS	conserve
LYON	boisson
LYON	conserve
LYON	droguerie
MARSEILLE	boisson
MARSEILLE	frais
MARSEILLE	conserve
MARSEILLE	droguerie
ANGERS	boisson
ANGERS	frais
ANGERS	droguerie
TOULOUSE	boisson
TOULOUSE	frais
TOULOUSE	conserve
TOULOUSE	droguerie

Dividende : T_ENTREPOT (à gauche)

Diviseur : T_RAYON

RAYON_RYN
boisson
frais
conserve
droguerie

Question : quels sont les entrepôts qui approvisionnent tous les rayons ?

Résultat : T_RESULTAT

VILLE_ETP
MARSEILLE
TOULOUSE

Retour sur les DFs

Théorème (de Heath, ou de décomposition de Casey-Delobel...) :
Soit une relation R(X,Y,Z) avec X, Y, Z groupes d'attributs disjoints.
Si $X \rightarrow Y$ alors la relation peut être divisée sans perte d'information $$R(X,Y,Z) = R_1(X,Y) \underset{R_1.X = R_2.X}{\bowtie} R_2(X,Z)$$

Exemple : R(A,B,C,D) avec

A : numéro de vol (clé),
B : pilote,
C : type d'avion,
D : nombre de places.

X = C → Y = D : $$R(A,B,C,D) = R_1(C,D) \underset{R_1.C = R_2.C}{\bowtie} R_2(A,B,C)$$

Autre décomposition préservant les DFs

Soit la relvar R(X,Y,Z) dans laquelle X, Y et Z sont des sous-ensembles d'attributs de R. Si R satisfait aux dépendances fonctionnelles $X \rightarrow Y$ et $Y \rightarrow Z$, alors plutôt que de décomposer R en {X,Y} et {X,Z}, on décomposera R en {X,Y} et {Y,Z} : $$R(X,Y,Z) = R_1(X,Y) \underset{R_1.Y = R_2.Y}{\bowtie} R_2(Y,Z)$$

Exemple : R(A,B,C,D,E) avec

A : tournoi,
B : joueur (blancs ou noirs),
C : numéro de ronde,
D : partie,
E : résultat.

X = (A,B,C) → Y = D → Z = E : $$R(A,B,C,D,E) = R_1(A,B,C,D) \underset{R_1.D = R_2.D}{\bowtie} R_2(D,E)$$

Définitions - décompositions

Une décomposition (binaire) de la relation $R(X = X_1,...,X_n)$ consiste en un couple de relation $R_1(Y), R_2(Z)$ telles que $Y \cup Z = X$.

Soit une décomposition de R en $R_1$ et $R_2$...

La décomposition est sans perte d'informations si $R = R_1 \bowtie R_2$
La décomposition est sans perte de dépendances si on peut retrouver (par transitivité) toutes les DF de R via des projections sur $R_1$ et $R_2$

La projection de l'ensemble des DF de R sur $R_1$ est l'ensemble des DF de R qui ont leurs attributs de départ et d'arrivée dans $R_1$

Requêtes SQL avec SQLite

Requêtes sur une seule table

SELECT ... FROM ...

Requête la plus simple : affiche des (combinaisons de) colonnes.

Exemples dans le contexte d'une médiathèque, sur la table Document( Code,Type,Description,Titre,Auteur,Date,Emprunteur)

-- Afficher toute la table
SELECT *
FROM Document;

-- Afficher seulement le code et l'auteur
SELECT Code,Auteur
FROM Document;

-- Afficher aussi l'identifiant de l'emprunteur
SELECT Code,Auteur,Emprunteur AS IdentifiantAdherent
FROM Document;

SELECT ... FROM ... WHERE ...

Requête la plus courante : filtre sur les colonnes.

Document( Code,Type,Description,Titre,Auteur,Date,Emprunteur)

-- Les identifiants de documents non empruntés
SELECT Code
FROM Document
WHERE Emprunteur IS NULL;

-- Les documents produits entre 1980 et 1990
SELECT *
FROM Document
WHERE Date >= '1980-01-01' AND Date <= '1990-01-01';

-- Documents dont le nom de l'auteur commence par un B
SELECT *
FROM Document
WHERE Auteur LIKE 'B%';

Exercices

Document( Code,Type,Description,Titre,Auteur,Date,Emprunteur)

1] Titre et date des documents empruntés par Alice.

SELECT Titre,Date
FROM Document
WHERE Emprunteur = 'Alice';

2] Titre et auteur des documents qui ne sont pas des BDs.

SELECT Titre,Auteur
FROM Document
WHERE Type <> 'BD';

UNION

Concatène des résultats de requêtes.

Exemple : caractéristiques de divers moyens de transport.

SELECT 'voiture',vitesse_max,masse
FROM Voiture
WHERE marque = 'Nissan'
  UNION
SELECT 'moto',vitesse_max,masse
FROM Moto
  UNION
SELECT 'sous-marin',vitesse_max,masse
FROM SousMarins
WHERE pays = 'Japon';

"UNION" élimine les doublons (comme "SELECT DISTINCT").
Si on veut les doublons, il faut utiliser "UNION ALL".

COUNT

Compte les lignes vérifiant un certain critère.

-- Nombre de ligne d'une table
SELECT COUNT(*)
FROM Commande;

-- Nombre de commandes effectuées avant le 9/01/2009
SELECT COUNT(*) FROM Commande WHERE Date < '2009-01-09'
-- ou
SELECT COUNT(CASE Date < '2009-01-09'
	WHEN 1 THEN 0 ELSE NULL END)
FROM Commande;

-- Nombre de commandes effectuées apres le 9/01/2009
-- dont la quantité est superieure a 5
SELECT COUNT(*)
FROM Commande
WHERE Date >= '2009-01-09' AND Quantité > 5;

MAX, MIN, SUM, ...

$f(e) = f(e(r_1), ..., e(r_n))$, où

$e$ est une expression portant sur les colonnes,
$r_k$ désigne la k^ème rangée de la table.

-- Prix maximum d'une commande
SELECT MAX(Prix * Quantité)
FROM Commande;

-- Quantité minimum commandée par Bob
SELECT MIN(Quantité)
FROM Commande
WHERE Client = 'Bob';

-- Somme des quantités commandées par Alice
SELECT SUM(Quantité)
FROM Commande
WHERE Client = 'Alice';

Exercices

Concert( ID,Groupe,Lieu,NomSalle,CapacitéSalle,NbEntrées)

1] Nombre total d'entrées réalisé par le groupe 'Rhapsody'.

SELECT SUM(NbEntrees)
FROM Concert
WHERE Groupe = 'Rhapsody'

2] Capacité moyenne des salles de Berlin ayant totalisé plus de 300 entrées au moins une fois. NB : les salles ont des capacités ≠

SELECT AVG(subQuery.CapaciteSalle)
FROM
  (SELECT DISTINCT CapacitéSalle
  FROM Concert
  WHERE Lieu = 'Berlin' AND NbEntrées >= 300) AS subQuery;

SELECT ... FROM ... WHERE ... GROUP BY ...

Commande( ID,Client,Produit,Prix,Quantité,Date)

-- Prix total pour les achats effectues le 12/10/2010
SELECT DISTINCT Client,Produit,Prix * Quantité AS prixTotal
FROM Commande WHERE Date = 'October 12, 2010';

-- Sommes des prix totaux par client,
-- pour les achats effectués le 12/10/2010
SELECT Client,SUM(Prix * Quantité) AS sommePrixTotal
FROM Commande WHERE Date = '2010-10-12'
GROUP BY Client;

-- Clients qui ont commandé quelque chose le 9/01/2009
SELECT Client
FROM Commande WHERE Date = '2009-01-09'
GROUP BY Client
HAVING SUM(Quantité) > 0;

ORDER BY ...

-- Prix total par ordre croissant
SELECT DISTINCT Client,Produit,Prix * Quantité AS prixTotal
FROM Commande WHERE Date = 'October 12, 2010'
ORDER BY prixTotal;

-- Sommes des prix totaux par client, par ordre decroissant,
-- pour les achats effectues le 12/10/2010
SELECT Client,SUM(Prix * Quantité) AS sommePrixTotal
FROM Commande WHERE Date = '2010-10-12'
GROUP BY Client
ORDER BY sommePrixTotal DESC;

-- Clients qui ont commandé quelque chose le 9/01/2009
-- Tri alphabetique puis décroissant sur les quantités
SELECT Client,Quantité
FROM Commande WHERE Date = '2009-01-09'
ORDER BY Client, Quantite DESC;

Exercices

Document( Code,Type,Description,Titre,Auteur,Date,Emprunteur)

1] Nombres de documents datant de 2004 empruntés par chaque utilisateur, rangés par ordre croissant.

SELECT Emprunteur,COUNT(*) AS nbDocs FROM Document
WHERE Date BETWEEN '2004-01-01' AND '2004-12-31';
GROUP BY Emprunteur
ORDER BY nbDocs;

2] Nombres totaux d'emprunts (si ≥ 2) par Emilie pour chaque "tranche alphabétique" de titre ("A...", "B...", etc.).

SELECT subQuery.firstLetter,COUNT(*) AS total
FROM
  (SELECT substring(Titre from 1 for 1) AS firstLetter
  FROM Document
  WHERE Emprunteur = 'Emilie') AS subQuery
GROUP BY subQuery.firstLetter HAVING COUNT(*) >= 2;

CASE WHEN ... THEN ...

Expression conditionnelle, similaire au IF/ELSE dans les autres langages

Exemple :

SELECT * FROM test;

 a
---
 1
 2
 3

SELECT a,
	CASE
    WHEN a=1 THEN 'one'
    WHEN a=2 THEN 'two'
    ELSE 'other'
  END
FROM test;

 a | case
---+-------
 1 | one
 2 | two
 3 | other

Note : peut être considéré comme un opérateur sur les attributs.