likes
comments
collection
share

考位分配的空洞考位查询和处理

作者站长头像
站长
· 阅读数 3

这是一个有趣的SQL思想实验。希望有人能够理解和感兴趣。

基本设定和概念

情况是这样的，这里有一个统一的考试座位分配系统，有一个需求是检查排位后，有没有按照规则空余的座位。

我们稍微抽象和简化一下，这个系统里面包含有这么几个要素：

  • 考生(Student)：

相关核心的属性就是两个，考生STUID和考生的准考证编号EMID。为了简单和规范起见，这个EMID就是由考点ID、考场ID和座位ID构成。本质上就是这个考生，在此次考试当中的座位编码。

  • 考点(Site)：

学生在考试之前，会被预先分配到某个考试点，在现实中可能就是一个学校。但应该不能确定他会被分配到某个考场的某个座位。

  • 考场(Room)：

基于管理的要求和方便，考点可以提供多个考场，在现实中，考场可能就是一个教室，学生在教室中的座位上实际参加和完成考试。逻辑上而言，一个考点中，所有的考场能够提供的考位数量，应该大于该考点中参考考生的人数。

  • 考位(Seat)：

每个考场提高一定容量的座位来容纳考生考试。在一个考点中，每个考场的容量可以不同。在考场中的座位使用简单整数进行顺序编码，如考场容量为30，就可以提供从1到30号的考位。

  • 分配规则(Rules)：

学生在考点中，在那个考场的那个座位参加考试，原则上是随机的，不需要特地安排。但为了管理方便，在实际安排考位的时候，应该按照考场的编号顺序安排。

  • 尾考场(TailRoom)

这样就会造成一个情况，在一个考点中，对于一个有序的考场列表，会按照次序进行编号，最后只会出现一个考场，考生数量不足的情况，这个考场被称为“尾考场”。

  • 尾编号(TailID)

在给学生编号时，尾考场中的学生可能没有填满，编到最后的那个座位的编号，显然就是“尾编号”

  • 编号规则

在此场景中，一个合规的考号的编码规则为 三位考点编码+三位考场编码+2位座位编码，原始数组都是整数，编码时在前面补零。

  • 数据模型

简化的数据模型，包括：

学生表(stuid,stid,emid)，初始情况下emid为N，代表未编码；stuid为主键不重复。

考场表(stid,roomid,rsize)，stid+roomid为联合主键，不重复。

考位安排

符合规则的考位安排的基本过程如下：

1 对考点内的考生，进行随机排序

2 对随机排序后的考生，按照考场的顺序，和考场内座位的顺序，依次排位

3 直到所有的考生都排位完成，最后的那个考生的考位就是该考点的尾编号

结合多个考点的安排，在整个系统和所有参考学生中，进行考位安排的SQL伪代码如下：


with 
S as (
select stuid, stid || '-' || row_number() over (partition by stid order by random()) rn1 from emstus where EMID = 'N'),
N1 as (
select stid, LPAD(stid::text,3, '0') || LPAD(rmid::text,3, '0') || LPAD(generate_series(1, rsize )::text,2,'0') SeatID  from exrooms),
N as (
select N1.stid::text || '-' ||row_number() over (partition by N1.stid order by seatid) rn2, SeatID from N1 left join emstus on emid = SeatID where emid is null ),
U as (
select S.stuid s1, SeatID from S join N on rn1 = rn2)
--select * from U;
update emstus set EMID = SeatID from U where stuid = s1 and EMID = 'N'
returning *;

简单说明如下：

  • S是未编码考生数据集，字段分别是考生ID，考点+随机排序后在考点分组中的序号(RN1)，作为一个临时ID，过滤条件是SeatID为"N"(默认编码)
  • N1是所有考位的编码，来自考点-考场-考场容量的组合
  • N是所有可用考位的编码，通过N1和考生表的联合查询，找到未匹配学生考号的那些编码，结果字段分别是完整考位编号，考点+在考点中的序号作为临时ID(RN2)
  • U是编码使用参考的临时表，通过RN对S和N进行强制关联，得到考生ID和可用编码的对应关系
  • 使用U对考生表的考号进行更新

