Подтвердить что ты не робот

Представление графика с использованием реляционной базы данных

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

Предположим, что 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: Есть ли общий способ представления структуры графа с использованием реляционной базы данных?
4b9b3361

ОТВЕТЫ

Ответ 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 о Троице. Вот текстовая стенограмма .