Привет всем!

Делаю веб-проектик для себя на связке PHP+Mysql. В основе - динамический граф. Необходимо искать всевозможные пути и кратчайшее расстояние между двумя узлами. Смущает то, что для поиска приходится постоянно доставать из бд целиком весь граф (и алгоритмом Дейкстры искать). Со скоростью выборки графа пока проблем нет, потому как граф с малым количеством узлов .

По ходу разработки возникают вопросы:

1. Оптимально ли вообще на стороне клиента (языка программирования) работать с графом у которого большое количество узлов (например миллион) или лучше делать весь поиск на уровне хранимых функций/процедур СУБД?

2. Существуют ли более эффективные/оптимальные средства/подходы для работы с графами? (сайтец на начальном этапе разработки, поэтому могу экспериментировать)


Уважаемы специалисты, помогите, пожалуйста, разобраться.

p/s: По совету на хpoint, читаю "Кристофидес Н. Теория графов. Алгоритмический подход." Хотелось бы услышать еще мнения, по этому поводу.

ОКТОГЕН,
Спасибо, что ответили.

Выбирал между несколькими вариантами хранения древовидных структур:

Adjacency List Tree Structure
Nested Set Tree Structure
Materialized Path Tree


Остановился, на таком простеньком варианте:

Табличка объектов(вершин) Objects
idname1 Узел 12 Узел 23 Узел 3

И табличка связей между вершинами - Relations
parent child1 21 3

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

Как я понял реляционные бд, не совсем удобны для работы со сложными графами.
А в какую сторону тогда смотреть? Просто в сети мало информации, по работе с графами.

Мимопроходящий
fedd, привет!

--
With best regards, Мимопроходящий.




Привет!!! Тока я не fedd :)

Senya_LDaffyПока весь граф выбираю итеративно, но в последствии хочу добавиться табличку RelationsMap, хранящую все пути между любыми связанными узлами ( карта путей узлов), для того чтобы весь граф можно было "выбрать" одним запросом. Плохо только то, что избыточность будет большая.Что-то мне непонятно назначение RelationsMap. Граф можно и так выбрать двумя запросами
Другое дело, что может погибнуть клиент, расставляя дуги между лимоном вершин. Хотя если использовать нормальные коллекции с быстрым поиском, то все будет нормально.

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

Senya_L,

авторХотя если использовать нормальные коллекции с быстрым поиском, то все будет нормально.

Поясните, пожалуйста, насчет коллекций. Пока не понимаю о чем идет речь.

Так как идея на стадии разработки, могу к Mysql не привязываться, а использовать другие средства/подходы.

DPH3Если граф большой, а работать с ним нужно быстро, то СУБД, скорее всего, не подойдет, увы.

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

Если же хочется логику оставить в БД, то стоит поглядеть на бесплатные БД с хорошим SQLем (ну, я традиционно рекомендую DB2 Express C, там с деревьями все хорошо, но может быть подойдет и что-нибудь еще).

Вообще, про то, как работать с большими графами был доклад на последнем Highload++ - включая распределение графа на несколько серверов и т.п.

Спасибо большое за наводку - буду копать!

DPH3,
автор
Если же хочется логику оставить в БД, то стоит поглядеть на бесплатные БД с хорошим SQLем (ну, я традиционно рекомендую DB2 Express C, там с деревьями все хорошо, но может быть подойдет и что-нибудь еще).


У меня вся основная работа происходить будет с графом, а в перспективе он может расти, да и функционал по работе с графом - расширяться. Как раз скорость работы очень важна. И если, действительно, СУБД не подходят под эту "планку", то откажусь от них.
А DB2 Express C обязательно, для общего развития - гляну. Спасибо!

DPH3,

Собственно весь проект делается мной ради "спортивного" интереса (стартап). Это будет портал с элементами социальной сети. За 2 года, надеюсь, наберется аудитории 1000 - 1500 человек. Точное количество запросов, затрудняюсь сказать, потому как не знаю насколько активно будут юзать сайт. Высокая скоростью работы важна (особенно если проект будет пользоваться интересом), приятно когда интерфейс реагирует на действия пользователя максимально быстро. Так как основная идея завязана на графе (поиск, добавление вершин, удаление вершин, объедение подграфов, выборка, модификация элементов графа), хочется подобрать средства/методы для этой задачи, чтобы в последствии можно было максимально безболезненно масштабировать систему и т.д.

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

Подскажите пожалуйста, что такое ApplicationLayer ??? В сети нахожу разные трактовки.

DPH3,

авторВообще, про то, как работать с большими графами был доклад на последнем Highload++ - включая распределение графа на несколько серверов и т.п.

http://highload.ru/papers2009/12480.html

Вот об этом докладе идет речь?

DPH3, strizh . Спасибо большое!

В памяти работать с графом, действительно шустро. Только в этом убедился поюзав key-value хранилище Redis. Саму работу с графом - перенесу на СИ. И этого функционала с головой хватит.
Ставлю сейчас Ubuntu Linux , чтобы для разнообразия потестить: Tokyo Cabine/Tokyo Tyrant, BerkeleyDB/MemcacheDB, MongoDB. Единственное, немного смущает, что проекты 'свежие' и первые версии падали(речь о MongoDB и Redis) . Собственно к хранилищам присмотрелся из-за "легкости" горизонтальной масштабируемости, да еще благодаря отсутствию SQL (парсить ничего не нужно) скорость выборок в разы выше того же Mysql.Так как проект тестовый и не коммерческий, интересно обкатать новые технологии.

Возможно кто-то уже пользовался перечисленными хранилищами поделитесь, пожалуйста, насколько стабильно они себя ведут при больших объемах инфы в бд ???

Alexander Ryndin , Спасибо! Про Oracle Spatial даже не слышал. Погуглю о нем.