הבלוג של גרי רשף

02/05/2010

Packing Date Intervals

Filed under: Uncategorized — תגיות: , , — גרי רשף @ 19:35

איציק בן-גן פירסם פוסט שזה כותרתו, והוא עוסק באתגר הבא:
נתונה טבלת פעילויות שכל אחת נמשכת מתאריך (התחלה) עד תאריך (סיום),
ויש לחשב את תקופות הפעילות השונות,
כלומר- התקופות בהן מתבצעת איזו פעילות.
בצורה ציורית ניתן היה לתאר זאת כלוח גאנט של הפעילויות השונות שבתחתיתו נסמן את ההיטל המשותף של הפעילויות השונות, וכך נקבל מספר קטעים שלכל אחד יש התחלה וסוף שבינהם יש פעילויות, ובין קטע לקטע אין אף פעילות.
הנה דוגמה בה תשע פעילויות מתקבצות לשלוש תקופות (הקטעים האדומים העבים על הציר האופקי למטה):

20100502 הפתרון של איציק מתבסס באופן כללי על Join בין טבלת הפעילויות לטבלת תאריכים (כמו טבלת מספרים אבל עם רצף תאריכים) – כך שמקבלים את כל התאריכים בהם יש פעילות,
מבצעים על הרשימה Distinct כדי לנפות כפילויות,
ולבסוף מוצאים את ה"איים" שברצפי התאריכים (מציאת איים ורווחים ברצף של מספרים או תאריכים זו בעייה מוכרת שאיציק ואחרים טיפלו בה ולכן אין צורך להמציא מחדש את הגלגל).

הנה פתרון שונה- על ידי CTE רקורסיבי:
בשלב ראשון אני ממספר את הרשומות לפי סדר עולה של תאריך התחלה כי אם יש שתי פעילויות עוקבות שיש בינהן רווח-יהיה בוודאי רווח גם בין התקופות המקובצות (הכוונה, ליתר דיוק, שהפעולה הראשונה מבין השתיים כבר שוקללה עם הקודמות לה באותה תקופה ותאריך ההתחלה הוא זה של התקופה),
ולאחר מפעיל רקורסיה כפולה-
פעם אחת עבור מקרה בו שתי פעילויות עוקבות מתקבצות לתקופה אחת (ואז אדאג יהיה לשתיהן אותו תאריך התחלה),
ופעם שניה עבור מקרה בו נוצר רווח (ואז לרשומה העוקבת יהיה תאריך ההתחלה המקורי שלה השונה משל הקודמת וזה יציין תחילת תקופה חדשה);
ועל כל זה אבצע Group By לפי תאריך ההתחלה ואמצע לכל תארייך התחלה את תאריך הסיום המקסימלי.

כדי שהדוגמה תהיה מעניינת- הוספתי כמה וכמה פעילויות:

CREATE TABLE dbo.Projects

( projectid  INT          NOT NULL,

  title      VARCHAR(100) NOT NULL,

  start_date DATE         NOT NULL,

  end_date   DATE         NOT NULL);

Go

INSERT INTO dbo.Projects(projectid, title, start_date, end_date) VALUES

  (1, 'Project 1', '20100212', '20100220'),

  (2, 'Project 2', '20100214', '20100312'),

  (3, 'Project 3', '20100124', '20100201'),

  (4, 'Project 4', '20100401', '20100410'),

  (5, 'Project 5', '20100420', '20100425'),

  (6, 'Project 6', '20100501', '20100509'),

  (7, 'Project 7', '20100409', '20100415'),

  (8, 'Project 8', '20100414', '20100421'),

  (9, 'Project 9', '20100605', '20100610'),

  (10, 'Project 10', '20100614', '20100621'),

  (11, 'Project 11', '20100601', '20100625');

Go

והשליפה הרקורסיבית:

With T1 As

(Select    Row_Number() Over(Order By Start_date) N,

        *

From    Projects),

T2 As

(Select 1 N,

        start_date,

        end_date

From    T1

Where    N=1

Union All

Select    T2.N+1,

        T2.start_date,

        Case When T1.end_date>=T2.end_date Then T1.end_date Else T2.end_date End

From    T1

Inner Join T2

        On T2.End_date >= T1.start_date

Where    T1.N=T2.N+1

Union All

Select    T2.N+1,

        T1.start_date,

        T1.end_date

From    T1

Inner Join T2

        On T2.End_date < T1.start_date

Where    T1.N=T2.N+1

)

Select    start_date,

        Max(end_date) end_date

From    T2

Group By start_date;

הפלט המתקבל:

start_date    end_date

2010-01-24    2010-02-01

2010-02-12    2010-03-12

2010-04-01    2010-04-25

2010-05-01    2010-05-09

2010-06-01    2010-06-25

מודעות פרסומת

תגובה אחת »

  1. […] כן נתקלתי בבעיות שרק כך הן נפתרו (עץ פורש מינימלי או Packing Date Intervals), ולכן אנצל את ההזדמנות לעקוב אחר […]

    פינגבאק של CTE רקורסיבי « הבלוג של גרי רשף — 26/05/2010 @ 13:10


RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: