Introduction

Lors de ma dernière mission, une question intéressante a été soulevée : est-il possible de gérer la gestion des événements dans la base de données ? Nous travaillions avec des objets qui étaient sujets à de multiples événements au cours de leur durée de vie. Pour simplifier les choses, nous allons prendre comme exemple tout au long de cet article un modèle simple dans lequel les objets sont des personnes auxquelles les états "Né", "Marié", "Divorcé" et "Mort" peuvent être associés.

Le but ici est de créer un modèle de données dans lequel on peut encoder un automate en renseignant les états possibles et les transitions existantes entre ces états. Nous pourrons aussi décrire des "mots" du langage accepté par cet automate, c'est-à-dire la "vie" d'un objet sans qu'il soit possible d'introduire d'erreurs. Avec notre exemple, le premier état doit nécessairement être "Né", suivi d'une séquence potentiellement nulle de couples "Marié, Divorcé", d'un éventuel état "Marié" et pour finir d'un éventuel dernier état "Mort".

Dialecte

J'utiliserai PostgreSQL pour illustrer la solution à cette problématique. Mais il est possible de la transposer dans les autres principaux SGBDR (Système de Gestion de Base de Données Relationnel) sans problèmes. La raison pour laquelle j'aime utiliser PostgreSQL quand je produis des articles est qu'il supporte les transactions comportant du DDL, ce qui me permet de mettre tout mon code entre START TRANSACTION; et ROLLBACK;. Pour le moment rares sont les autres SGBDR qui supportent cette fonctionnalité.

Types d'états

La première chose à modéliser est une table comportant les types d'états possibles. Pas de surprise ici : Un état est défini par un id entier et un nom. Bien sûr une application réelle aurait probablement d'autres informations associées aux états, par exemple un fichier joint, un document JSON ou autre. Il s'agit d'ailleurs d'un bon cas d'utilisation des tables héritées en PostgreSQL. Mais dans le cadre de cet article, ces détails ne feraient qu'alourdir le code.

CREATE TABLE status_type (
    id SERIAL NOT NULL PRIMARY KEY,
    name VARCHAR(50) NOT NULL,
    initial BOOLEAN NOT NULL DEFAULT FALSE
);

Transitions

Maintenant qu'il est possible d'encoder les types d'états, il reste à encoder les transitions possibles, c'est-à-dire quels états peuvent survenir après chaque type d'état. J'utilise pour cela une table "transitions", qui est à nouveau simpliste. Dans une application réelle, il y aurait probablement des données associées aux transitions.

CREATE TABLE transition (
    status_id_from INT NOT NULL REFERENCES status_type,
    status_id_to INT NOT NULL REFERENCES status_type,
    PRIMARY KEY (status_id_from, status_id_to)
);

Pour les plus visuels comme moi, les états et transitions définis correspondent à l'automate suivant. La première flèche indique le point d'entrée de l'automate (`initial = true` dans la table `status_type`).

Le bloc de code suivant indique comment encoder cet automate dans les tables que nous venons de créer. Les identifiants des quatre états de notre exemple doivent être stockés dans des variables. Pour cela, la manière la plus simple est d'utiliser un bloc DO.

DO $$
    DECLARE
        born INT;
        married INT;
        divorced INT;
        dead INT;
    BEGIN

        INSERT INTO status_type (key, initial) VALUES ('Born', true) RETURNING id INTO born;
        INSERT INTO status_type (key) VALUES ('Married') RETURNING id INTO married;
        INSERT INTO status_type (key) VALUES ('Divorced') RETURNING id INTO divorced;
        INSERT INTO status_type (key) VALUES ('Dead') RETURNING id INTO dead;

        INSERT INTO transitions (status_id_from, status_id_to) VALUES
        (born, married), (born, dead),
        (married, divorced), (married, dead),
        (divorced, married), (divorced, dead);

    END;
$$ LANGUAGE plpgsql;

États

Le point crucial du schéma est d'avoir une table des états associés à un objet dans laquelle on ne puisse pas entrer de données qui ne respectent pas les règles suivantes :

• Le premier état associé à chaque objet doit être un état initial;
• Pour chaque état, la transition de l'état précédent à l'actuel doit exister dans la table transitions;
• Chaque état doit exister dans la table status_type;
• Chaque état ne peut être suivi que par un seul état au maximum.

Comme point de départ, il est évident que la table "status" devra contenir l'identifiant de l'objet auquel il se rattache et l'état actuel. Nous allons associer à chaque état le numéro d'état dans la séquence de vie de l'objet (j'ai choisi de démarrer la numérotation à 1 de manière arbitraire : zéro aurait été un choix tout à fait valable également, 42 un peu moins même si je dois bien avouer y avoir pensé).

CREATE TABLE status (
    id SERIAL NOT NULL,
    story_id INT NOT NULL,

    story_status_number INT NOT NULL CHECK (value > 0),
    status_type_id INT NOT NULL REFERENCES status_type,

    PRIMARY KEY (story_id, story_status_number)
);

De cette manière, les deux dernières conditions sont vérifiées : la clé étrangère assure que les états existent et la clé primaire empêche d'avoir deux états avec le même numéro dans la séquence de vie d'un objet. Satisfaire les deux autres conditions ne sera pas si simple.

Le premier état doit être initial

L'idée est d'avoir une clé étrangère vers status_type quand le numéro dans la séquence de vie de l'objet est 1. Cela a deux implications :

• Il faut une colonne booléenne dans status qui indique si story_status_number vaut 1;
• Il faut une clé unique sur (id, initial) dans la table status_type.

CREATE TABLE status_type (
    id SERIAL NOT NULL PRIMARY KEY,
    name VARCHAR(50) NOT NULL,
    initial BOOLEAN NOT NULL DEFAULT FALSE,
    UNIQUE (id, initial)
);

CREATE TABLE status (
    id SERIAL NOT NULL,
    story_id INT NOT NULL,

    story_status_number INT NOT NULL CHECK (value > 0),
    status_type_id INT NOT NULL REFERENCES status_type,
    initial BOOLEAN GENERATED ALWAYS AS (NULLIF(story_status_number = 1, FALSE)) STORED,

    PRIMARY KEY (story_id, story_status_number),
    FOREIGN KEY (status_type_id, initial) REFERENCES status_type (id, initial)
);

La colonne initial est générée. Le modèle exposé à l'utilisateur n'est donc pas plus compliqué qu'avant (c'est toujours une bonne chose de garder les choses simples pour l'utilisateur). Si vous vous demandez pourquoi le NULLIF, c'est parce que je ne veux pas vérifier la clé étrangère pour les états non-initiaux. Par défaut les vérifications de clé étrangères se font en MATCH SIMPLE, donc si au moins une valeur est NULL, la clé étrangère n'est pas vérifiée.

Remarquez que les deux clés étrangères ont leur utilité : L'une vérifie que l'état existe dans la table status_type et l'autre vérifie que l'état est initial.

L'état précédent doit être correct

Pour commencer, il n'existe actuellement aucun moyen de faire une contrainte par rapport à l'état précédent lié à l'objet, comme par exemple "Soit R la ligne courant de status et X la ligne de la table status telle que l'état de X.story_id = R.story_id et X.story_status_number + 1 = R.story_status_number.

Il faudra donc nécessairement avoir dans la table status le status_type et le story_status_number de l'état précédent. Le story_status_number peut être calculé automatiquement grâce à une colonne générée (1). L'autre colonne devra par contre être fournie directement (2). Nous pouvons toutefois vérifier que la donnée existe bien dans la table status grâce à une clé étrangère (3); à condition de rajouter une clé unique sur les colonnes référencées (4). Il ne nous manquera alors plus qu'une clé étrangère vers la table transitions pour vérifier que la transition est permise (5). Pour finir, nous forçons status_type_previous_id à être NULL pour les états initiaux (6).

CREATE TABLE status (
    id SERIAL NOT NULL,
    story_id INT NOT NULL,

    story_status_number INT NOT NULL CHECK (value > 0),
    status_type_id INT NOT NULL REFERENCES status_type,
    initial BOOLEAN GENERATED ALWAYS AS (NULLIF(story_status_number = 1, FALSE)) STORED,

    story_status_previous_number INT GENERATED ALWAYS AS (NULLIF(story_status_number - 1, 0)) STORED, -- 1
    story_type_previous_id INT REFERENCES status_type, -- 2

    PRIMARY KEY (story_id, story_status_number),
    FOREIGN KEY (status_type_id, initial) REFERENCES status_type (id, initial)

    UNIQUE (story_id, story_status_number, status_type_id), -- 4
    FOREIGN KEY (story_id, story_status_previous_number, status_type_previous_id) REFERENCES status (story_id, story_status_number, status_type_id), -- 3
    FOREIGN KEY (status_type_previous_id, status_type_id) REFERENCES transitions, -- 5
    CHECK (CASE WHEN status_type_initial THEN status_type_previous_id IS NULL ELSE TRUE END) -- 6
);

Tests

Il est maintenant temps de vérifier qu'il est possible d'insérer des données correctes dans notre table status, et qu'il est impossible d'insérer des données incorrectes. Nous allons procéder méthodiquement en violant le moins possible chacune des quatre contraintes énoncées ci-dessus.

Ces tests vont dans le bloc DO que nous avons commencé plus haut, afin d'avoir accès aux variables born, married, divorced et dead.

Happy path

INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
(1, 1, null, born),
(1, 2, born, married),
(1, 3, married, divorced),
(1, 4, divorced, married),
(1, 5, married, dead),

(2, 1, null, born),
(2, 2, born, dead);

