4 ms·

I always wondered about this, a while ago I saw a library similar to this that modeled FSMs in Postgres, and had a comment saying "todo: cycle detection". And m

• wchargin 2y ago
  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!
  • zinclozenge 2y ago
    Amazing! I also learned about domains with your comment.