Представление графика с использованием реляционной базы данных
Мне нужно представить информацию о графе с реляционной базой данных.
Предположим, что a связано с b, c и d.
a -- b
|_ c
|_ d
Я могу иметь таблицу node для a, b, c и d, и я также могу иметь таблицу ссылок (FROM, TO) → (a, b), (a, c), (a, д).
Для другой реализации может быть способ сохранить информацию о ссылке как (a, b, c, d), но количество элементов в таблице является переменной.
- Q1: Есть ли способ представления переменных элементов в таблице?
- Q2: Есть ли общий способ представления структуры графа с использованием реляционной базы данных?
Ответы
Ответ 1
Q1: Есть ли способ представления переменных в таблице [database]?
Я предполагаю, что вы имеете в виду что-то вроде этого?
from | to_1 | to_2 | to_3 | to_4 | to_5 | etc...
1 | 2 | 3 | 4 | NULL | NULL | etc...
Это не очень хорошая идея. Он нарушает первую нормальную форму.
Q2: Есть ли какой-либо общий способ представления структуры графа с использованием базы данных?
Для ориентированного графа вы можете использовать таблицу edges
с двумя столбцами:
nodeid_from nodeid_to
1 2
1 3
1 4
Если какая-либо дополнительная информация о каждом node (например, имя node), это может быть сохранено в другой таблице nodes
.
Если ваш график неориентирован, у вас есть два варианта:
- сохраните оба направления (т.е. сохраните 1- > 2 и 2- > 1)
- используйте ограничение, которое
nodeid_from
должно быть меньше nodeid_to
(т.е. сохраняйте 1- > 2, но подразумевается 2- > 1).
Первый требует в два раза больше места для хранения, но может упростить и ускорить запрос.
Ответ 2
В дополнение к двум таблицам, указанным Марком, посмотрите следующую ссылку:
http://articles.sitepoint.com/article/hierarchical-data-database/2
Эта статья в основном предопределяет элементы в дереве, назначая левое и правое значения. Затем вы можете выбрать части или все дерево с помощью одного оператора select.
Node | lft | rght
-----------------
A | 0 | 7
B | 1 | 2
C | 3 | 4
D | 5 | 6
EDIT: если вы собираетесь интенсивно обновлять дерево, это не оптимальное решение, так как все дерево должно быть пронумеровано
Ответ 3
Я сохранил несколько узлов "TO" в реляционном представлении структуры графа. Я смог сделать это, потому что мой график был направлен. Это означало, что если бы я хотел знать, к каким узлам "A" подключен, мне нужно было выбрать только одну запись из моей таблицы соединений. Я сохранил узлы TO в строке для простого анализа, и он отлично справился с классом, который мог бы управлять преобразованием из строки в коллекцию и обратно.
Ответ 4
Я рекомендую посмотреть на специализированные базы данных графов, как предлагает nawroth. Одним из примеров может служить база данных "Тринити", предназначенная для очень больших наборов данных. Но есть и другие.
Прослушайте подкаст Скотта Гензельмана в Hanselminutes о Троице. Вот текстовая стенограмма .