GraphDB勉強会に行ってきました
フューチャーアーキテクトで行われたGraphDB勉強会に参加しました。
The Definition of GraphDB (@doryokujin)
Graph Type for GraphDB
Graphとは?
- NodeとEdge
- NodeとNodeのあいだにはEdgeがあり、EdgeにはNodeとNodeの関係(Relationship)をもっている。
- Undirected Graph, Directed Graph
- Mixied Graph
- Undirected Graph + Directed Graph
- Multigraph
- NodeとNodeに複数のEdgeがある、Edgeがループしている
- システムとしてあつかいやすくするため、矢印のないものは両方向に矢印をもつ2本のEdgeとし、1本の矢印は片方の方向しかもたないものとしましょう。
- Sigle-Relational Graph
- NodeとEdgeの関係はひとつだけ
- Multi-Relational Graph
- NodeとEdgeの関係は複数ある
- Property Graph
- Multi-relational Graphを拡張しNodeとEdgeにプロパティ(keyとvalue)をもたせる。
- GraphDBであつかうグラフはほぼProperty Graph
Graph Traversals
Traversal
- GraphDBのクエリはあるNodeやEdgeを中心に隣接をたどっていく。
- RDBやNoSQLでもグラフ構造のデータをもたせることはできる。
- クエリはあるNodeやEdgeの集合から条件に満たすNodeやEdgeを見つける。
- Traversalは指定の条件をもとに、幅優先または深さ優先で探索する。
- NodeからNodeの移動は2Step(NodeからEdge(1step)、EdgeからNode(1step))
- あるNodeを基準に近傍のNodeやEdgeをもってくるモデルがGraphDBに適している。
- リコメンデーション、ソーシャルネットワーク分析、最短経路問題...
- あるプロパティの条件を満たすNodeを検索するようなモデルは適してない。
- RDBやNoSQLのほうがいい(かも)。
Index Free Adjacency
- GraphDBはNodeからNodeに移動するのにIndex-Treeを見ません。
- Mini-IndexというそれぞれのNodeが接続の情報をもっている。
- Lookupのコストが小さい、グラフが大きくなってもほぼコンスタント。
- ただしNodeとEdgeのプロパティはIndex-Treeを作ります。
- はじめのNodeを見つけるのにIndex-Treeを使う。
- Mini-IndexというそれぞれのNodeが接続の情報をもっている。
An Introduction to Neo4j (@doryokujin)
Introduction
- なんでJava?
- EnterPriseむけだから
- #neo4jをつけてTweetすればNeo4jのなかの人がRetweetしてくれます。
Code Example
- Hello World
- MatrixでTraversal
- IndexingにはLuceneを使っている。
Cypher
- TraversalをSQLのように記述できる。
An Introduction to Tinkerpop (@doryokujin)
- TinkerpopはGraphDBを統一してあつかうライブラリを提供するプロジェクト。
Blueprints
- GraphDBのJDBC
- TinkerGraph
- ライトウェイトなIn-MemoryのGraphDB
reXster
- RESTfulに操作できるAPI
- ランク・スコア計算もできる
- ブラウザで操作できるThe Dog House
Gremlin
- Groovyで記述されたTraversal Language
- Code Example
- v.outE: Node vから外にむかって出ているEdgeを取りだす。
- v.outE.inV: Node vから外にむかって出ているEdgeとつながるNodeを取りだす。
- またはv.outと書ける。
- filter: 条件を満たすNodeとEdgeを取りだす。
- paths: 起点から終点までのパスを取りだす。
- loop: Traversのくりかえしをイテレーションしながら取りだす。
Pipes
- Gremlinのドット(.)でつなげるデータフローフレームワーク。
Enjoy Graph DB! (@bibrost)
GraphDBにアクセスする方法
- ネイティブドライバで直接接続する
- DB固有のHTTPインターフェイス
- TinkerPop/Gremlinを経由
- Tinkerpop/Rexster経由(HTTP)
Enjoy!への道
- JVM環境を入れておく。
- Rexterのパッケージをダウンロードする。
- 0.6があるけどbulbsは0.5用なので0.5をダウンロードしましょう。
- Rexterを起動する。
- rexster-start (sh|bat)
- Bulbsをインストールする。
- easy_install bulbs
- あとはEnjoy!
ここで問題
- ユーザ[u]のまだ友だちになっていない友だちの友だちを取りだすクエリ。
- Except Pattern
- g.v(u).ouot.aggregate(x).out.except(x)で書ける。
- aggregate(x): 友だちの集合をxにいれる。
- except(x): xを除く集合(差集合)を取りだす。
- じっさいは自分が友だちに含まれているので集合に自分を含めるとか、uniqueObjectで同じ人を排除する。
- コードはGitHubにあげてある。
告知
- 次回はミクシィでやる(予定)