2-7 SQL và tập hợp hồi quy

Giữa SQL và luận tập hợp Trong SQL thì chìa khoá để lập trình đó là lập trình từ quan điểm của luận tập hợp. Đặc biệt là những tập hợp con mà trong tập hợp lại có tập hợp, hay chính là những tập hợp hồi quy thì việc biết được cách sử dụng của nó mang lại ý nghĩa rất quan trọng. Chương này sẽ nhắc đến tính quan trọng của tập hợp hồi quy đối với SQL.

Tập hợp hồi quy trong công việc

Mọi người còn nhớ quyển sách này đã giới thiệu một SQL để tính ranking bằng tự kết hợp không đồng giá trị mà không sử dụng hàm RANK trong chương "Cách sử dụng tự kết hợp" trong phần 1 không? Chúng ta có thể nghĩ đó là truy vấn tìm luỹ kế sử dụng subquery tương quan cũng không sai. Đây cũng là vấn đề được đề cập một chút tại những chương đó nhưng cách nghĩ cơ sở của truy vấn đó chính là định nghĩa số tự nhiên sử dụng tập hợp hồi quy theo Neumann.

Có lẽ khi đầu tiên nhìn thấy cách suy nghĩ như thế này thì mọi người chắc chắn sẽ ngạc nhiên. Đây chính là một ví dụ tốt chỉ sự liên kết mật thiết giữa SQL và luận tập hợp, nhưng việc kết nối số và tập hợp thì ngoài dự tính sẽ có những người không biết được bản chất đằng sau. Là đương nhiên nếu chúng ta có những nghi vấn như "Tại sao Neumann lại có một cách suy nghĩ đột biến như định nghĩa số tự nhiên bằng tập hợp được". Trong chương này qua những câu chuyện mang tính lịch sử xung quanh mong rằng sẽ giúp ích để giải quyết những nghi vấn này của mọi người. Trong bối cảnh mà Neumann đưa ra ý tưởng về tập hợp hồi quy này chắc hẳn có những thứ gọi là tiền đề phía trước.

Những tiền bối của Neumann

Đề án định nghĩa số tự nhiên theo tập hợp hồi quy của Neumann chính là luận văn về đưa vào số thứ tự siêu hạn (transfinite ordinals) năm 1923. Đây là bản luân văn thứ 2 của ông, đây có thể là câu chuyện mà các bạn sẽ không thích nhưng lúc viết bản luận văn này, ông mới chỉ là học sinh cấp 3. Tên của bản luận văn là số thứ tự nhưng nói một cách đúng hơn, thứ mà Neumann nêu ra ở đây không là định nghĩa số tự nhiên mà chính là định nghĩa về số thứ tự. Số thứ tự cũng như cái tên của nó chính là tên gọi của số tự nhiên khi ý thức về thứ tự như sau 0 là 1, sau 1 là 2, sau 2 là 3,...

Thực tế, nhìn vào định nghĩa của Neumann thì đầu tiên định nghĩa 0, rồi sử dụng 0 để định nghĩa 1, tiếp theo dùng 1 để định nghĩa 2,... Chúng ta đã xem cái này ở phần tự kết hợp nhưng ở đây lại xem lại một lần nữa.

Trong các bước của định nghĩa đúng là có thứ tự. Để định nghĩa 3 thì cần có 2. Để định nghĩa 2 thì cần có 1. Để định nghĩa 1 thì phải có 0. Chính từ đó, để định nghĩa một số thì nhất thiết phải chuẩn bị số đằng trước nó. Chính vì đặc trưng mang tính bậc thang này nên nó được gọi là định nghĩa mang tính quy nạp. Trong SQL, bằng việc đếm số yếu tố của tập hợp đang định nghĩa từng số tự nhiên thì ta có thể áp dụng nó để tính toán xếp hạng.

