چهارمین چالش SQL (رزرو صندلی)

[محمد سلیم آبادی]

مقدمه

"فاکتوری که برای انتخاب برنده مورد استفاده قرار خواهد گرفت عملکرد و کوتاهی نقشه ای اجرا کوئری است."

یک شرکت اتوبوس رانی نیاز به یک گزارش برای رزرم صندلیهای اتوبوس ها دارد.

هدف دادن تعداد مسافر به کوئری و دریافت شماره صندلی های مناسب است. صندلی های خالی باید کنار هم و در یک دریف باشند. تعداد مسافرینی که قصد دارند کنار هم مسافرت کنند حد اکثر در گروههای 4 نفری دسته بندی می شوند.

اپراتور ممکن است اعداد متغیری بین 1 تا 4 به کوئری بدهد و انتظار دارد اولین جای خالی مناسب را به عنوان نتیجه دریافت کند.

جدول و داده ها

داده هایی که ما احتیاج داریم به قرار زیر است:

1. شماره صندلی -nbr

2.شماره ردیف- row_nbr
3.مقداری مبنی بر پر یا خالی بودن صندلی- reserve_mark

اتوبوس های این شرکت دارای 10 ردیف چهارتایی هست که مجموعا 40 نفر ظرفیت دارد.

CREATE TABLE BusBooking

(nbr INTEGER NOT NULL PRIMARY KEY

 CONSTRAINT possible_nbrs

 CHECK (nbr BETWEEN 1 AND 40),

 row_nbr INTEGER NOT NULL

 CONSTRAINT possible_row_nbrs

 CHECK (row_nbr BETWEEN 1 AND 10),

 reserve_mark BIT NOT NULL DEFAULT 0);

 

/*every row has exactly 4 chairs

NOT EXISTS

(SELECT 1

 FROM BusBooking

 GROUP BY row_nbr

 HAVING COUNT(*) <> 4)

*/



INSERT INTO BusBooking VALUES 

(1, 1, 1),

(2, 1, 1),

(3, 1, 0),

(4, 1, 0),



(5, 2, 1),

(6, 2, 1),

(7, 2, 1),

(8, 2, 1),



(09, 3, 1),

(10, 3, 0),

(11, 3, 0),

(12, 3, 0),



(13, 4, 0),

(14, 4, 0),

(15, 4, 0),

(16, 4, 0);

نتیجه مورد نظر

با فرض داده های آزمایشی، اگر کاربر مقدار 1 را منظور کرد نتیجه ی مطلوب و خواسته این است:

3

برای مقدار 2:

3

4

برای 3:

10

11

12

برای 4:

13

14

15

16

یعنی اولین صندلی های خالی کنار هم که در یک دریف قرار دارند و به تعداد مورد نیاز نیز هستند به عنوان جواب بایستی انتخاب شود.
بطور پیشفرض امکان کنسل کردن رزور وجود نداره. در غیر اینصورت ممکنه صندلی های خالی در یک دریف موجود باشه ولی مجاور نباشن. شما میتونید دو راه حل ارائه بدین یکی برای برای حالتی که امکان کنسل کردن وجود نداره و یکی که این امکان وجود داره. بدیهی هست که مساله دوم به مراتب پیچیده تر از مساله 1 هست.

راه حل نباید شامل Dynamic SQL باشد

راهنمایی

شما میتونید از راه حل های مناسبی که در چالش اول مطرح شد برای حل مساله ایده بگیرد. همچنین روشی را در زیر شرح می دهم تا بتوانید ایده هایی را از آن برداشت کنید. ولی آن را به هیچ وجه به عنوان پاسخ پیشنهاد نمی کنم.

اگر ما برای هر درخواست یک کوئری جدا گانه تولید کنیم و سپس آنها را با همدیگر اجتماع کنیم و سطرهایی را انتخاب کنیم که مناسب به تعداد درخواست کاربر باشد مساله حل میشه.

با این فرض که کاربر 3 صندلی کنار هم را درخواست کرده است ما می توانیم سطرجاری را با 2 سطر بعدی مرتبط به ردیف فعلی به شرط خالی بودن هر سه صندلی اتصال دهیم و بعد از بدست آوردن کوچکترین شماره صندلی توسط تکنیکی فوق العاده (unpivoting by cross apply) مقادیر بین minimum و minimum + 2 را بدست می آوریم.

