Help us understand the problem. What is going on with this article?

適用期間付きデータと束

More than 1 year has passed since last update.

導入

適用開始を表す列sと適用終了を表す列eを持つテーブルTについて、t時点のデータを選択したい、というときこのように書くことがあると思います。

select * from T where T.s <= t and T.e >= t;

以上のことを、数学における半順序あるいは束という代数の記法を使用して考えてみる、というのがこの記事です。

区間と束

定義

区間 [a, b]を集合の記法で次のように定めます。

[a, b] = { t | t >= a ∧ t <= b } 

[a, b]とは、a以上b以下のtの集まり、ということです。

このようにして表される区間の集まりは以下のような束になります(厳密には結びでは閉じないので束ではない)。

最小元    最大元 交わり 結び 順序
区間 ∅(空集合) [⊥, ⊤] ∩(積集合) ∪(和集合) ⊆(包含)

また、区間上の各点も束になります。

最小元    最大元 交わり 結び 順序
⊥(最小値) ⊤(最大値) ∧(下限) ∨(上限) <=

(下限)、(上限)は、二項を受けとり小さい方(大きい方)を返す演算子で、三項演算子で書けば次のようになります。

a∧b = a < b ? a : b
a∨b = a < b ? b : a

そして、論理式も束になります。

最小元    最大元 交わり 結び 順序
論理式 ⊥(false) ⊤(true) ∧(and) ∨(or) ⇒(含意)

つまり、以下の3つの束がここにはあることになります。

最小元    最大元 交わり 結び 順序
区間 ∅(空集合) [⊥, ⊤] ∩(積集合) ∪(和集合) ⊆(包含)
⊥(最小値) ⊤(最大値) ∧(下限) ∨(上限) <=
論理式 ⊥(false) ⊤(true) ∧(and) ∨(or) ⇒(含意)

空区間あるいは非空区間

さて、区間[a,b]が空であることは、以下の条件と同値です。

b < a

同じことではありますが、区間[a, b]が非空であることは、以下の条件と同値です。

a <= b

明らかなことではありますが、証明します。

b < a のとき、区間[a, b]の条件を満たすt

      t >= a ∧ t <= b
⇔    t >= a ∧ t < a  // t <= b < a
⇔ ¬ (t < a) ∧ t < a  // t >= a = ¬ (t < a)
⇔    ⊥               // 排中律

よって、b < a のとき、区間[a, b]の条件はつねに偽ですので、空集合です。

積区間

続いて、区間[a, b]と区間[c, d]の積集合

[a, b] ∩ [c, d] = { t | t >= a ∧ t <= b } ∩ { t | t >= c ∧ t <= d }

を区間の記法で表すことを考えます。

  [a, b] ∩ [c, d] 
= { t | t >= a ∧ t <= b } ∩ { t | t >= c ∧ t <= d } // 区間の定義
= { t | t >= a ∧ t <= b ∧ t >= c ∧ t <= d }         // ∩の定義
= { t | t >= a ∧ t >= c ∧ t <= b ∧ t <= d }         // ∧の可換性
= { t | t >= a∨c ∧ t <= b∧d }                       //(*)
= [a∨c, b∧d]

(*)の変形について補います。文字をそのままで証明しましょう。まず、a,cについて。

a > c のとき
   t >= a ∧ t >= c
⇒ t >= a                        // ∧の下限性
⇒ t >= a∨c                     // a = a∨c
...
   t >= a∨c ⇒ t >= a           // a∨c = a
   t >= a∨c ⇒ t >= c           // a∨c = a > c
   t >= a∨c ⇒ t >= a ∧ t >= c 
...
   t >= a ∧ t >= c ⇔ t >= a∨c
a = c のとき 明らか
a < c のとき a > c のときの双対なので明らか

続いて、b,dについて。a,cのときの双対なので明らかですが。

b < d のとき
   t <= b ∧ t <= d
⇒ t <= b                        // ∧の下限性
⇒ t <= b∧d                     // b = b∧d 
...
   t <= b∧d ⇒ t <= b           // b∧d = b 
   t <= b∧d ⇒ t <= d           // b∧d = b < d 
   t <= b∧d ⇒ t <= b ∧ t <= d
...
   t <= b ∧ t <= d ⇔ t <= b∧d
b = d のとき 明らか
b > d のとき b < d のときの双対なので明らか

非空積区間

改めて、区間の積集合は以下の等式が成り立ちます。

 [a, b] ∩ [c, d] = [a∨c, b∧d]

[a, b] ∩ [c, d]が非空である条件は以下のように書くことができます。

a∨c <= b∧d

(*)で示したことを当てはめればこの条件は次のように書き換えられます。

a <= b ∧ c <= d ∧ a <= d ∧ c <= d

もし、[a, b], [c, d]が非空であれば、さらに短く書けます。

   a <= b ∧ c <= b ∧ a <= d ∧ c <= d
⇔ ⊤      ∧ c <= b ∧ a <= d ∧ ⊤      // a <= b, c <= d
⇔ c <= b ∧ a <= d                     // ⊤は単位元
⇔ a <= d ∧ b >= c                     // 整列

SQL

たとえば、SQLにおいて、ある期間[s, e]と重なる適用期間付きデータを選択したい、というとき、このようにwhere句を書けばいいということになります。

select * from T where T.s <= e and T.e >= s;

また、SQLにおいて、ある基準点tで適用期間付きデータを選択したい、というとき。

select * from T where T.s <= t and T.e >= t;

と書くことがあると思いますが、これは期間[s, e]と点期間[t, t](単集合)の重なりの条件

s <= t ∧ e >= t

と考えられます。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away