Представление Графовых баз данных (Перевод)

Перевод 12 главы книги NoSQL for Mere Mortals by Dan Sullivan.

Темы затроннутые в этой главе

Критерии Конструирования для Графовых баз данных

Графы и Сетевые модели

Преимущества Графовых Баз Данных

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

Что такое Граф?

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

Вершины представляют собой вещи. Это может быть что угодно , включая:

• Города
• Сотрудников компании
• Белки
• Электрические цепи
• Соединения в водопроводе
• Организмы в экосистеме
• Железнодорожные станции

Одна вещь, которая является общей для всех этих вещей в том, что они имеют отношения к другим вещам, часто в той же категории. Города связаны с другими городами  дорогами. Сотрудники работают с другими сотрудниками.Белки взаимодействуют с другими белками.Электрические цепи связаны с другими электрическими цепями. Места соединения водопроводе подключены к другим соединениям. Организмы в экосистемах являются хищниками и добычей для других организмов. Железнодорожные станции связанны с другими станциями по железнодорожным путям.

Связи или соединенния между объектами представлены ребрами.Это может показаться очевидным представлением для некоторых отношений, таких как дороги и железнодорожные пути между городами. Но, это так же может быть менее очевидным и в других случаях, на напримере белков и организмов в экосистеме. Гибкая природа вершин и ребер делает их идеальнимы для моделирования абстрактных и конкретных отношений между вещами.

На рисунке 12.1 показан простой граф с двумя вершинами и одним ребром.

Рисунок 12.1 Простой граф с двумя вершинами и одним ребром.

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

Графы и и сетевое моделирование

На первый взгляд, очевидно, что графы хорошо подходят для моделирования сетей.

Тем не менее, может показаться, что сети являются специализированными системами и не обобщены в широком кругу проблем; это предположение неверно. Если вы думаете о сетях как о вещах и отношениям между этими вещами, вы увидете сети вокруг. Вот несколько примеров которые могут отобразить широту проблем, которые  вы можете решать с помощью сетевого моделирования в виде графов.

Моделирование географических местоположений

Автомобильные дороги и железные пути имеют два различных свойства, которые интересуют нас: они предназначены, чтобы связьвать географические местоположения, и длиные промежутоки времени.

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

Автомобильные дороги можно смоделировать двумя способами. Дорога может быть одним ребром между двумя городами, в этом случае она моделирует дорожное движение в обоих направлениях. В качестве альтернативы, графическое представление может использовать два ребра, один для представления в каждом направлении (например, с востока на запад и с запада на восток). Какой  же "правильный путь",  для моделирования автодорог? Это зависит от многих вещей.

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

Рисунок 12.2 Автомобильные дороги между городами смоделированны как вершины и ребра.

Моделирование инфекционных заболеваний

Инфекционные заболевания могут передаваться от человека к человеку. Например, человек кашляет в руку после чего бактерии и вирусы оставляют на его руке.Когда этот человек пожимает руку кого-то другого, то есть шанс, что вирус передается другому человеку, который со временем может стать зараженными. Распространение инфекционных заболеваний легко моделируется с помощью графов.

Вершины представляют собой людей, в то время как ребра представляют собой взаимодействие между людьми, рукопожатие или стояние в непосредственной близости.

Обе вершины и ребра имеют свойства, которые помогают представлять путь распространения болезни (рис 12.3).

Рисунок 12.3 Распространение гриппа и других инфекционных заболеваний смоделированные в виде графов.

Люди имеют свойства, такие как возраст и вес. В случае модели инфекционного заболевания, наиболее важным свойством является статус инфекции, которая может быть

• Не инфицированный в данный момент,и никогда не был инфицирован
• Не инфицированный в данный момент,но был инфицирован в прошлом
• Инфицирован в данный момент
• Имеет имунитет

Необходимо следить за этими свойствами поскольку они влияют на вероятность инфицирования:

• Если вы не заражены и никогда не были, у вас есть умеренно высокая вероятность инфицирования при контакте с инфицированным человеком.
• Если вы не заражены, но были заражены в прошлом, вы, вероятно, приобрели некоторый иммунитет к инфекционным заболеваниям. Это означает, что у вас есть низкая вероятность заражения при контакте с инфицированным человеком.
• Если вы инфицированы и вступили  в контакт с другим инфицированным человеком, вы оба остаетесь зараженными. Без изменений.
• Если у вас есть иммунитет, либо из-за врожденного иммунитета или медицинской иммунизации, то вы не заразитесь при контакте с другим инфицированным человеком.

Состояние графа инфекционной болезни будет часто меняться в виде взаимодействия людей; некоторые люди будут становиться зараженными в то время как другие будут восстанавливаться после болезни. Как видите, это отличается от железных и автомобильных дорог, в тоже время мы остаемся неизменными в использовании терминов - узлов и ребер.

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

Ребра или в нашем случае, взаимодействие между людьми -  это свойства.Например, существует вероятность того, что кто-то будет передавать болезнь другому человеку, пожимая руку. Данное взаимодействие имеет более высокую скорость передачи болезни , чем двое людей, стоящих в непосредственной близосте не касаясь друг друга. Некоторые возбудители требуют физического контакта для распространения болезни, в то время как другие воздушно-капельные  заболевания могут передавать без непосредственного контакта.Эти виды свойств, которые будут связаны с ребрами.

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

Моделирование абстрактных и конкретных сущностей

Графы хорошо подходят для моделирования абстрактных отношений, как часть - отношения.

Например, штат Орегон является частью Соединенных Штатов, и  провинция Квебек является частью Канады.Город Портленд находится в штате Орегон, и город Монреаль расположен в Квебеке. Такого рода иерархические отношения моделируется с помощью специального типа графа, известное как дерево.

Дерево имеет специальную вершину которую называют корнем. Корень является вершиной иерархии. На рисунке 12.4 показано два дерева, один для Соединенных Штатов и один для Канады. Оба показывают взаимосвязь между национальными, региональными и местными государственными органами.

Рисунок 12.4 Иерархические государственные структуры, смоделированные в виде графов.

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

Деревья также используют для моделирования иерархических отношений, для организационных схем,как часть - отношения, например на частях автомобиля, как показано на рисунке 12.5.

Рисунок 12.5 Часть-отношения, для частей автомобиля, смоделированы с помощью графа.

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

Моделирование социальных медиа

Сайты социальных сетей, как Facebook и LinkedIn позволяют пользователям взаимодействовать и общаться друг с другом в Интернете. Они расширили способ общения людей, вводя новые способы взаимодействия, такие как кнопка "Нравиться". Это позволяет быстро и легко показать что вам нравится или оценить чужую запись.

Социальный медиа "Нравиться" может быть смоделирована в качестве связующего звена между человеком и записью. Вершинами в этом случае будут люди и посты. Стоит отметить, не все вершины и ребра должны быть одного и того же типа; может быть сочетание различных типов в одном графе.

Рисунок 12.6 Показывает пример графа людям-нрявяться-записи . Вы заметите,что  в отличие от многих других графов, у этого есть специальное свойство. Ребра движуться только от людей к записям; где нет ребер между людьми и между записями. Этот особый тип графа, называемый как двудольный граф, используют для моделирования отношений между различными типами сущностей.

Рисунок 12.6 Записи из социальных медия и “Нравиться” смоделированые с помощью графа.

Как показывают эти примеры, графы способны моделировать широкий спектр сущностей и отношений. Очевидный вопрос, скорее всего приходит вам на ум: Какие хорошие примеры использования для графовых БД?

Преимущества Графовых Баз Данных

Графовые БД показывают явные отношения между субъектами. Вершины представляют собой объекты, связаны или соединены ребрами. В реляционных базах данных, соединения не представлены в виде ссылок. Вместо этого две сущности имеют общее значение атрибута, который выступает в качестве ключа.

