踊る犬.netブログ (旧)

Cayleyでお手軽グラフデータ操作入門

Takuya

Cayleyとは

Cayleyは、最近リリースされたばっかりのグラフエンジンです。
グラフエンジンとは、グラフ構造を扱うために特化したNOSQLのDBMSです。グラフデータベースなどと呼ばれたりもします。
Cayleyの他には、neo4jが有名です。
Cayleyの作者のBarak Michener氏はGoogleナレッジチームのエンジニアです。
特徴は以下の通り：

Google Open Source Blogによると、Cayleyが作られた経緯には、Freebaseの膨大なグラフデータを素早くフリーで簡単に使えるようにする事が挙げられています。

本エントリでは、付属のサンプルデータセットを使って基本的な使い方を把握したいと思います。

グラフ構造の基本

Cayleyを使う前に、それが扱うデータ構造についての理解が必要です。
Cayleyが扱うグラフ構造とは、以下のような要素間関係構造をもつデータのことです。

データは、Vertex(頂点)とEdge(枝)の群で構成されます。
これで表される情報は、例えば友達関係、親子関係、所属、ネットワーク、部品構成などです。
巷で人間関係が「ソーシャルグラフ」と呼ばれるゆえんは、このデータ構造の名称にあります。

上図は、Steveの親はJohnである事を示すグラフデータです。
このようなエッジに方向性を含むグラフ構造を有向グラフと呼びます。
Cayleyは有向グラフを扱うエンジンです。

インストールと開始

Release Binaryからプラットフォームに合ったバイナリをダウンロードして任意の場所に展開します。

$ wget https://github.com/google/cayley/releases/download/v0.3.1/cayley_0.3.1_linux_amd64.tar.gz
$ cd cayley_0.3.1_linux_amd64

次にサンプルデータのパスを指定して起動します。

$ ./cayley http --dbpath=30kmoviedata.nq.gz
Cayley now listening on 0.0.0.0:64210

起動すると、ポート64210でウェブサーバが立ち上がります。
ブラウザからアクセスすると以下のような画面が表示されます。

そのほかの起動方法

起動オプションは他にもいろいろあります。詳しくはこちらを参照。

httpの代わりにreplを指定するとREPLプロンプトが立ち上がります。

$ ./cayley repl --dbpath=30kmoviedata.nq.gz
cayley>

基本的なクエリ

クエリはJavaScriptで書けます。
読み込んだサンプルデータはFreebaseの映画データです。
まずは女優の「Uma Thurman」のVertexを探してみます。

graph.Vertex("Uma Thurman").All()

結果：

{
 "result": [
  {
   "id": "Uma Thurman"
  }
 ]
}

このように、graphオブジェクトのメソッドを呼び出してグラフデータにアクセスします。

ここで、Uma Thurmanは名前でありエンティティではありません。
nameにUma Thurmanを持つエンティティを取得してみます。

graph.Vertex("Uma Thurman").In("name").All()

結果：

{
 "result": [
  {
   "id": "/en/uma_thurman"
  }
 ]
}

また、graphにはg、VertexにはVというエイリアスがあります。
以下の式は等価です：

graph.Vertex("Uma Thurman").In("name").All()
g.V("Uma Thurman").In("name").All()

では、Uma Thurmanのエンティティが取得できたので、更に主演した映画の一覧を取得してみます：

graph.V().Has("name", "Uma Thurman").In("/film/performance/actor").In("/film/film/starring").Out("name").All()

結果：

{
 "result": [
  {
   "id": "The Golden Bowl"
  },
  {
   "id": "Les Miserables - The Dream Cast in Concert"
  },
  {
   "id": "Vatel"
  },

...

  {
   "id": "Kill Bill"
  },

...

  {
   "id": "The Life Before Her Eyes"
  },
  {
   "id": "The Avengers"
  }
 ]
}

みなさんご存知「キル・ビル」に主演している事が分かりました！
では逆に、Kill Billの出演者一覧を取得してみます：

g.V().Has("name","Kill Bill").Out("/film/film/starring").Out("/film/performance/actor").Out("name").All()

結果：

