述語論理をつかったSQL

はじめに

僕は、SQLが苦手である。 普段使い慣れている言語とは別の考えがSQLには必要なのであろうと痛感している。

ということで、達人に学ぶ SQL徹底指南書を使って最近SQLの考え方を学習中。
今回は、SQLで数列を扱うの備忘録を残す。

達人に学ぶ SQL徹底指南書 (CodeZine BOOKS)

問題

以下の座席表から空席が 3 つ連続している部分を求めろ たとえば、(3,4,5), (7,8,9)となる。

id	status
1	占
2	占
3	空
4	空
5	空
6	占
7	空
8	空
9	空
10	空
11	空
12	占
13	占
14	空
15	空

データの準備

CREATE TABLE seats
(
    seat   INT NOT NULL,
    status VARCHAR(10),
    PRIMARY KEY (seat)
);

INSERT INTO seats
VALUES (1, "占"),
       (2, "占"),
       (3, "空"),
       (4, "空"),
       (5, "空"),
       (6, "占"),
       (7, "空"),
       (8, "空"),
       (9, "空"),
       (10, "空"),
       (11, "空"),
       (12, "占"),
       (13, "占"),
       (14, "空"),
       (15, "空");

回答

SELECT
  s1.seat as '始点',
  s2.seat as '終点'
FROM seats s1,
     seats s2
WHERE s1.seat + 2 = s2.seat
  AND NOT exists(
        SELECT * FROM seats s3 WHERE (s3.seat BETWEEN s1.seat AND s2.seat) AND (s3.status <> '空')
    );

始点	終点
3	5
7	9
8	10
9	11

考え方

始点、終点を s1, s2 の自己結合によって得、その間に s3 のすべての status が空を満たすというクエリをつくる方針をとる。

すべての〇〇が XX という条件を満たすというクエリを記述するのにAll演算子を使おうと考えるが、MySQLにはAll演算子は用意されていない。

なので、EXSITS演算子を利用して All と同じ意味をもつ式を記述することになる。
いきなりだが、以下は述語論理から成立する式である。

1. ∀xF(x) => ¬∃x¬F(x)
2. ∃xF(x) => ¬∀x¬F(x)

∀ は All を意味するので、今回は 1 のパターンである。
この考え方を日本語で整理すると、
始点・終点間のすべての座席が空である
は
始点・終点間に空ではない(a)座席は存在しない(b)
と表現可能となる。

(a), (b)をクエリで記述すると

1. SELECT * FROM seats s3 WHERE (s3.seat BETWEEN s1.seat AND s2.seat) AND (s3.status <> '空')
2. NOT exists(1.)

となる。

よって、上記回答の通りになる。

おわりに

にしてもSQLはクエリに悩むよりも、データの準備が大変だ。。。 もっと楽にデータ準備できないものかと感じる