グラフデータベース

グラフデータベース( GDB )は、ノード、エッジ、プロパティを使用してセマンティッククエリにグラフ構造を使用してデータを表し、保存するデータベースです。 ^[1]このシステムの重要な概念はグラフ(またはエッジまたは関係) です。グラフは、ストア内のデータ項目をノードとエッジのコレクションに関連付けます。エッジはノード間の関係を表します。関係により、ストア内のデータを直接リンクでき、多くの場合、1 回の操作で取得できます。グラフデータベースは、データ間の関係を優先します。関係はデータベースに永続的に保存されるため、クエリは高速です。関係はグラフデータベースを使用して直感的に視覚化できるため、相互接続が密集したデータに役立ちます。^[2]

グラフデータベースは、一般的にNoSQLデータベースと呼ばれます。グラフデータベースは、一般的なグラフを表現するという点で1970年代のネットワークモデルデータベースに似ていますが、ネットワークモデルデータベースは抽象化のレベルが低く^[3]、エッジのチェーンを簡単にトラバーサルすることができません。 ^[4]

グラフデータベースの基盤となるストレージメカニズムはさまざまです。関係はグラフデータベースの第一級オブジェクトであり、ラベル付け、方向付け、およびプロパティの指定が可能です。一部はリレーショナルエンジンに依存し、グラフデータをテーブルに格納します(ただし、テーブルは論理要素であるため、このアプローチではグラフデータベース管理システムと物理ストレージデバイスの間に抽象化のレベルが課せられます)。その他のものは、キーと値のストアまたはドキュメント指向のデータベースをストレージとして使用し、本質的に NoSQL 構造になっています。

2021年現在^{[アップデート]}、リレーショナルデータベースに対するSQLのように広く採用されているグラフクエリ言語はなく、多種多様なシステムがあり、その多くは1つの製品に密接に結びついています。初期の標準化の取り組みにより、Gremlin、SPARQL、Cypherなどのマルチベンダークエリ言語が生まれました。2019年9月、新しい標準グラフクエリ言語（ISO/IEC 39075情報技術—データベース言語—GQL）を作成するプロジェクトの提案が、ISO/IEC合同技術委員会1（ISO/IEC JTC 1）のメンバーによって承認されました。GQLは、SQLのような宣言型データベースクエリ言語となることを目的としています。クエリ言語インターフェースに加えて、一部のグラフデータベースにはアプリケーションプログラミングインターフェース（API）を介してアクセスします。

グラフデータベースはグラフ計算エンジンとは異なります。グラフデータベースは、リレーショナルオンライントランザクション処理（OLTP）データベースを翻訳した技術です。一方、グラフ計算エンジンは、バルク分析のためのオンライン分析処理（OLAP）で使用されます。 ^{[5]グラフデータベースは、大手テクノロジー企業が独自のグラフデータベースを使用して成功したことと、}^[6]オープンソースのグラフデータベースの導入により、2000年代に大きな注目を集めました。

ある研究では、RDBMSはグラフクエリを実行する際のパフォーマンスにおいて既存のグラフ分析エンジンと「同等」であると結論付けられました。^[7]

歴史

1960年代半ばには、IBMのIMSなどのナビゲーションデータベースは階層モデルでツリーのような構造をサポートしていましたが、厳密なツリー構造は仮想レコードによって回避できました。^[8]^[9]

グラフ構造は、1960 年代後半からネットワークモデルデータベースで表現できるようになりました。1959年にCOBOL を定義したCODASYLは、1969 年にネットワークデータベース言語を定義しました。

ラベル付きグラフは、1980年代半ばから論理データモデルなどのグラフデータベースで表現されるようになりました。^[10]^[11]

商用オブジェクトデータベース(ODBMS) は 1990 年代初頭に登場しました。2000 年に、Object Data Management Group は、 ODMG'93 出版物で、オブジェクトと関係 (グラフ) 構造を定義するための標準言語を公開しました。

1990 年代初頭にはグラフデータベースに対するいくつかの改良が登場し、1990 年代後半には Web ページのインデックス作成の取り組みによりその進歩は加速しました。

2000 年代半ばから後半にかけて、Neo4jやOracle Spatial and Graphなど、ACID保証を備えた商用グラフデータベースが利用可能になりました。

