関係束 (かんけいそく、relational lattice) は、 関係モデル (リレーショナル・モデル) のための代数的な理論です。 関係モデルは関係を基本要素とした計算体系です。 この計算体系は、ふたつの関係を合成する演算として 結び と 交わり を用意し、 関係の計算に必要な演算規則を定式化しています。
関係型データ言語のひとつの 甲州記法 では、
結びは演算子 join で実行され、
交わりは演算子 meet で実行されます。
このノートでは、甲州記法を使って、関係モデルを初めて学ぶ方のために、
結びと交わりを説明します。
たし算とかけ算が、ふたつの数 a と b を合成した新しい数
c = a + b と d = a * b をつくるように、
結びと交わりは、ふたつの関係 a と b を合成した新しい関係
c : a | join b と d : a | meet b をつくります。
結びは、ふたつの関係の共有する項目のみに着目することで、
内包 を 概括 し外延を拡大します。
逆に、交わりは、ふたつの関係のすべての項目に着目することで、
内包を 限定 し 外延 を縮小します。
たとえば、3 項目 /v /w /x からなる 3 項関係 a と
4 項目 /w /x /y /z からなる 4 項関係 b があるとします。
そのとき、共有項目は /w /x であるため、
結びは /w /x のみからなり、
交わりはすべての項目 /v /w /x /y /z からなります。
a : /v /w /x a : /v /w /x
b : /w /x /y /z b : /w /x /y /z
------------------ join ------------------ meet
c : /w /x d : /v /w /x /y /z
共有項目のみに着目するということは、
a と b から /v と /y /z を捨象して概括することに相当します。
a で /w /x の間に成立している関係と、
b で /w /x の間に成立している関係とを考えるように、
内包が緩和されるため、外延が拡大します。
逆に、交わりがすべての項目に着目するということは、
/v /w /x /y /z の間に成立する関係として、
a と b を同時に考慮することになります。
a において /v /w /x の間の関係が成立することに加えて、同時に、
b において /w /x /y /z の間にも
関係が成立するという条件で情報が限定されます。
内包が限定されるほど、それをみたせる組み合わせが減るため、外延が縮小します。
甲州記法では、判断集合を関係として読み出し、
その関係上で計算し、最後に、関係を判断集合として書き出します。
判断の書き方 の説明は別の文書にゆずりますが、判断集合として、
判断種 A の判断が 3 つ、判断種 B の判断も 3 つあるとします。
|-- A /v 1 /w 20 /x 100
|-- A /v 2 /w 30 /x 100
|-- A /v 2 /w 40 /x 120
|-- B /w 30 /x 100 /y 10 /z 140
|-- B /w 40 /x 120 /y 10 /z 150
|-- B /w 50 /x 140 /y 20 /z 150
これを、関係写像演算子 source を使って、
関係 a と b として読み出し、
a : source A /v /w /x
b : source B /w /x /y /z
関係写像演算子 join と meet で、
結び c と交わり d を計算します。
c : a | join b
d : a | meet b
最後に、関係 c と d のそれぞれに、
判断種 C と D を付与し、計算結果を書き出します。
|== C : c
|== D : d
そうすると、判断種 C として、つぎの 4 つの概括的な判断が書き出され、
|-- C /w 20 /x 100
|-- C /w 30 /x 100
|-- C /w 40 /x 120
|-- C /w 50 /x 140
判断種 D として、つぎの 2 つの限定的な判断が書き出されます。
|-- D /y 10 /z 140 /v 2 /w 30 /x 100
|-- D /y 10 /z 150 /v 2 /w 40 /x 120
この計算は koshu lattice.k によって実行でき、
その結果は 入出力リスト で確認できます。
項目 /v /w /x からなる関係 a と
項目 /w /x /y /z からなる関係 b は、
各項目が列をなし、各組が行となるように配置すると、
つぎのように視覚化できます。
a : /v 1 /w 20 /x 100 b : /w 30 /x 100 /y 10 /z 140
/v 2 /w 30 /x 100 /w 40 /x 120 /y 10 /z 150
/v 2 /w 40 /x 120 /w 50 /x 140 /y 20 /z 150
これらを共有項目 /w /x で重ね合わせると、
結びは、共有項目部分を抜き出すことで計算できます。
関係 a と b の重ね合わせはつぎのようになり、
c :
/v 1 | /w 20 /x 100 |
/v 2 | /w 30 /x 100 | /y 10 /z 140
/v 2 | /w 40 /x 120 | /y 10 /z 150
| /w 50 /x 140 | /y 20 /z 150
垂直線で囲まれた領域を抜き出したものが結び c に相当することになります。
交わりは、一方の関係の各組に対して、
共有項目の内容が一致する組を他方の関係から探し出し、
たとえば、関係 a の組 /v 2 /w 30 /x 100 に対して、
関係 b の組 /w 30 /x 100 /y 10 /z 140 を探し出し、
それらの項目を合併することで計算できます。
関係 a と b の重ね合わせ
/v 1 /w 20 /x 100
- - - - - - - - - - - - - - - - -
d : /v 2 /w 30 /x 100 /y 10 /z 140
/v 2 /w 40 /x 120 /y 10 /z 150
- - - - - - - - - - - - - - - - -
/w 50 /x 140 /y 20 /z 150
のなかで、水平線で囲まれた領域を抜き出したものが交わり d に相当します。