Và từ đây sẽ là trung tâm của câu chuyện lần này. Thực ra, nghĩ về cách định nghĩa có tính quy nạp số tự nhiên như thế này thì Neumann không phải là người đầu tiên. Trước đó thì cũng ít nhất 2 người đã đề ra ý tưởng đó. Một người là Gottlob Frege. Là nhà triết học vĩ đại đã sáng tạo ra một cơ sở của mô hình quan hệ, là logic vị từ. Một người nữa là Ernst Zermelo, nhà toán học được biết đến là người đã hoàn thiện luận tập hợp hiện tại,... Đây cũng là nhân vật lớn để lại tên tuổi trong lịch sử nền toán học thế giới.

Phương pháp của 2 người cũng bắt đầu chia tập hợp từ 0 và bằng một luật nào đó định nghĩa ra 1,2,3,... Chúng ta cùng nhìn và so sánh cách làm của 3 người qua bảng sau.

Nhìn bảng trên có thể chúng ta sẽ bị hoa mắt bởi số lượng dấu ngoặc nhưng nói chung cách làm của 3 người cũng có những điểm chung và cũng có những điểm đặc trưng riêng biệt. Đầu tiên, đập vào mắt chính là độ đơn giản của mô hình Zermelo. Điểm bắt đầu tập hợp là tập hợp rỗng là điểm giống với Neumann nhưng điểm đơn giản của ông là đơn giản chỉ cần thêm những dấu ngoặc bên ngoài để định nghĩa tiếp. Với tình hình như thế này, số càng cao lên, ví dụ như 30 thì sẽ trở thành hình dạng như sau,