{
 "result": [
  {
   "id": "Uma Thurman"
  },
  {
   "id": "David Carradine"
  },
  {
   "id": "Daryl Hannah"
  },

...

  {
   "id": "Sonny Chiba"
  },
  {
   "id": "Julie Dreyfus"
  }
 ]
}

使用したメソッドが In から Out に変化した事にお気づきでしょうか？
これは、起点とするVertexが逆になり、それに伴ってエッジの方向も逆になったためです。

クエリのビジュアライズ

ウェブUIのQuery Shapeを選択して、下記の主演映画一覧のクエリを実行してみます。

graph.V().Has("name", "Uma Thurman").In("/film/performance/actor").In("/film/film/starring").Out("name").All()

すると、下記のような図が表示されます。なんかぐねぐねしてます。

モーフィズムとタグを使う

graph.Morphism(Alias: graph.M)は、パスオブジェクトを作ります。
以下のようによく使うパスを定義すれば、後から使い回せます。

var shorterPath = graph.Morphism().Out("foo").Out("bar")

以下のようにMorphismを呼び出します：

var p = graph.M().Has("name", "Uma Thurman").In("/film/performance/actor").In("/film/film/starring").Out("name");
graph.V().Follow(p).All();

タグを使うと、辿ったパスの任意の頂点を保存できます。
例えば、Uma Thurmanが主演した全ての映画で、共演した俳優・女優の一覧を取得するには：

costar = g.M().In("/film/performance/actor").In("/film/film/starring").Out("name")
graph.V().Has("name", "Uma Thurman").Follow(costar).As("Movie")
.FollowR(costar).Out("name").As("Costar").All()

結果：

{
 "result": [
  {
   "Costar": "Jeremy Northam",
   "Movie": "The Golden Bowl",
   "id": "Jeremy Northam"
  },
  {
   "Costar": "Peter Eyre",
   "Movie": "The Golden Bowl",
   "id": "Peter Eyre"
  },
  {
   "Costar": "Madeleine Potter",
   "Movie": "The Golden Bowl",
   "id": "Madeleine Potter"
  },
  {
   "Costar": "Nickolas Grace",
   "Movie": "The Golden Bowl",
   "id": "Nickolas Grace"
  },

...

  {
   "Costar": "Uma Thurman",
   "Movie": "The Avengers",
   "id": "Uma Thurman"
  },
  {
   "Costar": "Sean Connery",
   "Movie": "The Avengers",
   "id": "Sean Connery"
  },
  {
   "Costar": "Eddie Izzard",
   "Movie": "The Avengers",
   "id": "Eddie Izzard"
  },
  {
   "Costar": "Fiona Shaw",
   "Movie": "The Avengers",
   "id": "Fiona Shaw"
  },
  {
   "Costar": "Patrick Macnee",
   "Movie": "The Avengers",
   "id": "Patrick Macnee"
  },
  {
   "Costar": "Jim Broadbent",
   "Movie": "The Avengers",
   "id": "Jim Broadbent"
  }
 ]
}

クエリ結果のビジュアライズ

Uma Thurmanと過去に共演した事のある主演者同士の関係を取得します：

costar = g.M().In("/film/performance/actor").In("/film/film/starring")


function getCostars(x) {
  return g.V(x).As("source").In("name")
          .Follow(costar).FollowR(costar)
          .Out("name").As("target")
}


function getActorNeighborhood(primary_actor) {
  actors = getCostars(primary_actor).TagArray()
  seen = {}
  for (a in actors) {
    g.Emit(actors[a])
    seen[actors[a].target] = true
  }
  seen[primary_actor] = false
  actor_list = []
  for (actor in seen) {
    if (seen[actor]) {
      actor_list.push(actor)
    }
  }
  getCostars(actor_list).Intersect(g.V(actor_list)).ForEach(function(d) 
{
    if (d.source < d.target) {
      g.Emit(d)
    }
  })
}

getActorNeighborhood("Uma Thurman")

ウェブUIでVisualizeを選択して、上記クエリを実行すると、下図のような画像が得られます：

おお、かっこいいですね！

参考