Mở đầu

Chúng ta bắt đầu bằng việc làm rõ một vài điểm quan trọng trong các truy vấn quan hệ. Đầu vào và đầu ra của truy vấn đều là các quan hệ. Kết quả của truy vấn phụ thuộc vào các minh hoạ dữ liệu của mỗi quan hệ đầu vào. Trong phần 3.4, chúng ta sử dụng tên các trường để tham chiếu tới các trường bởi vì chú thích này làm cho các truy vấn dễ đọc hơn. Cách lựa chọn khác là ta dùng thứ tự các trường để tham chiếu tới quan hệ thay vì việc sử dụng tên trường.

Trong định nghĩa đại số và các phép toán logic quan hệ, lựa chọn tham chiếu tới các trường bằng vị trí thông dụng hơn bằng tên của trường: Các truy vấn thường dựa trên những tính toán của các kết quả trung gian, và nếu chúng ta sử dụng tên các trường để tham chiếu tới các trường, định nghĩa cấu trúc truy vấn phải xác định trên tên các trường của các kết quả trung gian này. Điều này có thể làm dài dòng và vì thế chúng ta lựa chọn cách tham chiếu thứ hai. Tuy nhiên, cách tham chiếu thứ nhất làm cho truy vấn dễ đọc hơn.

Từ những cân nhắc trên, chúng ta sử dụng cách tham chiếu theo vị trí để định nghĩa đại số quan hệ và các phép toán logic quan hệ. Chúng ta cũng giới thiệu một quy tắc đơn giản là cho phép các quan hệ trung gian được 'thừa hưởng' tên các trường.

Chúng ta biểu diễn một số ví dụ truy vấn sử dụng những lược đồ sau:

Sailors(sid: integer, sname: string, rating: integer, age: real) Boats(bid: integer, bname: string, color: string) Reserves(sid: integer, bid: integer, day: date)

Những trường khoá được gạch chân, và miền xác định của mỗi trường được liệt kê sau tên trường. Trong ví dụ trên, sid là khoá của Sailors, bid là trường khoá của Boats, và tất cả các trường cùng nhau làm khóa của Reservers. Những trường trong minh hoạ của một trong các quan hệ trên sẽ được tham chiếu bằng tên, hoặc vị trí dựa trên thứ tự của chúng được liệt kê.

Trong một vài ví dụ minh hoạ các toán tử đại số quan hệ, chúng ta sẽ sử dụng minh hoạ dữ liệu S1 và S2 (của Sailors) và R1(của Reservers) trong Hình 1, 2, và 3.

Đại số quan hệ

Đại số quan hệ là một trong hai dạng ngôn ngữ truy vấn hỗ trợ trong mô hình quan hệ. Những truy vấn trong đại số được soạn thảo sử dụng tập các toán tử. Một đặc tính cơ bản là tất cả các toán tử trong đại số quan hệ nhật một hoặc hai minh hoạ quan hệ như là tham biến và trả lại kết quả là một minh hoạ quan hệ. Đặc tính này làm nó dễ soạn thảo các toán tử để xây dựng các truy vấn phức tạp - biểu thức đại số quan hệ được định nghĩa đệ quy trong một quan hệ, một toán tử đại số đơn được áp dụng cho một biểu thức đơn, một toán tử đại số nhị phân được áp dụng cho hai biểu thức. Chúng ta biểu diễn những toán tử cơ bản của đại số quan hệ (chọn, chiếu, hợp, nhân chéo, trừ), cũng như một số các toán tử khác có thể được định nghĩa dựa trên các toán tử cơ bản trên.

Mỗi truy vấn quan hệ biểu diễn một thủ tục theo từng bước để tính toán ra kết quả mong đợi, dựa trên thứ tự các toán tử được áp dụng trong truy vấn. Biểu diễn tự nhiên của đại số quan hệ cho phép chúng ta nghĩ một biểu thức đại số như một cách thức thực hiện, hay một kế hoạch để đánh giá truy vấn, và hệ thống quan hệ trên thực tế sử dụng những biểu thức đại số để biểu diễn những kế hoạch đánh giá truy vấn.

• Phép chọn và phép chiếu

Đại số quan hệ bao gồm các toán tử để lựa chọn các dòng trong quan hệ (σ) và các cột (π). Những toán tử này cho phép chúng ta thực thi dữ liệu trên các quan hệ đơn. Xem xét minh họa của quan hệ Sailors (S2) chỉ ra trong Hình 2. Chúng ta có thể truy cập đến các dòng ứng với các thủy thủ lão luyện bằng cách sử dụng phép toán σ. Biểu diễn

σ _rating>8(S2)

kết quả chỉ ra trong Hình 4. Chỉ số dưới rating>8 chỉ ra điều kiện lựa chọn để lọc ra các bộ giá trị.

Toán tử chọn σ chỉ ra những bộ giá trị còn lại thông qua điều kiện chọn. Nói chung, điều kiện chọn là một tổ hợp logic (ví dụ, biểu thức sử dụng các kết nối logic ∧, và ∨) của các thành phần, có dạng thuộc tínhophằng số hoặc thuộc tính 1 opthuộc tính 2, trong đó op là một trong số những toán tử so sánh <, <=, =, ≠, >=, hoặc >. Tham chiếu tới một thuộc tính có thể bằng vị trí (theo dạng .i hoặc i) hoặc theo tên (theo dạng .name hoặc name). Lược đồ kết quả của phép chọn là lược đồ của minh họa quan hệ đầu vào.

Phép chiếu (π) cho phép trích ra một số các cột từ một quan hệ; ví dụ, chúng ta có thể đưa ra sname và rating của tất cả các thủy thủ sử dụng toán tử π. Biểu diễn

π_sname,rating(S2)

cho kết quả trong Hình 5. Chỉ số dưới sname, rating chỉ ra những trường cần đưa ra. Lược đồ kết quả của phép chiếu được xác định bằng những trường được đưa ra trong phép chiếu. Giả sử rằng chúng ta chỉ muốn đưa ra age của các thủy thủ. Biểu diễn

π_age(S2)

cho kết quả trong Hình 6. Một điểm quan trọng cần ghi nhớ là, mặc dù ba thủy thủ có tuổi bằng 35, nhưng chỉ có một bộ giá trị có age=35 xuất hiện trong kết quả của phép chiếu, vì những bộ giá trị trùng nhau đã bị loại đi.

Vì kết quả của một biểu thức đại số quan hệ luôn là một quan hệ, chúng ta có thể thay quan hệ bằng một biểu thức. Ví dụ, chúng ta có thể đưa ra name và rating của các thủy thủ lão luyện bằng việc kết hợp hai truy vấn phía trên. Biểu diễn

π_sname,rating(σ _rating>8(S2))

cho kết quả trong Hình 7. Kết quả này nhận được bằng việc áp dụng phép chọn trên S2 (để có quan hệ trong Hình 4) và sau đó áp dụng phép chiếu.

• Các phép toán tập hợp

Những phép toán trên tập hợp sau đây được hỗ trợ trong đại số quan hệ: phép hợp, phép giao, phép trừ (－), phép nhân chéo (×).

Phép hợp: R U S trả về một minh họa quan hệ chứa tất cả các bộ giá trị có trong minh họa quan hệ R hoặc trong minh họa quan hệ S (hoặc cả hai). R và S phải là khả hợp, và lược đồ kết quả được định nghĩa giống hệt của R.

Hai quan hệ được gọi là khả hợp nếu nó thỏa mãn các điều kiện sau đây:

• Chúng có cùng số lượng các trường, và
• Những trường tương ứng, theo thứ tự từ trái sang phải, có cùng miền xác định.

Ghi nhớ rằng tên các trường không được sử dụng trong định nghĩa khả hợp. Cho thuận tiện, chúng ta sẽ giả sử rằng các trường của R U S thừa kế tên các trường từ R, nếu các trường của R có tên. (Giả định này là ngầm định trong định nghĩa lược đồ của R U S)

Phép giao: R giao S trả về một minh họa quan hệ chứa tất cả các bộ giá trị xuất hiện trong cả hai quan hệ R và S. Quan hệ R và S phải là khả hợp, và lược đồ kết quả được định nghĩa giống hệt với lược đồ của R.

Phép trừ: R － S trả về một minh họa quan hệ chứa tất cả các bộ giá trị xuất hiện trong R nhưng không xuất hiện trong S. Quan hệ R và S phải là khả hợp, và lược đồ kết quả được định nghĩa giống hệt với lược đồ của R.

Phép nhân chéo: R × S trả về một minh họa quan hệ mà trong lược đồ chứa tất cả các trường của R (theo thứ tự xuất hiện của chúng trong R) và theo sau là tất cả các trường của S (theo tứ tự xuất hiện của chúng trong S). Kết quả của R × S chứa một bộ giá trị <r,s> (sự móc nối của r và s) cho mỗi cặp của các bộ giá trị r ∈ R, s ∈ S. Phép nhân chéo đôi khi được gọi là phép Tích đề các.

Chúng ta sử dụng thỏa thuận rằng các tên của các trường trong R × S được thừa kế từ tên của các trường tương ứng trong R và S. Có thể trong R và S có những trường có tên trùng nhau; tình trạng này tạo ra sự tranh chấp tên. Những trường tương ứng trong R × S sẽ không có tên và chúng được tham chiếu chỉ thông qua vị trí của trường.

Trong những định nghĩa trước, ghi nhớ rằng mỗi toán tử có thể được áp dụng tới các minh họa quan hệ được tính toán từ các biểu thức đại số quan hệ.

Bây giờ chúng ta sẽ minh họa các định nghĩa này thông qua một vài ví dụ. Phép hợp của S1 và S2 chỉ ra kết quả trong Hình 8. Những trường được liệt kê theo thứ tự; tên của các trường được kế thừa từ S1. S2 có cùng tên các trường, tất nhiên, vì nó cũng là một minh họa của quan hệ Sailors. Nói chung, tên của các trường trong S2 có thể khác, vì chúng ta chỉ yêu cầu sự tương đương về miền giá trị (tên trường có thể khác nhau). Ghi nhớ rằng kết quả là một tập các bộ giá trị. Bộ giá trị xuất hiện trong cả S1 và S2 chỉ xuất hiện một lần trong S1 U S2.

S1 U R1 không phải là phép toán đúng vì hai quan hệ này không khả hợp. Phép giao của S1 và S2 chỉ ra trong Hình 9, và phép trừ chỉ ra trong Hình 10.

Kết quả của phép nhân chéo S1 × R1 được chỉ ra trong Hình 11. Bởi vì R1 và S1 cùng có trường có tên là sid, do thỏa thuận của chúng ta về tên các trường, hai trường tương ứng trong S1 × R1 không được đặt tên, và tham chiếu tới chúng chỉ thông qua vị trí xuất hiện trong Hình 11. Các trường của S1 × R1 có cùng miền với các trường tương ứng trong R1 và S1. Trong Hình 11, sid được liệt kê trong ngoặc để nhấn mạnh rằng nó không được thừa kế tên trường, chỉ miền tương ứng là được thừa kế.

• Đổi tên

Chúng ta đã cẩn thận để chọn các thỏa thuận đặt tên cho trường, kết quả của một biểu thức đại số quan hệ thừa kế các tên từ các minh họa quan hệ. Tuy nhiên, xung đột tên có thể xảy ra trong một vài trường hợp; ví dụ S1 × S2. Vì thế, sẽ thuận lợi hơn nếu có thể được đặt tên rõ ràng cho các trường trong các biểu thức đại số quan hệ.

Chúng ta giới thiệu một toán tử đổi tên ρ cho mục đích này. Biểu diễn ρ(R( $\overline{F}$), E) lấy một biểu thức đại số quan hệ bất kỳ E và trả về một minh họa của quan hệ (mới) gọi là R. R chứa những bộ giá trị như trong E, và có cùng lược đồ với E, nhưng một số trường đã được đổi tên. Tên các trường trong quan hệ R cũng giống như trong E, trừ những trường được đổi tên nằm trong danh sách đổi tên$\overline{F}$, liệt kê theo dạng tên cũ!tên mới hoặc vị trí!tên mới. Với những ρ được định nghĩa tốt, tham chiếu tới các trường (theo dạng trên) không mập mờ, và không có hai trường trong kết quả có cùng tên. Đôi khi chúng ta muốn chỉ đổi tên các trường hoặc tên các quan hệ; chúng ta sẽ coi cả R và $\overline{F}$là không bắt buộc trong sử dụng của ρ. (Tất nhiên, nó sẽ vô nghĩa nếu bỏ cả hai).

Ví dụ, biểu diễn ρ(C(1 → sid1, 5 → sid2), S1 × S2) trả về một quan hệ chứa những bộ giá trị trong Hình 11 và có lược đồ sau: C(sid1: integer, sname: string, rating: integer, age: real, sid2: integer, bid: integer, day: dates).

