Bài báo của Codd năm 1970, chú giải

#TL;DR

Bài báo năm 1970 của Edgar Codd trong Communications of the ACM đã định nghĩa lại cách máy tính lưu trữ dữ liệu. Nó cũng là một tác phẩm viết dày đặc bất thường — một tài liệu mười hai trang âm thầm thả xuống các định nghĩa toán học về quan hệ, khóa ngoại, dạng chuẩn, và một ngôn ngữ truy vấn đầy đủ trong khoảng thời gian của một lần nghỉ cà phê tại hội chợ. Bài viết này đi qua những gì bài báo thực sự nói, các định nghĩa chính xác có nghĩa gì, cái gì đã tồn tại đến SQL, cái gì không, và tại sao Codd cảm thấy cần đấu tranh thêm một thập kỷ sau khi xuất bản để các ý tưởng của chính ông được triển khai theo cách ông dự định.

#Bối cảnh

Năm 1970, Edgar Codd là một nhà toán học gốc Anh làm việc tại Phòng Nghiên cứu IBM San Jose. Ông đã ở IBM gần hai thập kỷ — đủ lâu để thấy thế hệ cơ sở dữ liệu phân cấp đầu tiên (IMS) và cơ sở dữ liệu mạng (CODASYL) trong sản xuất. Ông cho rằng cả hai đều được thiết kế sai. Không phải lỗi — sai về mặt khái niệm.

Bài báo ông xuất bản vào tháng 6 năm 1970, “A Relational Model of Data for Large Shared Data Banks,” là lập luận cho một cách tiếp cận khác. Dày mười hai trang, dày đặc, chính xác về mặt toán học, và rõ ràng nhắm đến các nhà khoa học máy tính hơn là DBA. Nhóm cơ sở dữ liệu của chính IBM phần lớn đã phớt lờ nó trong nhiều năm.

#”Quan hệ” có nghĩa là gì

Bài báo mở đầu với một định nghĩa dễ bị bỏ qua:

Cho các tập S₁, S₂, …, Sₙ (không nhất thiết khác nhau), R là một quan hệ trên n tập này nếu nó là một tập các n-bộ, mỗi bộ có phần tử thứ nhất từ S₁, phần tử thứ hai từ S₂, v.v.

Dịch ra: một quan hệ là một tập các bộ, trong đó mỗi bộ có cùng cấu trúc. Mỗi “tập” Sᵢ được gọi là một miền (domain) — tập tất cả các giá trị có thể mà một vị trí nhất định trong bộ có thể lấy. Ví dụ:

Customers là một quan hệ trên { CustomerID, Name, City }:

(101, "Ada Lovelace", "London")
(102, "Alan Turing",  "London")
(103, "Grace Hopper", "New York")

Mỗi bộ là một phần tử của CustomerID × Name × City — một tích Descartes của ba tập. Quan hệ là tập con của tích Descartes đó. Không phải mọi tổ hợp khả dĩ đều nằm trong quan hệ; chỉ những cái thực sự đại diện cho dữ liệu hợp lệ.

Bài báo cẩn thận phân biệt quan hệ (đối tượng toán học — một tập các bộ) với lược đồ quan hệ (mô tả cấu trúc — tên và kiểu của các cột). Trong SQL, một bảng nôm na là biểu diễn lưu trữ của một quan hệ, nhưng với những khác biệt quan trọng.

#Sự phân biệt Codd quan tâm: Trùng lặp và thứ tự

Hai chi tiết từ bài báo quan trọng rất lớn và không tồn tại đầy đủ đến SQL:

Quan hệ là một tập. Không có bộ trùng lặp. Hai hàng với giá trị giống hệt nhau gộp thành một.
Quan hệ không có thứ tự. Không có hàng “đầu tiên”. Các truy vấn dựa vào thứ tự vật lý đang gian lận — bạn chỉ có thể sắp xếp nếu bạn nói rõ ràng cách sắp xếp.

SQL nới lỏng cả hai. Một bảng SQL về mặt kỹ thuật là một túi (bag) (multiset), không phải một tập — trùng lặp được phép. SQL có SELECT DISTINCT để khôi phục tính chất tập, nghĩa là mặc định là phi-quan hệ. Codd phản đối điều này trong suốt sự nghiệp còn lại của mình. “Quy tắc 1” sau này của ông (từ 12 quy tắc của Codd, xuất bản năm 1980) yêu cầu rõ ràng các bảng phải là quan hệ, không phải túi.

