InfoQ ホームページアーティクルグラフデータベース、NOSQL、Neo4j

グラフデータベース、NOSQL、Neo4j

ブックマーク

2010年6月15日読了時間 38 分

作者：

Peter Neubauer

翻訳者

笹井崇司

原文(投稿日：2010/05/12)へのリンク

はじめに

データモデルにはいろいろあるが、80年代以降、主流になっているのはリレーショナルモデルだ。このモデルにはOracle、MySQL、MSSQLなどの実装があり、RDBMS（リレーショナルデータベース管理システム: Relational Database Management System）と呼ばれることもある。しかし最近になって、リレーショナルデータベースを使うことで問題が起こるケースが増えている。リレーショナルモデルによるデータモデリングには弱点と問題があり、複数サーバに及ぶ水平方向のスケーラビリティと膨大なデータの扱いに制約があるためだ。これらの問題の要因には、世界中のソフトウェアコミュニティが注目している2つのトレンドがある。

ユーザ、システム、センサーによって生み出されるデータの指数的な増加。Amazon、Google、その他クラウドサービスなどの巨大な分散システムにデータが集中することによって、この傾向にはさらに拍車がかかっている。
データの相互依存と複雑さの増大。インターネット、Web2.0、ソーシャルネットワーク、そして、データソースに対する多様なシステムからのオープンで標準化されたアクセスによって、この傾向に拍車がかかっている。

こうしたトレンドに対処するにあたって、リレーショナルデータベースには深刻な問題がある。そこで特定の領域をターゲットとした様々な技術が開発されており、従来のRDBMSとともに、あるいはその代わりとして使われている。こうした状況は多言語パーシステンス（Polyglot Persistence）と呼ばれている。代替となるデータベースと言っても全く新規のものではない。オブジェクト指向データベース（OODBMS）、階層データベース（例えば、LDAP）など、これまでも様々な形で存在していたものだ。しかし、ここ数年、数々のプロジェクトが新しく始まっており、それらはいずれもNOSQLデータベースと呼ばれている。

この記事では、NOSQLというムーブメントにおけるグラフデータベースの位置付けについて、その概要を説明する。また後半では、Javaベースのグラフデータベース、Neo4jについて紹介する。

NOSQL-環境

NOSQL（Not Only SQL）は実際には、永続化ソリューションにおける非常に大きなカテゴリのひとつであり、リレーショナルデータモデルではなく、クエリ言語としてSQLを使っていないものを指している。

簡単に言うと、NOSQLデータベースはそのデータモデルによって4つのカテゴリに分類できる。

キー/バリューストア（Key-Value-stores）
BigTable実装
ドキュメントストア（Document-stores）
グラフデータベース（Graph Databases）

VoldemortやTokyo Cabinetといったキー/バリューシステムにおけるモデリングの最小単位はキー/バリューペアになる。そして、BigTableやそのクローンでは可変数の属性をもつタプルに、CouchDBやMongoDBといったドキュメントデータベースではドキュメントになる。これに対しグラフデータベースでは、データセット全体をひとつの巨大な高密度ネットワーク構造としてモデル化する。

ここではNOSQLデータベースにおける2つの興味深いポイント、スケーラビリティと複雑さについて詳しく説明する。

1. スケーラビリティ

CAP: ACID 対 BASE

従来のデータベースシステムのほとんどは、トランザクションに基づいてデータの完全性を保証する。トランザクションを使うことで、データ管理のあらゆる状況において、データの一貫性を確保している。こうしたトランザクションの性質は、ACID（Atomicity, Consistency, Isolation, Durability: アトミック性、一貫性、独立性、永続性）として知られている。しかし、ACIDに準拠したシステムをスケールアウトしようとすると問題が発生する。分散システムにおける高可用性に関して、様々なところで競合が発生するためだ。この問題はまだ十分解決されておらず、CAP定理として知られている。

強い一貫性（Consistency）: データセットが更新されても、すべてのクライアントが同一バージョンのデータを見ていること。例えば、2フェーズコミットプロトコル（XAトランザクション）、ACIDにより実現される。
高い可用性（Availability）: クラスタにあるマシンのいくつかがダウンしても、常にすべてのクライアントが要求したデータの少なくとも1コピーを見つけられること。
分割耐性（Partition-tolerance）: たとえ異なるサーバにデプロイされても、クライアントにとって透過的に、システム全体がその特性を維持すること。

