После выступления на PgConf2023 и общению с профессионалами по базам данных, у меня на выходных появилось время на реализацию идеи, как реализовать логику конечного автомата на SQL в PostgreSQL. Идея применима к любой СУБД, поддерживающей агрегатные функции, определяемые пользователем.
Скоро сказка сказывается, да не скоро дело делается... Жил был Вася. И устои в обществе где он жил, были описаны с помощью конечного автомата. А конечный автомат мудрости - finite-state machine (FSM) был задан в виде таблицы переходов, в TSV формате:
И записали летописцы его житие в виде таблицы в 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 | И хотелось современникам Василия расписать состояние каждого года его учебы и жизни, добавив к life еще одну колонку state, из которой становится ясно в каком состоянии статус его учебы в каждый момент времени.
Было бы любопытно посмотреть, как выглядит автомат 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;
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 --появился на свет
CASE
WHEN transition->'st0_1'='true' -- age>=3 and desire_to_learn
THEN 1 --ходит в детсадик
ELSE state
END
WHEN state=1 THEN --ходит в детсадик
CASE
WHEN transition->'st1_2'='true' -- age>=7 and exams is null and desire_to_learn
THEN 2 --ученик начальной школы
ELSE state
END
WHEN state=2 THEN --ученик начальной школы
CASE
WHEN transition->'st2_3'='true' -- age>=11 and exams is null and desire_to_learn
THEN 3 --ученик средней школы
ELSE state
END
WHEN state=3 THEN --ученик средней школы
CASE
WHEN transition->'st3_4'='true' -- age>=15 and exams='выпускные экзамены в 9 классе'
THEN 4 --основное общее образование
ELSE state
END
WHEN state=4 THEN --основное общее образование
CASE
WHEN transition->'st4_5'='true' -- age>=15 and desire_to_learn
THEN 5 --ученик старших классов
WHEN transition->'st4_7'='true' -- age>=16 and exams='вступительные экзамены в техникум' and desire_to_learn
THEN 7 --учащийся техникума
WHEN transition->'st4_14'='true' -- not(desire_to_learn)
THEN 14 --больше не обучается
ELSE state
END
WHEN state=5 THEN --ученик старших классов
CASE
WHEN transition->'st5_6'='true' -- age>=17 and exams='выпускные экзамены в 11 классе'
THEN 6 --среднее общее образование
ELSE state
END
WHEN state=6 THEN --среднее общее образование
CASE
WHEN transition->'st6_9'='true' -- age>=18 and exams='вступительные экзамены в ВУЗ' and desire_to_learn
THEN 9 --учащийся института
WHEN transition->'st6_14'='true' -- not(desire_to_learn)
THEN 14 --больше не обучается
ELSE state
END
WHEN state=7 THEN --учащийся техникума
CASE
WHEN transition->'st7_8'='true' -- age>=18 and exams='защита диплома'
THEN 8 --среднее профессиональное образование
ELSE state
END
WHEN state=8 THEN --среднее профессиональное образование
CASE
WHEN transition->'st8_9'='true' -- age>=18 and exams='вступительные экзамены в ВУЗ' and desire_to_learn
THEN 9 --учащийся института
WHEN transition->'st8_14'='true' -- not(desire_to_learn)
THEN 14 --больше не обучается
ELSE state
END
WHEN state=9 THEN --учащийся института
CASE
WHEN transition->'st9_10'='true' -- age>=22 and exams='защита диплома' and desire_to_learn
THEN 10 --оконченное высшее образование
ELSE state
END
WHEN state=10 THEN --оконченное высшее образование
CASE
WHEN transition->'st10_11'='true' -- age>=22 and exams='экзамены в аспирантуру' and desire_to_learn
THEN 11 --аспирант
WHEN transition->'st10_14'='true' -- not(desire_to_learn)
THEN 14 --больше не обучается
ELSE state
END
WHEN state=11 THEN --аспирант
CASE
WHEN transition->'st11_12'='true' -- age>=24 and exams='кандидатский минимум' and desire_to_learn
THEN 12 --претендент на ученую степень
ELSE state
END
WHEN state=12 THEN --претендент на ученую степень
CASE
WHEN transition->'st12_13'='true' -- age>=25 and exams='защита диссертации' and desire_to_learn
THEN 13 --кандидат наук
ELSE state
END
WHEN state=13 THEN --кандидат наук
CASE
WHEN transition->'st13_14'='true' -- not(desire_to_learn)
THEN 14 --больше не обучается
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 ]))Конечно было бы удобнее не формировать этот монструозный параметр ключ-значение, а иметь доступ в теле функции ко всей строке(без хардкода типа параметра).
Также сгенерировал словарь для расшифровки числового представления состояния в строковое. Можно было бы сохранить их в таблице-справочнике, но генерация варианта с VALUES удобнее при частом пересоздании конечного автомата:
String statesSQL = "(VALUES "+stateName.entrySet().stream().map(stateNameEntry -> "("
+ stateNameEntry.getKey() + ", '"
+ stateNameEntry.getValue() + "')").collect(Collectors.joining(", "))
+ ") AS state_name(state, name)";Данные в примере денормализованные, но никто не мешает в запросе собирать их соединением множества таблиц. В мире же аналитики и колоночных баз данных денормализованные таблицы - норма, для ускорения доступа.
Правильность описания таблицы переходов оставим на откуп ее создавшего. И задача функции не гадать какой должна быть модель для верного описания реальности, а просто исполнять заданный автомат. То есть описание автомата с условиями перехода на SQL и являются входными правилами для разметки набора данных. Если пользователь меняет определение таблицы переходов, то нужно пересоздать из этой таблицы новую функцию и шаблон параметров.
Объединив эти части в один запрос мы дешифруем учебу Василия по годам на основе конечного автомата:
# 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.
erogov
Признаться, не понял, какую задачу мы решаем и зачем. Если у нас уже есть Таблица Судьбы
life, зачем нам конечный автомат? Вот если бы была таблица переходов, а на вход автомату подавались бы радости и невзгоды, определяющие, по какой ветке идти дальше — это бы имело для меня смысл.igor_suhorukov Автор
Задача классифицировать по заданному таблицей переходов КА классифицировать события(тут они в life). Есть события, которые выполнял Василий — сдавал экзамены и рос молодцом. Его друг Лёлик решил после 9класса вообще в жизни не учиться, а одноклассники Николай пошел в аспирантуру и сдал диссертацию. Это все события в жизни нескольких товарищей. И этот конечный автомат как раз таки и классифицирует траектории каждого в жизни, по этой заданной модели.
Если определите состояния КА по входам радостей и невзгод, то будет по ним определять по какой ветки идёт по жизни Василий. Разве не оно?)
igor_suhorukov Автор
В этом примере мы обогащаем события в life состояниями из траектории обучения, которую он своими действиями выбрал в своей жизни