問題タブ [graph-databases]

私は、.NET/Mono フレームワークに基づいてアプリケーションを設計してきました。これは、グラフ理論で最短パスを多用する必要があり、ネイティブ ソリューションを使用してグラフのノードをトラバースしたいと考えています。保守が難しく、パフォーマンスに大きな影響を与える代替ソリューションを実装します。

私のスコープに最適なアプリケーションを見つけました: neo4j。

残念ながら、このアプリケーションは純粋に Java コードで記述されており、.NET には移植できません。これは、2 つのアーキテクチャ間に大きな違いがあるためです。

neo4jのポートまたは.NET用の同様のソリューションがあるかどうかを知っている人はいますか?

私はリレーショナルDBを頻繁に使用しており、利用可能な他のタイプに挑戦することにしました。

この特定の製品は見栄えがよく、有望です：http: //neo4j.org/

グラフベースのデータベースを使用した人はいますか？ユーザビリティの観点からの長所と短所は何ですか？

これらを実稼働環境で使用しましたか？それらを使用するように促した要件は何でしたか？

背景:オブジェクト データベースと思われるものを探しています。ただし、私が調べた (確かに少数の) オブジェクト データベースは単純な永続化レイヤーであり、本格的な DBMS ではありません。私が探しているものがオブジェクトデータベースと見なされるかどうかさえわからないので、正しい方向に私を向けるのに本当に助けていただければ幸いです。

私が探しているものを 2 ページにわたって説明したくないので、例を使用して私の要点を説明します。保存する必要がある "BlogPost" オブジェクトがあるとします。疑似コードでは、次のようなものです。

Comment(独自のクラスであると仮定します。)

現在、リレーショナル データベースでauthorは、 を指す外部キーとして格納され、User.idと はtags、comments関係を格納する別のテーブルを使用して、1 対多または多対多の関係として格納されます。私が欲しいのは、次のことを行うデータベース エンジンです。

• 追加のルックアップが必要な外部キーを使用する代わりに、直接参照を使用して関連オブジェクト ( author、など) を格納します。tags言い換えれば、互いの上にあるオブジェクトは、データベースによってネイティブにサポートされる必要があります
• オブジェクト全体を取得して更新し、データベースに戻すことなく、コメントやタグをブログ投稿に追加できます (ドキュメント指向データベースのように -- CouchDB がその例です)。

私が探しているのはナビゲーションデータベースだと思いますが、わかりません。私が考えていることに少しでも似ているものはありますか？もしそうなら、それは何と呼ばれていますか？(あるいは、実際に動作するデータベースを教えてください。) それとも、私がうるさすぎますか?

編集：

明確にするために、私は ORMや抽象化レイヤーなどを探しているわけではありません。これを内部的に行う実際のデータベースを探しています。難しくて申し訳ありませんが、検索しても何も見つかりませんでした。

編集：

また、JVM 用の何かが優れていると思いますが、現時点では、それがどのプラットフォームで実行されるかはあまり気にしません。

Python でグラフ データベースを開発する必要があります (誰かが開発に参加してくれると嬉しいです。既に少しコードを持っていますが、それについて喜んで話し合います)。

私はインターネットで調査を行いました。Java では、neo4jが候補ですが、実際のディスク ストレージについては何も見つかりませんでした。Python には、多くのグラフ データ モデルがあります(PEP 以前のこの提案を参照してください。

ただし、トリプルストアについては知っています。triplestores は基本的に RDF データベースであるため、グラフ データ モデルを RDF にマップして保存することもできますが、この解決法については (主に経験不足のため) 不安です。その一例がセサミです。実際には、クライアント コードが RDF ドキュメントを直接ハッキングしたい場合を除いて、いずれにせよ、インメモリ グラフ表現から RDF 表現に、またはその逆に変換する必要がありますが、これはほとんどありそうにありません。オブジェクトを作成する代わりに、DB タプルを直接処理するようなものです。

現時点で、Python でのグラフ データの保存と検索 ( a la DBMS) の最先端は何ですか? できれば実装に関心のある誰かの助けを借りて、Graph API PEP の提案者と協力して、実装の開発を開始することは理にかなっていますか? これは今後数か月の私の仕事の一部になることに注意してください。したがって、この最終的なプロジェクトへの私の貢献は非常に深刻です;)

編集： directededgeも見つかりましたが、商用製品のようです

私は、C++ 用のグラフベース (またはキー値) データベース ライブラリの設計の準備段階にいます。これは、多くの人がhttp://neo4j.org/などのプロジェクトに似ていることがわかります。

これは設計の非常に初期の段階であるため、私の要件は単純で洗練されておらず、(認めますが)おそらくまだかなり素朴です。

