読者です 読者をやめる 読者になる 読者になる

絶品ゆどうふのタレ

ふと気づいたことを綴るだけのメモ

第1回GraphDB勉強会に参加してきた。

昨日、フューチャーアーキテクトさんで開催された第1回GraphDB勉強会に参加してきました。


ほぼスーパー @doryokujin タイムみたいな感じの勉強会だったりしますがw
それでなおこのクオリティなのがさすがですね。

運営の皆さまも、いつもよい勉強会ありがとうございますm(_ _)m


スライドやtwitterまとめについては、@bibrostさんによる、できたてほやほやのgraphdb.jpにまとめ記事が既にまとめられているので、そちらへどうぞ。

ついでに、今回発表内容の中心のネタになっていたneo4jとThinkerPopについてもリンクを置いておきます。


以下、自分が参加して聞いていた際のまとめです。


はてダがmarkdownに対応してくれてないので、まんま貼り付け。そろそろposterousに乗り換えようか。。。

第1回 GraphDB勉強会
====================

The Definition of GraphDB
-------------------------

* Graphとは
  * NodeとEdge(Relationship)で構成されるもの

* 有向グラフと無向グラフ
  * 無向 = お互いが対等になる 
  * 有向 = やじるしになる。方向性を持ち、対等ではない。

* 例:
  * Facebook -> friendは対等で向きを持たない。無向グラフ
  * Twitter -> follow関係は一方向。有向グラフ

* その他にも以下のようなものが考えられる。
  * 有向と無向の混在 = Mixied
  * Node感に複数のedgeがある。Multiple

* Mixiedはシステム的に扱うのは面倒なので考え方を変える
  * 無向グラフは、2本の有向の線と考えられる。
  * 両方の向きを持つグラフは片方の向きのみを持つグラフとして表現することができる。

* Sngle-Relational Graph
  * 全ての頂点が同じオブジェクト・タイプしか持たない
  * 全ての辺も同じ性質しか持たない

* Multi-Relational Graph
  * 各頂点は様々なオブジェクトタイプを持つ
  * 複数の種類のrelationを持つ

* 例:
  * Livlis
  * 物と人というものが、followやイイネ、欲しいなど様々な関係が成り立っている。

* 現実の事象をシステムに落とす場合には、Graph として落とさないと関係性が失われてしまう。

* Property Graph
  * Nodeに対するProperty、Edgeに対するPropertyとして、様々な情報・特徴を持たせる。
  * ここで言うPropertyはkey-valueで表現され、さらにschema freeであるとする。

* 任意の特徴を持つオブジェクト同士を、任意の性質をもつrelationで結ぶ事が出来る、という柔軟性を持たせたGraphをデータとして保持することができるのが、GraphDBと定義されている。


* Hyper Graph というのもある。


### Traversals

* GraphDBでの検索
  * RDBMSなどの検索は、全体の中から特徴を検索するものだが、それとは違う。
  * 主役の頂点を決めて、その近傍を検索する。
  * RDBMSはGlobalな検索、Graphの検索はlocalityを重視した検索になっていると言える。

* Q:XMLDBのXPathの検索と同じ考え方ではないか?
  * A:その通りです。
  * Q:どう同じなの?
    * A:tree構造の中から取ってくるという考え方が、TravarsalとXPathで似ている。

* 頂点から頂点をたどっていく検索がTravarsal

* 幅優先か、深さ優先か、2種類の探索方法がある。

* 最小ステップを定義
* 自分から、出ている辺に移動するのを1ステップ、辺から、はいってくるノードへ移動するのを1ステップ。
  * Q:なぜ、わざわざ2ステップと見るのか?
    * 

* Q:どういうデータの場合に向いている?
  * A:多くのJOINしたほうがいい場合などが考えられる。もちろん、一意にJOINしまくるものがGraphに載せられるということではないはず。
  * そういう意味で、GraphDBを使うかどうかはまず目的が見えてないといけない。

### index-free adjaceny

* External Indexを読みに行かない、というのがGraphDBのindexの特徴。
  * 通常のRDBMSはindex treeと実際のデータを行き来するようにしてデータのTravarsalをする。