CAP定理は「これらスケールアウトの3つの側面のうち、同時に2つまでしか十分実現できない」と主張する。

巨大な分散システムでうまく機能するために、それぞれのCAP特性について詳しく研究されてきた。

NOSQLデータベースの多くは、特に一貫性の要件を緩和することで、すぐれた可用性と分割耐性を実現している。こうして作られたシステムは、BASE（Basically Available, Soft-state, Eventually consistent）として知られている。これらのシステムでは従来の意味でのトランザクションをもたず、（Dynamoシステムなどのような）すぐれた分割スキーマを可能にするためデータモデルに制約を課している。CAP、ACID、BASEに関するもっと幅広い解説がこちらにある（日本語訳）。

2. 複雑さ

タンパク質ホルモンネットワーク、提供: Alex Adai氏、テキサス大学細胞・分子生物学研究所

データとシステムの相互接続性が増すにつれ、ドメイン非依存な単純明快な方法ではスケール、自動共有できないような高密度なデータセットが増えてきている。Todd Hoff氏ですらそう述べている。Visual Complexityにあるような巨大で複雑なデータセットの可視化はなおさらだ。

リレーショナルモデル

リレーショナルデータモデルを時代遅れなものとして片付ける前に、リレーショナルデータベースシステムが成功したひとつの理由は、E.F. Codd氏によるリレーショナルデータモデルの正規化のおかげだということを見落してはいけない。理論上、どんなデータ構造であっても、正規化によって冗長性や情報欠損なくモデル化することができる。そして、モデリングした後は、SQLを使った非常に強力な方法でデータを挿入、修正、問い合わせすることができる。また、OLTP、OLAP、Webアプリケーション、レポーティングなどの各種ユースケースに合わせて、挿入スピードや多次元クエリに最適化したスキーマ（例えば、スタースキーマ）を実装しているRDBMSもある。

理論上はそうだ。しかし現実には、RDBMSは先ほど述べたCAP問題の制約にぶつかる。多数のテーブルの結合を必要とするような「深い」SQLクエリは、実装に起因するパフォーマンス上の問題がある。スケーラビリティ、長期のスキーマ評価、木構造のモデリング、半構造化データ、階層やネットワークなど、他にも様々な問題を抱えている。

また、リレーショナルモデルはオブジェクト指向や動的言語といった最近のソフトウェア開発のアプローチにあまりマッチしていない。これはオブジェクトとリレーショナルのインピーダンス・ミスマッチとして知られている。この領域ではJavaのHibernateのようなORM層が開発され、さまざまな結果が得られている。確かに、こうしたものを使うとオブジェクトモデルをリレーショナルデータモデルに簡単にマッピングできるが、最適なクエリパフォーマンスが実現できるわけではない。特に、半構造化データの場合には、ほとんどの行が空のカラムを多数含んだ巨大なテーブル（疎なテーブル）としてモデル化されてしまうことが多い。これはパフォーマンスに悪影響を与えることになる。こうする代わりに多数のテーブルの結合としてモデル化しても、依然として問題がある。RDBMSにおいて、結合は非常にパフォーマンスコストのかかる集合操作であるためだ。

リレーショナル正規化の代わりとしてのグラフ

ドメインモデルをデータ構造に投影するのには、大きく2つの流派がある。ひとつはRDBMSに使われるようなリレーショナルなやり方で、もうひとつはSemantic Webに使われるようなグラフやネットワーク構造を使うやり方だ。

理論上、グラフ構造はRDBMSでも正規化することはできる。しかし、ファイルツリーのような再帰的構造やソーシャルグラフのようなネットワーク構造の場合、リレーショナルデータベースの実装特性のためクエリパフォーマンスはひどいものになるだろう。ネットワーク上のリレーションに対する操作はすべて、RDBMSにおける「結合」操作となり、2つのテーブルの主キーによる集合操作として実装されることになる。こうした操作は遅く、テーブルのタプル数が増えるとスケールできなくなるのだ。

ラベル付きプロパティグラフの基本用語

グラフ分野における用語について、まだ一般的なコンセンサスはできていない。グラフモデルには数多くの種類があるためだ。しかし、様々なグラフ実装の多くをまとめた、プロパティグラフモデル（Property Graph Model）を作ろうという取り組みがある。これによると、プロパティグラフの情報は3つの基本構成要素を使ってモデル化される。

