Vasya’s study history and state machine in SQL

After speaking at PgConf2023 and talking to database professionals, I had time over the weekend to implement an idea on how to implement state machine logic in SQL in PostgreSQL. The idea is applicable to any DBMS that supports user-defined aggregate functions.

Soon the fairy tale is told, but the deed is not soon done … Once upon a time there was Vasya. And the foundations in the society where he lived were described using a state machine. A state machine of wisdomfinite state machine (FSM) was given as a jump table, in TSV format:

0	0	появился на свет
0	1	ходит в детсадик	age>=3 and desire_to_learn
1	2	ученик начальной школы	age>=7 and exams is null and desire_to_learn
2	3	ученик средней школы	age>=11 and exams is null and desire_to_learn
3	4	основное общее образование	age>=15 and exams="выпускные экзамены в 9 классе"
4	5	ученик старших классов	age>=15 and desire_to_learn
5	6	среднее общее образование	age>=17 and exams="выпускные экзамены в 11 классе"
4	7	учащийся техникума	age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn
7	8	среднее профессиональное образование	age>=18 and exams="защита диплома"
6	9	учащийся института	age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
8	9	учащийся института	age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
9	10	оконченное высшее образование	age>=22 and exams="защита диплома" and desire_to_learn
10	11	аспирант	age>=22  and exams="экзамены в аспирантуру" and desire_to_learn
11	12	претендент на ученую степень	age>=24 and exams="кандидатский минимум" and desire_to_learn
12	13	кандидат наук	age>=25 and exams="защита диссертации" and desire_to_learn
4	14	больше не обучается	not(desire_to_learn)
6	14	больше не обучается	not(desire_to_learn)
8	14	больше не обучается	not(desire_to_learn)
10	14	больше не обучается	not(desire_to_learn)
13	14	больше не обучается	not(desire_to_learn)

And the chroniclers wrote down his life in the form of a table in tab separated value format and loaded into PostgreSQL:

# CREATE TABLE life( name text, age int, desire_to_learn boolean, exams text, CONSTRAINT pk_life PRIMARY KEY (name,age));

# \d life
                    Table "public.life"
     Column      |  Type   | Collation | Nullable | Default 
-----------------+---------+-----------+----------+---------
 name            | text    |           | not null | 
 age             | integer |           | not null | 
 desire_to_learn | boolean |           |          | 
 exams           | text    |           |          | 
Indexes:
    "pk_life" PRIMARY KEY, btree (name, age)

# \copy life from 'state_machine_example/src/main/resources/life.txt';

# select * from life;              
 name | age | desire_to_learn |             exams              
------+-----+-----------------+--------------------------------
 Вася |   1 | t               | 
 Вася |   2 | t               | 
 Вася |   3 | t               | 
 Вася |   4 | t               | 
 Вася |   5 | t               | 
 Вася |   6 | t               | 
 Вася |   7 | t               | 
 Вася |   8 | t               | 
 Вася |   9 | t               | 
 Вася |  10 | t               | 
 Вася |  11 | t               | 
 Вася |  12 | t               | 
 Вася |  13 | t               | 
 Вася |  14 | t               | 
 Вася |  15 | t               | выпускные экзамены в 9 классе
 Вася |  16 | t               | 
 Вася |  17 | t               | выпускные экзамены в 11 классе
 Вася |  18 | t               | вступительные экзамены в ВУЗ
 Вася |  19 | t               | 
 Вася |  20 | t               | 
 Вася |  21 | t               | 
 Вася |  22 | t               | защита диплома
 Вася |  23 | t               | 
 Вася |  24 | t               | 
 Вася |  25 | t               | 
 Вася |  26 | t               | 
 Вася |  27 | f               | 
 Вася |  28 | f               | 
 Вася |  29 | f               | 
 Вася |  30 | f               | 

It would be interesting to see what the state diagram machine looks like in UML. To do this, I will write a small Java program:

