Cours2.pdf

Base de données et interopérabilité Département Informatique École supérieure d'ingénieurs Léonard-de-Vinci (ESILV) 19 Février, 2023 Ruiwen HE 2 B D D & i n t e r o p é r a b i l i t é [email protected] Plan Les vues SQL sequence L'index LES VUES PÔLE LÉ ONARD DE VINCI [email protected] i n t...

Base de données et interopérabilité Département Informatique École supérieure d'ingénieurs Léonard-de-Vinci (ESILV) 19 Février, 2023 Ruiwen HE 2 B D D & i n t e r o p é r a b i l i t é [email protected] Plan Les vues SQL sequence L'index LES VUES PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 4 Les vues Une vue fournit un mécanisme permettant de masquer certaines données à la vue de certains utilisateurs. Les vues en deux mots : des tables virtuelles Prenons l'exemple d'une personne qui a besoin de connaître le nom et le numéro d’étudiant d'un élève, pas l’anniversaire. Cette personne devrait voir une relation décrite, en SQL, par SELECT sid, sname FROM student [email protected] i n t e r o p é r a b i l i t é & B D D 5 Les raisons d’utiliser des vues Simplifier le code, nous pouvons encapsuler des requêtes réutilisables dans des vues et les réutiliser, tout en rendant les requêtes complexes faciles à comprendre ; Sécurité, par exemple, si une table contient beaucoup de données et d'informations que vous ne voulez pas que d'autres personnes voient, vous pouvez utiliser des vues et utiliser des vues différentes pour différents utilisateurs. [email protected] i n t e r o p é r a b i l i t é & B D D 6 Les vues Une vue est définie à l'aide de l'instruction CREATE VIEW qui se présente sous la forme suivante CREATE VIEW view_name AS < expression de la requête > où est une expression SQL légale. Le nom de la vue est représenté par view_name. Une fois qu'une vue est définie, le nom de la vue peut être utilisé pour faire référence à la relation virtuelle que la vue génère. La définition d'une vue ne revient pas à créer une nouvelle relation en évaluant l'expression de la requête La définition d'une vue entraîne plutôt l'enregistrement d'une expression ; l'expression est substituée dans les requêtes utilisant la vue. [email protected] i n t e r o p é r a b i l i t é & B D D 7 Example Views Une vue de l'élève sans sa date d'anniversaire CREATE VIEW list_attendence AS SELECTsid, sname FROM student; Créez une vue du score moyen pour chaque cours : CREATE VIEW list_score AS SELECT cid, AVG (score) FROM sc GROUP BY cid; [email protected] i n t e r o p é r a b i l i t é & B D D 8 Vues définies à l'aide d'autres vues CREATE VIEW note AS SELECT sc.sid, student.sname, course.cname,sc.score FROM course, student, sc WHERE course. cid = sc.cid AND sc. sid = student.sid ; SELECT * FROM note; [email protected] i n t e r o p é r a b i l i t é & B D D 9 Vues définies à l'aide d'autres vues CREATE VIEW note_cv AS SELECT sid, sname, score FROM note WHERE cname ='Computer vision'; SELECT * FROM note _cv; [email protected] i n t e r o p é r a b i l i t é & B D D 10 Vues définies à l'aide d'autres vues CREATE VIEW ViewPractice1_5 AS SELECT sid, sname, score FROM note WHERE cname ='Computer vision'; SELECT * FROM note _cv; SELECT AVG SELECT sid, COUNT (cid) FROM sc WHERE COUNT (cid)=3 GROUP BY sid; [email protected] i n t e r o p é r a b i l i t é & B D D 11 Jointure entre les vues CREATE VIEW avgnote AS SELECT sid, AVG(score) AS ss FROM sc GROUP BY sid; CREATE VIEW avgnote_full AS SELECT * FROM (SELECT * FROM list_attendence ) AS v1 NATURAL JOIN (SELECT * FROM avgnote) AS v2 ON v1.sid=v2.sid; CREATE VIEW avgnote_course AS SELECT * FROM list_score NATURAL JOIN [email protected] B D D & i n t e r o p é r a b i l i t é Jointure entre vue et table 12 Course NATURAL JOIN teacher [email protected] i n t e r o p é r a b i l i t é & B D D 13 Mise à jour d'une vue Ajouter un nouveau tuple à la vue de la faculté que nous avons définie plus tôt INSERT INTO list_attendence VALUES ('15', 'Anna'); [email protected] i n t e r o p é r a b i l i t é & B D D 14 Certaines mises à jour ne peuvent pas être effectués CREATE VIEW note_cv AS Ajouter un nouveau tuple à la vue de la faculté que nous avons définie plus tôt INSERT INTO note_cv VALUES ('15', 'Anna', '16'); Can not modify more than one base table through a join view Parce qu'il n'est pas possible de modifier simultanément deux tables sur une vue qui est reliée à plusieurs tables connexes ; SELECT sid, sname, score FROM note WHERE cname ='Computer vision'; SELECT * FROM note _cv; [email protected] i n t e r o p é r a b i l i t é & B D D 15 Certaines mises à jour ne peuvent pas être effectués La plupart des implémentations SQL n'autorisent les mises à jour que sur des vues simples (vues actualisables). La clause FROM ne contient qu'une seule relation de base de données. La clause select ne contient que les noms des attributs de la relation, et ne contient aucune expression, agrégat ou spécification distincte. Tout attribut non répertorié dans la clause select peut être défini comme nul. La requête ne comporte pas de clause "GROUP BY" ou "HAVING". [email protected] i n t e r o p é r a b i l i t é & B D D 16 Suppression d’une vue DROP VIEW nom-de-vue La suppression d’une vue n’entraîne pas la suppression des données 17 B D D & i n t e r o p é r a b i l i t é [email protected] Renommer une vue RENAME ancien-nom TO nouveau-nom [email protected] * Vue et indépendance des données logiques Si la relation S(a, b, c) est divisée en deux sous-relations S1(a,b) et S2(a,c). Comment réaliser l'indépendance logique des données ? CREATE TABLE S2 …; 2) INSERT INTO S1 SELECT a, b FROM S; INSERT INTO S2 SELECT a, c FROM S; & 3) DROP TABLE S; 4) CREATE VIEW S(a,b,c) AS SELECT a,b,c FROM S1 NATURAL JOIN S2; B D D i n t e r o p é r a b i l i t é 1) CREATE TABLE S1 …; SELECT * FROM S WHERE … → SELECT * FROM S1 NATURAL JOIN S2 WHERE … INSERT INTO S VALUES (1 ,2,3) → INSERT INTO S1 VALUES (1, 2); INSERT INTO S2 VALUES (1 ,3); 18 Vues vs Tables B D D & i n t e r o p é r a b i l i t é View il s'agit d'une table virtuelle qui n'occupe pas d'espace de stockage La vue est dynamique. 19 SQL SEQUENCE PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é SEQUENCE 21 Dans MySQL, une séquence est un objet qui s'auto-incrémente en une séquence de nombres, un ensemble d'entiers 1, 2, 3,... En effet, une table de données ne peut avoir qu'un seul champ à clé primaire auto-incrémentée. Bien que MySQL ne dispose pas d'un type de séquence intégré, vous pouvez simuler le comportement d'une séquence en utilisant l'attribut AUTO_INCREMENT, qui est généralement utilisé pour spécifier la nature auto-incrémentale d'une colonne dans une table. [email protected] i n t e r o p é r a b i l i t é & B D D 22 Utilisation de AUTO_INCREMENT CREATE TABLE roman ( id INT UNSIGNED NOT NULL AUTO_INCREMENT, PRIMARY KEY (id), book_name VARCHAR(30) NOT NULL, date_loue DATE NOT NULL, date_rendu VARCHAR(30) ); [email protected] i n t e r o p é r a b i l i t é & B D D 23 Utilisation de AUTO_INCREMENT INSERT INTO roman (id, book_name , date_loue , date_rendu) VALUES (NULL,'La vie heureuse', '2001-09-10', '2001-09-17'), (NULL,'Un soir d’ete','2001-05-30', '2001-10-07'), (NULL,'Le diplome','2001-09-01', NULL); [email protected] i n t e r o p é r a b i l i t é & B D D 24 Définir la valeur de départ de la séquence Récupérer la valeur AUTO_INCREMENT SELECT LAST_INSERT_ID(); ALTER TABLE roman AUTO_INCREMENT = 4; [email protected] i n t e r o p é r a b i l i t é & B D D 25 Réinitialisation de séquence Si vous supprimez plusieurs enregistrements d'une table de données et que vous souhaitez réorganiser les colonnes AUTO_INCREMENT pour les données restantes, vous pouvez le faire en supprimant les colonnes autoincrémentées et en les ajoutant à nouveau. Toutefois, cette opération doit être effectuée avec beaucoup de précautions, car si la suppression s'accompagne de l'ajout de nouveaux enregistrements, il y a un risque de confusion des données. ALTER TABLE roman DROP id; ALTER TABLE roman ADD id INT UNSIGNED NOT NULL AUTO_INCREMENT FIRST, ADD PRIMARY KEY (id); 26 B D D & i n t e r o p é r a b i l i t é [email protected] Réinitialisation de séquence L'INDEX PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é INDEX 28 Un index est un type particulier de table de recherche qui peut être utilisé par les moteurs de recherche de bases de données pour accélérer la récupération des données. En termes simples, un index est un pointeur vers les données d'une table. L'index d'une base de données est très similaire à l'index figurant à la fin d'un livre. Par exemple, si vous voulez voir toutes les pages d'un livre relatives à un sujet particulier, vous devez d'abord interroger l'index (qui répertorie tous les sujets par ordre alphabétique), puis trouver une ou plusieurs pages de l'index relatives à ce sujet, puis effectuer une recherche dans l'index pour trouver une ou plusieurs pages relatives à ce sujet, et enfin trouver une ou plusieurs pages relatives à ce sujet. [email protected] i n t e r o p é r a b i l i t é & B D D 29 Index Dans un index ordonné, les entrées de l'index sont stockées en fonction de la valeur de la clé de recherche. Par exemple, le catalogue des auteurs dans une bibliothèque. Index primaire : dans un fichier ordonné séquentiellement, l'index dont la clé de recherche spécifie l'ordre séquentiel du fichier.Également appelé index de regroupement.La clé de recherche d'un index primaire est généralement, mais pas nécessairement, la clé primaire. Index secondaire : un index dont la clé de recherche spécifie un ordre différent de l'ordre séquentiel du fichier. Également appelé index non groupé. 30 B D D & i n t e r o p é r a b i l i t é [email protected] Index primaire 31 B D D & i n t e r o p é r a b i l i t é [email protected] Index secondaire B D D & i n t e r o p é r a b i l i t é Structures d’index 32 En l’absence d’un index, seule solution : le parcours séquentiel du fichier. Avec un index : accès direct à l’enregistrement, amélioration très importante des temps de réponse [email protected] Une clé (d’indexation) est une liste (l’ordre est important) d’attributs d’une table. En toute rigueur, il faudrait toujours distinguer la clé (les noms d’attributs) de la valeur de la clé (celles que l’on trouve dans un enregistrement). On se passera de la distinction quand elle est claire par le contexte. Une adresse est un emplacement physique dans la base de données, qui peut être soit celle d’un bloc, soit un peu plus précisément celle d’un enregistrement dans un bloc. Reportez-vous au chapitre sur la stockage qui détaille comment est construite l’adresse d’un enregistrement. B D D & i n t e r o p é r a b i l i t é Quelques définitions Une entrée (d’index) est un enregistrement constitué d’une paire de valeurs. La première est la valeur de la clé, la seconde une adresse. Un index est un fichier structuré dont les enregistrements sont des entrées. 33 [email protected] i n t e r o p é r a b i l i t é & B D D 34 Exemple: une table des films La table des films, avec : 1 000 000 (un million) de films Un enregistrement = 1200 octets Un bloc = 4K => 3 enregistrements par bloc environ 300 000 blocs, 1,2 Go [email protected] i n t e r o p é r a b i l i t é & B D D 35 Index = concept bien connu Prenons un livre à contenu technique (pas une fiction !), par exemple un livre de recettes. Il contient (au moins) un index. L’index présente les termes importants, classés par ordre alphabétique À chaque terme sont associés les numéros de page où on trouve le terme. En parcourant l’index (par dichotomie !) on trouve la ou les pages qui nous intéressent. [email protected] i n t e r o p é r a b i l i t é & B D D 36 Les index informatiques C’est un fichier qui permet de trouver un enregistrement dans une table. Vocabulaire : Clé d’indexation = une liste d’un ou plusieurs attributs. Une adresse (déjà vu) est une adresse de bloc ou une adresse d’enregistrement. Entrée d’index : enregistrements de la forme [valeur,addr], valeur est une valeur de clé. L’index est trié sur valeur [email protected] i n t e r o p é r a b i l i t é & B D D 37 Exemples Clés de recherche : Le titre du film (c’est aussi la clé primaire) l’année du film Une paire constituée du titre et de l’année Opérations : Rechercher Vertigo Rechercher les films parus entre 1960 et 1975 Rechercher les films commençant par ’V’ [email protected] i n t e r o p é r a b i l i t é & B D D Le cas des dictionnaires Les dictionnaires ont la particularité de trier les termes. On peut alors créer un index qui ne référence que le premier mot de chaque page. - ballon, page 56 - bille, page 57 - bulle, page 65, - cable, page 72 On peut quand même utiliser cet index pour trouver n’importe quel mot. ("armée", "crabe", "botte", "belle"). 38 [email protected] B D D & i n t e r o p é r a b i l i t é Index dense 39 Index dense sur l’année, avec fichier de films triés par titre [email protected] i n t e r o p é r a b i l i t é & B D D Index dense Sur notre fichier de 1,2 Go Une année = 4 octets, une adresse 8 octets Taille de l’index : 1 000 000 *(4 + 8) = 12 Mo 100 fois plus petit que le fichier. Recherches : Par clé : comme sur un index non-dense Par intervalle (exemple [1950, 1979]) : recherche, dans l’index de la borne inférieure parcours séquentiel dans l’index à chaque valeur : accès au fichier de données Engendre des accès aléatoires. 40 [email protected] B D D & i n t e r o p é r a b i l i t é Index non dense 41 Hypothèse : le fichier de données est trié sur la clé, comme un dictionnaire. L’index ne référence que la première valeur de chaque bloc. [email protected] B D D & i n t e r o p é r a b i l i t é Index non dense 42 Hypothèse : le fichier de données est trié sur la clé, comme un dictionnaire. L’index ne référence que la première valeur de chaque bloc. [email protected] i n t e r o p é r a b i l i t é & B D D 43 Opérations Recherches : Par clé : je recherche Shining Par intervalle : tous les films entre Greystocke et Psychose. Par préfixe : tous les films commençant par ’M’. [email protected] i n t e r o p é r a b i l i t é & B D D 44 Index non dense(suite) Par rapport aux index denses : Moins d'espace et moins de frais généraux de maintenance pour les insertions et les suppressions. Généralement plus lent que l'index dense pour la localisation des enregistrements. Bon compromis : Index non dense avec une entrée d'index pour chaque bloc du fichier, correspondant à la plus petite valeur de clé de recherche dans le bloc. [email protected] i n t e r o p é r a b i l i t é & B D D 45 Index non dense Sur notre fichier de 1,2 Go En supposant qu’un titre occupe 20 octets, une adresse 8 octets Taille de l’index : 300 000 *(20 + 8) = 8.4Mo octets Beaucoup plus petit que le fichier ! Problème : maintenir l’ordre sur le fichier et sur l’index. 46 B D D & i n t e r o p é r a b i l i t é [email protected] Index multi-niveaux: on indexe l’index [email protected] B D D & i n t e r o p é r a b i l i t é Index multi-niveaux : jusqu’où ? 47 Arrêt quand racine constitué d’un seul bloc. structure hiérarchique ; recherche de haut en bas. [email protected] On recherche le ou les films parus en 1980, avec l’index de la figure a gauche. Partant du troisième niveau d’index, on décide qu’il faut descendre vers la droite pour accéder au second bloc du deuxième niveau d’index. Le contenu de ce second bloc nous indique qu’il faut cette fois descendre vers la gauche, vers le troisième bloc du premier niveau d’index. B D D & i n t e r o p é r a b i l i t é Exemple 48 On trouve dans ce troisième bloc l’entrée correspondant à 1980, avec les adresses des films à aller chercher dans le fichier de données. [email protected] i n t e r o p é r a b i l i t é & B D D 49 Arbre-B Aboutissement des structures d’index basées sur l’ordre des données C’est un arbre équilibré chaque noeud est un index local il se réorganise dynamiquement Utilisé universellement ! Comparable aux séquentiel indexé, mais évite d’avoir à maintenir des fichiers triés. 50 B D D & i n t e r o p é r a b i l i t é [email protected] Exemple d’un arbre B [email protected] i n t e r o p é r a b i l i t é & B D D 51 Noeud feuille d’un arbre B Un noeud feuille est un index dense local, contenant des entrées d’index. Chaque entrée référence un (ou plusieurs) enregistrements du fichier de données : celui (ceux) ayant la même valeur de clé que l’entrée. Un noeud interne est un index non dense local, les enregistrements servant de clé, intercalés avec des pointeurs. B D D & i n t e r o p é r a b i l i t é [email protected] Noeud interne d’un arbre B Le sous-arbre référencé par A2 contient tous les enregistrements dont la clé est comprise entre C1 et C2. 52 [email protected] i n t e r o p é r a b i l i t é & B D D 53 Insertion dans un arbre B On construit l’index sur le titre des films. Situation initiale. [email protected] B D D & i n t e r o p é r a b i l i t é La procédure d’éclatement Hypothèse: l’unique bloc de l’arbre B est plein Quand un noeud est plein, il faut effectuer un éclatement. 54 [email protected] B D D & i n t e r o p é r a b i l i t é Les insertions continuent Continuons avec les insertions de Underground, puis de Easy Rider Dans notre cas, Underground étant supérieur dans l’ordre lexicographioque à Twin Peaks, va à droite, et Easy Rider va à gauche. 55 Underground vient donc prendre place dans la feuille de droite, qui ne déborde pas encore. En revanche, Easy Rider doit aller dans la feuille de gauche, qui devient trop pleine. Un éclatement a lieu, l’entrée correspondant à la valeur médiane (Easy Rider) est transmise au niveau supérieur qui indexe donc les trois blocs de feuilles. [email protected] B D D & i n t e r o p é r a b i l i t é Les insertions continuent Après insertion de Jurassic Park, Manhattan et Metropolis 56 [email protected] i n t e r o p é r a b i l i t é & B D D 57 Suppression: cas 1 - très simple Suppression de la clé 25 On peut le supprimer directement [email protected] i n t e r o p é r a b i l i t é & B D D 58 Suppression: cas 2 - simple Suppression de la clé 25 Solution: Combinaison avec un nœud voisin Descente de la clé (ici 15) Suppression du nœud 59 B D D & i n t e r o p é r a b i l i t é [email protected] Suppression: cas 3 - avec éclatement 60 B D D & i n t e r o p é r a b i l i t é [email protected] Suppression: cas 3 - avec éclatement 61 B D D & i n t e r o p é r a b i l i t é [email protected] cas 4 : avec un nombre de clés inférieurs à m 62 B D D & i n t e r o p é r a b i l i t é [email protected] cas 4 : avec un nombre de clés inférieurs à m [email protected] i n t e r o p é r a b i l i t é & B D D 63 Recherche par clé On Lit La Racine De L’arbre : Manhattan Étant Situé Dans L’ordre Lexicographique Entre Easy Rider Et Psychose, On Doit Suivre Le Chaînage Situé Entre Ces Deux Titres ; On Lit Le Bloc Intermédiaire, On Descend À Gauche ; Dans La Feuille, On Trouve L’entrée Correspondant À Manhattan ; Il Reste À Lire L’enregistrement. [email protected] i n t e r o p é r a b i l i t é & B D D 64 Recherche par intervalle On fait une recherche par clé pour l’année 60 on parcourt les feuilles de l’arbre en suivant le chaînage, jusqu’à l’année 1975 à chaque fois on lit l’enregistrement Attention, les accès aux fichiers peuvent coûter très cher. [email protected] i n t e r o p é r a b i l i t é & B D D 65 Création d’un arbre B Sur la clé primaire CREATE TABLE Film (titre varchar(30) not null,..., PRIMARY KEY (titre) ); Sur n’importe quel attribut. CREATE INDEX filmAnnee on Film (annee) [email protected] i n t e r o p é r a b i l i t é & B D D 66 Quand faut-il éviter les index ? Bien que les index soient créés pour améliorer les performances des bases de données, il existe des situations dans lesquelles ils doivent être évités. Les lignes directrices suivantes indiquent quand il convient de reconsidérer l'utilisation des index : Les petites tables de données ne doivent pas être indexées ; Les tables qui nécessitent des opérations de mise à jour ou d'insertion fréquentes et volumineuses ; Les colonnes qui contiennent de grands nombres ou des valeurs NULL ne doivent pas être indexées ; Les colonnes qui font l'objet d'opérations fréquentes ne doivent pas être indexées. [email protected] i n t e r o p é r a b i l i t é & B D D 67 Référence http://sys.bdpedia.fr/arbreb.html https://moodle.insarouen.fr/pluginfile.php/43973/mod_folder/content/0/13ArbreB.pdf?forcedownload=1 "Database System Concepts, Seventh Edition." Avi Silberschatz, Henry F. Korth, S. Sudarshan (2020)