اولین چالش SQL

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

مقدمه

مساله زیر را جهت تقویت مهارت های SQL برنامه نویسان طراحی کرده ام.

راه حل باید دارای شرایط زیر باشد:

1. استاندارد بوده به این معنا که از Syntax هایی که مخصوص RDBMS های مختلف هست استفاده نشده باشد. این ویژگی باعث می شود راه حل قابل حمل (Portable) شود و در نرم افزارهایی که طبق استاندارد های SQL کار می کنند قابل اجرا شود.
2. راه حل تنها از یک عبارت SELECT تشکیل شده باشد.
3. حق استفاده از View یا Common Table Expression وجود ندارد.
4. استفاده از توابع Ranking ممنوع است.
   

هدف ارائه کوتاه ترین راه حل است.

پس کوتاه ترین راه حل به عنوان راه حل برنده شناخته خواهد شد. از راه حل هایی که دوستان ارسال می کنند استقبال خواهد شد. 7 روز دیگر من راه حل های خودم را همراه با راه حلهایی که دوستان ارسال کردند (در صورت ارسال) را انتشار خواهم داد.

مساله

فروشگاهی را در نظر بگیرید که تعدادی فروشنده در آن کار می کنند. فروشندگان در تمام روزهای سال مشغول به کار نیستند و ممکن است روزهای تعطیل فروشگاه بسته شود یا اینکه در ایام غیر تعطیل فروشنده به مرخصی رود.

مدیر فروشگاه قصد دارد جهت تشویق کارکنان خود افرادی را که 5 روز کاری، بطور متوالی توانسته اند فروش صعودی مطلق داشته باشند را مورد تشویق نقدی قرار دهد.

منظور از فروش صعودی مطلق این است که فروش روز بعد از فروش روز قبل بیشتر بوده (حتی برابر هم نباشد) و فروش روز سوم از روز دوم بیشتر بوده و همینطور تا 5 روز.

این 5 روز باید 5 روز متوالی کاری فرد بوده باشد. به این معنا که می تواند بین این 5 روز، روزهایی باشد که فرد به مرخصی رفته باشد یا اینکه آن روزها تعطیل بوده باشند.

به نمودار دو بعدی زیر دقت کنید:
chart.png



کاربر (فروشنده) ای که با رنگ قرمز مشخص شده است به عنوان نتیجه باید اعلام شود. به دلیل اینکه توانسته 5 روز متوالی کاری موفق به فروش صعودی مطلق شود. یعنی فروش روز پانزدهم از روز دوازدهم بیشتر بوده و فروش روز شانزدهم از پانزدهم بیشتر همینطور تا روز بیستم.

روزهای 13و 14و 18 این فرد مشغول کار نبوده است و مشکلی هم در روال کار بوجود نیامده است. اگر روزی که بوده باشد و کاری انجام نداده باشد فروش صفر برای فرد در نظر گرفته می شود مثل روز 21 یکم کاربری که با رنگ آبی مشخص شده است.

برای ذخیره کردن این اطلاعات جدول زیر را در نظر گرفته ایم:

  CREATE TABLE Sales

  (user_nbr INTEGER NOT NULL,

  day_nbr INTEGER NOT NULL

  CHECK(day_nbr BETWEEN 1 AND 365),

  Value INTEGER NOT NULL

  CHECK(value >= 0),

  PRIMARY KEY (user_nbr, day_nbr));

حالا قصد ما این است که توسط یک SELECT تنها لیست افرادی را بدست آوریم که دارای شرط ما باشند. نکته اینکه ممکن است یک فرد در چند توالی فروش صعودی داشته باشد ولی یکبار بیشتر نمی خواهیم نام فرد انتخاب شود. مثلا از روز پنجم تا نهم پنج روز متوالی فروش صعودی داشته است و همچنین در روز بیستم تا بیست هشتم بازهم 5 روز متوالی فروش صعودی داشته است.