package com.github.isuhorukov.statemachine;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class StateMachineGenerator {
  
    public static void main(String[] args) throws Exception{
        Set<String> states;
        List<String> transitions;
        String stateMachineSource = StateMachineGenerator2.class.getResource("/education.statemachine").getFile();
        try (Stream<String> lines =  Files.lines(Paths.get(stateMachineSource))){
            List<DualValue> parsingValue = lines.map(line -> { //A   B   STATE_NAME   TRANSITION_RULE
                String[] parts = line.split("\t");
                String stateValue = "state \"" + parts[2] + "\" as state" + parts[1];
                if (parts.length < 4) {
                    return new DualValue(stateValue, null);
                }
                final int state = Integer.parseInt(parts[0]);
                String transitionValue = "state" + parts[0] + " --> state" + parts[1] + " : " + parts[3];
                return new DualValue(stateValue, transitionValue);
            }).collect(Collectors.toList());
            states = parsingValue.stream().map(dualValue -> dualValue.state).collect(Collectors.toSet());
            transitions = parsingValue.stream().map(dualValue -> dualValue.transition).
                    filter(Objects::nonNull).collect(Collectors.toList());
        }
        System.out.println("@startuml\n" + String.join("\n", states) + "\n" +
                                            String.join("\n", transitions) + "\n@enduml");
    }
    private static class DualValue {
        String state;
        String transition;
        String calculatedExpression;

        public DualValue(String state, String transition) {
            this.state = state;
            this.transition = transition;
        }
    }
}

With this program, I got the text in PlantUML format for the “wisdom state machine”.

@startuml
state "ученик старших классов" as state5
state "ученик средней школы" as state3
state "основное общее образование" as state4
state "среднее общее образование" as state6
state "аспирант" as state11
state "появился на свет" as state0
state "претендент на ученую степень" as state12
state "среднее профессиональное образование" as state8
state "учащийся института" as state9
state "кандидат наук" as state13
state "больше не обучается" as state14
state "ходит в детсадик" as state1
state "оконченное высшее образование" as state10
state "ученик начальной школы" as state2
state "учащийся техникума" as state7
state0 --> state1 : age>=3 and desire_to_learn
state1 --> state2 : age>=7 and exams is null and desire_to_learn
state2 --> state3 : age>=11 and exams is null and desire_to_learn
state3 --> state4 : age>=15 and exams="выпускные экзамены в 9 классе"
state4 --> state5 : age>=15 and desire_to_learn
state5 --> state6 : age>=17 and exams="выпускные экзамены в 11 классе"
state4 --> state7 : age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn
state7 --> state8 : age>=18 and exams="защита диплома"
state6 --> state9 : age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
state8 --> state9 : age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
state9 --> state10 : age>=22 and exams="защита диплома" and desire_to_learn
state10 --> state11 : age>=22  and exams="экзамены в аспирантуру" and desire_to_learn
state11 --> state12 : age>=24 and exams="кандидатский минимум" and desire_to_learn
state12 --> state13 : age>=25 and exams="защита диссертации" and desire_to_learn
state4 --> state14 : not(desire_to_learn)
state6 --> state14 : not(desire_to_learn)
state8 --> state14 : not(desire_to_learn)
state10 --> state14 : not(desire_to_learn)
state13 --> state14 : not(desire_to_learn)
@enduml

This description is easily converted into a graphical representation using the visualization plugin:

And by code generation from the same “wisdom finite automaton” I received the text of the finite automaton function in SQL for PostgreSQL:

CREATE OR REPLACE FUNCTION fsm_transition(
  state smallint,
  transition hstore
) RETURNS smallint AS $$
  select CASE
        WHEN state=0 THEN --null
       	CASE
       		WHEN transition->'st0_1'='true' THEN 1 --age>=3 and desire_to_learn
       		ELSE state
       	END
        WHEN state=1 THEN --ходит в детсадик
       	CASE
       		WHEN transition->'st1_2'='true' THEN 2 --age>=7 and exams is null and desire_to_learn
       		ELSE state
       	END
        WHEN state=2 THEN --ученик начальной школы
       	CASE
       		WHEN transition->'st2_3'='true' THEN 3 --age>=11 and exams is null and desire_to_learn
       		ELSE state
       	END
        WHEN state=3 THEN --ученик средней школы
       	CASE
       		WHEN transition->'st3_4'='true' THEN 4 --age>=15 and exams="выпускные экзамены в 9 классе"
       		ELSE state
       	END
        WHEN state=4 THEN --основное общее образование
       	CASE
       		WHEN transition->'st4_5'='true' THEN 5 --age>=15 and desire_to_learn
       		WHEN transition->'st4_7'='true' THEN 7 --age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn
       		WHEN transition->'st4_14'='true' THEN 14 --not(desire_to_learn)
       		ELSE state
       	END
        WHEN state=5 THEN --ученик старших классов
       	CASE
       		WHEN transition->'st5_6'='true' THEN 6 --age>=17 and exams="выпускные экзамены в 11 классе"
       		ELSE state
       	END
        WHEN state=6 THEN --среднее общее образование
       	CASE
       		WHEN transition->'st6_9'='true' THEN 9 --age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
       		WHEN transition->'st6_14'='true' THEN 14 --not(desire_to_learn)
       		ELSE state
       	END
        WHEN state=7 THEN --учащийся техникума
       	CASE
       		WHEN transition->'st7_8'='true' THEN 8 --age>=18 and exams="защита диплома"
       		ELSE state
       	END
        WHEN state=8 THEN --среднее профессиональное образование
       	CASE
       		WHEN transition->'st8_9'='true' THEN 9 --age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn
       		WHEN transition->'st8_14'='true' THEN 14 --not(desire_to_learn)
       		ELSE state
       	END
        WHEN state=9 THEN --учащийся института
       	CASE
       		WHEN transition->'st9_10'='true' THEN 10 --age>=22 and exams="защита диплома" and desire_to_learn
       		ELSE state
       	END
        WHEN state=10 THEN --оконченное высшее образование
       	CASE
       		WHEN transition->'st10_11'='true' THEN 11 --age>=22  and exams="экзамены в аспирантуру" and desire_to_learn
       		WHEN transition->'st10_14'='true' THEN 14 --not(desire_to_learn)
       		ELSE state
       	END
        WHEN state=11 THEN --аспирант
       	CASE
       		WHEN transition->'st11_12'='true' THEN 12 --age>=24 and exams="кандидатский минимум" and desire_to_learn
       		ELSE state
       	END
        WHEN state=12 THEN --претендент на ученую степень
       	CASE
       		WHEN transition->'st12_13'='true' THEN 13 --age>=25 and exams="защита диссертации" and desire_to_learn
       		ELSE state
       	END
        WHEN state=13 THEN --кандидат наук
       	CASE
       		WHEN transition->'st13_14'='true' THEN 14 --not(desire_to_learn)
       		ELSE state
       	END
       	ELSE state
END
$$ LANGUAGE sql;

This generated code will do the main job of determining the state of the state machine for each year of Vasily’s education. But in order to turn the function above into an aggregate one, we need a binding of two more functions for PostgreSQL. The publication “User-defined aggregate and window functions in PostgreSQL and Oracle” helped me figure out how to develop them.

CREATE OR REPLACE FUNCTION fsm_final( state smallint) RETURNS smallint AS $$ select state $$ LANGUAGE sql;

CREATE OR REPLACE AGGREGATE fsm(transition hstore) (
  sfunc     = fsm_transition,
  stype     = smallint,
  finalfunc = fsm_final,
  initcond  = '0'
);

By code generation, I also received a call to the FSM function with parameters that determine the transition between states:

