1

リレーショナル データベースは、さまざまな種類のグラフ (ツリー、有向グラフ、無向グラフなど) を格納するためによく使用されます。

では、主要な DBMS (Microsoft、MySql、Oracle、PostgreSQL、SqlLite など、アルファベット順にいくつか例を挙げると) のどれにも、リレーションをグラフとして扱うためのライブラリ サポートが含まれていないのはなぜでしょうか?

例として、いくつかの望ましい機能：

  • 制約チェック (接続性、非循環性、平面性など)
  • 一般的に必要な機能 (最短パス、最小全域木、推移閉包、最大フロー/最小カット、クリーク検出、ハミルトニアン/オイラー サイクルなど)
  • 上記のいずれかのパフォーマンスを向上させるために必要な補助データ構造

データベースの外部でこれらのいくつかのサポートを構築することは、(他の理由の中でも) 次の理由で複雑です。

  • 本質的に複雑です（ライブラリがここで役立ちます）
  • 短い答えは多くの場合、多くのデータによってサポートされます。最短パス アルゴリズムを実行している外部クライアントは、データベースと非常に「おしゃべり」する必要があるか、必要以上の量のデータを取得する必要があります。どちらを選択してもネットワークに悪影響を与える
  • 整合性がグラフ理論の制約に依存する場合、整合性を維持するには、提案されたすべての更新にアクセスする必要があるため、トリガーが必要であり、トリガーから既存のグラフ ライブラリにアクセスすることは、多くのシステムでは複雑です。
  • DBMS ストレージ マネージャーとオプティマイザーは、インデックスの場合と同様に、補助データ構造の問題に対処するために独自に配置されています。

これは修辞的な質問ではありません。興味深い技術的 (または歴史的) な理由があるかどうかを実際に知りたいのです。

4

3 に答える 3

2

私は研究グループで働いており、RDF(S) データのデータベースを開発することに特に関心を持っています。これは基本的にグラフのラベルが付けられているか、トリプル [主語、述語、目的語] であり、基本的にはグラフのエッジ [sourceNode, edgeLabel,ターゲットノード]。

問題の難しさを理解するために尋ねる質問: ラベル付きグラフに対してどのような種類のインデックスを作成する予定ですか? 共通の「プロパティ」(各「述語」は、オブジェクトの値を持つサブジェクトのプロパティ) を利用し、それに応じてエッジにインデックスを付ける必要があります。価値が18インチ以上の人。

説明のために、ここに単純なアプローチを示します。これはスキーマを無視します (そして、スキーマがあれば良いと全会一致で同意する従来のデータベース研究とはまったく反対の方向に進んでいます)。スキーマ情報は完全に無視されます (このホワイト ペーパーは有用なコンテキストを提供します)。すべてを 3 つの大きなテーブル (s: 主語、p: 述語、o: オブジェクト) に格納するだけです。

  1. [s、p、o]
  2. [p、o、s]
  3. [o、s、p]

これらの 3 つは、(最大で) 主語、(最大で) 述語、(最大で) 目的語 (つまり、 、 、 、 、 、 の形式のクエリ) で効率的に評価される(s, *, *)クエリ(*, p, *)に(*, *, o)答える(s, p, *)のに(s, *, o)十分(*, p, o)です(s, p, o)。ただし、複雑なクエリは多くの「パス式」で構成され (つまり、いくつかの基準を満たす特定のパスを見つけることができるデータを記述します)、それぞれがこれらの (大きな!) テーブルの 1 つの自己結合に変換されますが、これはそうではありません。これは問題です。

ほら、これはポケットに入った単純なグラフ データベースです。:)

結論として、これは活発な研究の分野です。私は現在の最新技術について詳しくは知りませんが、AllegroGraphなどの非常に優れた結果を主張する製品を見てきました。

于 2010-01-14T01:48:50.727 に答える
0

あなたの質問には、それ自体の答えの始まりが含まれていると思います。

リストする一般的に必要な機能は、汎用データベースの場合、一般的にはまったく必要ありません。はい、グラフ操作には確かに必要ですが、顧客への請求にはめったに必要ありません。もちろん、リレーショナル データベースはグラフをテーブルに格納できますが、グラフの操作は、私が見た SQL のどのバージョンよりも優れています。

データベースの外部でこれらのいくつかのサポートを構築することは複雑です。それが真実であり、それが私たち全員が非常に多くの報酬を得る理由です。しかし、それらのサポートをデータベースに組み込むのは同じくらい複雑ですよね?

于 2010-01-14T02:07:32.260 に答える
0

Oracle は、グラフ機能 (Oracle Locator/Oracle Spatial) とセマンティック Web 機能をサポートしています。

于 2009-10-24T05:47:37.487 に答える