6

非常に複雑な検索アルゴリズムに関するアドバイス/ヘルプを探しています。関連するテクニックなどの記事は大歓迎です。

バックグラウンド

簡単に言えば、ユーザーが特定の日の「可用性」を設定できるアプリケーションを構築しています。ユーザーは最初に、次のことを許可する一般提供テンプレートを設定します。

Monday - AM   
Tuesday - PM  
Wednesday - All Day  
Thursday - None  
Friday - All Day

したがって、このユーザーは通常、月曜日の午前、火曜日の午後などに利用できます。

スキーマ:

id  
user_id  
day_of_week  (1-7)(Monday to Sunday)
availability

次に、特定の日付を手動で上書きできます。次に例を示します。

2013-03-03 - am  
2013-03-04 - pm  
2013-03-05 - all_day

スキーマ:

id
user_id
date
availability

これはすべてうまく機能します-テンプレートとオーバーライドを組み合わせてユーザーが空き状況などを変更できるようにするカレンダーが生成されています.

問題

ここで、管理者ユーザーが特定の可用性を持つユーザーを検索できるようにする必要があります。そのため、管理者ユーザーはカレンダーを使用して必要な日付と空室状況を選択し、検索をヒットします。

たとえば、利用可能なユーザーを見つけてください:

2013-03-03 - pm
2013-03-04 - pm
2013-03-05 - pm

検索プロセスでは、テンプレート化された可用性とオーバーライドを使用して利用可能なユーザーを検索し、最良の結果を返す必要があります。理想的には、いつでも利用可能なユーザーを返すことですが、日付に一致するユーザーが 1 人もいない場合は、一致できるユーザーの組み合わせを提供する必要があります。

私はこれが非常に複雑な問題であることを知っており、完全な答えを探しているわけではなく、おそらく関連する可能性のある手法へのガイダンスやリンクなどを探しています.

私が試したこと

現時点では、中途半端な解決策があります。利用可能なすべてのユーザーを取得し、それぞれをループして、そのループ内で、必要なすべての日付をループし、ユーザーが必要な日付を満たさないとすぐに中断します。これは明らかに非常にスケーラブルではなく、「完全な一致」しか返されません。

可能な解決策

集計表による全文検索

次のスキーマを持つ別のテーブルを作成することを考えました。

user_id
body

このbodyフィールドにはユーザー テンプレートの日数とオーバーライドが入力されるため、レコードの例は次のようになります。

user_id: 2
body: monday_am tuesday_pm wednesday_pm thursday_am friday_allday 2013-03-03_all_day 2013-03-03_pm

次に、Users 検索クエリを同様の形式に変換します。したがって、ユーザーが 2013 年 3 月 19 日の終日および 2013 年 3 月 20 日の午後に対応可能な人を探している場合、それを文字列に変換します。

まず、3 月 19 日は火曜日なので、これを tuesday_allday に変換し、20 日と同じにします。したがって、私は次のようになります:

tuesday_allday wednesday_pm 2013-03-19_allday 2013-03-20_pm

次に、集計テーブルに対して全文検索を実行し、「重み付けされた」結果セットを返します。これをループしてさらに調査することができます。

これが実際にどのように機能するかはわかりません。そのため、私が使用できるテクニックや関連記事へのリンクを誰かが持っているかどうかを尋ねています.

4

2 に答える 2

2

この問題は、より明確に定義された DB スキーマで解決できると確信しています。より詳細な DB スキーマを利用することで、必要に応じて (午前と午後だけでなく) 任意の時間枠で利用可能なユーザーを見つけることができます。また、テンプレート データを保持しながら、テンプレート情報で可用性データを汚染することはありません (代わりに、テンプレート テーブルから選択して、特定の日付の可用性をプログラムで入力し、ユーザーが変更できるようにします)。

私はこの問題を図式化するのに時間を費やし、指定された問題を解決し、最小限のスキーマ変更でアプリケーションを拡張できると思われるスキーマ構造を考え出しました。(これを読みやすくするために、この提案された回答の最後にSQLを追加しました)

また、任意の数の引数を使用して可用性データを取得できるようにする select ステートメントの例も含めました。SELECT がスキーマの SQL の上にあることを明確にするために、説明テキストの最後に記載します。select に惑わされないでください。一見複雑に見えるかもしれませんが、実際にはスキーマ全体へのマップです (templates テーブルを保存してください)。(ところで、私はあなたがそれを理解できるかどうか疑問があるので、私はあなたがそれを理解できると確信していますが、複雑すぎるように見えるため、より複雑なDB構造を無視して自分自身に損害を与える多くのプログラマーを知っていますが、分析すると、実際には、同様の結果を得るためにプログラムで実行する必要があるアクロバットよりも複雑ではありません...リレーショナルDBは数学の分野に基づいています@ 正確に、一貫して、& (比較的) 簡潔に、データを関連付ける) ことは良いことです。