2010年代には、水平方向に拡張可能な商用ACIDグラフデータベースが利用可能になりました。さらに、SAP HANAはグラフデータベースにインメモリおよび列指向技術をもたらしました。^[12]また、2010年代には、OrientDB、ArangoDB、MarkLogic （バージョン7.0以降）など、グラフモデル（およびリレーショナルデータベースやドキュメント指向データベースなどの他のモデル）をサポートするマルチモデルデータベースが利用可能になりました。この間、ソーシャルメディア企業の出現により、さまざまな種類のグラフデータベースがソーシャルネットワーク分析で特に人気になりました。また、この10年間で、Amazon NeptuneやNeo4j AuraDBなどのクラウドベースのグラフデータベースが利用可能になりました。

背景

グラフデータベースは、データを概念的に表現します。これは、データをノードに、その関係をエッジに転送することによって実現されます。

グラフデータベースは、グラフ理論に基づいたデータベースです。ノードまたはエッジであるオブジェクトのセットで構成されます。

ノードは、人、企業、アカウント、または追跡されるその他の項目などのエンティティまたはインスタンスを表します。これらは、リレーショナルデータベースのレコード、リレーション、または行、またはドキュメントストアデータベースのドキュメントとほぼ同等です。
エッジは、グラフまたは関係とも呼ばれ、ノードを他のノードに接続する線であり、それらの関係を表します。ノード、プロパティ、エッジの接続と相互接続を調べると、意味のあるパターンが浮かび上がります。エッジは有向または無向のいずれかです。無向グラフでは、2 つのノードを接続するエッジは 1 つの意味を持ちます。有向グラフでは、2 つの異なるノードを接続するエッジは、方向に応じて異なる意味を持ちます。エッジはグラフデータベースの重要な概念であり、リレーショナルモデルやドキュメントストアモデルでは直接実装されない抽象化を表します。
プロパティはノードに関連付けられた情報です。たとえば、Wikipedia がノードの 1 つである場合、Wikipediaのどの側面が特定のデータベースに関連しているかに応じて、Web サイト、参考資料、文字 w で始まる単語などのプロパティに関連付けられる可能性があります。

グラフモデル

ラベル付きプロパティグラフ

ラベル付きプロパティグラフモデルは、ノード、関係、プロパティ、ラベルのセットで表されます。データのノードとその関係は両方とも名前が付けられ、キーと値のペアで表されるプロパティを格納できます。ノードにはラベルを付けてグループ化できます。関係を表すエッジには2つの特性があります。常に開始ノードと終了ノードを持ち、有向です。^[13]グラフは有向グラフになります。関係にはプロパティもあります。これは、ノードの関係に追加のメタデータとセマンティクスを提供するのに役立ちます。^[14]関係を直接格納すると、定数時間のトラバーサルが可能になります。^[15]

リソース記述フレームワーク (RDF)

RDFグラフモデルでは、情報の追加はそれぞれ別のノードで表されます。たとえば、グラフ内で別個のノードとして表される人物の名前プロパティをユーザーが追加する必要があるシナリオを想像してください。ラベル付きプロパティグラフモデルでは、これは人物のノードに名前プロパティを追加することで行われます。ただし、RDF では、ユーザーはと呼ばれる別のノードを追加して、hasNameそれを元の人物ノードに接続する必要があります。具体的には、RDF グラフモデルはノードとアークで構成されます。RDF グラフ表記またはステートメントは、主語のノード、目的語のノード、述語のアークによって表されます。ノードは空白のままにすることも、リテラルにすることも、URIで識別することもできます。アークも URI で識別できます。ノードのリテラルには、プレーン (型なし) と型付きの 2 つのタイプがあります。プレーンリテラルには、語彙形式とオプションで言語タグがあります。型付きリテラルは、特定のデータ型を識別する URI を持つ文字列で構成されます。データにURIがない場合、空白ノードはデータの状態を正確に示すために使用されることがあります。^[16]

プロパティ

グラフデータベースは、グラフのようなクエリを実行するための強力なツールです。たとえば、グラフ内の 2 つのノード間の最短パスを計算します。その他のグラフのようなクエリは、グラフデータベース上で自然な方法で実行できます (たとえば、グラフの直径の計算やコミュニティの検出など)。

グラフは柔軟性があり、ユーザーはアプリケーションの機能を損なうことなく、既存のグラフに新しいデータを挿入できます。データベースの設計者は、データベースの将来の使用例について詳細に計画する必要はありません。

ストレージ

グラフデータベースの基盤となるストレージメカニズムはさまざまです。リレーショナルエンジンに依存し、グラフデータをテーブルに「保存」するものもあります(ただし、テーブルは論理要素であるため、このアプローチでは、グラフデータベース、グラフデータベース管理システム、およびデータが実際に保存される物理デバイスの間に別のレベルの抽象化が課されます)。その他のデータベースでは、キーと値のストアまたはドキュメント指向のデータベースをストレージに使用し、本質的にNoSQL構造になっています。ノードは他のドキュメントストアと同じように表現されますが、2 つの異なるノードをリンクするエッジは、そのドキュメント内に _from 属性と _to 属性という特別な属性を保持します。

インデックスフリー隣接

データ検索のパフォーマンスは、ある特定のノードから別のノードへのアクセス速度に依存します。インデックスフリーの隣接性により、ノードは直接の物理RAMアドレスを持ち、他の隣接ノードを物理的にポイントするように強制されるため、検索が高速になります。インデックスフリーの隣接性を備えたネイティブグラフシステムでは、ノード間のリンクを見つけるために他の種類のデータ構造を移動する必要がありません。グラフ内の直接関連するノードは、ノードの 1 つが取得されるとキャッシュに格納されるため、ユーザーが最初にノードを取得するときよりもデータ検索が高速になります。ただし、このような利点には代償があります。インデックスフリーの隣接性により、グラフトラバーサルを使用しないクエリの効率が犠牲になります。ネイティブグラフデータベースは、格納されたデータに対する CRUD操作を処理するためにインデックスフリーの隣接性を使用します。

アプリケーション

データの種類によって複数のグラフのカテゴリが認識されています。ガートナーは、グラフの5つの大まかなカテゴリを提案しています。^[17]

ソーシャルグラフ：これは人々のつながりに関するもので、例としてはFacebook、Twitter 、 6次の隔たりの考え方などがあります。
意図グラフ: 推論と動機を扱います。
消費グラフ: 「支払いグラフ」とも呼ばれる消費グラフは、小売業界で頻繁に使用されます。Amazon、eBay、Walmart などの電子商取引企業は、消費グラフを使用して個々の顧客の消費を追跡します。
興味グラフ: これは個人の興味をマッピングするもので、多くの場合、ソーシャルグラフによって補完されます。Web ページをインデックスするのではなく、興味に基づいて Web をマッピングすることで、Web 編成の以前の革命に従う可能性があります。
モバイルグラフ: これはモバイルデータから構築されます。将来のモバイルデータには、Web、アプリケーション、デジタルウォレット、GPS、モノのインターネット(IoT) デバイスからのデータが含まれる可能性があります。

リレーショナルデータベースとの比較

エドガー・F・コッドが1970年にリレーショナルモデルについて発表して以来、^[18] リレーショナルデータベースは大規模データストレージシステムの事実上の業界標準となっています。リレーショナルモデルでは、データを多数のテーブルに分割し、データベース内の重複データを削除する厳格なスキーマとデータ正規化が必要です。データの一貫性を維持し、ACIDトランザクションをサポートするために、データは正規化されます。しかし、これにより関係を照会する方法に制限が課せられます。

リレーショナルモデルの設計動機の1つは、行ごとの高速アクセスを実現することでした。^[18]格納されたデータ間で複雑な関係を形成する必要があるときに問題が発生します。関係はリレーショナルモデルで分析できますが、複数のテーブルにわたる多くの異なる属性に対して多くの結合操作を実行する複雑なクエリが必要です。リレーショナルモデルを使用する場合、関係を取得するときに外部キー制約も考慮する必要があり、追加のオーバーヘッドが発生します。

グラフデータベースは、リレーショナルデータベースと比較して、連想データセットの処理速度が速いことが多く^{[引用が必要] 、}オブジェクト指向アプリケーションの構造により直接的にマッピングされます。グラフデータベースは、通常、コストがかかる結合操作を必要としないため、大規模なデータセットに自然に拡張できます^{[引用が必要]}。グラフデータベースは、厳格なスキーマへの依存度が低いため、進化するスキーマを使用してアドホックで変化するデータを管理するのに適しているとされています。

逆に、リレーショナルデータベース管理システムは、通常、大量のデータ要素に対して同じ操作を実行する方が高速であり、データの自然な構造での操作が可能です。グラフデータベースはリレーショナルデータベースよりも優れており、最近人気が高まっていますが^{、グラフモデル自体が既存のリレーショナルデータベースを置き換える唯一の理由ではないことが推奨されます。パフォーマンスが桁違いに向上し、レイテンシが低減するという}証拠があれば、グラフデータベースが重要になる場合があります。^[19]

例

リレーショナルモデルは、データ内の情報を使用してデータをまとめて収集します。たとえば、電話番号に市外局番「311」が含まれるすべての「ユーザー」を検索するとします。これは、選択したデータストアまたはテーブルを検索し、選択した電話番号フィールドで文字列「311」を探すことによって行われます。これは大きなテーブルでは時間のかかるプロセスになる可能性があるため、リレーショナルデータベースではインデックスを提供しています。インデックスを使用すると、選択したデータとレコードの一意のキー(または主キー) のみを含む小さなサブテーブルにデータを保存できます。電話番号にインデックスが付けられている場合は、同じ検索が小さなインデックステーブルで行われ、一致するレコードのキーが収集され、次にそれらのキーを持つレコードがメインデータテーブルで検索されます。通常、テーブルはキーによる検索が非常に高速になるように保存されます。^[20]

リレーショナルデータベースには、レコード間の固定された関係という概念は本質的にuserpk含まれていません。代わりに、あるレコードの一意のキーを別のレコードのデータに格納することで、関連するデータが互いにリンクされます。たとえば、ユーザーの電子メールアドレスを含むテーブルには、関連付けられているユーザーレコードの主キーuserpkを含むというデータ項目が含まれている場合があります。ユーザーと電子メールアドレスをリンクするために、システムはまず、選択したユーザーレコードの主キーを検索し、電子メールテーブル (または、それらのインデックス) の列でそれらのキーを探し、電子メールデータを抽出し、次にユーザーレコードと電子メールレコードをリンクして、選択したすべてのデータを含む複合レコードを作成します。結合と呼ばれるこの操作は、計算コストが高くなる可能性があります。クエリの複雑さ、結合の数、およびさまざまなキーのインデックスによっては、システムは複数のテーブルとインデックスを検索し、すべてを並べ替えて一致させる必要がある場合があります。^[20]

対照的に、グラフデータベースはレコード間の関係を直接保存します。userpk列内のユーザーのキーを検索して電子メールアドレスを見つける代わりに、ユーザーレコードには電子メールアドレスレコードを直接参照するポインターが含まれています。つまり、ユーザーを選択すると、ポインターをたどって電子メールレコードに直接移動できるため、一致するレコードを見つけるために電子メールテーブルを検索する必要はありません。これにより、コストのかかる結合操作が不要になります。たとえば、市外局番「311」のユーザーのすべての電子メールアドレスを検索する場合、エンジンは最初に従来の検索を実行して「311」のユーザーを見つけますが、次にそれらのレコードで見つかったリンクをたどって電子メールアドレスを取得します。リレーショナルデータベースは、最初に「311」のすべてのユーザーを見つけ、主キーのリストを抽出し、それらの主キーを持つ電子メールテーブル内のレコードをもう一度検索して、一致するレコードをリンクします。これらの一般的な操作の場合、グラフデータベースは理論的にはより高速です。^[20]

グラフアプローチの真の価値は、1 レベル以上の深さの検索を実行するときに明らかになります。たとえば、"311" の市外局番に "subscribers" (ユーザーを他のユーザーにリンクするテーブル) を持つユーザーを検索する場合を考えてみましょう。この場合、リレーショナルデータベースは、まず "311" の市外局番を持つすべてのユーザーを検索し、次にそれらのユーザーのいずれかを subscribers テーブルで検索し、最後に一致するユーザーを取得するために users テーブルを検索する必要があります。対照的に、グラフデータベースは "311" のすべてのユーザーを検索し、次にsubscriber 関係を通じてバックリンクをたどってsubscriber ユーザーを見つけます。これにより、複数の検索、ルックアップ、および出力を作成するために必要な複数のレコードからの一時データをすべて保持するためのメモリ使用量が回避されます。ビッグO 表記法で言えば、このクエリは時間、つまりデータサイズの対数に比例します。対照的に、リレーショナルバージョンでは、複数のルックアップと、すべてのデータレコードを結合するために必要な時間が必要になります。^[20] $O(\log n)+O(1)$ $O(\log n)$ $O(n)$

グラフ検索の相対的な利点は、クエリの複雑さとともに増大します。たとえば、「潜水艦に関する映画で、その映画に出演した俳優が、風と共に去りぬで主役を演じた別の俳優と一緒に出演していた」ことを知りたい場合があります。これには、まずシステムが風と共に去りぬの俳優を見つけ、彼らが出演したすべての映画を見つけ、それらのすべての映画で風と共に去りぬで主役を演じなかったすべての俳優を見つけ、次に彼らが出演したすべての映画を見つけ、最後にそのリストを「潜水艦」を含む説明を持つ俳優に絞り込む必要があります。リレーショナルデータベースでは、映画と俳優のテーブルを個別に複数回検索し、潜水艦の映画で別の検索を行い、それらの映画に出演したすべての俳優を見つけ、次に収集された (大量の) 結果を比較する必要があります。対照的に、グラフデータベースは風と共に去りぬからクラークゲーブルまでたどり、彼が出演した映画へのリンクを収集し、それらの映画から他の俳優へのリンクを収集し、それらの俳優から映画のリストに戻るリンクをたどります。結果の映画リストは「潜水艦」で検索できます。これらすべてを1回の検索で実行できます。^[21]