Có thể có một số toán tử bổ sung trong đại số, nhưng tất cả chúng có thể được định nghĩa dưới dạng các toán tử ở phần sau. (Thực tế, toán tử đổi tên chỉ dùng để tạo sự thuận lợi về cú pháp,và thậm chí toán tử giao là dư thừa; R giao S có thể được định nghĩa bằng R － (R － S). Chúng ta xem xét những toán tử bổ sung này, và định nghĩa của chúng dựa trên các toán tử cơ bản trong những phần sau.

• Kết nối

Phép toán kết nối là một trong những phép toán hữu dụng nhất trong đại số quan hệ và nó là cách thông thường nhất để kết nối thông tin từ hai hoặc nhiều quan hệ. Mặc dù một kết nối có thể được định nghĩa như một phép nhân chéo, tiếp sau là phép chọn và phép chiếu. Trong thực tế, kết nối xuất hiện thường xuyên hơn phép nhân chéo đơn giản. Thêm nữa, kết quả của phép nhân chéo lớn hơn nhiều so với phép nối. Vì lý do này, phép nối đã nhận được rất nhiều sự chú ý, và có một loạt các biến thể của phép nối.

Điều kiện nối

Phiên bản chung nhất của phép nối chấp nhận a điều kiện nối c và cặp của minh họa quan hệ được xem như đối số, và kết quả trả về là một minh họa quan hệ. Dạng của điều kiện nối giống như điều kiện chọn. Phép nối được định nghĩa như sau:

Vì thế, phép được định nghĩa như một phép nhân chéo, theo sau là phép chọn. Ghi nhớ rằng điều kiện c có thể tham chiếu tới các thuộc tính của cả R và S. Sự tham chiếu tới một thuộc tính của quan hệ, giả sử R, có thể bằng vị trí (theo dạng R.i) hoặc bằng tên (theo dạng R.name).

Như ví dụ, kết quả của S1 _{S1.sid<R1.sid}R1 được chỉ ra trong Hình 12. Vì sid xuất hiện trong cả S1 và R1, những trường tương ứng trong kết quả của phép nhân chéo S1 × R1 (và do đó cũng trong kết quả của S1 _{S1.sid<R1.sid}R1) sẽ không được đặt tên. Miền xác định được thừa kế từ những trường tương ứng của S1 và R1.

Nối bằng

Trường hợp thường gặp của phép nối R S là khi điều kiện nối chứa chỉ các đẳng thức (liên quan tới ∧) theo dạng R.name1 =S.name2, đó là đẳng thức giữa hai trường trong R và S. Trong trường hợp này, rõ ràng có một số sự dư thừa trong những thuộc tính còn lại của kết quả. Nếu điều kiện nối chỉ chứa các đẳng thức, phép nối được tinh lọc bằng việc thêm các phép chiếu để S.name2 bị xóa bỏ. Phép nối với sự tinh lọc này được gọi là phép nối bằng.

Lược đồ kết quả của phép nối bằng chứa những trường của R (với tên và miền xác định tương đương trong R), theo sau là các trường của S mà các trường này không xuất hiện trong điều kiện nối. Nếu tập các trường trong quan hệ kết quả có hai trường được thừa kế từ R và S có cùng tên, chúng sẽ không được đặt tên trong quan hệ kết quả.

Chúng ta minh họa kết quả S1 _R.sid=S.sid R1 trong Hình 13. Ghi nhớ rằng chỉ có một trường sid xuất hiện trong kết quả.

Nối tự nhiên

Trường hợp đặc biệt khác của phép nối R S là nối bằng trong đó các đẳng thức được xác định trên tất cả các trường có cùng tên trong R và S. Trong trường hợp này, để đơn giản chúng ta có thể lờ đi điều kiện nối; mặc định điều kiện nối là tập các đẳng thức trên tất cả các trường chung. Chúng ta có thể gọi trường hợp đặc biệt này là nối tự nhiên, và nó được đảm bảo sẽ không có hai trường có cùng tên. Biểu diễn nối bằng S1 _R.sid=S.sid R1 là một trường hợp của nối tự nhiên và có thể được ghi đơn giản là S1 R1, vì chỉ có trường chung là sid. Nếu hai quan hệ không có các thuộc tính chung, S1 R1 đơn giản chỉ là phép nhân chéo.

• Phép chia

Phép chia hữu ích để biểu diễn một số kiểu truy vấn, ví dụ: "Tìm tên của các thủy thủ đã phục vụ trên tất cả chuyến tàu". Việc hiểu được làm thế nào để sử dụng các toán tử cơ bản của đại số quan hệ cho định nghĩa phép chia là một bài tập hữu ích. Tuy nhiên, phép chia không quan trọng như là các phép toán khác- nó không cần thường xuyên, và các hệ thống cơ sở dữ liệu không cố gắng để khai thác ngữ nghĩa của phép chia bằng cách thực hiện nó như là một toán tử riêng biệt (ví dụ, nó được thực hiện cùng với phép nối).

Chúng ta sẽ bàn tới phép chia thông qua một ví dụ. Xem xét hai minh họa quan hệ A và B trong đó A có chính xác hai trường x và y, và B chỉ có một trường y, có miền như trong A. Chúng ta định nghĩa phép chia A/B như sau: Với mỗi giá trị x trong (cột đầu tiên của) A, giả sử tập của giá trị y xuất hiện trong (trường thứ hai của) các bộ giá trị của A cùng với giá trị của x. Nếu tập giá trị này chứa (tất cả giá trị y trong) B, giá trị x là kết quả của A/B.

Sự tương đương với phép chia số nguyên có lẽ giúp chúng ta hiểu được phép chia. Với hai số nguyên A và B, A/B tạo ra số nguyên lớn nhất Q, với Q*B ≤ A. Với các minh họa quan hệ A và B, A/B là minh họa quan hệ lớn nhất để Q × B ⊆ A.

Phép chia minh họa trong Hình 14. A là một quan hệ liệt kê các sản phẩm (Parts) được cung cấp bởi các nhà cung cấp (Suppliers), và B là quan hệ liệt kê tất cả các sản phẩm (Parts). Kết quả của A/Bi là tất cả các nhà cung cấp, người mà cung cấp tất cả các sản phẩm được liệt kê trong Bi.

Biểu diễn A/B dựa trên những toán tử đại số quan hệ là một bài tập thú vị, và người đọc nên cố gắng để làm trước khi đọc tiếp. Ý tưởng cơ bản là để tính ra được tất cả giá trị x trong A không bị loại ra (disqualified). Giá trị x bị loại ra nếu khi gán giá trị y cho B, chúng ta có một bộ giá trị <x,y> không nằm trong A. Chúng ta có thể tính được các bộ giá trị bị loại sử dụng biểu diễn đại số sau:

π _x((π(A) × B) － A)

Vì thế, chúng ta có thể định nghĩa A/B như sau:

π_x(A) － π _x((π(A) × B) － A)

Để hiểu được phép chia trong dạng tổng quát, chúng ta phải xem xét trường hợp khi cả x và y được thay thế bằng một tập các thuộc tính. Sự tổng quát không quá khó hiểu và nó là một bài tập cho người đọc. Chúng ta sẽ bàn tới những ví dụ khác minh họa phép chia trong phần sau (Truy vấn Q9 và Q10)

• Những ví dụ khác của Truy vấn đại số quan hệ

Bây giờ chúng tôi trình bày một số ví dụ để minh họa việc viết các truy vấn trong đại số quan hệ. Chúng ta sử dụng các lược đồ Sailors, Reserves và Boats cho những ví dụ trong phần này. Chúng ta sẽ sử dụng những dấu ngoặc đơn cần thiết để những biểu thức đại số được rõ ràng. Ghi nhớ rằng tất cả các truy vấn ví dụ trong chương này được đánh số thứ tự. Những mã số này được sử dụng trong cả chương này và chương về truy vấn SQL (Chương 5). Sự đánh số thứ tự làm cho ta dễ dàng xác định truy vấn khi đọc lại trong ngữ cảnh của các phép toán quan hệ và trong SQL và cũng để so sánh các cách khác nhau để viết một truy vấn. (Tất cả tham chiếu tới một truy vấn có thể được tìm thấy trong phần chỉ số chủ đề của cuốn sách)

Trong chương này (và chương 5), chúng ta sẽ biểu diễn truy vấn sử dụng minh họa dữ liệu S3 của Sailors, R2 của Reserves và B1 của Boats, chỉ ra trong Hình 15, 16 và 17.

(Q1) Tìm tên của các thủy thủ đã đặt chỗ trên chuyến tàu 103.

Truy vấn này có thể được viết như sau:

π_sname((σ_bid=103Reserves) Sailors)

Đầu tiên, chúng ta lấy ra bộ giá trị trong Reserves thỏa mãn bid =103 và sau đó kết nối tự nhiên bộ giá trị này với Sailors. Biểu thức này có thể được đánh giá trên minh hoạ của Reserves và Sailors. Kết quả dựa trên minh hoạ R2 và S3, kết quả là một quan hệ chỉ có một trường, gọi là sname, và ba bộ giá trị <Dustini>, <Horatioi> và <Lubberi>.(Quan sát thấy rằng có hai thuỷ thủ có cùng tên Horatio, và chỉ có một trong số họ đã phục vụ trên chuyến 103).

Chúng ta có thể chia truy vấn này thành các phần nhỏ sử dụng toán tử đổi tên:

ρ(Temp1, σ _bid=103 Reserves)

ρ(Temp2, Temp1 Sailors)

π_sname(Temp2)

Ghi nhớ rằng bởi vì chúng ta chỉ sử dụng ρ để cung cấp tên cho quan hệ trung gian, đổi tên không bắt buộc và có thể bỏ qua. Temp1 chỉ ra một quan hệ trung gian để xác định các Reservations của chuyến 103. Temp2 là một quan hệ trung gian khác, và nó chỉ ra các thuỷ thuỷ đã làm một Reservation trên tập Temp1. Minh hoạ của các quan hệ khi đánh giá truy vấn này trên các minh hoạ R2 và S3 được chỉ ra trong Hình 18 và 19. Cuối cùng, chúng ta trích ra cột sname từ Temp2.

Phiên bản của truy vấn sử dụng ρ cơ bản giống như truy vấn nguyên bản; sủ dụng ρ như kiểu cú pháp. Tuy nhiên, có một số cách khác nhau để viết truy vấn trong đại số quan hệ. Đây là một cách viết khác:

πsname(σbid=103(Reserves Sailors))

Trong phiên bản này, đầu tiên chúng ta thực hiện phép nối tự nhiên của Reserves và Sailors, sau đó áp dụng phép chọn và phép chiếu.

Ví dụ đưa ra cách nhìn sơ qua về vai trò của đại số trong quan hệ DBMS. Các truy vấn được viết bởi người sử dụng bằng ngôn ngữ như là SQL. DBMS thực hiện biên dịch một truy vấn thành đại số quan hệ, và sau đó tìm những cách biểu diễn đại số khác để có thể thực hiện truy vấn hiệu quả hơn. Nếu truy vấn của người sử dụng đầu tiên được biểu diễn như sau:

πsname(σbid=103(Reserves Sailors))

một bộ tối ưu hoá truy vấn tốt sẽ tìm ra một cách biểu diễn khác như sau

πsname((σbid=103Reserves) Sailors)

Thêm nữa, bộ tối ưu hoá sẽ nhận ra rằng cách biểu diễn thứ hai hiệu quả hơn cách biểu diễn thứ nhất vì kích thước của những quan hệ trung gian nhỏ hơn vì đã sử dụng phép chọn trước.

πsname((σcolor='red'Boats) Reserves Sailors)

Truy vấn này bao gồm một loạt các phép nối đôi. Đầu tiên, chúng ta chọn được những bộ giá trị trên Boats có màu 'red'. Sau đó chúng ta liên kết tập giá trị này với Reserves (kết nối tự nhiên, cùng đẳng thức được xác định trên cột sid) để truy cập đến tên của các thuỷ thủ đã đặt chỗ trên tàu có màu 'red'. Cuối cùng, chúng ta thực hiện phép chiếu để lấy ra tên (name) các thuỷ thủ. Khi thực hiện trên minh hoạ B1, R2 và S3, kết quả của truy vấn trên lấy được ba tên: Dustin, Horatio, và Lubber.

Biểu diễn tương đương là:

πsname(πsid((πbid σcolor='red'Boats) Reserves) Sailors)

Người đọc được yêu cầu viết lại những truy vấn này sử dụng ρ để làm những quan hệ trung gian rõ ràng và để so sánh các lược đồ của các quan hệ trung gian. Cách viết thứ hai đưa ra những quan hệ trung gian với ít trường hơn (và vì thế kết quả của các minh hoạ quan hệ trung gian có ít bộ giá trị hơn). Tối ưu hoá truy vấn quan hệ sẽ cố gắng đạt đến cách biểu diễn thứ hai nếu đầu tiên nó được cung cấp như cách biểu diễn thứ nhất.

(Q3) Tìm màu của các tàu được Lubber phục vụ.

πcolor((σsname='Lubber ' Sailors) Reserves Boats)

Truy vấn này rất giống truy vấn chúng ta đã sử dụng để đưa ra các thuỷ thủ đã phục vụ trên tàu màu 'red'. Trên minh hoạ quan hệ B1, R2 và S3, truy vấn này sẽ trả về các màu là 'green' và 'red'.

(Q4) Tìm tên của các thuỷ thủ đã phục vụ trên ít nhất một tàu.

π sname(Sailors Reserves)

Kết nối của Sailors và Reserves tạo ra các quan hệ trung gian trong đó các bộ giá trị chứa một bộ giá trị của Sailors 'kết nối với' một bộ giá trị Reserves. Một bộ giá trị của Sailors xuất hiện trong (một vài bộ giá trị của) quan hệ trung gian chỉ khi có ít nhất một bộ giá trị Reserves có cùng giá trị sid. Khi đánh giá dựa trên minh hoạ B1, R2 và S3, kết quả chứa ba bộ giá trị <Dustinini>, <Horatio>, và <Lubber>. Ngay cả khi có hai thuỷ thủ có cùng tên <Horatio> đã từng phục vụ trên một tàu, kết quả cũng chỉ chứa duy nhất một bộ giá trị <Horatio>, bởi vì kết quả là một quan hệ nên không có bất kỳ sự trùng nhau nào.

Ở thời điểm này, ta đã thấy được sự thường xuyên xuất hiện của phép kết nối tự nhiên trong các ví dụ của chúng ta. Sự thường xuyên này không chỉ là ngẫu nhiên trên những ví dụ truy vấn này, mà kết nối tự nhiên là phép toán được sử dụng rất rộng rãi. Đặc biệt, kết nối tự nhiên được sử dụng thường xuyên khi kết nối hai quan hệ dựa trên trường khoá ngoại. Trong truy vấn Q4, nối bằng giữa quan hệ Sailors và Reserves dựa trên trường sid, trong đó sid là khoá ngoại của Reserves tham chiếu tới trường sid của Sailors.

(Q5) Tìm tên của các thuỷ thủ đã phục vụ trên tàu màu 'red' hoặc màu 'green'

ρ(Tempboats, (σcolor='red'Boats) U (σcolor='green'Boats))

πsname(Tempboats Reserves Sailors)

Chúng ta xác định tập tất cả các tàu hoặc có màu 'red', hoặc có màu 'green' (Tempboats chứa những tàu có bid là 102, 103 và 104 trong các minh hoạ quan hệ B1, R2 và S3). Sau đó chúng nối với quan hệ Reserves để xác định sid của những thuỷ thủ đã phục vụ trên một trong những tàu đó; điều này cung cấp cho chúng ta sids 22, 31, 64 và 74 ứng với những minh hoạ quan hệ nói trên. Cuối cùng, chúng ta nối (một quan hệ trung gian chứa tập các sid này) với Sailors để tìm ra tên của các thuỷ thủ tương ứng với các sid này. Kết quả nhận được là các tên Dustin, Horatio, và Lubber ứng với các minh hoạ quan hệ B1, R2 và S3.

Một định nghĩa tương đương khác như sau:

ρ(Tempboats, (σcolor= 'red' ∨ color='green'Boats))

πsname(Tempboats Reserves Sailors)

Bây giờ hãy cùng chúng tôi xem xét một truy vấn rất giống truy vấn này:

(Q6) Tìm tên các thuỷ thủ đã phục vụ trên tàu màu 'red' và tàu màu 'green'. Cố gắng để làm truy vấn này đơn giản bằng việc thay thế hợp bằng giao trong định nghĩa của Tempboats:

ρ (Tempboats2, (σ color='red'Boats) giao (σ color='green'Boats))

π sname(Tempboats2 Reserves Sailors)

Tuy nhiên, giải pháp này là không đúng - nó đã thay vì cố gắng đưa ra những thuỷ thủ đã phục vụ trên tàu có cả màu 'red' và 'green'. (Vì bid là khoá của Boats, một tàu chỉ có thể có một màu; truy vấn này sẽ luôn trả kết quả là một quan hệ rỗng.) Cách thực hiện đúng là tìm ra những thuỷ thuỷ đã phục vụ trên tàu có màu 'red', sau đó là những thuỷ thủ đã phục vụ trên tàu có màu 'green', và sau đó thực hiện phép giao hai tập kết quả này.

ρ (Tempred, π sid((σ color= 'red' Boats) Reserves))

ρ (Tempgreen, π sid((σ color='green'Boats) Reserves))

π sname((Tempred giao Tempgreen) Sailors)

Hai quan hệ tạm (Temp…) này đưa ra sid của các thuỷ thủ, và xác định tập giao để chỉ ra những người đã phục vụ trên cả tàu màu 'red' và tàu màu 'green'. Trên minh hoạ B1, R2 và S3, các sid của thuỷ thủ đã phục vụ trên tàu màu 'red' là 22, 31 và 64. Sid của các thuỷ thủ đã phục vụ trên tàu màu 'green' là 22, 31 và 74. Vì thế, thuỷ thủ có sid là 22 và 31 là những người đã phục vụ trên cả tàu màu 'red' và tàu màu 'green'; tên của họ là Dustin và Lubber.

Công thức thực hiện truy vấn Q6 có thể được sửa dễ dàng để đưa ra được những thuỷ thủ phục vụ trên tàu màu 'red' hoặc tàu màu 'green' (truy vấn Q5); chỉ cần thay thế phép giao bằng hợp.

ρ (Tempred, π sid((σ color= 'red' Boats) Reserves))

ρ (Tempgreen, π sid((σ color='green'Boats) Reserves))

π sname((Tempred U Tempgreen) Sailors)

Đối với các công thức trên của Q6 và Q5, việc sid là khoá của Sailors rất quan trọng. Xem xét một cách thử để trả lời truy vấn Q6 sau:

ρ (Tempred, π sname((σ color= 'red' Boats) Reserves Sailors))

ρ (Tempgreen, π sname((σ color='green'Boats) Reserves Sailors))

Tempred U Tempgreen

Công thức trên là không đúng vì một lý do tinh vi hơn. Hai thuỷ thủ khác nhau có cùng tên, trong ví dụ minh hoạ quan hệ là Horatio, có thể phục vụ trên tàu màu 'red' và tàu màu 'green'. Trong trường hợp này, tên Horatio sẽ (không đúng) có trong kết quả mặc dù không có một ai có tên Horatio đã phục vụ trên tàu màu 'red' và 'green'. Nguyên nhân của lỗi này là sname được sử dụng để xác định thuỷ thủ (trong khu thực hiện phép giao) trong phiên bản này của truy vấn, nhưng sname không phải là khoá.

(Q7) Tìm tên các thuỷ thủ đã phục vụ trên ít nhất hai tàu.

ρ(Reservations, π sid,sname,bid(Sailors Reserves))

ρ(Reservationpairs(1 → sid1, 2 → sname1, 3 → bid1, 4 → sid2, 5 → sname2, 6 → bid2), Reservations × Reservations)

π sname1 σ (sid1=sid2)^(bid1 ≠bid2)Reservationpairs

Đầu tiên, chúng ta đưa ra những bộ giá trị theo dạng <sid, sname,bid>, nơi các thuỷ thủ (sid) đã phục vụ cho tàu (bid); tập các bộ giá trị này nằm trong một quan hệ tạm thời là Reservations. Tiếp theo, chúng ta tìm tất cả các cặp của các bộ giá trị trong Reservations biểu diễn một thuỷ thủ phục vụ trên hai tàu khác nhau. Đây là ý tưởng chính: Để chỉ ra một thuỷ thủ đã phục vụ trên hai tàu, chúng ta phải tìm hai bộ giá trị Reservations mà cùng một thuỷ thủ nhưng ứng với hai tàu phân biệt. Trên minh hoạ B1, R2 và S3, những thuỷ thủ có sid 22, 31 và 64 thoả mãn. Cuối cùng, chúng ta thực hiện phép chiếu lấy ra tên các thuỷ thủ này, đó là Dustin, Horatio, và Lubber.

Ghi nhớ rằng chúng ta sử dụng sid trong Reservations vì đó là trường khoá của Sailors, và chúng ta cần nó để kiểm tra hai bộ giá trị trong Reservations có liên quan đến cùng một thuỷ thủ không. Nhớ lại trong ví dụ trước, chúng ta không thể sử dụng sname thay vì sid trong trường hợp này.

(Q8) Tìm ra những sid của Sailors có tuổi (age) lớn hơn 20 và không phục vụ trên tàu màu 'red'.

π sid(σ age>20Sailors) − π sid((σ color='red'Boats) Reserves Sailors)

Truy vấn này minh hoạ việc sử dụng toán tử trừ. Một lần nữa, chúng ta sử dụng một thực tế rằng sid là khoá của quan hệ Sailors. Đầu tiên, chúng ta tìm ra những thuỷ thủ có age trên 20 (trên minh hoạ B1, R2 và S3, sid thoả mãn là 22, 29, 31, 32, 58, 64, 74, 85, và 95), sau đó loại bỏ những người đã phục vụ trên tàu màu 'red' (sid 22, 31 và 64), kết quả là những sid còn lại (29, 32, 58, 74, và 95). Nếu chúng ta muốn đưa ra tên các thuỷ thủ này, đầu tiên chúng ta phải tìm được các sid (như trên), sau đó nối với Sailors và thực hiện phép chiếu để lấy được sname.

(Q9) Tìm ra tên các thuỷ thủ đã phục vụ trên tất cả các tàu. Việc sử dụng từ 'tất cả' (hoặc 'mọi') là dấu hiệu tốt để lựa chọn phép chia:

ρ(Tempsids, (π sid,bidReserves)/(π bidBoats))

π sname(Tempsids Sailors)

Quan hệ trung gian Tempsids được định nghĩa sử dụng phép chia, và đưa ra tập các sid của thuỷ thủ phục vụ trên tất cả các tàu (trên minh hoạ B1, R2 và S3, chỉ có sid 22 thoả mãn). Ghi nhớ chúng ta định nghĩa hai quan hệ như thế nào để phép chia (/) có thể được áp dụng- quan hệ đầu tiên có lược đồ (sid, bid) và quan hệ thứ hai có lược đồ (bid). Phép chia sau đó trả lại tất cả sid mà có một bộ giá trị <sid, bid> trong quan hệ đầu tiên ứng với mỗi bid trong quan hệ thứ hai. Kết nối Tempsids với Sailors là cần thiết để lấy được tên của các sid tương ứng, với sid là 22 thì tên là Dustin.

(Q10) Tìm tên của các thuỷ thủ phục vụ trên tất cả các tàu có tên là Interlake.

ρ(Tempsids, (π sid,bidReserves)/(πbid(σ bname='Interlake'Boats)))

π sname(Tempsids Sailors)

Chỉ khác với truy vấn trước là bây giờ chúng ta áp dụng một phép chọn trên Boats, để đảm bảo rằng chúng ta đưa ra chỉ những bid có tên là Interlake trong định nghĩa đối số thứ hai của toán tử chia. Trên minh hoạ B1, R2 và S3, Tempsids có hai sid là 22 và 64, và tên thuỷ thủ tương ứng là Dustin và Horatio.

Phép toán logic quan hệ

Phép toán logic quan hệ là một phần khác với đại số quan hệ. Đối lập với đại số, là những thủ tục, phép toán logic là phi thủ tục, cho phép chúng ta biểu diễn tập kết quả không cần tường minh về cách chúng được tính toán thế nào. Phép toán logic quan hệ có ảnh hưởng lớn đến thiết kế ngôn ngữ truy vấn thương mại như SQL và đặc biệt là Truy vấn-bằng-ví dụ (Query-by-Example (QBE)).

Một dạng của phép toán logic mà chúng ta sẽ biểu diễn chi tiết được gọi là các Phép toán logic quan hệ trên bộ (tuple relational calculus - TRC). Các biến trong TRC nắm giữ các bộ giá trị như là các biến. Một dạng khác, gọi là Phép toán logic trên miền (domain relational calculus - DRC), các biến nhận giá trị là các miền giá trị của các trường trên. TRC có nhiều ảnh hưởng tới SQL, trong khi DRC có ảnh hưởng mạnh mẽ tới QBE. Chúng ta sẽ bàn tới DRC trong phần 3.2.

• Phép toán logic trên bộ

Một biến bộ là một biến nắm giữ các bộ giá trị của một lược đồ quan hệ cụ thể. Đó là, tất cả giá trị gán cho một biến bộ có cùng số lượng và kiểu của trường. Một truy vấn TRC có dạng {T | p(T)}, trong đó T là một biến bộ và p(T) là một công thức biểu diễn T; chúng ta sẽ định nghĩa các công thức và các truy vấn một cách nghiêm ngặt. Kết quả của truy vấn này là một tập gồm tất cả các bộ giá trị t mà với T=t thì p(T) đúng. Chúng ta xem xét ví dụ truy vấn sau:

(Q11) Tìm tất cả các thuỷ thủ có Rating>7

{S | S ∈ Sailors ∧ S.rating >7}

Khi truy vấn được thực hiện trên minh hoạ của quan hệ Sailors, biến bộ S được áp dụng lần lượt với mỗi bộ giá trị để kiểm tra điều kiện S.rating>7. Kết quả của truy vấn chứa những bộ giá trị của S thoả mãn điều kiện này. Trên minh hoạ S3 của Sailors, kết quả chứa những bộ giá trị mà sid là 31, 32, 58, 71 và 74.

Cú pháp của truy vấn TRC

Bây giờ chúng ta định nghĩa những khái niệm này một cách chính thức, bắt đầu bằng khái niệm của công thức. Giả sử Rel là tên một quan hệ, R và S là những biến bộ, a là một thuộc tính của R, và b là một thuộc tính của S. Giả sử op biểu diễn một toán tử trong tập {<, >. =, ≤, ≥, ≠}. Một công thức nguyên thuỷ là một trong những công thức sau:

• R ∈ Rel
• R.a op S.b
• R.a op Hằng_số, hoặc Hằng_số op R.a

Một công thức được định nghĩa đệ quy như một trong những dạng sau, trong đó p và q là một công thức, và p(R) là một công thức trong đó có R xuất hiện:

• bất kỳ công thức nguyên tử nào
• p, p ∧q, p ∨q, hoặc p ⇒q
• ∃ R(p(R)), trong đó R một tuple variable
• ∀ R(p(R)), trong đó R một tuple variable

Trong hai mệnh đề cuối cùng ở trên, lượng tử ∃ và ∀ được gọi là 'kết buộc' với biến R. Biến được gọi là 'tự do' nếu trong công thức hoặc công thức con (công thức nằm trong một công thức lớn) không chứa một sự kiện nào chứa các lượng tử 'kết buộc' tới biến đó.

Chúng ta quan sát thấy rằng, tất cả các biến trong công thức TRC đều xuất hiện trong một công thức con nào đó- những công thức nguyên tử, và tất cả các lược đồ quan hệ chỉ ra một miền ứng với mỗi trường; quan sát này đảm bảo rằng mỗi biến trong công thức TRC có kiểu dữ liệu được định nghĩa tốt theo tư duy của ngôn ngữ lập trình. Quả thật, một công thức nguyên tử R ∈ Rel đem đến R một kiểu (type) của các bộ giá trị trong Rel, và những so sánh như R.a op S.b và R.a op Hằng_số đem lại những giới hạn trên trường R.a. Nếu một biến R không xuất hiện trong một công thức nguyên tử theo dạng R ∈ Rel (tức là, nó xuất hiện chỉ trong các công thức nguyên tử là các so sánh), chúng ta sẽ sinh ra một thoả thuận ngầm rằng kiểu của R là một bộ giá trị của những trường bao gồm tất cả (và chỉ) những trường của R xuất hiện trong công thức.

Chúng ta sẽ không định nghĩa các kiểu của biến một cách chính thức, nhưng kiểu của một biến nên rõ ràng trong hầu hết các trường hợp, và điểm quan trọng phải ghi nhớ là những so sánh thực hiện trên những kiểu dữ liệu khác nhau luôn bị lỗi. (Trong những bàn luận của phép toán logic quan hệ, giả định đơn giản thường được làm là có một miền duy nhất của các hằng số và miền liên quan đến mỗi trường của mỗi quan hệ.)

Truy vấn TRC được định nghĩa theo dạng {T | p(T)}, trong đó T là biến 'tự do' trong công thức p.

Ngữ nghĩa của các truy vấn TRC

Ý nghĩa của TRC là gì? Hay chính xác hơn, cái gì là tập các bộ giá trị kết quả của một truy vấn TRC? Câu trả lời tới truy vấn TRC {T | p(T)}, như chúng ta đã nói tới phía trên, là tập của tất cả các bộ giá trị t trong công thức p(T) mà với T=t thì p(T) đúng.

Một truy vấn được đánh giá trên một minh hoạ được cơ sở dữ liệu cung cấp. Mỗi biến 'tự do' trong công thức F được gán một giá trị của bộ, F đúng nếu thỏa mãn một trong những điều kiện sau:

• F là một công thức nguyên tử R ∈ Rel, và R được gán bằng một bộ giá trị trong minh họa của quan hệ Rel.
• F là một so sánh R.a op S.b, R.a op Hằng_số, hoặc Hằng_số op R.a, và những bộ giá trị gán cho R và S có giá trị trường R.a và R.b làm cho công thức đúng.
• F có dạng p, trong đó p không đúng; hoặc có dạng p ∧ q, trong đó cả p và q đúng; hoặc có dạng p ∨ q trong đó p hoặc q đúng; hoặc có dạng p ⇒ q trong đó q đúng hoặc p đúng.
• F có dạng ∃R(p(R)), trong đó có một hoặc một số phép gán của các bộ giá trị cho các biến trong p(R), kể cả biến R, làm cho công thức p(R) đúng.
• F có dạng ∀R(p(R)), trong đó có một số phép gán của các bộ giá trị cho các biến trong p(R) làm cho công thức p(R) đúng với bất kỳ bộ giá trị nào được gán cho R.

Những ví dụ của truy vấn TRC

Bây giờ chúng ta minh hoạ phép toán logic quan hệ thông qua một số ví dụ, sử dụng minh hoạ B1 của Boats, R2 của Reserves và S3 của Sailors chỉ ra trong Hình 15, 16 và 17. Chúng ta sử dụng các dấu ngoặc khi cần thiết để làm công thức của chúng ta rõ ràng hơn. Thường thì một công thức p(R) bao gồm một điều kiện R ∈ Rel. Chúng ta sẽ sử dụng ký hiệu ∃ R ∈ Rel(p(R)) cho ∃R(R ∈ Rel ∧ p(R)). Tương tự, chúng ta sử dụng ghi chú ∀R ∈ Rel(p(R)) cho ∀R(R ∈ Rel ⇒ p(R)).

(Q12) Tìm tên và tuổi của các thuỷ thủ có Rating>7.

{P | ∃ S ∈ Sailors(S.rating > 7 ∧ P.name = S.sname ∧ P.age = S.age)}

Truy vấn này minh hoạ: P được xem là một biến bộ với chính xác hai trường là name và age. Kết quả của truy vấn này là một quan hệ gồm hai trường, name và age. Công thức nguyên tử P.name=S.name và P.age=S.age cung cấp giá trị cho các trường của bộ giá trị kết quả P. Trên minh hoạ B1, R2 và S3, kết quả là tập bộ giá trị <Lubber, 55.5>, <Andy, 25.5>, <Rusty, 35.0>, <Zorba, 16.0>, và <Horatio, 35.0>.

(Q13) Tìm tên thủy thủ (name), mã thuyền (bid), và ngày phục vụ (date) của mỗi sự phục vụ.

{ P | ∃ R ∈ Reserves ∃ S ∈ Sailors

(R.sid = S.sid ∧ P.bid = R.bid ∧ P.day = R.day ∧ P.sname = S.sname)}

Với mỗi bộ giá trị của Reserves, chúng ta tìm một bộ giá trị trong Sailors có cùng sid. Với mỗi cặp của các bộ giá trị như thế, chúng ta xây dựng một bộ giá trị kết quả P với các trường sname, bid và day bằng cách sao chép các trường tương ứng từ hai bộ giá trị này. Truy vấn này minh hoạ cách chúng ta có thể kết hợp những giá trị từ những quan hệ khác nhau trong mỗi bộ giá trị kết quả. Kết quả của truy vấn này thực hiện trên minh hoạ quan hệ B1, R2 và S3 chỉ ra trong Hình 20.

(Q1) Tìm tên những thuỷ thủ đã phục vụ trên tàu 103

{P | ∃ S ∈ Sailors ∃R ∈ Reserves(R.sid=S.sid ∧ R.bid=103 ∧ P.sname=S.sname)}

Truy vấn này có thể được đọc như sau: Tìm ra tất cả các bộ giá trị Sailors, cái mà có tồn tại một bộ trong Reserves, có cùng giá trị trong trường sid, và với bid=103. Đó là, với mỗi bộ giá trị sailor, chúng ta tìm một bộ giá trị trong Reserves chỉ ra rằng sailor này đã phục vụ trên tàu 103. Bộ giá trị kết quả P chỉ chứa một trường là sname.

(Q2) Tìm tên những thuỷ thủ đã phục vụ trên tàu có màu 'red'

{P | ∃ S ∈ Sailors ∃R ∈ Reserves(R.sid = S.sid ∧ P.sname = S.sname

∧ ∃ B ∈ Boats(B.bid = R.bid ∧ B.color = 'red'))}

Truy vấn này có thể được đọc như sau: Tìm tất cả các bộ giá trị Sailors, cái mà có tồn tại các bộ giá trị R trong Reserves và B trong Boats để S.sid=R.sid, R.bid=B.bid và B.color='red'. Cách viết khác phù hợp với cách đọc trên là:

{ P | ∃S ∈ Sailors ∃R ∈ Reserves ∃B ∈ Boats

(R.sid = S.sid ∧ B.bid = R.bid ∧ B.color ='red' ∧ P.sname = S.sname)}

(Q7) Tìm ra tên các thuỷ thủ đã phục vụ trên ít nhất hai tàu.

{P | ∃S ∈ Sailors ∃R1 ∈ Reserves ∃R2 ∈ Reserves

(S.sid = R1.sid ∧ R1.sid = R2.sid ∧ R1.bid ≠ R2.bid ∧ P.sname = S.sname)}

So sánh truy vấn này trong phiên bản sử dụng đại số quan hệ và thấy chúng đơn giản hơn nhiều khi sử dụng các phép toán logic. Một phần, sự khác nhau này là do sự cồng kềnh trong việc đổi tên các trường trong phiên bản đại số quan hệ, nhưng phiên bản phép toán logic thì thực sự đơn giản hơn.

(Q9) Tìm tên các cầu thủ đã phục vụ trên tất cả các chuyến tàu.

{P | ∃ S ∈ Sailors ∀B ∈ Boats

(∃R ∈ Reserves(S.sid=R.sid ∧ R.bid=B.bid ∧ P.sname=S.sname))}

Truy vấn này được biểu diễn sử dụng phép chia trong đại số quan hệ. Hãy xem nó được biểu diễn dễ dàng như thế nào trong phép toán logic. Biểu diễn truy vấn theo phép toán logic trực tiếp phản chiếu cách chúng ta biểu diễn một truy vấn bằng tiếng Anh: "Tìm những thủy thủ S để với tất cả các tàu B có một bộ giá trị Reserves chỉ ra rằng thủy thủ S đã phục vụ trên tàu B."

(Q14) Tìm tất cả các thủy thủ đã phục vụ trên tất cả tàu có màu 'red'.

{S | S ∈ Sailors ∧ ∀B ∈ Boats

(B.color ='red') ⇒ (∃R ∈ Reserves(S.sid = R.sid ∧ R.bid = B.bid)))}