如果是从初始状态开始，一次性编码，这种处理方式，是没有问题的，完全可以满足所有非尾考场，所有座位都能安排考生，尾考场，可以按照编号顺序安排考生的需求。

现在需要处理的问题，就是如果进行了调整，比如中间某个考生的数据错误，或者需要安排到其他考点，他现在的考位编号就会被空出来，出现了所谓的“空洞考位”。我们下面来讨论这种情况的处理。

处理空洞

出现空洞考位的时候，显然已经违反了排位的基本原则。但这时，大部分排位已经完成，这时如果全部重排，会造成比较大的影响。这时我们只希望做一个小的调整，尽量减少这一调整的影响面。一个简单的思路，就是将尾编号那个学生的考号，重新编为那个空位的编号，这时的操作只会影响一个人。

解决这个问题，首先需要找到那个“空洞”。

先看代码，再进行分析说明如下：


with 
N1 as (
select stid, LPAD(stid::text,3, '0') || LPAD(rmid::text,3, '0') roomid1, rsize  from exrooms),
C as (
select stid, emid, substring(emid,1,6) roomid2, substring(emid,7,2)::int rsize2 from (
select stid, emid, row_number() over (partition by stid order by emid desc) rn from emstus where emid <> 'N'
) N where N.rn = 1),
A as ( select emid2 from (
select N1.roomid1 || LPAD(generate_series(1,coalesce (rsize2, rsize)::int)::text,2,'0') emid2 from N1 left join C on roomid1 = roomid2 where rsize2 is not null
) A1 left join emstus on emid2 = emid where emid is null
) 
select * from C left join A on C.roomid2 = substring(emid2,1,6) where emid2 is not null limit 1;
  • N1找到所有考场的名义容量
  • C找到每个考点的尾编号，及其对应的考场，就是尾考场，这个检索基于所有已编码考生
  • 对于尾考场，将其容量改为尾编码对应的数值
  • 按照每个考场的容量，包括修改后尾考场的容量，生成所有应使用过的编码列表
  • 使用此编码列表，链接对照考生编码列表，得到未使用的编码，就是空洞
  • 可以基于空洞的编码，进一步检索其对应考点的尾编码
  • 将尾编码对应的考生编码，更新为空洞编码
  • 为了简化操作，一次只检索和更新一个空洞记录，循环执行直到找不到空洞记录
  • 这些操作都可以使用SQL，无需借助外部程序

文中涉及到的PG技术

本文中，相关涉及到的一些比较重要的postgres数据库操作技术包括：

  • CTE(Common Table Express，公共表表达)

这是一个可以使用查询语句，构造一个临时的记录集，并在后续的查询或者处理中使用的操作方式。PG提供CTE的功能功能强大而丰富，它可以链接(多个CTE)或者嵌套使用(在CTE中使用前面声明的CTE)。在开发实践中，CTE有助于将复杂问题分解，逐步操作和实现，明确和清晰处理的思路和流程。

  • Genarate Serise() 生成序列

Generage Serise可以用于生成一个值序列，当用在查询子句中时，它可以生成一个有序的记录集，是用于构造一些临时数据时经常使用的一种方法。

  • row_number() 记录行编号

这是一种窗口函数。用于在分组中得到在分组中的序号。和窗口函数结合使用的通常是分组方法over( partition by ... order by ...) ，还可以定义在分组内的排序方法。结合排序和嵌套函数，可以取得每个分组中的第一条记录(本文中用于获取尾编码)。

  • lpad()方法

字符串补足函数，其参数包括补足后的长度和补足使用的字符，经常用于构造固定长度的编码字符串。lpad是在左边补足，同样还有rpad用于右边补足。

lpad接收三个参数，要补足的字符串，补足长度和补足用的字符，比如"0"。如果要处理非字符串如数字，需要先转化为字符串。

  • substring() 字符串切割

对于有编码规则的字符串而言，字符串其实就是一系列有意义编码的集合，而要将这些部分的编码，从整体编码中提取出来，必须使用字符串切割方法。

PG的substring()方法接收三个参数，要切割的字符串、开始位置和切割长度，返回就是切割后的子字符串。

  • random() 随机数生成

random()可以用来生成一个随机数，它是一个在0和1之间的小数。用它可以来构造一些随机数值。我们这里使用它来实现随机排序，就是使用随机数作为排序的依据，排序后可以获得随机的排序结果。

  • 子查询(Subquery)

对于比较简单的嵌套查询，可以不使用CTE，而直接使用子查询。它的模式为 select from (select ...) Q where...。需要注意子查询必须提供一个别名。简单子查询的一个常用场景就是整理窗口函数的查询结果，如获得每个窗口分段的第一条记录。

  • 表连接过滤(join)

合理的使用表连接结合查询条件，可以用来过滤数据集合。常用的就是获取两个集合的交集和差集。

  • coalesce (rsize2, rsize)::int)

coalesce这个词是“合并”的意思。从功能上来看，它的作用是接受一系列参数的值，返回其中第一个非NULL的值。使用它可以实现“如果为空，则返回某个值”的效果。本文中，使用此方法来处理如果是尾考场，返回尾编号的值；否则返回考场容量，这样一个业务需求。

  • concat 连接字符串

Postgres支持使用concat方法来连接多个字符串，也可以使用"||"操作符来完成这个需求，本文中使用了后者，更直观一点。

  • 关联更新

使用一个记录集，作为参照条件，来更新记录。本文中就是先构造学生对应的可以使用的学号的临时记录集，然后使用考生ID进行关联后进行的更新。关联更新的语法通常为 update set x = y from where ....。

特点和不足

本文中探讨的处理方案，有比较强的灵活性和适应性。首先，这是一个纯SQL数据操作，不需要外部应用程序来处理，也不需要编写和调用存储过程；第二，这个操作考虑比较多的情况，可以重复的执行，而且后续执行不影响前面操作的结果，而且尽量符合编码规范；第三，可以方便的重置并且重新执行，没有太多限制条件。

由于SQL执行本身收到的限制，遇到多个空洞时，不能处理所有的情况，为处理简单起见，从尾号开始进行的漏洞填补，一次只能处理一条。当需要修正的记录数量较大时，效率比较低。

补充内容： 回避规则

对于一些对考试纪律和安全要求更高的场合，可能会有这样一个需求，就是特定属性的考试，不能被安排在临近的座位。这个需求看起来比较简单，但如果真的使用信息系统实现，需要考虑很多因素。

为了简化讨论，我们先来考虑一个比较常见的规则，就是同一个班的学生，不能被分派到相邻的座位。同一个班的意思是，每个学生都有一个班级代码的属性，这个代码相同，则认为他们同班，这个信息来源于其他信息系统，或者需要手动设置；相邻的座位，我们也简化一下，就是考场中的座位安排，必须是一个MxN的矩形，所谓相邻就是这个座位的前后左右四个位子，如果靠边角可以忽略。

针对上面的设定，笔者可以从抽象的角度来思考这个问题，提出以下的一个处理思路：

1 我们可以针对每一个考场，通过斜向遍历的方式，间隔分成两个部分，遍历计算所有考场，得到两个考号的集合

2 在考点范围内，将所有的考生，按照他们的班级，尽量分在两个大组里面

3 对两个考生集合，在两个考号集合内，进行顺序安排，直到所有考生都得到对应的考号

最后，笔者想要强调一点的是，由于这些规则的限制，可能对于一些特定的数据集合，完全符合规则的编排方案，可能在数学和理论上是无解的。但理论上而言，只要能够提供足够多的考场和考位，就可以在一些考位空缺的情况下，满足这一需求，从而提供一个通用的方案。

小结

本文谈到了使用SQL进行考场座位编码处理的过程和方式，其中涉及到很多Postgresql的技术运用，无论对于学习、思考和实践，都是很好的参考材料。