그래프 집합에 대한 쿼리 언어 : 데이터 모델링 질문

Question

나는 방향성 그래프 집합이 있다고 가정합니다. 나는 그 그래프를 질의 할 필요가있다. 그래프 모델링 작업에 최선의 선택을하고 싶습니다. 지금까지 나는 이러한 옵션을 가지고 있지만, 다른 사람을 제안하는 것을 망설이지 말라 :

• 독점 구현 (매트릭스) 그래프 탐색 알고리즘을.

너희들은 무엇을 제안

RDBM와 (너무 느린) SQL 옵션 (너무 공간이 소모)

RDF와 SPARQL 옵션? 문안 인사.

편집 : 그냥 미친의 질문에 대답 :

• 각각은, 상대적으로 작은 이하 200 개 정점, 400 가장자리. 그러나 수백 가지가 있습니다.

• 쿼리 빈도 : 실험 시스템입니다.

• 속도 : 실시간이 아니지만 실용적이며 4-5 초 길이라고 말합니다.

Answer 1

잘 생각한 대답으로 응답하기에 충분한 정보를 제공하지 않았습니다. 예 : 어떤 크기의 그래프입니까? 이 그래프를 어떤 주파수로 쿼리 하시겠습니까? 이 쿼리에 대한 실시간 응답이 필요합니까? 응용 프로그램이 무엇인지에 대한 자세한 정보, 사용자의 목적은 도움이 될 것입니다.

Graph Transformation in Relational Databases (.PDF), G. 바로 (Varro), K.의 :

어쨌든, SQL 기반의 DBMS 효과적으로 그래프 구조를 처리 할 수없는 가정 일반적인 반응에 대응하기 위해, 나는 약간의 참조를 줄 것이다 Friedl, D. Varro, International Workshop on Graph-Based Tools (GraBaTs) 2004;

5 결론 및 향후 연구 논문에서

, 우리는 기성품 관계형 데이터베이스를 기반으로 새 그래프 변환 엔진을 제안했다. 우리의 접근 방식의 기본 개념을 스케치 한 후 우리는 을 수행하여 AGG [5] 및 PROGRES [18] 도구의 변형 엔진 인 과 비교함으로써 프로토 타입 구현을 평가했습니다.
우리의 실험에서 얻을 수있는 주요 결론은 관계형 데이터베이스가 그래프 변환 엔진의 구현 프레임 워크로 유망한 후보를 제공한다는 것입니다. 우리는 유망한 실험 방법 인 결과가 최악의 평가 방법을 사용하여 얻은 것이라는 사실에 주목한다. 즉, 다음 규칙의 관점을 여전히 비효율적으로 처음부터 다시 계산하고, 특히 을 사용하여 모델 변환을 다시 계산한다. 같은 규칙을 가진 많은 수의 독립 매치 . ...

그들은 PostgreSQL을 DBMS로 사용했는데,이 응용 프로그램에서는별로 좋지 않습니다. 내가 의심 할 여지가 있으면 LucidDB을 시도해보고 더 나은지 확인할 수 있습니다.

Incremental SQL Queries (여기에 하나 이상의 종이, 당신은 "는 SQL에서 그래프의 전 이적 폐쇄 유지"에 집중해야한다) : "

는 .. 우리는 보여 주었다 전이 폐쇄, 교류 경로, 동일 세대 및 재귀 기타 일부 보조 관계가 허용되는 경우 쿼리는 SQL에서 유지 될 수있다. 사실, 그들은 모두 인수에 대응 2. 중 가장 보조 관계를 이용하여 유지 될 수있다 ..

Incremental Maintenance of Shortest Distance and Transitive Closure in First Order Logic and SQL을.

편집 : 당신은 내가 다음, 가장 좋은 방법은 모두 메인 메모리 전용 그래프 라이브러리와 DBMS 기반의 솔루션으로 조금 실험을 생각 신중하게 장단점을 평가 ... 그래서 더 자세한 정보를 제공 두 솔루션의

예 : DBMS를 설치해야합니다 (SQLite과 같은 "삽입 가능"DBMS를 사용하지 않는 경우). 응용 프로그램을 배포해야 할 위치와 사용자를 알 수 있습니다. 반면 DBMS를 사용하면 지속성 (그래프 라이브러리를 지원하여 그래프를 유지할 수 있는지 여부는 알 수 없음), 트랜잭션 관리 및 기타 수많은 이점을 얻을 수 있습니다. 귀하의 신청서와 관련이 있습니까? 다시 한 번 당신 만 알 수 있습니다.

Answer 2

처음 언급 한 옵션이 가장 적합합니다. 그래프는 많은 가장자리가없는 경우 (| E | = O (| V |)) 다음 사전을 사용하여 시간과 공간의 더 나은 복잡성을받을 수 있습니다

var graph = new Dictionary<Vertex, HashSet<Vertex>>(); 

흥미로운 그래프 라이브러리 QuickGraph입니다. 절대 사용하지는 않았지만 유망한 것으로 보인다.

Answer 3

나는 다양한 프로그래밍 콘테스트와 프로덕션 코드를위한 꽤 많은 그래프 알고리즘을 작성하고 디자인했다. 그리고 내가 필요할 때마다 그래프 이론 (BFS, DFS, 토폴로지 정렬 등)에서 개념을 모으고 처음부터 다시 개발해야한다는 것을 알았습니다.

아마 경험이 부족한 것이지만, 그래도 그래프 문제를 해결할 수있는 합리적인 범용 쿼리 언어가 없다고 생각됩니다. 몇 가지 범용 그래프 라이브러리를 선택하고 특정 작업을 프로그래밍 언어가 아닌 언어로 해결하십시오. 그것은 당신에게 최고의 성능과 공간 소비를 줄뿐만 아니라 그래프 이론의 기본 개념과 한계에 대한 이해가 필요합니다.

그리고 마지막 하나는 입니다. 그래프에는 SQL을 사용하지 마십시오.