• 有向非巡回グラフ
  • 根が少なく葉が多い木のような構造
  • ブランチには他のブランチへの参照が含まれる場合があります
  • しかし、サイクルはありません
  • グラフはキーと値のペアで表されます。ほとんどの場合、キーと値は単純な型 (整数) ですが、一部は文字列などのより複雑な型を参照する場合があります。
• クエリ
  • 通常、単純なクエリではエッジが返されます。つまり、このルートから始まるエッジは、(キー / 値 / キーと値のタプル) に対応しますか?
  • キーの文字列を使用したクエリ (キー、キー、キー、値)
• アクセスパターンとパフォーマンス
  • 高速ルックアップを強調する必要があります
  • エッジの追加
  • ただし、グラフからのエッジ/ノードの削除はありません。つまり、グラフは大きくなりますが、縮小することはありません。
  • キャッシュの使用に合わせてメモリ レイアウトを最適化するために、グラフで最適化が実行される場合があります。
  • グラフのサイズは約 1 MB ～ 2 GB で、ほとんどの場合、プライマリ メモリに収まるはずです。

これらの大まかな要件を課題として考えると、主な懸念事項は次のとおりです。

• メモリ ストレージ: レイアウト、割り当て
  • たとえば、固定サイズのブロックのプールですか?
  • クラスタリングアルゴリズムによるメモリ割り当て?
• 高速クエリ
• 動的再編成
  • エッジ/ノードの追加を処理する方法は?
  • 最適化のための更新 (例: メモリ レイアウトの改善)
• 同時アクセス
  • たとえば、最適化スレッドによるメモリ レイアウトの変更を処理しますか?

私は仕事をするための良い出発点を探しているので、既存の仕事への参照を喜んで受け取ります. 最も重要なのは、私が考えていなくて、何を考えるべきか?

ノードがペアでラベル付けされ（現在これには String[] を使用）、他のノードに任意にリンクできる無向グラフが必要です。タイプ Hashtable から始めました。これは私にとって十分なスペース効率ではないことがわかりました.60,000ノード程度（最終的にはその数をはるかに超える）にするつもりです.

メモリ効率を高めるために、この種のグラフをどのように実装すればよいですか? 代わりに、ある種のリレーショナル データベースを検討する必要がありますか?

非常に大きな無向で重みのないグラフ (数億の頂点から始まり、頂点あたり最大 10 個のエッジ) があり、分散されておらず、シングル スレッドのみで処理され、幅優先検索を実行したいとします。それらは I/O バウンドであると予想されるため、BFS に適したディスク ページ レイアウトが必要です。ディスク容量は問題ではありません。検索は、すべての頂点で同じ確率で開始できます。直観的には、異なるディスク ページ上の頂点間のエッジの数を最小限に抑えることを意味します。これは、グラフの分割の問題です。

グラフ自体はスパゲッティのように見えます。ランダムに相互接続されたポイントのランダムなセットを考えてみてください。短いエッジに偏りがあります。

問題は、どのようにして 1 つのパーティション グラフをこのように大きくするかということです。私が見つけた利用可能なグラフ パーティショナーは、メモリにのみ収まるグラフで動作します。ストリーミング グラフ パーティショニング アルゴリズムの説明も実装も見つかりませんでした。

または、BFS で適切に機能するディスク レイアウトを取得するためのパーティション グラフの代わりになるものがあるでしょうか?

現在、近似として、頂点に空間座標が関連付けられているという事実を使用し、頂点をヒルベルトのソート順でディスクに配置します。このようにして、空間的に近い頂点は同じページに配置されますが、それらの間のエッジの有無は完全に無視されます。私はもっ​​とうまくやれるだろうか？

別の方法として、頂点のヒルベルト ソート順を使用してグラフを断片に分割し、サブグラフを分割し、それらをつなぎ合わせて、継ぎ目の不十分な分割を受け入れることができます。

私がすでに調べたいくつかのこと：

1. 数十億のノードと頂点を持つ大規模な重み付けされていない有向グラフを保存する方法
2. http://neo4j.org/ - ディスク上でグラフ レイアウトを行う方法に関する情報が見つかりませんでした

パーティショニングの実装 (私が間違っていない限り、それらはすべてグラフをメモリに収める必要があります):

1. http://glaros.dtc.umn.edu/gkhome/views/metis
2. http://www.sandia.gov/~bahendr/chaco.html
3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
4. http://www.cerfacs.fr/algor/Softs/MESHPART/

編集: グラフがどのように見えるか、および BFS はどこからでも開始できるという情報。編集:サブグラフの分割に関するアイデア

グラフベースのデータベース ( http://neo4j.org/ ) とオブジェクト指向データベース ( http://www.db4o.com/ )の違いは何ですか?