SQL进阶-10-SQL处理序列

SQL进阶-10-用SQL处理数列

在关系型数据库的数据结构中，默认是不考虑数据的顺序。处理有序集合在SQL中不能直接实现，但是可以通过集合和谓词来间接实现处理有序数据的需求。

重要的知识点：用存在量化的否定形式来解决全称量化问题

需求1-生成连续编号

需求

不使用数据库中自带的函数，实现任意长的连续编号序列，比如生成0-99的100个连续编号

SQL实现

先解决一个问题：00-99这100个数字中，0，1，2……9这10个数字分别出现了多少次？

从下面的表中可以明显看出来：每个数字出现了20次

生成一个digits表，用来存储各个数位上的数字，因为不管多大的数字都可以由0-9这10个数字组成

通过对两个Digits集合求笛卡尔积得出0-99的数字

1
2
3

select D1.digit + (D2.digit * 10) as seq  -- 两位数
from Digits D1 cross join Digits D2  -- 两个集合的笛卡尔积
order by seq  -- 排序

什么是笛卡尔积

通过交叉联结求出集合的笛卡尔积：实现所有可能的组合

需求2-生成1-542的编号

select  D1.digit + (D2.digit * 10) + (D3.digit * 100) as seq
from Digits D1 cross join Digits D2 cross join Digits D3
where D1.digit + (D2.digit * 10) + (D3.digit * 100)
between 1 and 542   -- 可以指定任意数字
order by seq;

生成视图调用

-- 事先将结果生成视图，方便后续调用
create view Sequence (seq)
as select D1.digits + (D2.digits * 10) + (D3.digits * 100)
from Digits D1 cross join Digits D2 cross join Digits D3;

-- 后续调用
select seq
from Sequence
where seq between 1 and 100
order by seq;

需求3-求解全部的缺失值

如何从已知的序列中求出全部的缺失值？我们借助上面生成的视图：

-- except版本

select seq
from Sequence  -- 上面生成的视图
where seq between 1 and 12
except select seq from Seqtab1;   -- 排除从已知表中查询的seq

-- not in 版
select seq
from Sequence
where seq between 1 and 12
and seq not in (select seq from Seqtab1);   -- 不在查询的seq中

-- 动态地指定连续编号范围的SQL语句
select seq
from Sequence
where seq between (select min(seq) from Seqtab1) and (select max(seq) from Seqtab1)
except select seq from Seqtab1

火车问题-连续空位

我们假设3个人一起去旅行，准备预订这列火车的车票，要求是从1-15号的座位中选择出连续的3个空位置，我们把连续的整数构成的集合称之为序列，这样的序列中不能出现缺失的编号。

满足要求的序列：

根据上面的图形，我们发现满足要求的序列：以n为起点，n+(3-1)=n+2为终点的作为全部是未预定状态

SQL实现-不考虑换排

-- 不考虑换排

select
	s1.seat as start_seat
	,"~"
	,s2.seat as end_seat
from Seats s1, Seats s2
where s2.seat = s1.seat + (:head_cnt - 1)   -- 1、决定起点和终点
and not exists (select * from Seats s3   -- 2、不存在“不是未预定的状态”：全部都是“未预定”的状态
               where s3.seat between s1.seat and s2.seat
               and s3.status <> "未预定");

:head_cnt表示需要的空位个数的参数，通过给参数赋值能够应对任意多个人的预约。上面代码的主要工作：

找到起点和终点
起点和终点之间的座位都是未预定的状态

全称量化问题：将所有满足条件P转成不存在不满条件P的行

SQL实现-考虑换排

给表中的数据加上了行编号row_id

因为发生换排，9,10,11不再符合要求。因此，为了解决换排问题，需要保证：全部都在同一排

-- 考虑换排

select
	s1.seat as start_seat
	,"~"
	,s2.seat as end_seat
from Seats s1, Seats s2
where s2.seat = s1.seat + (:head_cnt - 1)   -- 1、决定起点和终点
and not exists (select * from Seats s3   -- 2、不存在“不是未预定的状态”：全部都是“未预定”的状态
               where s3.seat between s1.seat and s2.seat
               and (s3.status <> "未预定"   -- 3、全部都是未预定
                    or s3.row_id <> s1.row_id  -- 4、在同一排：和起点的行号相同
                ));

肯定等于双重否定

火车问题—最多坐几个人

按照空位的问题，最多能够坐下几个人：求出最长的序列。下图中的2-5号就是满足要求的

要保证从座位A到座位B全部是未预定的状态，必须满足3个条件：

起点和终点之间的所有座位都是未预定状态
起点之前的座位不是未预定（不能往前延伸）
终点之后的座位不是未预定（不能往后扩展）

SQL实现

生成所有序列的视图：存在量化的否定形式来表达全称量化

-- 1、创建视图
create view Sequence (start_seat, end_start, seat_cnt) as  -- 1、创建视图
select s1.seat as start_seat,
			s2.seat as end_seat,
			s2.seat - s1.seat + 1 as seat_cnt   -- 2、起点和终点间的个数
from Seats s1, Seats s2
where s1.seat <= s2.seat   -- 3、起点小于终点
and not exists(select * from Seats s3   -- 全称量化：双重否定
               where (s3.seat between s1.seat and s2.seat    -- 4、条件1的否定
                     and s3.status <> '未预定')
               or (s3.seat = s2.seat + 1 and s3.status = "未预定")  -- 5、条件3的否定
               or (s3.seat = s1.seat - 1 and s3.status = '未预定')  -- 6、条件2的否定
              );

求出最长的序列：

1
2
3

select start_seat,'~',end_seat,seat_cnt
from Sequences  -- 视图
where seat_snt = (select max(seat_cnt) from Sequences);   -- 最大值