database-design - 1 つの次元内で範囲が重複しないデータ構造

Question

1 つのディメンション内で重複しない範囲を格納できるデータ構造が必要です。次元の全範囲を完全にカバーする必要はありません。

例としては、会議室のスケジューラーがあります。次元は時間です。2 つのスケジュールが重複することはありません。会議室は常にスケジュールされているわけではありません。つまり、特定の時間に存在できるスケジュールは最大 1 つです。

簡単な解決策は、範囲に開始時刻と終了時刻を格納することです。

Range {
    Date start
    Date end
}

これは正規化されておらず、コンテナが重複しないようにする必要があります。隣接する 2 つの範囲の場合、前の終了は次の開始と冗長になります。

別のスキームでは、各範囲に 1 つの境界値を格納する必要があります。ただし、範囲の連続したシーケンスでは、範囲よりも 1 つ多くの境界値が常に存在します。これを回避するには、シーケンスを交互の境界値と範囲として表すことができます。

B = 境界値、r = 範囲

ぶんぶん

データ構造は次のようになります。

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

本質的に、これは交互の型を持つ二重連結リストです。

最終的には、使用するデータ構造が何であれ、メモリ (アプリケーションコード) とリレーショナルデータベースの両方で表現されます。

学術的または業界が試みたソリューションが存在することに興味があります。

score 1 · Accepted Answer

重複しない間隔の場合は、開始点で間隔を並べ替えることができます。この構造に新しい間隔を追加すると、開始点と終了点がこの間隔セットに属していないことを確認できます。ポイント X が間隔セットに属しているかどうかを確認するには、バイナリ検索を使用して最も近い開始点を見つけ、X がその間隔に属していることを確認します。このアプローチは、変更操作には最適ではありません。
間隔ツリー構造を見ることができます-重複しない間隔の場合、最適なクエリと変更操作があります。

score 1 · Accepted Answer

運が良ければ (!) Postgres を使用できる場合は、tstzrange列を使用し、制約を適用して重複を防ぐことができます。範囲タイプを使用する利点は、開始が終了より大きくなるのを本質的に防止できることです。

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =);

CREATE EXTENSION IF NOT EXISTS btree_gist&& を使用した Gist の作成は、その拡張子なしではサポートされないため、必要になる場合があります。

score 1 · Accepted Answer

データを表す正規化された方法は、時間単位ごとにレコードを保存することです。これは、会議スケジューリングアプリケーションの例で行うことができます。あなたの制約は一意の制約になります

(RoomId, StartTime)

連続した範囲の場合、1 つの境界と 2 つ目の境界または長さの 2 つのものを格納する必要があります。これは通常、2 番目の境界を格納してから、その種類の両方の境界に制約を作成することによって行われます。

(boundary not between colBoudaryA and colBoundaryB)

追加の制約で

(startBoundary < endBoundary)

score 1 · Accepted Answer

二重にリンクされたリストは、範囲を満たした分だけメモリを使用するだけでよく機能し、挿入時にオーバーラップをチェックするだけで済みます。その時点でチェックするのはほとんど簡単です。重複がある場合、新しいアイテムは拒否されます。

ルームID
予約ID
前の予約ID
次の予約ID
開始日時
終了日時
優先順位
ユーザーID

優先度と UserID を使用すると、スケジュールに優先度を持たせることができ (教授は学生グループよりも影響力が大きい可能性があります)、挿入中に新しいアイテムが優先度の低いアイテムを邪魔にならないように「ノック」することができます。ぶつかった会議の主催者に送信されます。

検索を最適化できるように、毎日の最初の会議を指すテーブルを追加することを検討してください。

-アダム

score 0 · Accepted Answer

（データベースの世界では）重複しない範囲を決定するために複数の行を比較する必要があるため、これは重要です。明らかに、情報がメモリ内にある場合、時間順のリストなどの他の表現が可能です。ただし、リスト内であっても、「開始+終了」の表記が最適だと思います。

この主題に関する本全体があります-「時制データベース」の取り扱いの一部です。見ることができる2つは、Darwen、Date、Lorentzosの「TemporalData and the Relational Model」と（根本的に異なる極端な場合）「DevelopingTime-Oriented Database Applications in SQL」、Richard T. Snodgrass、Morgan Kaufmann Publishers、Inc.、サンフランシスコ、1999年7月、504 + xxiiiページ、ISBN1-55860-436-7。これは絶版ですが、彼のWebサイトcs.arizona.eduでPDFとして入手できます（したがって、Google検索で簡単に見つけることができます）。

関連するデータ構造の1つは、Rツリーだと思います。これは2次元構造によく使用されますが、1次元構造にも効果的です。

間隔については「 Allen'sRelations」を探すこともできます-それらはあなたに役立つかもしれません。

score 0 · Accepted Answer

これは、制約プログラミングの世界では「単項リソース」制約と呼ばれます。この分野では、特にイベントの時間が固定されておらず、それぞれの時間枠を見つける必要がある場合について、多くの研究が行われています。あなたの問題とより多くのIlog CPを実行する商用 C++ パッケージがありますが、それはやり過ぎの可能性があります。eclipseと呼ばれるややオープンソースのバージョンもあります(IDE とは関係ありません)。

score 0 · Accepted Answer

データをどう処理するかに大きく依存するため、どの操作を効率化する必要があります。ただし、Start と End のセッターにロジックを持つ Ranges の二重にリンクされたリストを検討して、現在隣接するものとオーバーラップしているかどうかを確認し、オーバーラップしている場合はそれらを縮小します (または例外をスローするか、試行を処理したい場合)重なります）。

これにより、予約された期間のリンクされた素敵でシンプルなリストが表示されますが、重複しないルールを維持する責任を負うコンテナーはありません。

score 0 · Accepted Answer

開始時間と期間の保存に成功しました。オーバーラップのテストは次のようになります

WHERE NOT EXISTS (
   SELECT 1 FROM table
   WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime
)
AND NOT EXISTS (
   SELECT 1 FROM table
   WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime
)

テストはしていないと思いますが、ドリフトを理解していただければ幸いです

database-design - 1 つの次元内で範囲が重複しないデータ構造

8 に答える 8

Related

Reference