Fonctions du SGBD.
Les fonctions du SGBD sont de haut et bas niveau.
Fonctions de haut niveau :
1. Définition des données - à l'aide de cette fonction, il est déterminé quelles informations seront stockées dans la base de données (type, propriétés des données et comment elles seront liées les unes aux autres).
2. Traitement de l'information. Les informations peuvent être traitées de différentes manières : sélection, filtrage, tri, combinaison d'une information avec une autre, calcul de totaux.
3. Gestion de données. Cette fonction précise qui est autorisé à consulter les données, à les corriger ou à ajouter de nouvelles informations, ainsi qu'à définir les règles d'accès partagé.
Fonctions de bas niveau :
1. Gestion des données dans la mémoire externe ;
2. Gestion des mémoires tampons RAM ;
3. Gestion des transactions;
4. Introduction d'un journal des modifications apportées à la base de données ;
5. Assurer l'intégrité et la sécurité de la base de données.
Par opération est appelée une séquence indivisible d'opérations, qui est surveillée par le SGBD du début à la fin, et dans laquelle si une opération échoue, la séquence entière est annulée.
Journal du SGBD - une base de données spéciale ou une partie de la base de données principale, inaccessible à l'utilisateur et utilisée pour enregistrer des informations sur toutes les modifications apportées à la base de données.
Présentation du journal du SGBD est conçu pour assurer la fiabilité du stockage dans la base de données en présence de pannes matérielles et de pannes, ainsi que d'erreurs dans le logiciel.
Intégrité de la base de données - il s'agit d'une propriété de la base de données, ce qui signifie qu'elle contient des informations complètes, cohérentes et reflétant de manière adéquate le domaine.
Classement SGBD.
Les SGBD peuvent être classés :
1. Par types de programmes :
une. Serveurs de bases de données (par exemple, la SEP serveur SQL, InterBase (Borland)) - conçu pour organiser les centres de traitement de données en réseaux informatiques et mettre en œuvre les fonctions de gestion de base de données demandées par les programmes clients à l'aide d'instructions SQL (c'est-à-dire des programmes qui répondent aux requêtes) ;
b. Clients de base de données - les programmes qui demandent des données. PFSBMS peut être utilisé comme programme client, feuilles de calcul, traitements de texte, programmes E-mail;
c. Bases de données entièrement fonctionnelles (MS Access, MS Fox Pro) - un programme avec une interface développée qui vous permet de créer et de modifier des tableaux, de saisir des données, de créer et de formater des requêtes, de développer des rapports et de les imprimer.
2. Selon le modèle de données du SGBD (ainsi que de la BD) :
une. Hiérarchique - sont basés sur une structure arborescente de stockage d'informations et ressemblent au système de fichiers d'un ordinateur ; le principal inconvénient est l'incapacité à mettre en œuvre la relation plusieurs-à-plusieurs ;
b. Réseau - qui ont remplacé les hiérarchiques et n'ont pas duré longtemps, car le principal inconvénient était la complexité de développer des applications sérieuses. La principale différence entre le réseau et le réseau hiérarchique est que dans la structure hiérarchique "enregistrement - descendant" n'a qu'un seul ancêtre, et dans le réseau descendant, il peut avoir n'importe quel nombre d'ancêtres ;
c. Relationnel - dont les données sont situées dans des tableaux, entre lesquels existent certains liens ;
ré. Orienté objet - ils stockent des données sous forme d'objets et le principal avantage en travaillant avec eux est de pouvoir leur appliquer une approche orientée objet ;
e. Hybride, c'est-à-dire objet - relationnel - combiner les capacités des bases de données relationnelles et orientées objet. Un exemple d'une telle base de données est Oracle (auparavant, elle était relationnelle).
3. Selon l'emplacement des différentes parties du SGBD, on les distingue :
une. local - dont toutes les parties sont situées sur un seul ordinateur ;
b. réseau.
Le réseau comprend :
- avec fichier d'organisation - serveur;
Avec une telle organisation, toutes les données se trouvent sur un seul ordinateur, appelé serveur de fichiers et connecté au réseau. Lors de la recherche des informations nécessaires, l'intégralité du fichier est transférée, y compris de nombreuses informations redondantes. Et ce n'est que lors de la création d'une copie locale que l'enregistrement requis est trouvé.
- avec une organisation client-serveur ;
Le serveur de base de données accepte une demande du client, recherche l'enregistrement requis dans les données et le transfère au client. La requête au serveur est formée dans le langage structuré Requêtes SQL par conséquent, les serveurs de base de données sont appelés serveurs SQL.
- SGBD distribué contiennent plusieurs dizaines et centaines de serveurs situés sur un vaste territoire.
Dispositions de base du modèle de base de données relationnelle.
Base de données relationnelle est appelée une base de données dans laquelle toutes les données sont organisées sous forme de tables, et toutes les opérations sur ces données sont réduites à des opérations sur des tables.
Particularités bases de données relationnelles Les données:
1. Les données sont stockées dans des tableaux constitués de colonnes et de lignes ;
2. Il y a une valeur à l'intersection de chaque colonne et ligne ;
3. Chaque colonne - champ a son propre nom, qui lui sert de nom - un attribut, et toutes les valeurs d'une colonne sont du même type;
4. Les colonnes sont disposées dans un certain ordre, qui est spécifié lors de la création d'un tableau, par opposition aux lignes, qui sont disposées dans un ordre arbitraire. Le tableau peut ne pas avoir une seule ligne, mais il doit y avoir au moins une colonne.
Terminologie de la base de données relationnelle :
| Élément de base de données relationnelle | Formulaire de présentation |
| 1. Base de données | Ensemble de tables |
| 2. Schéma de la base de données | Un ensemble d'en-têtes de tableau |
| 3. Attitude | tableau |
| 4. Diagramme de relations | Ligne d'en-tête de colonne de tableau |
| 5. Essence | Description des propriétés de l'objet |
| 6. Attribut | En-tête de colonne |
| 7. Domaine | Nombreuses valeurs d'attributs valides |
| 8. Clé primaire | Un identifiant unique qui identifie de manière unique chaque enregistrement dans la table |
| 9. Type de données | Le type des valeurs des éléments du tableau |
| 10. Tuple | Chaîne (écrire) |
| 11. Cardinalité | Nombre de lignes dans le tableau |
| 12. Degré d'attitude | nombre de champs |
| 13. Relation corporelle | Tuples de relations multiples |
Lors de la conception d'une base de données relationnelle, les données sont placées dans plusieurs tables. Les relations sont établies entre les tables à l'aide de clés. Lors de la liaison de tables, les tables principales et supplémentaires (subordonnées) sont sélectionnées.
Exister les types suivants relations entre les tables :
1. Relation de la forme 1 : 1 (un à un) signifie que chaque enregistrement de la table principale correspond à un enregistrement de la table supplémentaire et, à l'inverse, chaque enregistrement de la table supplémentaire correspond à un enregistrement de la table principale.
2. Type de relation 1 : M (un à plusieurs) signifie que chaque enregistrement de la table principale correspond à plusieurs enregistrements de la table supplémentaire et, à l'inverse, chaque enregistrement de la table supplémentaire correspond à un seul enregistrement de la table principale.
3. Relation comme M : 1 (plusieurs à un) signifie qu'un ou plusieurs enregistrements de la table principale correspondent à un seul enregistrement de la table secondaire.
4. Relation de la forme M : M (plusieurs à plusieurs) - c'est lorsque plusieurs enregistrements de la table supplémentaire correspondent à plusieurs enregistrements de la table principale et inversement.
5. Les principaux composants de MS Access.
Les principaux composants (objets) de MS Access sont :
1. Tableaux ;
3. Formulaires ;
4. Rapports ;
5. Macro :
Modules.
tableau Est un objet conçu pour stocker des données sous forme d'enregistrements (lignes) et de champs (colonnes). Chaque champ contient une partie distincte de l'enregistrement et chaque table est utilisée pour stocker des informations sur une question spécifique.
Demande - une question sur les données stockées dans les tables, ou une instruction de sélection des enregistrements à modifier.
Forme Est un objet dans lequel vous pouvez placer des contrôles pour saisir, afficher et modifier des données dans les champs des tables.
Reportage Est un objet qui vous permet de présenter des informations définies par l'utilisateur d'une certaine manière, de les visualiser et de les imprimer.
Macro - une ou plusieurs macros qui peuvent être utilisées pour automatiser une tâche spécifique. La macro est le bloc de construction principal d'une macro ; une instruction autonome qui peut être combinée avec d'autres macros pour automatiser une tâche.
Module - un ensemble de descriptions, instructions et procédures stockées sous un même nom. Il existe trois types de modules dans MS Access : module de formulaire, module de rapport et module général. Les modules de formulaire et de rapport contiennent un programme local pour les formulaires et les rapports.
6. Tableaux dans MS Access.
Il existe les méthodes suivantes pour créer des tables dans MS Access :
1. Mode tableau ;
2. Constructeur;
3. Assistant de tableau ;
4. Importation de tableaux ;
5. Relation avec les tableaux.
DANS mode tableau les données sont saisies dans une table vide. Un tableau de 30 champs est fourni pour la saisie des données. Après l'avoir enregistré, MS Access décide lui-même du type de données à affecter à chaque champ.
Constructeur offre la possibilité de créer indépendamment des champs, de sélectionner des types de données pour les champs, des tailles de champ et de définir des propriétés de champ.
Pour définir un champ dans le mode Constructeur sont fixés :
1. Nom de domaine , qui dans chaque table doit avoir un nom unique qui est une combinaison de lettres, de chiffres, d'espaces et de caractères spéciaux, à l'exception de " .!” “ ». Longueur maximale nom 64 caractères.
2. Type de données définit le type et la plage de valeurs valides, ainsi que la quantité de mémoire allouée pour ce champ.
Types de données MS Access
| Type de données | La description |
| Texte | Texte et chiffres, tels que noms et adresses, numéros de téléphone, codes postaux (jusqu'à 255 caractères). |
| Champ mémo | Texte long et chiffres, tels que commentaires et explications (jusqu'à 64 000 caractères). |
| Numérique | Type de données général pour les données numériques qui permet des calculs mathématiques, à l'exception des calculs monétaires. |
| Date Heure | Valeurs de date et d'heure. L'utilisateur peut choisir des formes standard ou créer un format personnalisé. |
| Monétaire | Valeurs monétaires. Pour les calculs monétaires, il n'est pas recommandé d'utiliser des types de données numériques, car ils peuvent être arrondis dans les calculs. Les valeurs monétaires sont toujours affichées avec le nombre spécifié de décimales après la virgule. |
| Compteur | Numéros séquentiels automatiquement exposés. La numérotation commence à partir de 1. Le champ compteur est pratique pour créer une clé. Ce champ est compatible avec un champ numérique dont la propriété Size est définie sur Long. |
| Logique | Les valeurs sont Oui/Non, Vrai/Faux, On/Off, une des deux valeurs possibles. |
| Champ d'objet OLE | Objets créés dans d'autres programmes prenant en charge le protocole OLE. |
3. Les propriétés de champ les plus importantes :
- Taille du champ demande taille maximum données stockées sur le terrain.
- Format de champ est un format d'affichage d'un type de données donné et définit les règles de présentation des données lors de leur affichage à l'écran ou lors de l'impression.
- Signature de champ définit le texte qui s'affiche dans les tableaux, formulaires, rapports.
- Condition sur la valeur vous permet de contrôler l'entrée, définit des restrictions sur les valeurs d'entrée, en cas de violation des conditions, interdit l'entrée et affiche le texte spécifié par la propriété Message d'erreur ;
- Message d'erreur spécifie le texte du message affiché à l'écran lorsque les contraintes spécifiées par la Condition sur la valeur sont violées.
Type de contrôle- une propriété définie dans l'onglet Substitution de la fenêtre du concepteur de table. Cette propriété détermine si le champ sera affiché dans le tableau et sous quelle forme - en tant que champ ou en tant que zone de liste déroulante.
Clé unique (primaire) les tables peuvent être simples ou complexes avec plusieurs champs.
Pour définir la clé, les champs qui composent la clé sont mis en surbrillance et le bouton de la barre d'outils est enfoncé champ clé ou la commande est exécutée Modifier/Champ clé.
© 2015-2019 site
Tous les droits appartiennent à leurs auteurs. Ce site ne revendique pas la paternité, mais fournit une utilisation gratuite.
Date de création de la page : 2016-02-16
outils linguistiques disponibles et systèmes logiciels assurer leur haute performance et jeter les bases de la théorie de la conception des bases de données. Cependant, pour l'utilisateur général de SGBD relationnels, des équivalents informels de ces concepts peuvent être appliqués avec succès :
"Relation" - "table" (parfois fichier), "tuple" - "ligne" (parfois enregistrement), "attribut" - "colonne", "champ".
Cela suppose que « record » signifie « instance de l'enregistrement » et « champ » signifie « nom et type de champ ».
Base de données relationnelle
Une base de données relationnelle est un ensemble de relations contenant toutes les informations qui doivent être stockées dans une base de données. Cependant, les utilisateurs peuvent percevoir une telle base de données comme un ensemble de tables. Ça devrait être noté:
Chaque table est constituée de lignes du même type et porte un nom unique ; Les lignes ont un nombre fixe de champs (colonnes) et de valeurs (beaucoup
Les champs génériques et les groupes en double ne sont pas autorisés). Autrement dit, à chaque position du tableau à l'intersection d'une ligne et d'une colonne, il y a toujours exactement une valeur ou rien ;
Les lignes d'un tableau doivent nécessairement différer les unes des autres d'au moins une seule valeur, ce qui permet d'identifier sans ambiguïté toute ligne d'un tel tableau ;
Les noms sont attribués de manière unique aux colonnes du tableau et des valeurs de données homogènes (dates, noms de famille, nombres entiers ou montants monétaires) sont placées dans chacune d'elles ;
Le contenu complet des informations de la base de données est représenté sous forme de valeurs de données explicites et cette méthode de présentation est la seule ; Lors de l'exécution d'opérations sur une table, ses lignes et colonnes peuvent être traitées dans n'importe quel ordre quel que soit leur contenu d'information. Ceci est facilité par la présence de noms de tables et de leurs colonnes, ainsi que par la possibilité de sélectionner n'importe laquelle de leurs lignes ou n'importe quel ensemble de lignes avec les caractéristiques spécifiées (par exemple, les vols avec la destination "Paris" et l'heure d'arrivée
jusqu'à 12 heures).
Manipulation des données relationnelles
En proposant modèle relationnel données, E.F. Codd a également créé un outil pour travailler facilement avec les relations - l'algèbre relationnelle. Chaque opération de cette algèbre utilise un ou plusieurs tableaux (relations) comme opérandes et produit par conséquent un nouveau tableau, c'est-à-dire permet de "couper" ou de "coller" des tables (Fig. 1.5).
Riz. 1.5. Quelques opérations d'algèbre relationnelle
Des langages de manipulation de données ont été créés qui permettent de mettre en œuvre toutes les opérations d'algèbre relationnelle et presque toutes les combinaisons d'entre elles. Parmi eux, le plus courant SQL (Structured Query Language - structuré
Query Language) et QBE (Quere-By-Example). Les deux de-
sont liés à des langues de très haut niveau, à l'aide desquelles l'utilisateur indique quelles données doivent être obtenues, sans préciser la procédure pour les obtenir.
Avec une seule requête dans l'une de ces langues, vous pouvez joindre plusieurs tables dans une table temporaire et en découper les lignes et les colonnes requises (sélection et projection).
Conception de bases de données relationnelles, objectifs de conception
Seules les petites organisations peuvent partager des données dans une base de données entièrement intégrée. Le plus souvent, il est pratiquement impossible de couvrir et de comprendre toutes les exigences d'information des employés de l'organisation (c'est-à-dire les futurs utilisateurs du système). Ainsi, les systèmes d'information des grandes organisations contiennent plusieurs dizaines de bases de données, souvent réparties entre plusieurs ordinateurs interconnectés de différents services. (Donc dans les grandes villes, non pas une, mais plusieurs bases végétales sont créées, situées dans différentes régions.)
Des bases de données distinctes peuvent combiner toutes les données nécessaires pour résoudre un ou plusieurs problèmes appliqués, ou des données liées à n'importe quel domaine (par exemple, finance, étudiants, enseignants, cuisine, etc.). Les premières sont généralement appelées bases de données d'applications et les secondes sont appelées bases de données thématiques (liées aux sujets de l'organisation et non à ses applications d'information). Les premières peuvent être assimilées à des bases logistiques ou de loisirs, et les secondes à des bases végétales et vestimentaires.
Les bases de données thématiques permettent de fournir un support pour toutes les applications actuelles et futures, puisque l'ensemble de leurs éléments de données comprend des ensembles d'éléments de données des bases de données appliquées. En conséquence, les bases de données thématiques créées
Fournir un cadre pour le traitement des requêtes et applications informelles, changeantes et inconnues (applications pour lesquelles il est impossible de prédéterminer les besoins en données). Une telle flexibilité et adaptabilité permet de créer des systèmes d'information assez stables sur la base de bases de données thématiques, c'est-à-dire. systèmes dans lesquels la plupart des modifications peuvent être apportées sans avoir à réécrire les anciennes applications.
En basant la conception de la base de données sur les applications actuelles et prévisibles, il est possible d'accélérer considérablement la création d'un système d'information très efficace, c'est-à-dire un système dont la structure prend en compte les chemins d'accès aux données les plus courants. Par conséquent, la conception appliquée attire toujours certains développeurs. Cependant, à mesure que le nombre d'applications de ces systèmes d'information augmente, le nombre de bases de données appliquées augmente rapidement, le niveau de duplication des données augmente fortement et le coût de leur maintenance augmente.
Ainsi, chacune des approches de conception considérées affecte les résultats de conception dans différentes directions. Le désir d'atteindre à la fois la flexibilité et l'efficacité a conduit à la formation d'une méthodologie de conception qui utilise à la fois des approches thématiques et appliquées. Dans le cas général, l'approche sujet est utilisée pour construire la structure d'information initiale, et l'approche appliquée est utilisée pour l'améliorer afin d'augmenter l'efficacité du traitement des données.
Lors de la conception d'un système d'information, il est nécessaire d'analyser les objectifs de ce système et d'identifier les exigences des utilisateurs individuels (employés de l'organisation). La collecte de données commence par l'examen des entités de l'organisation et des processus qui utilisent ces entités. Les entités sont regroupées par « similarité » (la fréquence de leur utilisation pour effectuer certaines actions) et par le nombre de connexions associatives entre elles (avion - passager, enseignant - discipline, élève - session, etc.). Les entités ou groupes d'entités présentant la plus grande similitude et (ou) la fréquence de liens associatifs la plus élevée sont combinés dans des bases de données thématiques. (Souvent, les entités sont combinées dans des bases de données de sujets sans l'utilisation de méthodes formelles - selon le "bon sens").
L'objectif principal de la conception d'une base de données est de réduire la redondance des données stockées et, par conséquent, d'économiser la quantité de mémoire utilisée, de réduire le coût des opérations multiples pour mettre à jour les copies redondantes et d'éliminer la possibilité d'incohérences dues au stockage d'informations. sur le même objet à des endroits différents. Le projet DB dit « propre » (« Every fact in one place ») peut être créé en utilisant la méthodologie de normalisation des relations.
La normalisation consiste à diviser une table en deux ou plus qui ont de meilleures propriétés lors de l'inclusion, de la modification et de la suppression de données.
Le but ultime de la normalisation est d'avoir une conception de base de données dans laquelle chaque fait n'apparaît qu'à un seul endroit, c'est-à-dire la redondance des informations est exclue. Ceci est fait non pas tant pour économiser de la mémoire, mais pour éliminer une éventuelle incohérence des données stockées.
Chaque table d'une base de données relationnelle satisfait à la condition qu'à l'intersection de chaque ligne et colonne de la table, il y a toujours une seule valeur atomique, et il ne peut jamais y avoir un ensemble de telles valeurs. Toute table qui satisfait à cette condition est dite normalisée. En fait, les tables non normalisées, c'est-à-dire les tables contenant des groupes répétitifs ne sont même pas autorisées dans une base de données relationnelle.
Toute table normalisée est automatiquement considérée comme une table dans première forme normale, abrégé en 1NF. Donc, à proprement parler, "normalisé" et "en 1NF" signifient la même chose. Cependant, dans la pratique, le terme "normalisé" est souvent utilisé dans un sens plus étroit.
- "entièrement normalisé", ce qui signifie que le projet ne viole aucun principe de normalisation.
Maintenant, en plus de 1NF, d'autres niveaux de normale
malisation - deuxième forme normale (2NF), troisième forme normale
(3NF), etc. Essentiellement, une table est en 2NF si elle est en 1NF
et satisfait en outre une condition supplémentaire, dont l'essence sera examinée ci-dessous. Une table est en 3NF si elle est en 2NF et, en plus, remplit une autre condition supplémentaire
etc.
Ainsi, chaque forme normale est en quelque sorte plus limitée, mais aussi plus souhaitable que la précédente. Cela est dû au fait que la "(N + 1) ème forme normale" ne présente pas certaines des caractéristiques inesthétiques inhérentes à la "N ème forme normale". Le sens général de la condition supplémentaire imposée à la (N+1) ième forme normale par rapport à la Nième forme normale est d'éliminer ces singularités inesthétiques.
La théorie de la normalisation est basée sur la présence de l'une ou l'autre relation entre les champs de la table. Deux types de telles dépendances sont définis :
rationnel et ambigu.
Dépendance fonctionnelle. Le champ B de la table dépend fonctionnellement du champ A de la même table si et seulement si à un instant donné pour chacune des différentes valeurs du champ A une seule des différentes valeurs du champ B existe nécessairement. est supposé ici que les champs A et B peuvent être composites.
Plein dépendance fonctionnelle. Le champ B est en pleine fonction
dépendance fonctionnelle au champ composite A s'il dépend fonctionnellement de A et ne dépend fonctionnellement d'aucun sous-ensemble du champ A.
Dépendance multi-valuée... Le champ A définit de manière ambiguë le champ B qui
Toutes les bases de données modernes utilisent CBO (Cost Based Optimization), optimisation des coûts. Son essence réside dans le fait que pour chaque opération son « coût » est déterminé, puis le coût total de la demande est réduit en utilisant les chaînes d'opérations « les moins chères ».Pour mieux comprendre l'optimisation des coûts, nous examinerons trois façons courantes de joindre deux tables et verrons comment même une simple requête de jointure peut se transformer en cauchemar pour un optimiseur. Pour notre discussion, nous nous concentrerons sur la complexité temporelle, bien que l'optimiseur calcule le « coût » en ressources CPU, mémoire et E/S. C'est juste que la complexité temporelle est un concept approximatif, et pour déterminer les ressources processeur requises, vous devez compter toutes les opérations, y compris l'addition, les instructions if, la multiplication, l'itération, etc.
Outre:
- Pour chaque opération de haut niveau, le processeur effectue un nombre différent d'opérations de bas niveau.
- Le coût des opérations du processeur (en termes de cycles) est différent pour différents types processeurs, c'est-à-dire que cela dépend de l'architecture spécifique du processeur.
Nous en avons parlé lorsque nous avons regardé les arbres B. Comme vous vous en souvenez, les indices sont déjà triés. Soit dit en passant, il existe d'autres types d'index, par exemple les index bitmap. Mais ils n'offrent aucun avantage en termes d'utilisation du processeur, de la mémoire et du disque par rapport aux index B-tree. De plus, de nombreuses bases de données modernes peuvent créer dynamiquement des index temporaires sur les requêtes en cours si cela peut aider à réduire le coût d'exécution du plan.
4.4.2. Modes de contact
Avant de pouvoir utiliser les opérateurs de jointure, vous devez d'abord obtenir les données dont vous avez besoin. Cela peut être fait des manières suivantes.
- Scan complet. La base de données lit simplement l'intégralité de la table ou de l'index. Comme vous pouvez l'imaginer, l'index est moins cher à lire pour le sous-système de disque que la table.
- Balayage de portée. Utilisé, par exemple, lorsque vous utilisez des prédicats comme WHERE AGE> 20 AND AGE< 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.
Dans la première partie de l'article, nous avons déjà découvert que la complexité temporelle d'une requête de plage est définie comme M + log (N), où N est la quantité de données dans l'index, et M est le nombre estimé de lignes dans la gamme. Les valeurs de ces deux variables nous sont connues grâce aux statistiques. Lors de l'analyse d'une plage, seule une partie de l'index est lue, donc cette opération coûte moins cher que l'analyse complète.
- Numérisation par valeurs uniques. Il est utilisé lorsque vous avez besoin d'obtenir une seule valeur de l'index.
- Accès par ID de ligne. Si la base de données utilise un index, la plupart du temps, elle recherchera les lignes qui lui sont associées. Par exemple, nous faisons une requête comme celle-ci :
SELECTIONNER NOM, PRENOM de PERSONNE O AGE = 28
Si nous avons un index sur la colonne d'âge, l'optimiseur utilisera l'index pour trouver tous les 28 ans, puis interrogera les ID des lignes de table correspondantes, car l'index ne contient que des informations sur l'âge.Disons que nous avons une autre demande :
SELECTIONNER TYPE_PERSON.CATEGORY à partir de PERSON, TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE
Pour joindre avec TYPE_PERSON, l'index sur la colonne PERSON sera utilisé. Mais comme nous n'avons pas demandé d'informations à la table PERSON, personne ne s'y référera par ID de ligne.Cette approche n'est bonne que pour un petit nombre de hits car elle est coûteuse en termes d'E/S. Si vous avez besoin de contacter fréquemment par ID, il est préférable d'utiliser une analyse complète.
- Autres méthodes... Vous pouvez lire à leur sujet dans la documentation Oracle. Différentes bases de données peuvent utiliser des noms différents, mais les principes sont les mêmes partout.
Donc, nous savons comment récupérer les données, il est temps de les fusionner. Mais d'abord, définissons quelques nouveaux termes : dépendances internes et dépendances externes... La dépendance peut être :
- tableau,
- indice,
- un résultat intermédiaire d'une opération précédente (par exemple, une jointure précédente).
Le plus souvent, le coût de A JOIN B n'est pas égal au coût de B JOIN A.
Supposons que la dépendance externe contienne N éléments et que la dépendance interne contienne M. Comme vous vous en souvenez, l'optimiseur connaît ces valeurs grâce aux statistiques. N et M sont les nombres cardinaux des dépendances.
- Concaténation à l'aide de boucles imbriquées. C'est la façon la plus simple de combiner.
Cela fonctionne comme ceci : pour chaque ligne de la dépendance externe, des correspondances sont recherchées pour toutes les lignes de la dépendance interne.
Exemple de pseudo-code :
Nested_loop_join (tableau externe, tableau interne) pour chaque ligne a en externe pour chaque ligne b en interne if (match_join_condition (a, b)) write_result_in_output (a, b) end if end for end for
Comme il s'agit d'une double itération, la complexité temporelle est O (N * M).Pour chacune des N lignes de la dépendance externe, il faut compter M lignes de la dépendance externe. C'est-à-dire que cet algorithme nécessite N + N * M lectures de disque. Si la dépendance interne est suffisamment petite, vous pouvez la mettre entièrement en mémoire et le sous-système de disque n'aura alors que M + N lectures. Il est donc recommandé de rendre la dépendance interne aussi compacte que possible afin de la conduire en mémoire.
En termes de complexité temporelle, il n'y a pas de différence.
Vous pouvez également remplacer la dépendance interne par un index pour économiser les E/S.
Si la dépendance interne ne tient pas entièrement dans la mémoire, vous pouvez utiliser un algorithme différent qui utilise le disque de manière plus économique.- Au lieu de lire les deux dépendances ligne par ligne, elles sont lues par groupes de lignes (bunch), avec un groupe de chaque dépendance stocké en mémoire.
- Les lignes de ces groupes sont comparées entre elles et les correspondances trouvées sont enregistrées séparément.
- Ensuite, de nouveaux groupes sont chargés en mémoire et sont également comparés les uns aux autres.
Exemple d'algorithme :
// version améliorée pour réduire les E/S disque. nested_loop_join_v2 (fichier externe, fichier interne) pour chaque groupe ba dans l'extérieur // ba est maintenant en mémoire pour chaque groupe bb dans l'intérieur // bb est maintenant en mémoire pour chaque ligne a dans ba pour chaque ligne b dans bb if (match_join_condition ( a, b)) write_result_in_output (a, b) fin si fin pour fin pour fin pour fin pour
Dans ce cas, la complexité temporelle reste la même, mais le nombre d'accès disque diminue : (le nombre de groupes externes + le nombre de groupes externes * le nombre de groupes internes). À mesure que la taille du groupe augmente, le nombre d'accès au disque diminue encore plus.Remarque : dans cet algorithme, davantage de données sont lues à chaque appel, mais cela n'a pas d'importance, car les appels sont séquentiels.
- Hash rejoindre. Il s'agit d'une opération plus complexe, mais dans de nombreux cas, le coût est inférieur.
L'algorithme est le suivant :
- Tous les éléments de la dépendance interne sont lus.
- Une table de hachage est créée en mémoire.
- Tous les éléments de la dépendance externe sont lus un par un.
- Pour chaque élément, un hachage est calculé (à l'aide de la fonction correspondante de la table de hachage) afin que le bloc correspondant puisse être trouvé dans la dépendance interne.
- Les éléments du bloc sont comparés aux éléments de la dépendance externe.
- La dépendance interne contient X blocs.
- La fonction de hachage distribue les hachages presque de la même manière pour les deux dépendances. C'est-à-dire que tous les blocs ont la même taille.
- Le coût pour trouver une correspondance entre les éléments de la dépendance externe et tous les éléments à l'intérieur du bloc est égal au nombre d'éléments à l'intérieur du bloc.
(M / X) * (N / X) + hashtable_cost (M) + hash_function_cost * N
Et si la fonction de hachage crée des blocs suffisamment petits, alors la complexité temporelle sera de O (M + N).
Il existe une autre méthode de jointure par hachage qui est plus efficace en mémoire et ne nécessite pas plus d'E/S :
- Les tables de hachage pour les deux dépendances sont calculées.
- Mettre sur disque.
- Et puis ils sont comparés comportementalement les uns avec les autres (un bloc est chargé en mémoire et le second est lu ligne par ligne).
L'opération de fusion peut être divisée en deux étapes :
- (Facultatif) Une jointure de tri est effectuée en premier, lorsque les deux ensembles d'entrées sont triés par les clés de la jointure.
- Ensuite, la fusion a lieu.
L'algorithme de tri par fusion a déjà été évoqué plus haut, dans ce cas il est tout à fait justifié s'il est important pour vous d'économiser de la mémoire.
Mais il arrive que des jeux de données arrivent déjà triés, par exemple :
- Si la table est organisée nativement.
- Si la dépendance est un index lorsqu'une condition de jointure est présente.
- Si l'union se produit avec un résultat trié intermédiaire.
Cette opération est très similaire à l'opération de fusion dans la procédure de tri par fusion. Mais au lieu de sélectionner tous les membres des deux dépendances, nous sélectionnons uniquement des membres égaux.
- Les deux membres actuels des deux dépendances sont comparés.
- S'ils sont égaux, ils sont alors entrés dans la table résultante, puis les deux éléments suivants sont comparés, un pour chaque dépendance.
- S'ils ne sont pas égaux, la comparaison est répétée, mais au lieu du plus petit des deux éléments, l'élément suivant de la même dépendance est pris, car la probabilité de coïncidence dans ce cas est plus élevée.
- Les étapes 1 à 3 sont répétées jusqu'à ce que vous n'ayez plus d'éléments de l'une des dépendances.
Si les deux dépendances doivent encore être triées, la complexité temporelle est O (N * Log (N) + M * Log (M)).
Cet algorithme fonctionne bien car les deux dépendances sont déjà triées et nous n'avons pas à les parcourir dans les deux sens. Cependant, une certaine simplification est autorisée ici : l'algorithme ne gère pas les situations où les mêmes données se produisent plusieurs fois, c'est-à-dire lorsque plusieurs correspondances se produisent. En réalité, une version plus complexe de l'algorithme est utilisée. Par exemple:
MergeJoin (relation a, relation b) relation sortie entier a_key : = 0 ; entier b_key : = 0 ; tandis que (a! = nul et b! = nul) si (a< b) a_key++; else if (a >b) clé_b ++ ; else // Prédicat de jointure satisfait write_result_in_output (a, b) // Nous devons être prudents lorsque nous augmentons les pointeurs entier a_key_temp: = a_key; entier b_key_temp : = b_key ; si (a! = b) b_key_temp : = b_key + 1; end if if (b! = a) a_key_temp: = a_key + 1; end if if (b == a && b == a) a_key_temp: = a_key + 1; b_key_temp : = b_key + 1 ; fin si a_key : = a_key_temp; b_key : = b_key_temp ; fin si fin pendant
S'il y avait une meilleure façon de combiner, alors toutes ces variétés n'existeraient pas. La réponse à cette question dépend donc de plusieurs facteurs :
- Mémoire disponible... Si cela ne suffit pas, oubliez la puissante concaténation de hachage. Du moins, à propos de sa mise en œuvre entièrement en mémoire.
- La taille des deux cas de test. Si vous avez une table grande et l'autre très petite, une jointure en boucle imbriquée fonctionnera le plus rapidement, car la jointure par hachage coûte cher à générer des hachages. Si vous avez deux très grandes tables, une jointure en boucle imbriquée consommera toutes les ressources CPU.
- Disponibilité des indices. Si vous avez deux index B-tree, il est préférable d'utiliser la jointure par fusion.
- Si le résultat doit être trié. Vous souhaiterez peut-être utiliser une jointure de fusion (triée) coûteuse si vous travaillez avec des ensembles de données non triés. Ensuite, vous obtenez des données triées dans la sortie, ce qui est plus pratique à combiner avec les résultats d'une autre union. Ou parce que la requête, implicitement ou explicitement, consiste à obtenir des données triées par des instructions ORDER BY / GROUP BY / DISTINCT.
- Les dépendances de sortie sont-elles triées... Dans ce cas, il est préférable d'utiliser la jointure par fusion.
- Quels types de dépendances utilisez-vous... Jointure d'équivalence (table.column1 = table.B.column2) ? Dépendances internes, externes, produit cartésien ou auto-jointure ? Dans différentes situations, certaines méthodes de combinaison ne fonctionnent pas.
- Diffusion des données... Si les données sont rejetées en raison de la condition d'union (par exemple, vous combinez des personnes par nom de famille, mais il y a souvent des homonymes), vous ne devez en aucun cas utiliser l'union de hachage. Sinon, la fonction de hachage créera des buckets avec une très mauvaise distribution interne.
- S'il est nécessaire de fusionner en plusieurs processus / threads.
4.4.4. Exemples simplifiés
Disons que nous devons combiner cinq tableaux pour obtenir une image complète de certaines personnes. Tout le monde peut avoir :
- Plusieurs numéros de téléphone portable.
- Plusieurs adresses e-mail.
- Plusieurs adresses physiques.
- Plusieurs numéros de compte bancaire.
SELECT * parmi PERSON, MOBILES, MAILS, ADRESSES, BANK_ACCOUNTS WHERE PERSON.PERSON_ID = MOBILES.PERSON_ID AND PERSON.PERSON_ID = MAILS.PERSON_ID AND PERSON.PERSON_ID = ADRESSES.PERSON_ID AND PERSON_ID
L'optimiseur doit trouver la meilleure façon de traiter les données. Mais il y a deux problèmes:
- Quelle façon de combiner pour utiliser? Il existe trois options (jointure par hachage, jointure par fusion, jointure par boucle imbriquée), avec la possibilité d'utiliser 0, 1 ou 2 indices. Sans oublier que les index peuvent également être différents.
- Dans quel ordre fusionner ?
Sur la base de ce qui précède, quelles sont les options d'action ?
- Utilisez une approche de force brute. À l'aide de statistiques, calculez le coût de chacun des plans d'exécution de requêtes possibles et choisissez le moins cher. Mais il y a pas mal d'options. Trois méthodes de combinaison différentes peuvent être utilisées pour chaque ordre de combinaison, pour un total de 34 = 81 plans d'exécution possibles. Dans le cas d'un arbre binaire, le problème du choix de l'ordre de jointure se transforme en problème de permutation, et le nombre d'options est de (2 * 4) ! / (4 + 1) !.. Par conséquent, dans cet exemple très simplifié, le nombre total de plans d'exécution de requêtes possibles est de 34 * (2 * 4) ! / (4 + 1) ! = 27 216. Si nous ajoutons à cela les options où 0, 1 ou 2 index B-tree sont utilisés dans une jointure par fusion, le nombre de plans possibles s'élève à 210 000. Avons-nous mentionné qu'il s'agit d'une requête TRÈS SIMPLE ?
- Pleurer et arrêter. Très tentant, mais improductif, et il faut de l'argent.
- Essayez plusieurs forfaits et choisissez le moins cher. Calculer le coût de tout options possibles ne fonctionne pas, vous pouvez prendre un ensemble de données de test arbitraire et exécuter toutes sortes de plans dessus afin d'estimer leur coût et de choisir le meilleur.
- Appliquez des règles intelligentes pour réduire le nombre de plans possibles.
Il existe deux types de règles :- "Logique", à l'aide duquel vous pouvez exclure les options inutiles. Mais ils sont loin d'être toujours applicables. Par exemple, "lors de la jointure à l'aide de boucles imbriquées, la dépendance interne doit être le plus petit ensemble de données".
- Vous n'avez pas à chercher la solution la plus rentable et à appliquer des règles plus strictes pour réduire le nombre de plans possibles. Dites : « si la dépendance est petite, utilisez une jointure en boucle imbriquée, mais jamais une jointure de fusion ou une jointure de hachage ».
Alors, comment la base de données fait-elle des choix ?
4.4.5. Programmation dynamique, algorithme glouton et heuristique
Une base de données relationnelle utilise différentes approches, qui ont été mentionnées ci-dessus. Et le travail de l'optimiseur est de trouver une solution adaptée dans un temps limité. Dans la plupart des cas, l'optimiseur ne cherche pas le meilleur, mais simplement la bonne solution.
La force brute peut être utile pour les petites demandes. Et avec des moyens d'éliminer les calculs inutiles, la force brute peut être utilisée même pour les requêtes de taille moyenne. C'est ce qu'on appelle la programmation dynamique.
Son essence réside dans le fait que de nombreux plans d'exécution sont très similaires.
Dans cette illustration, les quatre plans utilisent la sous-arborescence A JOIN B. Au lieu de calculer son coût pour chaque plan, nous ne pouvons le compter qu'une seule fois, puis utiliser ces données autant que nécessaire. En d'autres termes, à l'aide de la mémorisation, nous résolvons le problème de chevauchement, c'est-à-dire que nous évitons les calculs inutiles.
Grâce à cette approche, au lieu de la complexité temporelle (2*N) !/(N+1) ! on obtient "seulement" 3 N. Comme appliqué à l'exemple précédent avec quatre jointures, cela signifie réduire le nombre d'options de 336 à 81. Si nous prenons une requête avec 8 jointures (une petite requête), alors la diminution de complexité sera de 57 657 600 à 6 561.
Si vous êtes déjà familiarisé avec la programmation dynamique ou les algorithmes, vous pouvez jouer avec cet algorithme :
Procédure findbestplan (S) si (bestplan [S] .cost infini) renvoie bestplan [S] // sinon bestplan [S] n'a pas été calculé plus tôt, calculez-le maintenant si (S ne contient qu'une relation) définissez bestplan [S]. plan et bestplan [S] .cost basé sur le meilleur moyen d'accéder à S / * En utilisant des sélections sur S et des indices sur S * / else pour chaque sous-ensemble non vide S1 de S tel que S1! = S P1 = findbestplan (S1) P2 = findbestplan (S - S1) A = meilleur algorithme pour joindre les résultats de P1 et P2 coût = P1.cost + P2.cost + coût de A si coût< bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = “execute P1.plan; execute P2.plan;
join results of P1 and P2 using A”
return bestplan[S]
La programmation dynamique peut être utilisée pour des requêtes plus volumineuses, mais des règles supplémentaires (heuristiques) devront être introduites pour réduire le nombre de plans possibles : 
Algorithmes gourmands
Mais si la demande est très volumineuse, ou si nous devons obtenir une réponse extrêmement rapidement, une autre classe d'algorithmes est utilisée : les algorithmes gloutonnes.
Dans ce cas, le plan d'exécution de la requête est construit étape par étape en utilisant une certaine règle (heuristique). Grâce à elle, l'algorithme glouton cherche meilleure solution pour chaque étape séparément. Le plan commence par une instruction JOIN, puis à chaque étape un nouveau JOIN est ajouté conformément à la règle.
Jetons un coup d'oeil à un exemple simple. Prenons une requête avec 4 jointures de 5 tables (A, B, C, D et E). Simplifions un peu la tâche et imaginons que la seule option est de combiner à l'aide d'algorithmes imbriqués. Nous utiliserons la règle « appliquer la jointure la moins coûteuse ».
- Nous commençons par l'une des tables, par exemple, A.
- On calcule le coût de chaque union avec A (ce sera à la fois dans le rôle de dépendance externe et interne).
- Nous constatons que A JOIN B nous coûtera le moins cher.
- Ensuite, nous calculons le coût de chaque jointure avec le résultat A JOIN B (nous le considérons également dans deux rôles).
- Nous trouvons que le plus rentable est (A JOIN B) JOIN C.
- Encore une fois, nous évaluons les options possibles.
- A la fin, on obtient le plan d'exécution de requête suivant : (((A JOIN B) JOIN C) JOIN D) JOIN E) /
Cet algorithme est appelé "Algorithme du voisin le plus proche".
Nous n'entrerons pas dans les détails, mais avec une bonne modélisation de la complexité du tri N*log(N), ce problème peut se poser. La complexité temporelle de l'algorithme est de O (N * log (N)) au lieu de O (3 N) pour la version complète avec programmation dynamique. Si vous avez une grande requête avec 20 jointures, ce serait 26 contre 3 486 784 401. Grosse différence, n'est-ce pas ?
Mais il y a une nuance. Nous supposons que si nous pouvons trouver le meilleur moyen de joindre les deux tables, nous obtiendrons le coût le plus bas en joignant le résultat des jointures précédentes avec les tables suivantes. Cependant, même si A JOIN B est l'option la moins chère, alors (A JOIN C) JOIN B peut avoir un coût inférieur à (A JOIN B) JOIN C.
Donc, si vous avez désespérément besoin de trouver le plan le moins cher de tous les temps, nous pouvons vous conseiller d'exécuter plusieurs fois des algorithmes gourmands en utilisant des règles différentes.
Autres algorithmes
Si vous en avez déjà marre de tous ces algorithmes, vous pouvez sauter ce chapitre. Il n'est pas nécessaire pour l'assimilation de tout le reste du matériel.
De nombreux chercheurs abordent le problème de la recherche meilleur plan exécution de la demande. Ils essaient souvent de trouver des solutions pour certaines tâches et modèles spécifiques. Par exemple, pour les jointures en étoile, l'exécution de requêtes parallèles, etc.
Nous recherchons des alternatives pour remplacer la programmation dynamique pour l'exécution de grandes requêtes. Les mêmes algorithmes gloutonnes sont un sous-ensemble d'algorithmes heuristiques. Ils agissent selon la règle, se souviennent du résultat d'une étape et l'utilisent pour rechercher meilleure option pour la prochaine étape. Et les algorithmes qui n'utilisent pas toujours la solution trouvée pour l'étape précédente sont appelés heuristiques.
Un exemple est les algorithmes génétiques :
- Chaque solution est un plan pour l'exécution complète de la demande.
- Au lieu d'une solution (plan), l'algorithme génère X solutions à chaque étape.
- Tout d'abord, X plans sont créés, cela se fait de manière aléatoire.
- Parmi ceux-ci, seuls les plans sont épargnés dont le coût satisfait à un certain critère.
- Ces plans sont ensuite mélangés pour créer X nouveaux plans.
- Certains des nouveaux plans sont modifiés au hasard.
- Les trois étapes précédentes sont répétées Y fois.
- Des plans du dernier cycle, nous obtenons le meilleur.
Soit dit en passant, les algorithmes génétiques sont intégrés dans PostgreSQL.
La base de données utilise également des algorithmes heuristiques tels que le recuit simulé, l'amélioration itérative, l'optimisation en deux phases. Mais ce n'est pas un fait qu'ils sont utilisés dans les systèmes d'entreprise, peut-être que leur destin est des produits de recherche.
4.4.6. De vrais optimiseurs
Ce chapitre est également facultatif et peut être ignoré.
Sortons de la théorisation et regardons des exemples concrets. Par exemple, comment fonctionne l'optimiseur SQLite. C'est une base de données "légère" qui utilise une simple optimisation gloutonne avec des règles supplémentaires :
- SQLite ne change jamais l'ordre des tables dans une opération CROSS JOIN.
- Il utilise l'union de boucles imbriquées.
- Les jointures externes sont toujours évaluées dans l'ordre dans lequel elles se sont produites.
- Jusqu'à la version 3.8.0, l'algorithme glouton Nearest Neighor est utilisé pour trouver le meilleur plan d'exécution des requêtes. Et depuis la version 3.8.0 « N Nearest Neighbors » (N3, N Nearest Neighbors) est appliqué.
- Algorithmes gourmands :
- 0 - optimisation minimale. Il utilise des balayages d'index, des jointures par boucles imbriquées et évite de réécrire certaines requêtes.
- 1 - faible optimisation
- 2 - optimisation complète
- Programmation dynamique:
- 3 - optimisation moyenne et approximation grossière
- 5 - optimisation complète, toutes les techniques heuristiques sont utilisées
- 7 - le même, mais sans l'heuristique
- 9 - optimisation maximale à tout prix, quel que soit l'effort fourni. Toutes les combinaisons possibles sont évaluées, y compris les produits cartésiens.
- Collecte de toutes les statistiques possibles, y compris attributions de fréquences et quantiles.
- Appliquer toutes les règles de réécriture des requêtes, y compris la composition d'une route tabulaire pour les requêtes matérialisées). L'exception concerne les règles de calcul intensives utilisées pour des nombre limité cas.
- Lors de l'itération sur les options de jointure à l'aide de la programmation dynamique :
- La dépendance interne composite est utilisée dans une mesure limitée.
- Pour les cartes en étoile avec tables de conversion, les produits cartésiens sont utilisés de manière limitée.
- Un large éventail de méthodes d'accès est couvert, y compris la prélecture de liste (plus d'informations ci-dessous), les opérations d'index AND spéciales et la compilation de routes de table pour les requêtes matérialisées.
Les autres conditions (GROUP BY, DISTINCT, etc.) sont gérées par des règles simples.
4.4.7. Cache de plan de requête
Étant donné que la création d'un plan prend du temps, la plupart des bases de données stockent le plan dans le cache du plan de requête. Cela permet d'éviter les calculs inutiles des mêmes étapes. La base de données doit savoir exactement quand elle doit mettre à jour des plans obsolètes. Pour cela, un certain seuil est défini, et si les changements de statistiques le dépassent, alors le plan lié à cette table est supprimé du cache.
Exécuteur des demandes
A ce stade, notre plan est déjà optimisé. Il est recompilé en code exécutable et, si les ressources sont suffisantes, il est exécuté. Les opérateurs contenus dans le plan (JOIN, SORT BY, etc.) peuvent être traités aussi bien de manière séquentielle qu'en parallèle, la décision est prise par l'exécuteur. Pour recevoir et écrire des données, il interagit avec le gestionnaire de données.5. Gestionnaire de données
Le gestionnaire de requêtes exécute une requête et a besoin de données provenant de tables et d'index. Il les demande au gestionnaire de données, mais il y a deux difficultés :
- Les bases de données relationnelles utilisent un modèle transactionnel. Il est impossible d'obtenir les données souhaitées à un moment précis, car à ce moment-là, elles peuvent être utilisées / modifiées par quelqu'un.
- La récupération des données est l'opération la plus lente dans la base de données. Par conséquent, le gestionnaire de données doit être capable de prédire son travail afin de remplir la mémoire tampon en temps opportun.
5.1. Gestionnaire de cache
Comme cela a été dit plus d'une fois, le goulot d'étranglement dans la base de données est le sous-système de disque. Par conséquent, un gestionnaire de cache est utilisé pour améliorer les performances.
Plutôt que de recevoir des données directement du système de fichiers, l'exécuteur de requêtes se tourne vers le gestionnaire de cache pour cela. Il utilise le pool de tampons contenu en mémoire, ce qui permet d'augmenter radicalement les performances de la base de données. Il est difficile d'estimer en nombre, car beaucoup dépend de ce dont vous avez besoin :
- Accès séquentiel (full scan) ou aléatoire (accès par ID de ligne).
- Lire ou écrire.
Cependant, nous sommes ici confrontés à un autre problème. Le gestionnaire de cache doit mettre les données en mémoire AVANT que l'exécuteur de requêtes n'en ait besoin. Sinon, il devra attendre qu'ils soient reçus du disque lent.
5.1.1. Proactif
L'exécuteur des requêtes sait de quelles données il aura besoin, puisqu'il connaît l'ensemble du plan, quelles données sont contenues sur le disque et les statistiques.
Lorsque l'exécuteur traite le premier bloc de données, il demande au gestionnaire de cache de charger le bloc suivant à l'avance. Et lorsqu'il procède à son traitement, il demande au DC de charger le troisième et confirme que la première partie peut être retirée du cache.
Le gestionnaire de cache stocke ces données dans un pool de mémoire tampon. Il leur ajoute également des informations de service (déclenchement, verrouillage) pour savoir s'ils sont toujours nécessaires dans le tampon.
Parfois, l'exécuteur ne sait pas de quelles données il aura besoin, ou certaines bases de données ne disposent pas de cette fonctionnalité. Ensuite, la prélecture spéculative est utilisée (par exemple, si l'exécuteur demande les données 1, 3, 5, alors il demandera probablement 7, 9, 11 à l'avenir) ou la précharge séquentielle (dans ce cas, le DC charge simplement la commande suivante un morceau de données.
N'oubliez pas que la mémoire tampon est limitée par la quantité de mémoire disponible. C'est-à-dire que pour charger certaines données, nous devons périodiquement en supprimer d'autres. Remplir et vider le cache consomme des ressources disque et réseau. Si vous avez une requête fréquemment exécutée, il serait contre-productif de charger et d'effacer les données qu'elle utilise à chaque fois. Pour résoudre ce problème, les bases de données modernes utilisent une stratégie de remplacement de tampon.
5.1.2. Stratégies d'échange de tampon
La plupart des bases de données (au moins SQL Server, MySQL, Oracle et DB2) utilisent pour cela l'algorithme LRU (Least Recent Used). Il est conçu pour conserver les données récemment utilisées dans le cache, ce qui signifie qu'il est fort probable qu'elles soient à nouveau nécessaires.
Pour faciliter la compréhension du fonctionnement de l'algorithme, supposons que les données dans le buffer ne soient pas bloquées par des déclencheurs (latch), et donc puissent être supprimées. Dans notre exemple, le tampon peut stocker trois blocs de données :
- Le gestionnaire de cache utilise les données 1 et les place dans un tampon vide.
- Ensuite, il utilise les données 4 et les envoie également au tampon.
- La même chose est faite avec les données 3.
- D'autres données sont prises 9. Mais le tampon est déjà plein. Par conséquent, la donnée 1 en est supprimée, car elle n'a pas été utilisée depuis le plus longtemps. Après cela, les données 9 sont placées dans le tampon.
- Le gestionnaire de cache utilise à nouveau les données 4. Elles sont déjà dans la mémoire tampon, elles sont donc marquées comme étant utilisées en dernier.
- La donnée 1 est à nouveau demandée, pour la mettre dans le buffer, la donnée 3 en est supprimée, car elle n'a pas été utilisée le plus longtemps.
Améliorations des algorithmes
Pour éviter cela, certaines bases de données utilisent des règles spéciales. D'après la documentation Oracle :
« Pour les très grandes tables, l'accès direct est généralement utilisé, c'est-à-dire que les blocs de données sont lus directement pour éviter un débordement de la mémoire cache. Pour les tables de taille moyenne, l'accès direct et la lecture à partir du cache peuvent être utilisés. Si le système décide d'utiliser le cache, la base de données place les blocs de données à la fin de la liste LRU pour éviter de vider le tampon."
Une version améliorée de LRU, LRU-K, est également utilisée. SQL Server utilise LRU-K lorsque K = 2. L'essence de cet algorithme est que lors de l'évaluation d'une situation, il prend en compte davantage d'informations sur les opérations passées et ne se souvient pas seulement des dernières données utilisées. La lettre K dans le nom signifie que l'algorithme prend en compte les données qui ont été utilisées les K dernières fois. On leur attribue un certain poids. Lorsque de nouvelles données sont chargées dans le cache, les données anciennes mais fréquemment utilisées ne sont pas supprimées, car leur poids est plus élevé. Bien entendu, si les données ne sont plus utilisées, elles seront quand même supprimées. Et plus les données restent longtemps non réclamées, plus leur poids diminue avec le temps.
Le calcul du poids étant assez coûteux, SQL Server utilise LRU-K lorsque K n'est que de 2. À mesure que K augmente légèrement, l'efficacité de l'algorithme s'améliore. Vous pourrez mieux le connaître grâce à.
Autres algorithmes
Bien sûr, LRU-K n'est pas la seule solution. Il existe également 2Q et CLOCK (les deux sont similaires à LRU-K), MRU (Most Récemment Utilisé, qui utilise la logique LRU, mais une règle différente s'applique, LRFU (Moins Récemment et Fréquemment Utilisé), etc. Dans certaines bases de données, vous pouvez choisir, quel algorithme sera utilisé.
5.1.3. Tampon d'écriture
Nous n'avons parlé que du tampon de lecture, mais les bases de données utilisent également des tampons d'écriture, qui accumulent les données et les vident sur le disque en morceaux, au lieu d'écritures séquentielles. Cela permet d'économiser les opérations d'E/S.
N'oubliez pas que les tampons stockent pages(unités de données indivisibles), pas des lignes de tableaux. Une page du pool de mémoire tampon est dite sale si elle a été modifiée mais pas écrite sur le disque. Il existe de nombreux algorithmes différents par lesquels la synchronisation des écritures de pages modifiées est sélectionnée. Mais cela a beaucoup à voir avec la notion de transactions.
5.2. Gestionnaire de transactions
Son travail consiste à s'assurer que chaque requête est exécutée avec sa propre transaction. Mais avant de parler du répartiteur, clarifions le concept de transactions ACID.5.2.1. "Sous acide" (un jeu de mots, si quelqu'un ne comprend pas)
Une transaction ACID (Atomicité, Isolation, Durabilité, Cohérence) est une opération élémentaire, une unité de travail qui remplit 4 conditions :
- Atomicité Il n'y a rien de "moins" qu'une transaction, pas d'opération plus subtile. Même si la transaction dure 10 heures. Si la transaction échoue, le système revient à l'état "avant", c'est-à-dire que la transaction est annulée.
- Isolation... Si deux transactions A et B sont exécutées en même temps, alors leur résultat ne devrait pas dépendre du fait que l'une d'elles s'est achevée avant, pendant ou après l'exécution de l'autre.
- Durabilité. Lorsqu'une transaction est validée (commited), c'est-à-dire terminée avec succès, les données utilisées par celle-ci restent dans la base de données, quels que soient les incidents possibles (erreurs, plantages).
- Cohérence. Seules les données valides sont écrites dans la base de données (en termes de relations relationnelles et fonctionnelles). La cohérence dépend de l'atomicité et de l'isolement.
Lors de l'exécution d'une transaction, vous pouvez exécuter diverses requêtes SQL pour lire, créer, mettre à jour et supprimer des données. Les problèmes commencent lorsque deux transactions utilisent les mêmes données. Un exemple classique est le transfert d'argent du compte A vers le compte B. Disons que nous avons deux transactions :
- T1 prend 100 $ sur le compte A et l'envoie sur le compte B.
- T2 prélève 50 $ sur le compte A et l'envoie également sur le compte B.
- Atomicité permet d'être sûr que quel que soit l'événement qui se produit pendant T1 (crash de serveur, panne de réseau), il ne peut pas arriver que 100 $ soient débités de A, mais ne viendront pas à B (sinon ils parlent d'un "état incohérent") .
- Isolation dit que même si T1 et T2 sont effectués en même temps, en conséquence, 100 $ seront radiés de A et le même montant ira à B. Dans tous les autres cas, ils parlent à nouveau d'un état incohérent.
- Fiabilité vous permet de ne pas craindre que T1 disparaisse si la base tombe immédiatement après avoir commis T1.
- Cohérence empêche la possibilité que de l'argent soit créé ou détruit dans le système.
De nombreuses bases de données ne fournissent pas une isolation complète par défaut, car cela entraîne une surcharge de performances énorme. SQL utilise 4 niveaux d'isolement :
- Transactions sérialisables. Plus haut niveau isolation. La valeur par défaut est utilisée dans SQLite. Chaque transaction s'exécute dans son propre environnement entièrement isolé.
- Lecture répétable. Utilisé par MySQL par défaut. Chaque transaction a son propre environnement, à l'exception d'une situation : si la transaction ajoute de nouvelles données et réussit, ils seront visibles par les autres transactions encore en cours. Mais si l'opération modifie les données et réussit, ces modifications ne seront pas visibles pour les transactions en cours. Autrement dit, pour les nouvelles données, le principe d'isolement est violé.
Par exemple, la transaction A effectue
SELECT compte (1) de TABLE_X
Ensuite, la transaction B s'ajoute à la table X et valide les nouvelles données. Et si après cette transaction A exécute à nouveau count (1), alors le résultat sera différent.C'est ce qu'on appelle la lecture fantôme.
- Lire commis... Utilisé par défaut dans Oracle, PostgreSQL et SQL Server. C'est la même chose que la lecture répétée, mais avec une violation d'isolement supplémentaire. Disons que la transaction A lit des données ; ils sont ensuite modifiés ou supprimés par la transaction B, qui engage ces actions. Si A lit à nouveau ces données, alors elle verra les modifications (ou le fait de suppression) apportées par B.
C'est ce qu'on appelle une lecture non répétable.
- Lire les données non validées. Niveau d'isolement le plus bas. Une nouvelle violation d'isolement est ajoutée à la lecture des données validées. Disons que la transaction A lit des données ; ils sont ensuite modifiés par la transaction B (aucune modification n'est validée, B est toujours en cours). Si A lit à nouveau les données, il verra les modifications apportées. Si B est pompé, alors lors de la lecture répétée, A ne verra aucun changement, comme si de rien n'était.
C'est ce qu'on appelle la lecture sale.
La plupart des bases de données ajoutent leurs propres niveaux d'isolement (par exemple, basés sur des instantanés, comme dans PostgreSQL, Oracle et SQL Server). En outre, de nombreuses bases de données n'implémentent pas les quatre niveaux ci-dessus, en particulier la lecture de données non validées.
Un utilisateur ou un développeur peut remplacer le niveau d'isolement par défaut dès que la connexion est établie. Tout ce que vous avez à faire est d'ajouter une ligne de code très simple.
5.2.2. Contrôle de la concurrence
La principale chose pour laquelle nous avons besoin d'isolation, de cohérence et d'atomicité est la possibilité d'effectuer des opérations d'écriture sur les mêmes données (ajout, mise à jour et suppression).
Si toutes les transactions ne lisent que des données, elles peuvent fonctionner simultanément sans affecter les autres transactions.
Si au moins une transaction modifie les données lues par d'autres transactions, la base de données doit trouver un moyen de leur cacher ces modifications. Vous devez également vous assurer que les modifications apportées ne seront pas supprimées par d'autres transactions qui ne voient pas les données modifiées.
C'est ce qu'on appelle le contrôle de la concurrence.
Le moyen le plus simple consiste simplement à exécuter les transactions une par une. Mais cette approche est généralement inefficace (n'utilisant qu'un seul cœur d'un processeur), et elle perd également la capacité d'évoluer.
Le moyen idéal pour résoudre le problème ressemble à ceci (à chaque fois qu'une transaction est créée ou annulée) :
- Surveillez toutes les opérations de chaque transaction.
- Si deux transactions ou plus sont en conflit en raison de la lecture/modification des mêmes données, modifiez l'ordre des opérations au sein des parties au conflit afin de minimiser le nombre de raisons.
- Exécutez les parties conflictuelles des transactions dans un ordre spécifique. Les transactions non conflictuelles sont exécutées en parallèle à ce moment.
- Sachez que les transactions peuvent être annulées.
5.2.3. Gestionnaire de verrouillage
Pour résoudre le problème ci-dessus, de nombreuses bases de données utilisent des verrous et/ou des versions de données.
Si une transaction a besoin de certaines données, elle les bloque. Si une autre transaction les a également requis, il faudra alors attendre que la première transaction libère le verrou.
C'est ce qu'on appelle le blocage exclusif.
Mais il est trop inutile d'utiliser des verrous exclusifs lorsque les transactions n'ont besoin que de lire des données. Pourquoi interférer avec la lecture des données ? Dans de tels cas, des verrous partagés sont utilisés. Si une transaction doit lire des données, elle applique un verrou partagé et les lit. Cela n'empêche pas d'autres transactions de partager des verrous et de lire des données également. Si l'un d'entre eux doit modifier les données, il devra attendre que tous les verrous partagés soient supprimés. Ce n'est qu'alors qu'elle pourra appliquer un verrou exclusif. Et puis toutes les autres transactions devront attendre sa suppression pour pouvoir lire ces données.
Un gestionnaire de verrous est un processus qui applique et libère des verrous. Ils sont stockés dans une table de hachage (les clés sont les données verrouillées). Le répartiteur sait pour toutes les données quelles transactions ont appliqué des verrous ou attendent d'être libérées.
Impasse
L'utilisation de verrous peut conduire à une situation dans laquelle deux transactions attendent indéfiniment pour libérer les verrous :
Ici, la transaction A a verrouillé exclusivement les données 1 et attend la libération des données 2. Dans le même temps, la transaction B a verrouillé exclusivement les données 2 et attend la libération des données 1.
Dans une impasse, le répartiteur choisit la transaction à annuler (rollback). Et la décision n'est pas si facile à prendre :
- Serait-il préférable de tuer la transaction qui a modifié le dernier ensemble de données (ce qui signifie que la restauration sera la moins douloureuse) ?
- Serait-il préférable de tuer la transaction la plus jeune puisque les utilisateurs d'autres transactions ont attendu plus longtemps ?
- Serait-il préférable de tuer une transaction qui prend moins de temps à terminer ?
- Combien d'autres transactions l'annulation affectera-t-elle ?
Imaginons une table de hachage sous forme de diagramme, comme dans l'illustration ci-dessus. Si un lien cyclique est présent dans le schéma, le verrouillage est confirmé. Mais comme il est assez coûteux de vérifier les boucles (après tout, le diagramme sur lequel tous les verrous sont reflétés sera assez grand), une approche plus simple est souvent utilisée : utiliser des délais d'attente. Si le verrou n'est pas libéré dans un certain laps de temps, la transaction est alors entrée dans un état de blocage.
Le répartiteur peut également vérifier si cela provoquera un blocage avant d'imposer un verrou. Mais pour y répondre sans équivoque, il faut aussi dépenser de l'argent en calculs. Par conséquent, ces contrôles préalables sont souvent présentés comme un ensemble de règles de base.
Blocage biphasé
Le moyen le plus simple d'obtenir un isolement complet est d'appliquer le verrou au début et de le relâcher à la fin de la transaction. Cela signifie qu'une transaction doit attendre que tous les verrous soient libérés avant de commencer, et les verrous qu'elle a appliqués ne sont libérés qu'une fois terminés. Cette approche peut être appliquée, mais alors beaucoup de temps est perdu pour tous ceux qui attendent la libération des verrous.
DB2 et SQL Server utilisent le protocole de verrouillage en deux phases, qui divise une transaction en deux phases :
- La phase de croissance lorsqu'une transaction ne peut appliquer que des verrous, mais pas les libérer.
- Phase de rétrécissement lorsqu'une transaction ne peut libérer que des verrous (à partir de données qui ont déjà été traitées et ne seront pas traitées à nouveau), mais pas en appliquer de nouveaux.
Avant la transaction A, X = 1 et Y = 1. Il traite les données Y = 1, qui ont été modifiées par la transaction B après le début de la transaction A. En raison du principe d'isolement, la transaction A doit traiter Y = 2.
Objectifs atteints avec ces deux règles simples :
- Libérez les verrous qui ne sont plus nécessaires pour réduire le temps d'attente pour d'autres transactions.
- Empêchez les cas où une transaction reçoit des données modifiées par une transaction démarrée précédemment. Ces données ne correspondent pas à celles demandées.
Bien sûr, les vraies bases de données utilisent des systèmes plus complexes, plus de types de verrous et avec une plus grande granularité (verrous pour les lignes, les pages, les partitions, les tables, les espaces table), mais l'essence est la même.
Gestion des versions des données
Une autre façon de résoudre le problème de conflit de transaction consiste à utiliser la gestion des versions des données.
- Toutes les transactions peuvent mettre à jour les mêmes données en même temps.
- Chaque transaction fonctionne avec sa propre copie (version) des données.
- Si deux transactions modifient les mêmes données, alors une seule des modifications est acceptée, l'autre sera rejetée, et la transaction qui l'a effectuée sera annulée (et éventuellement redémarrée).
- Les transactions de lecture ne bloquent pas les transactions d'écriture, et vice versa.
- Un gestionnaire de verrouillage maladroit n'a aucun effet.
Les deux approches - verrouillage et versioning - ont des avantages et des inconvénients, cela dépend beaucoup de la situation dans laquelle elles sont appliquées (plus de lectures ou plus d'écritures). Vous pouvez consulter une très bonne présentation sur la mise en œuvre du contrôle de concurrence multiversion dans PostgreSQL.
Certaines bases de données (DB2 avant la version 9.7, SQL Server) n'utilisent que des verrous. D'autres, comme PostgreSQL, MySQL et Oracle, utilisent une combinaison d'approches.
Remarque : La gestion des versions a un effet intéressant sur les index. Parfois, des doublons apparaissent dans un index unique, l'index peut contenir plus d'enregistrements que de lignes dans la table, etc.
Si une partie des données est lue à un niveau d'isolement, puis qu'elle augmente, le nombre de verrous augmente, ce qui signifie que plus de temps est perdu à attendre les transactions. Par conséquent, la plupart des bases de données n'utilisent pas le niveau d'isolement maximal par défaut.
Comme d'habitude, consultez la documentation pour plus de détails : MySQL, PostgreSQL, Oracle.
5.2.4. Gestionnaire de journaux
Comme nous le savons déjà, dans un souci d'augmentation des performances, la base de données stocke une partie des données dans la mémoire tampon. Mais si le serveur plante lors de la validation d'une transaction, les données en mémoire seront perdues. Et cela viole le principe de la fiabilité des transactions.
Bien sûr, vous pouvez tout écrire sur le disque, mais si vous plantez, vous vous retrouverez avec des données incomplètes, et c'est déjà une violation du principe d'atomicité.
Toute modification écrite par la transaction doit être annulée ou terminée.
Cela se fait de deux manières :
- Clichés instantanés / pages. Chaque transaction crée sa propre copie de la base de données (ou une partie de celle-ci) et fonctionne avec cette copie. Si une erreur se produit, la copie est supprimée. Si tout s'est bien passé, la base de données passe instantanément aux données de la copie en utilisant une astuce au niveau du système de fichiers, puis supprime les "anciennes" données.
- Journal des transactions. Il s'agit d'une installation de stockage spéciale. Avant chaque écriture sur le disque, la base de données écrit des informations dans le journal des transactions. Ainsi, en cas d'échec, la base de données saura supprimer ou terminer la transaction en attente.
Dans les grandes bases de données avec de nombreuses transactions, les clichés instantanés / pages occupent une quantité incroyable d'espace disque. Par conséquent, les bases de données modernes utilisent le journal des transactions. Il doit être situé dans un stockage sans défaut.
La plupart des produits (notamment Oracle, SQL Server, DB2, PostgreSQL, MySQL et SQLite) fonctionnent avec les journaux de transactions via le protocole WAL (Write-Ahead Logging). Ce protocole contient trois règles :
- Chaque modification de la base de données doit être accompagnée d'une entrée de journal, et elle doit être entrée AVANT que les données ne soient écrites sur le disque.
- Les entrées du journal doivent être organisées conformément à l'ordre des événements correspondants.
- Lorsqu'une transaction est validée, un enregistrement doit être enregistré AVANT la réussite de la transaction.
La mise en œuvre de ces règles est surveillée par un gestionnaire de logs. Il se situe logiquement entre le gestionnaire de cache et le gestionnaire d'accès aux données. Le gestionnaire de journaux enregistre chaque opération effectuée par les transactions jusqu'à ce qu'elle soit écrite sur le disque. Semble-t-il juste ?
TORT! Après tout ce que nous avons traversé dans cet article, il est temps de rappeler que tout ce qui concerne la base de données est soumis à la malédiction de "l'effet base de données". Sérieusement, le problème est que vous devez trouver un moyen d'écrire dans le journal tout en gardant bonne performance... Après tout, si le journal des transactions est lent, il ralentit tous les autres processus.
BÉLIER
En 1992, les chercheurs d'IBM ont créé une version étendue de WAL appelée ARIES. ARIES est utilisé sous une forme ou une autre par la plupart des bases de données modernes. Si vous souhaitez approfondir ce protocole, vous pouvez étudier l'ouvrage correspondant.
Alors ARIES signifie UNE algorithmes pour R récupération et je désolation E exploiter Sémantique. Cette technologie a deux objectifs :
- Fournir de bonnes performances lors de l'écriture des journaux.
- Fournir une récupération rapide et fiable.
- L'utilisateur l'a annulé.
- Erreur de serveur ou de réseau.
- La transaction a violé l'intégrité de la base de données. Par exemple, vous avez appliqué la clause UNIQUE à une colonne et la transaction a ajouté un doublon.
- La présence de blocages.
Comment est-ce possible? Pour répondre à cette question, vous devez d'abord déterminer quelles informations sont stockées dans le journal.
Journaux
Chaque opération (ajout/suppression/modification) lors de l'exécution d'une transaction entraîne l'apparition d'un enregistrement dans le journal. Le dossier contient :
- LSN (numéro de séquence de journal)... C'est numéro unique, dont la signification est déterminée par ordre chronologique. C'est-à-dire que si l'opération A s'est produite avant l'opération B, le LSN pour A sera inférieur au LSN pour B. En réalité, la méthode de génération du LSN est plus compliquée, car elle est également liée à la façon dont le journal est stocké.
- TransID. L'identifiant de la transaction qui a effectué l'opération.
- ID de page... Espace disque où se trouvent les données modifiées.
- PrécLSN... Un lien vers une entrée de journal précédente créée par la même transaction.
- ANNULER... Comment annuler une opération.
Par exemple, si une opération de mise à jour a été effectuée, alors la valeur/l'état précédent de l'élément modifié (UNDO physique) ou l'opération inverse est écrit dans UNDO, vous permettant de revenir à l'état précédent (UNDO logique). ARIES n'utilise que la logique, le travail physique est très dur.
- REFAIRE... Méthode pour répéter l'opération.
Pour autant que l'on sache, UNDO n'est pas seulement utilisé dans PostgreSQL. Au lieu de cela, un ramasse-miettes est utilisé pour nettoyer les anciennes versions des données. Cela est dû à la mise en œuvre de la gestion des versions des données dans ce SGBD.
Pour vous permettre d'imaginer plus facilement la composition de l'entrée du journal, voici un exemple visuel simplifié dans lequel la requête UPDATE FROM PERSON SET AGE = 18; est exécutée. Qu'il soit exécuté dans la transaction numéro 18 :
Chaque journal a un LSN unique. Les journaux liés font référence à la même transaction, et ils sont liés par ordre chronologique (le dernier journal de la liste fait référence à la dernière opération).
Tampon de journal
Pour éviter que la journalisation ne devienne un goulot d'étranglement dans le système, un tampon de journalisation est utilisé.
Lorsque l'exécuteur de requêtes demande les données modifiées :
- Le gestionnaire de cache les stocke dans un tampon.
- Le gestionnaire de journaux stocke le journal correspondant dans son propre tampon.
- L'exécuteur des demandes détermine si l'opération est terminée et, par conséquent, si les données modifiées peuvent être demandées.
- Le gestionnaire de journaux stocke les informations requises dans le journal des transactions. Le moment de faire cet enregistrement est fixé par l'algorithme.
- Le gestionnaire de cache écrit les modifications sur le disque. Le moment de l'enregistrement est également défini par l'algorithme.
Politiques VOLER et FORCER
Pour améliorer les performances, l'étape 5 doit être effectuée après le commit, car en cas d'échec, il est toujours possible de restaurer la transaction en utilisant REDO. C'est ce qu'on appelle la "politique NO-FORCE".
Mais la base de données peut également choisir la politique FORCE pour réduire la charge lors de la récupération. Ensuite, l'étape numéro 5 est exécutée avant la validation.
La base de données choisit également d'écrire les données sur le disque étape par étape (politique STEAL) ou, si le gestionnaire de tampon doit attendre une validation, d'écrire tout en même temps (NO-STEAL). Le choix dépend de ce dont vous avez besoin : enregistrement rapide avec longue convalescence ou récupération rapide ?
Comment les politiques mentionnées affectent le processus de récupération :
- VOLER/NO-FORCE nécessite UNDO et REDO. Les performances sont supérieures, mais la structure des journaux et des processus de récupération est plus complexe (comme ARES). Cette combinaison de stratégies est utilisée par la plupart des bases de données.
- VOL / FORCE n'a besoin que d'UNDO.
- Pour NO-STEAL / NO-FORCE - seulement REDO.
- Pour NO-STEAL / FORCE, rien n'est nécessaire du tout. Les performances dans ce cas sont les plus faibles et une énorme quantité de mémoire est requise.
Alors, comment pouvons-nous utiliser nos merveilleuses bûches? Supposons qu'un nouvel employé plante la base de données (règle n°1 : le débutant est toujours à blâmer !). Vous le redémarrez et le processus de récupération commence.
ARIES se reconstruit en trois étapes :
- Une analyse... L'intégralité du journal des transactions est lu afin que la chronologie des événements survenus lors de la chute de base puisse être restaurée. Cela permet de déterminer la transaction à annuler. Toutes les transactions sont annulées sans ordre de validation. Le système décide également quelles données auraient dû être écrites sur le disque pendant le crash.
- Répéter... Pour mettre à jour la base de données à l'état avant le crash, REDO est utilisé. Ses journaux sont traités par ordre chronologique. Pour chaque journal, le LSN de la page sur disque contenant les données à modifier est lu.
Si LSN (pages_on_disk)> = LSN (records_in_log), alors les données ont déjà été écrites sur le disque avant l'échec. Mais la valeur a été écrasée par une opération qui a été effectuée après l'écriture dans le journal et avant l'échec. Donc rien n'a été fait en fait.
Si LSN (pages_on_disk)
La restauration est effectuée même pour les transactions qui seront annulées car elle simplifie le processus de récupération. Mais les bases de données modernes ne le font probablement pas.
- Annulation. A ce stade, toutes les transactions qui n'étaient pas terminées au moment de l'échec sont annulées. Le processus démarre avec les derniers journaux de chaque transaction et traite l'annulation dans l'ordre chronologique inverse à l'aide de PrevLSN.
Si la transaction est annulée « manuellement », soit par le gestionnaire de verrous, soit en raison d'une défaillance du réseau, alors l'étape d'analyse n'est pas nécessaire. Après tout, les informations pour REDO et UNDO sont contenues dans deux tables situées en mémoire :
- Dans la table des transactions (les états de toutes les transactions en cours sont stockés ici).
- La table des pages modifiées (contient des informations sur les données qui doivent être écrites sur le disque).
L'étape d'analyse est nécessaire uniquement pour restaurer les deux tables en utilisant les informations du journal des transactions. ARIES utilise des points de contrôle pour accélérer cette phase. Le contenu des deux tables est écrit sur le disque de temps en temps, ainsi que le dernier au moment de l'enregistrement LSN. Ainsi lors de la récupération, seuls les logs suivant ce LSN sont analysés.
6. Conclusion
Comme lecture d'ensemble supplémentaire sur les bases de données, je recommande l'article Architecture d'un système de base de données. C'est une bonne introduction au sujet, écrite dans un langage assez simple.Si vous avez lu attentivement tout le matériel ci-dessus, vous avez probablement une idée de l'étendue des capacités des bases de données. Cependant, cet article ne couvre pas d'autres questions importantes :
- Comment gérer les bases de données en cluster et les transactions globales.
- Comment obtenir un instantané si la base de données fonctionne.
- Comment stocker et compresser efficacement les données.
- Comment gérer la mémoire.
Donc, si quelqu'un vous demande comment fonctionnent les bases de données, alors au lieu de cracher et de partir, vous pouvez répondre :
Balises : ajouter des balises
2. Principes du modèle relationnel
Principes du modèle de base de données relationnelle, relation, table, jeu de résultats, tuple, cardinalité, attribut, dimension, titre, corps, domaine
Le modèle relationnel a été développé à la fin des années 1960 par E.F. Codd (employé d'IBM) et publié en 1970. Il définit la manière dont les données sont représentées (structure des données), les méthodes de protection des données (intégrité des données) et les opérations pouvant être effectuées avec les données ( manipulation de données).
Le modèle relationnel n'est pas le seul à pouvoir être utilisé lorsque l'on travaille avec des données. Il existe également un modèle hiérarchique, un modèle en réseau, un modèle en étoile, etc. Cependant, le modèle relationnel s'est avéré le plus pratique et est donc aujourd'hui le plus utilisé.
Les principes de base des bases de données relationnelles peuvent être résumés comme suit :
· Toutes les données au niveau conceptuel sont représentées sous la forme d'une organisation ordonnée définie sous forme de lignes et de colonnes et appelée relation. Le synonyme le plus courant de relation est une table (ou un jeu d'enregistrements, ou un jeu de résultats. C'est de là que vient le terme bases de données relationnelles, pas les relations entre les tables ;
· Toutes les valeurs sont des scalaires. Cela signifie que pour n'importe quelle ligne et colonne dans n'importe quelle relation, il y a une et une seule valeur ;
· Toutes les opérations sont effectuées sur l'ensemble de la relation et le résultat de ces opérations est également l'ensemble de la relation. Ce principe s'appelle l'accrochage. Par conséquent, les résultats d'une opération (par exemple, une requête) peuvent être utilisés comme entrée pour effectuer une autre opération (sous-requête).
Maintenant, à propos de la terminologie formelle :
· attitude(relation) est la structure entière dans son ensemble, un ensemble d'enregistrements (au sens habituel, une table).
· cortège est chaque ligne contenant des données. Un terme plus courant mais moins formel est record.
· Puissance- le nombre de tuples dans la relation (en d'autres termes, le nombre d'enregistrements) ;
· attribut est une colonne en relation ;
· dimension est le nombre d'attributs dans la relation (dans ce cas, 3);
Chaque relation peut être divisée en deux parties - titre et corps... En langage simple, le titre d'une relation est une liste de colonnes et le corps est constitué des enregistrements (tuples) eux-mêmes.
· Dans notre exemple, le nom de chaque colonne (attribut) se compose de deux mots séparés par deux points. Selon les définitions formelles, la première partie est Nom d'attribut(nom de la colonne) et la deuxième partie est domaine(le type de données que la colonne de données représente). Le domaine et le type de données ne sont pas équivalents. En pratique, le domaine est généralement omis.
· Le corps d'une relation consiste en un ensemble non ordonné de tuples (son nombre peut être quelconque - de 0 à infiniment grand).
Melnikov 620 000 Russie, région de Sverdlovsk, Ekaterinbourg. +7 953 039 559 1 [email protégé] site Internet
Base de données relationnelle L'information connexe est-elle présentée sous forme de tableaux à deux dimensions. Imaginez un carnet d'adresses. Il contient de nombreuses lignes, chacune correspondant à un individu donné. Pour chacun d'eux, il présente des données indépendantes, par exemple, nom, numéro de téléphone, adresse. Imaginons un tel carnet d'adresses comme un tableau contenant des lignes et des colonnes. Chaque ligne (également appelée enregistrement) correspond à un individu spécifique, chaque colonne contient des valeurs du type de données correspondant : nom, numéro de téléphone et adresse, représentés dans chaque ligne. Un carnet d'adresses peut ressembler à ceci :
Ce que nous avons maintenant est la base d'une base de données relationnelle, définie au début de notre discussion comme un tableau d'informations à deux dimensions (ligne et colonne). Cependant, une base de données relationnelle se compose rarement d'une seule table trop petite par rapport à la base de données. Lorsque vous créez plusieurs tables avec des informations connexes, vous pouvez effectuer des opérations plus complexes et plus puissantes sur les données. La puissance d'une base de données réside davantage dans les connexions que vous établissez entre les éléments d'information que dans les éléments eux-mêmes.
Utilisons l'exemple du carnet d'adresses pour discuter d'une base de données que vous pouvez réellement utiliser dans votre vie professionnelle. Supposons que les individus du premier tableau soient des patients hospitalisés. Des informations supplémentaires à leur sujet peuvent être stockées dans une autre table. Les colonnes du deuxième tableau peuvent être nommées Patient, Médecin, Assureur, Solde.
De nombreuses fonctions puissantes peuvent être exécutées en extrayant des informations de ces tables en fonction de critères spécifiés, en particulier si le critère comprend des informations connexes provenant de différentes tables.
Supposons que le Dr Halben veuille obtenir les numéros de téléphone de tous ses patients. Pour récupérer ces informations, il doit lier une table de numéros de téléphone de patients (carnet d'adresses) à une table qui identifie ses patients. Dans cet exemple simple, il peut effectuer mentalement cette opération et connaître les numéros de téléphone de ses patients Grillet et Brock, en réalité, ces tableaux peuvent bien être plus grands et beaucoup plus complexes.
Le logiciel de base de données relationnelle a été conçu pour fonctionner avec des ensembles de données volumineux et complexes qui sont les plus courants dans la vie professionnelle de la société. Même si la base de données de l'hôpital contient des dizaines ou des milliers de noms (comme c'est probablement le cas dans la vraie vie), une seule commande SQL fournira au Dr Halben les informations dont il a besoin presque instantanément.
L'ordre des lignes est arbitraire
Pour offrir une flexibilité maximale lors de l'utilisation des données, les lignes du tableau ne sont, par définition, pas ordonnées. Cet aspect distingue une base de données d'un carnet d'adresses. Les lignes du carnet d'adresses sont généralement triées par ordre alphabétique. L'une des fonctionnalités puissantes fournies par les systèmes de bases de données relationnelles est que les utilisateurs peuvent organiser les informations comme ils le souhaitent.
Considérez le deuxième tableau. Il est parfois pratique de visualiser les informations qu'il contient triées par nom, parfois par ordre croissant ou décroissant de solde (Balance), et parfois regroupées par médecin. La gamme impressionnante d'ordres de lignes possibles empêcherait l'utilisateur d'être flexible avec les données, de sorte que les lignes sont supposées non ordonnées. C'est pour cette raison que vous ne pouvez pas simplement dire : « Je suis intéressé par la cinquième ligne du tableau. Quel que soit l'ordre dans lequel les données sont incluses ou un autre critère, cette cinquième ligne n'existe pas par définition. Ainsi, les lignes du tableau sont supposées ne pas être dans un ordre particulier.
Identification des lignes (clé primaire)
Pour cela et un certain nombre d'autres raisons, il est nécessaire d'avoir une colonne de table qui identifie de manière unique chaque ligne. Typiquement, cette colonne contient un numéro, par exemple, attribué à chaque patient. Bien sûr, vous pouvez utiliser le nom du patient pour identifier les chaînes, mais il peut arriver qu'il y ait plusieurs patients nommés Mary Smith. Dans ce cas, il n'y a pas de moyen facile de les distinguer. C'est pour cette raison que les nombres sont couramment utilisés. Cette colonne unique (ou groupe de colonnes) utilisée pour identifier chaque ligne et s'assurer que toutes les lignes sont distinguables est appelée la clé primaire de la table.
Clé primaire de table- un concept essentiel de structure de base de données. C'est le cœur du système de données : pour trouver une ligne spécifique dans une table, spécifiez la valeur de sa clé primaire. De plus, il garantit l'intégrité des données. Si la clé primaire est correctement utilisée et gérée, vous pouvez être sûr qu'aucune ligne de la table n'est vide et que chaque ligne est distincte des autres.
Les colonnes sont nommées et numérotées
Contrairement aux lignes, les colonnes du tableau (également appelées champs) sont ordonnées et nommées. Par conséquent, dans notre tableau correspondant au carnet d'adresses, nous pouvons désigner la colonne « Adresse » par « colonne numéro trois ». dans cette table doit avoir un nom différent des autres noms pour éviter toute confusion. Il est préférable que les noms définissent le contenu du champ. Dans ce livre, nous utiliserons une abréviation pour nommer les colonnes dans les tables simples, par exemple : cname pour le nom du client (nom du client), odate correspond à la date de la commande, supposons également que la table contienne une seule colonne numérique utilisée comme clé primaire.
Les tableaux 1.1, 1.2, 1.3 forment une base de données relationnelle suffisamment petite pour comprendre sa signification, mais suffisamment complexe pour illustrer les concepts importants et les implications pratiques de SQL.
Vous remarquerez que la première colonne de chaque tableau contient des nombres qui ne se répètent pas d'une ligne à l'autre dans le tableau. Comme vous l'avez probablement deviné, ce sont les clés primaires de la table. Certains de ces nombres apparaissent également dans les colonnes d'autres tables (il n'y a rien de mal à cela), indiquant une relation entre les lignes qui utilisent une valeur de clé primaire particulière et la ligne qui utilise cette valeur directement dans la clé primaire.
Par exemple, le champ snum de la table Customers définit par quels vendeurs un client particulier est servi. Le numéro de champ snum renvoie à la table Salespeople, qui donne des informations sur ce vendeur. Il est évident que le vendeur qui sert le client donné existe, c'est-à-dire la valeur du champ snum dans la table Customers apparaît également dans la table Salespeople. Dans ce cas, on dit que le système est dans un état d'intégrité référentielle.
Les tableaux eux-mêmes sont destinés à décrire des situations réelles dans la vie professionnelle lorsque vous pouvez utiliser SQL pour faire des affaires liées aux vendeurs, à leurs clients et aux commandes. Fixons l'état de ces trois tables à un moment donné et clarifions l'objectif de chacun des champs de la table.
Voici une explication des colonnes du tableau 1.1 :
Le tableau 1.2 contient les colonnes suivantes :
Et enfin, les colonnes du tableau 1.3.
