2

これは小さなスケジューリングアプリ用です。2つの「スケジュール」を効率的に比較し、違いを見つけ、変更されたデータ行と、このテーブルを外部キーとして持つ別のテーブルのエントリのみを更新するアルゴリズムが必要です。これは大きな質問なので、すぐに一般的なアドバイスまたは具体的な解決策を探していると言います。

編集：提案されたように、私は質問を大幅に短縮しました。

1つの表では、リソースが使用される期間にリソースを関連付けています。

また、テーブルAのIDを外部キーとして使用する2番目のテーブル（テーブルB）もあります。

表Bに対応する表Aのエントリには、表Bの期間を含む期間があります。表Aのすべてのエントリに表Bのエントリがあるわけではありません。

ユーザーがテーブルAのリソーススケジュールを編集するためのインターフェイスを提供しています。これらは基本的に、DB内のバージョンとの差分として扱う必要があるテーブルAの新しいデータセットを提供します。

テーブルBが指すオブジェクトをテーブルAから完全に削除する場合は、テーブルBからもエントリを削除します。

したがって、次の3つのセットが与えられます。

  • 表Aの元のオブジェクト（DBから）
  • 表Bの元のオブジェクト（DBから）
  • 表Aから編集されたオブジェクトのセット（ユーザーからのものであるため、一意のIDはありません）

次のようなアルゴリズムが必要です。

  • これらのオブジェクトに変更が必要ない場合は、表Aと表Bの行を変更しないでください。
  • 必要に応じて、テーブルAに行を追加します。
  • 必要に応じて、テーブルAとテーブルBから行を削除します。
  • 必要に応じて、テーブルAとテーブルBの行を変更します。

適切なデータベース操作を適用できる配置にオブジェクトを並べ替えるだけで、ソリューションには十分すぎるほどです。

繰り返しになりますが、具体的または一般的に好きなように答えてください。アドバイスを探していますが、誰かが私の一日を作る完全なアルゴリズムを持っている場合。:)

編集： lassvekに応えて、私はいくつかの追加の詳細を提供しています：

テーブルBのアイテムは、単に重複するのではなく、常にテーブルAのアイテム内に完全に含まれます。

重要なのは、表Bの項目は量子化されているため、完全に内側または完全に外側に収まる必要があるということです。これが発生しない場合は、データ整合性エラーが発生しているため、個別に処理する必要があります。

例（省略形を使用する場合）：

表A
IDリソース開始終了
01リソースA10/67:00 AM 10/6 11:00 AM
02リソースA10/61:00 PM 10/6 3:00 PM

表B
IDTable_A_ID開始終了
01 02 10/6 1:00 PM 10/6 2:00 PM

したがって、次の動作が必要です。

  • テーブルAからID02を削除するか、午後2時から午後3時に短縮する場合は、テーブルBからID01を削除する必要があります。
  • テーブルAID01を午後1時に終了するところまで拡張すると、これら2つのエントリが1つの行にマージされ、テーブルBID01がテーブルAID01を指すようになります。
  • 表AID01から8:00AM-10:00AMを削除した場合、そのエントリは2つのエントリに分割する必要があります。1つは7:00 AM-8：00AM用で、新しいエントリ（ID 03）は10:00AM-11用です。午前00時。
4

5 に答える 5

7

私は生理を幅広く扱ってきましたが、表Aと表Bがどのように連携するかを完全には理解していないのではないかと思います。おそらく、私が理解していないのはsubsumという言葉です。

やりたいことの具体例を教えてください。

このように、テーブルAに記録されたタイムスパンにテーブルBのタイムスパンが完全に含まれているということですか？

|---------------- A -------------------|
    |--- B ----|      |--- B ---|

またはと重複しますか？

    |---------------- A -------------------|
|--- B ----|                        |--- B ---|

または逆に、BのタイムスパンにはAが含まれる/重複しますか？

それが最初のものであり、BのタイムスパンがテーブルAのリンクされたタイムスパンの内側/同じであるとしましょう。

これは次のことを意味しますか？

* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?

次に例を示します。

|-------------- A1 --------------|    |-------- A2 --------------|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

次に、A1を長くし、A2を短くして移動すると、次のようになります。

|-------------- A1 ---------------------------------|  |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

これは、次のようにデータを変更することを意味します。

1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead

この変更についてはどうでしょうか。A1は長くなりますが、B3を完全に含めるには不十分であり、A2は同じ方法で移動/短縮されます。

|-------------- A1 -----------------------------|      |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

B3は完全にA1またはA2のいずれかに含まれていないので、削除しますか？

私はあなたがしたいことのいくつかの具体的な例が必要です。

その他の質問を編集

わかりました、どうですか：

|------------------ A -----------------------|
  |------- B1 -------|  |------- B2 ------|
                           |---|                   <-- I want to remove this from A

これはどうですか？

また：

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|  |B3|   |--- B2 ---|

また：

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|

