Hamming numbers in SQL

SQL-99 では再帰が使えるので、それを使って　Hamming numbers を出力する。
まずは、再帰クエリが使えるデータベースを調べてみる。

• 再帰クエリ - Wikipedia

H2 Database が一番手軽に導入できるのでこれを使ってみる。

再帰クエリの書き方

H2 Dataabse のドキュメントから再帰クエリの書き方を引用する。

• Recursive Queries

WITH RECURSIVE recursiveQueryName(columnName, ...) AS (
    nonRecursiveSelect
    UNION ALL
    recursiveSelect
)
select

現時点では H2 Database の再帰クエリは experimental support らしい。
試したところ、次の2つのことができなかった。

• UNION ALL の代わりに UNION を使う
• WITH 句で複数のテーブルを宣言する

両方ともあとで PostgreSQL で試す。Hamming numbers を書く上で障害にはならない。

Hamming numbers で WITH RECURSIVE の理解を深める

-- H2 Database Engine version 1.3.165
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION ALL (
    SELECT 2*n FROM hamming WHERE 2*n < 100
    UNION
    SELECT 3*n FROM hamming WHERE 3*n < 100
    UNION
    SELECT 5*n FROM hamming WHERE 5*n < 100
  )
)
SELECT n FROM hamming /*GROUP BY n*/ ORDER BY n LIMIT 20
-- 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

H2 Database の再帰クエリでは、recursiveSelect に終了条件を指定しないと無限ループになって返ってこない。
Hamming numbers の最初の20個は100までに現れることは予め知っているのでそれを終了条件に指定した。

突然ですが、ここで問題です。
筆者はコメントアウトしている GROUP BY を必要だと思っていました。
しかし、必要ありませんでした。どうして不要なのでしょうか？

ヒント

不要な理由は2つあって、ひとつは数学的なもので、もうひとつが WITH RECURSIVE によるものである。
今知りたいのは、WITH RECURSIVE なので数学的な理由を説明しておく。
それは、素因数分解の一意性によるものである。*1
2,3,5 の3つの数字から同じ数字を何回選んでもいいので n 個選んで掛け合わせた数字と n+1 個選んで掛け合わせた数字は決して同じにならない。
そして n が違えば掛け合わせた数字は同じにならない。

ノブレス・オブリージュ

ここまで読んだ人は WITH RECURSIVE に関心のある人である。
したがって、次のどちらかの理由で最後まで読むことをお勧めする。
何故 GROUP BY が不要なのかわからない人は、理由を知るために最後まで読んだ方がよい。
理由がわかっている人は、筆者が間違ったことを広めていないか確認するために最後まで読んだ方がよい。

GROUP BY が必要だと思っていた理由

-- H2 Database Engine version 1.3.165
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION ALL (
    SELECT 2*n FROM hamming WHERE 2*n < 100
    UNION ALL
    SELECT 3*n FROM hamming WHERE 3*n < 100
    UNION ALL
    SELECT 5*n FROM hamming WHERE 5*n < 100
  )
)
SELECT n FROM hamming /*GROUP BY*/ n ORDER BY n LIMIT 20
-- 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18

recursiveSelect の UNION を UNION ALL に変更しただけだ。
2*n, 3*n, 5*n が重複するのは n が0のときだけのはずなので1以上の場合 UNION でも UNION ALL でも同じはずだ。
UNION と書いてはいたが筆者の想定では UNION ALL の意味で使っており、タイプ数をケチっただけだ。

Hamming numbers in PostgreSQL

H2 Database の WITH RECURSIVE は experimental support だし PostgreSQL なら動作するかもしれない。
調べているとどうやら PostgreSQL では recursiveSelect での終了条件も必須でないし、UNION も使えるらしい。
がしかし...

-- PostgreSQL 9.1.3
-- ERROR: クエリー "hamming" への再帰参照が２回以上現れてはなりません
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION (
    SELECT 2*n FROM hamming
    UNION ALL
    SELECT 3*n FROM hamming
    UNION ALL
    SELECT 5*n FROM hamming
  )
)
SELECT n FROM hamming ORDER BY LIMIT 20

これで H2 Database と比べることができなくなった。

さらに

-- PostgreSQL 9.1.3
-- ERROR: integerの範囲外です
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION
  SELECT m*n FROM hamming, factor
), factor(m) AS (
  SELECT 2 UNION SELECT 3 UNION SELECT 5
)
SELECT n FROM hamming ORDER BY n LIMIT 20

無限リストは返せるがソートはできないようだ。残念だがこれは想定内。

-- PostgreSQL 9.1.3
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION
  SELECT m*n FROM hamming, factor WHERE m*n < 100
), factor(m) AS (
  SELECT 2 UNION SELECT 3 UNION SELECT 5
)
SELECT n FROM hamming n ORDER BY n LIMIT 20
-- 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

ようやく Hamming numbers を手に入れた。

間違ったモデル

DB 間の違いは比較できなくなったので、SQL の結果を再現する手続き型の疑似コード *2 を書いてみる。

def withRecursive(opts=[all:false], nonRecursive, recursive) {
  def result = []
  def queue  = [] as Queue
  for (work in nonRecursive.call())
    queue.offer(work)
  while (queue) {
    def n = queue.poll()
    for (work in recursive.call(n))
      queue.offer(work)
    result.add(n)
  }
  if (opts.all)
    return result
  else
    return result.unique()
}

今まで実行した SQL を疑似コードで実行して確認する。

