Yii Framework
Узел 7 ссылается на узел 1.
Насколько я понимаю это граф. У меня возникла проблема как его лутше сохранять в БД ? И потом обходить его.
Все что нашел ето для каждого узла отдельно хранить в список всех соседних узлов к примеру в json. Или вде таблици в первшой все узлы во второй все переходы.
Есть ли какие то готовые поведения для этого? Все что нарыл это nested set но он не подходит так как листя у меня могут ссылатся на верхнее уровни. вплоть до корня.
Есть какие то идеи по етому поводу?
Скахин Алексей / pihel
В этой статье хотел бы осветить основные аспекты быстрого доступа к графовым данным
Графовые данные можно технически хранить 3 известными мне способами:
1. В реалиционных базах:
* Данные хранятся в плоских таблицах
* Связи между сущностями осуществляются через индексированные внешие ключи
2. Документные базы:
* Связанные данные лежат прямо в колонках основной таблицы
К примеру, информация о друзьях аккаунта положена в json поле таблицы
3. Графовая база
Остановимся подробней на примере бд Neo4j:
* Отдельно хранятся данные о нодах, ребрах и значениях в ноде в разных файлах
* Нода (Node) имеет фиксированный размер, что позволяет переходить к ней в файле по смещению за константное время: ID * fixed size
[ 1 байт — активность | 4 байт — указатель на файл связи | 5 байт — указатель на файл свойств ]
* файл соединение (Relationship — ребра) состоит:
[ 5 байт — файл 1 ноды | 5 байт — файл 2 ноды | тип соединение | указатель на следующий relation | указатель на предыдущий relation ]
первый 10 байт — это обратные ссылки на ноды, что в сочетании с сылками в нодах дает двунаправленный список
* Связанный список свойств
повторяющиеся значения сжимаются в словарь, а в самом property хранится ссылка на словарь
если значение достаточно маленькое, то оно хранится прямо в property файл
Графически это можно представить следующим образом:
Какие же преимущества дает такой тип хранения данных:
| Показатель | Графовая | Реалиционная | Документная |
| Простота выборки | Синтаксис проще и короче релиционной схемы: |
MATCH (john:Person < name:"John" >)- [:friend *1..2]->(friend: Person) RETURN friend.name, friend.age
WITH RECURSIVE r AS ( SELECT id, parent_id, name, 1 AS level FROM geo WHERE UNION ALL SELECT geo.id, geo.parent_id, geo.name, r.level + 1 AS level FROM geo JOIN r ON geo.parent_id = r.id ) SELECT * FROM r
val theget= new Get(Bytes.toBytes("rowkey1")) val result=table.get(theget) val value=result.value() println(Bytes.toString(value))
Исходя из этих данных можно сделать вывод, что графовые бд производительней реляционных во всех случаях и быстрей документных, если в графе больше 1 ребра.
Еще чуть информации об внутреннем устройстве Neo4J:
* для данных используется LFU кэш (least freaq use) — аналогично Oracle
* есть возможность горизонтального масштабирования черзе шардирования по одному из ключей графа
* Параллелизация запроса возможна через парадигму map-reduce, если задача разбивается на подзадачи
** собирается массив параметров, по которому будем параллелить
** запускаем запрос в N потоков, передавая порцию данных
** собираем результат от потоков и выполняется доагрегация в reduce
#параметры with collect(distinct a) as addresses # 1 параметр - код, для выполнения в потоке # 2 - параметры параллелизации и шага # 3 - параметры для передачи в поток # 4 - спит параметров на число партиций CALL apoc.cypher.mapParallel2(" optional match (_)<-[:LOCKED_BY]-(o: Output) where not (o)-[:UNLOCKED_BY]->() return _.address as address, round(sum(o.bitcoinValue)*100000000)/100000000 as balance" , , addresses, 20) yield value
Принципы хранение связей между объектами в SQL
При решении ряда задач возникает необходимость сохранять связи между объектами. К примеру, для поисковых задач нахождения пути — схемы маршрутов из точки А в точку Б. В социальных сетях необходимо хранить информацию о друзьях или подписчиках. На форумах присутствуют связи между пользователями и их сообщениями, сообщениями и ветками форума к которым они принадлежат. В корпоративных порталах необходимы связи пользователей и отделов корпорации, взаимоотношения коллег и так далее.
В большинстве случаев это односторонние связи — к примеру, принадлежность сообщения пользователю или пользователя к отделу в компании. Для этих связей признак направленности не нужен.
Но есть и случаи когда связи требуют признака направленности — маршруты из точки А в точку Б и из точки в Б в точку А могут кардинально отличаться, ведь существуют дороги с односторонним движением. Да и для определения взаимоотношений между пользователями — А может быть подписчиком Б, при этом Б в принципе может и не знать о существовании А.
Давайте рассмотрим самый неблагоприятный для нас случай:
Связи должны иметь направленность (двусторонние или односторонние).
Всю информацию о связях мы должны хранить в базе данных.
И как вариант, в самом конце, рассмотрим высоконагруженную систему, для которой требуется разделение баз данных по разным серверам (шардирование).
Но прежде, чем начать практическое воплощение, давайте освежим воспоминания по курсу математики.
Несколько слов о графах
Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).
Вершинами графа, в нашем случаи, будут рассматриваемые объекты (пользователи, сообщения, точки на карте, отделы компании и т.д.). В качестве ребер графа будут выступать связи между нашими объектами.
В теории графов, есть понятие «ориентированный граф». Этот тип графов описывает не только наличие связей между вершинами, но и направленность этих связей — как раз то что нам нужно. Ну а раз есть такое понятие, то математическое описание скорее всего тоже существует. Давайте не будем гадать — существует даже несколько описаний.
Матрица инцидентности
На мой взгляд это не самое лучший вариант представления графа. Более того, на данный момент я не вижу практической пользы от его использования. Но как сами понимает, простоя просто я еще не столкнулся с задачей, которая потребовала бы именно этого представления. Так что давайте рассмотри и его.
В чем суть. Дана матрица, столбцы которой это ребра графа, а строки — вершины графа. Каждая ячейка отображает взаимоотношение между конкретной вершиной и ребром. Возьмем для примера ячейку (10,2) — значение в этой ячейки будет определять взаимоотношение между 10ым ребром и 2ой вершиной.
Взаимоотношения определяются достаточно просто:
1 — ребро выходит из вершины.
-1 — ребро входит в вершину.
0 — для всех остальных случаем (нет связи или петля).
Размеры таблицы в базе данных:
Максимальное количество столбцов = 2 * количество вершин + 1 (первичный ключ таблицы базы данных).
Максимальное количество строк = количество вершин.
При воплощении данного представления могут возникнуть следующие затруднения:
При добавлении новой связи (нового ребра графа) вам придется добавлять еще одну колонку. Если вы храните ваш граф в двумерном массиве, то тут вопросов нет, а вот для случая базы данных — динамическое добавление новых столбцов в процессе работы скрипта, считается дурным тоном, хотя и возможно.
Помимо нумерации вершин (строки), приходится хранить еще и номера ребер. Причем надо понимать, что если между вершинами есть двусторонняя связь, то она отражается двумя разными ребрами.
Очень трудно делать выборки из базы данных о взаимоотношениях объектов. Чтобы выявить связь вполне возможно, что вам придется перебрать всю таблицу.
Мало вероятно, что вам понадобятся петли в графе, но тем не менее. Для отличия петель вам нужно будет уйти от классического построения и добавить новое возможно значение ячейки, к примеру 2. В классическом представлении отсутствие связи и петли обозначаются 0.
Достоинств представления, к сожалению, я пока назвать не могу, но они несомненно должны быть.
Я вижу возможность применения представления в виде матрицы инцидентности для следующих случаев:
Для систем, в которых заранее известно число вершин и число связей (для исключения динамического добавления столбцов таблицы). Причем число этих вершин и связей не велико для сокращения времени выборки и анализ связей.
Для систем требующих графического отображения графов (это уже не наша задача).
Матрица смежности
На мой взгляд это менее емкий способ представления графа. В данном случаи мы имеем матрицу, столбцы и строки которой являются вершинами графа, а значения ячеек отображают связи. Так например, ячейка (10,2) отображает отношение 10ой вершины ко 2ой. Значения на главной диагонали матрицы отображают наличие петель у вершины.
Взаимоотношения определяются элементарно:
1 — есть связь.
0 — нет связи.
Для определения двусторонности связи потребуется проверить всего две зеркальные относительно главной диагонали ячейки.
Размеры таблицы в базе данных:
Максимальное количество столбцов = количество вершин + 1 (первичный ключ таблицы базы данных).
Максимальное количество строк = количество вершин.
Ограниченное число вершин.
Представление хранит избыточную информацию (отсутствие связей).
Простые поисковые запросы (ищем только две строки).
Я вижу возможность применения представления в виде матрицы смежности для следующих случаев:
Для систем, в которых заранее известно только число вершин. Количество вершин может быть существенно больше по сравнению с матрицей инцидентности.
Список ребер
На мой взгляд это самый адекватный способ хранения информации о связях. Посмотрите хотя бы на название.
Итак, у нас есть список, каждая строка которого содержит номера двух вершин. Просто, не правда ли?
Для определения двусторонности связи потребуется так же две записи из списка.
Размеры таблицы в базе данных:
Максимальное количество столбцов = 2 номера вершин + 1 (первичный ключ таблицы базы данных).
Максимальное количество строк = 2 * количество вершин.
Простые поисковые запросы (ищем только две строки).
Не содержит избыточной информации — хранятся только записи существующих связей.
Мне кажется, что данное представление подходит для подавляющего большинства проектов.
Практическая реализация
В этом разделе мы рассмотрим практическую реализацию способа хранения связей. Как вы уже догадались мы будем разбирать представление «Список ребер», а так же, как я и обещал, посмотрим вариант реализации хранения связей для высоконагруженных систем.
Список ребер
Общий принцип остается без изменения. Рассмотрим структуру и поисковые запросы на примере таблице links.
Структура таблицы
key — первичный ключ
object1 — идентификатор первой вершины
object2 — идентификатор второй вершины
Итак каждая запись отображает связь между двумя вершинами, причем направление определяется порядком следования идентификаторов вершин. Другими словами запись (1, 10, 2) отображает связь от 10ой вершины ко 2ой, а запись (2, 2, 10) отображает обратную связь.
Запросы к базе данных
Запрос на внесение связи от вершины node1 к вершине node2:
SQL: INSERT INTO `links` SET `object1` = 'node1', `object2` = 'node2';
Запрос для определения всех связей идущих от вершины node1:
SQL: SELECT `object2` FROM `links` WHERE `object1` = 'node1';
Запрос для определения всех связей идущих к вершине node1:
SQL: SELECT `object1` FROM `links` WHERE `object2` = 'node1';
Запрос на проверку наличия двухсторонней связи между вершинами node1 и node2:
SQL: SELECT COUNT(`key`) FROM `links` WHERE (`object1` = 'node1' AND `object2` = 'node2') OR (`object1` = 'node2' AND `object2` = 'node1');
Связи в высоконагруженной системе
Представим, что мы проектируем высоконагруженную систему и предполагается высокая нагрузка на таблицу связей. Поэтому нам придется как-то распределять нагрузку между несколькими серверами. Будем считать, что мы используем метод шардирования базы данных.
Согласно этой концепции мы будем распределять записи по разным базам данных на основании некого хеша от поля object1. Теперь давайте подумаем. Для поиска связей исходящих из вершины все просто — мы ищем по полю object1, а все эти записи хранятся в одной базе. Но что будет если мы начнем искать связи идущие к заданной вершине? Тут придется искать по полю object2, а такие записи могут быть в разных базах.
Для решения этого конфликта я предлагаю такую простую схему:
Мы перенесем всю информацию направленности о связей между двумя заданными вершинами в одну запись.
Мы будем создавать две зеркальные записи.
Перенос информации о направленности связей в одну запись позволит получив всего лишь одну запись сказать, есть ли связь между вершинами и какой она направленности.
А две зеркальные записи позволят нам формировать все поисковые запросы только полю object1. Соответственно разрешается проблема разноса информации по разным базам данных.
Хранение графовых данных в БД 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-х часов.