طبق توضیحاتی که داده شد راه حل آموزشی همراه با نقشه متنی آن به این شکل در میاید (در اینجا متغیر N به عنوان تعداد درخواستی هست که من با 4 ستش کردم):

  DECLARE @N TINYINT = 1;

  

  ;WITH N1(m) AS

  (SELECT MIN(nbr)

     FROM BusBooking

    WHERE reserve_mark = 0),

  

   N2(m) AS

  (SELECT MIN(A.nbr)

     FROM BusBooking A, BusBooking B

    WHERE A.nbr + 1 = B.nbr

      AND A.row_nbr = B.row_nbr

      AND A.reserve_mark = 0

      AND B.reserve_mark = 0),

  

   N3(m) AS 

  (SELECT MIN(A.nbr)

     FROM BusBooking A, BusBooking B, BusBooking C

    WHERE A.nbr + 1 = B.nbr

      AND B.nbr + 1 = C.nbr

      AND A.row_nbr = B.row_nbr

      AND B.row_nbr = C.row_nbr

      AND A.reserve_mark = 0

      AND B.reserve_mark = 0

      AND C.reserve_mark = 0),

  

   N4(m) AS 

  (SELECT MIN(A.nbr)

     FROM BusBooking A, BusBooking B, BusBooking C, BusBooking D

    WHERE A.nbr + 1 = B.nbr

      AND B.nbr + 1 = C.nbr

      AND C.nbr + 1 = D.nbr

      AND A.row_nbr = B.row_nbr

      AND B.row_nbr = C.row_nbr

      AND C.row_nbr = D.row_nbr

      AND A.reserve_mark = 0

      AND B.reserve_mark = 0

      AND C.reserve_mark = 0

      AND D.reserve_mark = 0)

  SELECT n

  FROM (

              SELECT m, 1

              FROM N1

  

              UNION ALL

  

              SELECT m, 2

              FROM N2

  

              UNION ALL

  

              SELECT m, 3

              FROM N3

  

              UNION ALL

  

              SELECT m, 4

              FROM N4

         )T(m, k)

         CROSS APPLY

  (

             VALUES 

  (m),(m + 1),(m + 2),(m + 3)

           ) D(n)

   WHERE n < m + @N

     AND k = @N;

  

[behrouzlo]

تست کنید ببینید صورت مسئله را درست حل می کند. ولی فکر کنم باز بشود بهینه تر کرد

/* Behrouzlo 371 chars*/

Declare @N Numeric = 4 ;

Declare @S Int = ( Select   min(Case When @N = 4

                                          And ( SS % 4 ) = 1

                                     Then SS

                                     When @N = 4

                                          And ( SS % 4 ) <> 1

                                     Then ( Floor(SS / 4) + 1 ) * 4

                                          + 1

                                     Else SS

                                End) S

                   From     ( SELECT    MIN(nbr) AS SS ,

                                        Count(*) As Count

                              FROM      ( SELECT    nbr ,

                                                    nbr

                                                    - ROW_NUMBER() OVER ( ORDER BY nbr ) As a

                                          FROM      BusBooking

                                          Where     reserve_mark = 0

                                        ) AS D

                              GROUP BY  a

                            ) As List

                   Where    Count >= @N

                 ) ;

WITH    seats ( s )

          AS ( Select   @S

               UNION ALL

               SELECT   s + 1

               FROM     seats

               WHERE    s < @S + @N - 1

                        ANd s <= 16

             )

    Select  *

    From    seats    

[محمد سلیم آبادی]

تنها ایرادی که ممکنه داشته باشه اینه که زمانی که صندلی خالی مناسب وجود نداشته باشه. خروجی یک سطر با مقدار Null است. ولی مشکلی نیست.
راه حل رو خیلی پیچیدش کردین. بسیار ساده تر میشه مساله رو حل کرد.

/*Msalim 169 Chars*/

SELECT n

  FROM (SELECT MIN(m) m

          FROM (

                 SELECT MIN(nbr) m

                   FROM BusBooking

                  WHERE reserve_mark = 0

                  GROUP BY row_nbr

                 HAVING COUNT(*) >= @N

               ) T

       ) T

       CROSS APPLY

         (

           VALUES 

             (m), (m + 1), (m + 2), (m + 3)

         ) D(n)

 WHERE n < m + @N;

[محمد سلیم آبادی]

یا حتی خیلی ساده تر،
اگر یک جدول اعداد از قبل تولید کرده باشیم. انگاه داریم:

--Msalim 136 Chars

