Комментарии 54
Вообще не очень понятно, при чём тут графы, если у документа есть линейная история изменения состояний. Почему нельзя просто пройти по ней от конца к началу, складывая статусы вершин в хэшмап?
Более того: вершины добавляются по одной, так что даже хэшмап не нужен. Просто при переходе в очередное состояние проверить – может, мы в нём уже были?
Например, есть 4ре состояния документа: Статус1 - Статус2 - Статус3 - Статус4
Есть условия: а) можно перейти из Статуса4 обратно в Статус1 не более одного раза. б) Статус2 при второй итерации можно пропустить.
1 итерация: Статус1 - Статус2 - Статус3 - Статус4
2 итерация: Статус1 - Статус3 - Статус4
3 итерация: запрет
Что здесь можно сделать? Не совсем понятна идея с хэшмапом. Там же без if-else для Статус2 не обойтись.
Тут не три итерации, а 6 отдельных переходов (и один запрет перехода). Проверка требуется при переходе. Задача куда проще описанной вами, каждый переход проверяется за линейное время, если не оптимизировать (для оптимизации понадобится хранить состояние чуть сложнее, чем просто номер текущего).
Я не спорю насчёт полезности графов, но по вашему описанию задача из другой области)
Кстати, насчёт хэшмапа я погорячился, набор состояний фиксированный, хватит массива бит или чего-то подобного.
Возможно, для вашей задачи действительно полезен алгоритм поиска циклов. Но описали вы задачу, в которой он не нужен. Тогда вы знаете, какой скилл прокачивать следующим: постановку задач.
В такой задаче можно хранить флаг что был подписан второй раз, а кейс с пропуском Статус2 проверять по наличию подписи, ведь мы её храним. Кстати, в этом случае и историю переходов можно не хранить, если этого в бизнес-логике не требуется. Оно всё это ещё и быстрее работать будет, даже если храним таки историю - никаких хождений по графам, читаем данные из колонки в базе, причем в момент выгрузки документа, потому что явно обработка статуса предполагает выгрузку каких-то данных о документе. Заодно аналитикам удобно будет и прочей логике если понадобится - один запрос в базу без рекурсий и мы получили все документы, которые подписаны были дважды. Или только единожды. Быстро и эффективно. Опыт энтерпрайза.
Как так, ведь почти идеальная шутка была...
Каждая правильная шутка про рекурсию порождала бы 2 идентичные шутки про рекурсию.
Это более похоже на бесконечный цикл, чем на рекурсию
Это вообще ни на что не похоже. Почему фраза "Шутить про рекурсию" запускает следующую итерацию?
Тут лучше подошла бы шутка "Сколько лет нужно коммерческому PHP-разрабочику, работающему с документооборотом, чтобы узнать про конечные автоматы". Интересно, что там за костыли были до того костыля, который описан в статье.
Тут больше похоже, что нужна просто матрица "в какое состояние можно перейти из каждого", с пометками, чья подпись делает этот переход.
Автор, не могли бы вы поподробнее расписать исходную задачу?
Автор, не могли бы вы поподробнее расписать исходную задачу?
вы не понимаете, если поподробнее расписать исходную задачу, то придется решать исходную задачу, тогда никак не получится приплести теорию графов.
На всякий случай, задача сформулирована вот так:
нужно определить, может ли документ в этом статусе подписываться несколько раз. Если да - обновлять подпись, если нет - выдавать ошибку.
в какой момент обновлять подпись, кому выдавать ошибку - фиг его знает! зачем вообще нужна подпись если достаточно (обычно) разрешения (прав) для перевода статуса? - тоже фиг его знает
Попробуйте описать через граф "не имеет ничего общего с другими узлами".
У узла нет ребер в другие узлы?
Хуже всякие групповые отношения описываются. Вроде как тройки элементов могут обладать каким-то свойством, а могут не обладать. Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь. Можно, конечно граф обобщить, сделав множество ребер подмножеством V^3, но практически ни один из существующих алгоритмов там работать не будет.
Нет. Факт отсутствия ребер в графе как раз описывает "не имеет ничего общего с другими узлами".
Не понимаю. Есть ребра — есть отношение. Изолированная вершина никаких отношений не имеет. Все описано.
Я так и не понял, что вы имеете ввиду под "не имеет ничего общего с другими узлами".
В примере выше можно провести направленное ребро "является" между человеком и сантехником. Можно провести ребро между сантехником и работой. Ребра между работой и человеком нет. Факт того, что "человек" не является работой, ни "работа" является человеком в графе записан.
Тут нет отношения к "робот", верно? Может ли "робот" быть сантехником?
Зависит от того, что мы в графе рисуем. Если это "любой объект X является У", то ребра нет. Не любой робот является сантехником. И все записанно. Если вас напрягает, что тут не записано, что некоторые роботы могут быть сантехниками, то надо вводить ребра разных цветов (или смотреть на 2 графа сразу. Один говорит о "могут быть", другой — "всегда являются").
Предположим, на вопрос "может ли быть сантехником" вы ответили "да" — значит ли это, что любое "существо", починившее кран — человек? Нет, верно?
Сами сделали какой-то логически противоречивый переход и теперь радуетесь, что поймали меня на противоречии. Как вы из "робот может быть сантехником" сделали вывод, что "любое "существо", починившее кран — человек" и как это относится к ребрам — вообще неясно.
Судя по карме, не я один считаю, что вы троль. Больше я на ваш троллинг отвечать не буду.
У вас карма отрицательная. Значит, скорее всего, общение с вами вызывает у приносящих пользу на этом ресурсе пользователей желание нажать кнопочку "пусть этот пользователь лучше помолчит". Значит более вероятно, что у нас тут с вами не какое-то недопонимание, а вы спорите, ради того чтобы поспорить.
Зачем вы в соседнем ответе мне дали ссылку на профиль автора статьи, я торже не знаю.
Реально считаете, что "отсутствие описания" === "отсутствие отношений"?
Давайте так: человек-сантехник-работа. Тут нет отношения к "робот", верно? Может ли "робот" быть сантехником? А человеком? А может-ли он делать работу?
Это зависит от того какая модель используется: основанная на open-world assumption или на closed-world assumption.
Если первая (RDF, OWL, ...), то, да, вы правы: если в модели что-то не описано, то это не значит, что этого не может быть (заранее извиняюсь, если при чтении этого предложения с тремя отрицаниями сломаются какие-нибудь англоязычные люди, зачем-то забредшие сюда).
А если вторая (UML, ER, ...), то отсутствие описания действительно означает отсутствие отношения. Например, в банке отсутствует запись о наличии у меня счетов. По вашему это ничего не значит? Вполне возможно, что у меня всё-таки есть там счёт может быть на тысячу долларов, а может быть и на миллион? Или другой пример: есть граф описывающий кто на кого подписан в социальной сети. Если там есть узел, который не связан с другими, то значит он действительно ни с кем не связан.
В общем, вы спорите о разном. Вы говорите о первом типе моделей, а ваш оппонент - о втором. И вы оба правы.
В общем-то и в RDF никто не запрещает сделать какой-нибудь базовый класс "Объекты, не имеющие отношения с другими объектами" и интерпретировать его соответствующим образом. Или сделать аналогичное свойство.
Всё зависит от интерпретации (семантики) графа. Сами по себе узлы и связи вообще ничего не значат.
Хотите сделайте тип ребра «нет связи»
Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь.
Гиперграф, многодольный граф?
Ну да, это гиперграф и есть. Я про это как раз и упомянул в конце (правда, без общепринятого названия). Но это уже не граф. И алгоритмы почти никакие из графовых на нем не работают.
А вот многодольный граф тут не подходит. Он все-равно только пары описывает. А я же говорил про тройки. Ибо может быть что {a,b,c} — обладает свойством, а {a,b,d} — нет. Что делать с ребром между a и b из соответствующих долей?
Но это уже не граф. И алгоритмы почти никакие из графовых на нем не работают.
С точки зрения теории графов — граф. Множество алгоритмов, работающих с ориентированными и неориентированными графами тоже разное, никто не ропщет.
Что мы, кстати, хотим с этим знанием сочетаемости блюд делать?
Может всё там нормально с алгоритмами. Для какого-нибудь кафе с бизнес-ланчами банально готового списка хватит.
С точки зрения теории графов — граф.
Нет, в теории графов определение графа дано. И гиперграф сюда не натягивается. Там есть слово "парных" перед "связями".
Множество алгоритмов, работающих с ориентированными и неориентированными графами тоже разное, никто не ропщет.
Почти все алгоритмы, работающие на ориентированных графах, работают и на неориентированных (кроме алгоритмов для ациклических графов). Тут пересечение настолько обширное, да и сами ориентированные и неориентированные графы настолько похожие объекты, что их считают разновидностями одного типа.
Что мы, кстати, хотим с этим знанием сочетаемости блюд делать?
Неважно, это был просто пример небинарного отношения. Может, вам надо составить набор хороших троек на неделю без пересечения по вершинам. Или найти подмножество где наибольшее количество троек сочетается. Пример, возможно, не практичный. В википедии написано, что гиперграфы применяются в рассчетах электрических сетей. Какие-то применения у этих структур наверняка есть.
тройки элементов могут обладать каким-то свойством, а могут не обладать. Например вот такие наборы первого блюда, второго блюда и десерта сочетаются. Это графом не запишешь.
Это легко описать. Добавляется ещё одна вершина "комплексный обед" или что-то подобное. Она связана с первым и вторым блюдом и с десертом, и может сама иметь какие-то дополнительные свойства и связи. Есть языки типа RDF или Object-role modeling. Я не могу придумать какие-то реальные вещи, которые нельзя на них описать.
Да, и в обычных ER-моделях N-арные отношения между объектами просто моделируются ещё одной сущностью. Грубо говоря, если нужно связать 3 таблицы, просто добавляем к ним ещё одну.
Звучит так, будто мы могли использовать Паттерн "состояние"
И будто бы даже решение было интуитивно понятнее:)
Но ваш подход тоже интересный
Выглядит как одну мелкую проблему, решают в другом месте и сильно сложнее.
Если документ изменился после подписи, то подпись больше не действительна.
В лоб можно было сделать конечный автомат с каким то состоянием. Заодно и графы там органично смотрятся.
create type doc_states AS ENUM ('S1', 'S2', 'S3', 'S4');
create type doc_state_flags AS ENUM ('S4_REACHED', 'S4_REACHED_TWICE');
create table docs
(
id bigserial not null primary key,
status doc_states default 'S1',
status_flags int default 0,
signature bytea
);
create or replace function doc_reached_s4() returns trigger
as
$$
begin
NEW.status_flags = NEW.status_flags | array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1);
return NEW;
end
$$
LANGUAGE plpgsql;
create trigger mark_s4_reached_trigger
before insert OR update
on docs
for each row
when ( NEW.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) =
0 AND NEW.status = 'S4')
execute FUNCTION doc_reached_s4();
create function disallow_signature() returns trigger
as
$$
BEGIN
raise exception 'The document with the ID % has already reached status S4 and thus cannot get signed once more during transition to status S2', OLD.id;
end
$$ LANGUAGE plpgsql;
create trigger prohibit_re_signing_trigger
before update
on docs
for each row
when (NEW.signature != OLD.signature AND
OLD.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) !=
0 AND NEW.status = 'S2')
execute FUNCTION disallow_signature();
create function doc_reached_s4_twice() returns trigger
as
$$
begin
NEW.status_flags = NEW.status_flags | array_length(enum_range(NULL, 'S4_REACHED_TWICE'::doc_state_flags), 1);
return NEW;
end
$$ LANGUAGE plpgsql;
create trigger mark_s4_reached_twice_trigger
before insert OR update
on docs
for each row
when ( NEW.status_flags & array_length(enum_range(NULL, 'S4_REACHED'::doc_state_flags), 1) !=
0 AND NEW.status = 'S4' AND OLD.status != 'S4')
execute FUNCTION doc_reached_s4_twice();
alter table docs
add constraint docs_s4_final CHECK (
status_flags & array_length(enum_range(NULL, 'S4_REACHED_TWICE'::doc_state_flags), 1) = 0 OR
status = 'S4');
Проверяем
insert into docs (signature)
values (NULL);
select *
from docs;
update docs
set status = 'S2',
signature = '\x00'
where id = 1;
select *
from docs;
update docs
set status = 'S3',
signature = '\x01'
where id = 1;
select *
from docs;
update docs
set status = 'S4',
signature = '\x02'
where id = 1;
select *
from docs;
update docs
set status = 'S1',
signature = '\xFF'
where id = 1;
select *
from docs;
BEGIN;
update docs
set status = 'S2',
signature = '\x00'
where id = 1;
select *
from docs;
ROLLBACK;
update docs
set status = 'S3',
signature = '\x01'
where id = 1;
select *
from docs;
update docs
set status = 'S4',
signature = '\x02'
where id = 1;
select *
from docs;
BEGIN;
update docs
set status = 'S1',
signature = '\xFF'
where id = 1;
select *
from docs;
ROLLBACK;
BEGIN;
update docs
set status = 'S2',
signature = '\x00'
where id = 1;
select *
from docs;
ROLLBACK;
BEGIN;
update docs
set status = 'S3',
signature = '\x01'
where id = 1;
select *
from docs;
ROLLBACK;
Какие подводные (конечно, кроме 'ALTER TYPE doc_states ADD VALUE ... BEFORE...', который, например, документацией запрещается и на всех ревью отсекается)?
Тут "надводный", SQL. В эти дни бизнес-логику в БД стараются класть в минимальном объеме. Дискуссии ведутся, есть за и против у обоих вариантов, но "умная" база потихоньку сдает позиции. Удобно, когда средства БД позволяют контролировать целостность и эффективно манипулировать данными, а высокоуровневая логика находится в прикладном слое.
Плюс можно вспомнить про сложность написания тестов, рефакторинга, масштабирования на большое количество типов документов, смены движка БД и т.д.
Я не спорю ни с одним сказанным вами словом. Если я уберу DEFAULT из DDL таблицы и заменю там же SERIAL на INTEGER, тогда принимается (с поправкой на обработку случаев, когда status / status_flags не инициализированы)?
Только не говорите мне, что "это бизнес-логика только потому, что там написано CREATE FUNCTION". В этих триггерах бизнес-логики не больше, чем в NOT NULL, PRIMARY KEY (UNIQUE CONSTRAINT), FOREIGN KEY и так далее. Ну, или покажите мне, какое место занимается бизнес-логикой в приведенном куске DDL.
Впрочем, я не настаиваю на реализации этого именно в СУБД, коли хочется закатывать солнце вручную. Можно и в код вынести, благо, код самоочевиден и его реализация на любом более-менее распространённом языке тривиальна. Разве что тогда коду придётся начать знать про поле status_flags, которое к бизнес-логике не относится.
В любом случае, реализация в СУБД или в коде, это приведет к печальному факту: имя этой статье "как я наоверинжинирил".
Задача БД хранить данные и позволять мне их эффективно их извлекать. Любое придание смысла этим данным - бизнес-логика.
Иными словами:
FOREIGN KEY -- это фу-фу-фу, потому как придает колонке user_id для записи в таблице books какой-то смысл
NOT NULL -- фу-фу-фу, потому как какая разница БД, нет там значения или есть, нету и нету, хранить меньше, это закидоны приложения, что такое состояние данных не валидно, пусть оно и разрибается
DEFAULT nextval('my_sequence'::regclass) -- совсем сдурели? Какая-то СУБД будет за меня там что-то решать, какое там значение (в самый фронт-енд прямо в табличку попадёт, если что, потом фронт по этому значению ссылаться на строку в таблице будет, самая настоящая часть бизнес-логики)? Да я сам там приложением значение запишу: `BEGIN; LOCK TABLE articles; INSERT INTO articles (id, ...) SELECT count(1), ... FROM articles; COMMIT;`. Хайлоадненько!
PostgreSQL Table Partitioning -- моё любимое; давайте какая-то тупая хранилка не будет за меня решать, в какую партицию мне запихнуть вот этот бакет, а моё умнейшее приложение само решит, лады?
Я правильно понял посыл? Вам за 10 минут на коленке написано решение без оверхеда. Посчитаем скорострельность, кстати? Решение занимается только и исключительно контролем целостности данных. Да, целостности с точки зрения приложения, потому что СУБД вообще плевать, что там в данных, приложение задаёт правила этой целостности. Все эти NOT NULL, CHECK, EXCLUDE, UNIQUE, PRIMARY/FOREIGN KEY, да даже типы данных - тоже вполне себе "придание смысла данным".
Ого, сколько экспрессии)) Прямо чувствуется вся боль от войны с ветряными мельницами))
Все эти NOT NULL, CHECK, EXCLUDE, UNIQUE, PRIMARY/FOREIGN KEY, да даже типы данных - тоже вполне себе "придание смысла данным".
Да нет же, это ограничения отношений. Теория реляционных БД, вот это все. А когда БД начинает лезть в мои данные, анализируя, что там конкретно за строка или число написаны и принимать на основании этого какие-то решения - это бизнес-логика.
PostgreSQL Table Partitioning? С чего вы взяли, что у меня PostgreSQL?
Факт остается фактом: никто в здравом уме не будет использовать это "на коленке написанное решение" во взрослом продакшне. Потому что, во-первых, мы тут хотим абстрагироваться от конкретного движка СУБД и, во-вторых, не понятно, кто все это добро будет поддерживать и развивать? А когда правила поменяются? А как я могу быть уверен, что эти правила не отвалились? А когда пользователь сам захочет эти правила настраивать? А в распределенной базе? И т.д., и т.п.
Да нет же, это ограничения отношений.
Да нет же, как минимум, NOT NULL, DEFAULT, CHECK не являются ограничениями отношений. Однако, первые два используются в каждом первом проекте с сикуелью.
А когда БД начинает лезть в мои данные, анализируя, что там конкретно за строка или число написаны и принимать на основании этого какие-то решения
Я же говорю: всё в блобы. Какие там тебе СУБД, они только лезть всюду будут. По файлам раскидал - и хорошо. Типы данных еще какие-то... Эта чумазая баговня мне еще будет запрещать 1<<32 в поле писать. Или к '500' прибавлять 100.
С чего вы взяли, что у меня PostgreSQL?
Во-первых, цитата из "Зелёного слоника": "Кто 'вы'?! Я здесь один!"
Во-вторых, постгрес -- у меня. Впрочем, за неимением оракла, иных вариантов для БД документооборота и не остаётся. Так что да, уверен, что постгрес.
во-первых, мы тут хотим абстрагироваться от конкретного движка СУБД
Это прям самоцель, да? Чтобы что? Неужто на каждом дейли стендапе скрам-мастер с каждого разработчика требует план на неделю по переезду с диалекта на диалект, а после спринта премию распределяет в зависимости от количества произведенных переездов? Только не надо говорить, мол, "а вдруг переехать на другой диалект надо будет". Уверяю, какие-то там триггеры и констрейнты будут самой незначительной проблемой при переезде. Гораздо больше дерьма можно навалить, например, в неотключаемых сиквелгреповых INT(5) и подобных непотребствах. А помимо схемы еще сторадж, вопросы выгрузки табличных данных, вопросы той же репликации. Ладно уж прикидываться-то, там вон ниже как раз вопросы намекают, где проблемы при переезде ожидаются. Вообще не в схеме данных.
во-вторых, не понятно, кто все это добро будет поддерживать и развивать
Ну а граф вот этот у автора кто будет поддерживать и развивать? Такой же олимпиадник? Так они часто отвратительнейшим характером обладают, да и код write-only (как у автора). Уж всяко моя реализация очевидна и не требует усилий сверх джуниорского уровня для понимания. В отличие от.
А когда правила поменяются?
Обновится набор ограничений целостности в соответствии с новыми правилами. В общем, произойдёт ровно то же самое, как если бы, например, новое поле у документа появилось. Модель, контроллер, вьюхи, фикстура. Протестил, запушил, в стейджинг.
А как я могу быть уверен, что эти правила не отвалились?
Никак. Ведь развернуть на стейдже снапшот базы запрещается. Мы же не эти самые, которые бэкапы по расписанию на восстановимость проверяют. У нас тут всё по-военному: сказал генерал "базе быть" -- значит, будет. Если же однажды получится у начальства выбить хотя бы на разочек развернуть бэкап просто чисто поиграться, то проверка правил -- второй кусок моего исходного сообщения. Да, я прямо с тесткейсом дал. Ожидания только расставить осталось, где должно рейзить и что, где не должно.
А когда пользователь сам захочет эти правила настраивать?
Немаловероятно, при должном уровне усердия правила, созданные пользователем, транслируются в ограничения целостности данных в базе (но я бы не рекомендовал: в этом случае лучше и правда приложением проверять -- не всякая аппликуха в своей базе имеет полномочия DDL жарить). Разве что у пользователя настройка правил -- это <textarea>, где он произвольным порядком описывает эти самые правила. Тогда да, задача в общем случае не решается. Впрочем, она тогда не решается вне всякой зависимости от того, где именно планируется производить контроль целостности -- в СУБД или в приложении.
А в распределенной базе?
Ну, фейспук же не разломался на части. Распределенный. Шардированный. Придумаете что-нибудь, вы там все умные. К примеру, будете хранить данные одного полного экземпляра контролируемого домена данных в пределах одного шарда в самой начальной стадии, пока не напилите себе кросс-сервер транзакции какие-нибудь. Или какой-нибудь consensus.
никто в здравом уме не будет использовать это "на коленке написанное решение" во взрослом продакшне
Поправочка: в стартапах на распил первого раунда инвестиций не будут, потому как там задача прогреть атмосферу ORM-ами до закритических температур, а не просто и элегантно задачу решить (тут думать надо, а это некогда).
А в кровавых тырпрайзах еще и сотнями пакетов с частичным выносом бизнес-логики обмажут (например, всякие движения документов по расписанию через планировщик). Но да, полирнут, конечно же, через сотню голов еще протащут -- здесь код-ревью на 10 человек, там QA - двадцать, тут - UAT - еще 15, вон там интеграционные тесты, как минимум, еще 50 человек в сумме. А потом в прод. Навечно.
Правила переходов состояний - логика приложения, а не системы хранения данных. В конечном итоге окажется, что во первых приложение всё равно должно гарантировать соблюдение этих правил на своей стороне, а бд в свою очередь не гарантирует выполнение других/новых реализация которых на её уровне может оказаться делом затруднительным/невозможным/накладывающим ограничения.
Не говоря уже о зависимости от sql хранилища, удобства тестировании и тд.
Например: начальнику что-то не понравилось и он отправил в статус «коррекция» - все по новой до начальника.
тем кто не пишет системы документооборота - такой пример не понятен
чем хуже статус "документ нуждается в коррекции, стоп обработки" - пусть исполнитель пишет новый ?
А как спас то и от чего ?
Как алгоритм 1972 года спас наш проект и при чем тут Тарьян?