Большинство из нас знают, что в последнее время наряду с привычными реляционными базами данных набирают обороты так называемые Document-oriented, key-value и иерархические базы. А я в последнее время заинтересовался другой разновидностью хранилищ - граф ориентированными базами данных.Что такое граф, я думаю все знают, а вот зачем для них понадобились свои собственные базы данных? Дело всё в том, что для структуры данных типа граф, набор действий зачастую несколько отличается от привычных нам вставок, обновлений и выборок по заданным условиям. Чего только стоят поиск в ширину и глубину. В принципе на небольших объемах данных традиционные способы представления себя оправдывают, но если предположить, что ваш граф начинает расти и в нём становится несколько миллионов вершин и десятки миллионов связей - реляционные базы данных загибаются под попытками провернуть нужное кол-во join-ов дабы удовлетворить многим условиям выборки при прохождении графа в случае поиска.
Что представляет собой граф ориентированная БД - это хранилище, которое использует некоторые априорные знания о графах, для формирования своей внутренней структуры. В таких базах поиск по критерию зачастую происходит не самым эффективных способом, а вот вычитка связей вершины, и вершин связей сильно оптимизирована. Таким образом обход графа (traversing) становиться операцией, которая в несколько раз быстрее аналогичной родственной реализации в реляционных БД.
Для ознакомления можно взглянуть на:
Posts
Недавно видел элегантный способ для Оракла по подсчёту самого короткого расстояния по графу. :)
ReplyDeleteпо памяти схематично суть:
begin
for i in (
select connect_by_path(lenght,'+') value
from table
connect by prior dist_begin = dist_end
start with start dist_begin = 'A'
) loop
execute immediate 'тут диначиеским SQL вызывает сгенерённый value и сравниваем с min значением';
end loop;
красиво, ИМХО )
Да, красиво, но на больших графах достаточно медленно.
ReplyDeleteДля постгреса реализация тоже есть: http://pgrouting.postlbs.org/wiki/Dijkstra
А большие графы для Dijkstra - это сколько вершин/ребер? TSP тоже используете? :)
ReplyDeleteСтатистика по вершинам, ребрам: http://www.openstreetmap.org/stats/data_stats.html
ReplyDeleteРешением TSP практически не занимались, ибо нужды были направлены в другое русло. Для небольшого класса специфичеких задач, таки реализовали решение, но объёмы расчетного подграфа были сильно лимитированы относительно кол=ва суммарного кол-ва ребер/вершин в графе.