グラフデータベースでの検索クエリの複雑さはどのくらいですか？

Question

グラフデータベースでの検索クエリの時間複雑度は何ですか（特にNeo4j）。

私は私と関係データを持っています。私はリレーショナルデータベースまたはグラフデータベースを使用してそのデータを格納することを混乱させる。だから、私はその特定のデータベースのクエリのパフォーマンスと時間の複雑さに基づいてデータを保存したいと思います。しかし、私はグラフデータベースのクエリのパフォーマンスと時間の複雑さを見つけることができません。

誰でもお手伝いできますか？

Answer 1

実際には、データのサイズと複雑さに依存します。

neo4jのようなグラフデータベースでは、時間の複雑さはクエリの種類とクエリの背後のplanners（エグゼキュータ）に依存します。 Neo4jは簡単にデータをグラフ化し、データを明確に表示します。

詳細については、Neo4jのblogを参照してください。 また、これと同じようにquestionを参照することもできます。

希望すると便利です。

Answer 2

時間の複雑さは、通常、クエリ（クエリプランナの結果）の処理に依存するため、答えは単純ではありません。すべてのクエリ。

私はNeo4jについて話すことができます（免責事項：私はNeo4j従業員です）。

Neo4jのLuceneインデックスルックアップは、通常、インデックスで開始ノードを見つけるためにのみ実行され、クエリの実行時間の一部を表現するためにはあまり意味がありません。リレーションシップ・トラバーサルは、実際の違いが現れる場所である傾向があります。

開始ノードが見つかると、Neo4jは関係トラバーサルを通じてグラフを歩きます。ネオ4jでは、基本的にネイティブグラフdbsがリレーショナルdbsよりも優れている傾向があります。ポインタを追うコストはトラバーサルごとに一定です。

リレーショナルdbs（リレーショナルdbの上に構築されたグラフレイヤーを含む）の場合、関係トラバーサルは通常、独自の時間複雑度（O（1）ではなく）を持ち、 （特に自己/再帰結合）の数が増加します。

これにより、Neo4jのようなネイティブグラフデータベースは、接続されたデータ、特に些細でないまたは増加するリレーションシップトラバーサルでクエリを処理できるようになります（または、リーバビリティがない場合、 、 その他）。クエリのコストは、データベース内のノードの総数ではなく、クエリに触れられたグラフの部分に関連付けられているため、データベース内の最小のサブグラフにタッチするようにクエリを適切に制約できる場合に役立ちます。

リレーショナルデータベースとグラフデータベースのどちらを使用するかは、データの接続性と実行するクエリによって決まります。

グラフデータベースを決定した場合は、ネイティブと非ネイティブの両方の実装（Neo4jはネイティブグラフデータベースで、インデックスフリー（Neo4がACIDデータベースであるかどうか）、豊富で表現力豊かな照会言語が必要な場合（CypherはNeo4jの照会言語であるため、他の言語と比較して自由に比較することができます）。

詳細については、Why Graph Databases Outperfrom RDBMS on Connected DataのDZone記事、Neo4jのチーフサイエンティストJim WebberのExplaining Graph Databases to a Developerに関する記事をご覧ください。

Answer 3

は実際には、最も可能性の高いシナリオは、いくつかのDBMS（リレーショナルまたはモンゴのようなNoSQL）両方のNeo4j とを使用することです。 Neo4jにすべてのデータセットを保存するのは難しいためです。

DBMSの速度掃引ノードは、Neo4jよりも10-100倍遅いです。また、Neo4jには、最短のPath（および他の多くの）メソッドが組み込まれています。

また、ArangoDBのようなハイブリッドソリューションについて言及することもできます。それは、グラフエンジン+ドキュメントベースのエンジンを持っています。しかし、それは2つの別々のテーブルなので、Neo4j + DBMSと同じくらい不便です。