Truy vấn này có thể được đọc như sau: Với mỗi ứng viên (thủy thủ), nếu một tàu có màu 'red', thủy thủ phải phục vụ trên tàu này. Đó là, với mỗi ứng viên thủy thủ, một tàu màu 'red' phải chỉ ra thủy thủ này phục vụ trên nó. Quan sát thấy rằng, vì chúng ta có thể trả về kết quả là một thực thể thủy thủ thay vì chỉ trả về tên của họ, nên chúng ta tránh đưa vào biến tự do mới (ví dụ, biến P trong ví dụ trước) để nắm giữ giá trị kết quả. Trên minh họa B1, R2 và S3, kết quả chứa các bộ giá trị Sailors có sid là 22 và 31.

Chúng ta có thể viết truy vấn này không cần sử dụng phép kéo theo, bằng cách thay p ⇒ q bằng công thức logic tương đương p ∨ q:

{S | S ∈ Sailors ∧ ∀B ∈ Boats

(B.color ≠ 'red' ∨ (∃R ∈ Reserves(S.sid = R.sid ∧ R.bid = B.bid)))}

Truy vấn này nên được đọc như sau: Tìm những thủy thủ S ứng với mọi tàu B, hoặc tàu không có màu 'red' hoặc một bộ giá trị Reserves nào đó chỉ ra rằng thủy thủ S đã phục vụ tàu B."