Le premier état associé à chaque objet doit être un état initial

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (3, 1, born, born);
EXCEPTION WHEN check_violation THEN RAISE NOTICE 'Correctly failing when before-first status is not null.'; END;

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (4, 1, null, married);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when inserting non-initial status.'; END;

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (5, 2, born, married);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when missing status number 1.'; END;

Pour chaque état, la transition de l'état précédent à l'actuel doit exister dans la table transition

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (6, 1, null, born),
    (6, 2, born, divorced);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when using an non-existent transition.'; END;

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (7, 1, null, born),
    (7, 2, married, divorced);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when not respecting the previous state.'; END;

Chaque status doit exister dans la table status_type

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (8, 1, null, born),
    (8, 2, born, (SELECT MAX(id) FROM status_type) + 1);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when inserting non-positive status number.'; END;

Chaque état ne peut être suivi que par un état au plus

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (9, 1, null, born),
    (9, 2, born, married),
    (9, 2, born, dead);
EXCEPTION WHEN unique_violation THEN RAISE NOTICE 'Correctly failing when transitioning to two states.'; END;

BEGIN
    INSERT INTO status (story_id, story_status_number, status_type_previous_id, status_type_id) VALUES
    (10, 0, null, born);
EXCEPTION WHEN foreign_key_violation THEN RAISE NOTICE 'Correctly failing when inserting non-positive status number.'; END;

Article de Joe Celko

En écrivant le code lié à cet article, je ne savais pas si ce que je voulais faire était réellement possible. Après m'être rendu compte que oui, j'ai cherché d'autres articles traitant du même sujet. Il s'avère que Joe Celko, dont j'apprécie énormément le travail, a consacré un article à ce sujet il y a une dizaine d'années !

Nous n'arrivons pas aux mêmes résultats. Notamment, il n'a pas utilisé des contraintes pour s'assurer que les transitions étaient bien respectées, mais a utilisé une série de procédures stockées qui insèrent des données correctes et vérifient que les données respectent les règles imposées.

Dans ce sens, je préfère ma solution. Ceci dit, il y a dix ans, les colonnes générées étaient très peu répandues : seul Oracle supportait cette construction. Insérer toutes les données manuellement aurait été théoriquement possible mais très peu pratique pour l'utilisateur du schéma. Je pense donc que sa solution était la meilleure à l'époque, mais que la situation a changé et que mon article est une extension du sien avec les nouvelles techniques disponibles. Un autre aspect que je préfère dans ma solution est que dans la table status, les états pré-initiaux sont NULL et pas l'état initial lui-même.

J'ai d'ailleurs changé mon exemple et repris le même que le sien pour arriver dans cette esprit de continuité de son article.

Conclusion

Il nous reste à répondre à la question : Est-ce une bonne idée de modéliser un automate à l'aide d'une base de données ?

Je pense que les automates sont généralement créés, utilisés puis jetés dans un délai très court. Lorsqu'on veut garder un automate plus longtemps, c'est souvent parce que la construction de l'automate a pris du temps et qu'on cherche à améliorer les performances. Dans ce contexte, une base de données n'est sans doute pas toujours le meilleur outil.

Toutefois, il existe des situations dans lesquelles utiliser une base de données pour cet usage a tout à fait du sens, par exemple si les automates sont construits par des utilisateurs d'une application et qu'on veut s'assurer qu'ils ne fassent pas n'importe quoi (même si vous me direz, avec raison à 100%, que les utilisateurs de nos applications finiront toujours par nous surprendre, quelles que soient les sécurités qu'on mette en place).

Dans tous les cas, l'exercice est intéressant et les utilisations arriveront peut-être un jour, qui sait ? En attendant, je m'intéresse en ce moment au TDD appliqué aux bases de données (notamment PostgreSQL avec pgTAP), et réimplémenter le code de cet article en utilisant cette méthodologie me semble un kata tout à fait intéressant ! Cela fera d'ailleurs probablement l'objet d'un prochain article :)

$ psql -f events.sql
START TRANSACTION
CREATE TABLE
CREATE TABLE
CREATE TABLE
psql:events.sql:110: NOTICE:  Correctly failing when before-first status is not null.
psql:events.sql:110: NOTICE:  Correctly failing when inserting non-initial status.
psql:events.sql:110: NOTICE:  Correctly failing when using an non-existent transition.
psql:events.sql:110: NOTICE:  Correctly failing when not respecting the previous state.
psql:events.sql:110: NOTICE:  Correctly failing when transitioning to two states.
psql:events.sql:110: NOTICE:  Correctly failing when missing status number 1.
psql:events.sql:110: NOTICE:  Correctly failing when inserting a non-existent status type.
DO
ROLLBACK

Merci de m'avoir lu jusqu'ici ! N'hésitez pas à m'envoyer un message en privé pour me faire part de vos remarques !