グラフ探索の構造

「グラフ探索の構造」では、各探索ステップの結果を確認します。

グラフ探索の構造

単純な探索でも複雑な場合がありますが、通常は、再帰や分岐などの特殊な手法を採用しません。

次のグラフ探索のチェーンを探索ステップに分解してみましょう。
g.V().hasLabel('recipe').count()
グラフに含まれるレシピの数を確認するこのグラフ探索には、4つの部分があります。
グラフ探索g
gは、単独で実行するとエラーを返します。
V()によってすべての頂点が収集されます。
すべての頂点が返されます。結果のサンプル:
gremlin>  g.V()
==>v[{~label=ingredient, member_id=18, community_id=1989847424}]
==>v[{~label=ingredient, member_id=19, community_id=1989847424}]
==>v[{~label=ingredient, member_id=16, community_id=1989847424}]
==>v[{~label=ingredient, member_id=17, community_id=1989847424}]
==>v[{~label=ingredient, member_id=22, community_id=1989847424}]
==>v[{~label=ingredient, member_id=13, community_id=1989847424}]
==>v[{~label=meal, member_id=25, community_id=1989847424}]
==>v[{~label=ingredient, member_id=24, community_id=1989847424}]
==>v[{~label=recipe, member_id=14, community_id=1878171264}]
==>v[{~label=recipe, member_id=21, community_id=1878171264}]
==>v[{~label=recipe, member_id=19, community_id=1878171264}]
==>v[{~label=meal, member_id=27, community_id=1989847424}]
==>v[{~label=recipe, member_id=20, community_id=1878171264}]
==>v[{~label=meal, member_id=26, community_id=1989847424}]
==>v[{~label=book, member_id=13, community_id=1878171264}]
==>v[{~label=book, member_id=10, community_id=1878171264}]
==>v[{~label=book, member_id=11, community_id=1878171264}]
==>v[{~label=author, member_id=1, community_id=1878171264}]
==>v[{~label=author, member_id=0, community_id=1878171264}]
==>v[{~label=author, member_id=3, community_id=1878171264}]
==>v[{~label=ingredient, member_id=2, community_id=1989847424}]
==>v[{~label=author, member_id=2, community_id=1878171264}]
hasLabel('recipe')によって、recipe(レシピ)とラベル付けされた頂点をフィルターで除外します。
レシピである頂点のみが返されます。
gremlin>  g.V().hasLabel('recipe')
==>v[{~label=recipe, member_id=14, community_id=1878171264}]
==>v[{~label=recipe, member_id=21, community_id=1878171264}]
==>v[{~label=recipe, member_id=19, community_id=1878171264}]
==>v[{~label=recipe, member_id=20, community_id=1878171264}]
==>v[{~label=recipe, member_id=17, community_id=1878171264}]
==>v[{~label=recipe, member_id=18, community_id=1878171264}]
==>v[{~label=recipe, member_id=15, community_id=1878171264}]
==>v[{~label=recipe, member_id=16, community_id=1878171264}]
count()によって頂点の数をカウントします。
最後の探索ステップによって返された頂点の数が合計されます。
gremlin>  g.V().hasLabel('recipe').count()
==>8
返される頂点情報は、次の3つの部分で構成されます。
member_id
グループ内の頂点ID
community_id
グラフ内のコミュニティID
label
指定された頂点ラベル
グラフ・パーティショニングは、グラフ・オブジェクト取得の重要な局面です。DSE Graphでは、最適化アルゴリズムを使用して各頂点の member_idcommunity_idを設定します。関係は次のとおりです。
  • グラフは、排反コミュニティの集合である
  • コミュニティは、排反メンバー頂点の集合である
排反セットには共通の要素がありません。したがって、頂点は1つのコミュニティのみのメンバーです。上述の例では、すべての頂点は2つのコミュニティにあります。 member_idは各コミュニティ内の値に設定されます。

グラフ探索と辺

以下に示された探索を試す前に、Studio(コピー&ペースト)またはGremlin Console(/tmp/generateReviews.groovyを読み込む)で以下のスクリプトを実行します。
// reviewer(レビュー担当者)頂点
johnDoe = graph.addVertex(label, 'reviewer', 'name','John Doe')
johnSmith = graph.addVertex(label, 'reviewer', 'name', 'John Smith')
janeDoe = graph.addVertex(label, 'reviewer', 'name','Jane Doe')
sharonSmith = graph.addVertex(label, 'reviewer', 'name','Sharon Smith')
betsyJones = graph.addVertex(label, 'reviewer', 'name','Betsy Jones')

beefBourguignon = g.V().has('recipe', 'name','Beef Bourguignon').tryNext().orElseGet {graph.addVertex(label, 'recipe', 'name', 'Beef Bourguignon')}
spicyMeatLoaf = g.V().has('recipe', 'name','Spicy Meatloaf').tryNext().orElseGet {graph.addVertex(label, 'recipe', 'name', 'Spicy Meatloaf')}
carrotSoup = g.V().has('recipe', 'name','Carrot Soup').tryNext().orElseGet {graph.addVertex(label, 'recipe', 'name', 'Carrot Soup')}

