پنجمین چالش (توالی)

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

مقدمه
یکی از معانی کلمه Run توالی هست. اگر ما اعداد 1و2و3و4و5.... را اعداد متوالی (Sequential) بنامیم. آنگاه اگه اعدادی در این بین حذف بشن و گپ ایجاد بشه دیگه این ها کاملا پشت سر هم نیستند. در این حالت بهشون بطور غیر رسمی به اصطلاح میگن Runs.
حتی شما میتونید به این لینک (http://en.wikipedia.org/wiki/Run) مراجعه کنید. آخرین معنی در بخش Computers.

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

جدول و داده های زیر رو تصور کنید:

CREATE TABLE Runs
(seq_nbr INTEGER NOT NULL PRIMARY KEY,
val INTEGER NOT NULL);

INSERT Runs VALUES
(1, 6),
(2, 41),
(3, 12),
(4, 51),
(5, 21),
(6, 70),
(7, 79),
(8, 62),
(9, 30),
(10, 31),
(11, 32),
(12, 34),
(13, 35),
(14, 57),
(15, 19),
(16, 84),
(17, 80),
(18, 90),
(19, 63),
(20, 53),
(21, 3),
(22, 59),
(23, 69),
(24, 27),
(25, 33);

توضیح داده ها:
ابتدا به جدول زیر توجه کنید:

rn str_run end_run
-------------------- ----------- -----------
1 1 2
2 3 4
3 5 7
4 8 8
5 9 14
6 15 16
7 17 18
8 19 19
9 20 20
10 21 23
11 24 25

اولین Run از 1 شروع میشه تا 2 ادامه داره یعنی اعداد 6 و 41 که به ترتیب مقدار بعدی از مقدار بعدی بزرگتر هست.
سومین Run از 5 شروع میشه تا 7 ادامه داره یعنی اعداد 21و70و79 که به ترتیب مقدار بعدی از مقدار قبلی بزرگت است.

یعنی Run تا زمانی ادامه داره که مقدار بعدی از مقدار قبلی بزرگتر باشه، ستونی که بعدی و قبلی رو مشخص میکنه seq_nbr هست.

پس باید تا اینجا با مفهوم و اصطلاح Run آشنا شده باشید.
نتیجه ی مورد نظر ما بدست آوردن زیر-توالی هایی هست که مربوط به یک Run میشن با طول مشخص.

بطور دقیق تر زیر-توالی هایی که طولشان بیش از 2 باشد را میخواهیم بدست بیاریم یعنی این نتیجه:

start_seq_nbr end_seq_nbr
------------- -----------
5 7
9 11
9 12
9 13
9 14
10 12
10 13
10 14
11 13
11 14
12 14
21 23


کوئری که سلکو تو کتابش نوشته این هست:

SELECT R1.seq_nbr AS start_seq_nbr, R2.seq_nbr AS end_seq_nbr
FROM Runs AS R1, Runs AS R2
WHERE R1.seq_nbr < R2.seq_nbr -- start and end points
ANDR2.seq_nbr - R1.seq_nbr >2 -- length restrictions
AND NOT EXISTS -- ordering within the end points
(SELECT *
FROM Runs AS R3, Runs AS R4
WHERE R4.seq_nbr BETWEEN R1.seq_nbr AND R2.seq_nbr
AND R3.seq_nbr BETWEEN R1.seq_nbr AND R2.seq_nbr
AND R3.seq_nbr < R4.seq_nbr
AND R3.val > R4.val);


در روش فوق جدول Runs چهار بار بکارگرفته شده. هدف اینه که این عدد کاهش پیدا کنه. اگه میخواهین مثل سلکو روشتون کلاسیک باشه نباید بیش از 3 بار جدول Runs رو بکاربگیرین اگر هم روشتون از توابع OLAP استفاده کرده تعداد جدول Runs استفاده شده باید کمتر از 3 باشه. چه مستقیم چه غیر مستقیم.
یعنی این کد:

WITH C AS
(SELECT *
FROM Runs)
SELECT *
FROM C AS R1, C AS R2

2 بار از جدول Runs استفاده کرده. نه یک بار.

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

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

یک راهنمایی می کنم که لزوما با دونستن اون نمی شه مساله رو حل کرد.
برای بدست آوردن بازه های توالی شما میتونید از جدول اعداد کمک بگیرین. ولی فراموش نکنید که جدول اعداد میتونه مقادیری خارج از مقدار ستون seq_nbr جدول Runs داشته باشه. این مقادیر باید فیلتر بشن.

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

راهنمایی بعدی برای حل شدن این مساله:
با کمک توابع Window امکان بدست آوردن مینیمم و ماکسیمم مقادیر به ازای هر سطر جدول بدون subquery یا چیزهای دیگر مقدور هست.

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

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

مساله جدید:
نتیجه ی مورد نظر را توسط کوئری فاقد هر گونه subquery و عبارت جدولی تولید کنید. یا اینکه حداقل یک روش کلاسیک جایگزین برای این مساله بدست بیارید

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

با در نظر گرفتن اینکه 8 روز از ایجاد تاپیک میگذره احتمال پست راه حل بسیار کم هست پس بیش از این منتظر نمی مانیم.
راه حل کلاسیک متمایز با روش سلکو با 3 ارجاع به جدول Runs:

SELECT A.seq_nbr AS start_seq_nbr , B.n AS end_seq_nbr
FROM (SELECT seq_nbr,
MIN(seq_nbr) OVER() AS mi,
MAX(seq_nbr) OVER() AS mx
FROM Runs
) AS A
CROSS JOIN Nbrs B --Tally Table
WHERE B.n - A.seq_nbr > 2
AND B.n BETWEEN A.mi AND A.mx
AND NOT EXISTS
(SELECT *
FROM Runs C
WHERE seq_nbr >= A.seq_nbr AND seq_nbr < B.n
AND EXISTS
(SELECT *
FROM Runs D
WHERE seq_nbr = C.seq_nbr + 1
AND D.val <= C.val));

راه حل توسط توابع آنالیزی :

SELECT A.seq_nbr AS start_seq_nbr,
B.seq_nbr AS end_seq_nbr
FROM Runs AS A, Runs B
WHERE B.seq_nbr - A.seq_nbr > 2
AND EXISTS
(SELECT 1
FROM (SELECT ROW_NUMBER()
OVER (ORDER BY seq_nbr) -
ROW_NUMBER()
OVER (ORDER BY val) AS k
FROM Runs
WHERE seq_nbr BETWEEN A.seq_nbr AND B.seq_nbr) D
HAVING MAX(k)=0
);

راه حل کلاسیک بدون هیچ گونه سابکوئری و عبارت جدولی:

SELECT A.seq_nbr, B.seq_nbr
FROM Runs A, Runs B, Runs C, Runs D
WHERE B.seq_nbr - A.seq_nbr > 2
AND C.seq_nbr BETWEEN A.seq_nbr AND B.seq_nbr - 1
AND C.seq_nbr + 1 = D.seq_nbr
AND C.val < D.val
GROUP BY A.seq_nbr, B.seq_nbr
HAVING COUNT(*) = B.seq_nbr - A.seq_nbr;

[behrouzlo]

راه حلی به نظر من رسید منطقش شبیه راه حل آخر بود ولی من به محدودیت سه بار ارجاع فکر می کردم ولی نتونستم به نتیجه برسم. به نظر شما می شه تقریبا با منطق شبیه راه حل آخر با سه بار ارجاع به نتیجه نهایی رسید یا نه؟

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

به نکته جالبی اشاره کردی.
اگه هدف کم کردن ارجاع به جدول Runs در راه حل آخر باشه می شه اونو تا 2 بار کاهش داد توسط جدول اعداد (در اینجا اسمش Nbrs هست که یک ستون با نام n داره). ولی اگه هدف کاهش ارجاع به جدول (چه Runs و چه غیره) باشه من بهش تاحالا فکر نکردم و نمی تونم نظر قطعی بدم.

شما می تونید به نقشه گرافیکی کوئری زیر نگاه کنید خواهید دید که فقط 2 گره مربوط به خواندن جدول Runs وجود دارد.

از اونجایی که ما فقط اعداد متوالی رو از دو جدول با نام های مستعار A و B احتیاج داریم میتونیم این مقادیر رو از جدول Nbrs بدست بیاریم. و تنها کاری که باید انجام داد فیلتر کردن سطرهای جدول Nbrs توسط مقادیر مینیمم و ماکسیمم جدول Runs هست.

پس داریم:

SELECT A.n, B.n
FROM (SELECT *,
MIN(seq_nbr) OVER() mi,
MAX(seq_nbr) OVER() mx
FROM Runs C) C
INNER JOIN Nbrs A
ON A.n BETWEEN mi AND mx
INNER JOIN Nbrs B
ON B.n BETWEEN mi AND mx
AND B.n - A.n > 2
INNER JOIN Runs D
ON C.val < D.val
AND C.seq_nbr + 1 = D.seq_nbr
AND C.seq_nbr BETWEEN A.n AND B.n - 1
GROUP BY A.n, B.n
HAVING COUNT(*) = B.n - A.n;