Быстрые запросы с помощью избеганий объединений

Чтобы найти соединения или ссылки в реляционной базе данных, необходимо выполнить операцию которая называется обьединением. Объединение смотрит и выбирает вверхние значения из одной таблицы в другой таблице. Например, на рисунке 12.7, таблица студентов содержит список имен стундентов и  их идентификаторов. Индификаторы студентов также используються в таблице Заявок, чтобы указать,на каком курсе обучается студент.

Рисунок 12.7 Представление отношения студент - курсы в реляционной базе данных.

В другом варианте, вы можете представлять отношения между студентом, используя графы, как показано на рисунке 12.8.Ребра между студентами и курсами предостовляют пользователю быстрые запросы ко всем курсам включая студентов записанных в них.

Рисунок 12.8 представление отношения студент - курс в виде графовой БД.

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

Рисунок 12.9 Нахождение Нолевого пациента при исследовании инфекционных заболеваний.

Во время эпидемии, это помогает понять кто являеться источником эпидемии или первого человека, зараженног этой болезнью. Предположим, что вы знаете, что Пациент А был заражен пациентом B, и пациент B был заражен пациентом C, и так далее. Если вам нужно будет начать с Пациента А, требуеться выполнить объединение, чтобы найти что он был заражен Пациентом Б. Затем вам нужно будет сделать запрос к таблице, чтобы выяснить что Пациент С имеет ли

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

Совет

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

Игры с графами

Графы даже пробрались в сферу популярных развлечений. Возьмите например настольную игру Pandemic от Z-Man Games. В Pandemic, игроки выполняют совместную работу что бы подавить и уничтожить четыре различных инфекционных заболевания, представленных цветными пластиковыми блоками.Игровое поле отображает многочисленные крупные города по всему миру, и каждый город имеет от двух до шести линий, соединяющих его с другим городом. Каждая линия представляет собой путь для передачи данного заболевания.В ходе игры, игроки используют уникальные полномочия, возложенные на них в начале игры, удалить цветные блоки с доски.

Как вы можете видеть,гемплей Pandemic происходит внутри графовой модели. Города выступают в роли вершин, в то время как линии служат в качестве ребер. Можно также приписать некоторые свойства для вершин и ребер. Например, каждый город имеет определенное количество линий, соединяющих его с другими городами, а также статус инфекции, представленный количеством цветных блоков в городе. В этом случае свойства ребер являются более абстрактными. Они содержат себе или не содержат линии соединяющие два инфицированных города, два не инфицированих города, или один инфицированый и один не инфицированный

Упрощенное Моделирование

Работа с графовыми БД может упростить процесс моделирования.При работе с реляционными базами данных, обычно начинают моделировать основные объекты в вашей области. В случае социальных медиа, это могут быть люди и записи. В случае инфекционных заболеваний, основным объектом являються всего лишь люди. Когда вы начинаете моделировать информацию о взаимодействии, это может быть сложным. Например, в области социальных медиа, многим людях может, нравиться запись так и запись может нравиться многим людям.

Это называеться отношение многие ко многим, которое смоделируеться как другая таблица, как показано на рисунке 12.10.

Рисунок 12.10 Моделирование отношения многие ко многим в реляционной базе данных.

В графовой БД, нет необходимости создавать таблицы для моделирования отношения многие-ко-многим; вместо этого, они подробно смоделированы с помощью ребер.

Множественые отношения между сущностями

Использование нескольких типов ребер позволяет разработчикам базы данных легко моделировать различные отношения между объектами. Это особенно полезно при моделировании вариантов транспортировки между объектами.Например, транспортная компания,которая возможно захочет, рассмотреть автомобильные, железнодорожные и воздушные перевозки между городами (смтр. рисунок 12.11). Каждый из них имеет различные свойства, такие как время доставки, стоимости и государственные регулирования.

Рисунок 12.11 Моделирование множестенных типов отношений в графовой БД.

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

Выводы

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