Mục lục
Giới thiệu
Hôm trước, tôi có giải một câu SQL trên HackerRank và tình cờ phát hiện ra một kỹ thuật hay tên là Tabibitosan (đọc là ta-bi-bi-tô-san). Kỹ thuật này được một người Nhật tên Aketi Jyuuzou giới thiệu lần đầu ở cộng đồng Oracle vào năm 2011 dựa trên đề thi đầu vào của một trường trung học Nhật.
Ý tưởng của kỹ thuật này là thực hiện là so sánh vị trí của các hàng trong nhóm với tập hợp các hàng tổng thể, để tìm ra liệu các hàng trong cùng một nhóm có cạnh nhau hay không.
Hừm, nghe có vẻ rắc rối nhỉ? Tạm bỏ qua cái định nghĩa kia đi. Chúng ta sẽ đi vào một ví dụ đơn giản nhé.
Bài toán
Giả sử bạn có cột dữ liệu val chứa các số như sau:
Chúng ta dễ thấy có những khoảng số liên tiếp không bị ngắt quãng là 1-3, 5-7, 10-12 và 20-21. Câu hỏi đặt ra là làm sao có thể nhóm chúng với nhau trong SQL?
Phương pháp
Bây giờ, tôi thêm cột số thứ tự rn , rồi thêm cột grp là kết quả khi trừ cột val cho cột rn. Ồ nhìn xem, tôi đã tạo ra một identical number cho mỗi chuỗi số.
Tạo bảng mới từ bảng đã cho và thêm cột rn (số thứ tự).
Để ý là khi dùng group by thì giá trị đầu và cuối của chuỗi được xác định là giá trị valnhỏ nhất và lớn nhất. Ví dụ, với grp = 0 thì chuỗi sẽ là 1-3. Dễ hiểu phải không nào?
SQL scripts
Giờ chúng ta sẽ dùng các scripts dưới đây để test trong MySQL.
createtable Tabibitosan asselect1as val from dual unionallselect2from dual unionallselect3from dual unionallselect5from dual unionallselect6from dual unionallselect7from dual unionallselect10from dual unionallselect11from dual unionallselect12from dual unionallselect20from dual unionallselect21from dual;select val
,row_number()over(orderby val)as rn
,val - row_number()over(orderby val)as grp
from Tabibitosan
orderby val;selectmin(val)as range_start
,max(val)as range_end
,count(*)as range_count
from(-- Đây là câu query để thêm 2 cột rn và grp ở trên-- Start queryselect val
,row_number()over(orderby val)as rn
,val - row_number()over(orderby val)as grp
from Tabibitosan
-- End query)as t1
groupby grp
orderby1;Challenge
Đề bài HackerRank
- Link câu hỏi: https://www.hackerrank.com/challenges/sql-projects/problem
- Bạn hãy chú ý vào từ mà tôi gạch chân ở hình dưới. Đây là những keywords của câu hỏi.
Đây là toàn bộ đề bài HackerRank. Hãy chú ý vào những từ mà tôi gạch chân
Phân tích câu hỏi
- Input: 1 bảng
Projectscó 3 cộtTask_ID(integer),Start_Date(date) vàEnd_Date(date). - Output: Ngày bắt đầu và kết thúc của tất cả project, sắp xếp theo thời gian hoàn thành project tăng dần và ngày bắt đầu project giảm dần. Hay chúng ta có thể hiểu là ngày bắt đầu và kết thúc của các chuỗi ngày liên tiếp nhau.
- “It is guaranteed that the difference between the End_Date and the Start_Date is equal to 1 day for each row in the table.” ⇒ Mỗi dòng sẽ có
Start_Date - End_Date = 1.
Input là bảng Projects có 3 cột
Kết quả trước khi sắp xếp
Lời giải
Cách giải 1 áp dụng kỹ thuật Tobibitosan
Vì mỗi dòng sẽ có Start_Date - End_Date = 1 nên chúng ta chỉ cần dùng tới cột Start_Date và bỏ qua cột End_Date. Chúng ta sẽ lặp lại các bước như ở bài toán ví dụ.
Tạo 1 bảng mới từ bảng Projects có 3 cột là Start_Date, rn (số thự tự) và cột grp (= Start_Date – rn)
Nhóm các dòng có cùng grp, Start_Date là giá trị nhỏ nhất, còn End_Date sẽ là giá trị lớn nhất + 1 ngày.
createtableifnotexists ProjectS (
id intnotnullauto_increment,
Start_Date datenotnull,
End_Date datenotnull,primarykey(id));insertinto ProjectS (Start_Date, End_Date)values("2015-10-01","2015-10-02"),("2015-10-02","2015-10-03"),("2015-10-03","2015-10-04"),("2015-10-13","2015-10-14"),("2015-10-14","2015-10-15"),("2015-10-28","2015-10-30"),("2015-10-30","2015-10-31");select
Start_Date
,id as rn -- Chúng ta đã có sẵn cột số thứ tự là id,Start_Date - row_number()over(orderby Start_Date)as grp
from Projects;selectmin(Start_Date)as range_start
,date_add(max(Start_Date),interval1day)as range_end
,count(*)as range_count
from(-- Phần query tạo bảng chứa 3 cột (Start_Date, rn và grp)-- Start queryselect Start_Date
,row_number()over(orderby Start_Date)as rn
,Start_Date - row_number()over(orderby Start_Date)as grp
from Project
-- End query)as t1
groupby
grp;selectmin(Start_Date)as range_start
,date_add(max(Start_Date),interval1day)as range_end
from(-- Phần query tạo bảng chứa 3 cột (Start_Date, rn và grp)-- Start queryselect Start_Date
,row_number()over(orderby Start_Date)as rn
,Start_Date - row_number()over(orderby Start_Date)as grp
from Project
-- End query)as t1
groupby
grp
-- Sắp xếp theo thời gian hoàn thành project tăng dần và ngày bắt đầu project giảm dầnorderbycount(*),range_start;Cách giải 2
Đây là cách lúc đầu tôi tiếp cận, ý tưởng ban đầu là tạo ra 2 bảng t1 và t2 từ bảng Projects lần lượt chứa các giá trị Start_Date và End_Date thoả mãn đề bài, rồi tìm cách join 2 bảng đó lại với nhau và lọc ra kết quả đúng.
Các bước thực hiện sẽ như sau:
- Tạo ra bảng
t1có 1 cột chứa các giá trịStart_Datevà bảngt2có 1 cột chứa các giá trịEnd_Datecần tìm - Dùng cross join để liên kết 2 bảng này với nhau
- Lọc bỏ các giá trị không thoả mãn bằng
where - Nhóm các giá trị trùng với
group by - Cuối cùng, sắp xếp data bằng
order by.
select
Start_Date,min(End_Date)as End_Date
from-- tạo bảng t1 có 1 cột chứa các giá trị Start_Date(select Start_Date from Projects where Start_Date notin(select End_Date from Projects)) t1,-- tạo bảng t2 có 1 cột chứa các giá trị End_Date (select End_Date from Projects where End_Date notin(select Start_Date from Projects)) t2
-- Bỏ các giá trị không hợp lệwhere
Start_Date < End_Date
-- Nhóm các giá trị trùng bằng group bygroupby
Start_Date
orderby-- Sắp xếp theo khoảng cách giữa ngày bắt đầu và ngày kết thúc giảm dần
DATEDIFF(Start_Date,min(End_Date))desc,-- Sắp xếp theo ngày bắt đầu tăng dần
Start_Date;Tổng kết
Wow, chỉ với một câu HackerRank tôi nghĩ mình đã học được kha khá kiến thức về SQL từ select, join, subquery, where, tới group by, order by và cả kỹ thuật xác định các phạm vi giá trị tuần tự có cái tên tiếng Nhật rất vui tai là Tabibitosan.
Tham khảo
Nguồn: viblo.asia