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

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

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

Давайте рассмотрим самый неблагоприятный для нас случай:

1. Связи должны иметь направленность (двусторонние или односторонние).
2. Всю информацию о связях мы должны хранить в базе данных.
3. И как вариант, в самом конце, рассмотрим высоконагруженную систему, для которой требуется разделение баз данных по разным серверам (шардирование).

Но прежде, чем начать практическое воплощение, давайте освежим воспоминания по курсу математики.

Граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

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

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

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

В чем суть. Дана матрица, столбцы которой это ребра графа, а строки - вершины графа. Каждая ячейка отображает взаимоотношение между конкретной вершиной и ребром. Возьмем для примера ячейку (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, а такие записи могут быть в разных базах.

Для решения этого конфликта я предлагаю такую простую схему:

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

Перенос информации о направленности связей в одну запись позволит получив всего лишь одну запись сказать, есть ли связь между вершинами и какой она направленности.

А две зеркальные записи позволят нам формировать все поисковые запросы только полю object1. Соответственно разрешается проблема разноса информации по разным базам данных.

• key - первичный ключ.
• object1 - идентификатор первой вершины.
• object2 - идентификатор второй вершины.
• link1 - признак связи от первой вершины ко второй.
• link2 - признак связи от второй вершины к первой.

Запрос на внесение связи от вершины node1 к вершине node2:

SQL:
 
INSERT INTO `links` SET `object1` = 'node1', `object2` = 'node2', `link1` = 1, `link2` = 0;
INSERT INTO `links` SET `object1` = 'node2', `object2` = 'node1', `link1` = 0, `link2` = 1;

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

Запрос для определения всех связей вершины node1:

SQL:
 
SELECT `object2`, `link1`, `link2`
FROM `links`
WHERE `object1` = 'node1';

Каждая полученная запись будет нести следующую информацию:

link1 = 1 - есть связь от вершины node1 к вершине object2
link2 = 1 - есть связь от вершины object2 к вершине node1