Хранение графовых данных в БД Vertica

В одном из проектов возникла необходимость работы с графовыми данными.

Сначала поискали готовые решения в сети.

Графовые модели мало распространены. В интернете много перепостов о графах с точки зрения математики, много аппроксимированных примеров, которые с практической точки зрения оказались непригодны даже для небольших объемов данных. Поэтому пришлось изобретать велосипед, сконструировав модель укладки данных и разработав простейшие методы для поиска оформленных в ТЗ закономерностей и аномалий.

Основное отличие графовых данных от реляционных (табличных) — акцент на взаимосвязях между объектами (вершинами), более широкий диапазон возможностей подобного анализа и низкая вычислительная стоимость алгоритмов в упомянутом сегменте. Реляционные модели, напротив, прекрасно приспособлены для препарирования внутренних свойств объектов.

Графовые модели мало распространены. С этим отчасти связано (с отсутствием инструментов для анализа и работы в этой сфере) разрушение за последние 30 лет производственных цепочек и нагрузка деструктивными хаотичными составляющими взаимодействия между социальными группами.

У нас стояла задача выявления деструктивных участков в цепочках перемещения продуктовых партий. Один из модулей так и назывался: «Компонент выявления лишних посредников». Сырые данные были в виде полусотни таблиц и справочников, объем таблиц с данными от сотен млн. до десятков млрд. строк. Инструмент для работы — БД Vertica из 3 нод, поднятых в виртуалке.

После пары попыток вычисления остановились на варианте преобразования данных в таблицу ребер, содержащую служебную информацию.

Существует 3 основных способа укладки графовых данных в таблицу.

Матрица смежности 

Данный способ на большинстве интернет ресурсов позиционируется как единственный. Пригоден для ограниченного количества ситуаций, когда число уникальных вершин не более ограничений на максимальное число колонок в базе данных. Например, при вычислении логистики между городами. Сами значения можно заполнить не только бинарными данными (True, False), но и одной из характеристик взаимосвязи. К примеру, в случае расчета оптимальной логистики это будет реальное время прохождения участка с учетом погодных условий, пробок, ДТП, ремонтов. Но значение можно сунуть только одно, или придется дублировать таблицу.

Список  смежности

a: {b, e}
b: {a, c, e, f}
c: {b, d, f}
d: {c, e}
e: {a, b, d}
f: {b, c}

Удобный способ как для представления разреженных графов и реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.

Список ребер (таблица ребер)

a b
a e
b c
b e 
b f
c d
c f
d e

В большинстве ситуаций наиболее удобный способ хранения данных. Таблицу можно дополнять столбцами со служебными характеристиками положения в графе данного звена, свойствами взаимосвязи и вершин. Основной недостаток – быстрое разрастание таблицы в длину.

Данные представляли собой деревья.

Для предобработки сырых данных использовался алгоритм «Обход графа в ширину». То есть за один проход формировался «этаж» записей, добавлялся номер level, соответствующий «этажу», звено цепочки в path2FATHER и число ветвлений в count_branch.  В сырых данных отсутствовали прямые связи между вершинами, для их связи использовались совпадающие id записей в журнал.

Из служебной информации были добавлены колонки:

• FATHER — корень каждой цепочки, вершина из которой начинается ветвление,

• level — удаленность от корня, «этаж»,

• maxlevel — максимальная величина level при ветвлении из данной точки,

• path2FATHER — разделенные запятыми ID в цепочке между данной вершиной и FATHER,

• count_branch — число ветвлений в каждой точке цепочки между данной вершиной и FATHER.

Техническая информация состояла из ID и наименований категорий перемещаемого или создаваемого продукта, хозяйствующего субъекта, площадки, времени транзакции, пары десятков различных вычисленных коэффициентов и статусов.

Таблица ребер со служебными полями.

Распарсивание id из цепочки path2FATHER выполнялось встроенной в Vertica функцией v_txtindex.StringTokenizerDelim:

SELECT  v_txtindex.StringTokenizerDelim(path2FATHER, ',') OVER()
FROM public.br_RT_0_18
WHERE cert2 = '123456’;

В данном проекте для визуализации была использована библиотека GOJS. Функция использовалась для выгрузки данных из Vertica.

Помимо алгоритмов поиска аномалий, затребованных в ТЗ, описание которых по понятным причинам не приводится, был получен достаточно очевидный признак лишних посредников, когда у партии товара в течение короткого промежутка времени меняется перечень владельцев, при этом товар остается в рамках одного склада (площадки) и его номенклатура не меняется (не производится изготовление сметаны из молока).

Другими словами, когда смена владельца партии товара связана не с транспортировкой или производственным преобразованием, а со стремлением «коммерсантов» накрутить цену на сырье или продукцию. С этой целью создаются от 7 до 30 ООО или ИП, и партия товара прогоняется через эту цепочку, обычно задерживаясь в каждом звене не более 3-х — 4-х часов.