|
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! |