String query = "fsm(hstore(ARRAY[" + String.join(", ", calculated) + "]))";
fsm(hstore(ARRAY['st0_1', (age>=3 and desire_to_learn)::text , 
                                        'st1_2', (age>=7 and exams is null and desire_to_learn)::text , 
                                        'st2_3', (age>=11 and exams is null and desire_to_learn)::text , 
                                        'st3_4', (age>=15 and exams="выпускные экзамены в 9 классе")::text , 
                                        'st4_5', (age>=15 and desire_to_learn)::text , 
                                        'st5_6', (age>=17 and exams="выпускные экзамены в 11 классе")::text , 
                                        'st4_7', (age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn)::text , 
                                        'st7_8', (age>=18 and exams="защита диплома")::text , 
                                        'st6_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st8_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st9_10', (age>=22 and exams="защита диплома" and desire_to_learn)::text , 
                                        'st10_11', (age>=22  and exams="экзамены в аспирантуру" and desire_to_learn)::text , 
                                        'st11_12', (age>=24 and exams="кандидатский минимум" and desire_to_learn)::text , 
                                        'st12_13', (age>=25 and exams="защита диссертации" and desire_to_learn)::text , 
                                        'st4_14', (not(desire_to_learn))::text , 
                                        'st6_14', (not(desire_to_learn))::text , 
                                        'st8_14', (not(desire_to_learn))::text , 
                                        'st10_14', (not(desire_to_learn))::text , 
                                        'st13_14', (not(desire_to_learn))::text ]))

Of course, it would be more convenient not to form this monstrous key-value parameter, but to have access to the entire string in the function body (without the hardcode of the parameter type).

I also generated a dictionary for decoding the numeric representation of the state into a string:

String statesSQL = "(VALUES "+stateName.entrySet().stream().map(stateNameEntry -> "("
                + stateNameEntry.getKey() + ", '"
                + stateNameEntry.getValue() + "')").collect(Collectors.joining(", "))
                + ") AS state_name(state, name)";

Combining these parts into one query, we decipher Vasily’s studies by year based on the state machine:

# SELECT life_alias.name,life_alias.age,life_alias.desire_to_learn,life_alias.exams, state_name.name state FROM 
            (SELECT *, fsm(hstore(ARRAY['st0_1', (age>=3 and desire_to_learn)::text , 
                                        'st1_2', (age>=7 and exams is null and desire_to_learn)::text , 
                                        'st2_3', (age>=11 and exams is null and desire_to_learn)::text , 
                                        'st3_4', (age>=15 and exams="выпускные экзамены в 9 классе")::text , 
                                        'st4_5', (age>=15 and desire_to_learn)::text , 
                                        'st5_6', (age>=17 and exams="выпускные экзамены в 11 классе")::text , 
                                        'st4_7', (age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn)::text , 
                                        'st7_8', (age>=18 and exams="защита диплома")::text , 
                                        'st6_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st8_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st9_10', (age>=22 and exams="защита диплома" and desire_to_learn)::text , 
                                        'st10_11', (age>=22  and exams="экзамены в аспирантуру" and desire_to_learn)::text , 
                                        'st11_12', (age>=24 and exams="кандидатский минимум" and desire_to_learn)::text , 
                                        'st12_13', (age>=25 and exams="защита диссертации" and desire_to_learn)::text , 
                                        'st4_14', (not(desire_to_learn))::text , 
                                        'st6_14', (not(desire_to_learn))::text , 
                                        'st8_14', (not(desire_to_learn))::text , 
                                        'st10_14', (not(desire_to_learn))::text , 
                                        'st13_14', (not(desire_to_learn))::text ]))              
                                         OVER (PARTITION BY name ORDER BY age) FROM life ORDER BY name,age) life_alias 
INNER JOIN 
( VALUES (0, 'появился на свет'), (1, 'ходит в детсадик'), (2, 'ученик начальной школы'), (3, 'ученик средней школы'), 
         (4, 'основное общее образование'), (5, 'ученик старших классов'), (6, 'среднее общее образование'), 
         (7, 'учащийся техникума'), (8, 'среднее профессиональное образование'), (9, 'учащийся института'), 
         (10, 'оконченное высшее образование'), (11, 'аспирант'), (12, 'претендент на ученую степень'), 
         (13, 'кандидат наук'), (14, 'больше не обучается')) AS state_name(state, name) 