* ルックアップにlog_2(n)のコストがかかっている。
  * 効率よくデータのTravarsalができなをもたないので、graphがどれだけ大きくなろうがある頂点から近傍のインデックスのみをい。

* GraphDBではどうしているか?
  * Indexを持たずに、NodeとEdgeの接続情報だけで進んでいく。
  * Graphの増大に対しても、検索コストはほぼコンスタンスである。
    * 自分自身にミニインデックスを持っている、という方が効率が良くなる。

* こういった特徴をindex free adjencyと呼び、このような特徴を持っているものをGraphDBと呼ぶ


* Q: 1回のTravarsalなら確かにコストは少ないが、グラフ全体に対して辿るようなTravarsalについてはコストはどうか?
  * まだまだ評価できていないので、答えづらい。あまり扱われないのではないか。

* RDBMSやDocumentDBも、Graphであらわすことができる。


* 例:レコメンドの評価が行列演算ベースではなく、Graphを使って表現できる。

* Q: 関係性に、重みをつけることは可能か?
  * A: propertyとして付与することが可能。

* Q: InsertやUpdateのような操作はどうなるのか?
  * A: それをやる場合は、外部のIndex経由で探していくしかない。


An Introduction Neo4j
---------------------

* ライセンス
  * 有償のものもある。好き勝手にできるもの、というわけでもない。
    * community(free , Advanced(SNMP & JMX, Enterprise(high load & HA
  * neotechnology スウェーデンの会社。
    * GraphDBはヨーロッパで盛ん

* Java製。エンタープライズを意識している。
* indexにはluceneを使っている。

* トランザクションをサポート
* しっかりした耐久性。
* Java

* コードサンプル。
* 追加
  * Pathクラス
  * トランザクションブロック内で実行。
  * Nodeの追加を行った後、Relationを追加する。
* Travarsal
  * Travarserクラス
  * 検索方法やリレーションの種類と深さなどを検索できる。
  * relationshipを複数設定するなども。

* Index
  * nodeとrelationshipに対してindexを張ることができる
    * luceneを使っている。
  * 各種propertyに対してもindexをつけることあできる。
  * Full text Searchも可能。Propertyの値に対して検索できる。


### Cypher

* Graph向けのDSL。
  * SQLライクに記述が可能

* 取ってきたデータに対して計算をすることが可能

* リリースされてからまだ数カ月

### Other Features

* 有償版のみ

* High Availability
  * Master Slave構成が取れる

* Backup
  * オンラインバックアップが可能


An Introduction to Thinkerpop
-----------------------------

* GraphDBを統一的に扱うインターフェース・ツールを提供するオープンソース・プロジェクト
  * ベンダーロックインを防ぐ

* 2009年にgremlinを発表
  * vendor側も好意的に対応

### 各プロダクト

### Blueprints

* GraphDBに共通なAPIを提供する、JDBCドライバのGraph版
* 各プロジェクトのベースになるもの。

### ThinkerGraph

* ライトウェイトなインメモリのGraphDB

### reXster

* RestFulなGraphのアクセスができる。
* Tomcatベース
* WebインターフェースとしてDog Houseというツールも提供してくれる。

### Gremlin

* consoleから操作できるコマンドインターフェース
  * Vertex、Edgeをたどる

* Graphをたどっていくような指定を、ステップごとに書いていく
  * filterという方法もある。
  * loopメソッドを使って繰返しを行っていくことが可能。

### pipes

* Gremlinのドットでつないでいくことによって入力から出力を得るフレームワークを提供している。

* transform
* filter
* sideEffect

* 独自に柔軟なpipeを定義してtravarseを行うこともできる。

### Summary

* Neo4j, OrientDB, RDFなどにも対応。
* 有志がHBaseやRedisにも対応している。


Enjoy Graph DB
--------------

* ネイティブドライバで直接接続するのは、心中する覚悟が必要。
* DB固有のHTTPインターフェスは心中する覚悟が必要。
* ThinkerPop/Gremlinを経由
  * Java/Groovyなのでパワーが必要

* Rexster経由
  * かなり距離があるので、パフォーマンスが悪い

* ネイティブドライバ以外、ほぼ情報がない
* 見渡す限りいばらの道

* pythonにはbulbflowというツールがある。
  * 使い方の紹介