유향 그래프를 저장/액세스하는 가장 좋은 방법 (Best Way to Store/Access a Directed Graph)

문제 설명

유향 그래프를 저장/액세스하는 가장 좋은 방법 (Best Way to Store/Access a Directed Graph)

나는 흐름 경로(기본적으로 방향성 그래프)를 결정하기 위해 네트워크로 표현하고 싶은 약 3500개의 홍수 조절 시설을 가지고 있습니다. 저는 현재 SqlServer와 CTE를 사용하여 모든 노드와 해당 업스트림 구성 요소를 재귀적으로 검사하고 있으며 업스트림 경로가 많이 분기되지 않는 한 작동합니다. 그러나 일부 쿼리는 추가된 업스트림 복잡성으로 인해 물리적으로 경로 아래(즉, 두 개 또는 세 개의 세그먼트 "다운스트림")가 훨씬 더 멀지 않은 경우에도 다른 쿼리보다 기하급수적으로 더 오래 걸립니다. 어떤 경우에는 쿼리를 종료하기 전에 10분 이상 그대로 두었습니다. 저는 단순한 2열 테이블을 사용하고 있습니다. 한 열은 시설 자체이고 다른 하나는 첫 번째 열에 나열된 것의 업스트림에 있는 시설입니다.

속도를 높이는 데 도움이 되도록 현재 기능을 사용하여 색인을 추가하려고 시도했지만 아무런 차이가 없었습니다. 그리고 그래프에서 가능한 연결에 관해서는 모든 노드가 여러 개의 업스트림 연결을 가질 수 있고 여러 "다운스트림" 노드에서 연결할 수 있습니다.

데이터에 주기가 있을 수 있지만 저는 (CTE 쿼리가 최대 재귀 카운트 적중을 보고한 경우를 제외하고는 이를 확인할 수 있는 좋은 방법을 아직 찾지 못했습니다. 수정하기 쉬웠습니다.)

그래서 제 질문은 이 정보를 저장하고 있습니까? 잘못된? CTE 외에 업스트림 포인트를 쿼리하는 더 좋은 방법이 있습니까?

데이터에 주기가 있을 수 있지만 아직 이를 확인할 수 있는 좋은 방법을 찾지 못했습니다. (CTE 쿼리가 최대 재귀 카운트 적중을 보고했을 때를 제외하고는 수정하기 쉬웠습니다.)

그래서 내 질문은 이 정보를 잘못 저장하고 있는 것입니까? CTE 외에 업스트림 포인트를 쿼리하는 더 좋은 방법이 있습니까?

데이터에 주기가 있을 수 있지만 아직 이를 확인할 수 있는 좋은 방법을 찾지 못했습니다. (CTE 쿼리가 최대 재귀 카운트 적중을 보고했을 때를 제외하고는 수정하기 쉬웠습니다.)

그래서 내 질문은 이 정보를 잘못 저장하고 있는 것입니까? CTE 외에 업스트림 포인트를 쿼리하는 더 좋은 방법이 있습니까?

참조 솔루션

방법 1:

The best way to store graphs is of course to use a native graph db :‑)

Take a look at neo4j. It's implemented in Java and has Python and Ruby bindings as well.

I wrote up two wiki pages with simple examples of domain models represented as graphs using neo4j: assembly and roles. More examples are found on the domain modeling gallery page.

방법 2:

I know nothing about flood control facilities. But I would take the first facility. And use a temp table and a while loop to generate the path.

‑‑ 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)
IF @@ROWCOUNT = 0
     BREAK
END

If we assume that every node points to one child. Then this should take no longer than 3500 iterations. If multiple nodes have the same upstream provider then it will take less. But more importantly, this lets you do this...

SELECT LastNode, CurrentNode, N FROM TempTable ORDER BY N

And that will let you see if there are any loops or any other issues with your provider. Incidentally 3500 rows is not that much so even in the worst case of each provider pointing to a different upstream provider, this should not take that long.

방법 3:

Traditionally graphs are either represented by a matrix or a vector. The matrix takes more space, but is easier to process(3500x3500 entries in your case); the vector takes less space(3500 entries, each have a list of who they connect to).

Does that help you?

방법 4:

i think your data structure is fine (for SQL Server) but a CTE may not be the most efficient solution for your queries. You might try making a stored procedure that traverses the graph using a temp table as a queue instead, this should be more efficient.

the temp table can also be used to eliminate cycles in the graph, though there shouldn't be any

방법 5:

Yes (maybe). Your data set sounds relatively small, you could load the graph to memory as an adjacency matrix or adjacency list and query the graph directly ‑ assuming you program.

As far as on‑disk format, DOT is fairly portable/popular among others. It also seems pretty common to store a list of edges in a flat file format like:

vertex1 vertex2 {edge_label1}+

Where the first line of the file contains the number of vertices in the graph, and every line after that describes edges. Whether the edges are directed or undirected is up to the implementor. If you want explicit directed edges, then describe them using directed edges like:

vertex1 vertex2
vertex2 vertex1

(by Michael Todd、nawroth、Cervo、Paul Nathan、Steven A. Lowe、paxos1977)

참조 문서

1. Best Way to Store/Access a Directed Graph (CC BY‑SA 2.5/3.0/4.0)