関係写像 both R は、入力関係と写像 R の出力との両結びを計算します。
両結びは、SQL の用語でいうところの完全外部結合 (full outer join) のことです。
このノートでは、両結びと等価な計算を、
より基礎的な演算子を使って実行する方法を説明します。
このノートの内容は甲州計算機のバージョン 0.50 に対応します。
ここで説明している甲州スクリプトの実行結果は
script ディレクトリにあります。
両結びの計算をつぎのデータ DATA.k を使って例示します。
判断 P は項目 /a /b をもち、
p : source P /a /b
|-- P /a 10 /b 40
|-- P /a 10 /b 50
|-- P /a 20 /b 50
判断 Q は項目 /b /c をもち、
ふたつの判断の共有項目は /b です。
q : source Q /b /c
|-- Q /b 50 /c 80
|-- Q /b 60 /c 90
両結びは、基本的には、ふたつの関係の交わりを計算しますが、
交わり不可能な組も計算結果に残すところが異なります。
この計算は、ふたつの判断 P と Q を
つぎの 3 つに分類することに対応します。
P(/a/b) が成り立ち、Q(/b/c) も成り立つ。P(/a/b) は成り立つが、Q(/b/c) は成り立たない。Q(/b/c) は成り立つが、P(/a/b) は成り立たない。
Q (/b /c) は成り立たないというのは、
P (/a /b) で固定されたある /b に関していうと、
どのような /c をもっても Q が成り立たないということです。
もしどこかの /c で Q が成立すれば、それは、1 番目に分類されます。
両結びを計算する素朴な方法は、p と q の片結びを左右とも計算し、
その結果を join で結び合わせることです。
この方法は、maybe.k の計算式に対応します。
pq : p | maybe q
qp : q | maybe p
|== MAYBE : pq | join qp
この計算式でデータを組み合わせると、つぎの判断集合が出力されます。
P (/a 10 /b 40) に対して、
Q (/b 40 /c ?) となる /c はないため、
値がないことをあらわす () を内容にもちます。
|-- MAYBE /a 10 /b 40 /c ()
|-- MAYBE /a 10 /b 50 /c 80
|-- MAYBE /a 20 /b 50 /c 80
|-- MAYBE /a () /b 60 /c 90
上の計算式から pg と gp の定義を除いて、
1 本の式に直すと、maybe-liner.k のように書けます。
これも同じ計算をします。
|== MAYBE-LINER : ( p | maybe q ) | join ( q | maybe p )
maybe-liner.k は p が 2 回か出現するので、
p が 1 回だけ出現するように書き換えます。
この copy-maybe.k も同じ計算をします。
|== COPY-MAYBE : p | copy i ( maybe q | join ( q | maybe i ))
少し技巧的ですが、同様にして、q も 1 回だけ出現するように書き換えると
once.k のようになります。
これで p と q を分離できたので、
copy i ( maybe q | join ( q | maybe i )) を
both q と書けるようになります。
|== BOTH : p | both q