Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
 Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
Привет всем!

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

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

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

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


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

p/s: По совету на хpoint, читаю "Кристофидес Н. Теория графов. Алгоритмический подход." Хотелось бы услышать еще мнения, по этому поводу.
25 окт 09, 00:16    [7834805]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Мимопроходящий
Member

Откуда: бурятский тундрюк, эсквайр
Сообщений: 32898

fedd, привет!

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

Posted via ActualForum NNTP Server 1.4

26 окт 09, 20:12    [7841031]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
ОКТОГЕН
Member

Откуда:
Сообщений: 2498
Daffy, Вряд ли можно получить высокую скорость за счёт использования ХП, особенно, на
задачах типа полного обхода графа. Да и процедурный язык у мускуля весьма убогий.
На миллионе узлов, мне кажется мускуль умрёт или будет очень долго работать.
Но если вас не смущает ожидание в течении нескольких минут в случае больших графов,
то я думаю, можете попробовать.
Ещё зависит от способа хранения. Как вы храните этот граф?
29 окт 09, 13:07    [7855475]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
ОКТОГЕН,
Спасибо, что ответили.

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

Adjacency List Tree Structure
Nested Set Tree Structure
Materialized Path Tree


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

Табличка объектов(вершин) Objects
idname
1 Узел 1
2 Узел 2
3 Узел 3


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


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

Как я понял реляционные бд, не совсем удобны для работы со сложными графами.
А в какую сторону тогда смотреть? Просто в сети мало информации, по работе с графами.
29 окт 09, 22:01    [7859215]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
Мимопроходящий

fedd, привет!

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




Привет!!! Тока я не fedd :)
29 окт 09, 22:02    [7859219]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Senya_L
Member

Откуда: Москва
Сообщений: 5381
Daffy
Пока весь граф выбираю итеративно, но в последствии хочу добавиться табличку RelationsMap, хранящую все пути между любыми связанными узлами ( карта путей узлов), для того чтобы весь граф можно было "выбрать" одним запросом. Плохо только то, что избыточность будет большая.
Что-то мне непонятно назначение RelationsMap. Граф можно и так выбрать двумя запросами
select * from Objects
select * from Relations
Другое дело, что может погибнуть клиент, расставляя дуги между лимоном вершин. Хотя если использовать нормальные коллекции с быстрым поиском, то все будет нормально.
30 окт 09, 09:27    [7859872]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
alecsey
Member

Откуда: Москва
Сообщений: 830
ОКТОГЕН
Daffy, Вряд ли можно получить высокую скорость за счёт использования ХП
ога, тянуть милион строк на клиента это конечно очень быстро
30 окт 09, 13:11    [7861779]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
ОКТОГЕН
Member

Откуда:
Сообщений: 2498
alecsey, я хотел сказать, что перебирать миллионные графы занятие тоскливое по любому.
Экономия на трафике в ХП уменьшит сетевой трафик, но эта ХП будет тяжёлая.
30 окт 09, 14:40    [7862681]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
Senya_L
Daffy
Пока весь граф выбираю итеративно, но в последствии хочу добавиться табличку RelationsMap, хранящую все пути между любыми связанными узлами ( карта путей узлов), для того чтобы весь граф можно было "выбрать" одним запросом. Плохо только то, что избыточность будет большая.
Что-то мне непонятно назначение RelationsMap. Граф можно и так выбрать двумя запросами
select * from Objects
select * from Relations
Другое дело, что может погибнуть клиент, расставляя дуги между лимоном вершин. Хотя если использовать нормальные коллекции с быстрым поиском, то все будет нормально.


В том-то и дело, что дуги расставляю на уровне БД и на клиенте уже осуществляю поиск.
Mysql не поддерживает иерархические запросы, с помощью таблицы RelationsMap хочу попытаться компенсировать это.
30 окт 09, 19:01    [7864587]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
Senya_L,

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


