从12306改签困惑到数据库设计——高铁随记

wabjtam123

从12306改签困惑到数据库设计——高铁随记

12306业务系统升级也能被普通人推动？

L老师准备去北京参加DTCC大会，便预订了从福州到北京的G302次高铁票。临时有事，L老师尝试将G302（7:23出发）改签到G322（9:14出发），结果发现系统提示G322"售罄"，无法完成改签。

实际情况是如果系统支持车内分段分配新座位，L老师是可以顺利完成全程订票。然而，现有系统只能查询和分配全程相同的座位，无法识别这种分段组合的可能性。

L老师很无奈的放弃了改签，被迫保持原定行程，于是在车上写下了“高铁随记”，故事就从这里开始。

我们把福州到北京的路线简化为只分四段，路线：福州 → 杭州 → 南京 → 北京，同时把车厢也限制在仅有10号车厢。

心有不甘的L老师经过查询，发现了一些玄机，

10车13F：福州至杭州空闲，杭州至南京已售，南京至北京空闲 10车07C：福州至杭州已售，杭州至南京空闲，南京至北京空闲

发现玄机了，实际上是有可行的座位组合的：

福州到杭州坐10车13F 杭州到南京换到10车07C 南京到北京可以回到10车13F或继续坐10车07C

这意味着，如果系统支持分段分配新座位，是可以完成全程订票的。然而，现有系统只能查询和分配全程相同的座位，无法识别这种分段组合的可能性。于是L老师放弃了，继续乘坐原来的G302（7:23出发）。

当然了，理论上L老师是可以买一张福州到杭州的车票，再购买杭州到北京的车，不过L老师觉得麻烦，也就算了。其实如果12306允许自动给乘客分段分配座位（即到不同的站换不同的座位），问题就可以解决。那该怎么实现呢？

wabjtam123

最简模型设计与SQL实现
我们可以做一个最小化的例子来示例说明一下该如何实现，以下是最简化的设计说明，实际情况当然远比这要复杂的多！

首先，创建表：

CREATE TABLE TRAIN_SEATS (
    SEAT_ID NUMBER PRIMARY KEY,
    TRAIN_ID VARCHAR2(10),
    CAR_NO NUMBER,
    SEAT_NO VARCHAR2(3),
    SEGMENT NUMBER,
    STATUS VARCHAR2(10)
);
插入示例数据：

