Почему графовые базы данных быстрее, чем RDB для обходов графов? - PullRequest
Новая
       5

Почему графовые базы данных быстрее, чем RDB для обходов графов?

1 голос
/ 13 февраля 2020


Я прочитал несколько статей (например, this ), в которых говорится, что DB графов по своей природе быстрее, чем RDB, при запуске алгоритмов обхода графов из-за смежности без индекса. Однако у меня возникают проблемы с пониманием теоретического обоснования этого. Мне кажется, что если вы создаете таблицы смежности с индексом ha sh, вы должны достичь такой же производительности по сложности.

Например, найти друзей человека (с помощью идентификатора человека) с помощью RDB с двумя таблицами: люди и дружба

1) Расположение друзей: O (m) - где m - количество друзей.
2) Для каждого идентификатора друга, находящегося в людях: O (1)
Итого: O (м)

В графе БД это должно быть то же самое, нет?

1 Ответ

1 голос
/ 20 февраля 2020

Нет, запросы выполняются в СУБД иначе, чем в графической базе данных.

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

    Однако, если вы хотите выполнить запрос n-прыжка (n> 3), в СУБД вы можете использовать подзапрос или объединение, и производительность будет зависеть от вашего оптимизатора.

    Ниже приведен пример:

    Предположим, что у нас есть класс таблиц с полями id (ПЕРВИЧНЫЙ КЛЮЧ) и name, студент с полями id (ПЕРВИЧНЫЙ КЛЮЧ), name и class_id.

Чтобы найти имя класса с идентификатором 2 и соответствующих учащихся, нам нужно объединить две таблицы класса таблицы и ученика 

SELECT c.name as c_name, s.name as s_name 
  FROM class as c 
    LEFT JOIN student as s 
      ON c.id = s.class_id 
        WHERE c.id = 2;

Объяснить запрос: Запрос объяснен в таблице

Вся таблица ученика будет отсканирована, чтобы найти class_id = 2.

Конечно, мы можем создать индекс для ученика class_id столбец.

таблица индекса

Он читает индекс student_class, чтобы получить указатели на физические строки, а затем считывает записи, как они есть. некластерный индекс.

В базе данных графа данные моделируются как узлы и соединения.

модель базы данных графа

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

Если вы хотите найти кратчайший путь и все возможные пути между двумя точками (но вы не знаете, сколько прыжков есть для запроса), тогда будет много проблем с использованием RDBMS. Запрос будет довольно длинным. LDB C имеет несколько хороших примеров использования SQL, GQL (Cypher) и SparQL соответственно. К сожалению, я не нашел различий во времени выполнения между разными языками.

С помощью RDBMS сложно выполнять вычисления на графах, такие как LPA (алгоритм распространения меток) и алгоритм Page Rank. Но было бы намного проще сделать это в некоторых (большинстве) графических СУБД

...