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ự).
Thêm cột grp (= val - rn)
Để ý là khi dùng group by thì giá trị đầu và cuối của chuỗi được xác định là giá trị val nhỏ 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.
create table Tabibitosan as
select 1 as val from dual union all
select 2 from dual union all
select 3 from dual union all
select 5 from dual union all
select 6 from dual union all
select 7 from dual union all
select 10 from dual union all
select 11 from dual union all
select 12 from dual union all
select 20 from dual union all
select 21 from dual;
select val
,row_number() over (order by val) as rn
,val - row_number() over (order by val) as grp
from Tabibitosan
order by val;
select min(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 query
select val
,row_number() over (order by val) as rn
,val - row_number() over (order by val) as grp
from Tabibitosan
-- End query
) as t1
group by grp
order by 1;
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.
Kết quả sau khi sắp xếp theo thời gian hoàn thành project tăng dần và ngày bắt đầu giảm dần.
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.
Bỏ cột range_count, 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.
create table if not exists ProjectS (
id int not null auto_increment,
Start_Date date not null,
End_Date date not null,
primary key (id)
);
insert into 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 (order by Start_Date) as grp
from Projects;
select
min(Start_Date) as range_start
,date_add(max(Start_Date), interval 1 day) 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 query
select Start_Date
,row_number() over (order by Start_Date) as rn
,Start_Date - row_number() over (order by Start_Date) as grp
from Project
-- End query
) as t1
group by
grp;
select
min(Start_Date) as range_start
,date_add(max(Start_Date), interval 1 day) as range_end
from (
-- Phần query tạo bảng chứa 3 cột (Start_Date, rn và grp)
-- Start query
select Start_Date
,row_number() over (order by Start_Date) as rn
,Start_Date - row_number() over (order by Start_Date) as grp
from Project
-- End query
) as t1
group by
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ần
order by
count(*)
,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 not in (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 not in (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 by
group by
Start_Date
order by
-- 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.