// reviewer - recipe間の辺
johnDoe.addEdge('rated', beefBourguignon, 'timestamp', Instant.parse('2014-01-01T00:00:00.00Z'), 'stars', 5, 'comment', 'Pretty tasty!')
johnSmith.addEdge('rated', beefBourguignon, 'timestamp', Instant.parse('2014-01-23T00:00:00.00Z'), 'stars', 4)
janeDoe.addEdge('rated', beefBourguignon, 'timestamp', Instant.parse('2014-02-01T00:00:00.00Z'), 'stars', 5, 'comment', 'Yummy!')
sharonSmith.addEdge('rated', beefBourguignon, 'timestamp', Instant.parse('2015-01-01T00:00:00.00Z'), 'stars', 3, 'comment', 'It was okay.')
johnDoe.addEdge('rated', spicyMeatLoaf, 'timestamp', Instant.parse('2015-12-31T00:00:00.00Z'), 'stars', 4, 'comment', 'Really spicy - be careful!')
sharonSmith.addEdge('rated', spicyMeatLoaf, 'timestamp',Instant.parse('2014-07-23T00:00:00.00Z'), 'stars', 3, 'comment', 'Too spicy for me. Use less garlic.')
janeDoe.addEdge('rated', carrotSoup, 'timestamp', Instant.parse('2015-12-30T00:00:00.00Z'), 'stars', 5, 'comment', 'Loved this soup!Yummy vegetarian!')
必要に応じてグラフ・データをフィルターおよび転換しながら、任意数の探索ステップを探索に関連付けることができます。場合によっては、予期せずして辺ができることがあります。以下の探索を取り上げてみましょう。
g.V().hasLabel('recipe').has('name', 'Beef Bourguignon').inE().values('comment')
このグラフ探索は、前回の探索と同様にg.V().hasLabel('recipe')で開始されます。その後には以下が続きます。
レシピのタイトルが指定された頂点のみを選択する探索ステップ
フィルターは、レシピのタイトルが一意であれば、その1つのレシピをキャプチャします。
gremlin>  g.V().hasLabel('recipe').has('name', 'Beef Bourguignon')
==>v[{~label=recipe, member_id=14, community_id=1878171264}]
内向き辺を取得する探索ステップ
このステップでは、全結果からサンプルした2つの辺からラベルの付いた辺がすべてフィルターされていることに注目してください。ターゲット結果が格付けのみである場合、inE('rated')を使用した方がより正確な結果が得られます。
gremlin>  g.V().hasLabel('recipe').has('name', 'Beef Bourguignon').inE()
==>e[{out_vertex={~label=reviewer, member_id=4, community_id=857859584}, 
local_id=ca461ec0-0e7e-11e6-b5e4-0febe4822aa4, 
in_vertex={~label=recipe, member_id=14, community_id=1878171264}, 
~type=rated}]
[{~label=reviewer, member_id=4, community_id=857859584}-rated->{~label=recipe, member_id=14, community_id=1878171264}]
==>e[{out_vertex={~label=reviewer, member_id=5, community_id=857859584}, 
local_id=ca5bf0b0-0e7e-11e6-b5e4-0febe4822aa4, 
in_vertex={~label=recipe, member_id=14, community_id=1878171264}, 
~type=rated}]
[{~label=reviewer, member_id=5, community_id=857859584}-rated->{~label=recipe, member_id=14, community_id=1878171264}]
==>e[{out_vertex={~label=reviewer, member_id=6, community_id=857859584}, 
local_id=ca72d410-0e7e-11e6-b5e4-0febe4822aa4, 
in_vertex={~label=recipe, member_id=14, community_id=1878171264}, 
~type=rated}]
[{~label=reviewer, member_id=6, community_id=857859584}-rated->{~label=recipe, member_id=14, community_id=1878171264}]
==>e[{out_vertex={~label=reviewer, member_id=7, community_id=857859584}, 
local_id=ca8a0590-0e7e-11e6-b5e4-0febe4822aa4, 
in_vertex={~label=recipe, member_id=14, community_id=1878171264}, 
~type=rated}]
[{~label=reviewer, member_id=7, community_id=857859584}-rated->{~label=recipe, member_id=14, community_id=1878171264}]
==>e[{out_vertex={~label=author, member_id=0, community_id=1878171264}, 
local_id=524504c0-0e7b-11e6-b5e4-0febe4822aa4, 
in_vertex={~label=recipe, member_id=14, community_id=1878171264}, 
~type=created}]
[{~label=author, member_id=0, community_id=1878171264}-created->{~label=recipe, member_id=14, community_id=1878171264}]
格付けされた辺のコメント・プロパティの解析
ここでは、inE()は、辺ラベルratedで指定されています。プロパティ・キーcommentのプロパティ値は次のように取得されます。
gremlin>  g.V().hasLabel('recipe').has('name', 'Beef Bourguignon').inE('rated').values('comment')
==>Yummy!
==>Pretty tasty!
==>It was okay.

