Versioned finite-state machines with Postgres (2019)

Wouldn't that risk some FSM getting modified while it's 'running'? That may or may not be desirable I guess. Eg. a customer not knowing that the process changed since they placed an order and not understanding the process anymore

Hmm… consider the following. Your FSM is acyclic iff you can assign each state an integer depth such that a state at depth d only ever transitions to states at depths strictly greater than d. So consider the following tables:

    CREATE TABLE states (
        state order_state PRIMARY KEY,
        depth int NOT NULL,
        UNIQUE(state, depth)
    );
    CREATE TABLE transitions (
        start_state order_state NOT NULL,
        event order_event NOT NULL,
        end_state order_state NOT NULL,
        start_depth int NOT NULL,
        end_depth int NOT NULL,
        CONSTRAINT transitions_start_depth_correct
            FOREIGN KEY(start_state, start_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_end_depth_correct
            FOREIGN KEY(end_state, end_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_depth_increases CHECK(end_depth > start_depth),
        PRIMARY KEY(start_state, event)
    );

Let's bang on it for a quick test. You can define a state machine; here's one that roughly matches the regex `^(AB|BA)$` (I know I'm being a bit sloppy):

    fsm=> CREATE DOMAIN order_state AS text;
    CREATE DOMAIN
    fsm=> CREATE DOMAIN order_event AS text;
    CREATE DOMAIN
    fsm=> -- "CREATE TABLE"s as above, then:
    fsm=> INSERT INTO states(state, depth) VALUES('start', 1), ('a', 2), ('b', 2), ('done', 3), ('error', 3);
    INSERT 0 5
    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('start', 'A', 'a', 1, 2), ('start', 'B', 'b', 1, 2), ('a', 'B', 'done', 2, 3), ('b', 'A', 'done', 2, 3), ('a', 'A', 'error', 2, 3), ('b', 'B', 'error', 2, 3);
    INSERT 0 6

And, as you need to modify it, you can increase a node's depth to make room for intervening nodes:

    fsm=> UPDATE states SET depth = 4 WHERE state = 'error';
    UPDATE 1
    fsm=> TABLE transitions;
     start_state | event | end_state | start_depth | end_depth 
    -------------+-------+-----------+-------------+-----------
     start       | A     | a         |           1 |         2
     start       | B     | b         |           1 |         2
     a           | B     | done      |           2 |         3
     b           | A     | done      |           2 |         3
     a           | A     | error     |           2 |         4
     b           | B     | error     |           2 |         4
    (6 rows)

But you can't decrease a node's depth too far:

    fsm=> UPDATE states SET depth = 2 WHERE state = 'error';
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (a, A, error, 2, 2).
    CONTEXT:  SQL statement "UPDATE ONLY "public"."transitions" SET "end_state" = $1, "end_depth" = $2 WHERE $3::pg_catalog.text OPERATOR(pg_catalog.=) "end_state"::pg_catalog.text AND $4 OPERATOR(pg_catalog.=) "end_depth""

And you can't introduce transitions that don't increase depth:

    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('done', 'AGAIN!', 'start', 3, 1);
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (done, AGAIN!, start, 3, 1).

Now, I don't know that I would immediately recommend this for high-throughput production use. You're storing "unnecessary" state not once but many times (each state's depth appears `1 + \deg(v)` times), plus additional indices and lookups. But I do think it meets the desired consistency goals!