Tutoriel pour débuter avec l’algèbre relationnelle
Bases de données
Jacques Le Maitre
Université du Sud Toulon-Var
Ce cours est mis à disposition selon les termes de la licence CreativeCommons
Paternité-Pas d'Utilisation Commerciale-Pas de Modification 2.0 France
Bibliographie
p C. J. Date, Introduction aux bases de données, Vuibert, 2001.
p P. Delmal, SQL2 - SQL3 Applications à ORACLE, De Boeck Université, 2001.
p H. Garcia-Molina, J. D. Ullman, J. Widom, Database Systems: the Complete Book, Computer Science Press, 2002.
p G. Gardarin, Bases de données, Eyrolles, 2003.
p P. M. Lewis, A. Bernstein, M. Kifer, Databases and
Transaction Processing. An Application-Oriented Approach, Addison-Wesley, 2002.
p J. Melton, A. R. Simon, SQL:1999 Understanding Relational Language Components, Morgan Kaufman Publishers, 2002.
Jacques Le Maitre BD et SGBD 2
Introduction
Qu’est ce qu’une base de données ?
p Une base de données (BD) est un ensemble d’informations archivées dans des mémoires accessibles à des ordinateurs en vue de permettre le traitement des diverses applications prévues pour elles.
p L’intérêt d’une BD est de regrouper les données communes à une application dans le but :
n d’éviter les redondances et les incohérences qu’entraînerait fatalement une approche où les données seraient réparties dans différents fichiers sans connexions entre eux,
n d’offrir des langages de haut niveau pour la définition et la manipulation des données,
n de partager les données entre plusieurs utilisateurs,
n de contrôler l’intégrité, la sécurité et la confidentialité des données, n d’assurer l’indépendance entre les données et les traitements.
p Les bases de données sont gérées par des logiciels spécialisés appelés systèmes de gestion de bases de données (SGBD).
n livre(cote: texte, titre: texte) auteur(nom: texte,
prénom: texte, année_naissance: entier) écrire(cote: texte, nom: texte)
p Extension
Schéma externe
p Un schéma externe représente la façon dont un utilisateur final ou un programme d’application voit la partie de la BD qui le concerne.
p Il existe en général plusieurs modèles externes pour une même BD.
p Le schéma conceptuel d’une BD peut être complexe : les schémas externes donnent aux utilisateurs une vision plus simple de ce schéma.
p Les schémas externes permettent aussi de protéger la BD contre des manipulations incorrectes ou non autorisées, en cachant certaines données à certains utilisateurs.
Contrôles
p Intégrité
n Les données stockées dans une BD doivent respecter un certain nombre de contraintes dites d’intégrité. Un SGBD doit assurer qu’elles sont toujours respectées.
p Confidentialité
n Un SGBD doit permettre d’interdire à certaines personnes de réaliser certaines opérations sur une partie ou sur toute la BD.
p Concurrence
n Plusieurs utilisateurs se partagent la même BD. Un SGBD doit gérer les conflits qui peuvent se produire lorsqu’ils manipulent simultanément les mêmes données de façon à ce que la BD ne soit pas mise dans un état incohérent.
p Reprise après panne
n Après une panne, qu’elle soit d’origine logicielle ou matérielle, un SGBD doit être capable de restaurer la BD dans un état cohérent, le même ou le plus proche de celui précédant la panne.
Indépendance données-traitements
p L’indépendance données-traitements est indispensable pour pouvoir faire évoluer facilement l’organisation logique ou physique d’une BD ou bien l’architecture matérielle du SGBD qui la gère.
p L’indépendance données-traitements permet si elle est atteinte :
n de modifier l’organisation physique (par exemple ajouter un index pour un accès plus rapide) sans modifier le schéma conceptuel ou les programmes d’applications,
n de modifier le schéma conceptuel (par exemple ajouter un nouveau type d’entité ou d’association) sans modifier les programmes d’applications non concernés par cet modification.
p On parle aussi d’indépendance logique et d’indépendance physique.
Qui intervient sur une BD ?
p L’administrateur (une personne ou une équipe) :
n Il définit le schéma conceptuel de la BD et le fait évoluer.
n Il fixe les paramètres de l’organisation physique de façon à optimiser les performances.
n Il gère les droits d’accès et les mécanismes de sécurité.
p Les programmeurs d’application :
n Ils définissent les schémas externes et construisent les programmes qui alimentent ou exploitent la BD en vue d’applications particulières.
n Ils utilisent pour cela le langage de bases de données du SGBD, éventuellement couplé avec un langage de programmation classique.
p Les utilisateurs finaux :
n Ils accèdent à la BD au travers des outils construits par les programmeurs d’applications ou pour les plus avertis au travers du langage de requêtes.
Modèle entité-association
Historique et objectifs
p Le modèle entité-association (EA) a été proposé par Peter Chen en 1976 sous le nom Entity-Relationship Model.
p C’est un langage graphique destiné à la construction du modèle conceptuel d’une BD, indépendamment du SGBD qui sera utilisé pour gérer celle-ci.
p Il est à la base de nombreuses méthodes de conception de BD dont la méthode Merise.
p Il est bien adapté à la conception d’une BD relationnelle car la traduction entité-association ? relationnel est relativement naturelle.
La BD Réseau de bibliothèques
p Les concepts du modèle EA seront illustrés, sur une BD décrivant un réseau de bibliothèques (universitaires, municipales, ...) et dont les données concernent :
n les bibliothèques dont chacune est identifiée par son nom,
n les exemplaires de livre dont chacun est identifié par sa cote et est conservé par une bibliothèque du réseau,
n les livres dont sont tirés ces exemplaires, dont chacun est identifié par son ISBN (numéro international),
n les personnes dont chacune est identifiée par son nom et son prénom,
n les auteurs des livres qui sont des personnes,
n les abonnés à ce réseau de bibliothèques qui sont des personnes, n les directeurs des bibliothèques de ce réseau, qui sont des personnes,
...
Entités et associations
p Le modèle EA repose sur deux concepts principaux :
n les entités du monde décrit par une BD, n les associations entre ces entités.
p Une entité est décrite par ses attributs. Par exemple, une personne décrite par son nom, son prénom, son âge et la ville dans laquelle elle habite.
p Une entité est identifiée par sa clé : les valeurs d’une partie de ses attributs. Par exemple, une personne peut être identifiée par son nom et son prénom.
p Une association exprime un lien entre plusieurs entités. Par exemple, l’emprunt d’un livre par une personne.
p Une association peut aussi avoir des attributs. Par exemple, l’emprunt d’un livre par une personne à une certaine date.
Désignation des entités et des associations
p Il est habituel de désigner un type d’entité par un substantif et une association :
n soit par un verbe, quand elle exprime une action n soit par un substantif quand elle exprime un état
p Par exemple :
n les type d’entité livre, personne, bibliothèque, ville,
n le type d’association écrire qui exprime qu’un livre a été écrit par une personne et qu’une personne a écrit un livre.
n le type d’association localisation qui exprime qu’un bibliothèque est localisée dans une ville.
Modèle relationnel
Introduction
p Proposé par E.F. Codd d’IBM en 1969, le modèle relationnel a fait l’objet d’un grand nombre de travaux de recherche qui, depuis le début des années 1980, ont débouché sur des produits commerciaux ou libres :
n DB2 d’IBM, Oracle, Sybase, Access ou SQL-Server de Microsoft, PostgreSQL, MySQL...
p Le succès du modèle relationnel est dû à :
n sa simplicité pour l’utilisateur : une BD est vue comme un ensemble de tables,
n ses fondements théoriques : l’algèbre relationnelle et la logique des prédicats.
Valeurs nulles
p Il peut arriver que certaines informations soient inconnues ou non pertinentes.
p Par exemple, une conférence dont la date n’est pas encore fixée ou bien le nombre de couleurs pour un écran noir et blanc.
p Pour représenter une telle absence d’information on utilise une valeur particulière :
n la valeur nulle que nous noterons _.
p Par exemple, le triplet :
n ("L'avenir des bases de données", "Paul Durand", _)
p peut indiquer que la date de la conférence « L’avenir des bases de données » donnée par Paul Durand, n’est pas encore connue.
Les faits (1)
p On veut représenter les faits suivants :
n Le nom, l’altitude, l’année de la 1ère ascension de chaque sommet et l’orientation de la face (ou de l’arête) empruntée. Un sommet est identifié par son nom.
n La localisation d’un sommet, c’est à dire le nom du ou des pays dans lequel il se trouve. Un sommet peut se trouver dans plusieurs pays quand il appartient à la frontière de chacun de ces pays.
n Le nom, le prénom et le pays de chaque grimpeur ayant réalisé la 1ère ascension d’un sommet de plus 8000 m. Un grimpeur est identifié par son nom et son prénom.
n Le nom et le prénom du grimpeur et le nom du sommet gravi pour chaque 1èreascension.
Clés
p Relation gravir(nom_grimpeur, prénom_grimpeur, nom_sommet) :
n plusieurs grimpeurs peuvent avoir réalisé la 1ère ascension d’un sommet : le constituant {nom_grimpeur, prénom_grimpeur, nom_sommet} est donc la clé primaire.
n un grimpeur ayant réalisé une ascension doit être décrit dans la relation grimpeur : le constituant {nom_grimpeur, prénom_grimpeur} est donc une clé étrangère qui réfère le constituant {nom, prénom} de la relation grimpeur.
n un sommet sur lequel a été réalisé une ascension doit être décrit dans la relation sommet : l’attribut nom_sommet est donc une clé étrangère qui réfère l’attribut nom de la relation sommet.
Vision tabulaire
|
| |||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||
|
Vision prédicative
p L’extension de la relation sommet est formée de l’ensemble des quadruplets (x, y, z, t) exprimant le fait qu’il y a un sommet de nom x, d’altitude y dont la 1ère ascension a été réalisée l’année z par la face t.
p L’extension de la relation localisation est formée de l’ensemble des doublets (x, y) exprimant le fait que le sommet de nom x se trouve dans le pays de nom y.
p L’extension de la relation grimpeur est formée de l’ensemble des triplets (x, y, z) exprimant le fait qu’il y a un grimpeur de nom x, de prénom y et de pays z.
p L’extension de la relation ascension est formée de l’ensemble des triplets (x, y, z) exprimant le fait que le grimpeur de nom x et de prénom y a réalisé la 1ère ascension du sommet z.
Du modèle entité-association au modèle relationnel
Traduction d’un type d’association (1)
p Un type d’association :
n A(E1, ... En ; attributs)
est traduit en une relation de schéma :
n A(clé(E1), ..., clé(En), attributs) où clé(E1), ..., clé(E1) sont des clés étrangères.
p Dans le cas particulier où les cardinalités maximum associées aux types d’entité E1, ..., En-1 sont égales à 1, la traduction peut consister à leur ajouter la clé de la relation En, qui est alors une clé étrangère référant la relation En.
p Les cardinalités minimales différentes de 0 et les cardinalités maximales différentes de * devront être exprimées sous forme de contraintes d'intégrité de type assertion.
p Afin d’éviter les collisions de noms dues à l’importation des clés, on pourra préfixer les noms des attributs constituant ces clés :
n soit par le nom de l’entité d’où ils proviennent,
n soit par le nom du rôle que joue cette entité, s’il est spécifié.
Algèbre relationnelle
Objectifs
p L'algèbre relationnelle fournit les opérateurs de base pour manipuler les extensions des relations (ensembles de n-uplets ou tables) d'une BD relationnelle.
p On peut faire un parallèle avec l'arithmétique qui fournit les opérations de base pour manipuler les nombres (addition, soustraction, multiplication et division).
p Tout SGBD relationnel se doit de fournir des implantations efficaces de ces opérateurs implantation de ces opérateurs.
p Une requête SQL est traduite, comme on le verra, en un arbre d'opérateurs de l'algèbre relationnelle.
Jointure externe (1)
p L’opérateur de jointure externe permet d’ajouter au résultat d’une jointure interne, les n-uplets de l’une, de l’autre ou des deux relations qui ne peuvent pas être joints.
p Soit P et Q les relations à joindre, on distingue :
n la jointure externe totale (ejoin) qui ajoute les n-uplets de P et de Q qui ne peuvent pas être joints,
n la jointure externe gauche (lejoin) qui n’ajoute que les n-uplets de P qui ne se joignent pas avec un n-uplet de Q,
n la jointure externe droite (rejoin) qui n’ajoute que les n-uplets de Q qui ne se joignent pas avec un n-uplet de P.
p Les n-uplets ainsi rajoutés sont complétés par des valeurs nulles pour les attributs qu’ils ne possèdent pas.
1 m
n schéma(q) = (B1, …, Bn)
n {A1, …, Am} ? { B1, …, Bn} = ?
p L’opérateur ejoin est défini par :
n schéma(pejoincondq) = (A1, …, Am, B1, …, Bn)
n ext(pejoincondq) = pext ? j ? qext où :
p j = pjoincondq
p pext = (p ? ?A1, …, Am(j)) ? {(nul, …, nul)})
p qext = {(nul, …, nul)} ? (q ? ?B1, …, Bn(j))
Jointure naturelle (1)
p Dans une jointure qu’elle soit interne ou externe, on peut omettre la condition lorsqu’elle se restreint à ce que les attributs de même nom de chacune des relations à joindre, doivent avoir la même valeur :
n on appelle jointure naturelle ce cas particulier de jointure.
p La jointure naturelle sera notée en omettant la condition sous l’opérateur de jointure considéré.
p Dans la relation produite, les attributs communs aux deux relations n’apparaîtront qu’une seule fois.
p Si les deux relations à joindre n’ont pas d’attributs communs, alors la jointure naturelle est équivalente au produit cartésien.
Requêtes en algèbre relationnelle (2)
p Prénom et nom des grimpeurs ayant réalisé la 1ère ascension d’un sommet sommets de plus de 8000 m du Népal ?
n asn := ascension join ?pays = "Népal"(localisation); réponse := ?prénom_grimpeur, nom_grimpeur(asn);
p Nom des sommets de plus de 8000 m qui ne sont pas au Népal ?
(on sélectionne les noms des sommets qui ne joignent pas avec les sommets du
Népal)
n nsn := ?nom_sommet(?pays = "Népal"(localisation))
réponse := ?nom(?nom_sommet = nul(sommet ejoinnom = nom_sommet nsn));
p Nom des sommets de plus de 8500 mètres situés au Népal mais pas sur la frontière chinoise ?
n ns := ?nom_sommet(?nom(?altitude > 8500(sommet))); nsn := ?nom_sommet(?pays = "Népal"(localisation)); nsc := ?nom_sommet(?pays = "Chine"(localisation)); réponse := ns ? nsn ? nsc;
?nom ?nom_sommet ?nom_sommet
?altitude > 8500 ?pays = "Népal" ?pays = "Chine"
sommet localisation localisation
Nom des sommets de plus de 8500 mètres situés au Népal mais pas sur la frontière chinoise ?
SQL
Introduction
p Le langage SQL est la version commercialisée du langage SEQUEL du prototype System R développé à IBM San José à partir de 1975.
p Il a depuis fait l’objet de plusieurs normes dont la plus récente est SQL-1992, qui est implantée plus ou moins complètement par tous les SGBD relationnels actuellement disponibles.
p Une nouvelle norme SQL:1999 a vu le jour, qui concerne les SGBD objets-relationnels.
p Le langage décrit dans ce chapitre est conforme à la norme SQL-1992.
Jointure et utilisation de synonymes
p Q6a. Donner pour chaque 1ère ascension d’un sommet de plus de 8500 m le nom du grimpeur, le nom du sommet et son altitude ?
n SELECT ascension.nom_grimpeur, , sommet.altitude
FROM ascension, sommet
WHERE ascension.nom_sommet = AND sommet.altitude > 8500;
p Q6b. Idem en désignant les tables ascension et sommet par les synonymes a et s ?
n SELECT a.nom_grimpeur, s.nom, s.altitude
FROM ascension a, sommet s
WHERE a.nom_sommet = s.nom AND s.altitude > 8500;
p Q6c. Idem sans qualifier les attributs car il n’y a pas d’ambiguïté sur leur table de provenance ?
n SELECT nom_grimpeur, nom, altitude
FROM ascension, sommet
WHERE nom_sommet = nom AND altitude > 8500;
Opérateurs de jointure dans la clause FROM
p Q26. Donner le prénom, le nom et le nom du sommet pour chaque grimpeur ayant réalisé la 1ère ascension d'un sommet de plus de 8000 m de l’Inde ?
n SELECT prénom_grimpeur, nom_grimpeur, nom_sommet
FROM ascension NATURAL INNER JOIN localisation WHERE pays = 'Inde';
p Q27. Parmi tous les grimpeurs ayant réalisé la 1ère ascension d'un sommet de plus de 8000 m, donner le pourcentage de ceux qui l'ont fait sur un sommet du Népal ?
n SELECT (CAST(COUNT(pays) AS FLOAT) / COUNT(*)) * 100
FROM (SELECT *
FROM ascension) AS a
NATURAL LEFT OUTER JOIN
(SELECT *
FROM localisation
WHERE pays = 'Népal') AS l;
Manipulation des valeurs nulles (1)
p Les comparateurs IS NULL et IS NOT NULL permettent de tester si une valeur est nulle :
n e IS NULL a la valeur TRUE si e a la valeur NULL, elle a la valeur FALSE sinon,
n e IS NOT NULL a la valeur Vrai si e a la valeur NULL, elle a la valeur FALSE sinon.
p Si l’un des opérandes d’un opérateur a la valeur NULL, le résultat de l’opération est la valeur NULL.
p Pour traiter les comparateurs (autres que IS NULL et IS NOT NULL) et les connecteurs logiques, on introduit une troisième valeur de vérité : UNKNOWN, en plus des valeurs TRUE et FALSE.
n La comparaison entre la valeur NULL et toute autre valeur y compris NULL a pour valeur UNKNOWN.
n On redéfinit les tables de vérité des trois connecteurs logiques en tenant compte de cette 3e valeur de vérité.
Tables de vérité à 3 valeurs des connecteurs logiques
AND T F U OR T F U NOT
T
F
U
Manipulation des valeurs nulles (3)
p Supposons que la relation sommet ait l’extension suivante :
sommet | |||
nom | altitude | année | face |
Everest K2 | 8848 8611 | _ 1954 | N SE |
p La requête :
n SELECT COUNT(*)
FROM sommet WHERE année < 1950 retourne le n-uplet (0). p La requête :
n SELECT nom
FROM sommet
WHERE année IS NULL; retourne le n-uplet ('Everest'). p La requête :
n SELECT nom
n FROM sommet n WHERE année IS NOT NULL; retourne le n-uplet ('K2').
Déclencheurs (2)
p Un déclencheur est activé par une requête de mise à jour.
p Pour définir un déclencheur, il faut :
n spécifier l’événement qui déclenche l’action en indiquant le type de la mise à jour (INSERT, UPDATE, DELETE), le nom de la relation et éventuellement le nom des attributs mis à jour ;
n indiquer si l’action est réalisée avant, après ou à la place de la mise à jour ;
n donner un nom à l’ancien et au nouveau n-uplet (uniquement le nouveau en cas d’insertion et uniquement l’ancien en cas de suppression) ;
n décrire la condition sous laquelle se déclenche l’événement sous la forme d’une expression SQL booléenne, c.-à-d. une expression pouvant être placée dans une clause WHERE ;
n décrire l’action à réaliser sous la forme d’une procédure SQL ;
n indiquer si l’action est réalisée pour chaque n-uplet mis à jour ou une seule fois pour la requête.
Confidentialité
p Une BD doit être protégée des accès malveillants.
p La solution adoptée classiquement consiste à n’autoriser un utilisateur à effectuer une opération sur un objet que s’il en a obtenu le droit (ou le privilège).
p L’identification des utilisateurs se fait en général par leur nom et par un mot de passe. Des procédés plus sophistiqués peuvent être utilisés comme les cartes à puce ou la reconnaissance des empreintes digitales ou rétiniennes.
p Dans un SGBD relationnel :
n les objets à protéger sont les tables et les vues,
n les opérations sont SELECT, INSERT, UPDATE ou DELETE.
p L’attribution des droits peut être :
n centralisé : l’administrateur a tous les droits sur tous les objets de la BD et peut transmettre certains de ces droits à d’autres utilisateurs.
n décentralisée : l’utilisateur qui crée un objet a tous les droits sur cet objet et peut les transmettre en totalité ou en partie à d’autres utilisateurs.
Protection par les vues
p Les vues jouent un rôle important pour la confidentialité en permettant de spécifier de façon très fine les données auxquels un utilisateur a le droit d’accéder.
p On pourra spécifier un accès à l’affectation des employés dans les départements en définissant la vue suivante :
n CREATE VIEW affectation(nom_emp, nom_dept) AS
SELECT e.nom_emp, d.nom_dept
FROM employe AS e, departement AS d
WHERE e.nom_dept = d.nom_dept;
p Un utilisateur dont les droits d’accès se limitent à la vue affectation ne pourra connaître ni le numéro et le salaire d’un employé, ni le numéro et le directeur d’un département.
Intégration de SQL dans un programme (1)
p Les principes sont les suivants :
p Chaque instruction SQL est préfixée par EXEC SQL.
p Ces instructions peuvent contenir des variables du programme qui :
n sont préfixées par :
n doivent avoir un type compatible avec les valeurs d’attributs qui leur seront affectées.
p Un mécanisme de curseur permet de parcourir une table ligne par ligne et d’affecter les valeurs de chaque ligne à des variables du programme.
p Le programme doit posséder une variable numérique SQLCODE dont la valeur résume l’exécution, correcte ou incorrecte, d’une instruction SQL.
Normalisation
Propriétés des dépendances fonctionnelles (2)
p Étant donné un ensemble de dépendances fonctionnelles F construit sur l’ensemble R des attributs d’une relation, l’ensemble F+ (fermeture de F) de toutes les dépendances fonctionnelles logiquement impliquées par F peut être calculé à partir des trois règles suivantes (axiomes d’Armstrong) :
n (réflexivité) si Y ? X ? R alors X ? Y
n (augmentation) si X ? Y et Z ? R alors X ? Z ? Y ? Z
n (transitivité) si X ? Y et Y ? Z alors X ? Z
p Des axiomes d’Armstrong on peut déduire deux règles plus pratiques pour calculer F+ :
n (union) si X ? Y et X ? Z alors X ? Y ? Z.
n (décomposition) si X ? Y ? Z alors X ? Y et X ? Z.
Insuffisance de la 2e forme normale
| |||||||
isbn | titre | éditeur | pays | ||||
2-212-09283-0 | Bases de données … | Eyrolles | France | ||||
2-7117-8645-5 | Fondements des … | Vuibert | USA | ||||
2-212-0969-2 | Internet/Intranet … | Eyrolles | France | ||||
Il reste des redondances : (…, Eyrolles, France).
Forme normale de Boyce-Codd (1)
p Une relation R est en forme normale de Boyce-Codd (FNBC) si pour chaque dépendance fonctionnelle non triviale X ? Y, X est une super-clé de R.
p La forme normale de Boyce-Codd implique la 3e forme normale.
p La forme normale de Boyce Codd est la forme idéale relativement aux dépendances fonctionnelles, mais malheureusement elle peut ne pas préserver les dépendances fonctionnelles.
4e forme normale (1)
p Une dépendance multivaluée X ?? Y d’une relation R est dite non triviale si :
n Y n’est pas un sous-ensemble de X,
n X ? Y n’inclut pas tous les attributs de R.
p Une relation R est en 4e forme normale, si pour chaque dépendance multivaluée X ?? Y non triviale, X est une super-clé de R.
p La 4e forme normale implique la forme normale de BoyceCodd puisqu’une dépendance fonctionnelle est un cas particulier de dépendance multivaluée.
Organisation physique
Une organisation physique simple
p Soit la BD relationnelle :
n livre(titre, auteur) n personne(nom, prénom, âge)
p La relation livre est stockée dans un fichier dont chaque enregistrement représente un doublet de la relation livre et a 2 champs : les valeurs des attributs titre et auteur de ce triplet.
p La relation personne est stockée dans un fichier dont chaque enregistrement représente un triplet de la relation personne et a 3 champs : les valeurs des attributs nom, prénom et âge de ce triplet.
p Deux métarelations décrivant les relations de la BD et leurs attributs :
n relation(nom, nb_att)
n attribut(nom_table, nom, type, rang) sont elles-même stockées dans les fichiers et .
Objectifs d'une bonne organisation physique
p Une BD relationnelle est constituée d’un ensemble de relations qui ont chacune une extension qui est un ensemble de n-uplets.
p Physiquement ces n-uplets sont stockés dans un ou plusieurs fichiers qui peuvent être répartis sur un ou plusieurs sites (dans le cas de BD distribuées).
p Le format de stockage choisi doit permettre :
n une utilisation optimale de la mémoire,
n un accès rapide et des mises à jour peu coûteuses.
p Afin d’accéder le plus rapidement possible à un ensemble de n-uplets vérifiant certaines conditions, une BD relationnelle doit être munie d’index qui permettent d’associer chaque valeur d’un constituant à l’ensemble des n-uplets qui possèdent cette valeur pour ce constituant.
Evolution de la taille des n-uplets
p Si la longueur d’un n-uplet augmente de k octets, deux cas sont possibles :
n s’il reste suffisamment de place dans la page, on décale les n-uplets qui le suivent de k octets vers la droite, puis on change leur adresse logique dans le répertoire ;
n sinon, on change le n-uplet de page et on met en place un pointeur de suivi.
p Si la longueur d’un n-uplet diminue de k octets, on décale les n-uplets qui le suivent de k octets vers la gauche, puis on change leur adresse logique dans le répertoire.
Recherche d’une page
p L’opération de recherche d’une page :
n a pour argument l’adresse p de la page cherchée,
n retourne l’adresse c de la case du tampon dans laquelle cette page est rangée.
p L’algorithme est le suivant :
n Si la page p est dans la case c du tampon, retourner c. On économise un accès disque.
n Si la page p n’est pas dans le tampon, il faut la lire sur le disque. On teste s’il existe une case libre pour la recevoir. Si oui, soit c cette case.
n Sinon, il faut libérer une case et donc renvoyer une page du tampon sur le disque. Plusieurs stratégies sont possibles.
n Si la page à rejeter a été modifiée pendant son séjour en mémoire centrale, il faut la réécrire sur le disque. Ce travail est pris en compte par le gestionnaire de transactions.
n Transférer la page p du disque dans la case c et retourner c.
Stratégies de remplacement de page
p FIFO (First-In First-Out)
n On renvoie sur disque la page qui n’a pas été utilisée depuis le plus longtemps. Cette stratégie repose sur l’hypothèse que cette pages a moins de chances d’être réutilisée que les autres.
p LIFO (Last-In First-Out)
n On renvoie sur disque la page qui a été utilisée le plus récemment. L’intérêt de cette stratégie est sa simplicité, car n’y a pas besoin de mémoriser les dates auxquelles les pages ont été chargées dans le tampon.
p Sous contrôle du SGBD
n Le SGBD peut punaiser (« to pin ») des pages dans la mémoire tampon, afin qu’elles ne soient pas renvoyées sur disque, car il sait qu’elles vont être réutilisées.
Exemple : la table sur laquelle sera construit l’index
Chaque mécanisme d’accès sera illustré par la construction de l’index primaire, que nous appellerons dico, de la relation suivante :
dictionnaire | |
mot | définition |
mélodie | Suite de sons formant un air... |
école | Etablissement où se donne un enseignement collectif… |
nez | Partie saillante du visage... |
bateau | Nom des embarcations, des navires... |
kayak | Embarcation étanche et légère... |
zébu | Bœuf à longues cornes et à bosse sur le garrot… |
dessin | Représentation sur une surface de la forme d’un objet... |
corde | Assemblage de fils tressés ou tordus ensemble… |
terre | Planète habitée par l’homme… |
Fonction de hachage
p La fonction de hachage s’applique à une clé, que nous supposerons être une chaîne de caractères, et à un nombre entier N. Elle retourne un nombre entier compris entre 0 et N - 1.
p Il n’est en général pas possible général de construire une fonction de hachage injective, c’est à dire, telle que :
n c1 ? c2 ? h(c1) ? h(c2)
p On construit donc une fonction qui minimise le nombre de collisions et les répartit uniformément.
p Les deux techniques les plus utilisées sont la division et le pliage.
p Dans les deux cas, on construit à partir des codes des caractères de la clé c, un nombre k grand devant N. La valeur de h(c) est alors calculée comme suit :
n Division. h(c) est le reste de la division de k par N. Il est montré que l’on a intérêt à choisir N premier.
n Pliage. On découpe la représentation binaire de k en tranches de b bits. h(c) est égal au « ou exclusif » des nombres binaires ainsi obtenus.
h(c) = (somme des codes ASCII des caractères de c) modulo 5.
Performances
p Sans répertoire et avec un bon ajustement des valeurs de N et du nombre d’enregistrements par page, on peut accéder à un enregistrement en 1,1 ou 1,2 accès disque en moyenne.
p On peut obtenir la même performance avec un répertoire pourvu que celui-ci tienne en mémoire centrale.
p Le répertoire permet de ne pas associer inutilement une page à un code-haché non instancié (2 dans notre exemple). Par contre, un répertoire occupe de la place et s’il ne tient pas en mémoire centrale le nombre d’accès disque sera augmenté.
p Le hachage statique est mal adapté à un fichier de données très évolutif car la taille du répertoire peut s’avérer sous-évaluée, entraînant un accroissement du nombre de pages de débordement et donc du nombre d’accès disque.
p Pour y pallier, des méthodes de hachage dites dynamiques ont été proposées, qui font évoluer la fonction de hachage en fonction du nombre d’enregistrements.
Hachage extensible
p Une suite de bits est associée à chaque clé.
p L’évolution de la clé de hachage consiste à augmenter le nombre de bits à prendre en compte dans une clé pour trouver la case du répertoire qui pointe vers la page contenant l’enregistrement associé à cette clé.
n si tous les enregistrements tiennent dans une seule page, 0 bits seront à prendre en compte,
n s’ils occupent 2 pages, 1 bit sera à prendre en compte, n s’ils occupent 3 ou 4 pages, 2 bits seront à prendre en compte,
...
Organisation
p La fonction de hachage h associe à chaque clé une séquence suffisamment longue de bits (32, par exemple).
p L’index est composé de deux parties :
n un ensemble de pages.
n un répertoire de 2n cases (n ? 0, profondeur du répertoire) dont chacune contient un pointeur vers une page.
p Plusieurs cases consécutives du répertoire peuvent pointer vers la même page.
p Un enregistrement de clé c est stocké dans la page pointée par la ie case du répertoire telle que i est égal au nombre formé par les n premiers bits de h(c).
p A chaque page est associé un nombre entier m (0 ? m ? n), appelée profondeur de la page.
p Si une page a la profondeur m, alors il y a 2n-m cases du répertoire qui pointent vers elle.
Construction de l’index dico (1)
Insertions successives des enregistrements : mélodie, école, nez
|
Construction de l’index dico (2)
Insertion de l’enregistrement : bateau
|
Construction de l’index dico (5)
Insertions successives des enregistrements : corde, terre
|
Résolution des requêtes
Les 3 phases de la résolution d’une requête
p La résolution d’une requête à une BD relationnelle se déroule en trois phases :
1. Traduction de la requête en un arbre d’opérateurs relationnels (sélection, jointure, projection, etc.) : l'arbre de requête.
2. Optimisation. Il s’agit de déterminer un plan d’exécution de coût minimal. Deux procédures sont principalement mises en œuvre :
p transformation de l’arbre de requête en un arbre équivalent, basée sur les propriétés d’associativité et de commutativité de l’algèbre relationnelle ;
p évaluation du coût de résolution de chaque opérateur.
3. Évaluation du plan d’exécution produit par la phase 2.
Étude de quelques méthodes
p On supposera que chaque relation est stockée dans un fichier qui contient les n-uplets de cette relation.
p Le coût d’une opération sera mesuré en nombre de transferts de pages entre disque et mémoire centrale.
p Ce coût peut se décomposer en deux parties :
n un coût de production de la relation résultat, n un coût d’écriture de cette relation.
p Le coût de production dépend de la méthode choisie pour réaliser l’opération alors que le coût d’écriture en est indépendant.
p Dans le cas d’une évaluation pipeline d’une suite d’opérations : op1, ..., opn
les résultats des opérations op1, ..., opn-1 ne sont pas stockés sur disque car les n-uplets produits sont directement transmis à l’opérateur suivant :
n les coûts de lecture d’une relation opérande ou d’écriture des résultats d’un opérateur peuvent donc être nuls.
Jointure par boucles imbriquées (1)
J := P joincondQ
Tampon
|
|
|
case 1 case M case M+1case M+2
Algorithme
pour chaque suite de M blocs de Pfaire Transférer les pages contenues dans ces blocs dans les cases 1 à M. pour chaque chaque bloc de Qfaire Transférer la page contenue dans ce bloc dans la case M + 1. pour chaque n-uplet t’ de cette page fairepour chaque page contenue dans les cases 1 à M |