• Phép toán logic trên miền

Biến miền là biến nhận giá trị là miền của một số thuộc tính (ví dụ, biến có thể được gán giá trị Integer nếu nó xuất hiện trong một thuộc tính mà miền của nó là tập các số Integer). Truy vấn DRC có dạng {<x₁, x₂, …, x_n> | p(<x₁, x₂, …, x_n>)}, trong đó mỗi x_i hoặc là biến miền hoặc là hằng số và p(<x₁, x₂, …, x_n>) là một công thức DRC, nơi mà chỉ có những công thức nguyên tố. Kết quả của truy vấn này là tập các bộ giá trị <x₁, x₂, …, x_n> làm cho P đúng.

Công thức DRC được định nghĩa theo cách tương tự như cách định nghĩa của công thức TRC. Sự khác nhau chính là các biến trong trường hợp này là các biến miền. Giả sử op là các phép toán trên tập hợp {<, >, =, ≤, ≥ ≠} và giả sử X, Y là các biến miền. Một công thức nguyên tử trong DRC có một trong những dạng sau:

• <x₁, x₂, …, x_n> ∈ Rel, trong đó Rel là một quan hệ có n thuộc tính, mỗi xi (1 ≤ i ≤ n) là một biến hoặc một hằng số.
• X op Y