ノード（node）（別名頂点）
リレーションシップ（relationship）（別名エッジ）- 方向とタイプを有する（ラベル付きで有向）
プロパティ（property）（別名属性）- ノードとリレーションシップにおける属性

具体的に言えば、モデルはラベル付きで有向の属性付き多重グラフになる。ラベル付きグラフは各エッジにラベルをもち、それがエッジのタイプとして使われる。有向グラフなので、末尾や起点ノードから先頭もしくは終点ノードへと、エッジに一定の向きがある。属性付きグラフなので、各ノードとエッジには属性の可変リストがある。属性は名前に関連した値であり、グラフ構造を単純化する。多重グラフなので、2つのノード間には複数のエッジが許される。つまり、2つのノードは別のエッジといくつでもつなげられる。2つのエッジが同一の末尾、先頭、ラベルであっても構わない。

図は小さなラベル付きプロパティグラフを示している。

TinkerPopに関連する人の小さなグラフ

グラフ理論は、様々な分野における数々の問題に関連があり、非常に有用であることがわかっている。よく利用されるグラフ理論アルゴリズムには、最短経路計算や測地経路、PageRank、固有ベクトル中心性（eigenvector centrality）、closeness、betweenness、HITSといった中心性など、様々な種類がある。しかし実際のところ、製品レベルのハイパフォーマンスなグラフデータベース実装はまだなく、こうしたアルゴリズム応用のほとんどは研究レベルに限られている。だが幸運なことに、ここ数年で状況はかなり変わってきた。24時間動作する製品を想定して、複数のプロジェクトが進行中だ。

Neo4j - オープンソース、Java、プロパティグラフモデル
AllegroGraph - クローズドソース、RDF-QuadStore
Sones - クローズドソース、.NETにフォーカス
Virtuoso - クローズドソース、RDFにフォーカス
HyergraphDB - オープンソース、Java、HyperGraphモデル
その他、InfoGrid、Filament、FlockDBなど

次の図は、複雑さとスケーラビリティに関して、代表的なNOSQLのポジションを示している。

「サイズに対するスケーリングと複雑さに対するスケーリング」について、詳しくはEmil Eifrem氏のブログ記事を参照。

Neo4j - Javaベースのグラフデータベース

Neo4jは、Javaで書かれたACIDトランザクションに完全準拠したグラフデータベースだ。データはグラフネットワークに最適なデータ構造でディスクに格納される。Neo4jカーネルは極めて高速なグラフエンジンであり、リカバリ - 2フェーズコミットトランザクション、XA準拠といった、製品データベースに期待されるあらゆる特性を備えている。Neo4jは2003年より24時間動作可能な製品となっている。そして、プロジェクトは安定性とコミュニティテスティングに関する大きなマイルストーンとなるversion 1.0をリリースしたところだ。オンラインバックアップとマスタースレーブリプリケーションによる高可用性はまだベータ段階だが、次のリリースロードマップに挙がっている。Neo4jは管理オーバーヘッド不要の組み込みデータベースとしても利用できるし、PHP、.NET、JavaScriptベースの環境に簡単に統合可能な、数多くのRESTインターフェイスを備えたスタンドアロンサーバとしても利用できる。ただし本記事では、Neo4jを直接利用する場合のみを想定する。

開発者はグラフモデルに対してJava-APIを使って直接作業することになる。このAPIは非常に柔軟なデータ構造を公開している。また、JRuby/Ruby、Scala、Python、Clojureといった言語向けに、コミュニティによるすぐれたバインディングも存在する。一般的に、Neo4jには以下のようなデータ特性がある。

簡単なスキーマ変更や遅延データマイグレーションのためのデータ構造はオプション、もしくは存在しない。
本来なら複雑なデータセットを簡単にモデリングできる。例えば、きめ細かなアクセスコントロールリストとしてのCMSのアクセスコントロールのモデリング、ユースケースのようなオブジェクトデータベース、TripleStores、などいろいろ。
次のような分野でよくあるユースケース。Semantic WebおよびRDF、LinkedData、GIS、ゲノム解析, ソーシャルネットワークデータのモデリング、賢い推薦アルゴリズムなどいろいろ。