داده های آزمایشی را برای تست راه حلتان استفاده کنید. جواب باید 1 باشد.

  INSERT INTO Sales

  VALUES (1, 12, 60),

  (1, 15, 70),

  (1, 16, 80),

  (1, 17, 83),

  (1, 19, 86),

  (1, 20, 90),

  (1, 21, 90),

   

  (2, 12, 80),

  (2, 13, 70),

  (2, 14, 70),

  (2, 17, 50),

  (2, 18, 60),

  (2, 19, 70),

  (2, 20, 80),

  (2, 21, 0),

   

  (3, 12, 70),

  (3, 13, 60),

  (3, 14, 50),

  (3, 15, 60),

  (3, 16, 60),

  (3, 17, 65),

  (3, 21, 65),

   

  (4, 1, 5),

  (4, 2, 6),

  (4, 3, 6),

  (4, 4, 7),

  (4, 5, 8),

   

  (5, 1, 1),

  (5, 2, 2),

  (5, 3, 3);

راه حل ها
اولین راه حل توسط آقای رضا یاراحمدی پیشنهاد شد. روشی که معرفی شد توسط ایشان سطر جاری را با 4 سطر بعدی (بر اساس نزدیک ترین روز) اتصال می داد و در صورتی که 5 مقدار به ترتیب از همدیگر بزرگتر بودند در خروجی اعلام می شد. و از آنجایی که ممکن بود فردی در بیش از 5 روز فروش صعودی داشته باشد یا اینکه در دو بازه ی زمانی جدا از هم 5 روز فروش صعودی داشته باشد از کلید واژه ی DISITNCT استفاده شده بود تا فروشنده های تکراری را حذف کند.
subquery های وابسته قطعا هزینه ی بالایی را به سیستم تحمیل می کرد و همچنین هزینه توسعه ی این روش بسیار بالا بود و به عبارتی قابل تعمیم به سختی بود. و برای مقادیر متغیر قابل استفاده نبود.

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

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

/*Msalim 4: 238 Chars*/

SELECT DISTINCT user_nbr

  FROM Sales S

 WHERE (SELECT COUNT(*)

          FROM Sales D

         WHERE S.user_nbr = user_nbr

           AND S.day_nbr < day_nbr

           AND S.value < value

           AND NOT EXISTS

               (SELECT *

                  FROM Sales

                 WHERE user_nbr = S.user_nbr

                   AND day_nbr > S.day_nbr AND day_nbr < D.day_nbr

                   AND value <= S.value)) >= 5;

[Reza_Yarahmadi]

تنها راه حلی که من به ذهنم رسید (راه حلی که فقط از دستورات استاندارد استفاده شده باشه) دستور زیره. نمیدونم منظور شما از یک Select چیه ولی به نظرم این کد از 6 Select استفاده کرده!!

Select    Distinct S1.user_nbr

From    Sales S1, Sales S2, Sales S3, Sales S4, Sales S5

Where    

        S1.user_nbr = S2.user_nbr 

        AND 

        S2.day_nbr = (Select MIN(day_nbr) From Sales Where user_nbr = S1.user_nbr AND day_nbr > S1.day_nbr) 

        AND

        S1.user_nbr = S3.user_nbr 

        AND 

        S3.day_nbr = (Select MIN(day_nbr) From Sales Where user_nbr = S1.user_nbr AND day_nbr > S2.day_nbr) 

        AND

        S1.user_nbr = S4.user_nbr 

        AND 

        S4.day_nbr = (Select MIN(day_nbr) From Sales Where user_nbr = S1.user_nbr AND day_nbr > S3.day_nbr) 

        AND

        S1.user_nbr = S5.user_nbr 

        AND 

        S5.day_nbr = (Select MIN(day_nbr) From Sales Where user_nbr = S1.user_nbr AND day_nbr > S4.day_nbr) 

    AND

        S1.Value < S2.Value

        AND

        S2.Value < S3.Value

        AND

        S3.Value < S4.Value

        AND

        S4.Value < S5.Value

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

راه حل شما مورد قبول است.
منظور از "یک عبارت SELECT" اینکه که از دستورات دیگه ای چون INSERT یا ... در بدست آوردن نتیجه استفاده نشود.
یک عبارت SELECT میتونه در ماده های مختلفش مثل WHERE از عبارات SELECT دیگه استفاده کنه. ولی روی هم رفته باز یک عبارت SELECT در نظر گرفته میشه. الان راه حل شما هم یک عبارت SELECT هست. که از 4 سلکت داخلی که در ماده WHERE وجود داره تشکیل شده است.

