subrelation

部分関係

関係束において、A が B の部分関係であるというのは、 A が B の一部分となっていることです。 これは、A とある関係 C の結びが B になるような C が存在するということでもあるし、 あるいは、B とある関係 D の交わりが A になるような D が存在するということでもあります。

A subrel B  iff  exists C : A join C = B
            iff  exists D : B meet D = A

甲州記法の計算式で書くと、 A | join C の join C が、A → B という写像になるし、 B | meet D の meet D が、B → A という写像になるということです。

関係の集合に join / meet による順序を入れて、 最小の関係を左端に、最大の関係を右端に書くと、 関係の集合は、つぎのようにイメージできます。 これは、ちょうど、ハッセ図を横にたおした形になっています。

                      |
                     / \
                    /   \
                   /     \
                  /   X   \
                 /   / \   \
                /   /   \   \
    meet side  E - Z --- V -- F  join side
                \   \   /   /
                 \   \ /   /
                  \   Y   /
                   \     /    Z subrel X subrel V
                    \   /     Z subrel Y subrel V
     E = reldau      \ /      Z = X meet Y
     F = reldee       |       V = X join Y

関係写像演算子

部分要素となる組を通過させる関係写像演算子は、 つぎのように書けるでしょう。

A | sub B

逆に、部分要素ではない組を通過させる関係写像演算子も考えられます。

A | non-sub B
A | none (sub B)

この演算子は、関係 B が項目 /x のドメインをあらわしているとすると、 関係 A の項目 /x がそのドメインの要素であるかを検査するときに使えます。

|=V OUT-OF-B : A | pick /x | non-sub B

直観的説明

A が B の部分関係であるとき、 A の項目集合は B と同じか、それより大きく、 A を B の項目に射影すると、 その関係に含まれる組は、すべて B のなかにあります。 つまり、A subrel B は、つぎのように分解できます。

• B の項目集合 ⊆ A の項目集合
• A の B に関する組集合 ⊆ B の組集合

なぜ、このようになるのでしょうか。

A の項目集合が B よりも大きいということは、 言及内容が増えているということです。 たとえば、B /x /y だけをみたせばよかったのが、 部分関係では B /x /y に加えて A /x /y /z もみたさなければならないからです。 そうすると必然的に、A /x /y /z を B に関して射影すれば、 B /x /y をみたす組の部分集合になります。

いま、A が B と C の交わりで定義されているとき、 A と B に関して成立した上の性質は、 A と C についても成立します。 たとえば、C /y /z に加えて A /x /y /z もみたすというように。

A が B の部分関係であるとは、 A が B より詳細化されているということで、 逆にいえば、B が A より抽象化されているということです。 だからこそ、抽象化の端が、無項万有関係という、 何にも言及せず、すべてをみたすという関係であり、 詳細化の端が、全項空関係という、すべてに言及し、何もみたさないという関係になります。