Vấn đề thứ tự tinh vi hơn. SQL không đảm bảo thứ tự hàng không có ORDER BY, nhưng trong thực tế các triển khai thường trả về hàng theo thứ tự chèn hoặc lưu trữ, và code ứng dụng phát triển phụ thuộc vào điều đó. Bài báo của Codd rõ ràng: nếu truy vấn cần kết quả đã sắp xếp, truy vấn phải chỉ định việc sắp xếp. Dựa vào triển khai là một lỗi phạm trù.

#Độc lập dữ liệu: Mục tiêu của bài báo

Động lực của bài báo — và lập luận hệ quả nhất — đến sớm:

Mô hình phổ biến của các ngân hàng dữ liệu có định dạng hiện nay là mô hình cây (hay phân cấp)… Công nghệ như vậy buộc các chương trình phải biết thứ tự cụ thể của biểu diễn lưu trữ.

Tuyên bố của Codd là cơ sở dữ liệu phân cấp và mạng có lỗi thiết kế: code ứng dụng phải biết dữ liệu được lưu trữ vật lý như thế nào. Nếu lưu trữ thay đổi, code hỏng. Thay đổi một index, phân mảnh một bảng, di chuyển sang phần cứng khác — bất kỳ điều nào trong số này có thể yêu cầu viết lại hàng trăm chương trình.

Giải pháp ông đề xuất là độc lập dữ liệu: một sự tách biệt rõ ràng giữa dữ liệu có ý nghĩa gì và được lưu trữ như thế nào. Truy vấn sẽ mô tả kết quả mong muốn; engine cơ sở dữ liệu sẽ tìm ra đường truy cập vật lý. Code ứng dụng sẽ không bao giờ cần biết về index, layout lưu trữ, hay phương pháp truy cập.

Đây là một tuyên bố cách mạng vào năm 1970. Nó yêu cầu hai thứ chưa tồn tại trong bất kỳ cơ sở dữ liệu sản xuất nào:

Một ngôn ngữ truy vấn khai báo có thể mô tả dữ liệu chỉ theo cấu trúc logic.
Một trình tối ưu truy vấn có thể dịch các truy vấn logic thành kế hoạch truy cập vật lý một cách hiệu quả.

Bài báo của Codd phác thảo cái thứ nhất. Cái thứ hai trở thành thách thức kỹ thuật cốt lõi của System R (dự án nghiên cứu 1974-79 của IBM) và mọi cơ sở dữ liệu sau đó.

#Đại số quan hệ

Bài báo giới thiệu một tập các phép toán trên quan hệ mà cùng nhau tạo thành đại số quan hệ. Đây là các nguyên thủy mà một ngôn ngữ truy vấn cuối cùng sẽ phơi bày. Danh sách gốc của Codd:

σ (Chọn) — chọn các bộ thỏa mãn một điều kiện. σ city='London' (Customers) trả về chỉ các khách hàng London.
π (Chiếu) — chọn các cột cụ thể. π name, city (Customers) trả về một quan hệ chỉ gồm các cặp (name, city).
× (Tích Descartes) — ghép mỗi bộ trong một quan hệ với mỗi bộ trong quan hệ khác.
⋈ (Join) — phép toán mà bài báo của Codd gọi là “join tự nhiên”: kết hợp các bộ từ hai quan hệ chia sẻ giá trị thuộc tính.
∪, ∩, − (Hợp, giao, hiệu) — các phép toán tập chuẩn.
÷ (Chia) — cho các truy vấn “tất cả X sao cho với mọi Y…”. Cái này hiếm khi tồn tại đến SQL mà không có mánh khóe.

Bài báo chứng minh rằng chỉ với các nguyên thủy này, bạn có thể diễn đạt bất kỳ truy vấn logic bậc nhất nào trên dữ liệu. Đó là cơ sở toán học cho cái chúng ta giờ gọi là “đầy đủ quan hệ” — một ngôn ngữ truy vấn diễn đạt mọi thứ đại số quan hệ có thể.

SQL, khi nó ra mắt, được thiết kế để đầy đủ quan hệ. Cú pháp của nó khác với ký hiệu của Codd — SELECT name FROM customers WHERE city = 'London' thay vì π name (σ city='London' (Customers)) — nhưng sức mạnh diễn đạt được cho là tương đương.

Được cho là. Trong thực tế, những sai lệch của SQL so với đại số quan hệ thuần túy (túi, NULL, ép kiểu ngầm) có nghĩa là một số truy vấn có thể diễn đạt được ở một bên mà không phải bên kia. Codd phàn nàn về điều này. Hầu hết người thực hành không quan tâm.

