Как хранить граф в реляционной БД?
Т.е. указываем одни рёбра. Кажется, это не очень быстро. Посоветуйте, пожалуйста, чтива.
P.S. Основная база — PostgreSQL. Хотелось бы оставить все данные в ней.
wyldrodney ☆
07.12.13 14:00:12 MSK
В одной таблице хранить узлы, а в другой — связи между узлами?
POLTER ★★
( 07.12.13 14:02:39 MSK )
Смотря какие операции нужны. Хранить можно много как, хоть в JSON засунуть и заgzipовать в BLOB-поле.
Legioner ★★★★★
( 07.12.13 14:04:33 MSK )
Ответ на: комментарий от POLTER 07.12.13 14:02:39 MSK
А как обходить граф? Имеет ли смысл хранить во второй таблице смежные вершины? Если понадобится писать свойства рёбер?
wyldrodney ☆
( 07.12.13 14:13:06 MSK ) автор топика
Ответ на: комментарий от wyldrodney 07.12.13 14:13:06 MSK
обходить просто — берем верхнюю вершину, достаем связи для нее из таблицы связей, переходим по ним и так далее. В принципе, можно хранить там и свойства ребер, ведь это и есть ребра по сути) Только во второй таблице нужно хранить в том порядке, чтоб обходить.
POLTER ★★
( 07.12.13 20:24:03 MSK )
У этого модуля есть ограничение на 65 килобайт на поле. Стало интересно: сколько пользователей «влезет».
У меня соц. сеть с реферальной регистрацией. Пусть, каждый пользователь приводит в среднем 1.001 пользователя (реферала).
Так, если корневой пользователь наберёт 50 000 потомков, а это 9 999 552 пользователей, запись пути от корневого родителя до любого предка будет не более 58 995 симолов. Масштаб! 🙂
P.S. В документации говорится о 65Kb. Хочется верить, что это байты, но никак не биты: привык что байты обозначаются большой «B».
wyldrodney ☆
( 08.12.13 07:36:43 MSK ) автор топика
Охренеть, Вылдротень вернулсо!
Как твоя игра поживает? Как секс-зависимость? Велком бек он боард 🙂
anonymous
( 08.12.13 07:40:28 MSK )
Ответ на: комментарий от anonymous 08.12.13 07:40:28 MSK
Жена вчера пообещала уйти. Хе-хе, куда она с Бали денется?
wyldrodney ☆
( 08.12.13 07:43:29 MSK ) автор топика
Ответ на: комментарий от wyldrodney 08.12.13 07:43:29 MSK
Ты её заэтосамое штоле? 🙂 А чё на Бали, отдыхаешь аль дауншифтишь?
anonymous
( 08.12.13 07:49:42 MSK )
Ответ на: комментарий от anonymous 08.12.13 07:49:42 MSK
Если откровенно, она недолюбливает ЛОР, и в этом корень разногласий.
Отдыха тут нет: пива нет, водки нет, мяса нет, бляди страшные, местные — быдло, ни одного театра. Тут — фрилансю 🙂
wyldrodney ☆
( 08.12.13 07:55:50 MSK ) автор топика
Ответ на: комментарий от wyldrodney 08.12.13 07:55:50 MSK
Если откровенно, она недолюбливает ЛОР, и в этом корень разногласий.
Охренеть! =-O Ты же в последнее время почти не заходишь. Да и мало ли ты где сидишь. Похоже просто на попытку дое*ться на пустом месте, сорри 🙁
Отдыха тут нет: пива нет, водки нет, мяса нет, бляди страшные, местные — быдло, ни одного театра. Тут — фрилансю 🙂
Вали оттуда поскорее, у этой страны нет будущего, гореть ей в клоаке огненной! Чо, неужели нет стран с похожим климатом, но без вышеописанных critical bug’ов?
anonymous
( 08.12.13 07:59:43 MSK )
Ответ на: комментарий от anonymous 08.12.13 07:59:43 MSK
На Тенерифе мне понравилось, +23..+25 круглый год, правда, дожди всего пять дней в году. Пива хоть залейся. Девки отличные. Жрачка вкусная. Народ цивильный, университет даже есть, джазовые фестивали проводятся.
Но — надо знать испанский, иначе не выкрутишься. И иммиграционные правила жёсткие шо пездец, а сколько там можно по туристической визе тусить — не помню.
Yii Framework
Узел 7 ссылается на узел 1.
Насколько я понимаю это граф. У меня возникла проблема как его лутше сохранять в БД ? И потом обходить его.
Все что нашел ето для каждого узла отдельно хранить в список всех соседних узлов к примеру в json. Или вде таблици в первшой все узлы во второй все переходы.
Есть ли какие то готовые поведения для этого? Все что нарыл это nested set но он не подходит так как листя у меня могут ссылатся на верхнее уровни. вплоть до корня.
Есть какие то идеи по етому поводу?
как хранить в БД граф value object
Как видно из названия классов — объекты типа EntityA являются сущностями(в терминах DDD), а объекты типов ValueObjectA и ValueObjectB — объектами значениями. Нужно определить каким образом хранить в БД данный граф объектов. Что вызвало у меня трудности: связь между EntityA и ValueObjectA — один-ко-многим, между ValueObjectA и ValueObjectB тоже один-ко-многим. В этом случае логично для каждого класса создать отдельную таблицу в БД и связать эти таблицы между собой. Проблема возникает в связывании этих таблиц. Я не хочу добавлять в классы ValueObjectA и ValueObjectB идентификаторы, хочу чтобы они остались полноценными value object. В этом случае связать таблицы EntityA и ValueObjectA очень просто, а вот как связать таблицы ValueObjectA и ValueObjectB — я ума не приложу.
Хранение графовых данных в БД Vertica
В одном из проектов возникла необходимость работы с графовыми данными.
Сначала поискали готовые решения в сети.
Графовые модели мало распространены. В интернете много перепостов о графах с точки зрения математики, много аппроксимированных примеров, которые с практической точки зрения оказались непригодны даже для небольших объемов данных. Поэтому пришлось изобретать велосипед, сконструировав модель укладки данных и разработав простейшие методы для поиска оформленных в ТЗ закономерностей и аномалий.
Основное отличие графовых данных от реляционных (табличных) — акцент на взаимосвязях между объектами (вершинами), более широкий диапазон возможностей подобного анализа и низкая вычислительная стоимость алгоритмов в упомянутом сегменте. Реляционные модели, напротив, прекрасно приспособлены для препарирования внутренних свойств объектов.
Графовые модели мало распространены. С этим отчасти связано (с отсутствием инструментов для анализа и работы в этой сфере) разрушение за последние 30 лет производственных цепочек и нагрузка деструктивными хаотичными составляющими взаимодействия между социальными группами.
У нас стояла задача выявления деструктивных участков в цепочках перемещения продуктовых партий. Один из модулей так и назывался: «Компонент выявления лишних посредников». Сырые данные были в виде полусотни таблиц и справочников, объем таблиц с данными от сотен млн. до десятков млрд. строк. Инструмент для работы — БД Vertica из 3 нод, поднятых в виртуалке.
После пары попыток вычисления остановились на варианте преобразования данных в таблицу ребер, содержащую служебную информацию.
Существует 3 основных способа укладки графовых данных в таблицу.
Матрица смежности
Данный способ на большинстве интернет ресурсов позиционируется как единственный. Пригоден для ограниченного количества ситуаций, когда число уникальных вершин не более ограничений на максимальное число колонок в базе данных. Например, при вычислении логистики между городами. Сами значения можно заполнить не только бинарными данными (True, False), но и одной из характеристик взаимосвязи. К примеру, в случае расчета оптимальной логистики это будет реальное время прохождения участка с учетом погодных условий, пробок, ДТП, ремонтов. Но значение можно сунуть только одно, или придется дублировать таблицу.
Список смежности
a: b: c: d: e: f:
Удобный способ как для представления разреженных графов и реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.
Список ребер (таблица ребер)
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-х часов.