چهارمین چالش 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 که نوشتین.

مهم نیست که از چه روشی می خواهین اعداد متوالی رو تولید کنید. همین که یک بار تولید بشه برای همیشه کافی هست.
اینجا ر (http://www.30sharp.com/article/13/216/11/%d8%ac%d8%af%d9%88%d9%84-%da%a9%d9%85%da%a9%db%8c-%d8%a7%d8%b9%d8%af%d8%a7%d8%af.aspx)اه حلهای زیادی پوشش داده شده است.

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

توجه:
من راجب امکان 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;