1. HOME
  2. ブログ
  3. テクノロジー
  4. Neo4j
  5. グラフデータベースとは何か

BLOG

ブログ

Neo4j

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

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

グラフDBとは

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

このグラフ検索を可能にしている土台が、「グラフ理論」がある。
18世紀初めにプロイセン王国のケーニヒスベルグ(現ロシア連邦)に流れるプローゲル川には、プレーゲル川中州を挟んで7つの橋があり、当時の人たちが「どこか1つの場所から7つの橋を1度ずつ全部わたって、元の場所に帰ってこられるか」という問題を議論していたそうです。数学者のオイラー(Lonhard Euler)は、地点と橋を点と線(ノードとエッジ)の図形に単純化し、「この図形は一筆書きで書くことができない」ので、その課題は無理であることを数学的に証明して見せた。これがグラフ理論の始まりと言われている

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

グラフDBはなぜ早いのか

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

RDBとグラフDBのデータ表現の違い

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

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

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

関連記事