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

Question

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

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

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

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

Answer 1

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

Взгляните на neo4j . Он реализован на Java, а также имеет привязки Python и Ruby.

Я написал две вики-страницы с простыми примерами моделей предметных областей, представленных в виде графиков, используя neo4j: сборка и роли Дополнительные примеры можно найти на странице Галерея моделирования домена .

Answer 2

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

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)

DECLARE @intN INT
SET @intN = 1

INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- Insert first item in list with no up stream items...call this initial condition
  SELECT LastNode, CurrentNode, @intN
  FROM your table
  WHERE node has nothing upstream

WHILE @intN <= 3500
BEGIN
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode, CurrentNode, @intN
      FROM your table
      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)</p>

IF @@ROWCOUNT = 0
     BREAK

END

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

SELECT LastNode, CurrentNode, N ОТ TempTable ЗАКАЗАТЬ НА N

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

Answer 3

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

Это тебе помогает?

Answer 4

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

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

Answer 5

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

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

vertex1 vertex2 {edge_label1}+

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

vertex1 vertex2
vertex2 vertex1

Answer 6

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

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

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

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