3.8.7. 関係代数の演算#

PySIMPLE は多次元の疎な集合を頻繁に扱いますが，これらの操作は関係代数の演算として整理できます．

まずは，基本的な演算である，和，差，交わり，直積，射影，選択を見てみます．

和 \(I\cup J=\{n \mid n\in I \lor n\in J\}\)
差 \(I-J=\{n \mid n\in I \land n\notin J\}\)
交わり \(I\cap J=\{n \mid n\in I \land n\in J\}\)
直積 \(I\times J=\{(i,j) \mid i\in I \land j\in J\}\)
射影 \(\pi_I(IJ)=\{i \mid (i,j)\in IJ\}\)

選択 \(\sigma_{I=3}(IJ)=\{(i,j) \mid i=3 \land (i,j)\in IJ\}\):

>>> I = Set(value=[1,2,3,4], name='I')
>>> J = Set(value=[2,4,6,8], name='J')
>>> print(I | J)  # 和
(I|J)=Set(value=[1, 2, 3, 4, 6, 8])
>>> print(I - J)  # 差
(I-J)=Set(value=[1, 3])
>>> print(I & J)  # 交わり
(I&J)=Set(value=[2, 4])
>>> S = Set(value=[1,2], name='S')
>>> print(S * S)  # 直積
(S*S)=Set(value=[(1, 1), (1, 2), (2, 1), (2, 2)])
>>> IJ = Set(value=[(1,3), (1,4), (2,3)], name='IJ')
>>> print(IJ(0))  # 射影
IJ(0)=Set(value=[1, 2])
>>> ij = Element(set=IJ, name='ij')
>>> Condition(ij, ij(1)==3)  # 選択
(ij, (ij(1)==3))[ij] in [(1, 3), (2, 3)]

選択以外は専用の演算子やメソッドが用意されており，集合の演算として自然に記述できます．また，これらの演算は(疎な)多次元集合でも記述できます．

結合演算の中でも基本的な演算が，直積を一般化した等結合(equijoin)や自然結合(natural join)です．これらの他に頻出する有用な結合演算が，交わりと差を一般化した準結合(semijoin)と反結合(antijoin)です．

等結合 \(\{(i,j_1,j_2,k) \mid j_1=j_2 \land (i,j_1)\in IJ \land (j_2,k)\in JK\}\)
自然結合 \(IJ \bowtie_J JK=\{(i,j,k) \mid (i,j)\in IJ \land (j,k)\in JK\}\)
準結合 \(IJK \ltimes_{I,K} IK=\{(i,j,k) \mid (i,j,k)\in IJK \land (i,k)\in IK\}\)

反結合 \(IJK \rhd_{I,K} IK=\{(i,j,k) \mid (i,j,k)\in IJK \land (i,k)\notin IK\}\):

>>> ij = Element(value=[(1,3), (1,4), (2,3)], name='ij')
>>> jk = Element(value=[(3,5), (3,6), (4,5)], name='jk')
>>> Condition((ij,jk), ij(1)==jk(0))  # 等結合
((ij,jk), (ij(1)==jk(0)))[ij,jk] in [(1,3,3,5), (1,3,3,6), (1,4,4,5), (2,3,3,5), (2,3,3,6)]
>>> Condition((ij,jk(1)), ij(1)==jk(0))  # 自然結合
((ij,jk(1)), (ij(1)==jk(0)))[ij,jk(1)] in [(1,3,5), (1,3,6), (1,4,5), (2,3,5), (2,3,6)]
>>>
>>> ijk = Element(value=[(1,3,5), (1,3,6), (1,4,5), (2,3,5)], name='ijk')
>>> ik = Element(value=[(1,6), (2,5)], name='ik')
>>> Condition(ijk, ijk(0,2)<ik.set)  # 準結合
(ijk, (ijk(0,2)<ik.set))[ijk] in [(1, 3, 6), (2, 3, 5)]
>>> Condition(ijk, ijk(0,2)>ik.set)  # 反結合
(ijk, (ijk(0,2)>ik.set))[ijk] in [(1, 3, 5), (1, 4, 5)]

結合は直積に対する条件付けとして定義されます．それぞれに専用の記法が用意されている訳ではありませんが， Condition によって述語を明示的に与えることで，結合を関係論理的に表現しています．このことは，先ほどの選択についても同様です．

最後に集約を見てみましょう．:

>>> ab = Element(value=[(1,1), (1,2), (1,4), (2,2), (2,3), (3,1), (3,5)], name='ab')
>>> Sum(ab(1))  # 合計
Sum(ab(1), ab(1))[1]=7
Sum(ab(1), ab(1))[2]=5
Sum(ab(1), ab(1))[3]=6
>>> Max(ab(1))  # 最大
Max(ab(1), ab(1))[1]=4
Max(ab(1), ab(1))[2]=3
Max(ab(1), ab(1))[3]=5
>>> Min(ab(1))  # 最小
Min(ab(1), ab(1))[1]=1
Min(ab(1), ab(1))[2]=2
Min(ab(1), ab(1))[3]=1
>>> Sum(1, ab(1))  # カウント
Sum(1, ab(1))[1]=3
Sum(1, ab(1))[2]=2
Sum(1, ab(1))[3]=2

平均は Sum(ab(1))/Sum(1, ab(1)) で計算できます．

データベースでは必須の関係代数ですが，PySIMPLE と異なる点として，データベースの関係は属性に名前がついている一方，PySIMPLE の集合には次元ごとに名前はついていません．そのため，属性は次元で指定することになりますが，IJK など次元に対応したオブジェクト名を用意することで，却って簡潔に記述することができます．