گرچه بنظر میرسه باید اشاره کنم که INNER JOIN هم جز ANSI/ISO محسوب میشه. شما امکان استفاده از این Syntax هم دارین.

[حمیدرضاصادقیان]

سلام.
منم این راه به ذهنم رسید.

Select S1.User_Nbr,COUNT(Distinct S1.Day_nbr) As DaySales

    From Sales S1 

    Left Outer Join 

        Sales S2

    On S1.user_Nbr=S2.User_nbr

Where S1.Value>S2.Value And S1.day_nbr>S2.Day_nbr

Group by S1.User_Nbr

Having count(distinct S1.Day_nbr)>5

توضیح مختصر هم اینکه بدون استفاده از Having دستور Select لیست کلیه فروشهای مشتریان رو میاره که روز فعلی از روز بعد بیشتره و فروشهایی که روز فعلی از روز بعد کمتره یا برابره حذف میشه. بعد با استفاده از Having نیز تعداد روزهای فروش هر کاربر بدست میاد که بیشترین آنها مربوط به کاربر 1 و برابر 6 است.

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

سلام،
متاسفانه باید بگم راه حلتون جواب مورد نظر را تولید نمیکنه. درنتیجه مورد قبول نیست.
ببینید، کوئری که نوشتین میاد User_nbr هایی رو انتخاب میکنه که مقادیر متناظر آن از بیش از 5 سطر که value و day_nbr کمتری دارند بزرگتر است. ولی شما موضوع ترتیب رو فراموش کردین.

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

INSERT INTO Sales(user_nbr, day_nbr, Value)

SELECT 1, 18, 50

ولی متاسفانه کوئری شما بازم نتیجه ای غیر از empty set تولید میکند.

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

اینهم اولین راه حل من، که از 435 کاراکتر بدون space تشکیل شده، راه حل آقای Reza_Yarahmadi از 610 کاراکتر تشکیل شده.
متاسفانه خوانایی این راه حل نزدیک به صفر است به این معنا که غیر ممکن است که با نگاه سطحی و گذرا قادر به درک این شویم که هدف از این کوئری چیست و به دنبال گرفتن چه نتیجه است. ولی نقطه مثبت آن به غیر از کوتاهی این است که برای هر تعداد sequence (که در اینجا 5 است) قابل استفاده است. در واقع کافیست عدد 5 را بصورت پارامتر در نظر بگیرید. در نتیجه نیاز به توسعه ندارد.

/*Msalim 1: 435  Characters (no space)*/

SELECT DISTINCT user_nbr

  FROM (

          SELECT *, 

                 (SELECT COUNT(*) 

                    FROM Sales S5

                   WHERE S5.user_nbr = S1.user_nbr

                     AND S5.day_nbr <= S1.day_nbr) rn

            FROM Sales S1

       ) AS S1

 WHERE EXISTS (SELECT 1

                 FROM (

                         SELECT (SELECT COUNT(*)

                                   FROM Sales S2

                                  WHERE S2.user_nbr = S3.user_nbr

                                    AND S2.day_nbr <= S3.day_nbr) rn1,

                                (SELECT COUNT(*)

                                   FROM Sales S4

                                  WHERE S4.user_nbr = S3.user_nbr

                                    AND S4.value < S3.value) + 1 rn2, *

                           FROM sales s3

                     ) d

               WHERE D.user_nbr = S1.user_nbr

                 AND D.rn1 BETWEEN S1.rn

                               AND rn + 4

              HAVING COUNT(*) = 5

                 AND MAX(D.rn1 - D.rn2) = 0

            ); 

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

نکته: توابع Ranking در سال 99 میلادی به زبان SQL اضافه شدن اگه اشتباه نکنم. در نتیجه توابعی چون RANK یا ROW_NUMBER نیز استاندارد هستند. ولی در این مورد چون هدف نوشتن یک راه حل super-portable هست از استفاده از این توابع صرف نظر شده است. مثلا MS Access هنوز این توابع رو ساپرت نمیکنه. ولی ما میخواهیم راه حل حتی در Access نیز اجرا شود.

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