Một công thức được định nghĩa đệ quy theo một trong các dạng sau, trong đó p và q là công thức, và p(X) là một công thức có biến X xuất hiện trong đó:

• Bất kỳ công thức nguyên tử nào
• p, p ∧q, p ∨q, hoặc p ⇒ q
• ∃X(p(X)), trong đó X là một biến miền
• ∃X(p(X)), trong đó X là một biến miền

Người đọc xem lại để so sánh định nghĩa này với định nghĩa công thức TRC và nhận thấy sự liên quan giữa hai định nghĩa này. Chúng ta sẽ định nghĩa ngữ nghĩa của công thức DRC chính thức, đây là một bài tập cho người đọc.

Ví dụ của truy vấn DRC

Chúng ta sẽ minh họa DRC thông qua một số ví dụ. Người đọc xem lại để so sánh với phiên bản định nghĩa theo TRC.

(Q11) Tìm tất cả thủy thủ có rating>7.

{<I, N, T, A> | <I, N, T, A> ∈ Sailors ∧ T > 7}

Điều kiện <I, N, T, A> ∈ Sailors đảm bảo rằng các biến miền I, N , T và A được giới hạn là các trường của cùng một bộ. So sánh với truy vấn TRC, chúng ta có thể dùng T>7 thay vì S.rating>7, nhưng chúng ta phải chỉ ra bộ <I, N, T, A> trong kết quả, không chỉ là S.

