Лучший способ сохранить/получить доступ к графику

У меня есть около 3500 объектов управления потоками, которые я хотел бы представлять как сеть для определения путей потока (по существу, ориентированного графика). В настоящее время я использую SqlServer и CTE для рекурсивного изучения всех узлов и их компонентов вверх, и это работает до тех пор, пока восходящий путь не поддерживает fork. Тем не менее, некоторые запросы экспоненциально больше, чем другие, даже если они не намного физически расположены по пути (т.е. Два или три сегмента "вниз по течению" ) из-за добавленной сложности восходящего потока; в некоторых случаях я пропустил это через десять минут, прежде чем убить запрос. Я использую простую таблицу с двумя столбцами, причем один столбец является самим объектом, а другой - средством, расположенным выше по потоку от указанного в первом столбце.

Я попытался добавить индекс, используя текущее средство, чтобы ускорить процесс, но это не имело никакого значения. И, что касается возможных соединений на графике, любые узлы могут иметь несколько восходящих соединений и могут быть связаны с несколькими "нисходящими" узлами.

Конечно, возможно, что в данных есть циклы, но я еще не понял хороший способ проверить это (кроме случаев, когда запрос CTE сообщил о максимальном рекурсивном счетчике, это было легко исправить).

Итак, мой вопрос: я неправильно храню эту информацию? Есть ли лучший способ, кроме CTE, запрашивать точки восходящего потока?

Ответ 1

Я ничего не знаю о средствах борьбы с наводнениями. Но я бы взял первый объект. И используйте временную таблицу и цикл while для генерации пути.

- Псевдокод
TempTable (LastNode, CurrentNode, N)

DECLARE @intN INT SET @intN = 1

INSERT INTO TempTable (LastNode, CurrentNode, N) - Вставить первый элемент в список без элементов потока вверх... вызвать это начальное условие SELECT LastNode, CurrentNode, @intN Из таблицы WHERE node не имеет ничего выше

WHILE @intN <= 3500 НАЧАТЬ SEt @intN = @intN + 1 INSERT INTO TempTable (LastNode, CurrentNode, N) SELECT LastNode, CurrentNode, @intN Из таблицы WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)

IF @@ROWCOUNT = 0
     BREAK

END

Если предположить, что каждый node указывает на одного ребенка. Тогда это займет не более 3500 итераций. Если несколько узлов имеют один и тот же провайдер, то это займет меньше. Но что более важно, это позволяет вам сделать это...

SELECT LastNode, CurrentNode, N FROM TempTable ORDER BY N

И это позволит вам увидеть, есть ли какие-либо петли или какие-либо другие проблемы с вашим провайдером. Кстати, 3500 строк не так уж и даже в худшем случае каждого провайдера, указывающего на другого провайдера восходящего потока, это не займет много времени.

Ответ 2

Лучший способ хранения графиков - это, конечно, использовать собственный граф db: -)

Посмотрите neo4j. Он реализован на Java и имеет привязки Python и Ruby.

Я написал две вики-страницы с простыми примерами моделей домена, представленных в виде графиков с помощью neo4j: assembly и roles. Дополнительные примеры можно найти на странице

Ответ 3

Традиционно графики либо представлены матрицей, либо вектором. Матрица занимает больше места, но ее легче обрабатывать (3500x3500 записей в вашем случае); вектор занимает меньше места (3500 записей, каждый из которых имеет список тех, с кем они подключаются).

Помогает ли вам это?

Ответ 4

Я думаю, что ваша структура данных в порядке (для SQL Server), но CTE может оказаться не самым эффективным решением для ваших запросов. Вы можете попытаться сделать хранимую процедуру, которая пересекает график, используя временную таблицу как очередь, это должно быть более эффективным.

временная таблица также может использоваться для исключения циклов в графике, хотя не должно быть никаких

Ответ 5

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

Что касается формата на диске, DOT довольно портативен/популярен среди других. Также представляется довольно обычным хранить список ребер в плоском формате файла, например:

vertex1 vertex2 {edge_label1}+

Если первая строка файла содержит количество вершин в графе, а каждая строка после этого описывает ребра. Являются ли ребра направленными или неориентированными, зависит от разработчика. Если вам нужны явные направленные ребра, то опишите их с помощью направленных ребер, например:

vertex1 vertex2
vertex2 vertex1

Ответ 6

Мой опыт хранения того, что вы описали в базе данных SQL Server:

Я хранил матрицу расстояний, рассказывая, сколько времени требуется для перемещения из точки А в точку В. Я сделал наивное представление и сохранил их непосредственно в таблице, называемой расстояниями с столбцами A, B, расстоянием, временем.

Это очень медленно при простом восстановлении. Я обнаружил, что намного лучше хранить всю мою матрицу в виде текста. Затем возвращайте его в память перед вычислениями, создайте матричную структуру в памяти и работайте с ней там.

Я мог бы предоставить некоторый код, но это будет С#.