#グラフ・ハイパーグラフというのは三項関係の特殊なケースなので，三項関係を表現するコンテナがあればグラフ・ハイパーグラフをまとめて表現できるような妄想を受信しているのですが，それってリレーショナルのコンパクト版になるのかしらん・・・・・
#三項を表す形式は，(1 2 . 3)という表現があり，カラム名はcar cadr cddrとなるようなリレーショナル構造で，それを格納したり操作するコンテナ。そういうのがあればグラフ(ハイパーグラフ)を処理しやすいのかしらとかと。（受信
##(元ネタは根基の集合がグラフを表現しうるという話だったのですが，根基の集合を三項関係とみなすようなインターフェースみたいな感じ。三項関係を効率よく表現できれば結構いろんな事象を表現できそうな気がしてます。中間報告のようなものなのです。ではでは)
#RDF で使われる「トリプル」を連想しました。 まさにこれじゃないですかね。
##主語・述語・目的語という抽象は汎用性が高いですね。
#制限された prolog って感じ？
#をお，RDFにそういうものが。ご教示ありがとうございます。わたしの受信してる電波はもっとゆるくて，たとえば関数は (f f(x) . x)のように表すと，不動点は(f x . x)なんですよね。
#中間を新たな三項の端につないでいけば，複雑な構造は表せるという。基本的な三項として (x xy . y)というのがあって，ただ組み合わせると言う感じ。
#で，そういう構造自体を格納するコンテナはリレーショナルのコンパクト版になるのかしらんということでした。
#根基を，そのコンテナの表現で表すと，整数の話とグラフの話が結びつくのではないかという電波でした。
#(三項自体に型がないとうまくいかないような気がするので，そのへんが煮詰まらない。)
#yamasushiさんが具体的に考えていることはわからないですが、グラフと三項関係についてなら、まさしく三項関係はグラフデータベースの基本要素になっています。AllegroGraphとか、中身はRDFトリプルの配列+高速インデクシングです。
#ハイパーグラフについては直接は表現できない気がしますが、「ハイパーグラフのエッジ」に対して無名ノードを割り当てるのが素直な表現かなあ。述語の方をエッジユニークにする (同じ述語を持つ目的語同士はつながってるとみなす)とかでもいいか。
#一応、subject-predicate-objectの3カラムのでっかいテーブル、とみなせばRDBに入るけど、それは「どんなプログラムも文字の配列」と言ってるようなものでレイヤ違いの感じが。データが表現する構造については関係演算のモデルにモデルには収まらないので、「リレーショナルのコンパクト版」が何を指してるのかよくわからないです。
#なるほど。レイヤ違いのようです。「「どんなプログラムも文字の配列」と言ってるようなもの」で，三項というのは構造を表す「文字」に相当するのではないかということです。文字列型があればどんな型も表現できるように，「RDFトリプルの配列+高速インデクシング」というようなものがあれば，いろんな構造が表せるのかしら？ みたいな。
#ハイパーグラフの無名ノードのくだりは良くわからないですのでわたしの考えなどを整理してみる：普通のグラフを表せる構造というのはエッジからノードの組みへのマップですが，これは(k s . e)の集合として見ることができる。ここでkは重複がないというわけです。このkが重複しないという条件を緩めるとハイパーグラフになるような。残る制約は「エッジはノードにならない，ノードはエッジにならない」です。この制約を緩めるとさらにいろんな構造が表せるような感じ。
#「kは重複が無い」という制約はいらないというか、あったらむしろ困りませんか。通常のトリプルでの制約は「s, p, o全てが一致するトリプルはない」だけです。
#kが重複すると, { (k s_1 . e_1) , (k s_2 . e_2) } が許されるので,これに組合せの残りを追加すれば，向き付きハイパーグラフが表現できます。始点と終点を組合せをすべて記憶するのは効率が悪いので，なにか正規表現のようなもの？で記憶するみたいな。
#正規表現で言うところの[abcd]k[efgh]が向き付きハイパーグラフのハイパーエッジ。
#そして，特殊シンボル∅を導入すれば，向き無しハイパーグラフになるということです。始点を空にするか，終点を空にするかの２種類があります。
#ああ、何を主語に、何を目的語にするかを定義しないと話が混乱しますね。上で無名ノード云々といっているのは、「エッジ」を主語に、「ノード」を目的語に、「エッジがノードを持っている(ノードがエッジに所属している」を述語に、と考えています。「無名ノード」と言った時のノードはRDFのノードで、前の文の「ノード」は対象とするハイパーグラフのノードです。混乱するし、エッジに名前をつけるなら無名である必要はないので、無名云々は忘れてください。ハイパーエッジeにノードX,Y,Zが所属するのは
#e <has> X.
e <has> Y.
e <has> Z.
#等と書けます。
#それは，向き無しハイパーグラフですね。向き無しハイパーグラフというのは集合と同じですからhasで記述できるわけです。
#向きありで「始点ノード」を主語に、「終点ノード」を述語に、「始点から終点」を<connects-to>という述語にすることももちろんできます。
#「終点ノード」を目的語に、でした。
#それだと，エッジのシンボルはどうなるんです？
#あ、<connects-to>だと普通のグラフになっちゃうか。
#エッジを述語にするんですね。そしたら有向ハイパーグラフ。
#もしrdfグラフデータベースに興味があるなら、AllegroGraphとGruffをダウンロードして遊んでみたらいかかでしょう。一定容量まではフリーで使えたはず。
#あ、GruffはAllegroGraphのヴィジュアライゼーションツールです。AllegroGraphはトリプルストアで、トリプルを保存して検索ができます。
#おお，ありがとうございます。yEdでごそごそと書いていたのですが，ハイパーグラフを直接扱えないので不便だなーと思っていました。
Gauche > Archives > 2014/09/06