그래프 데이터 구조를 관계형 데이터베이스에 매핑하는 것이 합리적입니까?

Question

특히 Multigraph입니다.

일부 동료가 제안했으며 완전히 당혹 스럽습니다.

이것에 대한 통찰력이 있으십니까?

Answer 1

그래프를 데이터베이스에 저장하는 것은 매우 간단합니다. 노드 테이블과 가장자리 테이블은 노드 테이블과 자체 간의 다 대다 관계 테이블로 작동합니다. 이와 같이 :

create table node (
    id integer primary key 
); 

create table edge (
    start_id integer references node, 
    end_id integer references node, 
    primary key (start_id, end_id) 
); 

그러나 그래프를 이런 방식으로 저장하는 데는 몇 가지 점이 있습니다.

먼저이 구성표의 가장자리는 자연스럽게 지시됩니다. 시작과 끝은 별개입니다. 가장자리가 방향이 지정되지 않은 경우 쿼리를 작성할 때주의해야하며 각 가장자리에 대해 테이블에 두 개의 항목을 저장해야합니다. 한 방향으로 하나씩 (그리고 쿼리 작성에주의하십시오!). 단일 모서리를 저장하는 경우 저장된 양식을 정규화 할 것을 제안합니다. 가장 낮은 ID를 가진 노드를 항상 시작으로 간주하고이를 적용하기 위해 CHECK 제약 조건을 테이블에 추가하십시오. 가장자리를 노드를 참조하지 않고 진정한 순서가 아닌 표현을 가질 수 있지만 그 사이에 조인 표가 있지만 이는 나에게 좋은 생각이 아닙니다.

둘째, 위의 스키마는 멀티 그래픽을 표현할 방법이 없습니다.그렇게 쉽게 확장 할 수 있습니다. 주어진 노드 쌍 사이의 가장자리가 구별 할 수없는 경우, 가장 간단한 것은 각 참조 행에 수를 추가하여 참조 된 노드 사이에 몇 개의 가장자리가 있는지를 말합니다. 이들이 구별 가능하다면 노드 테이블에 노드 테이블을 추가하여 노드 테이블을 구분할 수 있어야합니다. 자동 생성 된 에지 ID가 가장 간단한 방법 일 수 있습니다.

그러나 저장소를 정렬 했더라도 그래프 작업에 문제가 있습니다. 메모리에있는 객체에 대한 모든 처리를 수행하려는 경우 데이터베이스가 순전히 저장 영역 용이므로 아무런 문제가 없습니다. 그러나 데이터베이스의 그래프에 대해 쿼리를 수행하려는 경우 SQL에서 수행하는 방법을 파악해야합니다. SQL은 그래프에 대한 지원이 없으며 기본 작업을 쉽게 적용 할 수 없습니다. 그래프 작업. 재귀 적 SQL 지원 (PostgreSQL, Firebird, 독점 데이터베이스 중 일부)을 갖춘 데이터베이스가있는 경우 특히 그렇습니다. 이 작업을 원할 경우 제 제안은 특정 쿼리에 대한 추가 질문을 게시하는 것입니다.

Answer 2

정보는 어딘가에 저장해야하며, 관계형 데이터베이스는 나쁜 생각이 아닙니다.

이것은 단지 다 대다 관계, 노드 목록 테이블 및 가장자리/연결 목록 테이블 일뿐입니다.

Answer 3

Facebook이 소셜 그래프를 데이터베이스에 구현하는 방법을 고려하십시오. 그들은 사람들을위한 테이블과 우정을위한 테이블을 가질 수 있습니다. Friendships 테이블에는 적어도 두 개의 열이 있으며, 각각은 테이블의 외부 키입니다.

우정은 (Facebook에서) 대칭이므로 첫 번째 외래 키의 ID가 항상 두 번째 외래 키의 ID보다 작을 수 있습니다. 트위터는 소셜 네트워크를위한 유향 그래프를 가지고 있으므로 이와 같은 정식 표현을 사용하지 않을 것입니다.

Answer 4

허용되는 접근 방식입니다. 그 정보가 어떻게 조작 될지 고려해야합니다. 이 유형의 데이터가 의미하는 종류 그래프 관련 계산을 수행하려면 데이터베이스와 별도의 언어가 필요할 것입니다. Skiena's Algorithm Design Manual에는 광범위한 단면 그래프 데이터 구조와 그 조작이 있습니다.

실행할 쿼리 유형을 고려하지 않고 두 테이블 vertices 및 edges으로 시작하십시오. 정점은 간단하고 식별자와 이름입니다. multigraph가 주어진다면 모서리는 복잡합니다. 모서리는 두 개의 정점 (즉, 외래 키)과 몇 가지 추가 정보의 조합으로 고유하게 식별되어야합니다. 추가 정보는 현재 해결중인 문제에 따라 다릅니다. 예를 들어, 항공편 정보, 출발 및 도착 시간 및 항공사. 또한 엣지가 방향 지어져 있는지 (일방 통행) 여부를 결정하고 그 정보도 추적해야합니다.

계산에 따라 어떤 종류의 인공 지능/기계 학습 알고리즘으로 더 잘 해결할 수있는 문제가 발생할 수 있습니다. 예를 들어, 최적의 비행. 책 Programming Collective Intelligence에는이 목적을위한 몇 가지 유용한 알고리즘이 있습니다. 그러나 데이터가 보관되는 곳에서는 알고리즘 자체가 변경되지 않습니다.