ON state_name.state=life_alias.fsm;
 name | age | desire_to_learn |             exams              |             state             
------+-----+-----------------+--------------------------------+-------------------------------
 Вася |   1 | t               |                                | появился на свет
 Вася |   2 | t               |                                | появился на свет
 Вася |   3 | t               |                                | ходит в детсадик
 Вася |   4 | t               |                                | ходит в детсадик
 Вася |   5 | t               |                                | ходит в детсадик
 Вася |   6 | t               |                                | ходит в детсадик
 Вася |   7 | t               |                                | ученик начальной школы
 Вася |   8 | t               |                                | ученик начальной школы
 Вася |   9 | t               |                                | ученик начальной школы
 Вася |  10 | t               |                                | ученик начальной школы
 Вася |  11 | t               |                                | ученик средней школы
 Вася |  12 | t               |                                | ученик средней школы
 Вася |  13 | t               |                                | ученик средней школы
 Вася |  14 | t               |                                | ученик средней школы
 Вася |  15 | t               | выпускные экзамены в 9 классе  | основное общее образование
 Вася |  16 | t               |                                | ученик старших классов
 Вася |  17 | t               | выпускные экзамены в 11 классе | среднее общее образование
 Вася |  18 | t               | вступительные экзамены в ВУЗ   | учащийся института
 Вася |  19 | t               |                                | учащийся института
 Вася |  20 | t               |                                | учащийся института
 Вася |  21 | t               |                                | учащийся института
 Вася |  22 | t               | защита диплома                 | оконченное высшее образование
 Вася |  23 | t               |                                | оконченное высшее образование
 Вася |  24 | t               |                                | оконченное высшее образование
 Вася |  25 | t               |                                | оконченное высшее образование
 Вася |  26 | t               |                                | оконченное высшее образование
 Вася |  27 | f               |                                | больше не обучается
 Вася |  28 | f               |                                | больше не обучается
 Вася |  29 | f               |                                | больше не обучается
 Вася |  30 | f               |                                | больше не обучается
(30 rows)

Time: 13,711 ms

The expressiveness of this method is that it can be used both in window functions and in ordinary data aggregations.

For the entire dataset:

# SELECT life_alias.name, state_name.name state FROM 
            (SELECT name, fsm(hstore(ARRAY['st0_1', (age>=3 and desire_to_learn)::text , 
                                        'st1_2', (age>=7 and exams is null and desire_to_learn)::text , 
                                        'st2_3', (age>=11 and exams is null and desire_to_learn)::text , 
                                        'st3_4', (age>=15 and exams="выпускные экзамены в 9 классе")::text , 
                                        'st4_5', (age>=15 and desire_to_learn)::text , 
                                        'st5_6', (age>=17 and exams="выпускные экзамены в 11 классе")::text , 
                                        'st4_7', (age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn)::text , 
                                        'st7_8', (age>=18 and exams="защита диплома")::text , 
                                        'st6_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st8_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st9_10', (age>=22 and exams="защита диплома" and desire_to_learn)::text , 
                                        'st10_11', (age>=22  and exams="экзамены в аспирантуру" and desire_to_learn)::text , 
                                        'st11_12', (age>=24 and exams="кандидатский минимум" and desire_to_learn)::text , 
                                        'st12_13', (age>=25 and exams="защита диссертации" and desire_to_learn)::text , 
                                        'st4_14', (not(desire_to_learn))::text , 
                                        'st6_14', (not(desire_to_learn))::text , 
                                        'st8_14', (not(desire_to_learn))::text , 
                                        'st10_14', (not(desire_to_learn))::text , 
                                        'st13_14', (not(desire_to_learn))::text ])  ORDER BY age)
                                         FROM life  GROUP BY name) life_alias 