{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{∅}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Đây là tập hợp mà ngay cả những lập trình viên Lisp cũng phải ngạc nhiên vì sự đồ sộ của nó. Nhưng cũng không cần lo lắng gì cả. Để xem đây có thực sự biểu diễn số 30 không thì chúng ta có thể đơn giản kiểm tra. Số lượng dấu ngoặc bên trái (hoặc bên phải) chính bằng số cần định nghĩa. Mặt khác, trường hợp Neumann, số thành tố trong tập hợp bằng với số cần định nghĩa.Trong SQL, chúng ta có thể đếm được số thành tố bằng hàm COUNT nên thực khá giống với kiểu mô hình Neumann. Nhưng trong SQL không thể đếm được số dấu ngoặc nên trong SQL không thể sử dụng được mô hình Zermelo.(Mà trong SQL, khi biểu diễn tập hợp thì người ta không sử dụng dấu ngoặc {}).

Mô hình Frege cũng giống với mô hình Neumann về bản chất, nhưng chỉ có điểm 0 không là tập hợp rỗng mà được chia như một tập hợp. Theo tính lịch sử thì mô hình Freger là cũ nhất vào năm 1884, sau đó chúng ta có thể nghĩ mô hình của Neumann và Zermelo như là bản cải thiện của nó. Noimann là người có khả năng đặc biệt lấy ngang ý tưởng của người khác và biến nó từ một thứ bình thường thành một thứ siêu việt.

Cho đến đây thì chúng ta đã biết được ý tưởng của Neumann đang đứng ở vị trí nào trong dòng chảy lịch sử, nhưng chúng ta vẫn chưa giải quyết được 2 nghi vấn đặt ra bên trên.

1. Có nhiều cách định nghĩa số thứ tự thế này có được không. Nói về định nghĩa thì không phải bình thường chỉ có 1 thôi sao?
2. Tại sao lại có ý định lấy tập hợp để định nghĩa số thứ tự?

Cái nào cũng là nghi vấn. Vậy chúng ta cùng giải quyết từng cái một. Về những nghi vấn này thì cho đến đầu thế kỉ 20 mới được chú ý một chút.

Số là gì?

Chúng ta thường ngày khi học những khái niệm về số như 0,1 thì luôn lý giải gắn với số của vật cụ thể. Hồi cấp 1 mọi người chắc cũng nhớ, những bài toán trong sách giáo khoa hầu hết đều có những bức tranh về táo hay cam. Nhưng nếu nghĩ về định nghĩa thông thường của số thì sẽ không tốt nếu chúng ta gắn nó với một vật cụ thể là rất nguy hiểm. Nếu sử dụng táo để định nghĩa 1 thì đối với những đứa trẻ chưa từng nhìn thấy táo thì chắc chắn sẽ không hiểu được. Thực ra trển thực tế giữa những người biết hay không biết quả táo thì cũng có thể hình thành được những lý giải chung về số 1. Có nghĩa là số không bị buộc vào vật gì cụ thể mà phải định nghĩa theo một đối tượng có tính trừu tượng thông thường nào đó.

Nhà toán học tài giỏi lần đầu tiên nêu lên định nghĩa thông thường của số tự nhiên là nhà toán học người Ý, Giuseppe Peano. Ông ấy vào năm 1891 đã đưa ra 5 điều kiện mà số tự nhiên cần thoả mãn dựa trên chuẩn là số nào cứ thoả mãn một điều kiện nào đó thì sẽ được coi như là số tự nhiên. Đến bây giờ vẫn còn để lại một định nghĩa về số tự nhiên tên là hệ tiên đề Peano. (Trong đó có 5 tiên đề của Peano là

1. Tồn tại số ban đầu
2. Với một số tự nhiên a bất kì phải có số đằng sau nó
3. Số đầu tiên không là số đằng sau bất kì số tự nhiên nào
4. Những số tự nhiên khác nhau có những số sau nó khác nhau
5. Số ban đầu thoả mãn một tính chất nào đó, a nếu thoả mãn một tính chất mà số sau nó cũng thoả mãn tính chất đó thì cả dãy số tự nhiên sẽ thoả mãn tính chất đó.)

Nó cũng giống như đối với câu hỏi "Mong muốn đối tượng kết hôn là người đàn ông như thế nào" thì không phải sẽ trả lời là nêu một đối tượng cụ thể là "Anh Tanaka ở bộ phận kinh doanh" mà chúng ta phải nêu ra những điều kiện mà người đó cần thoả mãn như "Tốt nghiệp đại học Tokyo rồi làm việc cho bộ phận đầu tư nước ngoài, rồi thu nhập một năm trên 10 triệu yên,...". Cứ là người thoả mãn những điều kiện đó thì ai cũng trở thành đối tượng kết hôn, đó chính là tư tưởng của Peano.

Nội dung điều kiện đòi hỏi của số tự nhiên theo Peano hầu hết đều là những điều đương nhiên như "Trước 0 không tồn tại số tự nhiên nào",... Nếu là con người thì đó đều là những điều kiện cấp thấp như "Không phải là vũ phu" hay "Không là người mê bài bạc". Tuy nhiên, trong đó có một điều kiện quan trọng có liên quan đến câu chuyện lần này là

Với một số tự nhiên a bất kì thì chắc chắn tồn tại số đằng sau nó (successor)

Sau 5 phải có 6, sau 1988 phải có 1989, mà đó cũng là một điều kiện đương nhiên. Những số tự nhiên mà sau 17 có lỗ khuyết, nhảy luôn lên 19 sẽ không trở thành thứ có thể sử dụng được.

Như vậy hàm số phản ánh số tiếp theo của một số tự nhiên nào đó ta viết là suc(x). suc(5) = 6, suc(17) = 18. Như vậy ta có để tạo số tự nhiên sử dụng hàm suc() sẽ có được cách định nghĩa như sau.

0 = 0
1 = suc(0)
2 = suc(cuc(0))
3 = suc(suc(suc(0)))
.
.
.

Nhưng điều quan trọng ở đây là thực ra về hàm suc() này bên trong có nội dung cụ thể thế nào thì hoàn toàn chưa được quyết định. Bên trong thực hiện thao tác nào cũng được, miễn là tồn tại một hàm số có thể sinh ra số tiếp theo là được, đây là một điều kiện vẫn còn lỏng. Nói một cách khác, quay trở lại với điều kiện của đối tượng kết hôn bên trên thì nó sẽ là "Sẽ không hỏi người đó làm nghề gì, miễn là thu nhập hàng năm trên 10 triệu yên là được". Không hỏi về phương pháp mà chỉ có hứng thú với kết quả.

Tất nhiên số tự nhiên mà 3 người trong hội Neumann được nêu bên trên cũng có tồn tại hàm số suc() này.

Hàm suc() của Neumann và Frege: suc(a) = a U {a} Hàm suc() của Zermelo: suc(a) = {a}

Như thế này thì nội dung bên trong hàm suc() của Neumann, Frege hay Zermelo mặc dù có điểm khác nhau nhưng không có vấn đề gì cả. Cũng như kể cả chúng ta leo từ tỉnh Yamanashi hay từ Shizuoka thì cũng có thể leo lên được đỉnh núi Phú Sĩ nên kể cả dùng tool nào đi chăng nữa nhưng chỉ cần đến một số sau đó giống nhau là được. Như thế này, đến đây chúng ta đã giải quyết được nghi vấn đầu tiên. Có nghĩa là điều mà hội Neumann đã làm không phải là định nghĩa số tự nhiên. Định nghĩa chính là 5 điều kiện mà Peano đã nêu, hội Neumann chẳng qua chỉ là tạo nên những thứ hợp với những yêu cầu của Peano mà thôi. Bằng ý nghĩa đó thì công việc của 3 người được gọi là cấu trúc (construction).

Và từ đây sẽ có câu trả lời cho nghi vấn thứ 2. Không cần một tập hợp khác làm nguyên liệu để cấu thành nên số tự nhiên. Trên thực tế, điểm quan hệ sâu với khoa học máy tính ở đây được biết là phương pháp cấu thành sử dụng hàm số theo tính toán ngẫu nhiên. Số tự nhiên được cấu thành từ tính toán ngẫu nhiên được lấy tên từ Alonzo Church thành số Church. Mặc dù gọi là số nhưng thực ra trong đó chúng là một hàm số cấp cao sử dụng hàm số là đầu vào để đưa ra một hàm số. Như vậy chúng ta cũng có thể tạo được số tự nhiên có tính hồi quy như tiếp theo đây.

0 := λfx.x 1 := λfx.fx 2 := λfx.f(fx) 3 := λfx.f(f(fx))

Trong thời gian cuổi thế kỉ 19, đầu thế kỉ 20 mà Neumann, Frege, Zermelo hoạt động thì đại số trừu tượng như thế này chưa được phát triển nên nguyên liệu tiến hành cấu tạo theo định nghĩa có tính trừu tượng cao như thế này trở thành ứng cử là tập hợp được coi như khái niệm có tính trừu tượng cao nhất thời bấy giờ.

Khoa học và ma thuật của SQL

Từ một câu chuyện thực tế như tính toán xếp hạng bằng SQL thì chúng ta đã bay đến những câu chuyện xa xưa trong lịch sử toán học đầu thế kỉ 20. Có thể bay hơi quá chăng? Nhưng tôi nghĩ rằng điểm làm chúng ta giật mình ở đây chính là độ gần ngoài dự đoán giữa lý luận và thực hành trong SQL và cơ sở dữ liệu quan hệ. Ở xa trong cánh cửa của cơ sở dữ liệu quan hệ mở ra một thế giới phong phú một cách bất ngờ. Và chia khoá để mở cánh cửa đó tất nhiên chính là SQL của chúng ta.

Đầu tiên không hiểu nó thực hiện những động tác như thế nào rồi truy vấn tính ra xếp hạng trông như một câu thần chú, nếu chúng ta nhìn xuống phong cảnh đằng sau mang tính logic này thì sẽ nhìn thấy một sự thực là nó được hình thành từ một bộ phận của một hình thái mang tính toán học. Qui trình lý giải từ ma thuật đến khoa học như thế này không sai chính là một trong những vị ngon nhất của công việc làm SE hay là lập trình viên.