GraphDB
Теория графов изобретена Леонардом Эйлером .
в ходе решения задачи о 7 мостах в Кёнигсберге.
и представлена в Петербуржской Академии 26 августа 1735-го года.
Типы графов
Множественный, нагруженный, с поименованными вершинами, с поименованными ребрами, атрибутированные вершины и ребра, направленный и ненаправленный, связанный, хипер-граф, дерево, циклический и ациклический, планарный etc .
Граф дорог, нагруженный времен на отрезках
Граф дорог: путешествие
Социальная сеть aka stay in touch .
Facebook, Twitter, LinkedIn, ВКонтакте, Одноклассники етс етс .
Граф: ноды — люди (компании), ребра — «дружу», «служу», «работаю», «смотрю», «читаю» .
Алгоритмы — рекомендации:
* А не хочешь ли дружить с Петей, ибо с ним дружит твой друг Вася .
* Люди твоего семейного положения, возраста и достатка . любят смотреть рекламу о машинах .
Twitter: 3.43 / Facebook: 4.74 (source:Six degrees of separation)
Компьютерная сеть aka The Net .
Интернет сам по себе — компьютеры, свитчи, таблицы маршрутизации, пользователи . сайти и линки сайтов
Интересная презентация: Using A Graph Database To Power The “Web of Things” by Rick Bullotta and Emil Eifrem
Трансформации типов графов
Хранение графов: в реляционной базе
Хранение графов: в JSON / документной базе
Хранение графов: в xml
GraphDB: определение
Если графы можно хранить в любой базе, зачем термин graph db?
«Официального» определения не существует.
@twarko определяет это как: Граф база — это любое хранилище, реализующее «смежность» без использования индексов (index-free adjacency).
- Каждый элемент (ребро, вершина) напрямую знает о связанных элементах
- Не требуется o(ln(n)) поиск по индексу
- Если граф связан — это атомарная структура данных
Граф ДБ — можно рассматривать как распределенный индекс, когда в каждом элементе живет свой, маленький, кусочек индекса.
Граф ДБ — это о «локальных» вычислениях. Т.е. когда результат определяется «окрестностями» точки. «Глобальное вычисление» — плохо, нужно будет ходить по всем-всем точкам.
Neo4j: NOSQL for the Enterprise
Neo4j is a high-performance, NOSQL graph database with all the features of a mature and robust database.
«embedded, disk-based, fully transactional Java persistence engine that stores data structured in graphs rather than in tables»
“For anything with multiple relationships, multiple connections, Neo4j absolutely ROCKS!”
Werner Vogels, CTO of Amazon
http://neotechnology.com / Menlo Park, CA 94025 / 19 Malmo, Sweden
Несколько раз получали венчурный капитал, сейчас 25 человек в 5 странах етс .
Peter Neubauer, VP Product Management @peterneubauer
install neo4j ( Mac OS X )
Tinkerpop / http://tinkerpop.com
Open source software products in the graph space.
Blueprints: набор API ( a-la JDBC но для Graph DB 🙂 ) — реализации
Gremlin: язык обхода графов, работает со всеми базами у которых есть blueprints обертка
Rexter: превращаем BluePrints базу в REST server (http://localhost:8182/graphs/tinkergraph/vertices/1)
Pipes: библиотека для конструирования процессов обработки
Furnace: библиотека алгоритмов над графами
Frames: java object — graph bridge (ORM для графов)
Хочу данных!
- MovieLens 100k — Consists of 100,000 ratings from 1000 users on 1700 movies.
- MovieLens 1M — Consists of 1 million ratings from 6000 users on 4000 movies.
- MovieLens 10M — Consists of 10 million ratings and 100,000 tag applications applied to 10,000 movies by 72,000 users.
- Delicious bookmark data (105,000 bookmarks from 1867 users)
- Last.fm music artist data (92,800 artist listening records from 1892 users)
- MovieLens rating data with IMDb and Rotten Tomatoes links (86,000 ratings from 2113 users)
MovieLens
imdb данные
Создаем новую базу neo4j
Парсим входные файлы
«Гуляем» по данным
Надо еще подготовить уникальный список актеров:
NB: neo4j не дает назначить id вершинам, так что нужен «маппинг» из id файлов в ноды.
Как хранить граф в реляционной БД?
Т.е. указываем одни рёбра. Кажется, это не очень быстро. Посоветуйте, пожалуйста, чтива.
P.S. Основная база — PostgreSQL. Хотелось бы оставить все данные в ней.
В одной таблице хранить узлы, а в другой — связи между узлами?
Смотря какие операции нужны. Хранить можно много как, хоть в JSON засунуть и заgzipовать в BLOB-поле.
А как обходить граф? Имеет ли смысл хранить во второй таблице смежные вершины? Если понадобится писать свойства рёбер?
обходить просто — берем верхнюю вершину, достаем связи для нее из таблицы связей, переходим по ним и так далее. В принципе, можно хранить там и свойства ребер, ведь это и есть ребра по сути) Только во второй таблице нужно хранить в том порядке, чтоб обходить.
У этого модуля есть ограничение на 65 килобайт на поле. Стало интересно: сколько пользователей «влезет».
У меня соц. сеть с реферальной регистрацией. Пусть, каждый пользователь приводит в среднем 1.001 пользователя (реферала).
Так, если корневой пользователь наберёт 50 000 потомков, а это 9 999 552 пользователей, запись пути от корневого родителя до любого предка будет не более 58 995 симолов. Масштаб! 🙂
P.S. В документации говорится о 65Kb. Хочется верить, что это байты, но никак не биты: привык что байты обозначаются большой «B».
Охренеть, Вылдротень вернулсо!
Как твоя игра поживает? Как секс-зависимость? Велком бек он боард 🙂
Жена вчера пообещала уйти. Хе-хе, куда она с Бали денется?
Ты её заэтосамое штоле? 🙂 А чё на Бали, отдыхаешь аль дауншифтишь?
Если откровенно, она недолюбливает ЛОР, и в этом корень разногласий.
Отдыха тут нет: пива нет, водки нет, мяса нет, бляди страшные, местные — быдло, ни одного театра. Тут — фрилансю 🙂
Если откровенно, она недолюбливает ЛОР, и в этом корень разногласий.
Охренеть! =-O Ты же в последнее время почти не заходишь. Да и мало ли ты где сидишь. Похоже просто на попытку дое*ться на пустом месте, сорри 🙁
Отдыха тут нет: пива нет, водки нет, мяса нет, бляди страшные, местные — быдло, ни одного театра. Тут — фрилансю 🙂
Вали оттуда поскорее, у этой страны нет будущего, гореть ей в клоаке огненной! Чо, неужели нет стран с похожим климатом, но без вышеописанных critical bug’ов?
На Тенерифе мне понравилось, +23..+25 круглый год, правда, дожди всего пять дней в году. Пива хоть залейся. Девки отличные. Жрачка вкусная. Народ цивильный, университет даже есть, джазовые фестивали проводятся.
Но — надо знать испанский, иначе не выкрутишься. И иммиграционные правила жёсткие шо пездец, а сколько там можно по туристической визе тусить — не помню.
Как сохранить структуру данных графа в реляционной базе данных?
Я рассматривал возможность создания таблицы Vertices и таблицы Edges, но потребуется ли для построения графов в памяти и обхода подграфов большое количество поисковых запросов? Я хотел бы избежать чрезмерного чтения базы данных. Есть ли другой способ сохранить график?
Примечание: я слышал о Neo4j, но на самом деле мой вопрос заключается в том, как концептуально представить график в стандартной базе данных. Однако я открыт для некоторых решений NoSQL, таких как mongodb.
задан 03 сен ’13, 06:09
Чтобы дать вам ценный совет, мне нужно больше информации с вашей стороны. О скольких узлах и о скольких отношениях мы говорим? — Antoan Milkov
Ну, я бы сказал, миллиарды узлов. Как я уже сказал, это в основном концептуально, но мне любопытно, как масштабировать множество записей. Думаю, я имею в виду очень большие графики. — Frank Flannigan
Не с открытым исходным кодом, но это именно то, что вы ищете: новый Aster 6.0 поставляется с графическим движком в реляционной базе данных — он называется SQL-GR и предназначен для использования существующих и новых функций на графах, хранящихся в реляционных таблицах (в Aster): представлено с таблицей узлов и таблицей краев. — topchef
Я читал, что диаспора делает графики с использованием СУБД, но не уверен, какие требования к оборудованию должны быть, чтобы он поддерживал огромную базу (например, 70% facebook) или это даже возможно. — tgkprog
4 ответы
Ответ, к сожалению, таков: ваше соображение совершенно правильно во всех отношениях. Вы должны хранить узлы (вершины) в одной таблице и ребра, ссылающиеся на FromNode и ToNode, чтобы преобразовать структуру данных графа в реляционную структуру данных. И вы также правы, что это приводит к большому количеству поисков, потому что вы не можете разделить его на подграфы, которые могут быть запрошены сразу. Вам нужно пройти от узла к краю, к узлу, к краю, к узлу. и так далее (рекурсивно, пока SQL работает с наборами).
Дело в том.
Реляционные, графические, объектно-ориентированные, основанные на документах — это разные типы структур данных, отвечающие различным требованиям. Вот в чем все дело и почему появилось так много разных баз данных NoSQL (большинство из них представляют собой простые хранилища документов), потому что просто нет смысла организовывать большие данные реляционным способом.
Альтернатива 1 — База данных, ориентированная на граф
Но есть также базы данных NoSQL, ориентированные на графы, которые делают графовую модель данных первоклассной, такой как OrientDB с которым я немного играю в данный момент. Хорошая вещь в этом заключается в том, что, хотя он сохраняет данные в виде графика, его все же можно использовать в реляционной или даже объектно-ориентированной или документно-ориентированной манере (т.е. путем запросов с помощью простого старого SQL). Тем не менее Обход графа это оптимальный способ получить данные из него наверняка.
Вариант 2 — работа с графиками в памяти
Когда дело доходит до быстрой маршрутизации, такие платформы маршрутизации, как Графхоппер построить полный график (миллиарды узлов) внутри памяти. Поскольку Graphhopper использует MemoryMapped реализацию своего GraphStore, это работает даже на устройствах Android, которым требуется всего несколько МБ памяти. Полный граф считывается из базы данных в память при запуске, и затем маршрутизация выполняется там, поэтому вам не нужно искать базу данных.
+1 Кстати: единственная разница между «графовой БД» и «реляционной БД» заключается в реализация поиска. Если список ребер, указанный в таблице узлов, доступен через прямой указатель, его можно назвать БД графа, хотя данные все еще могут быть организованы в таблицы! Таким образом, если этот поиск является log (n) для списка ребер или даже для каждого ребра, тогда люди называют его «реляционной БД», и обход графа довольно дорог (независимо от того, является ли хранилище mmapped или в памяти или что-то еще) . — карусель
@Karussell Следует отметить, что большинство баз данных SQL поддерживают индексы на основе хэшей, при этом поиск ребер / вершин осуществляется за O (1), как и для базы данных графа. Время запроса O(log(n)) обычно связано с индексами на основе B-дерева, которые в основном используются, когда важна сортировка данных (что для идентификаторов ребер/вершин обычно не имеет значения). — Физик
Вы, вероятно, правы. Тем не менее индекс на основе хэша имеет накладные расходы (пространство и время) на практике IMO по сравнению с прямым указателем. Но, вероятно, используемая технология очень похожа для обеих БД, и только маркетинговая блабла делает их очень разными 🙂 — карусель
@Karussell log(n) не означает, что поиск медленный. Я сомневаюсь, что это приблизится ко всему остальному, что должен сделать запрос. Кроме того, может быть неплохо иметь ссылку, но что, если вам нужно пройти обратную связь? — Джастин Майнерс
Я столкнулся с этой же проблемой и решил, наконец, использовать следующую структуру, которая требует 2 запросов к базе данных, тогда остальная часть работы выполняется в памяти:
Сохраняйте узлы в таблице и ссылайтесь на график с каждой записью узла:
Также сохраните ребра в другой таблице и снова обратитесь к графу, к которому эти ребра принадлежат с каждым ребром:
Получите все узлы одним запросом, затем получите все ребра другим.
Теперь создайте предпочтительный способ хранения графа (например, список смежности) и продолжайте работу с приложением.
ответ дан 29 окт ’17, 09:10
Добавляя к предыдущим ответам тот факт, что MS SQL Server добавляет поддержка Graph Architecture начиная с 2017 года.
Он следует описанной модели наличия Nodes и Ребра таблицы (которые должны быть созданы со специальными ключевыми словами «AS NODE» и «AS EDGE»). 
Он также имеет новое ключевое слово MATCH, введенное «для поддержки сопоставления с образцом и обхода по графу», как это (друг — это имя край таблицу в приведенном ниже примере):
Я собираюсь не согласиться с другими сообщениями здесь. Если у вас есть особый класс графов с ограничениями, вы часто можете обойтись более специализированным дизайном (например, ограниченное количество ребер на вершину, нужно пройти только в одну сторону и т. д.).
Однако для хранения произвольного графа реляционные базы данных обеспечивают невероятно хороший набор компромиссов, которые хорошо работают практически во всех ситуациях. Кроме того, потребности в данных со временем меняются, а реляционная база данных позволяет безболезненно изменять хранилище и поиск без изменения представления данных.
Давайте рассмотрим ваш дизайн:
- одна таблица для вершин (id, данные)
- одна таблица для ребер (startId, endId, data)
Сначала обратите внимание, что хранилище эффективно, поскольку оно пропорционально хранимым данным. Если у нас есть 10 вершин и 10 ребер, мы храним 20 единиц информации.
Теперь давайте посмотрим на поиск. Предполагая, что у нас есть индекс по идентификатору вершины, мы можем искать любые данные, которые захотим, по крайней мере log(n) (возможно, лучше в зависимости от индекса).
- Учитывая узел, скажите мне ребра, выходящие из него
- Учитывая узел, сообщите мне ребра, входящие в него
- Учитывая ребро, сообщите мне узел, из которого оно пришло или входит
Это все основные запросы, которые вам нужны.
Теперь предположим, что у вас есть «база данных графов», в которой хранится список ребер, выходящих из каждой вершины. Это делает размер каждой вершины переменным. Немного легче пройти. Но что, если вы хотите пройти в другом направлении? Теперь у вас есть список ребер, входящих в каждую вершину. Теперь у вас есть две копии этой информации, и база данных (или вы, разработчик) должны проделать большую работу, чтобы они никогда не рассинхронизировались.
O (журнал (n)) против O (1)
Индексы реляционной базы данных обычно хранят данные в отсортированной форме или, как указывали другие, также могут использовать хеш-таблицу. Даже если вы застряли с sorted, он будет работать очень хорошо.
Во-первых, обратите внимание, что big oh измеряет масштабируемость, а не производительность. Хэши могут быть медленнее, чем многие циклы для небольших наборов данных. Несмотря на хеширование O(1) лучше, бинарный поиск O(log2) чертовски хорош. Вы можете найти миллиард записей за 30 шагов! Кроме того, он совместим с кэшем и предсказателем ветвлений.
Хранение графовых данных в БД Vertica
В одном из проектов возникла необходимость работы с графовыми данными.
Сначала поискали готовые решения в сети.
Графовые модели мало распространены. В интернете много перепостов о графах с точки зрения математики, много аппроксимированных примеров, которые с практической точки зрения оказались непригодны даже для небольших объемов данных. Поэтому пришлось изобретать велосипед, сконструировав модель укладки данных и разработав простейшие методы для поиска оформленных в ТЗ закономерностей и аномалий.
Основное отличие графовых данных от реляционных (табличных) — акцент на взаимосвязях между объектами (вершинами), более широкий диапазон возможностей подобного анализа и низкая вычислительная стоимость алгоритмов в упомянутом сегменте. Реляционные модели, напротив, прекрасно приспособлены для препарирования внутренних свойств объектов.
Графовые модели мало распространены. С этим отчасти связано (с отсутствием инструментов для анализа и работы в этой сфере) разрушение за последние 30 лет производственных цепочек и нагрузка деструктивными хаотичными составляющими взаимодействия между социальными группами.
У нас стояла задача выявления деструктивных участков в цепочках перемещения продуктовых партий. Один из модулей так и назывался: «Компонент выявления лишних посредников». Сырые данные были в виде полусотни таблиц и справочников, объем таблиц с данными от сотен млн. до десятков млрд. строк. Инструмент для работы — БД Vertica из 3 нод, поднятых в виртуалке.
После пары попыток вычисления остановились на варианте преобразования данных в таблицу ребер, содержащую служебную информацию.
Существует 3 основных способа укладки графовых данных в таблицу.
Матрица смежности
Данный способ на большинстве интернет ресурсов позиционируется как единственный. Пригоден для ограниченного количества ситуаций, когда число уникальных вершин не более ограничений на максимальное число колонок в базе данных. Например, при вычислении логистики между городами. Сами значения можно заполнить не только бинарными данными (True, False), но и одной из характеристик взаимосвязи. К примеру, в случае расчета оптимальной логистики это будет реальное время прохождения участка с учетом погодных условий, пробок, ДТП, ремонтов. Но значение можно сунуть только одно, или придется дублировать таблицу.
Список смежности
Удобный способ как для представления разреженных графов и реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.
Список ребер (таблица ребер)
В большинстве ситуаций наиболее удобный способ хранения данных. Таблицу можно дополнять столбцами со служебными характеристиками положения в графе данного звена, свойствами взаимосвязи и вершин. Основной недостаток – быстрое разрастание таблицы в длину.
Данные представляли собой деревья.
Для предобработки сырых данных использовался алгоритм «Обход графа в ширину». То есть за один проход формировался «этаж» записей, добавлялся номер level, соответствующий «этажу», звено цепочки в path2FATHER и число ветвлений в count_branch. В сырых данных отсутствовали прямые связи между вершинами, для их связи использовались совпадающие id записей в журнал.
Из служебной информации были добавлены колонки:
FATHER — корень каждой цепочки, вершина из которой начинается ветвление,
level — удаленность от корня, «этаж»,
maxlevel — максимальная величина level при ветвлении из данной точки,
path2FATHER — разделенные запятыми ID в цепочке между данной вершиной и FATHER,
count_branch — число ветвлений в каждой точке цепочки между данной вершиной и FATHER.
Техническая информация состояла из ID и наименований категорий перемещаемого или создаваемого продукта, хозяйствующего субъекта, площадки, времени транзакции, пары десятков различных вычисленных коэффициентов и статусов.
Таблица ребер со служебными полями.
Распарсивание id из цепочки path2FATHER выполнялось встроенной в Vertica функцией v_txtindex.StringTokenizerDelim:
В данном проекте для визуализации была использована библиотека GOJS. Функция использовалась для выгрузки данных из Vertica.
Помимо алгоритмов поиска аномалий, затребованных в ТЗ, описание которых по понятным причинам не приводится, был получен достаточно очевидный признак лишних посредников, когда у партии товара в течение короткого промежутка времени меняется перечень владельцев, при этом товар остается в рамках одного склада (площадки) и его номенклатура не меняется (не производится изготовление сметаны из молока).
Другими словами, когда смена владельца партии товара связана не с транспортировкой или производственным преобразованием, а со стремлением «коммерсантов» накрутить цену на сырье или продукцию. С этой целью создаются от 7 до 30 ООО или ИП, и партия товара прогоняется через эту цепочку, обычно задерживаясь в каждом звене не более 3-х — 4-х часов.