INSERT INTO TRAIN_SEATS VALUES (1, 'G322', 10, '13F', 1, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (2, 'G322', 10, '13F', 2, 'OCCUPIED');
INSERT INTO TRAIN_SEATS VALUES (3, 'G322', 10, '13F', 3, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (4, 'G322', 10, '07C', 1, 'OCCUPIED');
INSERT INTO TRAIN_SEATS VALUES (5, 'G322', 10, '07C', 2, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (6, 'G322', 10, '07C', 3, 'AVAILABLE');
以下是SQL实现的代码，具体如下。
WITH AVAILABLE_SEATS AS (
    SELECT
        CAR_NO,              -- 车厢号
        SEAT_NO,             -- 座位号
        SEGMENT,             -- 行程段（1：福州到杭州，2：杭州到南京，3：南京到北京）
        STATUS,              -- 座位状态
        ROW_NUMBER() OVER (
            PARTITION BY SEGMENT
            ORDER BY CAR_NO, SEAT_NO
        ) AS RN               -- 为每个行程段的可用座位分配一个**的行号
    FROM TRAIN_SEATS
    WHERE TRAIN_ID = 'G322'   -- 只选择G322列车的座位
    AND STATUS = 'AVAILABLE'  -- 只选择可用的座位
)
SELECT
    CASE
        -- 如果三个行程段都有可用座位，则可以全程乘坐
        WHEN COUNT(DISTINCT SEGMENT) = 3 THEN '可以全程乘坐'
        -- 如果至少有一个行程段有可用座位，则需要换座
        WHEN COUNT(DISTINCT SEGMENT) >= 1 THEN '需要换座'
        -- 如果没有任何可用座位，则无法完成行程
        ELSE '无法完成行程'
    END AS TRAVEL_PLAN,
    -- 使用LISTAGG函数将所有可用座位信息连接成一个字符串
    LISTAGG('段' || SEGMENT || ':' || CAR_NO || '车' || SEAT_NO || '座', ' -> ')
    WITHIN GROUP (ORDER BY SEGMENT) AS SEAT_ARRANGEMENT
FROM AVAILABLE_SEATS
WHERE RN = 1  -- 只选择每个行程段的第一个可用座位
GROUP BY RN;  -- 由于RN总是1，这里的GROUP BY实际上是将所有结果合并成一行

具体实现结果如下所示：

TRAVEL_PLAN | SEAT_ARRANGEMENT
------------+--------------------------------------------------
需要换座     | 段1:10车13F座 -> 段2:10车07C座 -> 段3:10车07C座

newkid

提一个有趣的扩展问题：如何安排能够使得换座的次数最少？大家可以构造一些例子来测试一下！
简单例子：把楼主的座位号改一下
INSERT INTO TRAIN_SEATS VALUES (1, 'G322', 10, '13F', 1, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (2, 'G322', 10, '13F', 2, 'OCCUPIED');
INSERT INTO TRAIN_SEATS VALUES (3, 'G322', 10, '13F', 3, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (4, 'G322', 10, '27C', 1, 'OCCUPIED');
INSERT INTO TRAIN_SEATS VALUES (5, 'G322', 10, '27C', 2, 'AVAILABLE');
INSERT INTO TRAIN_SEATS VALUES (6, 'G322', 10, '27C', 3, 'AVAILABLE');


预期结果只需换一次：
段1:10车:13F->段2:10车:27C

〇〇

换座走的路也尽量短

〇〇

看到了 ROW_NUMBER() OVER (             PARTITION BY SEGMENT              ORDER BY CAR_NO, SEAT_NO

sql_tigerliu

梁老师的写法逻辑上可能有点问题, 我先按照梁老师的逻辑写一个分步的操作:

--首先检查能不能不需要换座,如果可以, 列出所有可用座位:
SELECT
        CAR_NO,              -- 车厢号
        SEAT_NO,             -- 座位号
FROM TRAIN_SEATS
WHERE TRAIN_ID = 'G322'   -- 只选择G322列车的座位
AND STATUS = 'AVAILABLE'  -- 只选择可用的座位
group by car_no,seat_no
having count(*)=3         -- 全部3段都有相同空余座位
;

--如果没有直达座位,再看看是否能换座,如果能,给出其中一种换座组合:
select one_method from
(
SELECT
      listagg(segment||':'||min(car_no||'-'||seat_no),'-->') within group (order by segment) one_method
      ,count(segment) cnt
FROM TRAIN_SEATS
WHERE TRAIN_ID = 'G322'   -- 只选择G322列车的座位
AND STATUS = 'AVAILABLE'  -- 只选择可用的座位
group by segment
)
where cnt=3
;

这样可以避免使用复杂的分析函数(用一个SQL实现), 逻辑相对也更清晰一些.
如果要实现换座次数最少, 走动距离最小, 那算法就更复杂了

newkid

换座次数最少：
解题思路非常的直观，就是挑选那些尽可能连续多坐几个路段的座位。不存在那种坐得更短，最终结果反而更优的情况，因为即使是连续路段的座位，你也是可以从中间换的。
例如座位A可以坐1,2,3,4段，座位B可以坐3,4,5,6段，那么在3或4换座位都不会影响结果。
把这些连续段座位找出来之后，就可以用它们来拼出整个旅程。每个段只需留下一个坐得最远的座位就可以了，其他都不用考虑，这样在拼整个旅程的时候工作量就很小。

newkid

上述思路用SQL实现如下，找连续路段可以用经典的断点求和分组方法，也可以用match_recognize

with
available as (
  select *
    from train_seats
   where train_id = 'G322' and status = 'AVAILABLE'
         ---- and  segment between 开始 and 结束  ----- 如果对旅程路段有要求就写在这里
)
,s as ( ---- 这个子查询找出从每个段出发能够坐得最远的那些座位, 假设路段segment都是连续的正整数
select *
from (
   select t.*
         ,row_number() over(partition by first_segment order by cnt desc) rn  ---- 每个段只需留下能坐得最长的一个座位
    from available
    match_recognize ( ----- 识别出每张票最多能连续坐几段
    partition by car_no,seat_no
    order by segment
    measures
        min(segment) first_segment
       ,max(segment) last_segment
       ,count(*) cnt
    one row per match
    pattern (strt a*)
    define a as segment=prev(segment)+1
    ) t
  )
where rn=1 ------ 这个筛选过后数据已经很少了，每个路段最多留下一行数据，递归的工作量很少
)
,t(last_segment,path,rn) as ( ---- 执行递归SQL，利用上述结果拼出完整的行程
select last_segment
      ,'段'||first_segment||':'||car_no||'车:'||seat_no
      ,1
  from s
where first_segment=1  ---- 假设旅程开始段从1开始，也可以修改
union all
select s.last_segment
      ,t.path||'->'||'段'||first_segment||':'||s.car_no||'车:'||s.seat_no
      ,row_number() over(order by s.last_segment desc) rn ----- 那些拼上去的座位按终点路段排序找出最远的
  from t,s
where t.rn=1  ----- 只需留下能够走得最远的那一个座位
       and s.first_segment<=t.last_segment+1 and s.last_segment>t.last_segment
)
select path
from t
where rn=1
       and last_segment=3 ---- 终点路段为3，可以根据需求修改
;

wabjtam123

newkid 发表于 2024-9-26 21:33
上述思路用SQL实现如下，找连续路段可以用经典的断点求和分组方法，也可以用match_recognizewith available ...

newkid兄，昨天我想起那车内换座扩展的有趣思路，还和我弟探讨了一下，我们大致想到取连续数再并在一起的方案，在想怎么写，还想如果SQL搞不定，至少存储过程分步骤做肯定是可以的，结果登进来一看，newkid兄不但给了思路，连代码都写出来了，厉害啊！我忽然有一个想法，咱们再发公众号，写12306的第三集。把ITPUB的链接放上去，将newkid兄的思路分享出去，让更多人知道newkid大神的厉害，给业界年轻人一个学习榜样。另外也想告诉大家，国产数据库还是和Oracle有差距的，比如measures就没有。还有就是之前的SQL有逻辑错误，我漏了一个判断，正好也在第三集里提一下。

newkid

期待你妙笔生花，再写出一篇精彩的文章！

最近我是迷上了match_recognize这个新玩具，其实用在这里优势并不是很明显。很多老工匠还喜欢用ROW_NUMBER()的差额来求连续段，其原理是构造一个从1开始的连续序号，用这个序号和目标列进行相减，如果目标列是连续的话，这个差值就是一个恒定的数；假如目标列有断点，那么这个差值就会变成另外一个数字。用这个差值来进行分组就可以得到连续段。示意如下：

row_number()    segment    segment-row_number()
------------------------------------------------
1               3          2
2               4          2
3               5          2
4               8          4      ------- segment的断点导致差值发生变化
5               9          4
6               10         4

另外，在拼完整旅程的时候，也可以用CONNECT BY而不是递归WITH。这样用“传统”的SQL写法写出来就是：

with
available as (
  select train_seats.*
        ,segment-row_number() over(partition by car_no,seat_no order by segment) as grp_id --- 连续序号的差值作为分组依据
    from train_seats
   where train_id = 'G322' and status = 'AVAILABLE'
         ---- and  segment between 开始 and 结束  ----- 如果对旅程路段有要求就写在这里
)
,s as ( ---- 这个子查询找出从每个段出发能够坐得最远的那些座位, 假设路段segment都是连续的正整数
select * from (
select car_no,seat_no
       ,min(segment) first_segment
       ,max(segment) last_segment
       ,count(*) cnt
       ,row_number() over(partition by min(segment) order by count(*) desc) rn  ---- 每个段只需留下能坐得最长的一个座位
from available
group by car_no,seat_no,grp_id
  )
where rn=1 ------ 这个筛选过后数据已经很少了，每个路段最多留下一行数据，递归的工作量很少
)
select * from (
select sys_connect_by_path('段'||first_segment||':'||car_no||'车:'||seat_no,'->') as path
      ,level as change_count
  from s
where last_segment=3 ---- 终点路段为3，可以根据需求修改
start with first_segment=1
connect by first_segment<=prior last_segment+1 and last_segment>prior last_segment
order by level
)
where rownum=1;