非環式指示グラフ上の祖先の効率的なデータベースクエリ

StackOverflow https://stackoverflow.com/questions/3755439

質問

家族の「木」などの非環式指示グラフがあるとしましょう（子供には2人の親がいるので、実際には木ではありません）。このグラフの表現をに配置したい 関連した データベースにより、ノードのすべての祖先とノードのすべての子孫を計算することが速くなります。このグラフをどのように表しますか？すべての子孫をどのように照会しますか？ノードと関係をどのように挿入して削除しますか？データについてどのような仮定をしていますか？

最良のソリューションは、 select/insert/delete 祖先と子孫を照会するために実行するステートメント。合計ランタイムのベストビッグOによって壊れたネクタイは、スペースの要件によって結びつきます。

私の同僚は私にこの質問をしました。私は解決策を持っていますが、最悪の場合は指数サイズなので、他の人がそれをどのように解決するかを見たかったのです。

編集

明確化されたリレーショナルデータベース。この質問は、推移的な閉鎖を組み込んだグラフデータベースを使用する場合、些細な（および退屈な）です。

役に立ちましたか？

解決

もしも selects > manipulations, 、そして特にサブツリーを選択します（すべての先祖、すべての子孫）私は 閉鎖- テーブルアプローチ。はい、パステーブル内のパスの爆発ですが、結果を高速にします（隣接モデルとは対照的に）。関連する部分に限定された状態に保ちます（ネストされたセットでの50％の更新とは対照的に）。

ビル・カーウィンは、さまざまなモデルの長所と短所についてオンラインで素晴らしいプレゼンテーションを行っています。 http://www.slideshare.net/billkarwin/models-for-hierarchical-data （スライド48は概要です）。

他のヒント

SQLデータベースのDAGの場合、2つのソリューションしかないように見えました。

  1. 句との再帰。

  2. 推移的閉鎖

実用的なグラフラベル付けスキーム（ネストされたセット、間隔、具体化されたパスなど）にはわかりません

「このグラフをどのように表しますか？」

  • var nodes関係{node：sometype} key {node};
  • var Edges関係{parentNode：shomeType ChildNode：shomeType} key {parentNode ChildNode};
  • 制約no_cycles is_empty（tclose（edges）parentnode = childnode）;

「すべての子孫をどのように照会しますか？」

tclose（edges）parentnode = somevalue;

「ノードと関係をどのように挿入して削除しますか？」

  • エッジの挿入関係{tuple {parentnode somevalue chlidnode somevalue}};
  • 削除するエッジを削除します。

「データについてどのような仮定をしていますか？」

どのような仮定がありますか？ 「指示された非環式グラフ」と言うことにより、指定するすべてのものを指定しました。

RDBMS：Sは、この種のデータを処理するように実際には設計されていません。明らかな選択は、aを使用することです グラフデータベース 代わりに、グラフを別の表現に変換する必要はありません。グラフAPIをずっと使用します。マルコ・ロドリゲスによる良いプレゼンテーションがあります。グラフのトラバーサルを扱う際に基礎となるデータモデルの影響を説明しています。 グラフトラバーサルプログラミングパターン あなたがそれをより深く見たいなら。

の簡単な例を書きました NEO4JグラフデータベースでDAGを処理します 少し前にあなたに役立つかもしれません。

リレーショナルデータベースでは、各ノードに対して保存します。

  • 父親
  • チャイルド
  • 祖先

すべてのインデックスがあり、先祖のフルインデックスがあります

のリクエスト ：

  • すべての先祖：
    • o（log n）（ノードを見つけてから完了）
  • すべての子孫：
    • o（先祖のフルインデックス検索）（データベースの依存）
  • 新しいノード /削除ノード（チャイルドなし）を追加します。
    • o（1）父+祖先の場合
    • o（log n）父を見つける
    • 父の子供を更新するo（|父の子供|）
  • ノードを移動する（難しい） :
    • o（1）父親を更新する
    • o（log n）古い/新しい父親を見つける
    • 父の子供を2回更新しますo（|父の子供|）
    • すべての子孫の祖先を更新します（単純な置き換え）：o（|子孫|*|深さの最大ツリー|）（深さ-max：最大長の大きな文字列（深さ-max）を置き換えて作成します）

全体的な複雑さは次のとおりです。

  • 木の深さ
  • バランスの取れた木？
  • 子供の数？ （平均的に、マックス...）
  • 特定のリレーショナルデータベースでの動作の複雑さ

選択のみ、効率的ですが、更新は困難です。

実際には、RAMサイズの木（たとえば、すべてをRAMに入れておく）を使用して、より多くのRAMをより多くのRAMを購入します。

とにかく、すべてのdescendantsはかなりの費用がかかります。サブツリーでは、すべてを持っていなくても、最大Depth Dの子孫を持つことができます。

サブツリーからサブツリーへの「ジャンプ」：リクエストが増えますが、より高速なものとノードはより速く移動します（サブツリーを更新するだけです）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top