MySQLに、ネットワーク構造を格納する方法

題名の通りなのですが、MySQLに、ネットワーク構造（この言い方が正しいかどうか、わかりませんが…）を、
格納する方法を考えていますが、なかなか良い案が、見つかりません。

ネットワーク構造と書いたのは、WEBのサーバ同士がつながっているような感じで、
一つの丸から、複数の線が出ていて、その線で、他の丸と接続していて、
線の数、丸の数も、固定数ではなく、複数の線が出ていて、複数の丸と接続している丸もあれば、
一つの線しか出ていなくて、一つの丸とだけ接続しているものもある。
と書けばイメージ、伝わるでしょうか？

この、お互いの接続関係をDBに格納し、一つの丸を指定すると、それに接続されている丸を、
すべて見つけてこれるようにしたいということです。
丸の数、線の数に上限がない（と言っても計算負荷などから考えて常識的な数にはしますが）ので、
丸が追加されると、接続関係も、増えていきます。
ですが、接続が、全く増えない丸も、中にはあります。
こんな、構造を、どんな風にDBで表現したら、良いのか、悩んでいます。
わかりにくい説明で、申し訳ないのですが、調べてみても、
良い方法を見つけられなかったので、もしも、良い案がありましたら、
ご教授頂けると幸いです。

行動規範の内容に同意します

回答3件

こんにちは。

たぶん、それはグラフのことと思います。
グラフをコンピュータ内で表現する方法はたくさんあります。

データベースで表現できる方法としてパッと思いつくものは、ノード＝レコードとして各レコードの可変長フィールドで他のレコードのユニークなキーを記録することです。
これで有向グラフ（ノードからノードへ矢印でリンクする）を表現できます。
そして、効率は良くないですが必ず逆方向のリンクも用意すれば無向グラフにできます。

投稿2017/02/16 13:14

Chironian

総合スコア23272

zodiac

2017/02/16 13:51

お返事、ありがとうございます。イメージ、伝わって良かったです。私の作りたいものは、グラフと言うのですね。不勉強で、お恥ずかしい限りです。ノードを、レコードとして、そのノードにつながっているノードを、全て、そのレコードに記録していくという形ですね。ノードの数が増えたら、レコードを増やせばいいので、それは楽ですよね。 MySQLも、初心者なので、間違っていたら、ご指摘いただきたいのですが、ノードのキーが、例えば通し番号として、その数字を文字列にして、カンマ区切りとかで、可変長フィールドに、書いていくという感じの実装になるでしょうかね？　それで、処理する時は、カンマで、splitして、つながっているノードを得るという方法かなと思いました。わかりやすい、方法かなと思いましたので、検討してみます。ありがとうございます。

Chironian

2017/02/16 14:02

考え方はその通りです。可変長配列のようなものがMySQLにあればもっと効率良くできると思いますが、すいません。データベースを使い込んだ経験がなく詳しいことは分かりません。

zodiac

2017/02/16 14:06

いえいえ、ありがとうございます。これで、よくわかりましたので、大丈夫です。可変長の配列とか、あったら、きっとすごく便利ですよね。

行動規範の内容に同意します

全部の丸に一意の通し番号を振り、

SQL
1CREATE TABLE edge (
2  from INTEGER, // 線の入り口の丸#
3  to INTEGER // 線の出口の丸#
4)

で、いかがでしょ?

投稿2017/02/16 13:02

episteme

総合スコア16614

zodiac

2017/02/16 13:56

お返事、ありがとうございます。これは、丸の情報ではなく、接続情報をレコードに持つということですね。この場合だと、fromに目的の丸が書いてあるレコードを探して、そのtoの値を取ってくれば、その丸とつながっている全ての丸を得られるということですよね？こういう方法も思いつかなかったです。検討してみます。ありがとうございます。

episteme

2017/02/16 14:06 編集

ですね。SELECT to FROM graph WHERE graph.from=3 で3番からの接続先が得られます。方向を持たないのであれば (x,y) と (y,x) の両方をテーブルに突っ込んでおけば。

zodiac

2017/02/16 14:11

SQL文も書いてくださって、本当に、丁寧なご回答をありがとうございます。方向を持たない、接続関係のデータですので、両方を入れておく必要があるのですね。それも、書いていただいていなければ、きっと忘れていたと思います。感謝します。

episteme

2017/02/16 23:41

薀蓄垂れるなら、こいつはグラフ理論で扱う隣接行列のCOO-format(Coodinate-format)って呼ばれる疎行列(sparse matrix)の表現形式です。

zodiac

2017/02/21 12:09

お返事、遅くなりました。すみません。これは、そういうものなのですね。こうして、キーワードが、わかるだけでも、調べる取っ掛かりができるので、本当に助かります。ありがとうございます。