Есть граф (10^8 вершин), нужно хранить его в БД, так чтобы можно было достаточно эффективно по нему выполнять его обход, например поиск в ширину с ограничением по глубине. Плюс ежедневно нужно его актуализировать, примерно 10^7 вершин меняют свои атрибуты.
Возможно есть какие то типовые варианты решения подобных задач? Есть ли эффективные решения на базе реляционных СУБД? Почему то кажется, что стандартный подход для графа, хранить в виде двух таблиц вершины+ребра будет слишком медленно. Пока видится какой нибудь NoSQL вариант и каждая вершина хранит ссылки на соседние.

Dimitry Sibiryakovjust_vladimirВозможно есть какие то типовые варианты решения подобных задач? Есть ли эффективные
решения на базе реляционных СУБД?

Oracle + таблица рёбер + connect by = решение.

А как изнутри это работает? Все равно ведь будут join'ы? Надо по экспериментировать, но что то сомневаюсь в производительности (

Нет, надо именно в ширину, а по глубине ограничивать только интересующую область поиска, чтобы не перебирать весь граф. Граф с циклами.
ЗЫ: попробовал выполнить самый обычный join на таблице подобного размера, результатов работы не дождался...

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

Да, нужно именно это, определенный тип запросов к статичной таблице, актуализация происходит в отдельное время от этих запросов, во время актуализации можно выполнять пред подготовку данных. Мне эта пред подготовка видится в хранении сразу вместе с вершиной ребер относящихся к этой вершине, но их количество ведь не постоянно. На сколько накладно хранить их в чем то CLOB'о подобном?

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

RXLКакие критерии требуют такого?
Чем классика не подходит? Попробуйте обосновать.
Вы о чём вообще? Критерий - производительность. Если при работе с графом всегда нужна информация о соседях вершины, то зачем для этого каждый раз выполнять запрос, когда можно хранить эти данные вместе с самой вершиной? Согласен, что будет дублирование информации, но как тут заметили стоимость дискового пространства в наше время не так уж и высока.


MasterZivЭто получается 100 миллионов вершин ?
А что за задача ? У нас БОЛЬШЕ графы хранятся,
по несколько десятков миллиардов вершин, и ничего.
Да, 100 млн вершин. Подумал на тему, какие могут быть графы и их размеры, вот что получилось:
10^3 - Количество городов в России
10^6 - Количество записей в ЕГРЮЛ
10^8 - Население РФ, Количество пользователей vk.ru
10^9 - Количество пользователей fb, Количество платежей совершаемых в России за год
10^11 - Количество нейронов в мозгу человека.

Что-то Ваша цифра в 10^10 кажется весьма высокой...

Dimitry SibiryakovЗатем, что результаты запроса можно обработать в ХП, а парсить клоб - недешёвое удовольствие.

По этому сейчас я экспериментирую с MongoDB.