(Q1) Tìm ra tên các thủy thủ đã phục vụ trên tàu 103.

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors

∧ ∃Ir, Br, D(<Ir, Br, D> ∈ Reserves ∧ Ir = I ∧ Br = 103))}

Chú ý rằng chỉ có trường sname được giữ lại trong kết quả và chỉ có N là biến tự do. Chúng ta sử dụng biểu diễn ∃Ir, Br, D (…) như cách viết nhanh của ∃Ir(∃Br(∃D(…))). Rất thường xuyên, tất cả các biến định lượng xuất hiện trong một quan hệ đơn, như trong ví dụ này. Và thậm chí co lại là ∃Ir, Br, D ∈ Reserves. Chúng ta sẽ sử dụng cách này từ nay về sau, và truy vấn trên được viết như sau:

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors

∧ ∃<Ir, Br, D> ∈ Reserves(Ir = I ∧ Br = 103))}

Truy vấn này cũng có thể được viết như sau, lưu ý sự lặp lại của biến I và cách sử dụng hằng số 103:

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors ∧ ∃D(<I, 103, D> ∈ Reserves))}

(Q2) Tìm tên các thủy thủ đã phục vụ trên tàu có màu 'red'

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors

∧ ∃<I, Br, D> ∈ Reserves ∧ ∃<Br, BN, 'red'> ∈ Boats)}

(Q7) Tìm tên các thủy thủ đã phục vụ trên ít nhất hai tàu.

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors ∧

∃Br1, Br2, D1,D2(<I,Br1,D1>∈ Reserves ∧ <I,Br2,D2> ∈ Reserves ∧ Br1≠Br2))}

Ghi nhớ biến I được sử dụng lặp lại để đảm bảo rằng cùng một thủy thủ đã phục vụ trên hai tàu.

(Q9) Tìm tên các thủy thủ đã phục vụ trên tất cả các tàu.

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors ∧

∀B, BN, C(-,(<B, BN, C> ∈ Boats) ∨

(∃<Ir, Br, D> ∈ Reserves(I = Ir ∧ Br = B))))}

Truy vấn này có thể được đọc như sau: Tìm tất cả giá trị của N mà có một vài bộ <I, N, T, A> trong Sailors thỏa mãn điều kiện sau: với mỗi <B, BN, C>, hoặc ở đây không có một bộ nào trong Boats hoặc không có một số bộ <B, BN, C> trong Reserves để chứng minh rằng Sailors I đã phục vụ tàu B." Lượng tử ∀ cho phép các biến miền B, BN, và C có thể nhận tất cả các giá trị trong các miền thuộc tính tương ứng của chúng, và đoạn '-,(<B, BN, C> ∈ Boats) ∨' là cần thiết để hạn chế chú ý đến giá trị xuất hiện trong bộ giá trị của Boats. Đoạn này thường dùng trong công thức DRC, và có thể được thay bằng ∀<B, BN, C> ∈ Boats. Điều này tương đương với cách viết đối với lượng tử ∃ đã giới thiệu. Với cách này, truy vấn được viết như sau:

{<N> | ∃I, T, A(<I, N, T, A> ∈ Sailors ∧ ∀<B, BN, C> ∈ Boats

(∃<Ir, Br, D> ∈ Reserves(I = Ir ∧ Br = B)))}

(Q14) Tìm những thủy thủ đã phục vụ trên tất cả tàu có màu 'red'.

{<I, N, T, A> | <I, N, T, A> ∈ Sailors ∧ ∀<B, BN, C> ∈ Boats

(C =red) ⇒ ∃<Ir, Br, D> ∈ Reserves(I = Ir ∧ Br = B))}

Ở đây, chúng ta tìm ra tất cả các thủy thủ mà với tất cả tàu màu 'red' có một bộ trong Reserves chỉ ra thủy thủ này đã làm việc trên đó.

