Khoe

Được cái này, nhờ bài báo này. Như bạn mlteppi đã loan báo từ trước.

Bài báo “Worst-case optimal join algorithms” có một lịch sử thú vị liên quan đến blog KHMT. Số là năm ngoái bọn tôi làm một vấn đề về giải mã tín hiệu trong compressed sensing. (Bài ở STACS 2012.) Một trong những kết quả tìm được là một thuật toán cho bài lính bắn tia laser. Bài lính bắn laser vốn là một bất đẳng thức hình học, và do có cấu trúc khá chặt chẽ tôi thấy rất khó chịu khi thuật toán chỉ làm cho trường hợp 3-chiều. Tôi có viết trong một lời bình ngày 1 tháng 3, 2011 là

Tôi tin là có chứng minh tốt hơn cái CM tôi có, và có lẽ đây là trường hợp đặc biệt của cái gì đó đã biết, nhưng tôi không biết là cái gì.

Bài học 1: luôn không thoả mãn với các trường hợp đặc biệt. Nếu kết quả của mình có vẻ cơ bản thì nó phải là một ví dụ của cái gì đó tổng quát hơn, đẹp hơn!

May có bác Xuân Long cho ngay câu trả lời: đó là trường hợp đặc biệt của bất đẳng thức Loomis-Whitney. Từ đó bọn tôi đi tìm hiểu xem cách chứng minh bài laser của mình có dùng để chứng minh BĐT Loomis-Whitney hay không. Đây là chứng minh bằng thuật toán: cho các hình chiếu, xây dựng lại bộ tập điểm ban đầu, chứ không phải chứng minh BĐT toán học tuần tuý. Nếu chỉ chứng minh toán học thuần tuý thì cái chứng minh dùng entropy là tuyệt hảo rồi.

Sau một tháng, ngày 8 tháng 4, tôi ghi lại một chứng minh khác của BĐT Loomis-Whitney không dùng entropy cũng trên blog này. Lúc đó bác Nguyễn Tiến Zũng có bình luận là “chứng minh entropy có gì phù thuỷ đâu“?

Bài học 2: có sự khác biệt giữa tư duy toán học và tư duy KHMT. Dân KHMT thường nên nghĩ về thuật toán chứ không chỉ một chứng minh toán học thuần tuý.

Một trong những thứ mà tôi nhận ra ngay từ bài lính bắn laser là đây là một bài toán conjunctive join trong cơ sở dữ liệu quan hệ (relational database). Sau một vài tháng suy nghĩ thì bọn tôi tìm được một thuật toán “chứng minh” BĐT Loomis-Whitney. Tuy nhiên cái chứng minh (bằng thuật toán) này chứng minh được một BĐT yếu hơn Loomis-Whitney một chút. Dù sao, nó cũng là một kết quả thú vị về conjunctive query evaluation và bọn tôi viết lại, nộp vào SODA 2012. Các bác referees cũng khá thích kết quả này, nhưng họ càm ràm rằng lớp các conjunctive queries mà BĐT Loomis-Whitney đại diện quá đặc biệt; cần kết quả mạnh hơn. Thế là bài báo không được nhận dù review khá tốt.

Bài học 3: đôi khi một bài báo bị từ chối là một điều tốt.

Lẽ tất nhiên, bọn tôi lại phải quay lại với bút chì và giấy nháp; cố gắng thử xem thuật toán của mình có dùng để evaluate các conjunctive queries tổng quát hơn hay không. Nhưng cũng chằng đi đến đâu.

Trước đó, tôi gọi điện hỏi bác An Hải — nói cho bác ấy biết là bọn tôi có một thuật toán mới cho conjunctive join. Bác AH bảo: “không có thằng nào đi implement thuật toán mới đâu, đừng có nằm mơ, các RDBMS engines có mấy chục năm heuristics ở trong đó, inertia rất lớn, blah blah blah. Tuy nhiên, ở Wisconsin có chú Chris Ré làm lý thuyết, hay liên lạc với chú ấy xem sao.”

Bài học 4: gọi điện hỏi, nhưng đừng nghe lời bác An Hải.

Trùng hợp là một đồng tác giả của tôi, Atri Rudra, học cùng trường với Chris Ré. Sau khi liên lạc thì Chris rất thích kết quả (yếu) về BĐT Loomis-Whitney và đi hỏi các chuyên gia về join optimization. Cuối cùng, bọn tôi khám phá rất một bài báo tuyệt vời của Atserias-Grohe-Marx ở FOCS 2008. Bài báo này chứng minh một bất đẳng thức tổng quát cho mọi (full) conjunctive queries, mà trong đó Loomis-Whitney là một trường hợp đặc biệt. Hãy gọi bất đẳng thức này là BĐT AGM. BĐT AGM cũng được chứng minh bằng entropy như BĐT Loomis-Whitney.

Thế là bọn tôi chuyển hướng nghiên cứu thuật toán chứng minh BĐT AGM — và cũng là thuật toán evaluate conjunctive queries. Thuật toán trước đó cho LW không giải quyết được trường hợp tổng quát này. Do thuật toán được thiết kế cho LW, một trường hợp đặc biệt, nó tận dụng quá nhiều cấu trúc của trường hợp đặc biệt và do đó không thể tổng quát hoá nó lên.

Bài học 5: giải trường hợp tổng quát có thể “dễ” hơn trường hợp đặc biệt, và thường là sẽ cho lời giải “đúng” hơn với bản chất vấn đề.

Cuối cùng, sau khoảng 3, 4 tháng bí rị, trong vòng 1 tuần bọn tôi tìm ra thuật toán vừa chứng minh BĐT AGM, vừa là một thuật toán tối ưu cho conjunctive join. Lý do có thể “đục thủng” được sự bí rị là vì thuật toán trước chứng minh một phiên bản yếu của LW, và rất không đẹp. Cho nên quyết định chứng minh lại Loomis-Whitney một cách chặt chẽ dùng một thuật toán mới. Sau đó tổng quát hoá thuật toán mới này lên AGM.

Bài học 6: luôn luôn cảm thấy khó chịu với các lời giải không đẹp.

Lúc đó gần tháng 11. Định nộp vào STOC nhưng viết không kịp; vả lại PODS là hội nghị DB nên có lẽ là người ta “appreciate” kết quả này hơn.

Thuật toán cuối cùng phức tạp hơn thuật toán ban đầu cho LW nhiều, nhưng mặt khác nó cũng thoáng hơn vì nó giải quyết trường hợp tổng quát nên ta không bị gò bó vào các cấu trúc lắt nhắt.

OK, khoe đã xong, khi nào rảnh rỗi sẽ viết lại kỹ hơn về conjunctive joins, thuật toán NPRR, và các ứng dụng (nhiều vô kể) của conjunctive join query evaluation.

Link to full article