「従来の」RDBMSアプリケーションのなかにも、グラフで処理した方が望ましい困難なデータセットがたくさん含まれていることが多い。例えば、フォルダ構造、プロダクト構成、プロダクト組立およびカテゴリ、メディアメタデータ、金融部門におけるセマンティックトレーディング（semantic trading）および不正検知などだ。

Neo4jはカーネルを中心に、数多くのオプションコンポーネントがある。特に、メタモデル、SAIL- およびSparQL準拠RDF TripleStore実装や、数々のよく知られたグラフアルゴリズム実装によるグラフ構築をサポートしている。

Neo4jを別のサーバで動かしたい場合には、RESTラッパーを利用することができる。これはLAMPスタックを使って構築されたアーキテクチャに適している。RESTを使えば、memcached、e-tag、ApacheベースのキャッシュおよびWeb層によって、読み込み負荷を簡単に大幅にスケールできるようになる。

ハイパフォーマンス

パフォーマンスベンチマークとして明確な数値を示すのは難しい。内部のハードウェア、使用するデータセット、その他の要因にかなり依存するためだ。サイズに関して、Neo4jは特別なことをしなくても、数十億のノード、リレーションシップ、プロパティをもつグラフを処理できる。通常、読み込みパフォーマンスは、ミリ秒当たり2000リレーションシップのトラバーサル（フルトランザクション、ウォームキャッシュあり、スレッド毎）（1秒当たり1-2百万トラバーサルステップ）になる。最短経路計算において、2000ノードの小さなグラフでさえ、Neo4jはMySQLよりも1000倍高速だ。この差はグラフのサイズが大きくなればさらに大きくなる。

理由はNeo4jの中にある。グラフ全体のサイズに依存することなく、グラフのトラバーサルは一定の速度で実行される。RDBMSにおける結合演算のようなパフォーマンスを低下させる集合演算は必要ないためだ。Neo4jはグラフを遅延してトラバースする。結果のイテレータに要求されて初めて、ノードとリレーションがトラバースされて返される。これによって、大きな深いトラバーサルのパフォーマンスが向上する。

書き込みスピードはファイルシステムとハードウェアのシーク時間にかなり依存する。Ext3ファイルシステムとSSDディスクはよい組み合わせで、トランザクションの書き込みスピードは1秒当たり約100,000オペレーションになる。

例 - 『マトリックス』

グラフ

先ほど述べたように、ソーシャルネットワークはグラフデータベースの応用のほんの一例にすぎないが、これは理解しやすいだろう。Neo4jの基本機能を説明するため、以下にEclipse RCPベースのNeo4jのためのNeoclipseを使って可視化した、映画『マトリックス』から作った小さなグラフを示す。

便宜上、既知の開始点からネットワークのパスを見つけるために、グラフは既知のリファレンスノード（id=0）につながっている。これは必ずしも必要ではないが、実際のところ非常に便利だ。

Javaによる実装は次のようになる。

フォルダ "target/neo" に新しいグラフデータベースを作る

EmbeddedGraphDatabase graphdb = new EmbeddedGraphDatabase("target/neo");

Relationship タイプをその場で作ることができる。

RelationshipType KNOWS = DynamicRelationshipType.withName("KNOWS");

あるいは、タイプセーフJava Enumを使うこともできる。

enum Relationships implements RelationshipType { KNOWS, INLOVE, HAS_CODED, MATRIX }

それではノードを2つ作って、各ノードに"name"プロパティを追加しよう。次に、これらをKNOWSリレーションシップでつなげよう。

Node neo = graphdb.createNode();
node.setProperty("name", "Neo");
Node morpheus = graphdb.createNode();
morpheus.setProperty("name", "Morpheus");
neo.createRelationshipTo(morpheus, KNOWS);

グラフを修正したり、データの分離レベルを必要とするオペレーションは、すべてトランザクションでラップする。こうすることで、特別なことをしなくてもロールバックやリカバリが機能する。

Transaction tx = graphdb.beginTx();
try {
	Node neo = graphdb.createNode();
	...
	tx.success();
} catch (Exception e) {
	tx.failure();
} finally {
	tx.finish();
}

『マトリックス』のグラフを作る全コードは以下のようになる。