Khả năng của đại số và các phép toán logic trên quan hệ

Chúng tôi đã trình bày hai loại của ngôn ngữ truy vấn của mô hình quan hệ. Khả năng của chúng như thế nào? Có phải tất cả các truy vấn biểu diễn trong đại số quan hệ có thể được biểu diễn trong phép toán logic quan hệ? Câu trả lời là có. Trước khi chúng ta trả lời câu hỏi này, chúng ta xem xét một vấn đề chính cùng với phép toán logic.

Xem xét truy vấn {S |(S ∈ Sailors)}. Cú pháp của truy vấn này là đúng. Tuy nhiên, nó yêu cầu tất cả các bộ giá trị S mà S không phải là Sailors. Tập các bộ giá trị S như vậy là vô hạn. Ví dụ này là một minh hoạ của truy vấn không an toàn. Chúng ta cần phải hạn chế những phép toán logic quan hệ để không cho phép những truy vấn không an toàn.

Bây giờ chúng ta phác hoạ như thế nào các truy vấn phép toán logic được hạn chế để trở nên an toàn. Xem xét một tập I các minh hoạ quan hệ, với một minh hoạ trên một quan hệ xuất hiện trong truy vấn Q. Giả sử Dom(Q, I) là tập của tất cả các hằng số xuất hiện trong minh hoạ quan hệ I hoặc trong công thức của truy vấn Q. Vì chúng ta chỉ cho phép những minh hoạ I hữu hạn, Dom(Q, I) cũng là hữu hạn.

Với mỗi công thức logic quan hệ Q được xem là an toàn, chúng ta muốn đảm bảo rằng với bất kỳ I nào được cung cấp, tập kết quả của truy vấn Q chứa chỉ những giá trị thuộc Dom(Q,I). Trong khi hạn chế này được yêu cầu, nó vẫn là chưa đủ. Chúng ta không chỉ muốn tập kết quả được đưa ra dựa trên các hằng số trong Dom(Q,I)! Hy vọng này dẫn tới việc sử dụng các lượng tử phổ dụng ∃ và ∀: Với một công thức TRC có dạng ∃R(p(R)), chúng ta muốn tìm tất cả các giá trị của biến R làm cho công thức đúng bằng việc chỉ kiểm tra những bộ giá trị chứa các hằng số trong Dom(Q,I). Tương tự, với một công thức TRC có dạng ∀R(p(R)), chúng ta muốn tìm một giá trị nào đó của biến R làm cho công thức sai bằng cách chỉ kiểm tra những bộ giá trị chứa các hằng số trong Dom(Q, I).

Vì thế, chúng ta định nghĩa công thức Q là công thức TRC an toàn như sau:

1. Với bất kỳ giá trị I nào được cung cấp, tập kết quả của truy vấn Q chỉ chứa những giá trị trong Dom(Q, I).
2. Với mỗi công thức con có dạng ∃R(p(R)) trong Q, nếu một bộ r (gán tới biến R) làm cho công thức đúng, thì r chứa chỉ những hằng số trong Dom(Q, I).
3. Với mỗi công thức con có dạng ∀R(p(R)) trong Q, nếu một bộ r (gán tới biến R) chứa hằng số nào đó không ở trong Dom(Q, I), thì r phải làm cho công thức đúng.

Ghi nhớ rằng định nghĩa này không 'có tính xây dựng', nó không nói cho chúng ta cách làm thế nào để kiểm tra một truy vấn là an toàn.

Truy vấn Q= S (S ∈ Sailors) là không an toàn theo định nghĩa này. Dom(Q,I) là tập tất cả các giá trị xuất hiện trong (một minh hoạ I của) Sailors. Xem xét minh hoạ S1 trong Hình 4.1. Kết quả của truy vấn này rõ ràng bao gồm những giá trị không xuất hiện trong Dom(Q, S1).

Quay trở lại câu hỏi trên, chúng ta có thể chỉ ra rằng tất cả truy vấn có thể được biểu diễn sử dụng phép toán logic an toàn, truy vấn cũng có thể được biểu diễn trong đại số quan hệ. Sức mạnh của đại số quan hệ thường được sử dụng như thước đo sức mạnh của ngôn ngữ truy vấn cơ sở dữ liệu quan hệ. Nếu một ngôn ngữ truy vấn có thể biểu diễn được tất cả các truy vấn trong đại số quan hệ, nó được gọi là relationally complete. Ngôn ngữ truy vấn thực hành được hy vọng là relationally complete; thêm nữa, ngôn ngữ truy vấn thương mại điển hình hỗ trợ các đặc trưng cho phép chúng ta biểu diễn cả các truy vấn mà không biểu diễn được trong đại số quan hệ.

Câu hỏi tổng kết

Trả lời các câu hỏi tổng kết sau, tham khảo tới nội dung của phần kèm theo.

• Cái gì là đầu vào của một truy vấn quan hệ? Cái gì là kết quả của một truy vấn? (Phần 4.1)
• Các hệ cơ sở dữ liệu sử dụng một vài dạng của đại số quan hệ để trình bày những kế hoạch đánh giá truy vấn. Giải thích vì sao đại số là thích hợp cho mục đích này? (Phần 2)
• Trình bày phép chọn. Điều kiện của các bảng đầu vào và đầu ra của phép toán này? (Đó là, nếu đầu vào có k bộ giá trị, thì đầu ra là gì?). Trình bày phép chiếu. Điều kiện của các bảng đầu vào và đầu ra của phép toán này? (Phần 2.1)
• Trình bày các phép toán tập hợp của đại số quan hệ, bao gồm phép hợp (), phép giao (), phép trừ (－), và phép nhân (×). Với mỗi phép toán, điều kiện của các bảng đầu vào và đầu ra của phép toán này là gì? (Phần 2.2)
• Giải thích phép đổi tên được sử dụng như thế nào? Nó có bắt buộc không? Nếu phép toán này không được phép, có truy vấn nào không thể được biểu diễn bằng đại số không? (Phần 2.3)
• Định nghĩa tất cả các dạng của phép nối. Vì sao phép nối được đặc biệt quan tâm. Có phải chúng ta không thể biểu diễn tất cả các phép nối dựa trên phép nhân chéo, phép chọn và phép chiếu? (Phần 2.4)
• Định nghĩa phép chia dựa trên các phép toán đại số quan hệ cơ bản. Trình bày một truy vấn đặc trưng cho phép chia. Không như phép nối, phép chia không được biểu diễn riêng trong hệ cơ sở dữ liệu. Giải thích vì sao? (Phần 2.5)
• Phép toán logic quan hệ được gọi là ngôn ngữ phi thủ tục, đối lập với đại số quan hệ là ngôn ngữ thủ tục. Giải thích sự khác nhau. (Phần 3)
• Một truy vấn dựa trên phép toán logic quan hệ 'biểu diễn' các bộ kết quả như thế nào? Trình bày về cách sử dụng của các lượng tử tồn tại và phổ dụng, biến kết buộc và biến tự do. (Phần 3.1)
• Sự khác nhau giữa TRC và DRC là gì? (Phần 3.2)
• Truy vấn dựa trên phép toán logic không an toàn là gì? Vì sao phải hạn chế những truy vấn này? (Phần 4)
• Đại số quan hệ và phép toán logic quan hệ được cho là có khả năng tương đương. Giải thích nhận xét này và nó liên quan tới 'relationally complete' như thế nào.(Phần 4)

Bài tập

Tài liệu tham khảo

Đại số quan hệ đã được Codd đề xuất trong [187], và anh ấy đã chỉ ra sự tương đương giữa đại số quan hệ và TRRC trong [189]. Ở thời điểm sớm hơn, Kuhns [454] đã xem xét đến việc sử dụng logic để viết truy vấn.

LaCroix & Pirotte trình bày về DRC trong [459]. Klug tổng quát hóa đại số quan hệ và các phép toán logic bao gồm các hàm nhóm trong [439]. Những mở rộng của đại số và phép toán logic để thực hiện các hàm nhóm được bàn đến trong [578]. Merrett đã đề xuất về đại số quan hệ mở rộng dựa trên những lượng tử tồn tại và phổ dụng [530]. Lượng tử phổ dụng được trình bày nhiều trong [52].