Поясните, пожалуйста, насчет коллекций. Пока не понимаю о чем идет речь.
30 окт 09, 19:03    [7864593]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
Так как идея на стадии разработки, могу к Mysql не привязываться, а использовать другие средства/подходы.
30 окт 09, 19:08    [7864608]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
DPH3
Guest
Если граф большой, а работать с ним нужно быстро, то СУБД, скорее всего, не подойдет, увы.

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

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

Вообще, про то, как работать с большими графами был доклад на последнем Highload++ - включая распределение графа на несколько серверов и т.п.
30 окт 09, 21:02    [7864954]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

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

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

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

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


Спасибо большое за наводку - буду копать!
30 окт 09, 23:28    [7865518]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
DPH3,
автор

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


У меня вся основная работа происходить будет с графом, а в перспективе он может расти, да и функционал по работе с графом - расширяться. Как раз скорость работы очень важна. И если, действительно, СУБД не подходят под эту "планку", то откажусь от них.
А DB2 Express C обязательно, для общего развития - гляну. Спасибо!
30 окт 09, 23:43    [7865566]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
DPH3
Guest
Daffy

а в перспективе он может расти, да и функционал по работе с графом - расширяться. Как раз скорость работы очень важна.

А какие оценки требований к производительности и объему на ближайшие, ну, скажем, два года?
А то "скорость работы очень важна" может пониматься очень по разному

(Я видел ТЗ, где очень хотели высокую скоростью работы под большими нагрузками. После уточнения постановки выяснилось, что нужно порядка 100 пользователей (и запрос раз в минуту) при скорости реакции порядка 10 секунд. Для обычного корпоративного портала :)
31 окт 09, 14:54    [7866513]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
DPH3,

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

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


Подскажите пожалуйста, что такое ApplicationLayer ??? В сети нахожу разные трактовки.
31 окт 09, 20:57    [7866963]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
DPH3,

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


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

Вот об этом докладе идет речь?
31 окт 09, 22:32    [7867125]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
fedd
Member

Откуда: Москва
Сообщений: 33999
Daffy
Мимопроходящий

fedd, привет!

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




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

хотя топик интересный :)
3 ноя 09, 16:40    [7878057]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
Daffy
DPH3,
автор

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


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

ну почему же СУБД не подходят? ;) Все прекрасно подходит. Только смотреть нужно в сторону Oracle Spatial. Там тебе и все эти алгоритмы реализованы, и динамическая загрузка графов, и анализ прямо в базе...
6 ноя 09, 21:50    [7894829]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
DPH3
Guest
Daffy
DPH3,

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


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

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


Да.
Хотя при ваших объемах и задачах можно обойтись и более простыми решениями. Собственно, почти любыми (граф в простой БД, граф целиком в памяти, загружается при рестарте и т.д.). Проблемы начинаются, когда пользователей десятки-сотни тысяч и все приходят каждый день :)

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

Все остальное для ваших задач, насколько я могу судить, излишнее :)
6 ноя 09, 23:24    [7895129]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
strizh
Member

Откуда: Киев
Сообщений: 937
To Daffy
тынц
народ правильно советует - MySQL - фтопку.
7 ноя 09, 02:24    [7895793]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Daffy
Member

Откуда:
Сообщений: 12
DPH3, strizh . Спасибо большое!

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

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

Alexander Ryndin, Спасибо! Про Oracle Spatial даже не слышал. Погуглю о нем.
7 ноя 09, 19:21    [7896893]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
DocAl
Member

Откуда: Оккупирую западный берег
Сообщений: 10472
В MySQL, кстати, тоже есть Spatial Extension. На первый взгляд, может подойти, но сам не пользовался. Если попробуете -- сообщите о результатах, пожалуйста.
20 ноя 09, 14:23    [7956757]     Ответить | Цитировать Сообщить модератору
 Re: Динамический граф  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
DocAl,

в MySQL этой функциональности нет. ее также нет в MSSQL.
гуглить тоже не стоит - все то нужно есть вот здесь Oracle Network Data Model
20 ноя 09, 14:56    [7957024]     Ответить | Цитировать Сообщить модератору
Все форумы / Сравнение СУБД Ответить