10

個々の有向グラフを永続化することに興味があります。この質問は、本格的なグラフ データベース ソリューションを求めているのではなく、保存に使用できるドキュメント形式と個々の任意の有向グラフを求めています。 どの表記法とファイル形式が最も賢明な選択になるかはわかりません。

私の主な懸念事項は次のとおりです。

  1. 表現力・柔軟性- さまざまな種類のグラフを表現できる能力が欲しい。標準的なユースケースは単純な有向グラフですが、ツリー、循環グラフ、マルチグラフを表現できるはずです。最低限、エッジとノードのラベル付けと重み付けのサポートを期待します。ハイグラフとエッジ構成/ハイパーエッジを記述するための表記法も非常に望ましいですが、そのようなソリューションが存在しない可能性があることは承知しています。

  2. Type System-Independence - グラフの構造的な性質を表現することに興味があります。一部のソリューションには、型指定されたエッジとノード用の拡張可能な型システムが含まれています (例: RDF / OWL )。型付き要素のプリミティブ (ノード/エッジ/属性) への明確に定義された標準的な分解がある場合にのみ、そのような表現に興味があります。ここで私が避けようとしているのは、同等性が識別できない同等のグラフの複数の表現の機能です。

  3. Canonical Representation - グラフを標準的に表現できるメカニズムが必要です (canonical-representations の語彙的等価性を使用して等価性を判断できるような方法で)。

  4. プレゼンテーションに依存しない - グラフの表示に依存しない表記法を希望します。これには、空間的な向き、色、フォントなどが含まれます。データを表すことにのみ関心があります。DOT language、DGML、またはSVGについて(少なくともこの特定の目的では)気に入らない機能の 1 つは、視覚的表現に重点を置いていることです。

  5. 標準化 / オープン / 互換性- 私がしなければならない実装作業が少ないほど良い。形式が標準化されており、その形式を操作するための信頼できるツールが既に存在する場合は、その形式がより望ましいと言えます。この要件に付随して、フォーマットの互換性が高くなければならないというもう 1 つの要件があります。Microsoft の DGMLのプロプライエタリな性質は、Visual Studio ツールと、(現在) 主に .NET を使用しているという事実にもかかわらず、私の嫌悪感の理由です。W3C が RDF 標準を公開しているという事実は、RDF の限られたサブセットを表現ツールとして検討する動機となっています。GXLとGraphMLにも感謝します、十分に文書化された xml スキーマがあるため、xml 互換のソフトウェア パッケージとデータを統合する機能が容易になります。

  6. シンプルさ / 読みやすさ - 人間が読める構文と解釈の容易さを高く評価しています。また、解析を簡素化する表現も高く評価しています。このため、私はGMLを気に入っていますが、現実的な選択肢になるほど主流ではないことを懸念しています。複雑な (DAG 以外の) 構造を表すそれぞれの能力がそれほど制限されていない場合は、読みやすさのためにJSONまたはYAMLも検討します。

  7. 効率性 / 簡潔な表現- 最終的に選択する形式が何であれ、必然的に永続化してネットワーク経由で転送する必要があることを考慮する価値があります。したがって、ファイル サイズは関連する考慮事項です。

概要

ウィッシュリストのすべての基準を満たすソリューションを見つけることができない可能性が高いことを認識しています。私は単に、私が望むものに最も近く、サポートされていないユース ケースの拡張性を制限しないファイル形式を求めているだけです。

4

3 に答える 3

1

ObWindyPreamble: RDF の世界では、膨大な数の異なる表面構文フォーマットから選択できます。RDF 自体はデータの抽象的なメタモデルであり、直接的な「グラフ構文」ではありません。もちろん、RDF でグラフを直接表現することはできますが (RDF モデルはグラフであるため)、さまざまな種類のグラフを表現したい場合は、抽象化して、さまざまな種類のグラフ。

全体として、RDF が最適な方法であるとは確信していませんが、1 つを選択する場合、RDF のTurtle 構文は検討する価値があると言えます。それは確かに読みやすさとシンプルさのボックスにチェックを入れているだけでなく、標準であり（まあ、ほぼ... W3Cは標準化に取り組んでいます）、幅広い（オープンソース）ツールをサポートしています.

RDF モデルは大まかに集合セマンティクスに従います。つまり、正規の構文表現を実際に適用することはできません。実際のモデルに影響を与えずに 2 つのファイルに異なる順序で情報を格納したり、重複した情報を格納したりすることさえできます。ただし、ファイルを生成するときに単純なソート アルゴリズム (ほとんどの RDF パーサー/ライターがサポートしているアルゴリズム) を適用すると、行ベースの比較を実行し、表面の構文に基づいてグラフの同等性を判断する必要がなくなります。

単純な例として、非常に単純な有向のラベル付きグラフがあるとします。

 A ---r1---> B ---r2---> C

これは、次のように RDF で直接表すことができます (Turtle 構文を使用)。

 @prefix : <http://example.org/> .

 :A :r1 :B .
 :B :r2 :C .

より抽象的なモデリングでは、次のようなことができます。

 @prefix g: <http://example.org/graph-model/> .
 @prefix : <http://example.org/> .

 :A a g:Vertex .
 :B a g:Vertex .
 :C a g:Vertex .

 :r1 a g:DirectedEdge ;
     g:from :A ;
     g:to :B .
 :r2 a g:DirectedEdge ;
     g:from :B ;
     g:to :C .

もちろん、上記は単純化した例にすぎませんが、希望リストにあるもののかなりの数がこれで満たされる可能性があることを示していることを願っています.

ちなみに、さらに単純にしたい場合は、N-Triplesも RDF 構文であり、行ベースであるため、ストリーミング方式で簡単に処理できます。Turtle よりも少し冗長ですが、ファイルの比較が容易になる場合があります。

于 2013-05-06T06:25:29.593 に答える
1

自明なグラフ形式についてはどうですか：

于 2013-05-30T03:38:42.763 に答える