Livre_silo 30 août 2013 16:32 Page 285
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
285
11 – Base de données relationnelle
Pour chacune des recherches suivantes, on indiquera une décomposition dans l’algèbre relationnelle, ainsi
que le résultat obtenu.
1 Obtenir le nom des clients ayant séjourné dans le bâtiment Jasmin.
2 Obtenir le nom des clients ayant séjourné dans un bâtiment 3 étoiles.
3 Obtenir le nom des clients ayant séjourné dans une chambre ayant au moins 2 fenêtres.
Dans tous les cas, il faudra finir par une projection π client . On omet donc celle-ci, afin de se concentrer
sur les jointures et autres opérations.
1 L’information du bâtiment est accessible depuis la relation lit ; on effectue une jointure entre les relations
nuitee et lit, puis on sélectionne le bâtiment voulu :
σ batlit=Jasmin (nuitee [lit = idlit] lit)
On obtient les noms : McCartney, Page et Bonham.
2 Ici, il est nécessaire d’effectuer une jointure supplémentaire avec la relation batiment. Dans la mesure
où les jointures sont associatives, on peut les effectuer dans n’importe quel ordre. On omet donc les
parenthèses pour plus de clarté :
σ etoiles=3 (nuitee [lit = idlit] lit [batlit = nom] batiment)
On obtient les noms : Lennon, Starr, Harrison, Plant, Jones et Townshend.
3 Pour cette requête, on remarque tout d’abord qu’il n’existe pas de clé primaire pour la relation chambre.
Il faudra donc effectuer une jointure sur la clé {numero, batiment} à l’aide de deux conditions de recollement :
σ fenetres≥2 (nuitee [lit = idlit] lit [batlit = batiment, chambre = numero] chambre)
On obtient les noms : Lennon, Harrison, Plant, Jones et Townshend.
EN PRATIQUE La jointure dans les gestionnaires de bases de données
D’un point de vue théorique, on pourrait définir une algèbre relationnelle sans cet opérateur de jointure, puisqu’il s’exprime comme une composition d’un produit cartésien et
d’une sélection.
Concrètement, ce serait une très mauvaise idée de programmer les jointures par le biais
de ces deux autres opérations : si les relations R et R ′ contiennent respectivement n et
n ′ valeurs, le produit cartésien R × R ′ construit une relation de n × n ′ valeurs, qu’il faut
ensuite parcourir pour effectuer la sélection, d’où un coût quadratique.
Avec les tailles courantes des bases de données, un tel coût est impraticable et, de plus, la
relation R×R ′ a peu de chances de tenir dans la mémoire vive disponible. Les gestionnaires
de bases de données disposent d’algorithmes efficaces pour effectuer la jointure de deux
tables de taille n avec une complexité en O(n log n).
11.2.3 Agrégation
Le dernier concept qu’ on va présenter est assez complexe, mais très expressif. On va imaginer que l’on dispose de la relation suivante :
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
285
11 – Base de données relationnelle
Pour chacune des recherches suivantes, on indiquera une décomposition dans l’algèbre relationnelle, ainsi
que le résultat obtenu.
1 Obtenir le nom des clients ayant séjourné dans le bâtiment Jasmin.
2 Obtenir le nom des clients ayant séjourné dans un bâtiment 3 étoiles.
3 Obtenir le nom des clients ayant séjourné dans une chambre ayant au moins 2 fenêtres.
Dans tous les cas, il faudra finir par une projection π client . On omet donc celle-ci, afin de se concentrer
sur les jointures et autres opérations.
1 L’information du bâtiment est accessible depuis la relation lit ; on effectue une jointure entre les relations
nuitee et lit, puis on sélectionne le bâtiment voulu :
σ batlit=Jasmin (nuitee [lit = idlit] lit)
On obtient les noms : McCartney, Page et Bonham.
2 Ici, il est nécessaire d’effectuer une jointure supplémentaire avec la relation batiment. Dans la mesure
où les jointures sont associatives, on peut les effectuer dans n’importe quel ordre. On omet donc les
parenthèses pour plus de clarté :
σ etoiles=3 (nuitee [lit = idlit] lit [batlit = nom] batiment)
On obtient les noms : Lennon, Starr, Harrison, Plant, Jones et Townshend.
3 Pour cette requête, on remarque tout d’abord qu’il n’existe pas de clé primaire pour la relation chambre.
Il faudra donc effectuer une jointure sur la clé {numero, batiment} à l’aide de deux conditions de recollement :
σ fenetres≥2 (nuitee [lit = idlit] lit [batlit = batiment, chambre = numero] chambre)
On obtient les noms : Lennon, Harrison, Plant, Jones et Townshend.
EN PRATIQUE La jointure dans les gestionnaires de bases de données
D’un point de vue théorique, on pourrait définir une algèbre relationnelle sans cet opérateur de jointure, puisqu’il s’exprime comme une composition d’un produit cartésien et
d’une sélection.
Concrètement, ce serait une très mauvaise idée de programmer les jointures par le biais
de ces deux autres opérations : si les relations R et R ′ contiennent respectivement n et
n ′ valeurs, le produit cartésien R × R ′ construit une relation de n × n ′ valeurs, qu’il faut
ensuite parcourir pour effectuer la sélection, d’où un coût quadratique.
Avec les tailles courantes des bases de données, un tel coût est impraticable et, de plus, la
relation R×R ′ a peu de chances de tenir dans la mémoire vive disponible. Les gestionnaires
de bases de données disposent d’algorithmes efficaces pour effectuer la jointure de deux
tables de taille n avec une complexité en O(n log n).
11.2.3 Agrégation
Le dernier concept qu’ on va présenter est assez complexe, mais très expressif. On va imaginer que l’on dispose de la relation suivante :