読者です 読者をやめる 読者になる 読者になる

ネットの海の片隅で

技術ネタの放流、あるいは不法投棄。

排他的リソースに対するスケジュールの重複判定をSQLでシュッとやる

突然ですが、排他的にしか利用できないリソースに対するスケジュールの重複判定の問題を考えてみようと思います。 典型的には「ある会議室では同時に複数の会議を開催できない」というようなスケジューリングの問題です。

ある既存のスケジュールを下の図のピンクで示します。

すると、そこに対して新規にスケジュールを追加するときのパターンは既存のスケジュールの始点と終点のまたぎ方によって分けられ、黄色と青色を合わせて全部で6パターンあります。 *1

f:id:s_osa:20161126233115p:plain

このうち、黄色はピンクと重複している部分があるもの(invalidなスケジュール)、青色は重複していないもの(validなスケジュール)です。

新規に追加するスケジュールがinvaidな黄色の場合にエラーを返したいのですが、4パターンもあって場合分けが大変そうです。

というわけで、青色のパターンから考えます。

青色になる条件

黄色と違って、青色になる条件は比較的簡単です。

  • 新規追加するスケジュールの終点が既存のスケジュールの始点よりも前にある
  • 新規追加するスケジュールの始点が既存のスケジュールの終点よりも後にある

のいずれかですね。

したがって、新規追加するスケジュールの始点と終点をそれぞれSn, En、既存のスケジュールの始点と終点をそれぞれSe, Eeとすると、青色になる条件はEn < Se OR Sn > Eeとなります。

黄色になる条件

青色になる条件がわかったので、元々求めたかった黄色になる条件を求めます。

新規追加するスケジュールは黄色か青色のいずれかになるので、青色にならなければ黄色です。

したがって、さっき調べた青色になる条件を使うとNOT (En < Se OR Sn > Ee)と書けます。

ド・モルガンの法則を使って変形するとNOT (En < Se) AND NOT(Sn > Ee)

もう一歩整理してEn > Se AND Sn < Eeです。

シンプルになりました。

SQL

この条件を使って、これから挿入しようとするスケジュールが既存のスケジュールと重複していないかどうか調べるSQLを書くことができます。 *2

select
  *
from
  rooms
  inner join events on rooms.id = events.room_id
where 
  roooms.id = ROOM_ID
  and En > events.start_at
  and Sn < events.end_at
;

さいごに

このような重複判定をApp側で複雑に場合分けしてバリデーションしていたコードがあったのでこのエントリを書きました。

手続きで温かみある感じではなく、スパッと宣言的に判定していきたい気持ちです。

*1:議論が煩雑になって面倒なので、ここでは境界値を含むことはないこととします。

*2:テーブル定義はなんとなく察してください。