Bài giảng chương 3: Đại số quan hệ

Chương 3: Đại số quan hệ • I. Giới thiệu • II. Một số khái niệm bổ sung • III. Các phép toán căn bản • IV. Các phép toán khác • V. Các hàm kết tập I. Giới thiệu • DML trên mô hình quan hệ: –Ngôn ngữ hỏi: phần chính của DML –Ngôn ngữ cập nhật dữ liệu • 2 kiểu ngôn ngữ hỏi: • Ngôn ngữ đại số: có nền là đại số quan hệ • Ngôn ngữ tính toán tân từ II. Một số khái niệm bổ sung • 1. Đại số hệ • 2. Đại số quan hệ • 3. Biểu thức quan hệ • 4. Quan hệ tương thích II. Một số khái niệm bổ sung 1. Đại số hệ • Đại số hệ = : – M: tập hợp nền – F: tập các phép toán trên M Mỗi f∈F là một phép toán n ngôi. f: Mn→M Ví dụ: với F={+, -, *} II. Một số khái niệm bổ sung 2. Đại số quan hệ • Đại số quan hệ : một đại số hệ đặc biệt , với: –M: một CSDL quan hệ –F: tập các phép toán quan hệ trên M II. Một số khái niệm bổ sung 3. Biểu thức quan hệ • Biểu thức quan hệ : xây dựng bởi: – các quan hệ trong một CSDL quan hệ, và –các phép toán quan hệ II. Một số khái niệm bổ sung 4. Quan hệ tương thích • Quan hệ tương thích = Các quan hệ có cùng sơ đồ quan hệ III. Các phép toán căn bản • 1. Phép chọn • 2. Phép chiếu • 3. Phép trừ • 4. Phép hội • 5. Phép lấy tích Đề-các III. Các phép toán căn bản 1. Phép chọn • a. Mục đích: Tạo ra một tập con các bộ của quan hệ hiện hành, các bộ này phải thỏa một điều kiện luận lý nào dó. III. Các phép toán căn bản 1. Phép chọn (2) • b. Giả thiết: Cho – Tập các thuộc tính U – Quan hệ trên U: R(U) – Biểu thức luận lý F trên U, gồm có: • các tác tố: hằng/ tên thuộc tính/ số thứ tự thuộc tính • các phép so sánh số học: , ≥, ≤, =, ≠ • các phép kết nối luận lý: ∧ (và), ∨ (hoặc) , ⎤ (phủ định) => F= biểu thức chọn/ điều kiện chọn III. Các phép toán căn bản 1. Phép chọn (3) • c. Định nghĩa: –Phép toán một ngôi đặc biệt, trên quan hệ R theo điều kiện F, sinh ra một quan hệ P: P= R(F) ={t ∈R| F(t) } Ký hiệu khác: P= σF(R) III. Các phép toán căn bản 2. Phép chiếu a. Mục đích: Chỉ sử dụng một số thuộc tính cần thiết trong quan hệ đang xét. III. Các phép toán căn bản 2. Phép chiếu (2) b. Giả thiết: Cho –Tập các thuộc tính U= {A1, A2, …, An} –Quan hệ trên U: R(A1, A2, …, An) –Tập con các thuộc tính X⊂U, X ≠ U X= {Ai1, Ai2, …, Aim} j=1, .., m ij= 1, .., n III. Các phép toán căn bản 2. Phép chiếu (3) c. Định nghĩa: Phép toán một ngôi đặc biệt, trên tập thuộc tính X của quan hệ R, sinh ra một quan hệ P: P= R[X] = {t[X] | t ∈R} hoặc P= R.X = {t.X | t ∈R} Ký hiệu khác: P= ∏X(R) III. Các phép toán căn bản 3. Phép trừ/ hiệu • Định nghĩa : Kết quả của phép trừ giữa hai quan hệ tương thích R(U) et S(U) là P(U) (cũng tương thích với R và S): P= R-S= {t | t ∈R ∧ t ∉S } III. Các phép toán căn bản 4. Phép hội/ hợp • Định nghĩa: Hội của hai quan hệ tương thích R(U) et S(U) là P(U) (cũng tương thích với R và S): P= R∪S= {t | t ∈R ∨ t ∈ S } III. Các phép toán căn bản 4. Tích Đề-các • a. Giả thiết : Cho – R(A1, A2, …, An) Ai ∈U i=1,.., n – S(B1, B2, …, Bm) Bj∈V j=1,.., m – U ∩ V= ∅ III. Các phép toán căn bản 4. Tích Đề-các (2) • b.Định nghĩa: Tích Đề-các của R và S là một tập hợp có: • n*m bô, • n+m thuộc tính, • mỗi bộ có : n thuộc tính đầu có dạng một bộ u của R m thuộc tính cuối ----------------- v của S • (mỗi bộ u của R với mọi bộ v của S) R x S= { | u ∈R ∧ v ∈ S } IV. Các phép toán khác 1. Phép giao 2. Phép chia 3. Phép kết nối bình thường 4. Phép kết nối tự nhiên IV. Các phép toán khác 1. Phép giao • Định nghĩa: Giao của hai quan hệ tương thích R(U) et S(U) là P(U) (cũng tương thích với R và S): P= R∪S= {t | t ∈R ∧ t ∈ S } IV. Các phép toán khác 2. Phép chia • a. Giả thiết : Cho – R(U) n ngôi – S(V) m ngôi – V ⊂U – S ≠ ∅ Đặt X=U-V IV. Các phép toán khác 2. Phép chia (2) • b. Định nghĩa: Kết quả của phép chia quan hệ R cho S là một quan hệ gồm các bộ t có (n-m) thuộc tính, sao cho với mọi bộ v trong S, thì là một bộ thuộc R. R ÷ S = {t=u[X] | (u ∈R) ∧ (∀v∈ S) ( ∈R) } IV. Các phép toán khác 3. Phép kết nối bình thường • a. Giả thiết : Cho θ: phép so sánh số học R(U) S(V) IV. Các phép toán khác 3. Phép kết nối bình thường (2) • b. Định nghĩa : Phép kết nối-θ giữa quan hệ R đối với thụộc tính A (A ∈U) và quan hệ S đối với thuộc tính B (B ∈V) : R S= { | (u ∈R) ∧ (v∈ S) ∧ AθB (u[A] θ v[B])} IV. Các phép toán khác 3. Phép kết nối bình thường (3) • Phép kết nối-θ chỉ thực hiện được khi θ thực hiện được. • Là sự kết hợp phép chọn trên tích Đề- các. • θ : phép so sánh “=“ => kết nối-θ : kết nối bằng (equịoin) IV. Các phép toán khác 4. Phép kết nối tự nhiên • Định nghĩa : –Là phép kết nối bằng –Tại 2 thuộc tính cùng tên –Một trong hai thuộc tính đó bị loịa bỏ trong kết quả kết nối IV. Các phép toán khác 5. Phép kết nối mở rộng • a. Mục đích: – Cho phép làm việc với thông tin bị thiếu. – Tránh làm mất thông tin như trong kết nối bình thường. • b. Định nghĩa: – Là phép kết nối tự nhiên thực hiện trên các trị trống của thuộc tính dùng để kết nối. IV. Các phép toán khác 5. Phép kết nối mở rộng (2) Loại Ký hiệu Định nghĩa Mở rộng bên trái Mở rộng bên phải Mở rộng toàn bộ SR SR SR SRP∪ Q∪ SR P∪ Q∪ SR IV. Các phép toán khác 5. Phép kết nối mở rộng (3) P = { | u∈R, u khäng tæång æïng våïi bäü naìo cuía S & v∈S, caïc trë cuía caïc thuäüc tênh trong v âãöu âæåüc gaïn trë träúng} Q = { | v∈S, v khäng tæång æïng våïi bäü naìo cuía R & u∈R, caïc trë cuía caïc thuäüc tênh trong u âãöu âæåüc gaïn trë träúng } V. Các hàm kết tập 1. Hàm kết tập bình thường 2. Hàm kết tập trên nhóm các bộ V. Các hàm kết tập 1. Hàm kết tập bình thường a. Định nghĩa: Là hàm – Thực hiện trên một tập các trị: • có thể có trị trùng nhau: tập bội • không có trị trùng nhau – Trả lại kết quả là trị duy nhất – Nếu xét trên tập bội và muốn loại bỏ trị trùng: thêm “-distinct” sau tên hàm. V. Các hàm kết tập 1. Hàm kết tập bình thường (2) b. Danh sách hàm: Tãn haìm Ý nghĩa sum Tênh täøng cuía mäüt táûp giaï trë avg Tênh trung bçnh cuía mäüt táûp giaï trë count Âãúm säú giaï trë cuía mäüt táûp håüp min Tênh giaï trë låïn nháút cuía mäüt táûp giaï trë max Tênh giaï trë nhoí nháút cuía mäüt táûp giaï trë V. Các hàm kết tập 1. Hàm kết tập trên nhóm các bộ a. Nhu cáöu: Muäún aïp duûng haìm kãút táûp: - khäng phaíi chè trong mäüt táûp caïc bäü thäi, - maì trãn nhiãöu táûp caïc bä,ü mäùi tập laì mäüt nhoïm. V. Các hàm kết tập 1. Hàm kết tập trên nhóm các bộ (2) b. Giả thiết: E: biãøu thæïc âaûi säú quan hãû G1, G2, ..., Gm : danh saïch caïc thuäüc tênh maì viãûc chia nhoïm dæûa trãn âoï (mäùi nhoïm coï mäüt trị (g1, g2, ..., gm): + như nhau ở các bộ trong cung nhoïm + khaïc nhau åí caïc nhoïm khaïc nhau). (∀i=1, .., n) Fi : haìm kãút táûp, Ai: thuäüc tênh. V. Các hàm kết tập 1. Hàm kết tập trên nhóm các bộ (3) c. Định nghéa: Haìm kãút táûp trãn nhoïm coï daûng: G1, G2, ..., Gm G F1 A1, F2A2, ..., FnAn (E) Âäúi våïi mäùi nhoïm (g1, g2, ..., gm), kãút quaí seî coï mäüt bäü (g1, g2, ..., gm, a1, a2, ..., an): (∀i=1, .., n) ai : kãút quaí cuía viãûc aïp duûng haìm Fi trãn táûp bäüi caïc trë cuía Ai trong nhoïm.