グラフ探索の構造

グラフ探索の構造では、各探索ステップの結果が調べられます。

グラフ探索の構造

単純な探索が複雑になる場合もありますが、通常は、再帰や分岐などの特殊なテクニックは採用されません。

グラフ探索チェーンを探索ステップに分割します。

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')で除外します

レシピである頂点のみが返されます。

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

標準の頂点IDが自動生成され、一意であることが保証されます。標準の頂点IDは次の3つの部分から成ります。

member_id: グループ内の頂点ID
community_id: グラフ内のコミュニティID
label: 指定された頂点ラベル

標準の頂点IDは人工的であり、フットプリントが小さく抑えられています。構成は特定のドメインと関連付けられておらず、より柔軟です。グラフのパーティション分割は、グラフ・オブジェクトを取得するための重要な側面の1つです。DSE Graphでは、各頂点のmember_idとcommunity_idの設定に最適化アルゴリズムが使用されます。次のような関係があります。

グラフは排反コミュニティのコレクションです
コミュニティは排反メンバー頂点のコレクションです

排反セットは共通の要素を持ちません。そのため、各頂点は単一コミュニティのみのメンバーとなります。前述の例では、すべての頂点が2つのコミュニティに含まれています。member_idは各コミュニティ内の値に設定されます。

自然キー（外部で生成されるキー）を使用して、カスタムの頂点IDを作成することもできます。ただし、カスタムの頂点IDを使用するアプリケーションは手動でパーティション分割しなければならず、キーの一意性を保証することはユーザーの責任となります。

エッジを使用したグラフ探索

以下に示す探索を試行する前に、Studio（コピー＆ペースト）またはGremlin Console（:load /tmp/generateReviews.groovy）で次のスクリプトを実行します。

// reviewer vertices
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 edges
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!')

グラフ・データのフィルター処理と変換を必要に応じて行って、任意の数の探索ステップをつなげて1つの探索にまとめることができます。場合によっては、予想外にエッジが結果として生成されることがあります。次の探索があるとします。

g.V().hasLabel('recipe').has('name', 'Beef Bourguignon').inE().values('comment')

このグラフ探索は、前回の探索と同様にg.V().hasLabel('recipe')で始まります。その後に以下が続きます。

指定されたレシピ・タイトルを持つ頂点のみを選択するための探索ステップ

レシピ・タイトルが一意の場合は、このフィルターによって単一レシピが捕捉されます。

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}]

ratedエッジからのcommentプロパティの解析

ここでは、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番目の探索のパフォーマンスが最初の探索を上回ります。

DSE 5.1以降では、index-queryなどのメトリクスの詳細情報がDSE Studio 2.0によって提供され、使用されるクエリーのタイプ（検索、マテリアライズド、セカンダリ）が示されます。ここに示す2つの例では、使用されているマテリアライズド・ビュー・インデックスと検索インデックスが表示されます。