INNER JOIN 
( VALUES (0, 'появился на свет'), (1, 'ходит в детсадик'), (2, 'ученик начальной школы'), (3, 'ученик средней школы'), 
         (4, 'основное общее образование'), (5, 'ученик старших классов'), (6, 'среднее общее образование'), 
         (7, 'учащийся техникума'), (8, 'среднее профессиональное образование'), (9, 'учащийся института'), 
         (10, 'оконченное высшее образование'), (11, 'аспирант'), (12, 'претендент на ученую степень'), 
         (13, 'кандидат наук'), (14, 'больше не обучается')) AS state_name(state, name) 
ON state_name.state=life_alias.fsm;  

 name |        state        
------+---------------------
 Вася | больше не обучается
(1 row)

Only for lines where age<21:

# SELECT life_alias.name, state_name.name state FROM 
            (SELECT name, fsm(hstore(ARRAY['st0_1', (age>=3 and desire_to_learn)::text , 
                                        'st1_2', (age>=7 and exams is null and desire_to_learn)::text , 
                                        'st2_3', (age>=11 and exams is null and desire_to_learn)::text , 
                                        'st3_4', (age>=15 and exams="выпускные экзамены в 9 классе")::text , 
                                        'st4_5', (age>=15 and desire_to_learn)::text , 
                                        'st5_6', (age>=17 and exams="выпускные экзамены в 11 классе")::text , 
                                        'st4_7', (age>=16 and exams="вступительные экзамены в техникум" and desire_to_learn)::text , 
                                        'st7_8', (age>=18 and exams="защита диплома")::text , 
                                        'st6_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st8_9', (age>=18 and exams="вступительные экзамены в ВУЗ" and desire_to_learn)::text , 
                                        'st9_10', (age>=22 and exams="защита диплома" and desire_to_learn)::text , 
                                        'st10_11', (age>=22  and exams="экзамены в аспирантуру" and desire_to_learn)::text , 
                                        'st11_12', (age>=24 and exams="кандидатский минимум" and desire_to_learn)::text , 
                                        'st12_13', (age>=25 and exams="защита диссертации" and desire_to_learn)::text , 
                                        'st4_14', (not(desire_to_learn))::text , 
                                        'st6_14', (not(desire_to_learn))::text , 
                                        'st8_14', (not(desire_to_learn))::text , 
                                        'st10_14', (not(desire_to_learn))::text , 
                                        'st13_14', (not(desire_to_learn))::text ])  ORDER BY age)
                                         FROM life where age<21 GROUP BY name) life_alias 
INNER JOIN 
( VALUES (0, 'появился на свет'), (1, 'ходит в детсадик'), (2, 'ученик начальной школы'), (3, 'ученик средней школы'), 
         (4, 'основное общее образование'), (5, 'ученик старших классов'), (6, 'среднее общее образование'), 
         (7, 'учащийся техникума'), (8, 'среднее профессиональное образование'), (9, 'учащийся института'), 
         (10, 'оконченное высшее образование'), (11, 'аспирант'), (12, 'претендент на ученую степень'), 
         (13, 'кандидат наук'), (14, 'больше не обучается')) AS state_name(state, name) 
ON state_name.state=life_alias.fsm;  

 name |       state        
------+--------------------
 Вася | учащийся института
(1 row)

It’s a pity that in ClickHouse, I didn’t find how to solve this problem without executable / Python in pure SQL, even if auto-generated. No lengthy C++ development for one of the most popular open source analytical databases!

Nothing else in the database, capable of storing state between calls and performing conditional calculation of states, has yet to come to my mind. Perhaps there is a way to write the code more concisely. I would like to ask the advice of @erogov and colleagues: maybe there is an easier way without using aggregate functions and code generation?

As a result, I got another tool for marking up a data set “without leaving” the database. It can be useful for analysts, data science, in business reporting and markup of business processes based on a state machine and the transition between states, described as logical expressions in SQL.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *