グラフデータベースとは何か

グラフデータベースの仕組みと優位性

多くの人たちがSNSや乗換案内のようなアプリを利用している。
これらのアプリは、膨大なデータで、かつ様々な関係性を持っている
データから構成されているのは、誰の目にも明らかだろう。
実際、この膨大なデータからどのようにして、検索を起点にした関連情報を芋づる式に、
しかも即座に取り出しているのだろうか。疑問に思わないだろうか。
その背景には、グラフデータベース（以下、グラフDB)や、それに類した考え方がある。

グラフDBとは

グラフDBとは、一言で言えば、グラフ構造を備えたデータベースのことである。データの構造が、従来のリレーショナルではなく、ネットワーク状になっている場合、更新・検索の面で威力発揮する。グラフは「ノード」「エッジ」「プロパティ」の３要素によってノード間の「関係性」を表現できる。ここでいう「グラフ」とは、Excelの折れ線グラフ（＝チャート）等ではなく、ネットワーク状のデータ表現のことをいう。
グラフDBでは、一般的にノード(node)と呼ばれる１件のデータ(RDMの１レコードに相当）と、
そのデータ間を結ぶエッジ(edge)と呼ばれる一方通行の向きがあり（有向グラフ）があり、
その属性情報はプロパティ(property)という形で保持されている。

グラフ理論の起源

このグラフ検索を可能にしている土台が、「グラフ理論」がある。
18世紀初めにプロイセン王国のケーニヒスベルグ(現ロシア連邦）に流れるプローゲル川には、

中州を挟んで7つの橋があり、当時の人たちが「どこか1つの場所から7つの橋を1度ずつ全部わたって、元の場所に帰ってこられるか」という問題を議論していたとされる。数学者のオイラー（Lonhard Euler）は、地点と橋を点と線（ノードとエッジ）の図形に単純化し、「この図形は一筆書きで書くことができない」ので、その課題は無理であることを数学的に証明して見せた。これがグラフ理論の始まりと言われている

グラフ検索のアルゴリズム

代表的なグラフ検索のアルゴリズムとしては、ツリー構造のグラフで目的の情報を探す
「幅優先検索」や「深さ優先検索」、重み付けされたエッジを加味して最短経路検索を行う
ダイクストラ法やA*法などがある。要は点と線を結んだネットワークなので、
地下鉄の路線図、SNSの人と投稿記事の関係性、脳神経系、塩基配列、
インターネットなども広い意味ではグラフとみなせる。
このことからグラフ構造は、私たちにとって身近なものと言えるだろう。

グラフDBはなぜ早いのか

グラフDBは、つながりのあるデータを可視化する表現力があるのはわかる。
しかし検索が速い、SNSのような大規模なデータからの検索が効率的なのは、
どのような仕組みによるのだろうか。
我々がよく知るリレーショナルデータベース（以下、RDB）と比べてみよう。
グラフDBでは、テーブル単位ではなく個々のデータ単位で「つながり」が保持される。
RDBでは外部キー（インデックス）を使ってエンティティー（ノード）を2次的につなぐのに対し、
グラフDBのモデルではエンティティー間のリレーションが明示的に組み込まれている。
RDBはインデックスの参照やテーブルを連結したビューの用意で時間がかかるのに対し、
グラフDBはノードがもつ隣接ノードの情報をたどるだけなので、回答が速い。
ネットワークの規模が巨大になるほど、膨大な数のノードのネットワークから目的を探索する際に、
パフォーマンスを落とさずに結果を返すことができ、ビッグデータ時代に活躍する可能性がある。

次の図は、SNS内で友達の友達を最大５段階の深さまで見つける検証の結果である。
それぞれが約50人の友達をもつ100万人規模のSNSでは、効率の差が如実に現れる。
深さ3（友達の友達の友達）になると、RDBでは実用的な時間でクエリーに
対処できないのは誰の目に見ても明らかである。

グラフDBの限界

一方、グラフDBはデータ全体からの統計情報を分析する手続きなどは苦手で、そもそもデータ構造が「つながり」をもたない表だけであれば、グラフDBで処理するメリットは乏しい。
どんなケースでもRDBに置き換わるわけではない。ちなみにグラフDBは、非リレーショナルデータベースを意味するNoSQLデータベースの1つに分類されることもある。