راه حل دوم: 413 کاراکتر.
ولی هنوز راه حل اولم کوتاه ترین هست چرا که با حذف یکسری کاراکترهای غیر ضروری تونستم تعداد کاراکتر هاش رو به 407 تا کاهش بدم.
این روش رو خیلی دوست دارم چون کوتاه، ساده و خواناست.

/*Msalim 2: 413 Chars*/

SELECT DISTINCT a.user_nbr

  FROM Sales A, Sales B, Sales C, Sales D, Sales E

 WHERE A.user_nbr = B.user_nbr

   AND B.user_nbr = C.user_nbr

   AND C.user_nbr = D.user_nbr

   AND D.user_nbr = E.user_nbr

   AND B.day_nbr > A.day_nbr

   AND C.day_nbr > B.day_nbr

   AND D.day_nbr > C.day_nbr

   AND E.day_nbr > D.day_nbr 

   AND A.value < B.value

   AND B.value < C.value

   AND C.value < D.value

   AND D.value < E.value

   AND (SELECT COUNT(1) 

          FROM sales 

         WHERE user_nbr = a.user_nbr 

           AND day_nbr BETWEEN a.day_nbr AND e.day_nbr) = 5;

[حمیدرضاصادقیان]

سلام،
متاسفانه باید بگم راه حلتون جواب مورد نظر را تولید نمیکنه. درنتیجه مورد قبول نیست.
ببینید، کوئری که نوشتین میاد User_nbr هایی رو انتخاب میکنه که مقادیر متناظر آن از بیش از 5 سطر که value و day_nbr کمتری دارند بزرگتر است. ولی شما موضوع ترتیب رو فراموش کردین.

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

INSERT INTO Sales(user_nbr, day_nbr, Value)

SELECT 1, 18, 50

ولی متاسفانه کوئری شما بازم نتیجه ای غیر از empty set تولید میکند.

حق با شماست. دیشب که اینو نوشتم دیگه ترتیبش رو دقت نکردم و جواب لازم رو نمیده.البته فکر میکنم اگر Row_Number رو براساس روز یا مقدار اون ایجاد کنیم این مشکل هم حل بشه.درسته؟اینجوری راه حل کوتاه تر هم خواهد شد.

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

در پست شماره 7 اشاره کردم که Row_num قابل استفاده نیست، این جزء محدودیت های راه حله.
شما مجاز هستین که row_number رو از تکنیک های دیگه پیاده سازی کنید و در کوئریتون استفاده کنید. من تا راه حل کامل و صحیح رو نبینم نمی تونم راجب کوتاه یا بلند بودنش نظر بدم.

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

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

/*Msalim 3: 306 Chars*/

SELECT DISTINCT A.user_nbr

  FROM Sales A

    JOIN Sales B

      ON A.user_nbr = B.user_nbr

      AND A.day_nbr < B.day_nbr

      AND A.value < B.value

      AND EXISTS

          (SELECT 1

             FROM (SELECT CASE WHEN value > A.value THEN 1 END C

                     FROM Sales

                    WHERE user_nbr = A.user_nbr

                      AND day_nbr > A.day_nbr AND day_nbr < B.day_nbr

                  )D

           HAVING COUNT(*) = SUM(C))

  GROUP BY A.user_nbr, A.day_nbr

  HAVING COUNT(*) >= 4;

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

راه حل چهارم: 238 کاراکتر

/*Msalim 4: 238 Chars*/

SELECT DISTINCT user_nbr

  FROM Sales S

 WHERE (SELECT COUNT(*)

          FROM Sales D

         WHERE S.user_nbr = user_nbr

           AND S.day_nbr < day_nbr

           AND S.value < value

           AND NOT EXISTS

               (SELECT *

                  FROM Sales

                 WHERE user_nbr = S.user_nbr

                   AND day_nbr > S.day_nbr AND day_nbr < D.day_nbr

                   AND value <= S.value)) >= 5;