一般的な使用: (詳細については、SQL CREATE TABLE ステートメントのコメントを参照してください) - DaysOfWeek テーブルにデータを入力します。-TimeFrames テーブルに、追跡する時間枠を入力します (AM 時間枠の StartTime は 00:00:00 で終了時間は 11:59:59 であるのに対し、PM では StartTime が 12:00:00 で EndTime である可能性があります)。 23:59:59 の) - ユーザーを追加 - 追跡する日付を追加 (肥大化を回避するための考えとこのテーブルの利点については、SQL のメモを参照してください) - 各ユーザーのテンプレート テーブルにデータを入力します - デフォルトの可用性のリストを生成します ( -デフォルトの利用可能性をユーザーに公開して、デフォルトをオーバーライドできるようにします 注: Engagements のオプションのテーブルを追加して、利用可能性の反対にすることもできます (または、より適切な抽象化が存在する可能性があります両方の概念を含む...) 免責事項:ローカル DB を完全に作成してすべてを検証するために追加の時間を割かなかったため、図には見られなかったいくつかの弱点/エラーがある可能性があります... (申し訳ありませんが、これに意図したよりもはるかに長い時間を費やし、作業を行わなければなりません期限切れのプロジェクトで完了)。私はDB構造と他の人が12年以上作成したDBでかなり広範囲に働いてきましたが、私に過失がないわけではないと確信しています。

これ以上サンプル データを含めないことをお詫びします。近いうちに時間があれば、いくつか提供します (ユーザー テーブルにジョージ、フレッド、ハリーを追加し、日付テーブルにいくつかの日付を追加してから、学校の週にジョージとフレッドがハリーと比べてどれくらい忙しいかを詳しく説明します。 Availabilities、AvailableTimes & TimeFrames テーブル)。

SELECTステートメント(注:これをビューにすることを強くお勧めします...そのようにして、必要な列を選択し、毎回結合を書き出すことなく、WHERE句に必要な引数/条件を追加できます. .. したがって、ビューには WHERE 句は含まれません... 明確にするためだけに):

SELECT *
FROM Users Us
JOIN Availabilities Av
ON Us.User_ID=Av.User_ID
JOIN Dates Da
ON Av.Date_ID=Da.Date_ID
JOIN AvailableTimes Avt
ON Av.Av_ID=Avt.Av_ID
WHERE Da.Date='2014-01-03' -- whatever date 
-- alternately: WHERE Da.DayOWeek_ID=3 -- which would be Wednesday
-- WHERE Da.Date BETWEEN() -- whatever date range...
-- etc...

DaysOfWeek の推奨データ(実質的にルックアップ テーブル):

INSERT INTO DaysOfWeek(DayOWeek_ID,Name,Description)
VALUES (1,'Sunday', 'First Day of the Week'),(1,'Monday', 'Second Day of the Week')...(7,'Saturday', 'Last Day of the Week'),(8,'AllWeek','The entire week'),(9,'Weekdays', 'Monday through Friday'),(10,'Weekends','Saturday & Sunday')

テンプレートデータの例:

INSERT INTO Templates(Time_ID,User_ID,DayOWeek_ID)
VALUES (1,1,9)-- this would show the first user is available for the first time frame every weekday as their default... 
,(1,2,2) -- this would show the first user available on Tuesdays for the second time frame

推奨されるスキーマ構造は次のとおりです

CREATE  TABLE `test`.`Users` (

User_IDINT NOT NULL AUTO_INCREMENT , UserNameVARCHAR(45) NULL , PRIMARY KEY ( User_ID) );

CREATE  TABLE `test`.`Templates` (
  `Template_ID` INT NOT NULL AUTO_INCREMENT ,
  `Time_ID` INT NULL ,
  `User_ID` INT NULL ,
  `DayOWeek_ID` INT NULL ,
  PRIMARY KEY (`Template_ID`) )
`COMMENT = 'This table holds the template data for general expected availability of a user/agent/person (so the person would use this to set their general availability)'`;

CREATE  TABLE `test`.`Availabilities` (
  `Av_ID` INT NOT NULL AUTO_INCREMENT ,
  `User_ID` INT NULL ,
  `Date_ID` INT NULL ,
  PRIMARY KEY (`Av_ID`) )
COMMENT = 'This table holds a users actual availability for a particular date.\nIf the use is not available for a date then this table has no entry for that user for that date.\n(btw, this suggests the possiblity of an alternate table that could utilize all other structures except the templates called Engagements which would record when a user is actually busy... in order to use this table & the other table together would need to always join to AvailableTimes as a date would actually be in both tables but associated with different time frames).';

CREATE  TABLE `test`.`Dates` (
  `Date_ID` INT NOT NULL AUTO_INCREMENT ,
  `DayOWeek_ID` INT NULL ,
  `Date` DATE NULL ,
  PRIMARY KEY (`Date_ID`) )
COMMENT = 'This table is utilized to hold actual dates whith which users/agents can be associated.\nThe important thing to note here is: this may end up holding every day of every year... this suggests a need to archive this data (and everything associated with it for performance reasons as this database is utilized).\nOne more important detail... this is more efficient than associating actual dates directly with each user/agent with an availability on that date... this way the date is only recorded once, the other approach records this date with the user for each availability.';

 CREATE  TABLE `test`.`AvailableTimes` (
  `AvTime_ID` INT NOT NULL AUTO_INCREMENT ,
  `Av_ID` INT NULL ,
  `Time_ID` INT NULL ,
  PRIMARY KEY (`AvTime_ID`) )
COMMENT = 'This table records the time frames that a user is available on a particular date.\nThis allows the time frames to be flexible without affecting the structure of the DB.\n(e.g. if you only keep track of AM & PM at the beginning of the use of the DB but later decide to keep track on an hourly basis you simply add the hourly time frames & start populating them, no changes to the DB schema need to be made)';

CREATE  TABLE `test`.`TimeFrames` (
  `Time_ID` INT NOT NULL AUTO_INCREMENT ,
  `StartTime` TIME NOT NULL ,
  `EndTime` TIME NOT NULL ,
  `Name` VARCHAR(45) NOT NULL ,
  `Desc` VARCHAR(128) NULL ,
  PRIMARY KEY (`Time_ID`) ,
  UNIQUE INDEX `Name_UNIQUE` (`Name` ASC) )
COMMENT = 'Utilize this table to record the times that are being tracked.\nThis allows the flexibility of having multiple time frames on the same day.\nIt also provides the flexibility to change the time frames being tracked without changing the DB structure.';

CREATE  TABLE `test`.`DaysOfWeek` (
  `DaysOWeek_ID` INT NOT NULL AUTO_INCREMENT ,
  `Name` VARCHAR(45) NOT NULL ,
  `Description` VARCHAR(128) NULL ,
  PRIMARY KEY (`DaysOWeek_ID`) ,
  UNIQUE INDEX `Name_UNIQUE` (`Name` ASC) )
COMMENT = 'This table is a lookup table to hold the days of the week.\nI personally would recommend adding a row for:\nWeekends, All Week, & WeekDays \nThis will often be used in conjunction with the templates and will allow less entries in that table to be made with those 3 entries in this table.';
于 2014-03-01T10:56:16.530 に答える
0

わかりました、これは私がすることです:

  • users テーブルに、日曜日、月曜日、土曜日のフィールドを作成します。
  • これらのフィールドの値にはpmamまたはを使用します。both
  • また、クエリを高速化するために、データベース内の各フィールドにインデックスを付ける必要があります。
  • 次に、ユーザー/日付/子午線フィールド用に別のテーブルを作成します (子午線は午前または午後を意味します)。ここでも子午線フィールドの値はpmamまたはになりbothます。
  • 曜日番号を取得し、おそらくそれに対して switch ステートメントを使用するには、php の日付関数を使用して少し調査する必要があります。
  • 要求された日付を使用して曜日を取り出し、ユーザー テーブルにクエリを実行して曜日の空き状況を確認します。
  • 次に、要求された日付/子午線自体を使用して、新しいユーザー/日付/子午線テーブルにクエリを実行して、ユーザーの個々の利用可能な日付/子午線を取得します。

日付リクエストで曜日を抽出する場合を除いて、ここで多くのアルゴリズムがあるとは思いません。日付範囲を設定している場合は、アルゴリズムの恩恵を受けることができますが、それが単に厳選された日付の集まりである場合は、それらを 1 つずつ実行する必要があります。私に知らせてください、多分私はあなたのためにアルゴリズムを投げます.

于 2013-03-18T18:22:15.030 に答える