#Khóa ngoại và tính toàn vẹn tham chiếu

Bài báo giới thiệu ý tưởng về khóa ngoại — các thuộc tính trong một quan hệ mà giá trị phải khớp với giá trị khóa chính trong một quan hệ khác. Đây là cơ chế mà các mối quan hệ giữa các thực thể được biểu diễn mà không cần con trỏ vật lý.

Tính chất quan trọng là tính toàn vẹn tham chiếu: nếu một bộ orders có customer_id = 101, phải thực sự có một bộ customers với id = 101. Xóa khách hàng nên hoặc lan (xóa các đơn hàng) hoặc bị ngăn (việc xóa thất bại).

Cơ sở dữ liệu phân cấp có tính toàn vẹn tham chiếu theo cấu trúc — một bản ghi con đơn giản không thể tồn tại mà không có cha. Cơ sở dữ liệu quan hệ phải thực thi nó rõ ràng. Bài báo năm 1970 của Codd giới thiệu khái niệm nhưng để việc thực thi phần lớn không được đề cập. Công việc đó sẽ không xuất hiện trong SQL cho đến khi ràng buộc FOREIGN KEY được thêm vào tiêu chuẩn SQL-89 năm 1989.

#Dạng chuẩn (ngầm)

Bài báo năm 1970 không dùng thuật ngữ “dạng chuẩn” — điều đó đến trong bài báo tiếp nối 1971-72 của Codd. Nhưng bài báo năm 1970 đặt ra vấn đề mà dạng chuẩn giải quyết. Nó định nghĩa khóa (thuộc tính xác định duy nhất các bộ) và phụ thuộc hàm (thuộc tính A xác định thuộc tính B nếu biết A thì biết B). Nó ghi nhận nguy cơ “dị thường” khi các thuộc tính được lưu trữ dư thừa.

Đến năm 1972, Codd đã hình thức hóa Dạng Chuẩn Thứ Nhất, Thứ Hai, và Thứ Ba, và đến năm 1974 ông và Boyce đã định nghĩa Dạng Chuẩn Boyce-Codd để xử lý các trường hợp 3NF bỏ sót. Bài viết về dạng chuẩn đi qua các dạng này chi tiết. Bài báo năm 1970 là nơi hạt giống được gieo.

#Những gì bài báo không có

Một vài thứ cảm thấy không thể thiếu trong cơ sở dữ liệu quan hệ hôm nay không có trong bài báo năm 1970:

SQL. Bài báo dùng ký hiệu đại số quan hệ xuyên suốt. SQL — khi đó gọi là SEQUEL — sẽ được Chamberlin và Boyce tại IBM thiết kế bắt đầu từ năm 1974, rõ ràng để làm cho toán học của Codd có thể sử dụng được bởi lập trình viên.
Index. Bài báo không mô tả cấu trúc index hay lưu trữ vật lý. Đó là điểm mấu chốt — bài báo lập luận rằng các chi tiết đó nên vô hình với người dùng. Công việc thực tế về index (B-tree, hash index) được thực hiện riêng.
Giao dịch và ACID. Đồng thời và khôi phục lỗi được xử lý trong các công trình tiếp theo, đặc biệt là hình thức hóa ACID của Härder và Reuter năm 1983.
NULL của SQL. Codd, nổi tiếng, có cảm xúc hai chiều về NULL. Ông lập luận cho một logic ba giá trị (đúng, sai, chưa biết) nhưng cũng nghĩ NULL bị lạm dụng trong thực tế. Sau này ông đề xuất nhiều loại NULL (giá trị chưa biết vs. giá trị không áp dụng), mà các triển khai SQL không chấp nhận và ông không hoàn toàn từ bỏ.

#Những gì không tồn tại

Một vài phần của bài báo bị bỏ lại:

“Join tự nhiên” làm mặc định. Bài báo của Codd coi join chủ yếu là join tự nhiên — tự động join trên các thuộc tính cùng tên. SQL làm điều này trở thành opt-in (qua NATURAL JOIN), và hầu hết người thực hành dùng mệnh đề JOIN ... ON rõ ràng thay vì, vì dựa vào quy ước đặt tên qua các bảng là mong manh.
Chia. Phép toán ÷ (chia quan hệ) mạnh nhưng cồng kềnh. SQL không có tương đương trực tiếp; diễn đạt “tìm nhà cung cấp cung cấp tất cả các linh kiện” yêu cầu truy vấn con NOT EXISTS lồng nhau hoặc các giải pháp tương tự.
Ngữ nghĩa tập thuần túy. Như đã bàn, SQL dùng ngữ nghĩa túi.
Cách tiếp cận cụ thể của Codd với NULL. Các đề xuất của ông cho xử lý NULL đa giá trị chưa bao giờ vào SQL.
Các phép “Cập nhật” bài báo đề xuất. Bài báo có một số thảo luận vụng về về cách xử lý xóa khi có khóa ngoại mà sau đó đã được làm lại hoàn toàn.

