Implémentation des bases de données solides

Question 1

0 - BDD - Introduction

Retracez succintement l’histoire des SGBD.

Answer 1

1. Historiquement, les bases de données étaient des fichiers papier.
2. 1970, Edgar F. Codd introduit la notion de modèle relationnel chez IBM.
3. 1979, Oracle sort le premier SGBD.
4. 1980-2000, De nombreux SGBD sont créés et SQL devient un langage standard.

Question 2

1 - BDD - Transactions

De quoi est composée une base de données ?

Answer 2

• Un schéma, qui structure les données
• Du contenu, qui remplit la base de données
• Des contraintes d’intégrité qui assurent la cohérence de la BDD.

Question 3

0 - BDD - Introduction

Quelles sont les qualités des SGBD modernes ?

Answer 3

• Ils sont fiables et très stables.
• Ils sont performants et permettent de gérer de gros volumes de données.
• Ils sont durables car ils assurent la qualité des données.

Question 4

0 - BDD - Introduction

A quoit sert une contrainte d’intégrité ? Explicitez les différents types de contraintes.

Au moins 2

Answer 4

Les contraintes d’intégrité permettent de définir des limitations sur le contenu de la base de données.

• Contraintes explicites : elles sont stockées dans le SGBD et peuvent être vérifiées automatiquement à chaque modification du contenu.
• Contraintes implicites : elles sont dans la tête de l’administrateur de la base de données.

Question 5

0 - BDD - Introduction

Qu’est-ce qu’une super-clé ?

Answer 5

Soit K un sous-ensemble de colonnes d’une table T.

K est une super-clé si elle permet d’identifier de manière unique au plus une seule ligne de T. C’est à dire si le nombre de ligne ayant les mêmes valeurs sur les colonnes de K est au plus un.

Question 6

0 - BDD - Introduction

Qu’est-ce qu’une clé candidate ?

Answer 6

Soit K un sous-ensemble de colonnes d’une table T.

Une clé candidate, K, est une super-clé qui contient un nombre minimal de colonnes.

Question 7

0 - BDD - Introduction

Qu’est-ce qu’une clé étrangère ?

Answer 7

Une clé étrangère est un ensemble de colonnes K d’une table faisant référence à la clé primaire d’une autre table. La clé étrangère est satisfaite si les tuples de valeurs présents sur les colonnes de K sont aussi présents sur les colonnes de la clé primaire

Question 8

0 - BDD - Introduction

Qu’est-ce qu’une clé primaire ?

Answer 8

Soit K un sous-ensemble de colonnes d’une table T.

Une clé primaire est une clé candidate choisie pour identifier chaque ligne de T.

Question 9

0 - BDD - Introduction

Qu’est-ce qu’une base de données cohérente ?

Answer 9

Une base de données est cohérente si son contenu vérifie à la fois les contraintes explicites et implicites.

Question 10

1 - BDD - Transactions

Qu’est-ce qu’une transaction ?

Answer 10

Une transaction est un exécution d’un programme contenant plusieurs requêtes sur la base de données.

Question 11

1 - BDD - Transactions

Quel est le principe des transactions ?

Answer 11

Si un transaction s’exécute en l’absence d’autres transactions ou d’erreurs sur une base de données cohérente, alors la base de données à la fin de l’exécution est aussi cohérente.

Question 12

1 - BDD - Transactions

Qu’est-il nécessaire de mettre en place pour gérer les transactions ?

Answer 12

• Une gestion des interactions entre transactions.
• Une gestion des erreurs systèmes.

Question 13

1 - BDD - Transactions

Que définissent les transactions ?

Answer 13

Les transactions définissent les transformations valides de la base de données.

Question 14

1 - BDD - Transactions

Quand les contraintes d’intégrité sont-elles vérifiées ?

Answer 14

Par défaut, elles sont vérifiées à chaque requête à la BDD.

Question 15

1 - BDD - Transactions

Définissez l’acronyme ACID.

Answer 15

Atomique, Cohérente, Isolée, Durable

Question 16

1 - BDD - Transactions

Qu’est-ce que le principe d’atomicité d’une transaction ?

Answer 16

Une transaction est une suite d’opérations insécable. Elle ne peut avoir que trois états :

• Active : en cours d’exécution
• Validée (committed) : succès
• Annulée (aborted) : échec

Question 17

1 - BDD - Transactions

Que se passe-t-il lorsqu’une transaction est annulée ?

Answer 17

Lorsqu’un transaction est annulée, il faut défaire les changements apportés à la base de données et à son contenu, on effectue un rollback

Question 18

1 - BDD - Transactions

Décrivez le mécanisme de rollback.

Answer 18

Généralement, celui-c fonctionne sur le mécanisme de journalisation.

On journalise les données

Question 19

1 - BDD - Transactions

Q’est-ce que le principe de cohérence d’une transaction ?

Answer 19

Quelle que soit l’exécution des transactions, la BDD doit rester cohérente.

Question 20

1 - BDD - Transactions

Qu’est-ce que le principe d’irrévocabillité ?

Answer 20

L’irrévocabilité c’est le fait de ne pas pouvoir révoquer, dans notre cas, les décisions de commit et de rollback sont irrévocables. C’est à dire qu’une fois la transaction validée ou annulée, on ne peut plus changer son statut.

Question 21

1 - BDD - Transactions

Quelles sont les opérations irrévocables au sein d’une transaction SQL ?

Answer 21

Les opérations de commit et de rollback sont irrévocables. Elles terminent un transaction.

Aussi, les écritures sont irrévocables une fois une transaction terminée. Elles sont donc révoquables tant que celle-ci est active.

Question 22

1 - BDD - Transactions

Qu’est-ce que le principe de durabilité d’une transaction ?

Answer 22

Les effets d’une transaction validée sont persistants. Ils sont stockés sur le disque et persistants même en cas de panne 1ms après la validation de la transaction.

Cette propriété est garantie par la journalisation et permet une reprise après panne, sans pertes de données :

• Le journal est un fichier sur le disque.
• Le SGBD stocke toutes les modifications faites par les transactions.
• Les ordres de commit sont journalisées.

Question 23

1 - BDD - Transactions

Pourquoi différer la validation des contraintes d’intégrité ?

Answer 23

Différer la validation des contraintes d’intégrité à la fin d’une transaction permet d’avoir un état incohérent de la base de données au sein de la transaction, mais cohérent une fois celle-ci validée, ou annulée le cas échéant.

Question 24

1 - BDD - Transactions

Quels sont les différents moyens pour différer la validation des contraintes d’intégrité ?

Answer 24

• NOT DEFERABLE : la validation ne peut être différée.
• DEFERABLE INITIALLY IMMEDIATE : différée si précisée.
• DEFERABLE INITIALLY DEFERED : différée par défaut.

On ajoute ce mot clé à la suite d’une contrainte, comme : UNIQUE (id) DEFERABLE INITIALLY IMMEDIATE

Question 25

1 - BDD - Transactions

Quest-ce qu’une lecture impropre ?

Answer 25

Une lecture impropre (dirty read) survient lorsqu’une transaction lit une donnée écrite par une autre transaction pas encore validée.

Question 26

1 - BDD - Transactions

Quels sont les risques d’une lecture impropre ?

Answer 26

Le risque est que la transaction qui a écrit la donnée que l’on vient de lire peut être annulée ou ré-écrire la donnée. La transaction qui a lu cette donnée peut alors prendre des décisions qui ne sont pas cohérentes avec un état valide de la BDD.

Question 27

1 - BDD - Transactions

Qu’est-ce que le principe d’isolation d’une transaction ?

Answer 27

Les transactions doivent modifier la base de données comme si elles étaient chacune exécutées seules.

• Une transaction ne doit pas révéler ses modifications aux autres transactions tant qu’elle est active.
• Les transactions exécutées en parallèle peuvent engendrer des problèmes de cohérence.
• Des conflits entre les transactions peuvent entraîner l’annulation de certaines transactions.

Question 28

1 - BDD - Transactions

Qu’est-ce qu’une lecture non reproductible ?

Answer 28

Une lecture non reproductible ce sont en réalité deux lectures d’un état valide de la BDD qui vont retourner un résultat différent à cause d’une modification concurrente.

Question 29

1 - BDD - Transactions

Quels sont les deux niveaux d’isolation ? Est-il possible que des lectures impropres surviennent ? Des lectures non reproductibles ?

Answer 29

• READ COMMITED : aucunes lectures impropres, mais les lectures non reproductibles peuvent arriver.
• SERIALIZABLE : ni l’un, ni l’autre ne peuvent arriver.

On le définit à chaud dans la session avec : SET TRANSACTION ISOLATION LEVEL {READ COMMITED|SERIALIZABLE}

Question 30

1 - BDD - Transactions

Quel est le niveau d’isolation par défaut de Oracle ?

Answer 30

READ COMMITED

Question 31

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’une exécution concurrente ?

Answer 31

Une exécution concurrente est une suite d’opérations effectuées par une ou plusieurs transactions.

Question 32

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’une exécution en série ?

Answer 32

Une exécution est en série si toutes les opérations de chaque transaction sont exécutées de manière consécutive.

Question 33

2 - BDD - Gestion de la concurrence

Comment note-t-on l’exécution en série de deux transactions T₁ et T₂ ?

Answer 33

(T₁, T₂)

Question 34

2 - BDD - Gestion de la concurrence

Que signifie que les transactions T₁ et T₂ sont équivalentes ?

Answer 34

Cela signifie qu’elles ont le même effet sur toutes les bases de données.

Question 35

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’une exécution sérialisable ?

Answer 35

Une exécution E est sérialisable s’il existe une exécution E’ en série telle que E et E’ sont équivalentes.

Question 36

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’un conflit ?

Answer 36

On parle de conflit entre deux opérations consécutives d’une exécution lorsque leur ordre ne peut être inversé sans changer l’effet de cette exécution.

Question 37

2 - BDD - Gestion de la concurrence

Quelles sont les paires d’opérations qui ne présentent pas de conflit ? Il y en a trois.

Answer 37

Soient i et j deux entiers tels que i ≠ j et T_i et T_j deux transactions.

Il n’y a pas de conflit entre les opérations suivantes :

1. read_i(X) et read_j(X), même lorsque i = j ;
2. read_i(X) et write_j(Y) si X ≠ Y ;
3. write_i(Y) et write_j(X) si X ≠ Y ;

Question 38

2 - BDD - Gestion de la concurrence

Que signifie pour deux transactions d’être équivalentes par conflit ?

Answer 38

Deux transactions sont équivalentes par conflit si on peut passer de l’une à l’autre en inversant des opérations consécutives.

Question 39

2 - BDD - Gestion de la concurrence

Que signifie pour une exécution d’être sérialisable par conflit ?

Answer 39

Une exécution est sérialisable par conflit si elle est équivalente par conflit à une exécution en série.

Une exécution sérialisable par conflit est sérialisable.

Question 40

2 - BDD - Gestion de la concurrence

Quelle est la définition de précédence ?

Formellement

Answer 40

Au sein d’une exécution E, une transaction T_i précède la transaction T_j si, pour deux opérations O_i ∈ T_i et O_i ∈ T_j on a :

1. O_i précède O_j dans E.
2. O_i et O_j concernent le même élément de la base de données.
3. l’une ou l’autre est une écriture.

Question 41

2 - BDD - Gestion de la concurrence

Expliquez le principe de précédence ? Qu’est-ce que cela veut réellement dire si l’on prend deux transactions T_i et T_j de E et que T_i précède T_j ?

Avec vos mots.

Answer 41

Si l’on sait que deux transactions T_i et T_j se précèdent au sein d’une exécution E, alors dans toute exécution en série équivalente par conflit à E, on est certain que T_i sera exécutée avant T_j.

Question 42

2 - BDD - Gestion de la concurrence

Peut-on inverser deux opérations O_i et O_j dans une transaction E si l’on sait que : T_i ≺_E T_j

Answer 42

Non puisque l’on sait que quelque soit l’exécution équivalente par conflit à E, O_i sera toujours avant O_j.

C’est bien le principe de précédence.

Question 43

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’un graphe de précédence ?

Avec vos mots.

Answer 43

Un graphe de précédence ordonne les transactions et permet de déterminer si un exécution est sérialisable par conflit.

Il s’agit d’un graphe orienté où :

1. Les sommets du graphe sont les transactions de E.
2. Il y a une arête entre deux transactions T_i et T_j si T_i précède T_j

Formellement, on a : G = {V = {T_i ∈ E}, E = {(T_i, T_j) ∈ E² | T_i ≺_E T_j}}

Question 44

2 - BDD - Gestion de la concurrence

A partir d’un graphe de précédence G d’une exécution E, comment déterminer si cette exécution est sérialisable ?

Answer 44

Soit E un exécution et G son graphe de précédence.

L’exécution E est sérialisable par conflit si et seulement si son graphe de précédence G est acyclique.

Question 45

2 - BDD - Gestion de la concurrence

Soit G un graphe acyclique et E un exécution dont le graphe de précédence est G.

Peut-on déterminer facilement un ensemble d’exécutions en série équivalentes par conflit à E ?

Answer 45

Soit G le graphe de précédence de l’exécution E.

E est équivalente à toute exécution en série de ses transactions dès lors que si (T_i, T_j) est une arête de G, alors T_i est exécutée avant T_j.

Question 46

2 - BDD - Gestion de la concurrence

A quoi servent les verrous ?

Answer 46

Les verrous servent à différer certaines opérations pour conserver la sérialisabilité des transactions.

Question 47

2 - BDD - Gestion de la concurrence

Quels sont les différents vérrous existants ?

Answer 47

• Verrou partagé (shared) : nécessaire pour lire un élément ;
• Verrou exclusif (exclusive) : néecessaire pour écrire un élément ;

De manière abstraite, on note :

• s_i(X) : la transaction T_i obtient un verrou partagé sur l’élément X.
• x_i(X) : la transaction T_i obtient un verrou exclusif sur l’élément X.
• u_i(X) : la transaction T_i relâche ses verrous sur l’élément X.

Question 48

2 - BDD - Gestion de la concurrence

Comment assurer un bon usage des verrous ?

Answer 48

Sur chaque transaction T_i :
* Une lecture r_i(X) ne peut être exécutée que si T_i a un verrou quelconque sur X.
* Une écriture w_i(X) ne peut être exécutée que si T_i a un verrou exclusif sur X.
* Tous les verrous obtenus sont libérés avant la fin de la transaction.

Un élément X de la base de données peut être :
* Soit verouillé de manière exclusive par une unique transaction.
* Soit verouillé de manière partagée par plusieurs transactions.

Question 49

2 - BDD - Gestion de la concurrence

Si l’on applique deux verrous, l’un partagé et l’autre exclusif, lequel primera ?

Answer 49

Le verrou exclusif.

Question 50

2 - BDD - Gestion de la concurrence

Expliquez le protocole de Verouillage en deux phases.

Answer 50

1. Aquisition des verrous ;
2. Relachement des verrous ;

Tous les verrous sont déposés avant le relâchement du premier verrou.

Question 51

2 - BDD - Gestion de la concurrence

Que se passe-t-il lorsqu’une transaction A verrouille un élément X et qu’un transaction B verrouille ensuite ce même élément X.

Answer 51

La transaction B n’obtient pas le verrou et attend le relâchement du verrou de la transaction A.

Question 52

2 - BDD - Gestion de la concurrence

Quel est le risque du protocole 2PL ?

Donnez grossièrement un exemple.

Answer 52

Il y a un risque d’interblocage (deadlock), c’est à dire que des transactions sont forcées d’attendre indéfiniment un verrou obtenu par une autre transaction.

Exemple : Une transaction A verrouille un élément X₁, puis une transaction B verrouille un élément X₂. Si A demande un verrou sur X₂ et B sur X₁, alors c’est un deadlock.

Question 53

2 - BDD - Gestion de la concurrence

Qu’est-ce qu’une exécution réparable ?

Answer 53

Une exécution est réparable si toutes les transactions sont validées après les transactions dont elle a lu les données modifiées.

Question 54

2 - BDD - gestion de la concurrence

Qu’est-ce qu’une exécution sans annulation en cascade ?

Answer 54

Une exécution est sans annulation en cascade (SAC) si toute les transactions lisent des valeurs modifiées issues uniquement de transactions qui sont déjà validées.

Question 55

2 - BDD - gestion de la concurrence

De quelles propriétés bénéficient les exécutions sans annulation en cascade.

Answer 55

Si une exécution est sans annulation en cascade, alors elle est réparable. La réciproque n’est pas vraie.

Question 56

2 - BDD - gestion de la concurrence

Qu’est-ce qu’une exécution stricte ?

Answer 56

Une exécution avec verrous est stricte si dans chaque transaction, aucun verrou exclusif n’est relâché avant que la transaction ne soit validée ou annulée.

Question 57

2 - BDD - gestion de la concurrence

De quelles propriétés bénéficient les exécutions strictes ?

Answer 57

Une exécution stricte est sérialisable et sans annulation en cascade.

Question 58

2 - BDD - gestion de la concurrence

Faites un schéma ensembliste des classes d’exécutions.

Answer 58

En série ⊂ Stricte ⊂ SAC ⊂ Réparable

Une partie des SAC sont sérialisables.
Une partie des réparables sont sérialisables.