これまでのところ、私がそれをどのように見ているかを質問とともに要約すると、次のようになります。

  • Aに対して次の操作を実行できるようにする必要があります
    • 短くする
    • 長くする
    • それらが隣接しているときに結合し、2つ以上を1つに結合します
    • ピリオドを削除して分割することにより、それらに穴を開けます
  • 上記の更新後もA内に含まれているBは、必要に応じて再リンクします
  • 含まれていたが、現在は完全に外部にあるBは、削除します
  • 含まれていたが、現在は部分的に外部にあるB、編集：これらを削除、データの整合性を参照
  • 上記のすべての操作について、データを操作に合わせるために必要な最小限の作業を実行します（すべてを削除して新しく挿入するのではなく）

仕事から家に帰ったときに機能する可能性のあるC＃の実装に取り​​組み、今夜はさらに戻ってきます。

編集これがアルゴリズムの突き刺しです。

  1. 最初に新しいリストを最適化します（つまり、隣接するピリオドを組み合わせるなど）。
  2. 次の方法で、このリストをデータベース内のマスター期間と「マージ」します。
    1. 両方のリスト（つまり、新規および既存）のどこにいるかを追跡します
    2. 現在の新しい期間が現在の既存の期間より完全に前である場合は、それを追加してから、次の新しい期間に移動します
    3. 現在の新しい期間が現在の既存の期間の後に完全にある場合は、既存の期間とそのすべての子期間を削除してから、次の既存の期間に移動します
    4. 2つが重なっている場合は、次のように現在の既存の期間を新しい期間と等しくなるように調整してから、次の新しい既存の期間に進みます。
      1. 新しい期間が既存の期間より前に開始する場合は、開始を移動するだけです
      2. 新しい期間が既存の期間の後に開始する場合は、子期間が差分期間にあるかどうかを確認し、それらを覚えてから、開始を移動します
      3. もう一方の端でも同じことをします
  3. 「覚えている」期間については、再リンクまたは削除する必要があるかどうかを確認してください

単体テストの大規模なセットを作成し、変更のすべての組み合わせをカバーしていることを確認する必要があります。

于 2008-10-06T12:12:24.697 に答える
2

質問を2つの別々の質問に分離することをお勧めします。最初の質問は次のようになります。「スケジュールアトムを開始時刻と終了時刻のリソースとして表す場合、リソースのスケジューリングについてどのように推論しますか？」ここで、区間代数を使用するというADeptの提案は適切なようです。スケジューリングについては、ウィキペディアのエントリ「区間グラフ」およびSUNYアルゴリズムリポジトリのエントリを参照してください。2番目の質問はデータベースの質問です。「間隔をスケジュールし、2つの間隔が重なるか、1つが別の間隔に含まれるかを示すアルゴリズムがある場合、この情報を使用して特定のスキーマのデータベースを管理するにはどうすればよいですか？」スケジューリングアルゴリズムが導入されれば、データベースの質問ははるかに簡単に解決できると思います。HTH、ユヴァル

于 2008-10-06T12:07:51.243 に答える
1

このためのアルゴリズムには、NewA を介したパス、ResourceID、StartTime、および EndTime の一致、および OldA のどの要素がヒットしたかの追跡が含まれるように思えます。次に、UnmatchedNewA と UnmatchedOldA という 2 つの一致しないデータのセットがあります。

私が考えることができる最も簡単な方法は、基本的にこれらを最初からやり直すことです: すべての UnmatchedNewA を DB に書き込み、可能な場合は B の要素を UnmatchedOldA から新しい A キー (生成されたばかり) に転送し、そうでない場合は削除します。次に、UnmatchedOldA をすべて消去します。

多くの変更がある場合、これは確かに効率的な方法ではありません。ただし、データのサイズが圧倒的でない場合は、巧妙な最適化よりもシンプルさを好みます。

この最後の提案が背景なしに意味があるかどうかを知ることは不可能ですが、このように考えていない可能性があります:

A コレクション全体をやり取りする代わりに、イベント リスナーなどを使用して、変更が必要な場所だけデータ モデルを更新できますか? このようにして、変更されるオブジェクトは、どの DB 操作が必要かをその場で判断できます。

于 2008-10-05T19:56:14.170 に答える
1

あなたの投稿はほとんど「長すぎて読まなかった」カテゴリに属しています - 短くすると、おそらくより多くのフィードバックが得られるでしょう。

とにかく、トピックについて： 「インターバル代数」と呼ばれるものを調べてみることができます

于 2008-10-05T19:14:15.283 に答える
1

私が理解しているように、ユーザーはテーブル A に直接影響を与えることしかできません。C# でプログラミングしていると仮定すると、単純な ADO.Net DataSet を使用してテーブル A への変更を管理できます。行を適切に変更および削除しました。

さらに、テーブル B 内の対応するオブジェクトを自動的に削除するには、連鎖削除を定義する必要があります。

この方法で処理されない唯一のケースは、テーブル A のタイムスパンが短縮され、テーブル B の対応するレコードが含まれなくなった場合です。update ストアド プロシージャでそのケースをチェックするか、テーブル A に update-trigger を定義するだけです。

于 2008-10-05T19:42:51.123 に答える