0

グラフ データベースとリレーショナル データベースの横断の時間計算量はどれくらいですか?

4

3 に答える 3

2

コンピューターと代数のどちらが速いですか?

リレーショナルモデルは、データについて考える方法であり、ユーザーにデータを表す方法です。実装については何も述べていません。リレーショナルデータベースの時間計算量について尋ねるのは、の時間計算量について尋ねるようなものです。 f(x)

データを格納するために使用したタプルの線形配列を使用したSQLDBMSはありません。それらはすべて、ある種のツリーを使用します:Bツリー、B+ツリー。ツリーはグラフです。エルゴ、グラフデータベースが主張する物理的な利点は、私に言わせれば、まあ、何にも基づいていません。

SQL DBMSは、過去数年間に、いわゆる再帰クエリのサポートを追加しました。これらのクエリを効率的に実行しても、理論上の問題は発生しません。しかし、クエリオプティマイザはそれがうまく機能するためにそれをサポートする必要があり、オープンソースプロジェクトがその分野でやるべきことがあるとしても驚かないでしょう。

武器を選択する際には、「リレーショナルデータベース」についてではなく、特定の実装での再帰クエリ処理のサポートについて質問してください。

ただし、誤った対称性には注意してください。「グラフデータベース」に欠けているもののかなり長いリストがあります。たとえば、リレーショナルモデルは代数に基づいています。これは、SQLが(ほとんどの場合、大まかに)基づいているものです。グラフ理論にはそのような代数がなく、その結果、優れた操作言語がありません。制約の実施とトランザクションについても同様の話があります。

于 2013-03-14T16:07:55.867 に答える
1

グラフ データベースの (おそらく) 重要なポイントは、トラバーサルのために結合を行う必要がないことです。

于 2013-10-23T15:45:06.153 に答える
0

両方のO(N)?

グラフDBのコアにはテーブルがあります(https://stackoverflow.com/a/2968931/623735)。また、RDBは、テーブルの処理が非常に効率的になるように進化しました。したがって、永続ストレージを備えたほとんどの大規模なGDBは、RDBを使用してノードテーブルを格納します。GDBは、従来のすべてのデータテーブル行のIDを「ノード」の単一のテーブルにスタックするだけです(効率的なインデックス作成のためにグループ化およびソートされています)。GDBの魔法は、グラフを歩いたり探索したりするための効率的なアルゴリズムにあります。

したがって、GDBが2つのテーブルの結合(トラバーサル)を実際に行うのは、RDBMSが同じ種類のデータに対する同じ種類のクエリに対して行うのと同じではないと思います。GDBは、リンクリストのような方法で1つのノード(ノードテーブルの行)から別のノードに移動するだけです。クエリしたノードが見つかると、ノードプロパティテーブルに対して1回の「トラバーサル」を実行して、クエリした情報(名前、ランク、シリアル番号;)を取得します。

于 2013-03-08T18:26:18.547 に答える