対象とする数独の問題と考え方
次のような数独の問題を解きます。これはPinskiさんの記事で紹介されている難問で、AlEscargotという名前がついています。
数独を解くSELECT文
SQLでは「何が欲しいか」を書くものだと言いましたが、次のようなSELECT文ではさすがに解けません。
SELECT 解答 FROM すべてのあり得る盤面 WHERE 数独のルールに反しない
コンピュータが解釈できる程度まで、分かりやすく書き直しましょう。そのためにまず、各マス目を次のような名前で表すことにします。
AlEscargotの解を見つけるためのSELECT文は次のようになります。
SELECT 1 AS R1C1,tR1C2.n AS R1C2, ... ,tR9C9.n AS R9C9 FROM nums tR1C2,nums tR1C3, ... ,nums tR9C9 WHERE 1!=tR1C2.n AND 1!=tR1C3.n AND ... AND tR9C8.n!=tR9C9.n
FROM節
値が決まっていないマス目に入り得るすべての数字の組み合わせを、FROM節にテーブルを列挙することで生成します。1から9までの整数が入っているテーブル「nums」を使えば、あり得るすべての数字の組み合わせは次のように書けます（R1C1のように既に値が決まっているものを書く必要はありません）。同じテーブルを使うので、区別するためにラベルを付けておきます（テーブルを表す「t」を付けました）。
FROM nums tR1C2,nums tR1C3, ... ,nums tR9C9
今解こうとしている問題ではR1C1（1行1列）の値は決まっているため、「nums tR1C1」はFROM節に入っていません。これを書いてもWHERE節に「tR1C1.n=1」という条件を追記すれば、大抵のRDBMSでは解けると思われます。処理がとても重くなるということもないでしょう。しかし、後述するように結合できるテーブルの数の制限が厳しいRDBMSもあるため、不要なテーブルはFROM節には入れないようにします。
SELECT節
SELECT節には「欲しいもの」を列挙します。欲しいのは各マス目の値ですから、次のように書けばよいでしょう（後の処理を単純にするために、R1C1のように既に値の決まっているものも書いておきます）。
SELECT 1 AS R1C1,tR1C2.n AS R1C2, ... ,tR9C9.n AS R9C9
WHERE節
WHERE節には「欲しいもの」の条件を書きます。「数独のルールに反しない」という条件を具体的に書けば、「各行・各列・各ブロックに同じ数字がない」ということになります。この条件はSQLで表現可能ですが、ちょっと複雑そうなので、もう少しかみ砕いて、各マス目レベルでルールを記述します。
WHERE 1!=tR1C2.n AND 1!=tR1C3.n AND ... AND tR9C8.n!=tR9C9.n
クエリヒント
SQLが実行されるときには、最適と思われる方法（プラン）が、プランナ（オプティマイザ）によって選ばれるのがふつうです。しかし、ここで作ったSELECT文には、そういう戦略はあまり役に立ちません。例えば、テーブルの最適な結合順序を考えるのは、おそらく時間の無駄です。そういうことをしないように、OracleとSQL Server、PostgreSQLには「指示したとおりの順番でテーブルを結合せよ」という意味のクエリヒントを与えます。DerbyとMySQL、SQLiteでは、このような指示は不要です。
Oracle
SELECTの直後に「 /*+ ORDERED */ 」を挿入します。
SQL Server
SELECT文の最後に「 OPTION (FORCE ORDER)」を追記します。
PostgreSQL
FROM節を次のように書くことによって、テーブルの結合順序を明示します。
FROM nums tR1C1 CROSS JOIN nums tR1C2 CROSS JOIN ... CROSS JOIN nums tR9C9
RDBMSの制限
上で紹介したようなSELECT文は、どんな場合でも使えるというわけではありません。
例えば、MySQLでは結合できるテーブル数の上限が61です（参考：結合の制限）。ここで解こうとしている問題AlEscargotの空白は58個なので問題ありませんが、空白部分が62個以上（数字が19以下）の問題は、ここで紹介している方法では解けません。「『SQLによる数独の高速解法』を使って空白を減らし、空白が61個以下になったら本稿の方法で一気に解く」という戦略が必要になります（Minimum Sudokuで数字が17個の問題が多数紹介されています）。ちなみに、SQL Serverではテーブル数の上限が256なので、ひとまわり大きな盤面でもそのまま解けるはずです（参考：SQL Server 2005 の最大容量仕様）。現実的な時間で解けるかどうかは実験してみないと分かりませんが。
また、実行できるSQL文の長さに制限のあるRDBMSでは、盤面が大きくなってSELECT文が長くなると解けなくなるおそれがあります（ここで紹介しているSELECT文は15KB程度なので問題ありません）。
動的なSQL文の生成
前章で何気なく書いたSELECT文ですが、省略せずに書くと次のような膨大なものになります。
とりあえず試したい場合は、次のように、テーブル「nums」を作成してからSELECT文を実行してください（コマンドプロンプトからの接続では、クエリが長すぎて実行できない可能性があります）。
CREATE TABLE nums (n INT NOT NULL PRIMARY KEY); INSERT INTO nums VALUES (1); INSERT INTO nums VALUES (2); INSERT INTO nums VALUES (3); INSERT INTO nums VALUES (4); INSERT INTO nums VALUES (5); INSERT INTO nums VALUES (6); INSERT INTO nums VALUES (7); INSERT INTO nums VALUES (8); INSERT INTO nums VALUES (9);
PostgreSQLでは次のSELECT文を使ってください（FROM節中のテーブルを「CROSS JOIN」で結合しています）。
このSELECT文を手で書くのは現実的ではありません。そこで、本稿の主題である「動的SQL」です。SQL文自体を実行時に生成するのです。
動的SQLは珍しいものではありません。多くのWebアプリケーションにおいて、サーバサイド言語（JavaやPHP、Perl、Ruby）で文字列としてSQL文を作成し、それを使ってデータベース管理システム（MySQLやSQL Server）に問い合わせ、結果を受け取ります。実行されるSQL文がいつも同じではなく実行時に決まるなら、「動的SQL」と呼んでいいでしょう。
SQLに限らず、プログラムを動的に生成するというのは、非常に強力な手法です。典型的な例はプログラミング言語Lispにおけるマクロでしょう。Lispのコードは、それ自体がLispの基本的なデータ構造である構文木（S式）を使って表現されているため、プログラムからとても扱いやすいのです。残念ながら本稿では、SQLを単なる文字列として操作するだけで、LispにおけるS式のような扱いやすさはありません。それでも、「はじめに」で紹介したようなパフォーマンスが得られるのですから、試してみる価値は大きいです。
本稿では、動的にSQLを生成する方法を2つ紹介します。一つはJDBCを使う方法で、これはPHPやPerl、Rubyといったデータベースへのアクセス手法が用意されている他の言語でも簡単に応用できるでしょう。もう一つはストアド・プロシージャを用いた方法で、データベースだけで話が完結します（CALCULATE_GS_V3と比較するために実装しました。分かりやすさという点ではJDBC版がお勧めです）。