graphdb = new EmbeddedGraphDatabase("target/neo4j");
index = new LuceneIndexService(graphdb);
Transaction tx = graphdb.beginTx();
try {
	Node root = graphdb.getReferenceNode();
	// グラフへのエントリーポイントを得るため、Neoをルートノードにつなげる。
	// これは必ずしも必要ではないが便利だ。
	neo = createAndConnectNode("Neo", root, MATRIX);
	Node morpheus = createAndConnectNode("Morpheus", neo, KNOWS);
	Node cypher = createAndConnectNode("Cypher", morpheus, KNOWS);
	Node trinity = createAndConnectNode("Trinity", morpheus, KNOWS);
	Node agentSmith = createAndConnectNode("Agent Smith", cypher, KNOWS);
	architect = createAndConnectNode("The Architect", agentSmith, HAS_CODED);
	// TrinityはNeoを愛している。でも彼は知らない。
	trinity.createRelationshipTo(neo, LOVES);
	tx.success();
} catch (Exception e) {
	tx.failure();
} finally {
	tx.finish();
}

ノードとリレーションシップを作るメンバ関数。

private Node createAndConnectNode(String name, Node otherNode,
RelationshipType relationshipType) {
    Node node = graphdb.createNode();
    node.setProperty("name", name);
    node.createRelationshipTo(otherNode, relationshipType);
    index.index(node, "name", name);
    return node;
}

Neoの友達は誰？

Neo4jのAPIには、簡単なクエリに答えるためのJava-Collections指向のメソッドがたくさんある。次のように、ノード"Neo"のリレーションシップを調べて友達を見つけることができる。

for (Relationship rel : neo.getRelationships(KNOWS)) {
    Node friend = rel.getOtherNode(neo);
    System.out.println(friend.getProperty("name"));
}

これは唯一の友達として"Morpheus"を返す。

しかし、Neo4jの真のパワーはTraverser-APIを利用したときに発揮される。これを使えば、もっと複雑なトラバーサルやフィルターが記述できる。これは停止状態を評価するためのStopEvaluatorと、結果にノードが含まれているか評価するためのReturnableEvaluatorとを含むTraverserという形になる。また、トラバースするリレーションシップのタイプと向きも指定できる。TraverserはJavaのIteratorインターフェイスを実装しており、例えば for{...} ループで要求したときに初めて、ノードを遅延ロードしてグラフを走査する。よく使われるEvaluatorsとDefaultsはあらかじめ組み込まれている。

Traverser friends = neo.traverse(Order.BREADTH_FIRST,
StopEvaluator.DEPTH_ONE,
ReturnableEvaluator.ALL_BUT_START_NODE, KNOWS, Direction.BOTH);
for (Node friend : friends) {
    System.out.println(friend.getProperty("name"));
}

まず開始ノードから始めて、深いレベルにあるノードをたどる前に、同じ深さにあるすべてのノードをたどり（Order.BREADTH_FIRST）、深さ1にあるノードをたどったら停止して（StopEvaluator.DEPTH_ONE）、開始ノード（"Neo"）以外のすべてのノードを返すようにする（ReturnableEvaluator.ALL_BUT_START_NODE）。ここでは双方向（Direction.BOTH）でタイプがKNOWSのリレーションシップだけをトラバースする。この場合も、Neoの直接の唯一の友達としてMorpheusを返す。

友達の友達は？

Neoの友達の友達が誰かを調べるためには、Neoから始めてKNOWSを2ステップの深さまでたどる必要がある。これはTrinityとCypherを返す。プログラム上は、Traverserが深さ2までたどるよう、StopEvaluatorを調整すればよい。

StopEvaluator twoSteps = new StopEvaluator() {
    @Override
    public boolean isStopNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

カスタムのReturnableEvaluatorも深さ2にあるノードだけを返すようにする。

ReturnableEvaluator nodesAtDepthTwo = new ReturnableEvaluator() {
    @Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

友達の友達のTraverserは次のようになる。

Traverser friendsOfFriends = neo.traverse(Order.BREADTH_FIRST,

    twoSteps, nodesAtDepthTwo, KNOWS, Direction.BOTH);
for (Node friend : friendsOfFriends) {
    System.out.println(friend.getProperty("name"));
}

これは結果としてCypherとTrinityを返す。

誰が恋しているか？

もうひとつ興味深い質問は、例えばArchitectから始めて、このグラフで恋をしている人がいるかというものだ。

今度は、Architectから始まるすべてのリレーションを調査して（彼のノードIDは既知だがその先にさらにノードがあるとする）、外向きのLOVEのリレーションシップのあるノードを返さなくてはならない。カスタムのReturnableEvaluatorは次のようになるだろう。

ReturnableEvaluator findLove = new ReturnableEvaluator() {
@Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.currentNode().hasRelationship(LOVES, Direction.OUTGOING);
    }
};

すべてのリレーションシップをトラバースするには、グラフ全体のすべてのリレーションシップのタイプが必要になる。

List<Object> types = new ArrayList<Object>();
// グラフ全体のリレーションシップのタイプをすべて考慮する必要がある。
// （双方向で）
for(RelationshipType type : graphdb.getRelationshipTypes()) {
    types.add(type);
    types.add(Direction.BOTH);
}
// 開始!
Traverser inLove = architect.traverse(Order.BREADTH_FIRST,
StopEvaluator.END_OF_GRAPH, findLove, types.toArray());
for (Node lover : inLove) {
    System.out.println(lover.getProperty("name"));
}

これは唯一のノードとしてTrinityを返す。外向きのLOVEのリレーションシップのあるノードだけを返すようにしたためだ。

グラフのインデックス付け

リレーションシップのトラバース操作はNeo4jのスイートスポットのひとつだが、グラフ全体に及ぶ集合に対する機能も必要になることが多い。よくある例として、すべてのノードのプロパティの全文検索がある。Neo4jでは外部のインデックスシステムを使うことにより、車輪の再発明を避けている。よくあるテキスト検索のために、Neo4jはLuceneとSolrとの密接な連携を提供する。これにより、Lucene/Solrのセマンティックスを使って、任意のノードのプロパティをインデックス化することができる。

『マトリックス』の例では、次のようにして"name"プロパティをインデックス化できる。

GraphDatabaseService graphDb = // GraphDatabaseServiceのインスタンス

IndexService index = new LuceneIndexService( graphDb );

// 新しいノードを作り、"name"プロパティをインデックス化する
Node neo = graphDb.createNode();
neo.setProperty( "name", "Neo" );
index.index( neo, "name", neo.getProperty( "name" ) );

// "name=Neo"の最初のノードを検索する
Node node = index.getSingleNode( "name", "Neo" );

この例では、Luceneを使ってグラフに対する外部インデックスを作った。しかし、Neo4jには高速なグラフエンジンがあるため、グラフ自体にインデックス構造を構築することによって、特定のデータセットやドメイン向けにトラバーサルパターンを短縮するといった多様な戦略をとることもできる。例えば、一次元データのためのtimelineやB-Trees、（空間GISコミュニティでよく見られる）2次元データをインデックス化するRTreesやQuadTreesなど、他にもいろいろある。よく見かける便利なパターンとして、重要なサブグラフを直接ルートノードにつなぐことによって、重要な開始ノードをショートカットするという方法もある。

Javaなんて最低、もっと簡潔なのはないの？

さらにグラフ構造を簡単に扱えるよう、Neo4jには数多くのすぐれた言語バインディングがある。次の例では、すばらしいNeo4j-JRuby-bindingsを使ってみよう。これを使うと全体のコード量をかなり削減できる。

まず、neo4j gemをインストールする。

>gem install neo4j

『マトリックス』のグラフ全体とこれまで説明したクエリを実現するJRubyコードは、次のようになる。

require "rubygems"

require "neo4j"

class Person
  include Neo4j::NodeMixin

  # ノードのプロパティ
  property :name


  # リレーションシップのタイプ
  has_n :friends

  # プロパティのための Lucene インデックス
  index :name
end


# プレイヤ

neo       = Person.new :name => 'Neo'
morpheus  = Person.new :name => 'Morpheus'
trinity   = Person.new :name => 'Trinity'
cypher    = Person.new :name => 'Cypher'
smith     = Person.new :name => 'Agent Smith'
architect = Person.new :name => 'Architect'

# コネクション

cypher.friends << morpheus
cypher.friends << smith
neo.friends << morpheus
morpheus.friends << trinity
trinity.rels.outgoing(:loves) << neo

architect.rels.outgoing(:has_coded) << smith


# Neoの友達

neo.friends.each { |n| puts n }


# Neoの友達の友達

neo.friends.depth(2).each { |n| puts n }


# 誰が恋しているか？
architect.traverse.both(:friends, :has_coded, :loves).depth(:all).filter do
  outgoing(:loves).to_a.size > 0
end.each do |n|
 puts 'In love: ' + n.name
end

グラフプログラミング言語 - Gremlin

最近になるまで、グラフやグラフに関連したプロジェクトを広範囲にカバーできるようなクエリ言語は存在しなかった。Semantic Web/RDFのドメインには、SPARQLというSQLから着想を得たクエリ言語がある。この言語はトリプルにマッチさせるのに使うサンプルグラフの記述にフォーカスしている。しかし、この記事の『マトリックス』の例やその他ドメイン固有のデータセットのデータモデリングの場合、RDF互換ではない別のアプローチ、あるいは、もっと実用的なアプローチをとるグラフもたくさんある。Freebaseのためのクエリ言語MQLのように、JSON指向の言語もある。だが、こうした言語は自ら定義したデータモデルにおいてのみ機能する。現在の巨大なグラフに必要とされる深いグラフアルゴリズムやヒューリスティックな分析手法に対しては、何も提供しないか、ほんのわずかなサポートしかない。

様々なデータモデル（RDFも含む）でもっと複雑で興味深いクエリを実現するために、XPath指向でチューリング完全なグラフプログラミング言語、Gremlinがある。これはTinkerPopチームによって開発され、Marko A. Rodriguezを中心に推進されている。プロパティグラフモデル（Property Graph Model）の説明によると、従来のモデルのほとんどのスーパセットであり最小公分母になっているそうだ。さらに、他のグラフフレームワークとの接続や（例えば、JUNGを使うGremlin）異なるグラフ実装によるグラフトラバーサル表現も可能になっている。インメモリのTinkerGraphのようなシンプルなものから、AllegroGraph、Sesame、TinkerPop LinkedData SAIL（もともとJosh Shinavier氏によりRippleプログラミング言語用に開発された）のためのRDF-SAIL-adapterを介したものまで、Neo4jにつながるいくつかの実装がある。

Gremlinの構文はXPathに基づいており、グラフ全体にわたる深いパス記述も簡単に表現できる。簡単なケースであれば、通常のXPathとほとんど同じように見えるだろう。

Gremlinをインストールするか、オンラインで試してみよう。『マトリックス』のグラフのGremlinセッションは次のようになるだろう。

peterneubauer$ ~/code/gremlin/gremlin.sh


         \,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin> #open a new neo4j graph as the default graph ($_g)
gremlin> $_g := neo4j:open('tmp/matrix')
==>neo4jgraph[tmp/matrix]
gremlin> #the vertices
gremlin> $neo := g:add-v(g:map('name','Neo'))
==>v[1]
gremlin> $morpheus := g:add-v(g:map('name','Morpheus'))
==>v[2]
gremlin> $trinity := g:add-v(g:map('name','Trinity'))
==>v[3]
gremlin> $cypher := g:add-v(g:map('name','Cypher'))
==>v[4]
gremlin> $smith := g:add-v(g:map('name','Agent Smith'))
==>v[5]
gremlin> $architect := g:add-v(g:map('name','The Architect'))
==>v[6]
gremlin> #the edges
gremlin> g:list($cypher,$neo,$trinity)[g:add-e($morpheus,'KNOWS',.)]
==>v[4]
==>v[1]
==>v[3]
gremlin> g:add-e($cypher,'KNOWS',$smith)
==>e[3][4-KNOWS->5]
gremlin> g:add-e($trinity,'LOVES',$neo)
==>e[4][3-LOVES->1]
gremlin> g:add-e($architect,'HAS_CODED',$smith)
==>e[5][6-HAS_CODED->5]
gremlin> #go to Neo as the current root ($_) via a full-text index search
gremlin> $_ := g:key('name','Neo')
==>v[1]
gremlin> #is this Neo?
gremlin> ./@name
==>Neo
gremlin> #what links to here and from here?
gremlin> ./bothE
==>e[0][1-KNOWS->2]
==>e[4][3-LOVES->1]
gremlin> #only take the KNOWS-edges
gremlin> ./bothE[@label='KNOWS']
==>e[0][1-KNOWS->2]
gremlin> #Neo's friend's names
gremlin> ./bothE[@label='KNOWS']/inV/@name
==>Morpheus
gremlin>
gremlin> #Neo's Friends of friends, 2 steps
gremlin> repeat 2
               $_ := ./outE[@label='KNOWS']/inV
           end
==>v[4]
==>v[3]
gremlin> #What are their names?
gremlin> ./@name
==>Cypher
==>Trinity
gremlin> #every node in the whole graph with an outgoing LOVES edge
gremlin> $_g/V/outE[@label='LOVES']/../@name
==>Trinity

深いグラフアルゴリズム - リレーションシップの値

『マトリックス』の例は、Gremlinのパワーを示す非常に素朴な使い方だった。もっと興味深い使い方は、巨大なグラフにおけるアルゴリズムの開発とテストだろう。固有ベクトル中心性（Eigenvector Centrality）やダイクストラ（Dijkstra）のような網羅的なアルゴリズムは、このような巨大なグラフにはスケールしない。ネットワーク上のすべての頂点に触れなければならないためだ。このような問題には、文法に基づくランダムウォーク（Grammar Based Random Walkers）や拡張活性（Spreading Activation）（Marko Rodriguez氏による詳しい説明）のようなヒューリスティックなアプローチの方が適している。GoogleのPageRankアルゴリズムもヒューリスティックなアプローチのひとつであり、Gremlinを使うと次のようなコードにモデル化できる。（こちらから読み込んだGreatful Deadの楽曲、コンサート、アルバムのグラフ例。2500回のループとそのたびに15%のエネルギー損失）

$_g := tg:open()

g:load('data/graph-example-2.xml')

$m := g:map()

$_ := g:key('type', 'song')[g:rand-nat()]

repeat 2500

  $_ := ./outE[@label='followed_by'][g:rand-nat()]/inV

  if count($_) > 0

    g:op-value('+',$m,$_[1]/@name, 1.0)

  end

  if g:rand-real() > 0.85 or count($_) = 0

    $_ := g:key('type', 'song')[g:rand-nat()]

  end

end

g:sort($m,'value',true())

次のような重み付きの楽曲リストが返ってくる。

==>DRUMS=44.0
==>PLAYING IN THE BAND=38.0
==>ME AND MY UNCLE=32.0
==>TRUCKING=31.0
==>CUMBERLAND BLUES=29.0
==>PROMISED LAND=29.0
==>THE MUSIC NEVER STOPPED=29.0
==>CASSIDY=26.0
==>DARK STAR=26.0
==>NOT FADE AWAY=26.0
==>CHINA CAT SUNFLOWER=25.0
==>JACK STRAW=25.0
==>TOUCH OF GREY=24.0
==>BEAT IT ON DOWN THE LINE=23.0
==>BERTHA=23.0

インターネット上のLinkedDataグラフを基本とする別の興味深い例としては、LinkedDataとDBPediaにおける音楽のための推薦アルゴリズムがある。

おわりに

RDBMSやその他の永続化ソリューションと同じように、グラフはあらゆる問題に効く銀の弾丸ではない。いちばん重要なのはデータであり、扱うべきクエリの種類と操作構造、スケーラビリティとCAPに関してどんな要件が存在するかだ。

NOSQLデータベースがハイスケーラビリティであることを唯一の根拠にして、非リレーショナルソリューションを利用するのは望ましくないことが多い。Neo4jと現在のハードウェアを使うと、ほとんどの場合、ドメインモデル全体が単一インスタンスの無数のドメインオブジェクトに保持されてクエリされることになる。

もしこれでは不十分だとしても、常にドメイン最適なシャーディングの考えを取り入れられる可能性がある。必ずしもドキュメントやキー/バリューシステムのようなハードなデータモデリング制約を取り入れる必要はない。最終的に、ドキュメントモデルになるのか、ドメイン固有の「オブジェクトデータベース」になるのか、あるいはそれ以外のものになるのかは、ドメインのコンテキストとアプリケーションシナリオに依存する。

この記事で紹介したコードはここにある。

最後に、すばらしいフィードバックと有益な助言をくれたMichael Hunger氏とMarko Rodriguez氏に感謝する。

著者について

Peter Neubauer氏はNeo Technology社のCOOであり、Neo4j、Gremlin、LinkedProcess、OPS4J、Qi4jといった数多くのJavaおよびグラフベースのオープンソースプロジェクトの共同創始者だ。peter@neotechnology.comで彼とコンタクトできる。

Login with:

アカウントをお持ちでない方