После выступления на PgConf2023 и общению с профессионалами по базам данных, у меня на выходных появилось время на реализацию идеи, как реализовать логику конечного автомата на SQL в PostgreSQL. Идея применима к любой СУБД, поддерживающей агрегатные функции, определяемые пользователем.
Скоро сказка сказывается, да не скоро дело делается... Жил был Вася. И устои в обществе где он жил, были описаны с помощью конечного автомата. А конечный автомат мудрости - finite-state machine (FSM) был задан в виде таблицы переходов, в TSV формате:
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)И записали летописцы его житие в виде таблицы в tab separated value формате и загрузили в 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 | Было бы любопытно посмотреть, как выглядит автомат state diagram в UML. Для этого напишу небольшую программу на Java:
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;
}
}
}С помощью этой программы я получил текст в формате PlantUML для "конечного автомата мудрости".
@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Это описание легко превращается в графическое предстваление с помощью плагина визуализации:
И путем кодогенерации из того же "конечного автомата мудрости" получил текст функции конечного автомата на SQL для 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;Вот этот сгенерированный код и будет выполнять основную работу по определению состояния конечного автомата для каждого года обучения Василия. Но для того чтобы превратить функцию выше в агрегатную, понадобится обвязка из еще двух функций для PostgreSQL. Разобраться как их разрабатывать мне помогла публикация "Пользовательские агрегатные и оконные функции в PostgreSQL и Oracle".
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'
);Путем кодогенерации, я также получил вызов функции FSM с параметрами, определяющими переход между состояниями:
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 ]))Конечно было бы удобнее не формировать этот монструозный параметр ключ-значение, а иметь доступ в теле функции ко всей строке(без хардкода типа параметра).
Также сгенерировал словарь для расшифровки числового представления состояния в строковое:
String statesSQL = "(VALUES "+stateName.entrySet().stream().map(stateNameEntry -> "("
+ stateNameEntry.getKey() + ", '"
+ stateNameEntry.getValue() + "')").collect(Collectors.joining(", "))
+ ") AS state_name(state, name)";Объединив эти части в один запрос мы дешифруем учебу Василия по годам на основе конечного автомата:
# 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Выразительность этого метода в том, что можно его применять как в оконных функциях, так и в обычных агрегациях данных.
Для всего набора данных:
# 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)Только для строчек где 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)Жаль, что в ClickHouse, эту задачу не нашел как вообще можно решить без executable/Python на чистом SQL, хоть пусть и автосгенерированном. Без длительной разработки на C++ для одной из самых популярных open source аналитических баз данных!
Ничего другого в БД, способного хранить состояние между вызовами и выполнять вычисление состояний по условиям, мне в голову пока не пришло. Возможно, есть способ записать код компактнее. Хотел бы спросить совет@erogov и коллег: может есть более простой способ и без использования агрегатных функций и кодогенерации?
В результате, получил еще один инструмент для разметки набора данных "не выходя" из базы данных. Может быть полезно аналитикам, дата саенс, в бизнес-отчетности и разметке бизнес-процессов на основе конечного автомата и перехода между состояниями, описанными в виде логических выражений на SQL.
