グラフデータ構造をリレーショナルデータベースにマップするのは意味がありますか？

Question

特にMultigraphです。

一部の同僚がこれを示唆しており、私は完全に戸惑いました。

これについての洞察はありますか？

Answer 1

グラフはデータベースに格納するのが簡単です。ノード用のテーブルとエッジ用のテーブルがあり、ノードテーブルとそのノード間の多対多の関係テーブルとして機能します。このように：

create table node (
    id integer primary key 
); 

create table edge (
    start_id integer references node, 
    end_id integer references node, 
    primary key (start_id, end_id) 
); 

ただし、グラフをこのように保存することについては、いくつかの点があります。

最初に、このスキームのエッジは自然に指示されます。開始と終了は区別されます。あなたのエッジが無向であれば、クエリを書くことに注意しなければならないか、各エッジのテーブルに2つのエントリをどちらかの方向に格納しなければなりません。単一のエッジを保存する場合は、格納されているフォームを正規化することをお勧めします。最も低いIDのノードを開始と見なす（これを強制するためにチェック制約をテーブルに追加する）。エッジをノードを参照するのではなく、それらの間に結合テーブルを置くことによって真に順序付けられていない表現を持つことができますが、それは私には素晴らしいアイデアのようには見えません。

第2に、上記のスキーマはマルチグラフを表す方法がありません。そうするためには簡単に拡張することができます。与えられたノードのペアの間のエッジが見分けがたい場合、最も簡単なことは、各エッジの行にカウントを追加し、参照されるノードの間にいくつのエッジがあるかを指定することです。それらが区別できる場合は、ノード表に何かを追加して区別できるようにする必要があります。自動生成されたエッジIDは最も簡単な方法です。

しかし、ストレージをソートしても、グラフを扱うのに問題があります。メモリ内のオブジェクトに対するすべての処理を実行したいだけで、データベースはまったくストレージ用のものであれば問題ありません。しかし、データベースのグラフでクエリを実行する場合は、SQLでの実行方法を把握しておく必要があります。これは、グラフのサポートがなく、基本的な操作がグラフを使って作業する。再帰的なSQLサポート（PostgreSQL、Firebird、独自のデータベースのいくつか）を持つデータベースを持っている場合は、特に問題はありません。あなたがこれをしたいのであれば、私の提案は特定のクエリに関するさらなる質問を投稿することです。

Answer 2

情報はどこかに保存する必要があります。リレーショナルデータベースは悪い考えではありません。

多対多の関係、ノードのリストの表、およびエッジ/接続のリストの表です。

Answer 3

Facebookがソーシャルグラフをデータベースに実装する方法を検討します。彼らは人々のためのテーブルと友情のための別のテーブルを持っているかもしれません。 Friendshipsテーブルには少なくとも2つの列があり、それぞれがテーブルの外部キーです。

フレンドシップは（Facebook上で）対称的なので、最初の外部キーのIDが常に2番目の外部キーのIDより小さくなるようにすることができます。 Twitterはソーシャルネットワーク向けの有向グラフを持っているので、そのような正規表現は使用しません。

Answer 4

これは問題ありません。その情報をどのように操作するかを検討する必要があります。おそらく、このタイプのデータが意味する種類のグラフに関連する計算を行うには、データベースとは別の言語が必要になります。 Skiena's Algorithm Design Manualには、広範なセクショングラフのデータ構造とその操作があります。

実行するクエリの種類を考慮せずに、verticesとedgesという2つのテーブルから始めます。頂点はシンプルで、識別子と名前です。マルチグラフの場合、エッジは複雑です。エッジは、2つの頂点（すなわち、外部キー）およびいくつかの追加情報の組み合わせによって一意に識別されるべきである。追加情報は、あなたが解決している問題に依存しています。たとえば、フライト情報、出発時刻と到着時刻、および航空会社の場合。さらに、エッジが方向付けられているかどうか（つまり一方向）を決定し、その情報も追跡する必要があります。

計算によっては、何らかの人工知能/機械学習アルゴリズムでうまく解決されない問題が発生することがあります。例えば、最適な飛行。本書Programming Collective Intelligenceには、この目的に役立つアルゴリズムがいくつかあります。しかし、データが保存されている場所では、アルゴリズム自体は変更されません。