2005年12月16日 作成 有向 グラフ （ハッセ 図） >> 目次 （テーマ ごと）
2010年 1月16日 補遺 　


　
　まず、以下の 3つの概念を確認しておきます。

　　（1） 反射律　∀ a ∈ A に対して、aRa が成り立つ。
　　（2） 対称律　∀ a, b ∈ A に対して、aRb → bRa が成り立つ。
　　（3） 推移律　∀ a, b, c ∈ A に対して、aRb ∧ bRc → aRc が成り立つ。

　数の大小関係は、反射律、推移律かつ以下に述べる反対称律を満たす 2項関係です。

　　（2）' 反対称律　∀ a, b ∈ A に対して、aRb ∧ bRa → a ＝ b が成り立つ。

　全順序 （total order, linear order） とは、反射的、推移的かつ反対称的な 2項関係です。単純に言い切ってしまえば、全順序は、「等号付きの不等号 （≦）」 を一般化した概念です。それに対して、半順序 （partial order）は、なんらかの並べかたがある関係を示します。

　
　さて、以上を前提にして、全順序の有向 グラフ を考えてみます。全順序は、反射律を満たすから、すべての頂点には ループ があります。そして、全順序は、推移律を満たしますから、a から b へ辺があり、かつ、b から c へ辺があり、したがって、a から c へも辺があります。前回 （12月 1日） 示した片方向連結において、すべての頂点が ループ をもっていると考えれば良いでしょう。そのために、全順序を有向 グラフ にしてみれば、たいそう込み入った図になります。
　全順序の込み入った辺を簡略にした有向 グラフ を ハッセ 図 （Hasse） と云います。たとえば、｛a, b, c｝ の ハッセ 図を以下に描いてみます。

　　　　　　　｛a, b, c｝
　　　　　　　　／｜＼
　　　　　　　／　｜　＼
　　　　　　／　　｜　　＼
　　　　　／　　　｜　　　＼
　　　　／　　　　｜　　　　＼
　　　／　　　　　｜　　　　　＼
　　｛a, b｝　 ｛b, c｝　　｛c, a｝
　　　｜＼　　　　｜＼　　／　｜
　　　｜　＼　　　｜　／　　　｜
　　　｜　　＼　／｜　　＼　　｜
　　　｜　　／＼　｜　　　＼　｜
　　　｜／　　　＼｜　　　　＼｜
　　｛a｝　　　　｛b｝　　　｛c｝
　　　＼　　　　　｜　　　　　／
　　　　＼　　　　｜　　　　／
　　　　　＼　　　｜　　　／
　　　　　　＼　　｜　　／
　　　　　　　＼　｜　／
　　　　　　　　＼｜／
　　　　　　　　　φ

　
　順序を上下に描けば、辺の ↑ を省略でき、作図が簡単になりますね。
　さて、この図を観て、｛a, b, c｝ に対して、或る規約が導入されていることに気づきましたか。｛a, b｝ ｛b, c｝ ｛c, a｝ を観ればわかるでしょう。すなわち、x, y ∈ A を全順序 （A, ≦） として、x ＜ y を考えて── x ≦ y かつ x ≠ y として──、さらに、x ≦ z ≦ y となるような z ∈ A は存在しない、という前提が導入されています──言い換えれば、図中、a ≦ c ≦ b となるような c は存在しない とされています。このような関係を、y は x の直線上にある と云います。

　以上の考えかたを一般化して、E ＝ ｛ （x, y） ∈ A × A ｜ y は x の直線上にある｝ とします。そして、有向 グラフ （A, E） を全順序の ハッセ 図と云います。

　さて、ハッセ 図が、TM の作図法として使えるかどうか という点を考えてみて下さい。
　TM の 「event」に関しては、TM の文法では、「event」 のなかで演算するので、ハッセ 図を使うことはないでしょうね。TM の 「resource」 に関しては、「resource」 は全順序ではないので、ハッセ 図を使えないでしょう──仮に、「resource」 を アルファベット 順 （あるいは、50音順） に並べたとしても、「event」 といっしょにした （混成した） 状態では、ハッセ 図を使う有用性はないでしょうね。「Resource」 のみを対象にすれば、ハッセ 図は、「リレーションシップ の検証表」 に似ているかもしれない。

　実は、正直に言えば、かつての Ｔ字形 ER手法を作った際、「event」 であろうが 「resource」 であろうが、ハッセ 図が示すような構造──たとえば、「event」 と 「resource」 のあいだでも、関連表 （mapping-list） を作る構造──を考えていました。ただ、Ｔ字形 ER手法を公表する直前 （2日前） になって、ハッセ 図的な構造を止めて、いま使っている 「4つの文法 （{ event, resource }, { event, event }, { resource, resource } および 再帰）」 として整えました。
　その理由は、関係 R および個体の 「解釈」 に関して、意味論 （semantics） を導入したから。



[ 補遺 ] （2010年 1月16日）

　2項関係 R (x, y) を図にしたのが有向 グラフ です。

　TM （Ｔ字形 ER手法の改良版） の前身である Ｔ字形 ER手法を作ったとき、「関係」 を いかに図式化するかで私は悩んでいました。というのは、個体 （entity）──この文脈では 「項」 と謂ったほうが正確かも──が すべて 全順序であれば、ハッセ 図を なんとかして応用しようと考えられたのですが、個体には、関係のなかで 対称性を示す個体 （event） と非対称性を示す個体 （resource） が存在していて、個体の すべてに対して全順序を適用できなかった──言い換えれば、「event」 は全順序 （線形順序） のなかで並び、「resource」 は半順序 （偽順序） のなかで並ぶということ。

　そのために、私は、当時、「関係」 を 「関数」 として扱うことに躊躇 （ためら） いがあって、「関係」 を relation と謂わないで relationship と謂うようにしていました。

　しかし、その後、2つの 「関数」──全順序の関数、半順序の関数── を併用してもいいのではないかと考え直して、「関係の文法」 を見直しました。「event」 どうしには 「全順序の関数」 を適用して、「resource」 どうしには 「半順序の関数」 を適用すればいいのですが、争点になるのは、「event と resource のあいだの文法」 です。この争点に対する ソリューション は、数学的 ソリューション ではなくて、哲学的 ソリューション を導入しました──すなわち、「resource が event に関与する （侵入する、ingression）」 と。この哲学的 ソリューション は、ホワイトヘッド 氏・パース 氏の形而上学を借用しました。

　TM では、「関係」 を 「関数」 として扱い、全順序および半順序を軸にして、「event-resource」 関係を 「例外」 として扱うことにしました。そういう体系にしたので、「関係」 を本来の形で relation と謂うようにして、relationship という語を使わないようなりました。そして、TMD （TM Diagram） を有向 グラフ として扱うことにしました。

　TMD をご覧いただければ、一見、チェン ERD に似ているのですが、TMD が重視しているのは 「箱 （entity）」 ではなくて 「線 （relation）」 であって、ERD とは全然違う。TMD では、「線 （relation）」 は、かならず、TM の 「関係文法」 に従って構成され、「箱 （entity）」 は、その構成 （関数） のなかで単なる項にすぎない。「線」 を重視するという点が 「関数」 の特徴点です。




　 << もどる ベーシックス すすむ >>
　 ▼ データベースの基礎知識