グラフ探索を1ステップごとに構築することで、興味深い結果と、探索の作成方法に関する面白い洞察が得られます。

グラフ探索のパス

グラフ探索で使用するパスを示す探索ステップがあります。まず、料理本とレシピのタイトルを指定して、材料として牛肉と人参がリストされているレシピのどれが料理本に含まれるかという質問に答える探索結果を見つけます。
gremlin>  g.V().hasLabel('ingredient').has('name',within('beef','carrots')).in().as('Recipe').
out().hasLabel('book').as('Book').
select('Book','Recipe').by('name').
by('name')
==>[Book:The Art of French Cooking, Vol. 1, Recipe:Beef Bourguignon]
==>[Book:The Art of Simple Food:Notes, Lessons, and Recipes from a Delicious Revolution, Recipe:Carrot Soup]
ingredientからrecipe、そしてbookへという探索パスが想定されます。この仮定が正しいかどうかを確認するには、探索の末尾にpath()を追加します。
gremlin>  g.V().hasLabel('ingredient').has('name',within('beef','carrots')).
in().as('Recipe').
out().hasLabel('book').as('Book').
select('Book','Recipe').
by('name').by('name').path()
==>[v[{~label=ingredient, member_id=22, community_id=1878171264}], 
v[{~label=recipe, member_id=14, community_id=1878171264}], 
v[{~label=book, member_id=10, community_id=1878171264}], 
{Book=The Art of French Cooking, Vol. 1, Recipe=Beef Bourguignon}]
==>[v[{~label=ingredient, member_id=21, community_id=1989847424}], 
v[{~label=recipe, member_id=20, community_id=1878171264}], 
v[{~label=book, member_id=13, community_id=1878171264}], 
{Book=The Art of Simple Food:Notes, Lessons, and Recipes from a Delicious Revolution, Recipe=Carrot Soup}]
どの場合も、探索は想定されるパスに従っていることに注意してください。

探索メトリック

メトリックでは、各グラフ探索ステップの出力をトレースすることに加えて、興味深い洞察も得られます。最後に示した探索にメトリックを追加するには、追加の連鎖ステップをいくつか使用します。
gremlin>  g.V().hasLabel('recipe').has('name', 'Beef Bourguignon').inE('rated').values('comment').profile()
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
DsegGraphStep([~label.eq(recipe), name.eq(Beef ...                     1           1           0.979    73.00
query-optimizer                                                                              0.184
retrieve-new                                                                                 0.115
iterator-setup                                                                               0.390
DsegVertexStep(IN,[rated],edge)                                        4           4           0.286    21.37
query-optimizer                                                                              0.080
retrieve-new                                                                                 0.014
iterator-setup                                                                               0.062
DsegPropertiesStep([comment],value)                                    3           3           0.075     5.63
>TOTAL                     -           -          1.342        -
探索数、および探索ステップの完了にかかる時間とともに、その探索ステップのタイプがリストされています。探索ステップを並行して処理できる場合、データの取得に複数の探索を使用します。一部の探索ステップはグラフ全体を対象とするため、グラフ全体からの取得が必要です。DsegGraphStepでは、グラフ全体を対象として特定の条件に一致する頂点を見つけて取得します。その他の探索ステップは、特定のグラフを対象とした巡回であり、並行して処理できます。DsegVertexStepは、制約されたパスに沿って巡回する特定グラフ対象の巡回です。DSE Graphでは、自動クエリー最適化機能を使用して、存在するあらゆるインデックス構造を効率的に使用するための探索戦略を特定します。
メトリックを見ると、パフォーマンスに関する質問が浮かび上がります。たとえば、上述の探索を最適化する方法はあるかなどという質問です。実際、簡単な変更により、時間を節約できます。
==>Traversal Metrics
Step                                                               Count  Traversers       Time (ms)    % Dur
=============================================================================================================
DsegGraphStep([~label.eq(recipe), name.eq(Beef ...                     1           1           0.733    70.62
query-optimizer                                                                              0.143
retrieve-new                                                                                 0.059
iterator-setup                                                                               0.289
DsegVertexStep(IN,[rated],edge)                                        4           4           0.241    23.29
query-optimizer                                                                              0.083
retrieve-new                                                                                 0.006
iterator-setup                                                                               0.049
DsegPropertiesStep([comment],value)                                    3           3           0.063     6.10
>TOTAL                     -           -          1.038        -
加えた変更は微妙なものです。2つの探索ステップhasLabel('recipe').has('name', 'Beef Bourguignon') を1つの探索ステップ has('recipe', 'name', 'Beef Bourguignon')で置換しました。各測定値が異なる場合がありますが、通常、2番目の探索が最初の探索をしのぎます。