#Sự thất vọng của chính Codd

Bài viết về Mô hình Quan hệ đề cập rằng IBM “ngồi trên” mô hình quan hệ trong nhiều năm. Bản thân Codd đã thất vọng trong suốt những năm 1970 và 1980 rằng IBM đã xuất xưởng sản phẩm (SQL/DS, rồi DB2) mà ông coi là quan hệ không đầy đủ.

Năm 1985, ông xuất bản “12 quy tắc của Codd” (thực ra là 13, đánh số từ 0 đến 12) như một danh sách kiểm tra rõ ràng về những gì một cơ sở dữ liệu quan hệ nên làm. Các quy tắc cố tình nghiêm ngặt — không cơ sở dữ liệu thương mại nào đáp ứng đầy đủ tất cả. DB2 của IBM, Oracle, và mọi nhà cung cấp khác đều trượt ở nhiều điểm.

12 quy tắc của Codd một phần là một chiến thuật tiếp thị chống lại các nhà cung cấp tuyên bố “quan hệ” trong khi xuất xưởng sản phẩm gắn các truy vấn quan hệ vào các nội bộ cơ bản là phi-quan hệ. Ông dành phần lớn cuối những năm 1980 đi nói chuyện chấm điểm các sản phẩm thương mại theo quy tắc của ông. Các nhà cung cấp ghét điều đó.

Bản thân các quy tắc là một bài kiểm tra độ thuần túy hữu ích. Nhưng chúng cũng tiết lộ khoảng cách giữa sự thanh lịch lý thuyết và kỹ thuật thực tiễn — xây dựng một cơ sở dữ liệu thỏa mãn chặt chẽ các quy tắc của Codd không nhất thiết là cơ sở dữ liệu tốt nhất, chỉ là cơ sở dữ liệu nhất quán về mặt toán học nhất. Ngành công nghiệp chủ yếu lựa chọn các hệ thống “gần-quan hệ” làm các đánh đổi thực dụng mà Codd sẽ không tán thành.

#Tại sao bài báo vẫn đứng vững

Hầu hết các bài báo khoa học máy tính thời 1970 chỉ còn ý nghĩa lịch sử. Bài của Codd vẫn là cơ sở hạ tầng chịu tải. Mọi truy vấn SQL bạn từng viết đều chạy qua một trình tối ưu truy vấn đang áp dụng các khái niệm từ bài báo đó. Khóa ngoại, join, độc lập dữ liệu — tất cả đều truy nguyên trực tiếp về mười hai trang đó.

Lý do nó đứng vững:

Nó không đặc thù cho triển khai. Codd mô tả một mô hình toán học, không phải một cấu trúc dữ liệu. Điều đó có nghĩa là các ý tưởng sống sót qua các thay đổi thế hệ về phần cứng, lưu trữ, và kiến trúc phần mềm.
Nó tạo ra sự tách biệt mối quan tâm đúng. Logic vs. vật lý, khai báo vs. thủ tục. Mọi hệ thống cơ sở dữ liệu sau đó đều áp dụng sự tách biệt đó, vì phương án khác là xây dựng lại những lỗi ghép cặp mà CODASYL đã mắc phải.
Nó chứng minh được là đầy đủ. Đại số quan hệ đã được biết là diễn đạt chính xác logic bậc nhất trên dữ liệu có cấu trúc. Điều đó có nghĩa là ngôn ngữ truy vấn sẽ không hết sức mạnh diễn đạt theo cách bất ngờ — điều mà các ngôn ngữ truy vấn phân cấp sớm đôi khi làm.

Bài viết về Mô hình Quan hệ tóm tắt bài báo là “đơn giản một cách lừa dối”. Chữ “lừa dối” đang gánh rất nhiều sức nặng. Dưới bề mặt là lý thuyết tập hợp, logic bậc nhất, lý thuyết phụ thuộc hàm, và một lập luận chính xác về cơ sở dữ liệu là gì — lập luận cẩn thận đủ để năm mươi sáu năm kỹ thuật thực tiễn chủ yếu đã đang điền vào các chi tiết, không phải xem lại kế hoạch.