プロパティは、この構造にもう 1 つの抽象化レイヤーを追加し、多くの一般的なクエリも改善します。プロパティは基本的に、任意のレコード、または場合によってはエッジにも適用できるラベルです。たとえば、Clark Gable に「俳優」というラベルを付けると、システムは、監督やカメラマンではなく、俳優であるすべてのレコードをすばやく見つけることができます。エッジにラベルを付けることができる場合は、「風と共に去りぬ」と Clark Gable の関係に「主演」というラベルを付け、映画「風と共に去りぬ」の「主演」「俳優」である人物を検索すると、データベースはVivien Leigh、Olivia de Havilland、Clark Gable を生成します。同等の SQL クエリは、人物と映画をリンクするテーブル内の追加データに依存する必要があり、クエリ構文がさらに複雑になります。これらの種類のラベルは、特定の状況で検索パフォーマンスを向上させる可能性がありますが、一般的には、エンドユーザーにセマンティックデータを追加する場合に便利です。^[21]

リレーショナルデータベースは、データ間の関係が 1 レベルまたは 2 レベルの深さしかないフラットなデータレイアウトに非常に適しています。たとえば、会計データベースでは、特定の顧客のすべての請求書のすべての明細項目を検索する必要があり、これは 3 つの結合クエリです。グラフデータベースは、より多くのリンクを含むデータセットを対象としています。特に、 "友達" 関係が本質的に無制限であるソーシャルネットワーキングシステムに適しています。これらの特性により、グラフデータベースは、オンラインシステムやビッグデータ環境でますます一般的になっている検索の種類に自然に適しています。このため、グラフデータベースは、Facebook、Google、Twitterなどの大規模なオンラインシステムや、レコード間の深いリンクを持つ同様のシステムで非常に人気が高まっています。

さらに詳しく説明すると、および列peopleを持つテーブルとおよびを持つテーブル (テーブルからの外部キーである) の 2 つのテーブルを持つリレーショナルモデルを想像してください。この場合、ジャックの友達全員を検索すると、次の SQL クエリが実行されます。 person_idperson_namefriendfriend_idperson_idpeople

SELECT p2 . person_name FROM people p1 JOIN friend ON ( p1 . person_id = friend . person_id ) JOIN people p2 ON ( p2 . person_id = friend . friend_id ) WHERE p1 . person_name = 'Jack' ;

同じクエリは次のように翻訳できます。

グラフデータベースクエリ言語 Cypher

MATCH ( p1 : person { name : 'Jack' }) -[ : FRIEND_WITH ]- ( p2 : person ) RETURN p2 . name

SPARQL は、 W3Cによって標準化され、複数の RDFトリプルおよびクアッドストアで使用されるRDF グラフデータベースクエリ言語です。

長い形式

プレフィックス foaf :  <http://xmlns.com/foaf/0.1/>

SELECT  ?name 
WHERE  {  ?s  a           foaf : Person  .  
        ?s  foaf : name   "Jack"  .  
        ? s  foaf : ?o を知っている . ?o foaf : name ?name . }

短縮形

プレフィックス foaf :  <http://xmlns.com/foaf/0.1/>

SELECT  ?name 
WHERE  {  ?s  foaf : name      "Jack"  ; 
           foaf : ?oを知っています    。?o foaf : name ?name . }

SPASQL は、 SQL をSPARQLで拡張したハイブリッドデータベースクエリ言語です。

SELECT  people . name 
FROM  ( 
       SPARQL  PREFIX  foaf :  <http://xmlns.com/foaf/0.1/> 
              SELECT  ?name 
              WHERE  {  ?s  foaf : name   "Jack"  ;  
                         foaf :知っている ?o  . 
                      ?o  foaf : name   ?name  . 
                    } 
    )  AS  people  ;

上記の例は、基本的な関係クエリの簡単な説明です。これらは、データの総量に応じて増加するリレーショナルモデルのクエリの複雑さの概念を凝縮したものです。これに対して、グラフデータベースクエリでは、関係グラフを簡単に並べ替えて結果を表示できます。

また、グラフデータベースの単純で凝縮された宣言的なクエリは、リレーショナルデータベースと比較して必ずしも優れたパフォーマンスを提供しないことを示す結果もあります。グラフデータベースはデータの直感的な表現を提供しますが、リレーショナルデータベースはセット操作が必要な場合に優れた結果を提供します。^[15]