SELECT n

  FROM (SELECT TOP 1 MIN(nbr) m

          FROM BusBooking

         WHERE reserve_mark = 0

         GROUP BY row_nbr

        HAVING COUNT(*) >= @N

         ORDER BY m) T

       JOIN Nbrs N

         ON n BETWEEN m AND m + @N - 1;

[behrouzlo]

من قانون اینکه گروه مسافران باید در یک ردیف باشند را دقیق متوجه نشدم و در راه حل من تقریبا نقض شده است و فقط گروه های 4 نفری را در یک ردیف قرار می دهد.

[محمد سلیم آبادی]

نه، همه گروه ها از 2 تایی تا 4 تایی باید در یک ردیف قرار بگیرند. (یکی ای که هیچی)
اصلا بحث رزوراسیون فک نمیکنم چیزی جز این باشه. چون مسافرین که با هم میخوان مسافرت کنند اکثر زوج و خانواده هستند دوست دارن کنار هم باشن یا اینکه اگه در یک ردیف جا نشدن سعی بشه به بهترین شکل کنار هم قرار بگیرن مثلا در دو ردیف مجاور... نه اینکه 2تاشون یه ردیف 2تاشون یک ردیف دیگه.

شما نباید اعداد متوالی (جدول اعداد) رو داخل راه حل قرار بدین! گاها وقتی مسائل پیچیده میشن نیاز به جدول اعداد هست. شما همیشه باید یک جدول اعداد در بانکتون از قبل ایجاد کرده باشین که احتیاج به تولید اون در راه حلتون نباشین. این کار خیلی روی عملکرد تاثیر منفی داره. مخصوصا اون recursive cte که نوشتین.

مهم نیست که از چه روشی می خواهین اعداد متوالی رو تولید کنید. همین که یک بار تولید بشه برای همیشه کافی هست.
اینجا راه حلهای زیادی پوشش داده شده است.

[محمد سلیم آبادی]

توجه:
من راجب امکان cancel کردن رزرو صحبتی نکردم.
اگه امکان cancel کردن رزور وجود داشته باشه اون وقت روش من درست عمل نمی کنه. مثلا با فرض همون داده های اولیه اگر یک درخواست یکتایی داشته باشیم اولین مکان خالی شماره 3 هست. بعد از اون اگه صندلی 2 بعد از cancel شدن رزور خالی بشه اون وقت در اون ردیف 2 صندلی خالی وجود داره ولی مجاور نیستند!
حالا اگه درخواست دو صندلی خالی مجاور کنار هم در یک ردیف داده شود انگاه روش شما جواب صحیح رو میده یعنی اولین ردیفی که دارای 2 صندلی خالی مجاور هست یعنی: 10 و 11
ولی روش من جواب اشتباه 2 و 3 رو تولید میکنه.

با در نظر گرفتن این موضوع کنسلینگ راه حل پیشنهادی من فردا ارسال خواهد شد.

[محمد سلیم آبادی]

همانطور که در پستهای قبلی مشخص شد. بحث همجواری در راه حلهایم اعمال نشده بود. از طرفی راه حل فردی که در بحث شرکت کرده بود نیز بودن در یک ردیف را مورد بررسی قرار می داد. در نتیجه دو راه حل یکی کلاسیک و دیگری OLAP را به عنوان پاسخ ارائه میدم:

  /*Msalim: Classic Version*/

  SELECT MIN(nbr) AS start_place, 'to', MIN(nbr) + @N - 1 AS end_place

    FROM BusBooking AS A

   WHERE EXISTS

  (SELECT 1

            FROM BusBooking

           WHERE nbr BETWEEN A.nbr AND A.nbr + @N - 1

             AND reserve_mark = 0

          HAVING COUNT(DISTINCT row_nbr) = 1

             AND COUNT(*) >= @N)

   HAVING MIN(nbr) IS NOT NULL;

  

  /*Msalim: OLAP Version*/

  WITH Cte AS

  (

        SELECT nbr, row_nbr,

               nbr - ROW_NUMBER() OVER(PARTITION BY row_nbr ORDER BY nbr) AS rnk

          FROM BusBooking

         WHERE reserve_mark = 0

  )

  SELECT TOP 1 MIN(nbr) start_place, 'to', MAX(nbr) end_place

    FROM Cte

   GROUP BY row_nbr, rnk

  HAVING COUNT(*) >= @N

   ORDER BY row_nbr, rnk;