Đại số quan hệ và các phép toán logic

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.

Minh họa S1 của Sailors Minh họa S2 của Sailors Minh họa R1 của Reservers

Đạ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ị.

_rating>8(S2)

π _sname,rating(S2)

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.

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

• 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.

S1 U S2

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ế.

S1 giao S2 S1 － S2 S1 × S2

• Đổ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( F¯ size 12{ {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ênF¯ size 12{ {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à F¯ size 12{ {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.

S1 _{S1.sid<R1.sid}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ả.

S1 _R.sid=S.sid R1

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)

Ví dụ minh họa phép chia

Để 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)

Minh họa S3 của Sailors Minh họa R2 của Reserves

Minh họa B1 của Boats

Đầ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.

Minh hoạ của Temp1 Minh hoạ của 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