SQLで数列を扱う

SQLにおける順序を持ったデータの取り扱い方

単調増加と単調減少

　ある企業の株価の動向を表す次のようなテーブルを考えます。

MyStock

取引日(deal_date)	株価(price)
2007/01/06	1000
2007/01/08	1050
2007/01/09	1050
2007/01/12	900
2007/01/13	880
2007/01/14	870
2007/01/16	920
2007/01/17	1000

　前問までは、順序集合ということで「数」を考えてきましたが、「日付」も当然、順序を持ちます。今回は、株価が単調増加している期間を求めます。つまり、欲しい結果は、

• 2007/01/06 ～ 2007/01/08
• 2007/01/14 ～ 2007/01/17

　の2つです。とりあえず、「8日～9日」のような横ばいの期間は除外して考えます。それでは定石どおり、まずは「ステップ1：自己結合で始点と終点の組み合わせを作る」から行きましょう。

始点と終点の組み合わせを得るクエリ

SELECT S1.deal_date  AS start_date,
       S2.deal_date  AS end_date
  FROM MyStock S1, MyStock S2
 WHERE S1.deal_date < S2.deal_date;

　行数が多いので、結果は省略しますが、全部で28個の組み合わせが選択されます。ここから、不要な組み合わせを除外していきます。「ステップ2：始点-終点間のすべての点が満たすべき条件を記述する」です。

　ある期間において株価が単調増加していることを保証する十分条件は、その内部の任意の時点について、過去より未来の時点の値が大きい、ということです。そこでこの条件をひっくり返します。すると、

• 期間内の任意の二点について、前よりも後の時点の値が小さくなるようなペアが存在しない

　という条件になります。例えば、「2007/01/12」=900、「2007/01/13」=880のようなペアが一組でも含まれていたら、その期間は単調増加ではありません。従って答えはこうです。

単調増加する期間を求めるクエリ：部分集合も出力する

SELECT S1.deal_date   AS start_date,
       S2.deal_date   AS end_date
  FROM MyStock S1, MyStock S2
 WHERE S1.deal_date < S2.deal_date  
                             --ステップ1：始点と終点の組み合わせを作る
   AND  NOT EXISTS          
             --ステップ2：期間内のすべての行が満たすべき条件を記述する
           ( SELECT *
               FROM MyStock S3, MyStock S4
              WHERE S3.deal_date BETWEEN S1.deal_date AND S2.deal_date
                AND S4.deal_date BETWEEN S1.deal_date AND S2.deal_date
                AND S3.deal_date < S4.deal_date
                AND S3.price >= S4.price);

結果

start_date     end_date
------------   -------------
2007/01/06     2007/01/08
2007/01/14     2007/01/16
2007/01/14     2007/01/17
2007/01/16     2007/01/17

　期間内の二点をとりますから、それに対応して集合もS3とS4の2つを追加しています。サブクエリ内の2つのBETWEEN述語は、S3とS4の動く範囲が期間内である、ということを保証するものです（順序集合を扱うときは本当にBETWEEN述語が便利です）。次の「S3.deal_date < S4.deal_date」は、S3よりS4の方が未来の日付である、という条件。そして最後の「S3.price >= S4.price」で、過去の株価の方が高かった（または横ばいだった）という条件を記述しています。こうしてみると、全体としてはやや長いクエリですが、一つ一つの述語が明快な意味を持っていることが分かります。

　ところで、このクエリの結果は、「14日～17日」や「16日～17日」のような部分集合を含んでいます。最後に、こういう部分集合を除外します。これは、極値関数で簡単にできます。

部分集合を除外して、最大範囲の期間だけを取る

SELECT MIN(start_date) AS start_date,      --始点を最大限まえに伸ばす
       end_date
  FROM  (SELECT S1.deal_date AS start_date,
                MAX(S2.deal_date) AS end_date  --終点を最大限うしろに伸ばす
           FROM MyStock S1, MyStock S2
          WHERE S1.deal_date < S2.deal_date
            AND NOT EXISTS
             (SELECT *
                FROM MyStock S3, MyStock S4
               WHERE S3.deal_date BETWEEN S1.deal_date AND S2.deal_date
                 AND S4.deal_date BETWEEN S1.deal_date AND S2.deal_date
                 AND S3.deal_date < S4.deal_date
                 AND S3.price >= S4.price)
         GROUP BY S1.deal_date) TMP
GROUP BY end_date;

結果

start_date     end_date
------------   -------------
2007/01/06     2007/01/08
2007/01/14     2007/01/17

　始点と終点について、最大限まで伸ばすわけです。なお、横ばいも含めた「広義の単調増加」を求めたい場合は、サブクエリ内の「S3.price >= S4.price」から等号を除外すればOKです。サブクエリ内は裏返しの条件ですから、等しい期間を結果に含めたければ、逆に等号を外すのです。

おわりに

　今回は、数列に代表される順序集合のSQLでの扱い方を見てきました。単なるTipsの列挙に終わるのではなく、解法の背景に潜むSQLの原理を抽出しようと試みたつもりです。

　おそらく、すべてを集合と述語でやろうとするSQLの発想に初めて触れたときは、不思議な印象を受けるでしょう。私たちはまだ、この比較的新しい概念（どちらも生まれてから100年ちょっとしか経っていない）をよく知らないし、うまく扱えていないからです。この2つの概念の扱い方に慣れることが、SQL上達のポイントだと思います。

　それでは、今回の要点です。

1. SQLでのデータの扱い方は2通りある。
2. 1つは、順序を無視した集合と見なす方法。
3. もう1つは、順序集合と見なす方法。このときの基本的な指針は、
   1. まず自己結合で始点と終点の組み合わせを作る。
   2. 次に、相関サブクエリで、内部の要素同士の間に成立すべき関係を記述する。
4. SQLで全称文を記述したいときは、存在文の否定に同値変形して、NOT EXISTS述語を使う必要がある。これは、SQLが述語論理の存在量化子しか実装していないため。

参考資料

1. 『プログラマのためのSQL　第2版』 Joe Celko 著、ピアソンエデュケーション、2001年4月
SQLでの数列の扱い方については、「第24章　リージョン、ラン、シーケンス」が必読。
 
2. 『SQLパズル 第2版』 Joe Celko 著、ミック 訳、翔泳社、2007年11月
シーケンス・ビューを使った欠番の求め方は、「第57問　GAPS―VERSION ONE」を参照。セルコは、2つのテーブルはどちらも重複値を持たないだろうと仮定して、パフォーマンス向上のために「EXCEPT ALL」を使っています。
 
3. 『C. J. Dateのデータベース実践講義』 C. J. デイト 著、オライリージャパン、2006年2月
SQLにおける量化子の扱いについては、「付録A.5 数量化の補足」を参照。コラムの引用はこの章からのもの。
 
4. 『論理学をつくる』 戸田山和久 著、名古屋大学出版会、2000年10月
述語論理の量化子については「第5章　論理学の対象言語を拡張する」を参照。