Mô hình quan hệ (Relational model)

Mô hình quan hệ (Relational model) 1 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Giới thiệu  Mô hình quan hệ sử dụng lý thuyết tập hợp và logic bậc nhất để biểu diễn dữ liệu  CSDL được biểu diễn bằng một tập các bảng:  Mỗi bảng là tập hợp các các bộ giá trị  Mỗi cột đều có cùng một kiểu dữ liệu  Mỗi hàng trong bảng là bộ các giá trị có quan hệ với nhau  So sánh với mô hình ER:  Mỗi bảng tương ứng với một tập thực thể  Mỗi cột tương ứng một thuộc tính  Mỗi hàng trong bảng tương ứng với một thực thể 2 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Họ tên Tuổi Giới tính Trần Khánh Linh 25 Nam Bill Gates 50 Nam Lý Liên Kiệt 45 Nam Lưu Diệc Phi 25 Nữ Nguyễn Văn Bố 37 Nam Lê Thị Mẹ 30 Nữ … … … … … … … … … Các định nghĩa  Một mô hình quan hệ là tập hợp các quan hệ (relation)  Mỗi quan hệ gồm 2 phần:  Thể hiện (instance): là bảng các bộ giá trị (tuples)  Lược đồ (schema): chứa tên của quan hệ, cùng với tên và kiểu từng cột của bảng  VD: Book(id: integer, title: string, author: string, pub-year: integer)  Số dòng của bảng: lực lượng (cardinality) của quan hệ  Số cột của bảng: bậc (degree) của quan hệ  VD:  Lực lượng: 3  Bậc: 4 3 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội id title author pub-year 1 The call of the wild Jack London 1903 3 The universe in a nutshell Stephen Hawking 2001 4 Hồng lâu mộng Tào Tuyết Cần 1791 Định nghĩa bằng toán học  Lược đồ quan hệ R là tích Đề-các các miền giá trị của các thuộc tính  Đầy đủ: Book(id: int, title: string, author: string, pub-year: int)  Ngắn gọn: Book(id, title, author, pub-year) Book = dom(int) × dom(string) × dom(string) × dom(int) (trong đó dom(…) ký hiệu tập giá trị của một kiểu)  Quan hệ r trên R: ký hiệu bằng r(R) là một tập con của R my-books = my-books(Book) ⊂ Book  Một phần tử của r gọi là một thể hiện, một hàng, hay một bộ giá trị  Chú ý: người ta thường gọi tắt “quan hệ” thay cho “thể hiện của quan hệ” 4 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Khoá (key)  Các khái niệm về khoá của quan hệ cũng tương tự như với thực thể trong mô hình ER  Siêu khoá (superkey): tập các thuộc tính mà bộ giá trị không lặp lại  Nếu K là một siêu khoá thì K’ = K ∪ a cũng là một siêu khoá, với a là một thuộc tính của quan hệ  Khoá ứng viên (candidate key): là siêu khoá không cố thuộc tính dư thừa (không tồn tại siêu khoá là tập con)  Một quan hệ có thể có 0, 1 hoặc nhiều siêu khoá  Khoá chính (primary key): là một khoá ứng viên được người thiết kế CSDL lựa chọn  Mỗi quan hệ chỉ có nhiều nhất một khoá chính 5 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Ví dụ  K1 = {A} không phải khoá vì các giá trị có lặp lại  K2 = {A, B} là siêu khoá vì không có bộ giá trị nào lặp lại  K3 = {A, B, C} là siêu khoá vì K2 là siêu khoá và K2 ⊂ K3  K2 là khoá ứng viên vì không có tập con nào của K2 là siêu khoá  K3 không phải khoá ứng viên vì K2 ⊂ K3 là một siêu khoá 6 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội A B C 1 aa x 1 ab x 2 aa y 2 ab y 2 bb y 3 ab x 3 bb x 4 aa y 5 bb x Khoá ngoài (foreign key)  Một quan hệ r1 có chứa khoá chính K của quan hệ r2 thì K gọi là khoá ngoài của r1 tham chiếu tới r2  Với mỗi thể hiện của r1, tồn tại ít nhất một thể hiện của r2 có giá trị của K giống ở r1  Ví dụ: o sv ⊂ SinhVien(id-sinh-vien, ten, nam-sinh) diem ⊂ Diem(id-sinh-vien, mon-hoc, diem) o id-sinh-vien là khoá ngoài của quan hệ diem tham chiếu tới quan hệ sv o mỗi giá trị của id-sinh-vien tồn tại trong quan hệ diem cũng tồn tại trong quan hệ sv 7 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Sơ đồ CSDL  Một mô hình quan hệ cũng có thể được biểu diễn dưới dạng sơ đồ 8 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Tác giả id-tác-giả: int tên: string năm-sinh: int Bài hát id-bài-hát: int tên: string id-tác-giả: int năm-sáng-tác: int id-thể-loại: int Thể loại id-thể-loại: int tên: string Ca sĩ id-ca-sĩ: int tên: string năm-sinh: int Biểu diễn id-biểu-diễn: int id-ca-sĩ: int id-bài-hát: int Đĩa nhạc id-đĩa-nhạc: int tên: string năm-phát-hành: int Chứa id-đĩa-nhạc: int id-biểu-diễn: int số-thứ-tự: int thời-gian: time Biến thực thể  quan hệ  Customer(cid, name, address, phone) 9 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Customer cid: int name: string address: string phone: string Thực thể yếu  Book(bid, name, author, publisher, pub_date) Chapter(ch_num, bid, title) 10 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Book id: int name: string author: string publisher: string Chapter ch_num: int bid: int title: string pub_date: date Quan hệ 1-n  Book(bid, name, author_id, publisher, pub_date) Author(aid, name) 11 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Book bid: int name: string author_id: int publisher: string Author aid: int name: string pub_date: date Quan hệ n-n  Sinh ra một quan hệ phụ  Student(sid, name, birthday) Class(cid, name, room, teacher) Registration(sid, cid) 12 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Stud nt id: int name: string birthday: date Class cid: int name: string room: string teacher: string Registration sid: int cid: int Ngôn ngữ truy vấn (query language)  Để thao tác trên các quan hệ, chúng ta cần đến ngôn ngữ truy vấn  Ngôn ngữ truy vấn thường là ngôn ngữ cấp cao hơn so với các ngôn ngữ lập trình  VD: SQL  Trong phần tiếp theo, chúng ta tìm hiểu về ngôn ngữ truy vấn ở dạng lý thuyết hình thức 13 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Đại số quan hệ (Relational algebra) 14 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Khái niệm  Đại số quan hệ là một ngôn ngữ truy vấn dạng thủ tục (procedural query language), là một tập hợp các phép toán:  Có một hoặc hai đầu vào là các quan hệ  Đầu ra (kết quả) là một quan hệ mới  Các phép toán cơ bản: select (chọn), project (chiếu), union (hợp), set-diffrence (trừ), Cartesian-product (tích Đề-các) và rename (đổi tên)  Một số phép toán khác: set-intersection (giao), natural-join (gộp), division (chia), assignment (gán)  Được định nghĩa dựa vào các phép toán cơ bản 15 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Select (phép chọn) σ  Phép select nhận đầu vào là một quan hệ, và cho phép lựa chọn những bộ giá trị trong quan hệ đó thoả mãn một điều kiện (vị ngữ)  Ký hiệu: σvị ngữ(r)  VD:  σnăm-sinh <= 1950(tác-giả)  σsản-phẩm = “máy tính”(hoá-đơn) 16 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội id sản phẩm tiền … 1 máy tính 20 … 3 điện thoại 10 … 4 máy tính 22 … 7 tivi 5 … 10 tủ lạnh 8 … 11 máy tính 13 … id sản phẩm tiền … 1 máy tính 20 … 4 máy tính 22 … 11 máy tính 13 … σsản-phẩm = “máy tính”(hoá-đơn) Project (phép chiếu) Π  Phép project nhận đầu vào là một quan hệ, và cho phép chỉ giữ lại những thuộc tính mong muốn  Ký hiệu: Πcác thuộc tính giữ lại(r)  VD:  Πid, tên(tác-giả)  Πsản-phẩm, tiền(hoá-đơn) 17 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Πtitle, author(sách) id title author pub-year 1 The call of the wild Jack London 1903 3 The universe in a nutshell Stephen Hawking 2001 4 Hồng lâu mộng Tào Tuyết Cần 1791 title author The call of the wild Jack London The universe in a nutshell Stephen Hawking Hồng lâu mộng Tào Tuyết Cần Union (phép hợp) ∪  Phép union nhận đầu vào là hai quan hệ tương thích với nhau và kết quả là quan hệ bao gồm những bộ giá trị có mặt ở một trong hai quan hệ  Ký hiệu: r1 ∪ r2  VD:  thành-phố-Mỹ ∪ thành-phố-VN  sách-văn-học ∪ sách-lịch-sử 18 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội tên món giá phở 30 bún 25 cơm 40 tên món giá cafe 30 nước cam 25 coca 40 tên món giá phở 30 bún 25 cơm 40 cafe 30 nước cam 25 coca 40 đồ-ăn ∪ đồ-uống Set-difference (trừ) –  Phép set-difference nhận đầu vào là hai quan hệ tương thích với nhau, và trả về kết quả là những bộ giá trị trong quan hệ thứ nhất mà không có trong quan hệ thứ hai  Ký hiệu: r1 – r2  VD:  thực-đơn – đồ-ăn  máy-tính – laptop  điện-thoại – sản-phẩm-Apple 19 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội sản phẩm giá Xoom 15 Galaxy Tab 13 iPhone 20 Desire S 10 iPad 17 sản phẩm giá iPhone 20 Macbook 30 iPad 17 iPod 5 sản phẩm giá Xoom 15 Galaxy Tab 13 Desire S 10 điện-thoại – sản-phẩm-Apple Cartesian-product (tích Đề-các) ×  Phép Cartesian-product nhận đầu vào là hai quan hệ, và trả về kết quả là tập tất cả các bộ giá trị giữa chúng  Ký hiệu: r1 × r2  VD:  ca-sĩ × bài-hát  nhân-viên × chi-nhánh 20 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội id nhân viên tên 123 Lê Đức Thọ 427 Bùi Văn Hải id chi nhánh tên 2 Hà Nội 1 Sài Gòn 3 Đà Nẵng nhân-viên × chi-nhánh id nhân viên nhân- viên.tên id chi nhánh chi- nhánh.tên 123 Lê Đức Thọ 2 Hà Nội 123 Lê Đức Thọ 1 Sài Gòn 123 Lê Đức Thọ 3 Đà Nẵng 427 Bùi Văn Hải 2 Hà Nội 427 Bùi Văn Hải 1 Sài Gòn 427 Bùi Văn Hải 3 Đà Nẵng Để tránh trùng tên, dùng ký hiệu: tên-quan-hệ.tên-thuộc-tính Biểu thức quan hệ và phép rename (đổi tên)  Các phép toán quan hệ có thể được lồng nhau tạo thành biểu thức  VD:  Πtên, giá(σcalo <=100(món-ăn) ∪ σgiá < 30(đồ-uống))  Πtác-giả.tên, bài-hát.tên(σid-tác-giả = bài-hát.id-tác-giả(σtên=“Trịnh Công Sơn”(tác-giả) × bài-hát))  Kết quả các biểu thức quan hệ là các quan hệ không có tên, phép toán rename cho phép đặt tên cho kết quả một biểu thức  Ký hiệu: có 2 dạng  ρtên-quan-hệ(E) đặt tên cho quan hệ kết quả của biểu thức E  ρtên-quan-hệ(tên các thuộc tính)(E) đặt tên cho quan hệ và các thuộc tính kết quả của biểu thức E  VD:  ρđồ-uống-rẻ(σgiá < 30(đồ-uống))  ρnv-cn(tên-nhân-viên, tên-chi-nhánh)(Πnhân-viên.tên, chi-nhánh.tên (σnhân-viên.id-chi-nhánh = chi-nhánh.id(nhân-viên × chi-nhánh))) 21 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Set-intersection (giao) ∩  Phép set-intersection nhận đầu vào là hai quan hệ tương thích với nhau và kết quả là quan hệ bao gồm những bộ giá trị có mặt ở đồng thời trong hai quan hệ  Ký hiệu: r1 ∩ r2  VD:  món-ăn-Tàu ∩ món-ăn-VN  khách-mua-máy-tính ∩ khách-mua-điện-thoại  Phép set-intersection có thể được định nghĩa thông qua phép trừ: r1 ∩ r2 = r1 – (r1 – r2) 22 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Natural-join (gộp) ⋈  Trong việc khai thác CSDL, một câu hỏi rất hay gặp như sau: “Xuất ra danh sách các tác giả cùng với các bài hát được sáng tác”  sử dụng Cartesian- product và select:  σtác-giả.id-tác-giả = bài-hát.id-tác-giả(tác-giả × bài-hát)  Phép natural-join nhận hai quan hệ và thực hiện Cartesian-product giữa chúng, sau đó select những bộ giá trị dựa trên các thuộc tính chung và trả về tập kết quả  Ký hiệu: r1 ⋈ r2  VD:  tác-giả ⋈ bài-hát  hoá-đơn ⋈ sản-phẩm 23 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội id-sp sản phẩm giá 3 Xoom 15 6 Galaxy Tab 13 10 iPhone 20 id-hđ id-sp khách-hàng 333 3 Jobs 565 6 Obama 792 3 Bill 898 10 Paul ⋈ id-hđ id-sp khách-hàng sản phẩm giá 333 3 Jobs Xoom 15 565 6 Obama Galaxy Tab 13 792 3 Bill Xoom 15 898 6 Paul Galaxy Tab 13 Division (chia) ÷  Phép division dùng để giải quyết câu hỏi dạng: “Liệt kê các khách hàng đã đăng ký tất cả các dịch vụ của hãng”  Đáp án cảu câu hỏi này là kết quả của phép division: đăng-ký(id-khách, id-dịch-vụ) ÷ khách-hàng(id-khách)  Định nghĩa: Cho các quan hệ r(R) và s(S) với S ⊆ R. Kết quả của phép division r ÷ s là một quan hệ trên R – S, trong đó một phần tử t thuộc r ÷ s khi và chỉ khi:  t ∈ ΠR – S(r)  Với mọi ts ∈ S, có một tr ∈ R thoả mãn: ts[S] = tr[R] và tr[R – S] = t  Định nghĩa thông qua các phép toán cơ bản: r ÷ s = ΠR – S(r) – ΠR – S((ΠR – S(r) × s) – ΠR – S, S(r)) 24 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Assignment (gán) ←  Phép assignment dùng để gán kết quả của một biểu thức vào một biến (tương tự như trong các ngôn ngữ lập trình)  Ký hiệu: r1 ← r2  VD:  u ← ΠR – S(r) v = ΠR – S(u × s) – ΠR – S, S(r)) r ÷ s = u – v  Phép assignment chỉ giúp thu gọn và đơn giản hoá biểu thức 25 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Sửa đổi dữ liệu 26 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Giới thiệu  Đại số quan hệ chỉ giúp trích xuất thông tin từ CSDL. Phần này giúp tìm hiểu về việc thay đổi thông tin trong CSDL.  Các phép toán bao gồm:  Insert (thêm)  Delete (xoá)  Update (cập nhật)  View (tạo khung nhìn)  Việc thay đổi thông tin đều dựa vào phép assignment 27 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Insert (thêm)  Thêm dữ liệu mới vào một quan hệ được định nghĩa thông qua phép hợp: r ← r ∪ E trong đó r là quan hệ được thay đổi, E là quan hệ được thêm vào 28 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Delete (xoá)  Xoá dữ liệu mới từ một quan hệ được định nghĩa thông qua phép trừ: r ← r – E trong đó r là quan hệ được thay đổi, E là quan hệ được xoá bớt từ r 29 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Update (cập nhật)  Phép update được định nghĩa dựa trên phép chiếu: r ← Πf1,f2,...,fn(r) trong đó fi là thuộc tính thứ i của r nếu thuộc tính đó không muốn bị thay đổi, hoặc là giá trị cần cập nhật cho thuộc tính đó  Phép update sẽ cập nhật toàn bộ các hàng của r  Nếu chỉ muốn cập nhật một số hàng nhất định, dùng biểu thức như sau: r ← Πf1,f2,...,fn (σP(r)) ∪ (r − σP(r)) 30 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội View (tạo khung nhìn)  Trong thực thế làm việc với CSDL, vì lý do bảo mật hoặc để thuận tiện thao tác, một phần CSDL có thể được ẩn đi với những người dùng nhất định  Người dùng có thể không có thông tin tổng thể về sơ đồ của toàn bộ CSDL  VD:  một người dùng có thể chỉ biết danh sách nhân viên của công ty, mà không biết được lương của từng người. Ta có thể tạo một quan hệ như sau: view1 ← Πtên, tuổi(nhân-viên) và chỉ để người dùng thao tác với view1  Câu lệnh: create view v as E trong đó v là tên view được tạo ra, và E là biểu thức quan hệ  Phân biệt tạo view và phép gán: với phép gán, sau khi gán xong, nếu ta cập nhật các quan hệ trong biểu thức thì quan hệ được gán không thay đổi (còn với view thì có)  Chú ý: một view cũng là một quan hệ, nên có thể dùng view trong biểu thức để định nghĩa view khác 31 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội Bài tập Dùng mô hình quan hệ để biểu diễn các CSDL sau: 1. Giáo viên, sinh viên, khoá học, môn học, lớp học 2. Công ty, nhân viên, dự án, chi nhánh 3. Thư viện, người đọc, sách 4. Cửa hàng, khách hàng, hàng, nhà phân phối Dùng đại số quan hệ để thực hiện các yêu cầu sau: 5. Tìm các học sinh lớp C có điểm trung bình lớn hơn 5 6. Tìm mã và tên những người đã mượn cuốn sách “CSDL” 32 EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội