SYSTÈMES INFORMATIQUES Systèmes de gestion de bases de données

Accès concurrent et transactions

La notion d'accès concurrent décrit la situation où plusieurs applications veulent accéder à la même donnée en même temps. Par exemple, il est possible que deux applications bancaires accèdent simultanément au compte du même client (à la même donnée). Si les accès sont conflictuels, c'est-à-dire si au moins une des deux applications veut modifier le compte, le S.G.B.D. doit réagir afin d'éviter que la base de données se trouve dans un état incohérent à la fin des opérations. Le groupement d'opérations en transactions permet une vision cohérente des données.

Une transaction rassemble un ensemble d'opérations qui doivent toutes avoir la même vision d'une base de données. Ainsi, deux opérations successives de lecture du compte d'un client à l'intérieur d'une transaction doivent retourner la même valeur sans être dérangées par des opérations d'écriture par une autre transaction.

Les applications sont ainsi perçues par le S.G.B.D. comme un ensemble de transactions indépendantes auxquelles il doit fournir un accès cohérent aux données. Cette cohérence est formalisée par la notion de sérialisabilité.

L'exécution des opérations d'un ensemble de transactions est sérialisable s'il existe un ordre (partiel) < entre les transactions tel que toutes les opérations d'une transaction T qui sont en conflit avec les opérations d'une autre transaction T' < T, sont exécutées après ces opérations (deux opérations, comme on l'a dit, sont en conflit si elles accèdent à la même donnée et si au moins une opération est une écriture).

On peut montrer que chaque transaction dans un ensemble sérialisable peut posséder une vision différente des données, mais que chacune de ces visions est cohérente. Pour augmenter le débit transactionnel et réduire l'attente des utilisateurs, les opérations de transactions concurrentes sont interclassées, mais, pour une transaction, tout se passe comme si l'exécution des transactions concurrentes était séquentielle. Pour vérifier la sérialisabilité de l'exécution d'un ensemble de transactions, on peut construire un graphe de sérialisabilité.

Le graphe de sérialisabilité d'une séquence d'opération lectures/écritures effectuées par un ensemble de transactions contient un nœud pour chaque transaction et relie deux transactions différentes T' et T par un arc T'→ T si une opération effectuée par T' est en conflit avec une opération effectuée après par T.

On peut montrer que les transactions de l'ensemble sont sérialisables si ce graphe ne contient pas de cycle (fig. 3).

Le S.G.B.D. ne doit pas seulement vérifier la sérialisabilité d'un ensemble de transactions, mais également réagir quand il détecte que cette propriété est violée. Le verrouillage à deux phases est une des techniques utilisées qui garantissent la sérialisabilité.

Avant d'effectuer une opération sur une donnée (n-uplet, table), une transaction T doit demander un verrou au gestionnaire de transactions du S.G.B.D. Si la donnée est déjà verrouillée par une autre transaction T' pour une opération conflictuelle (par exemple pour une écriture), la transaction T est obligée d'attendre le relâchement du verrou par la transaction T'. Si on applique ce protocole en imposant qu'une transaction qui a déjà relâché un verrou ne peut plus en demander d'autres, on parle d'un protocole de verrouillage à deux phases et on peut montrer que l'exécution des opérations obtenue est sérialisable.

Ce protocole n'évite pas le problème d'interblocage (deux transactions attendent mutuellement le relâchement d'un verrou), qui doit être traité par le contrôleur de concurrence.