3人なんですけど、座れますか？
友人同士で旅行にでかける際、列車や飛行機の座席を予約しようとしたら、人数分の連続した空席がなくて、一人だけ離れ小島の席になってしまった――こんな淋しい経験をしたことのある人もいるのではないでしょうか。
次のような、座席の空席状況を表すテーブルを考えます。
| seat(座席) | status(状態) |
| 1 | 占 |
| 2 | 占 |
| 3 | 空 |
| 4 | 空 |
| 5 | 空 |
| 6 | 占 |
| 7 | 空 |
| 8 | 空 |
| 9 | 空 |
| 10 | 空 |
| 11 | 空 |
| 12 | 占 |
| 13 | 占 |
| 14 | 空 |
| 15 | 空 |
いま、3人で旅行に出かけようと思って、この列車に予約を取ろうとしているとします。問題は、この1～15までの席番号の中から、連続する3個の空席の組み合わせをすべて探すことです。この連続した整数の集合を「シーケンス」と呼ぶことにします。
上のデータから求めたい結果は、
- 3 ～ 5
- 7 ～ 9
- 8 ～ 10
- 9 ～ 11
の四つです。(7, 8, 9, 10, 11)というシーケンスは、部分集合として(7, 8, 9)、(8, 9, 10)、(9, 10, 11)という三つのシーケンスを含みますが、これらも区別して求めます。また、普通こういう座席は途中で行の折り返しが入るものですが、今はそれは無視して、席は直線的に並んでいるとします。
上図を使って考えれば、数nを始点として、n + (3 - 1) までの数が、すべて空席の状態にあるということです（マイナス1しないと席を1つ多く取ってしまうので注意してください）。答えは次のようになります。
SELECT S1.seat AS start_seat, '～' , S2.seat AS end_seat FROM Seats S1, Seats S2 WHERE S2.seat = S1.seat + (:head_cnt -1) --始点と終点を決める AND NOT EXISTS (SELECT * FROM Seats S3 WHERE S3.seat BETWEEN S1.seat AND S2.seat AND S3.status <> '空' );
:head_cntは、座りたい人数を表すパラメータです。パラメータに代入する人数を変えることで、集団の人数が何人でも対応できます。
このクエリには、SQLで順序集合を扱うときの原理がよく現れています。今から、それを詳しく説明しましょう。このクエリの要点は、二段階に分けて考えると理解しやすくなります。まずは、第一段階、
ステップ1：自己結合で始点と終点の組み合わせを作る。
このクエリで言えばS2.seat = S1.seat + (:head_cnt -1)の部分に相当します。これによって、「1～8」とか「2～3」のような大きさが3以外の組み合わせを排除して、始点と終点までにちょうど3個の座席を含むシーケンスのみに制限できます。お次は、
ステップ2：始点―終点間のすべての点が満たすべき条件を記述する
始点と終点が決まったら、今度はその内部の各点が満たすべき条件を記述します。そのために、始点と終点の間を移動する点集合を追加します（上のクエリの「S3」）。移動する範囲を画定するにはBETWEEN述語が便利です。
今回、シーケンス内の要素が満たすべき条件は、「すべての座席の状態が「空」であること」です。しかし、SQLではこの条件をストレートに記述できません。実は、ここもSQLを考える際のワンポイントなのですが、SQLでは「すべての行が条件Pを満たす」という文を、「条件Pを満たさない行が存在しない」と同値変形して、NOT EXISTS述語を使う必要があるのです。それゆえ、サブクエリ内の条件も「S3.status = '空'」ではなく、その否定形「S3.status <> '空'」となります。この妙な言語仕様の裏事情については、コラム「SQLと量化子」を参照してください。
では、次に応用版として、行の折り返しも考慮した修正を考えましょう。例えば、この列車が5列で折り返すと仮定します。テーブルに、行の識別子（row_id）を追加します。
| seat(座席) | row_id(行ID) | status(状態) |
| 1 | A | 占 |
| 2 | A | 占 |
| 3 | A | 空 |
| 4 | A | 空 |
| 5 | A | 空 |
| 6 | B | 占 |
| 7 | B | 占 |
| 8 | B | 空 |
| 9 | B | 空 |
| 10 | B | 空 |
| 11 | C | 空 |
| 12 | C | 空 |
| 13 | C | 空 |
| 14 | C | 占 |
| 15 | C | 空 |
このケースにおいては、たとえ連番だけ見ればシーケンスをなしていても、(9, 10, 11)のような集合は選択してはいけません。11番に座る人が実質ひとりぼっちになってしまうからです。
折り返しに対応するには、シーケンス内の座席がすべて空席であるだけではなく、「すべて同じ行内にある」ことを条件に組み込む必要があります。これは、次のような簡単な修正で可能です。
SELECT S1.seat AS start_seat, '～' , S2.seat AS end_seat FROM Seats2 S1, Seats2 S2 WHERE S2.seat = S1.seat + (:head_cnt -1) --始点と終点を決める AND NOT EXISTS (SELECT * FROM Seats2 S3 WHERE S3.seat BETWEEN S1.seat AND S2.seat AND ( S3.status <> '空' OR S3.row_id <> S1.row_id));
start_seat ‘～’ end_seat
------------ ----- ------------
3 ～ 5
8 ～ 10
11 ～ 13
シーケンス内の要素が満たすべき条件は「すべての行について、状態が「空」である、かつ、行IDが同じである」です。後半の「行IDが同じ」という条件が追加されたわけですが、これは要するに「始点の行IDと同じである」と同値です（もちろん終点でもかまいません）。それを素直にSQLに訳せば、
S3.status = '空' AND S3.row_id = S1.row_id
です。しかし、先述の通り、SQLではこの条件の否定を使わねばなりませんから、
NOT (S3.status = '空' AND S3.row_id = S1.row_id) = S3.status <> '空' OR S3.row_id <> S1.row_id
という条件になるわけです。この同値変形は、SQLで量化を扱うための必須技術ですから、スムーズにできるようにしてください。
これらのことから、形式言語ではEXISTSとFORALLの両方を明示的にサポートする必要がないことが分かる。だが、現実的には、両方をサポートしていることが非常に望ましい。なぜなら、EXISTSで表すほうが「自然な」問題と、FORALLで表すほうが「自然」な問題があるからだ。例えば、SQLはEXISTSをサポートするが、FORALLをサポートしない。結果として、SQLで表現しようとすると、非常にやっかいなクエリが存在する。（C.J.デイト）
SQLの基礎の1つ、述語論理には、量化子（限量子、数量詞）という特別な述語が存在します。これは、日本語で言えば「すべてのxが条件Pを満たす」、「条件Pを満たすxが（少なくとも1つ）存在する」という文を書くための道具です。前者が全称量化子、後者が存在量化子と呼ばれ、∀、∃と略記します。すぐにピンときた人もいるでしょうが、SQLの
EXISTS述語は、述語論理の存在量化子を実装したものです（まったく同等ではありませんが）。ところが、SQLはもう一方の全称量化子に対応する述語を持っていません。デイトは自分の本で
FORALL述語を導入していますが、現実のSQLにはありません。ただ、それでSQLの表現力が致命的に不足するかと言うと、そうでもないのです。というのも、全称量化子と存在量化子は、片方が定義されていれば、もう片方をそれによって表現できるからです。具体的には、次のような同値変形の規則（ド・モルガンの法則）があります。
∀xPx = ￢∃x￢Px （全てのxが条件Pを満たす = 条件Pを満たさないxが存在しない）
∃xPx = ￢∀x￢Px (条件Pを満たすxが存在する = 全てのxが条件Pを満たさないわけではない）
これで、なぜ上の問題で「すべての行が条件Pを満たす」という文を、SQLでは「条件Pを満たさない行が存在しない」へ変換する必要があったか、お分かりいただけたでしょう。デイトの言うようにSQLにも全称量化子があれば便利なのですが、こればかりは言語仕様なので仕方ありません。
述語論理と量化子についてさらに知りたい方は、参考文献に挙げた資料を参照してください。