-- PostgreSQL 9.1.3
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION
  SELECT m*n FROM hamming, factor WHERE m*n < 100
), factor(m) AS (
  SELECT 2 UNION SELECT 3 UNION SELECT 5
)
SELECT n FROM hamming n LIMIT 20
-- 1 5 2 3 25 10 15 4 6 9 50 75 20 30 45 8 12 18 27 40

def nonRecursive = { [1] }
def recursive    = { n ->
  def temp = []
  for (m in [5,2,3])
    if (m*n < 100)
      temp.add(m*n)
  return temp
}
println withRecursive(all:false, nonRecursive, recursive).take(20).join(' ')
// 1 5 2 3 25 10 15 4 6 9 50 75 20 30 45 8 12 18 27 40

5,2,3 になっているのは UNION の結果の順序に合わせたため。
完全に一致。

-- H2 Database Engine version 1.3.165
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION ALL (
    SELECT 2*n FROM hamming WHERE 2*n < 100
    UNION ALL
    SELECT 3*n FROM hamming WHERE 3*n < 100
    UNION ALL
    SELECT 5*n FROM hamming WHERE 5*n < 100
  )
)
SELECT n FROM hamming /*GROUP BY*/ n ORDER BY n LIMIT 20
-- 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18

def nonRecursive = { [1] }
def recursive    = { n ->
  def temp = []
  for (m in [2,3,5])
    if (m*n < 100)
      temp.add(m*n)
  return temp
}
println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ')
// 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18

こちらも完全に一致した。

ただしこのモデルでは次の結果を再現することができない。

-- H2 Database Engine version 1.3.165
WITH RECURSIVE hamming(n) AS (
  SELECT 1
  UNION ALL (
    SELECT 2*n FROM hamming WHERE 2*n < 100
    UNION
    SELECT 3*n FROM hamming WHERE 3*n < 100
    UNION
    SELECT 5*n FROM hamming WHERE 5*n < 100
  )
)
SELECT n FROM hamming /*GROUP BY n*/ LIMIT 20
-- 1 2 3 5 9 10 25 4 6 15 18 50 20 8 75 27 12 45 30 81

正しいモデル

探したところ PostgreSQL のドキュメントに書かれているようなのでこれを引用する。

• http://www.postgresql.jp/document/9.1/html/queries-with.html

再帰的問い合わせの評価

1. 非再帰的表現を評価します。 UNION（しかしUNION ALLではありません）では、重複行を廃棄します。その再帰的問い合わせの結果の残っている全ての行を盛り込み、同時にそれらを暫定的作業テーブルに置きます。
2. 作業テーブルが空でないのであればこれらの手順を繰り返します。
   1. 再帰自己参照に対する作業テーブルの実行中の内容を置換し、再帰的表現を評価します。 UNION（しかしUNION ALLではない）に対し、重複行と前の結果行と重複する行を破棄します。その再帰的問い合わせの結果の残っているすべての行を盛り込み、同時にそれらを暫定的中間テーブルに置きます。
   2. 中間テーブルの内容で作業テーブルの内容を差し替え、中間テーブルを空にします。

注意: 厳密には、この手順は反復であって再帰ではありませんが、RECURSIVEはSQL標準化委員会で選ばれた用語です。

高度な日本語が使われているので、理解できるようにこれを表現する手続き型の疑似コードを書いてみる。

def withRecursive(opts=[all:false], nonRecursive, recursive) {
  def result = []
  def work   = nonRecursive.call()
  result += work
  if (!opts.all)
    result = result.unique()
  while (work) {
    work = recursive.call(work)
    result += work
    if (!opts.all)
      result = result.unique()
  }
  return result
}

def nonRecursive = { [1] }
def recursive    = { work ->
  def temp = []
  for (n in work) {
    if (2*n <= 100) temp.add(2*n)
    if (3*n <= 100) temp.add(3*n)
    if (5*n <= 100) temp.add(5*n)
  }
  return temp.unique()
}

println withRecursive(all:true, nonRecursive, recursive).take(20).join(' ')
// 1 2 3 5 4 6 10 9 15 25 8 12 20 18 30 50 27 45 75 16

println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ')
// 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

unique() と UNION の違いか完全に一致しない。
しかしこれが正しいモデルだ。8 は決して 25 より前に現れない。

間違ったモデルで動作していたものも確認する。

def nonRecursive = { [1] }
def recursive    = { work ->
  def temp = []
  for (n in work) {
    if (2*n <= 100) temp.add(2*n)
    if (3*n <= 100) temp.add(3*n)
    if (5*n <= 100) temp.add(5*n)
  }
  return temp
}

println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ')
// 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18

問題の答え

WITH RECURSIVE の再帰では recursiveSelect に受け渡されるのはレコード単位ではなく1つ前のクエリの結果だから。

2
3
5
...

ではなく

2,3,5
2*2,...,5*5
2*2*2,...,5*5*5
...

と渡ってくる。
1つ前の結果が渡ってくるのは SQL 以外と同じだが、日ごろ recursiveSelect で1レコードしか返していないと勘違いしてしまう。
Hamming numbers の recursiveSelect　のクエリの結果は素因数の個数が等しい数の集まりである。
したがって、個数が等しいものの中で重複を取り除けば素因数分解の一意性により他の個数との重複は気にしなくてもよい。
よって GROUP BY は不要である。
Qed.

*1:素因数分解の一意性は 素因数分解 - Wikipedia や『数学ガール』 を持っているなら 8.9.3 に載っている

*2:Groovy です