Tài liệu về môn Cơ sở dữ liệu

93 trang vanle 2210

Download

Bạn đang xem 20 trang mẫu của tài liệu "Tài liệu về môn Cơ sở dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

tai_lieu_ve_mon_co_so_du_lieu.doc

Nội dung text: Tài liệu về môn Cơ sở dữ liệu

Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học LỜI NÓI ĐẦU Ngày này cơ sở dữ liệu đã có nhiều ứng dụng trong mọi hoạt động của xã hội. Muốn thiết kế, sử dụng cơ sở dữ liệu chúng ta phải nắm được các kỹ thuật cơ bản của cơ sở dữ liệu. Tập bài giảng này nhằm trình bày các kỹ thuật cơ bản của cơ sở dữ liệu truyền thống, đó là mô hình thực thể liên kết, mô hình cơ sở dữ liệu quan hệ. Tập bài giảng cũng trình bày cách thiết kế một cơ sở dữ liệu quan hệ, cách sử dụng các phép toán đại số quan hệ, ngôn ngữ tân từ, ngôn ngữ hỏi có cấu trúc để tạo, cập nhật và truy vấn cơ sở dữ liệu. Khái niệm phụ thuộc hàm và ứng dụng của nó trong thiết kế và chuẩn hóa cơ sở dữ liệu quan hệ. Tập bài giảng là tài liệu chính thức của học phần nhập môn cơ sở dữ liệu cho sinh viên chuyên ngành sư phạm Toán – Tin. Tập bài giảng cũng là tài liệu tham khảo hữu ích cho giảng viên khi giảng dạy các học phần liên quan đến cơ sở dữ liệu Tập bài giảng gồm 5 chương, cuối mỗi chương có câu hỏi và bài tập giúp sinh viên rèn luyện các kiến thức học được trong chương đó. Chương 4 là chương sinh viên tự nghiên cứu để hiểu biết thêm về mô hình thực thể liên kết. Chúng tôi xin tiếp nhận và chân thành cảm ơn sự giúp đỡ, đóng góp ý kiến của các đồng nghiệp để tập bài giảng ngày càng hoàn thiện hơn. Nhóm tác giả 1
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học MỤC LỤC CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN VỀ CSDL 4 1. Các khái niệm về hệ cơ sở dữ liệu 4 1.1. Khái niệm cơ sở dữ liệu và hệ cơ sở dữ liệu 4 1.2. Kiến trúc CSDL 4 1.3. Lược đồ và thể hiện của CSDL 6 1.4. Tính độc lập dữ liệu 7 2. Tổ chức dữ liệu mức vật lý 7 2.1. Mô hình tổ chức bộ nhớ ngoài 7 2.2. Tệp băm (Hashed file) 8 2.3. Tệp chỉ số (indexed file) 9 2.4. Cây cân bằng (Balanced tree – B cây) 11 3. Ba mô hình dữ liệu cơ bản 13 3.1. Mô hình hóa trong tin học 13 3.2. Mô hình dữ liệu 13 3.3. Các mô hình dữ liệu cơ bản 13 Kết chương 16 Câu hỏi và bài tập 16 CHƯƠNG II: NGÔN NGỮ THAO TÁC DỮ LIỆU 18 1. Cơ sở dữ liệu quan hệ 18 1.1. Khái niệm cơ bản 18 1.2. Các thao tác cập nhật dữ liệu trên quan hệ 19 1.3. Đại số quan hệ 20 1.4. Ngôn ngữ tân từ: 30 2. Ngôn ngữ hỏi có cấu trúc – SQL (Structured Query Language) 31 2.1. Ngôn ngữ định nghĩa dữ liệu 32 2.2. Ngôn ngữ thao tác dữ liệu 35 Kết chương 41 Câu hỏi và bài tập 41 CHƯƠNG III: THIẾT KẾ MỘT CƠ SỞ DỮ LIỆU 46 1. Mục đích thiết kế CSDL 46 2. Phụ thuộc hàm (Function Defendency-FD) 48 2.1. Đặt vấn đề 48 2.2. Định nghĩa phụ thuộc hàm 48 2.3. Hệ tiên đề Amstrong 48 2.4. Các luật suy ra từ hệ tiên đề 49 2.5. Bao đóng của 1 tập phụ thuộc hàm 49 2.6. Bao đóng của 1 tập thuộc tính 50 2.7. Định nghĩa khoá và siêu khoá theo ngôn ngữ phụ thuộc hàm 52 2.8. Tập phụ thuộc hàm tối thiểu 55 3. Phép tách các lược đồ quan hệ 58 3.1. Khái niệm phép tách 58 3.2. Phép tách kết nối không tổn thất 59 4. Chuẩn hoá lược đồ quan hệ 62 2
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 4.1. Các dạng chuẩn 62 4.2. Phép tách kết nối không tổn thất thành BCNF 64 4.3. Phép tách bảo toàn phụ thuộc hàm thành 3NF 67 Kết chương 68 Câu hỏi và bài tập 68 CHƯƠNG IV: MÔ HÌNH THỰC THỂ LIÊN KẾT (Entity Relationship Model) 72 1. Mô hình dữ liệu khái niệm bậc cao và quá trình thiết kế CSDL 72 2. Các thành phần cơ bản của mô hình thực thể liên kết: 73 2.1. Thực thể và thuộc tính 73 2.2. Kiểu thực thể, tập thực thể, khóa và tập giá trị 75 2.3. Kiểu liên kết, tập liên kết và các thể hiện 77 2.4. Cấp liên kết, tên vai trò và kiểu liên kết đệ quy 78 2.5 Các ràng buộc trên các kiểu liên kết 79 2.6. Thuộc tính của các kiểu liên kết 81 2.7. Các kiểu thực thể yếu 81 3. Ví dụ về thiết kế mô hình ER 82 Xác định các kiểu thực thể, các thuộc tính và các kiểu liên kết 82 CHƯƠNG V: HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 86 1. Định nghĩa một hệ quản trị CSDL: 86 2. Các chức năng của một hệ quản trị cơ sở dữ liệu 86 3. Các đặc trưng của giải pháp cơ sở dữ liệu 88 4. Ví dụ về một cơ sở dữ liệu 90 3
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN VỀ CSDL 1. Các khái niệm về hệ cơ sở dữ liệu 1.1. Khái niệm cơ sở dữ liệu và hệ cơ sở dữ liệu - Một CSDL (Database) là một tập hợp các dữ liệu có liên quan với nhau chứa thông tin về một tổ chức nào đó (như 1 trường ĐH, 1 công ty, ngân hàng, ) được lưu trữ trên các thiết bị nhớ thứ cấp (như bằng từ, đĩa từ ) để đáp ứng nhu cầu khai thác thông tin của nhiều người sử dụng với nhiều mục đích khác nhau. - Hệ quản trị CSDL (Database Management System- DBMS) là phần mềm cho phép người dùng giao tiếp với CSDL, cung cấp một môi trường thuận lợi và hiệu quả để tìm kiếm và lưu trữ thông tin của CSDL - Hệ csdl: (Database System): Gồm phần cứng, CSDL, Hệ quản trị csdl, người quản trị. Mục đích chính của hệ CSDL là che dấu đi những chi tiết phức tạp về cách thức dữ liệu được lưu trữ và bảo trì - Ví dụ về sử dụng CSDL: Thông qua giao diện Web đăng ký một khoá học, tìm hiểu chi tiết một mặt hàng, tra điểm thi tuyển sinh 1.2. Kiến trúc CSDL Cơ sở dữ liệu có kiến trúc 3 mức: - Mức trong (mức vật lý): mô tả dữ liệu thực sự được lưu trữ như thế nào trong CSDL. Đây là mức thể hiện các cài đặt có tính chất vật lý của CSDL để đạt hiệu quả tối ưu trong thao tác tìm kiếm và lưu trữ, để tận dụng được các vùng nhớ còn trống. Mức vật lý cũng phản ánh các cấu trúc dữ liệu, các tổ chức tệp được dùng cho việc lưu trữ dữ liệu trên các thiết bị nhớ thứ cấp. - Mức khái niệm (mức logic): mô tả những dữ liệu nào được lưu trữ trong CSDL và có mối quan hệ nào giữa chúng. Nói một cách cụ thể hơn, mức logic biểu diễn các thực thể, các thuộc tính và các mối quan hệ giữa các thực thể đó, mức logic cũng cho thấy các ràng buộc trên dữ liệu, các thông tin về ngữ nghĩa của dữ liệu, các thông tin về an ninh và toàn vẹn dữ liệu. 4
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Tuy nhiên mức này chỉ quan tâm đến cái gì được lưu trữ trong CSDL chứ không quan tâm đến cách thức để lưu trữ. - Mức ngoài (mức khung nhìn): Mô tả chỉ 1 phần của CSDL, phần thích hợp với một người sử dụng nhất định. Mỗi người sử dụng có thể không quan tâm đến toàn bộ thông tin của hệ CSDl mà chỉ cần một phần thông tin nào đó. Khung nhìn dành cho người sử dụng đó chỉ gồm những thực thể và những thuộc tính, những mối quan hệ giữa những thực thể mà họ quan tâm. Các khung nhìn khác nhau có thể cùng trình bày về một dữ liệu nhưng khuôn dạng khác nhau, ví dụ ngày tháng năm sinh có thể ở khung nhìn này là kiểu dd/mm/yyyy, khung nhìn khác là mm/dd/yy, một số khung nhìn có thể chứa các dữ liệu được suy dẫn hoặc tính toán chứ không chứa thật sự trong CSDL. Ví dụ như tính điểm trung bình cuối kỳ của sinh viên hoặc tính thành tiền của một đơn hàng không cần lưu trong CSDL. Khung nhìn 1 Khung nhìn 2 Khung nhìn n Mức ngoài Lược đồ khái niệm Mức khái niệm Mức trong Lược đồ vật lý Hình 1.1 Kiến trúc CSDL Mục đích của kiến trúc 3 mức là sự cách ly quan niệm về CSDL của nhiều người sử dụng với chi tiết về biểu diễn vật lý của nó. Điều đó dẫn đến thuận lợi sau: - Đối với 1 CSDL, mỗi người dùng có một khung nhìn riêng. Họ có thể thay đổi khung nhìn của mình mà không làm ảnh hưởng đến khung nhìn của người khác dùng chung CSDL này. - Những tương tác của người dùng CSDL không phụ thuộc vào những vấn đề chi tiết trong lưu trữ dữ liệu. - Người quản trị CSDL (Database Administrator-DBA) có thể thay đổi cấu trúc lưu trữ CSDL mà không làm ảnh hưởng đến khung nhìn của người sử dụng. 5
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Những thay đổi về khía cạnh vật lý trong lưu trữ, chẳng hạn thay đổi thiết bị nhớ khác cũng không làm ảnh hưởng đến cấu trúc bên trong của CSDL. - Người quản trị CSDL có thể thay đổi cấu trúc tổng thể hay cấu trúc khái niệm của CSDL mà không ảnh hưởng đến tất cả người dùng. 1.3. Lược đồ và thể hiện của CSDL  Toàn bộ mô tả CSDL được gọi là lược đồ CSDL (Database schema). Tương ứng với 3 mức kiến trúc trên có 3 loại lược đồ dữ liệu: Lược đồ ngoài, lược đồ khái niệm và lược đồ trong  Phân biệt bản thân CSDL và lược đồ CSDL. Lược đồ xác định trong quá trình thiết kế và người ta không muốn nó thay đổi thường xuyên. Trong khi đó bản thân CSDL lại thay đổi thường xuyên theo thời gian  Toàn bộ dữ liệu tại một thời điểm xác định gọi là thể hiện của CSDL (Database instance). Như vậy nhiều thể hiện của CSDL có thể cùng tương ứng với một lược đồ CSDL  Ví dụ: Khung nhìn 1 Khung nhìn 2 MaSV HoTen Ngaysinh quequan MaSV hocky MaMon diem Mức MaSV HoTen Ngaysinh quequan hocky MaMon diem logic Hình 1.2. Ví dụ lược đồ và thể hiện của CSDL Mức vật lý Struc SINHVIEN{ Int MaSV; Char hoten[25] Struc date ngaysinh Int hocky Int mamon Float diem Struc SINHVIEN next /* trỏ đến bản ghi tiếp của tệp nhân viên*/ }; 6
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 1.4. Tính độc lập dữ liệu  Là tính bất biến giữa các hệ ứng dụng đối với các thay đổi trong cấu trúc lưu trữ và chiến lược truy cập.  Có 2 mức độc lập dữ liệu: Độc lập vật lý và độc lập logic - Độc lập dữ liệu vật lý: Việc thay đổi trong tổ chức CSDL mức vật lý có thể làm ảnh hưởng đến hiệu quả của hệ ứng dụng nhưng không đòi hỏi viết lại chương trình. Ví dụ như sử dụng các tệp khác trước, dùng thiết bị nhớ khác, thay đổi chỉ mục hay thay đổi thuật toán băm. - Độc lập dữ liệu logic: Khi sử dụng CSDL có thể thay đổi lược đồ khái niệm mà không làm thay đổi các khung nhìn (lược đồ ngoài) cũng không cần thay đổi chương trình. Ví dụ thêm bớt các thực thể, các thuộc tính hay mối quan hệ giữa chúng. Tất nhiên những người dùng có chạm đến các thông tin đã thay đổi này sẽ được thông báo về sự thay đổi, nhưng điều quan trọng là những người dùng khác không ảnh hưởng gì. 2. Tổ chức dữ liệu mức vật lý 2.1. Mô hình tổ chức bộ nhớ ngoài - Bộ nhớ ngoài: Băng từ, đĩa từ - Cách lưu trữ trên đĩa từ: Đĩa từ được chia thành các khối vật lý (physical block) có kích cỡ như nhau. Mỗi khối chiếm khoảng 512 -> 4096 byte và được đánh địa chỉ khối. Một tệp (file) chiếm 1 hoặc nhiều khối. 1 khối chứa 1 hay nhiều bản ghi (record), 1 bản ghi chứa nhiều trường (field). Thông thường một bản ghi tương ứng với một thực thể, một trường tương ứng với một thuộc tính. Thao tác với tệp dữ liệu thông qua địa chỉ khối. - Địa chỉ của các bản ghi là địa chỉ của byte đầu tiên của bản ghi đó hoặc địa chỉ khối chứa bản ghi đó. - Con trỏ (Pointer) là chỉ dẫn tới địa chỉ của bản ghi hoặc các khối thường được lưu ở 1 tệp hay vị trí nào đó để khi cần qua đó truy cập tới dữ liệu cần thiết 7
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 2.2. Tệp băm (Hashed file) - Hàm băm: Nếu mỗi bản ghi có 1 khoá là x thì hàm băm H(x) nhận 1 giá trị nguyên dương nào đó. Vì thế tệp băm còn gọi là tệp ngẫu nhiên. Hàm băm được chọn sao cho các bản ghi được phân bố đều trong tệp. Có một kỹ thuật được gọi là gấp lại (Folding), nó áp dụng một hàm số học, chẳng hạn phép cộng vào các phần khác nhau của khóa. Kết quả có được từ phép cộng đó được lấy làm địa chỉ của khối chứa bản ghi nói trên. Có một kỹ thuật thông dụng hơn được gọi là chia dư (division – remainder). Kỹ thuật chia dư sử dụng hàm MOD, giá trị của khóa được chia cho một số nguyên định trước và số dư trong phép chia đó được sử dụng làm địa chỉ của khối chứa bản ghi. Khi địa chỉ được sinh ra cho 2 hay nhiều bản ghi , các bản ghi được gọi là các đồng nghĩa. Khi một bản ghi mà khối cho bản ghi đó đã đầy thì ta nói rằng xuất hiện các xung đột (collision). - Tệp băm phân chia tập hợp các bản ghi của tệp dữ liệu thành các cụm (Buckets). Mỗi cụm gồm 1 hoặc nhiều khối (block). Mỗi khối chứa 1 số lượng cố định các bản ghi. - Mỗi cụm ứng với 1 địa chỉ băm. Địa chỉ băm được đánh số từ 0 đến k-1. Ở đầu mỗi khối đều chứa con trỏ tới khối tiếp theo trong cụm. Khối cuối cùng trong cụm chứa con trỏ rỗng. - Có 1 bảng chỉ dẫn cụm (buckets directory) chứa k con trỏ. Mỗi con trỏ ứng với 1 cụm, đó là địa chỉ của khối đầu tiên trong cụm - Nếu bảng chỉ dẫn có kích thước nhỏ có thể được lưu trữ trong bộ nhớ trong, ngược lại được để ở bộ nhớ ngoài 0 * Null 1 * Null k-1 * Null Hình 1.3. Tổ chức tệp băm 8
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Tìm kiếm bản ghi Giả sử cần tìm bản ghi có khoá x. Trước hết tính hàm băm H(x), giả sử H(x) =i, i sẽ là địa chỉ băm của cụm i. Trong bảng chỉ dẫn cụm cho biết con trỏ đến khối đầu tiên (nếu có). Tìm trong khối này xem liệu có bản ghi có khoá x hay không. Theo con trỏ ở đầu khối, tìm tới các khối tiếp theo cho tới khi tìm được bản ghi hoặc tới cuối cùng của cụm i mà không có bản ghi đó. Thêm 1 bản ghi Thêm bản ghi có khoá x vào tệp. Thực hiện thủ tục như tìm kiếm. Nếu tìm thấy bản ghi có khoá x thì bản ghi mới là sai (vì khoá không được trùng nhau). Nếu không có bản ghi trùng, bản ghi có khoá x được thêm vào khối đầu tiên trong cụm còn chỗ trống. Nếu không còn chỗ trống nào trong mọi khối của cụm, thì phải tạo thêm khối mới, con trỏ null của khối cuối cùng được trỏ sang khối mới này. Lúc này bản ghi mới là bản ghi đầu tiên của khối và khối này trở thành khối cuối cùng. Xoá 1 bản ghi Để xóa bản ghi có khoá x, sử dụng thủ tục tìm bản ghi có khoá x. Nếu bản ghi thuộc một khối nào đó có nhiều bản ghi thì bản ghi đó được xoá, nếu bản ghi đó là duy nhất trong khối, thì sẽ xoá đồng thời khối đó khỏi cụm. Sửa 1 bản ghi Cần sửa một số trường của bản ghi có khoá x. Nếu có sửa trường tham gia trong khoá, việc sửa chữa sẽ là loại bỏ bản ghi này và thêm vào một bản ghi mới cho tệp. Nếu trường cần sửa không thuộc khoá thì tiến hành sửa bình thường, nếu bản ghi không tồn tại xem như có lỗi. 2.3. Tệp chỉ số (indexed file) Quy ước: Tệp dữ liệu được sắp xếp theo khoá, khoá bao gồm các trường có thứ tự và chiều dài cố định. Tệp chỉ số được tạo theo khoá, bao gồm các cặp (k, d) trong đó k là giá trị của khoá, d là địa chỉ của khối. Các cặp này được sắp xếp theo giá trị của khoá 9
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học (k1,d1) (k1,d1) * k1 k2 (k2,d2) (k2,d2) * * * * kn (kn,dn) (kn,dn) Null Bảng chỉ số khối Tệp chỉ số Tệp dữ liệu chính Hình 1.4. Tệp chỉ số Tìm kiếm bản ghi Giả sử tìm bản ghi có khoá x, có nhiều cách để duyệt tệp chỉ số Tìm tuần tự Duyệt trong tệp chỉ số các cặp (k,d) trong bảng chỉ số khối, so sánh giá trị x với k, gặp cặp đầu tiên (k’,d’) có k’>x thì dừng. Như vậy giá trị x có thể ở trong khối ngang với khối trước đó. Trong khối này ta tìm tuần tự cho tới khi gặp k=x thì d tương ứng là bản ghi cần tìm. Nếu không có giá trị k nào trong khối đang xét bằng x, xem như x không tồn tại. Tìm kiếm nhị phân Phương pháp tìm kiếm tuần tự thường là chậm, thường có thể sử dụng phương pháp khác nhau như phương pháp tìm kiếm nhị phân vì tệp chỉ số bao giờ cũng được sắp xếp. Giả sử tệp chỉ số được lưu trên n khối (b1 b1). Để tìm một bản ghi có khoá x, trước hết chọn khối b[n/2]. So sánh giá trị k thuộc khối b[n/2] và x, nếu k>x thì bộ cần tìm nằm trong các khối từ b 1 b[n/2], ngược lại thì nằm trong các khối b[n/2+1] bn. Quá trình lặp lại cho đến khi chỉ còn một khối chứa bản ghi có khoá x. Trong khối này tiếp tục tuần tự trong các cặp (k,d) như phương pháp tìm tuần tự. Thêm bản ghi Thực hiện thao tác tìm bản ghi để xác định khối sẽ chứa bản ghi mới Nếu trong khối còn chỗ trống thì thêm bản ghi này vào khối theo thứ tự sắp xếp của khoá. Việc đặt đúng vị trí này đòi hỏi phải chuyển chỗ các bản ghi đứng sau bản ghi có khoá x. Nếu bản ghi có khoá x là bản ghi đầu tiên của khối thì phải 10
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học sửa khoá k = x trong bảng chỉ dẫn khối. Nếu khối bị hết chỗ thì bản ghi cuối cùng của khối này phải đẩy xuống khối tiếp theo để dành chỗ của nó cho bản ghi có khoá x. Khi đó phải sửa lại giá trị (k,d). Nếu bản ghi có khoá x là bản ghi cuối cùng, tức là x lớn hơn mọi khoá k trong tệp chỉ dẫn và mọi khối đều hết chỗ, khi đó thiết lập một khối mới, bản ghi này là bản ghi đầu tiên của khối mới thành lập. Xoá bản ghi Quá trình giống như thêm 1 bản ghi. Lưu ý nếu bản ghi có khoá x là bản ghi duy nhất của khối thì, xoá cả khối đó. Sửa bản ghi Dùng thủ tục tìm bản ghi để tìm bản ghi cần sửa + Nếu các trường cần sửa không phải là khoá thì việc sửa tiến hành bình thường, giá trị của bản ghi sau khi sửa được ghi lại vị trí cũ. + Nếu giá trị của trường cần sửa tham gia trong khoá. Quá trình sửa sẽ là thêm vào và xoá 1 bản ghi. Chú ý: Tệp chỉ số có thể được cấu trúc một cách đơn giản hơn rất nhiều. Tệp này chỉ gồm 2 trường, khoá k và con trỏ d. Mỗi bản ghi của tệp chỉ số tương ứng với một bản ghi của tệp chính. Khoá k là giá trị khoá của bản ghi chính, con trỏ d là địa chỉ của bản ghi trong tệp chính. Trong trường hợp này, tệp dữ liệu chính không nhất thiết phải được sắp xếp. 2.4. Cây cân bằng (Balanced tree – B cây) - B- cây cân bằng được tổ chức theo cấp m, có các tính chất sau đây: o Gốc của cây hoặc là 1 nút lá hoặc là có ít nhất 2 con o Mỗi nút (trừ nút gốc và nút là) có từ [m/2] đến m con oMỗi đường đi từ gốc đến bất kỳ lá nào đều có độ dài như nhau - Cách tổ chức dữ liệu: o Mỗi nút trên cây cân bằng có dạng (P 0,k1,P1, kn.Pn). Với Pi là con trỏ trỏ tới khối i mà ki là khoá đầu 1≤k≤n o Các khoá trong 1 nút được sắp xếp tăng dần o Mọi khóa trong cây con trỏ bới con trỏ P 0 đều nhỏ hơn k 1. Mọi khoá trong cây con trỏ bởi Pn đều > Kn o Các nút lá chỉ chứa khoá của bản ghi trong tệp (nút lá trỏ bởi P i chứa khoá cả khoá ki 11
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học ▪ ▪ ▪ ▪ ▪ 12 ▪ 15 ▪ ▪ ▪ ▪ ▪ ▪ 1 2 3 12 13 14 Hình 1.5. Biểu diễn cây cân bằng. Tìm kiếm bản ghi Giả sử cần tìm bản ghi có khoá x. Trước hết cần xác định đường đi từ nút gốc đến nút là có thể chứa bản ghi này. Muốn vậy liên tiếp duyệt các nút của B-cây kể từ nút gốc. Tại mỗi nút sẽ xác định con trỏ đi tới nút tiếp theo. Thủ tục: So sánh khoá x với các khoá k 1, kn tại nút đang xét. Nếu k i≤x<ki+1 sẽ chọn con trỏ p i để duyệt tiếp nút con trỏ từ p i tới. Quá trình duyệt tiếp tục như trên. Nếu x<k1 thì có khả năng tìm x trong nút trỏ p0, Nếu x ≥ kn thì tìm theo nút trỏ từ pn. Cuối cùng sẽ tới 1 nút lá. Trong nút lá tìm tuần tự cho đến khi tìm thấy hoặc bản ghi không tồn tại. Bổ xung bản ghi Giả sử cần bổ xung bản ghi có khoá x vào B-cây. Trước hết cần xác định vị trí nút lá sẽ chứa bản ghi đó. Dùng thủ tục tìm kiếm bản ghi. Giả sử nút là tìm được là L. Nếu nút lá L còn chỗ trống, việc thêm bản ghi mới vào đúng thứ tự cuả khoá. Nếu nút L hết chỗ trống, tạo nút lá mới L’, chuyển nửa dữ liệu cuối của L’ rồi bổ xunh bản ghi có khoá x vào vị trí tương ứng trong L hoặc trong L’ Giả sử nút L-1 là nút ngay trên nút L, Khi đó phải thêm cặp (p’,k’) vào L-1, trong đó p’ là con trỏ tới lá L’ và k’ là khoá bé nhất chứa trong L’. Nếu L-1 đã đủ m con trỏ rồi, việc bổ xung (p’, k’) vào L-1 dẫn đến việc nút L-1 phải tách là 2 như làm với nút L. Quá trình này có thể truyền ứng đến tận gốc theo đường đi đã chọn. Loại bỏ bản ghi Dùng thủ tục tìm kiếm bản ghi để tìm bản ghi cần xoá . Nếu bản ghi cần xoá là bản ghi đầu tiên của nút L thì phải tìm tới nút P ngay trên nút L để chỉnh lại giá trị khoá đầu tiên của L có trước đó. 12
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Nếu L lại là nút con đầu tiên của P thì khoá đầu tiên của L không đặt được ở P, khi đó không cần thiết chỉnh sửa nữa. Tuy nhiên có thể khoá đầu tiên đó lại xuất hiện ở một nút trên đó. Do vậy việc tìm và chỉnh lý khoá này vẫn tiếp tục ngược lên cho tới tận gốc như đường đi đã vạch ra khi dùng thủ tục tìm kiếm Nếu sau khi loại bỏ bản ghi có khoá x khỏi nút L thì nút L thành nút rỗng, khi đó cần chỉnh lý lại cặp (k,p) ứng với L trong nút trên là p để mô tả sự thay đổi xảy ra. Việc thay đổi này có thể làm nút P có ít hơn [m/2] cặp (k,p), khi đó xem xét nút đó có hơn [m/2+1] cặp (k,p). ngược lại nếu nút bên trái hoặc phải có đúng [m/2] khi đó ghép p và p’ thành 1 nút mới, quá trình truyền ứng lên đến gốc của cây. 3. Ba mô hình dữ liệu cơ bản 3.1. Mô hình hóa trong tin học Là sự xác lập tương quan giữa các đặc trưng, các tính chất của đối tượng trong thế giới thực với các phần tử của 1 tập hợp cho trước sao cho các thông tin của các phần tử này luôn phù hợp với sự vận động và biến đổi của đối tượng được mô tả. 3.2. Mô hình dữ liệu: Mô hình dữ liệu là một tập hợp các khái niệm và các ký pháp dùng để mô tả dữ liệu, các mối quan hệ của dữ liệu, các ràng buộc trên dữ liệu của một tổ chức. Mô hình dữ liệu gồm 3 thành phần: - Phần mô tả cấu trúc của CSDL - Phần mô tả các thao tác, định nghĩa các phép toán được phép trên dữ liệu - Phần mô tả các ràng buộc toàn vẹn để đảm bảo sự chính xác của dữ liệu. 3.3. Các mô hình dữ liệu cơ bản Có 3 nhóm cơ bản: Mô hình logic trên cơ sở đối tượng, mô hình logic trên cơ sở bản ghi và mô hình vật lý 3.3.1. Mô hình logic trên cơ sở đối tượng (Object-based Data Models): Có 2 loại mô hình thường được nhắc đến là mô hình thực thể mối quan hệ và mô hình đối tượng. 3.3.1.1 Mô hình thực thể mối quan hệ (mô hình E-R): 13
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Mô hình này được xây dựng trên nhận thức là thế giới thực mà chúng ta muốn phản ánh là một tập hợp các đối tượng cơ sở và các mối quan hệ (liên kết) giữa chúng. - Thực thể (Entity): Là đối tượng có thực hay trừu tượng mà ta muốn ghi chép thông tin của nó - Mối quan hệ (Relationship): Là liên kết giữa các thực thể phản ánh sự ràng buộc về mặt quản lý. - Kiểu liên kết: Có 3 kiểu: o Liên kết 1-1: A –B o Liên kết 1-n: A B o Liên kết n-n : A B Thông thường liên kết 1-1 được đưa về cùng một thực thể, liên kết n-n được tách thành 2 liên kết 1-n, bằng cách thêm 1 thực thể C B, C A Cấu trúc tổng thể của một CSDL có thể được biểu thị bởi một biểu đồ E- R, được thành lập từ các thành phần sau: Hình chữ nhật biểu diễn các tập thực thể Hình ellip biểu diễn các thuộc tính Hình thoi biểu diễn các quan hệ Các đường nối các thuộc tính với tập các thực thể và các tập thực thể với mối quan hệ. Ví dụ 1: người gửi Khách hàng Tài khoản Tên khách hàng Địa chỉ Số dư Số tài khoản Số chứng minh thư Hình 1.6 Ví dụ mô hình E-R Ví dụ 2: Cho 2 thực thể độc giả và sách, quan hệ là người mượn Với thực thể độc giả có các thuộc tính: Mã thẻ độc giả, Tên độc giả, Địa chỉ 14
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Với thực thể Sách có các thuộc tính Mã sách, tên sách, tác giả, năm xuất bản, nhà xuất bản. Hãy vẽ biểu đồ E- R cho mô hình trên. 3.3.1.2 Mô hình hướng đối tượng: Dựa trên cơ sở tập các đối tượng. Mỗi đối tượng chứa các thuộc tính (Property) được lưu trữ qua các biến thể hiện (Instance variables) ở bên trong đối tượng. Một đối tượng chứa phần mã thao tác trên đối tượng gọi là phương thức (method). VD: Đối tượng tài khoản ngân hàng chứa biến thể hiện là số hiệu tài khoản và số dư. Nó chứa 1 phương thức là trả lãi 3.3.2. Mô hình logic trên cơ sở bản ghi. Có 3 loại: - Mô hình quan hệ (Relation Data model): Sử dụng các khái niệm về quan hệ: lược đồ quan hệ, thuộc tính (cột), bộ (hàng). Trong mô hình quan hệ, dữ liệu được biểu diễn dưới 1 dạng duy nhất là các quan hệ (bảng) gồm các thuộc tính (cột) và các bộ (hàng). Mối liên kết giữa các quan hệ có 3 loại liên kết như mô hình thực thể Lop sinhvien, xác định một lớp có nhiều sinh viên. Đặc điểm của mô hình quan hệ: + Có sơ sở chặt chẽ cho phép áp dụng rộng rãi các công cụ đại số và logic. + Khá tự nhiên, gần gũi với quan niệm thông thường của người sử dụng. + Ngôn ngữ rõ ràng, dễ học dễ hiểu, dễ cập nhật tới các đơn vị dữ liệu + Dễ đảm bảo tính độc lập dữ liệu. VD: bảng SINHVIÊN MA Ho_Ten Ngay_Sinh Dia_Chi Ma_Nganh SV K1301 Nguyễn An 10/10/91 Hoa Lư TT K1302 Trần Cường 5/9/90 Hoa Lư LK K1303 Lê Lan 15/3/89 Kim Sơn VS - Mô hình phân cấp (Hierarchical data model) Trong mô hình phân cấp, dữ liệu được biểu diễn theo dạng cây. Mỗi đối tượng của cơ sở dữ liệu được thể hiện như một nút của cây và các liên kết được thể hiện như các cung. 15
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học ĐH Hoa lư Khoa tự nhiên Khoa Kt & CN Khoa xã hội T12A T12B T13A T13B T13C DH Văn Hình 1.7 Ví dụ mô hình phân cấp - Mô hình mạng (Network data model): Là trường hợp đặc biệt của mô hình phân cấp. Trong đó CSDL được biểu diễn dưới dạng một đồ thị, các đối tượng là các nút, các cung là các liên kết. 3.3.3. Mô hình vật lý Mô tả dữ liệu ở mức thấp nhất, nghĩa là mô tả dữ liệu được lưu trữ như thế nào trong máy tính, mô tả các cấu trúc bản ghi, thứ tự các bản ghi và con đường truy cập. Mô hình vật lý có 2 loại cơ bản: mô hình thống nhất và mô hình khung - bộ nhớ. (không nghiên cứu trong nội dung giáo trình) Kết chương Chương này đã trình bày các khái niệm cơ bản nhất về cơ sở dữ liệu. Trình bày về tổ chức dữ liệu mức vật lý với ba phương pháp tổ chức cụ thể và giới thiệu các mô hình dữ liệu cơ bản Câu hỏi và bài tập Câu 1: Nêu khái niệm CSDL, hệ quản trị cơ sở dữ liệu, hệ cơ sở dữ liệu? Câu 2: Mục đích của kiến trúc 3 mức trong CSDL? Nêu rõ từng mức kiến trúc đó? Câu 3: Phân biệt độc lập dữ liệu mức vật lý và độc lập dữ liệu mức logic Câu 4: Nêu cách tổ chức dữ liệu dạng tệp băm. Các thao tác với bản ghi trong mô hình này? Câu 5: Nêu cách tổ chức dữ liệu dạng tệp chỉ số. Các thao tác với bản ghi trong mô hình này? 16
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Câu 6: Nêu cách tổ chức dữ liệu dạng cây cân bằng. Các thao tác với bản ghi trong mô hình này? Câu 7: Nêu các loại mô hình dữ liệu mà Anh (Chị) biết? 17
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG II: NGÔN NGỮ THAO TÁC DỮ LIỆU 1. Cơ sở dữ liệu quan hệ 1.1. Khái niệm cơ bản - Mô hình quan hệ: là các dữ liệu của bài toán quản lý được tổ chức dưới dạng các bảng dữ liệu. Bảng được tổ chức theo hàng, cột. - Thuộc tính: là một đặc trưng của đối tượng được mô tả. - Lược đồ quan hệ: Bao gồm tên lược đồ và tập các thuộc tính. ký hiệu: R(U), R(A1,A2, An) - Khái niệm miền trị: Cho tập thuộc tính U có n thuộc tính, lược đồ quan hệ R(U)= R(A1,A2, Rn), mỗi thuộc tính Ai có một miền giá trị ký hiệu là Dom(Ai) - Quan hệ (r) trên tập thuộc tính R là một tập con của tích đề_các các miền giá trị Dom(Ai). Như vậy mỗi phần tử của quan hệ r là một bộ t=(t 1,t2 tn) trong đó ti Dom(Ai) - VD1:Cho quan hệ r1={SBD,HoDem, Ten, NgaySinh, QueQuan} Dom(SBD)={C2701, C2702,C2703 } ký hiệu gồm chữ và số Dom(HoDem)={Nguyễn Thị, Nguyễn Văn, Phạm Thị } tập hợp họ đệm của người VN Dom(Ten)={Lan, Hoa, Mai } tập hợp tên của người VN Dom(NgaySinh }={ngày/tháng/năm} Dom(QueQuan)={Hoa Lư, Gia viễn } tập hợp tên các huyện thị t=(C2734, Nguyễn Thị, Lan, 16/5/1988, Hoa Lư, 7, 9, 6) - VD2: Cho quan hệ r2={SBD, Đmôn1, Đmôn2, Đmôn3} Dom (Đmôn1)={0->10} - Khoá: Là một tập con các thuộc tính, khoá đảm bảo rằng không có cặp bộ nào trong quan hệ hoàn toàn giống nhau. Trong VD1 thì SBD là khoá. - Khoá kết nối: Là một loại khoá dùng để kết nối 2 quan hệ. Chẳng hạn ở 2 VD trên để liên kết 2 quan hệ r1 và r2 thì khoá kết nối là SBD. 18
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 1.2. Các thao tác cập nhật dữ liệu trên quan hệ Có 3 phép cơ bản trên một quan hệ: phép chèn, phép xoá và phép sửa đổi. Giả sử ta có quan hệ r trên tập các thuộc tính {A1, A2, A3, ,An} khoá của quan hệ là thuộc tính Ak. - Phép chèn: Phép này bổ xung thêm 1 bộ vào một quan hệ. Ký hiệu Insert(r;A1=a1,A2=a2, .An=an). Nếu coi thứ tự các thuộc tính là cố định thì có thể viết Insert (r; a1, a2, an). - VD cho quan hệ: r MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK K1303 Lê Lan Ninh 15/3/89 Kim Sơn VS Phép chèn: Insert(r; “K1304”; “Nguyễn Hoàng”, “Oanh”, “12/7/88”, “Gia Viễn”, “TT”) lúc đó quan hệ trở thành MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK K1303 Lê Lan Ninh 15/3/89 Kim Sơn VS K1304 Nguyễn Hoàng Oanh 12/7/88 Gia Viễn TT Lưu ý: Khi chèn thêm bộ, khóa của bộ mới thêm không được trùng với bất cứ khóa nào đã có trong quan hệ - Phép xoá: Xoá đi một bộ đã có trong quan hệ r, ký hiệu Delete (r; A 1=a1, A2=a2, , An=an) hoặc Delete (r; a1, a2, , an) hoặc thuộc tính khoá là Ak thì Delete (r; Ak=ak). - VD với quan hệ r trên, Delete (r; K1302) thì quan hệ r biến đối thành MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Lê Lan Anh 10/10/91 Hoa Lư TT K1303 Nguyễn An Ninh 15/3/89 Kim Sơn VS K1304 Nguyễn Hoàng Oanh 12/7/88 Gia Viễn TT - Phép sửa đổi: cho phép thay đổi giá trị của một thuộc tính, ký hiệu Update (r; A1=a1, A2=a2, .An=an). hoặc có thể viết Update (r; Ak=ak,Ai=ei) Vd: cần sửa mã ngành của sinh viên Lê Lan Anh thành LK 19
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Update( r; Mã SV=K1301, Mã ngành = LK) MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Lê Lan Anh 10/10/91 Hoa Lư LK K1303 Nguyễn An Ninh 15/3/89 Kim Sơn VS K1304 Nguyễn Hoàng Oanh 12/7/88 Gia Viễn TT 1.3. Đại số quan hệ 1.3.1 Các phép toán tập hợp - Hai quan hệ khả hợp là 2 quan hệ có cùng bậc (Có số thuộc tính bằng nhau và thuộc tính thứ i của quan hệ này có cùng miền trị với thuộc tính thứ i của quan hệ kia. - Phép hợp (Union): Cho 2 quan hệ khả hợp r(U) và s(U). Hợp của 2 quan hệ r và s cho ta một quan hệ với tập thuộc tính U và các bộ là các bộ thuộc ít nhất 1 trong 2 quan hệ r hoặc s r  s= {t | t r hoặc t s} Ví dụ cho 2 quan hệ r và s như sau: SBD HoTen SBD HoTen K1301 Lê Lan K1305 Thi Hồng K1302 Trần Lê K1304 Mai Ca K1303 Nguyễn An K1303 Nguyễn An r  s= SBD HoTen K1301 Lê Lan K1302 Trần Lê K1303 Nguyễn An K1305 Thi Hồng K1304 Mai Ca - VD2: r (A B C) s(A B C) a1 b1 c1 a1 b1 c1 a2 b1 c2 a2 b2 c2 a2 b2 c1 r  s = (A B C) a1 b1 c1 20
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học a2 b1 c2 a2 b2 c1 a2 b2 c2 - Phép giao (Intersect): Giao của 2 quan hệ khả hợp r(U) và S(U) cho ta một quan hệ mới với tập thuộc tính U, các bộ là các bộ đồng thời thuộc 2 quan hệ đó. r  s= {t | t r và t s} Ví dụ có 2 quan hệ r và s như sau: SBD HoTen SBD HoTen K1301 Lê Lan K1305 Thi Hồng K1302 Trần Lê K1304 Mai Ca K1303 Nguyễn An K1303 Nguyễn An r  s= SBD HoTen K1303 Nguyễn An - VD2: r (A B C) s(A B C) a1 b1 c1 a1 b1 c1 a2 b1 c2 a2 b2 c2 a2 b2 c1 r  s = (A B C) a1 b1 c1 - Phép trừ (Substraction): Phép trừ quan hệ r(U) cho quan hệ khả hợp s(U) cho ta một quan hệ mới với tập thuộc tính U và các bộ là các bộ thuộc r nhưng không thuộc s r-s={t | t r và t s} Ví dụ có 2 quan hệ r và s như sau: SBD HoTen SBD HoTen K1301 Lê Lan K1305 Thi Hồng K1302 Trần Lê K1303 Nguyễn An 21
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học K1304 Mai Ca r-s = K1303 Nguyễn An SBD HoTen K1301 Lê Lan K1302 Trần Lê VD2: Cũng với 2 quan hệ r và s ở VD2 trên ta có r-s (A B C) a2 b1 c2 a2 b2 c1 - Phép tích Đề các (Catersion Product): Cho 2 quan hệ r(U) và s(V). Tích đề các của r và s cho ta một quan hệ với tập thuộc tính U và V với các bộ r x s = {tq | t r và q s} Nếu r có t1 bộ, s có t2 bộ thì kết quả của phép tích đề các có bao nhiêu bộ? (t1.t2 bộ) Ví dụ có 2 quan hệ r và s như sau SBD HoDem Ten NgaySinh K1301 Lê Lan Anh 10/10/91 K1302 Trần Lê Mai 5/9/90 r x s = SBD HoDem Ten NgaySinh K1301 Lê Lan Anh 10/10/91 K1301 Lê Lan Mai 5/9/90 K1302 Trần Lê Anh 10/10/91 K1302 Trần Lê Mai 5/9/90 - VD2: r(A B C) s(D E) a1 b1 1 1 e1 a2 b2 2 2 e2 3 e3 r x s = p(A B C D E) a1 b1 1 1 e1 a1 b1 1 2 e2 a1 b1 1 3 e3 a2 b2 2 1 e1 22
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học a2 b2 2 2 e2 a2 b2 2 3 e3 - Phép chia (Division): Cho 2 quan hệ r(U) và s(V), V U, s , đặt X=U-V. Phép chia quan hệ r cho quan hệ s cho ta một quan hệ mới với tập thuộc tính X và các bộ có dạng {t[X] | t r, q s thì t[X],q r } r s={t[X] | t r, q s thì t[X],q r } Ví dụ: cho quan hệ r Quan hệ s SBD HoDem Ten K1301 Lê Lan Anh HoDem Ten K1302 Trần Phương Mai Lê Lan Anh K1303 Hoàng Vân Anh Trần Lê Mai K1301 Trần Lê Mai K1302 Lê Lan Anh r s= SBD K1301 VD2: r(A B C D) s(C D) a b c d c d a b e f e f b c e f e d c d e d e f a b d e rs=(A B) a b e d 23
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học VD3: PHAN_CONG DU_AN Mã_CB MãD_an 100 D1 MãD_an 101 D2 D1 101 D3 D3 102 D1 D15 100 D15 105 D3 102 D3 100 D3 102 D15 105 D15 PHAN_CONG DU_AN= Mã_CB 100 102 1.3.2 Các phép toán đặc biệt trên quan hệ - Phép chọn (SELECTION) Cho quan hệ r(U) tập thuộc tính U={A1,A2, ,An}. E là một biểu thức logic phát biểu trên U. Phép chọn trên E cho ta một quan hệ mới có tập thuộc tính U và các bộ thoả biểu thức E. Khi đó E gọi là biểu thức chọn (hay điều kiện chọn) của quan hệ r trên tập thuộc tính U. + Các phép toán trên E có thể là , =, ≥, ≤, ≠, , , . + Ký hiệu: E(r)={t | t r và E(t) là đúng} VD1: với quan hệ r: MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK K1303 Lê Lan Ninh 15/3/89 Kim Sơn VS E : “DiaChi = Hoa Lư” phép chọn E(r) sẽ cho ta quan hệ sau: 24
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK ? E: “NgaySinh >1/1/1990” VD2: Cho E: (A=a1)  (B=b2)và quan hệ r (A B C D) thì  E(r)=(A B C D) a1 b1 c1 d1 a1 b2 c2 d1 a1 b2 c2 d1 a1 b2 c2 d2 a1 b2 c2 d2 a2 b1 c2 d1 a2 b2 c1 d1 - Phép chiếu (Project) Cho quan hệ r(U), X là tập con của U, giả sử t là một bộ thuộc quan hệ r, phép chiếu t[X] cho ta một quan hệ mới với các bộ là các bộ thuộc quan hệ r và các thuộc tính là tập X Ký hiệu: X(r)={t[X] | t r} VD3: Với quan hệ cho trong ví dụ của phép chọn ta thực hiện phép chiếu với tập X: Mã SV, mã ngành mã SV, mã ngành (r)= MaSV MaNganh K1301 TT K1302 LK K1303 VS VD4: Cho X=AB và quan hệ r (A B C D) thì  X(r)= (A B) a1 b1 c1 d1 a1 b1 a1 b2 c2 d1 a1 b2 a1 b2 c2 d2 a2 b1 a2 b1 c2 d1 a2 b2 a2 b2 c1 d1 - Phép kết nối (join) Cho 2 quan hệ r(U) và s(V), giả sử A i U và Bj V sao cho dom(Ai)=dom(Bj). Gọi  là một trong 6 phép toán so sánh { , =, ≥, ≤, ≠}. Phép kết nối quan hệ r 25
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học với thuộc tính Ai và quan hệ s với thuộc tính B j cho ta một quan hệ mới với tập thuộc tính là U  V và được các bộ được xác định bởi r s ={tq | t r, q s AB và t[A]  q[B] là đúng} - Nếu  là phép toán bằng “=” thì phép kết nối gọi là phép kết nối bằng - Nếu  là phép toán bằng “=” và AiBjA gọi là phép kết nối tự nhiên, ký hiệu là *. Ta có r * s = {tq | t r, q s và t[A] = q[A], A UV} VD1: Cho quan hệ r1={SBD, Họ đệm, Tên, Ngày sinh, quê quán} SBD HoDem Ten NgaySinh QueQuan K1301 Lê Lan Anh 10/10/91 Hoa Lư K1302 Trần Lê Mai 5/9/90 Hoa Lư K1303 Nguyễn An Ninh 15/3/89 Kim Sơn - Cho quan hệ r2={SBD, Đmôn1, Đmôn2, Đmôn3} SBD Dmon1 Dmon 2 Dmon 3 K1301 6 9 6 K1302 9 9 8 K1303 3 4 3 r1 * r2 = SBD HoDem Ten NgaySinh QueQuan Dmon1 Dmon 2 Dmon 3 K1301 Lê Lan Anh 10/10/91 Hoa Lư 6 9 6 K1302 Trần Lê Mai 5/9/90 Hoa Lư 9 9 8 K1303 Nguyễn Ninh 15/3/89 Kim Sơn 3 4 3 An VD2: Cho r1 (A B) r2 (B C) r3(A D) a1 b1 b1 c1 a2 d1 a1 b2 b1 c2 a2 d2 a2 b1 b2 c1 a3 d3 a2 b3 b2 c2 a3 b3 r1*r2 (A B C) r1*r3 (A B D) a1 b1 c1 a2 b1 d1 a1 b1 c2 a2 b1 d2 a1 b2 c1 a2 b3 d1 26
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học a1 b2 c2 a2 b3 d2 a2 b1 c1 a3 b3 d3 a2 b1 c2 - Phép kết nối ngoài trái (Left Outer Join) Kết nối ngoài trái của r và s bao gồm không chỉ những bộ là kết quả của việc xếp cạnh nhau của 2 bộ t,u kết nối tự nhiên được với nhau, mà còn bao gồm những bộ có phần bên trái là một bộ t không kết nối được với bộ nào trong s, phần bên phải là các giá trị null r < s ={(t,u)| (t,u) r*s hoặc ((t, null, null ) và (u s:t[A]≠u[A]))} ở đây A là thuộc tính xuất hiện ở cả 2 lược đồ quan hệ r và s Ví dụ: Cho 2 quan hệ NCC MaCty TenCty Dia_Chi S1 Hoàng Hồng Hà nội S2 Thái học Ninh Bình S3 Minh Hương Nam định S4 Trần Anh Hà Nội S5 Mai Linh Tp HCM CUNG_UNG Ma_Cty Ma_SP So_luong S1 P1 5000 S2 P1 1000 S1 P2 2000 S2 P3 1500 S3 P3 500 S4 P5 3000 NCC CUNG_UNG MaCty TenCty Dia_Chi Ma_SP So_luong S1 Hoàng Hồng Hà nội P1 5000 S1 Hoàng Hồng Hà nội P2 2000 S2 Thái học Ninh Bình P1 1000 S2 Thái học Ninh Bình P1 1000 S3 Minh Hương Nam định P3 1500 S4 Trần Anh Hà Nội P5 3000 27
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học S5 Mai Linh Tp HCM Null null - Phép kết nối ngoài phải (Right Outer Join) Tương tự kết nối ngoài trái của r và s bao gồm không chỉ những bộ là kết quả của việc xếp cạnh nhau của 2 bộ t,u kết nối tự nhiên được với nhau, mà còn bao gồm những bộ có phần bên phải là một bộ u không kết nối được với bộ nào trong r, phần bên trái là các giá trị null r s ={(t,u)| (t,u) r*s hoặc (( null, null, u) và (t r:t[A]≠u[A]))} - Đặt lại tên cho quan hệ Để đạt được quan hệ kết quả, có thể phải áp dụng nhiều phép toán quan hệ liên tiếp. trong trường hợp đó, chúng ta có thể viết một biểu thức đại số quan hệ mà các phép toán có thể xếp lồng với nhau. Có thể làm cho việc này trở nên đơn giản hơn bằng cách áp dụng mỗi phép toán tại một thời điểm và tạo ra các quan hệ kết quả trung gian, những quan hệ trung gian như vậy cần phải đặt tên. Ví dụ: KQTG  NCC*CUNG_UNG KQ  Ma_Sp=’P2’(KQTG) Cũng có thể đặt lại tên thuộc tính trong các quan hệ trung gian và kết quả cuối cùng, ta liệt kê tên mới của các thuộc tính trong dấu ngoặc đi kèm theo tên quan hệ kết quả Ví dụ: CUNG_UNG_P2(CTY, SOLUONG) Ma_Cty, so_luong(KQ) 1.3.3. Các phép toán quan hệ bổ sung Các hàm tính toán Chúng ta hay gặp những dạng câu hỏi kiểu như phòng đó có bao nhiêu nhân viên, trung bình lương của các nhân viên trong một công ty là bao nhiêu Sau đây là một số hàm thường dùng SUM, AVERAGE, MAX, MIN, COUNT Các hàm gộp nhóm Sử dụng khi cần nhóm dữ liệu theo một tiêu chí nào đó, chẳng hạn tính tổng số sinh viên quê ở mỗi Huyện của Tỉnh Ninh Bình Ta định nghĩa như sau: F (r) 28
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Kết quả của phép gộp nhóm là một quan hệ. Nếu danh sách thuộc tính cơ sở để gộp nhóm là rỗng thì hàm tính toán áp dụng cho tất cả các bộ trong quan hệ và quan hệ kết quả chỉ có một bộ Ví dụ: có quan hệ NHAN_VIEN như sau: Ma_NV HO_TEN NG_SINH MA_PHONG LUONG(x100.000) 1 Nguyễn An 10/10/91 P1 150 2 Trần Cường 5/9/90 P2 230 3 Lê Lan 15/3/89 P1 170 4 Trịnh Khanh 6/7/89 P4 310 5 Thu Cúc 12/10/89 P1 230 6 Xuân Giao 3/7/90 P2 180 7 Mai Lan 1/3/80 P4 220 8 Lê Chi 5/3/82 P3 310 9 Hoàng Hải 7/12/85 P4 80 10 Hoàng Minh 15/7/84 P1 250 Nếu thực hiện phép gộp nhóm MA_PHONG FCOUNT Ma_NV, AVERAGE LUONG(NHANVIEN) Quan hệ kết quả sẽ là MA_PHONG COUNT_MA_NV AVERAGE_LUONG P1 4 200 P2 2 205 P3 1 310 P4 3 203,33 Nếu thực hiện phép gộp FCOUNT Ma_NV, AVERAGE LUONG(NHANVIEN) Quan hệ kết quả sẽ là COUNT_MA_NV AVERAGE_LUONG 10 213 29
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 1.4. Ngôn ngữ tân từ: Đại số quan hệ cung cấp một tập các phép toán (chọn, chiếu, kết nối,hợp ) và ta sử dụng chúng để chỉ ra cho hệ thống biết làm thế nào để từ những quan hệ đang có xây dựng nên những quan hệ ta muốn có. Trong khi đó ngôn ngữ tân từ (các phép tính quan hệ) cung cấp những ký hiệu để phát biểu định nghĩa quan hệ ta muốn có theo các quan hệ đang có. Đây là điểm khác nhau cơ bản giữa đại số quan hệ và phép tính quan hệ, mặc dù chúng đều là ngôn ngữ hình thức của cơ sở dữ liệu quan hệ. Cơ sở toán học của phép tính quan hệ là logic tân từ cấp 1. Hai loại ngôn ngữ tân từ là ngôn ngữ tân từ biến bộ và ngôn ngữ tân từ biến miền. Trong nội dung chương trình chúng ta nghiên cứu ngôn ngữ tân từ biến bộ. - Các biến bộ: Ngôn ngữ tân từ biến bộ (gọi tắt là phép tính biến bộ) dựa trên sự đặc tả các biến bộ. Miền trị mỗi biến bộ là một quan hệ cụ thể của cơ sở dữ liệu, nói cách khác mỗi biến bộ có thể nhận là một bộ nào đó trong quan hệ này. Một câu hỏi đơn giản trong phép tính biến bộ có dạng {t | ĐK(t)} - Với t là biến bộ và ĐK(t) là một biểu thức điều kiện chứa biến t. Kết quả trả ra cho câu hỏi là tập tất cả các bộ làm cho ĐK(t) - điều kiện t được thoả mãn. Chẳng hạn muốn tìm trong quan hệ NHAN_VIEN ở trên những nhân viên có lương trên 2triệu, ta có thể dùng câu hỏi sau: {t| NHAN_VIEN (t) and t.luong>2000000} trong câu hỏi này t.luong là để chỉ thuộc tính lương của biến bộ t. Mỗi bộ trong kết quả được trả ra với tất cả các thuộc tính. Nếu chỉ cần biết một số thuộc tính nào đó của các bộ kết quả, chẳng hạn ho_ten và ma_da có thể dùng câu hỏi dưới đây {t.ho_ten, t.ma_da |NHAN_VIEN (t) and t.luong>2000000} Trong một biểu thức của phép tính biến bộ có thể xuất hiện nhiều biến bộ Ví dụ biểu diễn câu hỏi bằng phép tính biến bộ: Cho CSDL gồm các lược đồ sau: NHANVIEN (ma_nv, ho_ten, ng_sinh, gioi_tinh, ma_dv, luong) PHONG (ma_dv, ten_phong, ma_tp) DD_DVI(ma_dv, dia_diem) DU_AN(ma_da, ten_da, dd_da, ma_dv) CHAMCONG(ma_nv, ma_da, so_gio) 30
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Câu 1: Tìm tên dự án có mã D4 {t.ten_da | DU_AN(t) and t.ma_da=’D4’} Câu 2: Cho biết họ tên và lương của những nhân viên thuộc phòng ‘Kinh doanh’ {t.ho_ten, t.luong | u (NHANVIEN(t) and PHONG(u) and u.ten_phong=’Kinh doanh’ and t.ma_dv=u.ma_dv)} Câu 3: Với mỗi dự án thực hiện tại Ninh Bình hãy cho biết mã số dự án đồng thời cho biết họ tên trưởng phòng quản lý dự án này {t.ma_da, u.ho_ten | v (DU_AN(t) and NHANVIEN(u) and PHONG(v) and t.dd_da = ‘Ninh Bình’ and t.ma_dv=v.ma_dv and v.ma_tp=u.ma_nv)} Câu 4: Tìm tên nhân viên, lương thuộc đơn vị có mã PKT1 Câu 5: Cho biết ma_da, ten_da của những dự án do phòng ‘Kinh doanh’ quản lý Câu 6: Cho biết ho_ten, ten_phong của những nhân viên tham gia dự án với số giờ>75 Lưu ý: Khi trả lời các câu hỏi truy vấn dữ liệu chúng ta phải xác định Cần gì? ở đâu? thoả mãn điều kiện gì? 2. Ngôn ngữ hỏi có cấu trúc – SQL (Structured Query Language) Đây là ngôn ngữ định nghĩa dữ liệu và thao tác dữ liệu rất mạnh được đề xuất vào năm 1986 nhằm đáp ứng nhu cầu cần một ngôn ngữ thân thiện hơn với người sử dụng trong các hệ csdl thương mại. Ngôn ngữ SQL đã được chuẩn hoá gọi là ANSI SQL. Tuy nhiên các hệ CSDL khác nhau cũng có những chi tiết khác nhau. Một số quy ước khi trình bày về SQL - Các từ khoá, các hàm được viết bằng chữ in hoa - Các tên do người dùng đặt được viết bằng chữ in thường, tên bảng và tên ràng buộc toàn vẹn viết bằng chữ in đậm. - Các phạm trù cú pháp, tức là các thành phần ngôn ngữ mà người sử dụng phải điền vào khi viết lệnh sẽ được viết trong cặp dấu ngoặc - Các thành phần tuỳ chọn, tức là chúng có thể xuất hiện hoặc không xuất hiện trong câu lệnh được viết trong cặp dấu ngoặc vuông [ ] - Việc lựa chọn một trong các khả năng được viết bằng dấu gạch đứng | - Thành phần bắt buộc phải chọn trong danh sách được viết trong cặp dấu {}. - Lệnh SQL có thể được viết trên nhiều dòng và kết thúc bằng dấu ;, những mỗi từ khoá tên hàm, tên thuộc tính, tên bảng phải nằm trọn vẹn trên một dòng. 31
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 2.1. Ngôn ngữ định nghĩa dữ liệu Trong SQL có một số phép tính được sử dụng để có thể tạo ra các quan hệ (bảng), các khung nhìn của người sử dụng (View), các tệp chỉ số (Index). 2.1.1. Tạo bảng Cú pháp: CREATE TABLE ( ([ [, ])] [NULL / NOT NULL] [CHECK [ERROR ]] [DEFAULT ] [PRIMARY KEY / UNIQUE] [REFERENCES [TAG ]] [, ([ [, ])] [NULL / NOT NULL] [CHECK [ERROR ] [DEFAULT ] .) Trong đó: Tên bảng là xâu ký tự không chứa ký tự trống, không trùng từ khoá Tên trường là xâu ký tự không chứa ký tự trống. trong một bảng không có 2 tên trường trùng nhau Kiểu trường: là một trong các kiểu sau: Char(n) Xâu ký tự độ dài cố định Varchar[(n)] Xâu ký tự độ dài thay đổi, độ dài tối đa n int Số nguyên. Smallint Số nguyên nhỏ. Numeric (p,d) Số dấu chấm thập phân cố định, gồm p chữ số và 1 dấu chấm, trong đó d chữ số bên phải dấu chấm. Real, Double Precision Số dấu phẩy động và số dấu phẩy động độ chính xác gấp đôi Float (n) Số dấu phẩy động độ chính xác n chữ số sau dấu phẩy Date Ngày tháng năm Time Giờ phút giây NULL: Cho phép bỏ trống giá trị nếu cần thiết NOT NULL: Bắt buộc cột phải có giá trị cụ thể Check (btđk): Kiểm tra điều kiện trường Error :Lời thông báo nếu nhập sai điều kiện trên Default: giá trị mặc định cho trường Primary key:Lựa chọn trường này làm khoá chính Unique:Xác định tính duy nhất của trường 32
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học References: Tham chiếu đến bảng khác Tag: Tên trường khoá chính ở bảng tham chiếu VD1: Tạo bảng Khoa gồm mã khoa gồm 2ký tự không chấp nhận giá trị rỗng, tên khoa gồm 20 ký tự, số điện thoại gồm 7 số CREATE TABLE khoa (MaKhoa char(2) NOT NULL, TenKh varchar(20), Đthoai int) VD2: CREATE TABLE Lop (lopID char(5) PRIMARY KEY, tenlop varchar(20), nganh varchar(20), khoahoc varchar(10), MaKhoa char(2) REFERENCES khoa TAG MaKhoa) VD3: CREATE TABLE sinhvien(svid varchar(10) PRIMARY KEY, hodem varchar(20), ten varchar(10), ngaysinh date CHECK ngaysinh 0 2.1.5. Thêm cột mới Cú pháp:ALTER TABLE tên_bảng ADD tên_cột kiểu VD1: Thêm cột Trưởng khoa cho bảng KHOA với kiểu là xâu ký tự ALTER TABLE khoa ADD TruongKhoa varchar(25) VD2: Thêm cột ngày thành lập khoa cho bảng KHOA ALTER TABLE khoa ADD NgayTL date 2.1.6. Xoá cột: Cú pháp:: ALTER TABLE tên_bảng DROP tên_cột Ví dụ: xoá cột trưởng khoa trong bảng khoa ALTER TABLE khoa DROP TruongKhoa 2.1.7. Tạo lập các chỉ mục: 33
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Tạo chỉ mục là tạo ra một bảng lưu trữ vị trí các bản ghi dựa trên giá trị tăng dần của một hay một số cột nào đó. Điều này có ý nghĩa làm tăng tốc độ tìm kiếm thông tin trong CSDL. Tạo chỉ mục không làm thay đổi thứ tự vật lý của các bản ghi trong bảng Cú pháp:CREATE INDEX ON ( [, , ]) Ví dụ: CREATE INDEX nv_index ON nhanvien(ten) 2.1.7. Loại bỏ bảng chỉ mục: DROP INDEX Ví dụ: Tạo CSDL gồm 5 bảng như sau: Bảng SINHVIEN Tên trường Kiểu độ rộng Chú thích / Ràng buộc Svid C 10 Mã sinh viên Hodem C 20 họ đệm Tên C 10 Tên Ngaysinh D 8 Ngày sinh < ngày hiện tại+365*16 Noisinh C 30 Nơi sinh Lopid C 5 Mã lớp Ghichu M Thông tin thêm về sinh viên Bảng LOP Tên trường Kiểu độ rộng Chú thích / Ràng buộc Lopid C 5 Mã lớp Tenlop C 20 Tên lớp Nganh C 20 Ngành học Khoahoc C 10 Khoá học Bảng RENLUYEN Tên trường Kiểu độ rộng Chú thích / Ràng buộc Svid C 10 Mã sinh viên Hocky I 4 0< học kỳ <= 10 Nd1 I 4 0<= nội dung 1 <=10 Nd2 I 4 0<= nội dung 1 <=10 Nd3 I 4 0<= nội dung 1 <=10 Nd4 I 4 0<= nội dung 1 <=10 34
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Nd5 I 4 0<= nội dung 1 <=10 Kq I 4 Kết quả Xeploai C 5 Xếp loại Bảng MONHOC Tên trường Kiểu độ rộng Chú thích / Ràng buộc Monid I 4 Mã môn học Tenmon C 35 Tên môn Dvht I 4 Đơn vị học trình Hocky I 4 0< học kỳ <= 10 Lopid C 5 Mã lớp Bảng HOCTAP Tên trường Kiểu độ rộng Chú thích / Ràng buộc Htid B 8 Mã cho mỗi bản ghi trong bảng Svid C 10 Mã sinh viên Hocky I 4 0< học kỳ <= 10 Monid I 4 Mã môn học Dhs1 F 20 0<= dhs1 <= 10 Dhs2 F 20 0<= dhs2 <= 10 Dtlan1 F 20 0<= dtlan1 <= 10 Dtlan2 F 20 0<= dtlan2 <= 10 Dtlan3 F 20 0<= dtlan3 <= 10 Thiết lập mối quan hệ giữa các bảng. 2.2. Ngôn ngữ thao tác dữ liệu Cho CSDL QLDAYHOC gồm các quan hệ sau: khoa (MaKh, TenKh, TruongKh, DTk) cbgd (MaCB, TenCB, Monday, Dtc, MaKh) sv (MaSV, TenSV, NS, QQ, MaLop) lop (MaL, TenL, Nganh, Khoahoc, MaKh) diem (MaSV, Mon, Diem) Trong đó: Bảng khoa: MaKh: Mã khoa TenKh: Tên khoa TruongKh: Tên Trưởng Khoa 35
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học DTk: Điện thoại văn phòng khoa Bảng cbgd: MaCB: Mã cán bộ TenCB: Tên cán bộ Monday: Tên môn học mà cán bộ đó dạy Dtc: Điện thoại liên lạc với cán bộ giảng dạy MaKh: Mã khoa Bảng sv: MaSV: Mã số sinh viên TenSV: Họ Tên của sinh viên NS: Ngày sinh QQ: Quê quán của sinh viên MaLop: Mã lớp của sinh viên Bảng lop: MaL: Mã lớp TenL: Tên lớp Nganh: Ngành học Khoahoc: Khóa học của lớp MaKh: Mã khoa quản lý lớp Bảng diem: MaSV: Mã sinh viên Mon: Tên môn học Diem: Điểm môn học của sinh viên 2.2.1. Các lệnh cập nhật dữ liệu: - Nhập dữ liệu cho bảng INSERT INTO [( )] VALUES ( ) VD: Thêm bộ INSERT INTO sv VALUES (‘C2701’,Trần Thị Hà’,’1985’,Gia viễn’, ‘T14B’) - Xoá 1 bản ghi trong bảng DELETE FROM WHERE VD: DELETE FROM sv WHERE MaLop = ‘T10A’ - Sửa nội dung bản ghi UPDATE SET = , . WHERE VD: UPDATE cbgd SET MaKh=’01’ WHERE MaKh=’02’ 2.2.2. Lệnh truy vấn dữ liệu - Khối SELECT Cấu trúc cơ sở của một truy vấn gồm 3 câu SELECT, FROM và WHERE 36
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Câu SELECT ứng với phép chiếu của đại số quan hệ, được dùng để liệt kê các thuộc tính (Cột) muốn có trong kết quả của một câu hỏi. Câu FROM: ứng với tích đề_các của đại số quan hệ, được dùng để liệt kê các quan hệ cần được sử dụng khi tìm kết quả cho câu hỏi. Câu WHERE ứng với phép chọn của đại số quan hệ, được dùng để đưa ra điều kiện chọn. SELECT [DISTINCT] * / [AS FROM [WHERE ] [GROUP BY HAVING ] [ORDER BY {têncột / Tênbt} [ASC/DESC] Trong đó: Dấu * để chỉ tất cả các cột trong bảng Dscột: Tên các cột của bảng cần lấy ra kết quả, viết cách nhau dấu , Dsbt: Các biểu thức cần lấy ra kết quả DISTINCT: Chỉ rằng trong bảng kết quả không lấy các bản ghi trùng nhau FROM ds bảng: Tên các bảng chứa dữ liệu mà ta cần lấy thông tin WHERE btđk: Xác định các bản ghi cần đưa thông tin ra GROUP BY dscột: Nhóm các bản ghi theo các cột trong danh sách cột HAVING btđk: Điều kiện được nhóm trong group ORDER BY: Sắp xếp theo cột hoặc theo biểu thức Khi dịch một lệnh trong SELECT thì thứ tự thực hiện như sau: FROM WHERE GROUP BY HAVING SELECT ORDER BY Chú ý: Phân biệt mục đích câu điều kiện trong Where và trong Having - Câu WHERE lọc lấy một số bộ nào đó trong một bảng để đưa vào bảng kết quả. Câu Having lọc lấy một số nhóm nào đó để đưa vào bảng kết quả - Theo chuẩn ISO tên cột dùng trong câu HAVING cũng có mặt trong danh sách tên cột ở câu Group by hay trong hàm gộp - Thực tế là điều kiện chọn trong câu HAVING luôn chứa ít nhất một hàm gộp, nếu không điều kiện này có thể chuyển vào câu WHERE. 37
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Hàm gộp không được dùng trong câu WHERE. Các lệnh tìm kiếm - Tìm kiếm đơn giản: + Tìm kiếm không điều kiện VD: Tìm TenKh của trường SELECT TenKh FROM khoa + Tìm kiếm với điều kiện đơn giản VD1: Tìm tên sinh viên thuộc lớp T13B SELECT TenSV FROM sinhvien WHERE MaL= ‘T13B’ VD2: SELECT DISTINCT MaL FROM sv VD3: SELECT * FROM khoa WHERE TenKh= ‘CN’ Trong biểu thức điều kiện WHERE có thể sử dụng các toán tử so sánh và toán tử logic ( , =, = , <> ,and, or, not) VD4: Cho xem tên sinh viên của những sinh viên thuộc lớp T13B và sinh trước ngày 1/1/85 SELECT TenSV FROM sv WHERE (TenL= ‘T13B’) and (Ngaysinh<{1/1/85}) + Tìm kiếm có xử lý xâu ký tự: Dùng từ khoá LIKE nếu không nhớ chính xác nội dung Dấu % đại diện cho xâu ký tự, dấu _ đại diện cho 1 ký tự: VD: SELECT TenSV FROM sv WHERE QQ LIKE ‘Ninh%’ SELECT * FROM sv WHERE TenSV LIKE ‘%Hoa’ + Tìm kiếm có xử lý ngày tháng: Thêm dấu ngoặc {} vào ngày tháng SELECT * FROM sv WHERE NS={1980.9.11} + Tìm kiếm có từ khoá IN và BETWEEN AND VD: SELECT DISTINCT MãKh FROM lop WHERE TenL IN(‘T13A’,’T13B’,’T13C’) VD: SELECT MaSV FROM diem WHERE Diem BETWEEN 8 AND 10 + Tìm kiếm có sắp xếp: ORDER BY Cho xem danh sách sinh viên theo Diem giảm dần SELECT * FROM diem ORDER BY dToan DESC + Tìm kiếm có sử dụng Group by: VD1: Cho xem DS SV trong bảng SV theo từng khoa 38
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học SELECT * FROM sv GROUP BY MaKh VD2: Cho biết maKh của các Khoa có số lượng SV >1000 SELECT DISTINCT MaKh FROM sv GROUP BY Makh HAVING count(*)>1000 + Tìm kiếm với các hàm Các hàm thư viện của SQL: o COUNT: Tính số lượng các bộ hiện có trong 1 quan hệ o MAX: Cho giá trị cực đại của 1 trường o MIN: Cho giá trị cực tiểu của 1 trường o AVG: Tính giá trị trung bình của 1 trường o SUM: Tính tổng các giá trị xuất hiện trên cột VD: o SELECT Count(*) FROM sv WHERE MaLop=’T13B’ o SELECT Sum(Slg) FROM donhang WHERE MaH= ‘P1’ o SELECT Max(DTin) FROM diem WHERE MaLop=’T13B’ Tìm kiếm với câu hỏi phức tạp (sử dụng phép kết nối và ánh xạ lồng) Một truy vấn con là một biểu thức SELECT lồng trong một truy vấn khác. Câu truy vấn con có thể xuất hiện trong câu SELECT, WHERE hay HAVING của câu truy vấn ngoài. Để sử dụng truy vấn con ta phải tuân thủ các luật sau: - Câu order by không được sử dụng trong truy vấn con, nhưng được phép trong truy vấn ngoài cùng. - Danh sách các mục được liệt kê bởi truy vấn con SELECT phải chứa tên của một cột hoặc một biểu thức trừ khi câu truy vấn con này dùng từ khoá EXISTS. - Các tên cột trong câu truy vấn con có thể tham chiếu đến bảng trong câu From của truy vấn ngoài. - Khi một câu truy vấn con là một trong 2 toán hạng của một biểu thức so sánh thì truy vấn con này phải xuất hiện bên phải biểu thức so sánh. Phép kết nối: Để kết nối 2 bảng: + Miền trị của các cột tham gia kết nối là sánh được với nhau + Tên các bảng tham gia kết nối phải được liệt kê sau từ khoá From + Điều kiện kết nối phải được chỉ ra sau Where 39
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học + Tên các cột trong bảng có thể phải chỉ ra tường minh cùng tên bảng theo dạng: tênbảng.têncột VD: Cho xem thông tin cbộ, môn dạy, tên khoa của tất cả các cbgd SELECT TênCB,môn dạy, tênKH FROM cbgd, khoa WHERE cbgd.Mah= khoa.MaKH Ánh xạ lồng: Trong câu lệnh tìm kiếm có các khối lồng nhau theo nhiều mức lồng nhau. Tức là trong biểu thức điều kiện của khối này lại chứa một khối khác VD: SELECT * FROM sv WHERE MaL IN (SELECT MaL FROM lop WHERE TenL=’D2 Công nghệ’) Các từ khoá ALL, SOME, ANY trong SQL luôn đi kèm một câu hỏi con mà câu hỏi con này trả ra kết quả chỉ là một cột. VD: Tìm sinh viên nhỏ tuổi hơn mọi sinh viên lớp T13B SELECT TenSV FROM sv WHERE NS>ALL (SELECT NS FROM sv WHERE MaL=’T13B’ (Ánh xạ lồng chỉ lấy được thông tin từ một quan hệ mà điều kiện thuộc về 1 quan hệ khác, chứ không lấy được thông tin ở cả hai quan hệ) Các phép toán tập hợp Trong SQL-92 có các phép UNION, INTERSECT, EXCEPT thao tác trên các quan hệ tương ứng với phép hợp, giao và trừ của đại số quan hệ. Các quan hệ tham gia trong phép toán này phải khả hợp. Các phép toán này tự động loại bỏ các bộ trùng nhau. VD1: Xét CSDL QLDAYHOC nói trên giả sử có thêm quan hệ hoc (MaCB, TenCB, trinhđộ, chuyennganh) chứa thông tin về việc đi học của cbgd. Ta cần MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ và dạy môn CSDL (SELECT MaCB, TenCB FROM cbgd 40
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học WHERE Monday=’CSDL’) INTERSECT (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) VD2: Cho biết MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ hoặc dạy môn CSDL (SELECT MaCB, TenCB FROM cbgd WHERE Monday=’CSDL’) UNION (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) VD3: Cho biết MaCB, TenCB của những cán bộ đi học trình độ Tiến sỹ nhưng không dạy môn CSDL (SELECT MaCB, TenCB FROM hoc WHERE trinhdo=’Tiến sỹ’) EXCEPT (SELECT MaCB, TenCB FROM cbgd WHERE Monday=’CSDL’) Kết chương Chương II đã giới thiệu một số ngôn ngữ thao tác dữ liệu như đại số quan hệ, ngôn ngữ tân từ và đặc biệt là ngôn ngữ hỏi có cấu trúc SQL có khuôn dạng và ví dụ cụ thể. Câu hỏi và bài tập Câu 1: Nêu các khái niệm cơ bản của mô hình quan hệ: Thuộc tính, Lược đồ quan hệ, Miền trị, Quan hệ, Khóa, Khóa kết nối. Câu 2: Khái niệm khả hợp Bài tập: Bài 1: Cho 3 quan hệ 41
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học r1(A B C) r2 (D F) r3 (B E D) a1 b1 c1 d1 f1 b1 e1 d1 a2 b2 c2 d2 f2 b2 e2 d2 a1 b1 c3 d3 f3 b3 e3 d1 a2 b3 c1 r4 (A B C D) r5(C D) a b c d c d a b e f e f b c e f e d c d e d e f a b d e Tính các biểu thức sau: a) r1xr2 b)r1*r3 c)D=d1(r1*r3) d)r1*r2*r3 e) BC(r1*r2*r3) f) r4r5 Bài 2: Cho CSDL gồm các lược đồ sau: congty(MaCT, TenCT, DC, DT) mathang(MaMH, TenMH, Mau, TrongLuong) sanpham(MaCT, MaMH, Soluong) Trả lời các câu hỏi sau bằng ngôn ngữ đại số quan hệ a. Tìm MaCT của những công ty đã cung cấp mặt hàng có mã là P2 b. Tìm MaCT của những công ty cung ứng ít nhất 1 mặt hàng mầu đỏ c. Tìm MaMH của những mặt hàng do công ty có tên SamSung cung cấp d. Tìm MaMH những mặt hàng chưa được công ty nào cung ứng e. Tìm TenCT đã cung cấp mặt hàng có tên là “Notebook” Bài 3: Cho CSDL gồm các lược đồ sau: nhanvien (ma_nv, ho_ten, ng_sinh, gioi_tinh, ma_dv, luong) phong (ma_dv, ten_phong, ma_tp) dd_dvi(ma_dv, dia_diem) du_an(ma_da, ten_da, dd_du_an, ma_dv) chamcong(ma_nv, ma_da, so_gio) Trả lời các câu hỏi bằng đại số quan hệ a. Tìm tên dự án có mã số D4 42
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học b. Cho biết họ tên và lương của những nhân viên làm việc ở phòng ‘Nghiên cứu và phát triển’ c. Với mỗi dự án thực hiện ở Ninh Bình, hãy cho biết mã số dự án đồng thời, cho biết họ tên, ngày sinh của trưởng phòng quản lý dự án này d. Tìm tên những nhân viên làm việc cho tất cả các dự án do phòng có mã P4 quản lý e. Tìm mã số những dự án có sự tham gia của một người lãnh đạo phòng trực tiếp quản lý dự án này Bài 4: Cho CSDL về các khách sạn gồm các lược đồ sau: Khach_san(ma_ks, ten_ks, dia_chi) Phong(ma_ph, ma_ks, loai, gia) Dat_phong(ma_ks, ma_khach, tu_ngay, den_ngay, ma_ph) Khach(ma_khach, ho_ten, dia_chi) Hãy viết các biểu thức đại số quan hệ tương ứng với mỗi câu hỏi sau: a. Cho biết tên tất cả các khách sạn b. Liệt kê tất cả các phòng có giá dưới 200.000 đ c. Cho biết giá và loại của tất cả các phòng thuộc khách sạn Sao mai d. Liệt kê họ tên của tất cả các khách đã đặt thuê phòng ở khách sạn Sao mai e. Cho biết thông tin chi tiết về các phòng của khách sạn Sao mai với những phòng đang có người đặt thuê thì cho biết cả họ tên và địa chỉ của khách. Bài 5: Xét CSDL gồm các lược đồ quan hệ sau: Nhan_vien (ht_nv, duong_pho, thanh_pho) Lam_viec (ht_nv, ten_cty, luong) Cong_ty(ten_cty, thanh_pho) Quan_ly(ht_nv, ten_thu_truong) Hãy biểu diễn các câu hỏi sau bằng ngôn ngữ đại số quan hệ. a. Tìm họ tên và thành phố sinh sống của tất cả các nhân viên làm việc cho công ty FBC b. Tìm họ tên, tên đường phố, thành phố sinh sống của tất cả các nhân viên làm việc cho FBC có lương lớn hơn 2triệu. c. Tìm tất cả nhân viên trong CSDL sinh sống cùng thành phố của công ty nơi họ làm việc d. Tìm tất cả nhân viên trong CSDL sống trong cùng thành phố và trong cùng phố với thủ trưởng của họ 43
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học e. Tìm tất cả các nhân viên không làm việc cho FBC f. Tìm tất cả các nhân viên có lương cao hơn mọi nhân viên của công ty FBC g. Giả sử các công ty được đặt tại nhiều thành phố. Tìm tất cả các công ty đặt tại mọi thành phố nơi có mặt công ty FBC h. Tìm tất cả các nhân viên có lương cao hơn lương trung bình của mọi nhân viên công ty của họ i. Tìm công ty có nhiều nhân viên nhất j. Tìm công ty có quỹ tiền lương nhỏ nhất k. Tìm các công ty mà nhân viên đều có lương trung bình cao hơn lương trung bình tại FBC Bài 6: Cho csdl gồm các lược đồ quan hệ sau: tacgia(MaTG, TenTG, Dt) nxb(MaNXB, TenNXB, Dc, dt) sach(MaS, TenS, NamXB, Slg, MaTG, MaNXB) Trả lời các câu hỏi sau bằng ngôn ngữ SQL a. Cho biết tên cuốn sách xuất bản năm 2007 b. Cho biết Mã sách, tên sách xuất bản năm 2007 và số lượng xuất bản trên 1000 cuốn c. Tên cuốn sách xuất bản năm 2000 của NXB GD d. Xoá tác giả “Nguyễn Văn Thành” trong CSDL trên e. Thêm nhà xuất bản có mã “NB”, tên là “nhà xuất bản Ninh Bình”, Dc là “TP Ninh Bình”, dt là 0303888888) f. Sửa Dt của tác giả có mã TT07 thành 0983.98.98.98 Bài 7: Cho CSDL gồm các lược đồ quan hệ sau: truong(MaTr, TenT, DC, DT, Hieu truong) khoa(MaTr, MaKh, TenKh, SoSV) sinhvien(MaTr, MaKH, MaSV, TenSV, QQ) Trả lời bằng Ngôn ngữ SQL a. Cho biết tên trường ĐH có khoa CNTT b. Tổng số SV khoa CNTT ở tất cả các trường ĐH c. Khoa nào của trường nào có số SV đông nhất d. Tên Tr có tổng số SV đông nhất Bài 8: Cho CSDL gồm các lược đồ quan hệ: nhanvien (MaNV, HoTen, NgaySinh, MaPhong) 44
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học phong (MaPhong, TenPhong, DiaDiem, Sodt) du_an(MaDA, TenDA, NganSach) thamgia(MaNV, MaDA, SoGioThamGia) Biểu diễn các câu tìm kiếm trên bằng Đại số quan hệ và ngôn ngữ SQL a. Đưa ra danh sách (họ tên, ngày sinh) của các nhân viên tham gia Dự án có tên là đào tạo từ xa hoặc tham gia dự án có tên là QLTC b. Đưa ra danh sách (tên phòng, địa điểm) của phòng có nhân viên mã số là ‘NV03’ làm việc c. Cho biết danh sách (họ tên, ngày sinh, mãPh) của các nhân viên tham gia vào dự án d. Cho biết có bao nhiêu dự án có ngân sách lớn hơn 100.000.000 Bài 9: Xét CSDL gồm các lược đồ quan hệ sau: Nhan_vien (ht_nv, duong_pho, thanh_pho) Lam_viec (ht_nv, ten_cty, luong) Cong_ty(ten_cty, thanh_pho) Quan_ly(ht_nv, ten_thu_truong) Hãy biểu diễn các câu hỏi sau bằng ngôn ngữ SQL. a. Tìm họ tên và thành phố sinh sống của tất cả các nhân viên làm việc cho công ty FBC b. Tìm họ tên, tên đường phố, thành phố sinh sống của tất cả các nhân viên làm việc cho FBC có lương lớn hơn 2triệu. c. Tìm tất cả nhân viên trong CSDL sinh sống cùng thành phố của công ty nơi họ làm việc d. Tìm tất cả nhân viên trong CSDL sống trong cùng thành phố và trong cùng phố với thủ trưởng của họ e. Tìm tất cả các nhân viên không làm việc cho FBC f. Tìm tất cả các nhân viên có lương cao hơn mọi nhân viên của công ty FBC g. Giả sử các công ty được đặt tại nhiều thành phố. Tìm tất cả các công ty đặt tại mọi thành phố nơi có mặt công ty FBC h. Tìm tất cả các nhân viên có lương cao hơn lương trung bình của mọi nhân viên công ty của họ i. Tìm công ty có nhiều nhân viên nhất j. Tìm công ty có quỹ tiền lương nhỏ nhất 45
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học k. Tìm các công ty mà nhân viên đều có lương trung bình cao hơn lương trung bình tại FBC 46
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG III: THIẾT KẾ MỘT CƠ SỞ DỮ LIỆU 1. Mục đích thiết kế CSDL Mục đích chính của thiết kế CSDL là nhóm các thuộc tính vào các bảng sao cho giảm được nhiều nhất sự dư thừa dữ liệu bởi vậy giảm được không gian lưu trữ cần thiết cho các quan hệ cơ sở. Nếu để dư thừa dữ liệu sẽ nảy sinh một số vấn đề. Ta xét ví dụ sau: Để lưu các thông tin về sinh viên trong một khoa với nhiều lớp ta có 2 phương án khác nhau như sau: - Phương án a: dùng một lược đồ sinhvien_lop(svid, hoten, ns, qq, diachi, lopid, tenlop, nganhhoc, khoahoc) - Phương án b: dùng 2 lược đồ sinhvien(svid, hoten, ns, qq, diachi) và lop(lopid, tenlop, nganhhoc, khoa) Ta nhận thấy ở phương án a các thông tin về lớp bị lặp lại rất nhiều lần khi sinh viên thuộc cùng một lớp. Trong khi ở phương án b thông tin về mỗi lớp được thể hiện là một bộ trong quan hệ lop và trong quan hệ sinhvien chỉ lopid là lặp lại với một số bộ. Khi thao tác dữ liệu sẽ xảy ra một số dị thường sau Ví dụ: quan hệ lop Lopid Tenlop Nganhhoc Khoa 1 T14A Hoá sinh Tự nhiên 2 T14B Tin Công nghệ 3 T14C Văn sử Xã hội Quan hệ sinhvien Svid Hoten Ns Qq Diachi lopid T14A1 Phạm Thị Mai 1/12/1988 Kim Sơn Chính Tâm, KS 1 T14A2 Trần Văn Giang 4/5/1989 Nho quan Gia Sinh, NQ 1 T14B1 Lê Văn Chính 3/3/1988 Yên Khánh Khánh Nhạc, YK 2 T14B2 Phạm Thu Thuỷ 7/4/1989 Hoa Lư Ninh Hoà, HL 2 Quan hệ sinhvien_lop Svid Hoten Ns Qq Diachi lopi Tenlop Nganhho khoa d c T14A Phạm Thị Mai 1/12/1 Kim Chính Tâm, 1 T14A Hoá sinh Tự 47
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 1 988 Sơn KS nhiên T14A Trần Văn Giang 4/5/19 Nho Gia Sinh, NQ 1 T14A Hoá sinh Tự 2 89 quan nhiên T14B Lê Văn Chính 3/3/19 Yên Khánh Nhạc, 2 T14B Tin Công 1 88 Khánh YK nghệ T14B Phạm Thu Thuỷ 7/4/19 Hoa Ninh Hoà, 2 T14B Tin Công 2 89 Lư HL nghệ - Dị thường thêm bộ: Có 2 loại dị thường thêm bộ  Khi thêm sinh viên mới vào lớp thì tất cả các bộ mới thêm đều phải có thông tin về lớp chẳng hạn thêm sinh viên vào lớp có mã lớp = 2 thì tất cả các bộ thêm vào đều phải có tên lớp = T14B, ngành học Tin, khoá hoc 2007-2010, nếu điều kiện này không thoả mãn thì tính nhất quán bị phá vỡ. Trong trường hợp dùng 2 bảng thì ta chỉ cần lopid mà không phải quan tâm đến vấn đề khác.  Khi cần thêm lớp mới mà lớp này chưa có sinh viên nào thì ta phải bỏ trống các trường thông tin về sinh viên, tuy nhiên điều đó là không chấp nhận được vì ít nhất svid là khoá chính không được phép null, nếu dùng 2 bảng thì ta chỉ cần thêm vào bảng lop là xong. - Dị thường xoá bộ: Nếu ta xoá một bộ nói về sinh viên duy nhất còn lại của lớp thì toàn bộ thông tin về lớp đó bị mất, khi dùng 2 bảng ta giải quyết được vấn đề đó. - Dị thường sửa bộ: Khi ta muốn chuyển lớp sang khoa khác quản lý sẽ phải sửa tất cả các bộ có chứa sinh viên về lớp này, nếu dùng 2 bảng ta chỉ phải sửa một lần Tuy nhiên, việc tách thành nhiều bảng cần phải thoả điều kiện không làm mất thông tin và bảo toàn các ràng buộc quan trọng. 48
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 2. Phụ thuộc hàm (Function Defendency-FD) 2.1. Đặt vấn đề Phụ thuộc hàm là một khái niệm dùng để mô tả các ràng buộc dữ liệu trong một cơ sở dữ liệu chẳng hạn để chỉ ràng buộc mỗi giáo viên chỉ dạy một môn học: giáo viên -> môn dạy. 2.2. Định nghĩa phụ thuộc hàm Cho quan hệ R(U). X, Y là các tập con của U. Ta nói rằng Y phụ thuộc hàm vào X (hay X xác định Y), được viết X Y. Nếu  t1,t2 R mà t1[X]=t2[X] thì t1[Y]=t2[Y] VD: Cho quan hệ sinhvien như sau: SVID Ho_ten NgaySinh QueQuan LopID C2701 Nguyễn Vân Anh 15/7/89 Hoa Lư T13B C2702 Hoàng Thị Bình 18/9/88 Yên Khánh T13B C2703 Trần Thị Tuyết 8/5/89 Kim Sơn T13B C2704 Lã Thị Vân 9/12/88 TP Ninh Bình T13B Trong ví dụ trên thì các thuộc tính Ho_ten, NgaySinh, QueQuan phụ thuộc hàm vào SVID. 2.3. Hệ tiên đề Amstrong Cho quan hệ R(U). X, Y, Z là tập con của U. Khi đó ta có A1: Tính phản xạ (reflexivity). Nếu YX thì X Y A2: Tính tăng trưởng (Augmentation). Nếu X Y thì XZ YZ (XZ=XZ) A3: Tính bắc cầu (Transitivity): Nếu X Y và Y Z thì X Z Tính phản xạ phát biểu rằng một tập hợp các thuộc tính luôn luôn xác định chính nó hoặc một tập con bất kỳ của nó. Vì A1 tạo ra các phụ thuộc luôn luôn đúng, những phụ thuộc như vậy được gọi là tầm thường. Một cách hình thức, một phụ thuộc hàm X Y là tầm thường nếu XY, ngược lại, nó được gọi là không tầm thường. Tính tăng trưởng nói rằng việc thêm cùng một tập thuộc tính vào cả hai vế của một phụ thuộc hàm sẽ tạo ra một phụ thuộc hàm đúng đắn. Theo tính A3, các phụ thuộc hàm là bắc cầu. Chứng minh hệ tiên đề Armstrong, ta chứng minh bằng phản chứng dựa trên định nghĩa phụ thuộc hàm. 49
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học A1: Giả sử X Y và 2 bộ t1 và t2 là các thể hiện quan hệ r của R sao cho t1[X]=t2[X]. Khi đó t1[Y] = t2[Y] bởi vì X Y, như vậy X Y phải xảy ra trong r. A2: Giả sử X Y đúng trong một thể hiện quan hệ r của R nhưng XZ YZ không đúng. Khi đó có hai bộ t1 và t2 trong r sao cho: t1[X] = t2[X], t1[XZ] = t2[XZ] t1[Z] = t2[Z] t1[Y] = t2[Y] t1[YZ] = t2[YZ], mẫu thuẫn với giả thiết. A3: Giả sử X Y, Y Z nhưng không có X Z. t1,t2 là 2 bộ của r, khi đó t1[X] = t2[X] và X Y nên t1[Y] = t2[Y] vì Y Z nên t1[Z] = t2[Z], mẫu thuẫn với giả thiết. 2.4. Các luật suy ra từ hệ tiên đề Luật 1: L1: Luật hợp (Union): Nếu X Y và X Z thì X YZ Luật 2: L2: Luật tựa bắc cầu (Pseudotransitivity): Nếu X Y và YW Z thì XW Z Luật 3: L3: Luật tách (Decompisition): Nếu X Y, ZY thì X Z Sinh viên tự chứng minh các luật dựa theo các tích chất trong hệ tiên đề Amstrong. 2.5. Bao đóng của 1 tập phụ thuộc hàm - Định nghĩa 1 phụ thuộc hàm được suy dẫn logic từ một tập phụ thuộc hàm: Cho quan hệ r(U), F là một tập phụ thuộc hàm phát biểu trên U. X, YU. X->Y Là một phụ thuộc hàm phát biểu trên U. Khi đó ta nói rằng phụ thuộc hàm X->Y được suy dẫn logic từ F nếu mỗi quan hệ r(U) được xác định trên U thoả F thì r cũng thoả X->Y F Ký hiệu X  Y - Định nghĩa bao đóng của 1 tập phụ thuộc hàm là một tập phụ thuộc hàm ký hiệu F+ = {X->Y | X->Y được suy dẫn logic từ F}. Việc tính toán bao đóng rất khó khăn và mất thời gian nên ta chỉ định nghĩa hình thức. Nếu F+ = F thì F được gọi là họ phụ thuộc hàm đầy đủ. - VD Cho lược đồ quan hệ r(U) với U={A,B,C,D,E,F,G,H}. Và tập phụ thuộc hàm F={AB->C, C->DE, E->F, AF->H} 50
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học + Hỏi phụ thuộc hàm AB->H có được suy dẫn logic từ F không? + Hỏi phụ thuộc hàm AB->GH có được suy dẫn logic từ F không? - Trả lời: (Sử dụng các luật và các tính chất từ F để suy ra các phụ thuộc hàm đó. Nếu không suy ra được thì coi như không được suy dẫn logic từ F). C D L3 A3 C DE E F C F  A3 C E   AB F + AB C  AB A L1 AB AF AF H A3 AB H Vậy AB->H được suy dẫn lgic từ F + Trong các phụ thuộc hàm của F không có phụ thuộc hàm nào suy ra G nên AB-> G không được suy dẫn logic từ F 2.6. Bao đóng của 1 tập thuộc tính Cho lược đồ quan hệ R(U, F), XU, F là tập phụ thuộc hàm xác định trên U. Ta định nghĩa bao đóng của 1 tập thuộc tính X đối với tập phụ thuộc hàm F là tập thuộc tính được xác định như sau X+={A | (X A F+} Thuật toán tìm bao đóng của tập thuộc tính X Input: Lược đồ quan hệ R(U), Tập thuộc tính X là con của U Tập phụ thuộc hàm F xác định trên U Output: X+={A | X A F+} Action: Bước 1: Đặt X(0)=X Bước 2: X i 1  A Nếu  (Y Z) F mà A Z và YXi-1 X i i 1 X Nếu ngược lại Bước 3: Nếu Xi=Xi-1 thì dừng, Xi chính là X+ cần tìm - VD1: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,F,G,H}. Và tập phụ thuộc hàm F={A BC, B E, CE GH} Cho X=AD. Tìm bao đóng X+ Đặt X0=X=AD 51
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học X1=ABD vì A BC nên A B X2=ABCD vì A BC nên A C X3=ABCDE vì B E X4=ABCDEG vì CE GH nên CE G X5=ABCDEGH vì CE GH nên CE H X6=X5 dừng. Vậy X+=ABCDEGH - VD2: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,G}. Và tập phụ thuộc hàm F= { AB C, C A, BC D, D EG, BE C, CG BD, ACD B, CE AG } Cho X=BD. Tìm bao đóng X+ Đặt X0=X=BD X1=BDEG vì D EG X2=BCDEG vì BE C X3=ABCDEG vì C A X4=X3 Vậy X+=ABCDEG Bổ đề: X Y thì YX+ Sử dụng bổ đề để kiểm tra X Y hay không Bước 1: Tính X+ Bước 2: Kiểm tra YX+ hay không đúng thì X Y, sai thì X Y - VD3: Cho lược đồ quan hệ R(U, F) với U={A,B,C,D,E,G,H,I}. Và tập phụ thuộc hàm F={A D, AB E, BI E, CD I, E C} X=AE I không? Tìm bao đóng X+ Đặt X0=X=AE X1=ADE vì A D X2=ACDE vì E C X3=ACDEI vì CD I X4=X3 Vậy X+=ACDEI 52
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học IX+ Vậy X I 2.7. Định nghĩa khoá và siêu khoá theo ngôn ngữ phụ thuộc hàm Cho lược đồ quan hệ R(U, F), F là tập phụ thuộc hàm xác định trên U. K là một tập con của U (KU), Khi đó: + K được gọi là siêu khoá của R nếu K U + K là khoá của R nếu K U và K’ K thì K’ U Thuật toán tìm 1 khoá Input: Lược đồ quan hệ R(U, F), Tập thuộc tính U, Tập phụ thuộc hàm F={Ti Pi | Ti,Pi U, TiWPi =, i=1 n} Output: K là tập con của U sao cho K là khoá của R Action: Đặt P= Pi Bước 1: Đặt K0=U \ P (những thuộc tính không nằm trong vế phải FD) Bước 2: Nếu K0+ = U thì chuyển Bước 5 Bước 3: K1:=K0  (T  P) Bước 4: Với mỗi Ai TP ta thực hiện i-1 + Tính K i 1 \ A  Nếu (K \{Ai}) = U K i i i 1 Ngược lại K Bước 5: Kết luận Ki là khoá VD1: Cho lược đồ quan hệ r(U) với U={A,B,C,D,E,F,G,H} F={A BC,B E,CE GH} Tìm 1 khoá của R Đặt: P=BCEGH K0=U \ P = ADF Tính (K0)+ =ABCDEFGH Kết luận ADF là một khoá của R VD2: Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,F,G,H} F={AB CD, C D, E FG, AE H} Tìm 1 khoá của R Đặt: P=CDFGH Tính :K0=U \ P =ABE, (ABE)+=U Kết luận ABE là khoá của R VD3:Cho lược đồ quan hệ R(U) với U={A,B,C} 53
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học F={AB C, C B} Tìm 1 khoá của R Đặt P=BC K0=A tính A+=A U K1=A  BC K2=A B (AB)+ =ABC=U, vậy AB là một khoá của R VD4:Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,G} F={AB C, G A, C B, ABD E} Tìm 1 khoá của R Đặt P=ABCE K0=U \ P = DG tính DG+ = ADG U K1= DG  ABC K2= DG AB, (ABDG)+ =ABCDEG = U vậy bỏ được C K3= DG A, (ADG)+=ADG U, không bỏ được B, K3=K2 K4=DG B, (BDG)+=ABCDEG=U vậy bỏ được A Kết luận BGD là một khoá của R. Thuật toán tìm mọi khoá của một quan hệ: Input: Lược đồ quan hệ R(U,F) Output: Tập KR tất cả các khoá của lược đồ R Ý tưởng: Thực hiện như thuật toán tìm một khoá nhưng thay đổi thứ tự bớt các thuộc tính Ai Giả mã: 1. Đặt T=Ti và P=Pi 2. KR:={K | K là khóa của lược đồ R(U,F) và K chứa trong siêu khóa (U\P) (TP)} 3. For each K in KR do 4. For each (Ti Pi) in F do 5. M:=Ti (K\Pi); 6. Test:=true; 7. for each H in KR do 8. if H  M then test:=false; 9. If test then KR:= KR  {K | K là khóa của R(U,F) và K chứa trong T} 54
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 10. end (4) 11. end; (3) 12. Return KR VD1: Xét lại VD3 ở trên Cho lược đồ quan hệ R(U) với U={A,B,C} F={AB C, C B} Tìm mọi khoá của R Đặt P=BC K0=A tính A+=A U K1=A  BC K2=A B (AB)+ =ABC=U, bỏ được C, vậy AB là một khoá của R, K2’=A C (AC)+=ABC=U, bỏ được B, vậy AC là một khoá của R Kết luận R có 2 khoá là AB và AC VD2: Xét lại VD4 ở trên Cho lược đồ quan hệ R(U) với U={A,B,C,D,E,G} F={AB C, G A, C B, ABD E} Tìm mọi khoá của R Đặt P=ABCE K0=U \ P = DG tính DG+ = ADG U K1= DG  ABC K2= DG AB, (ABDG)+ =ABCDEG = U vậy bỏ được C K3= DG A, (ADG)+=ADG U, không bỏ được B, K3=K2 K4=DG B, (BDG)+=ABCDEG=U vậy bỏ được A, DGB là một khoá của R K2’= DG BC, (BCDG)+ =ABCDEG = U vậy bỏ được A K3= DG C, (DGC)+=ABCDEG=U vậy bỏ được B, DGC là một khoá của R. Kết luận R có 2 khoá là DGB, DGC Chú ý: Thuật toán tìm mọi khóa cải tiến Input: Lược đồ quan hệ R(U, F), Tập thuộc tính U, Tập phụ thuộc hàm F={Ti->Pi | Ti,Pi U, TiWPi =, i=1 n} Output: Mọi Ki là tập con của U sao cho Ki là khoá của R Action: Đặt P= Pi 55
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Bước 1: Đặt K0=U \ P (những thuộc tính không nằm trong vế phải FD) Bước 2: Nếu K0+ = U thì K0 là khóa duy nhất và kết thúc Bước 3: K1:=K0 Bước 4: Với mỗi Ai TP ta thực hiện i-1 + Tính K i 1 Nếu (K ) = U K i i 1 Ngược lại K  Ai  Bước 5: Kết luận các (Ki )+ là các khoá của lược đồ 2.8. Tập phụ thuộc hàm tối thiểu  Các tập phụ thuộc hàm tương đương ? ĐN bao đóng của tập phụ thuộc hàm - Hai phụ thuộc hàm gọi là tương đương nếu F +=G+ (nói cách khác F phủ G và G phủ F) - Ký hiệu FG Kiểm tra 2 tập phụ thuộc hàm có tương đương hay không + Lấy mỗi phụ thuộc hàm X Y F kiểm tra X Y G+ không? + Lấy mỗi phụ thuộc hàm X’ Y’ G kiểm tra X’ Y’ F+ không? VD: Cho quan hệ r(U) với U={A,B,D,E,F,G} F={A BC, D E, AD F} G={A B, A C, D E, AD F} Kiểm tra FG? + Kiểm tra mỗi phụ thuộc hàm G có thuộc F+ hay không Kiểm tra A B, ta có A BC nên A B F vậy A B F+ Kiểm tra A C, ta có A BC nên A C F vậy A C F+ Kiểm tra D E và AD F đều thuộc F Vậy F phủ G + Kiểm tra mỗi phụ thuộc hàm F có thuộc G+ hay không Kiểm tra A BC, ta có A B, và A C nên A BC F vậy A BC G+ Kiểm tra D E và AD F đều thuộc F Vậy G phủ F Kết luận FG 56
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học  Tập phụ thuộc hàm tối thiểu: Tập phụ thuộc hàm F được gọi là tối thiểu nếu nó thoả mãn 3 điều kiện sau: F không dư thừa phải  mỗi phụ thuộc hàm của F đều không dư thừa phải  mỗi phụ thuộc hàm của F có vế phải chỉ gồm 1 thuộc tính F không dư thừa phụ thuộc hàm  không tồn tại phụ thuộc hàm dạng X Y sao cho (F-{X->Y}+=F+ F không dư thừa trái  mọi phụ thuộc hàm F không dư thừa trái. Dư thừa trái nghĩa là X Y nếu  A X mà (X-{A}) Y. Định lý: Mỗi tập phụ thuộc hàm F đều tương đương với 1 tập phụ thuộc hàm tối thiểu F’ nào đó. Khi đó F’ gọi là phủ tối thiểu của F Thuật toán: Tìm phủ tối thiểu của 1 tập phụ thuộc hàm Input: Cho lược đồ quan hệ R(U) Tập phụ thuộc hàm F (Li->Ri, i=1 m) Output: Phủ tối thiểu F’ của F Action: 1. Xác định tập phụ thuộc hàm F1  F. F1 không dư thừa phải. Nếu tồn tại phụ thuộc hàm dạng X A 1A2 An thì ta tách thành phụ thuộc hàm dạng X A1, X A2, X, An 2. Xác định tập phụ thuộc hàm F2  F1. F2 không dư thừa phụ thuộc hàm. Bước 2.0: Đặt F0=F1 Fi 1 Li Ri  nếu Fi-1\Li Ri Fi-1 Bước 2.i: Tính Fi nếu ngược lại Fi-1 Bước 3: Xác định tập phụ thuộc hàm F3 F2 không dư thừa trái. Bước 3.0: Đặt F0=F2 Bước 3.i: Tính Fi 1\ Li Ri  Zi Ri nếu ZiLi sao cho Fi-1\{Li Ri}  Fi {Zi Ri} Fi-1 Fi-1 Nếu ngược lại VD1: Cho lược đồ quan hệ r(U), U={A,B,C,D,E,F,G} F={A BC, D E, AD F} 57
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Tìm phủ tối thiểu của F + Xác định F1F, F1 không dư thừa phải F1={A B, A C, D E, AD F} + Xác định F2  F1 không dư thừa phụ thuộc hàm B0: Đặt F0=F1={A B, A C, D E, AD F} B1: Bỏ A B, A+=AC, không chứa B không bỏ được Bỏ A C, A+=AB, không chứa C không bỏ được Bỏ D E, không bỏ được Bỏ AD F, không bỏ được F2=F1 + Xác định F3F2, F3 không dư thừa trái B0: Đặt F0=F2={A B, A C, D E, AD F} B1: Chỉ phụ thuộc hàm AD F là có nhiều hơn 1 thuộc tính ở vế phải của phụ thuộc hàm. Ta bỏ A, kiểm tra D F, D+ = DE không chứa F, nên không bỏ được Ta bỏ D, kiểm tra A F, A+=ABC không chứa F, nên không bỏ được Kết luận: F’={A B, A C, D E, AD F} VD2: Cho lược đồ quan hệ R(U, F), U={A,B,C,D,E,F,G,H} F={A CD, C D, EG F, B H, E G}, tìm phủ tối thiểu của F + Xác định F1F, F1 không dư thừa phải F1={A C, A D, C D, EG F, B H, E G} + Xác định F2  F1 không dư thừa phụ thuộc hàm B0: Đặt F0=F1={A C, A D, C D, EG F, B H, E G} B1: Bỏ A C, A+=AD, không chứa C -> không bỏ được Bỏ A D, A+=CD chứa D, nên bỏ được FD A D Bỏ C D, không bỏ được Bỏ EG F, không bỏ được Bỏ B H, không bỏ được Bỏ E G, không bỏ được F2={A C, C D, EG F, B H, E G} + Xác định F3F2, F3 không dư thừa trái Xét FD EG F, bỏ E, G+=G không chứa F nên không bỏ được 58
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học bỏ G, E+=EGF chứa F nên bỏ được G F3={A C, C D, E F, B H, E G} Kết luận F’={A C, C D, E F, B H, E G} VD3: Cho lược đồ quan hệ R(U, F), U={A,B,C,D,E,F,G,H} F={AEF CD, A GH, EF B, G H}, tìm phủ tối thiểu của F + Xác định F1F, F1 không dư thừa phải F1={AEF C, AEF D, A G, A H, EF B,G H} + Xác định F2  F1 không dư thừa phụ thuộc hàm F2={AEF C, AEF D, A G, EF B,G H} + Xác định F3F2, F3 không dư thừa trái F3=F2={AEF C, AEF D, A G, EF B,G H} Kết luận F’={AEF C, AEF D, A G, EF B,G H} 3. Phép tách các lược đồ quan hệ 3.1. Khái niệm phép tách + Cho lược đồ quan hệ R(U). Tập các lược đồ =(R1(U1), R2(U2), , Rn(Un)) được gọi là phép tách của R nếu U1U2 Un=U Giả sử trên U có tập phụ thuộc hàm F, với ZU, hình chiếu F lên Z, ký hiệu Z(F), được xác định như sau: + Z(F)={(X Y) F | XYZ} khi đó ta ký hiệu phép chiếu F lên mỗi Ui là Fi, khi đó phép tách lược đồ R(U, F) như trên có thể viết là R 1(U1, F1), R2(U2,F2), , Rn(Un,Fn)) và ký hiệu =(R 1, R2, , Rn) + Mục đích của phép tách là tránh dư thừa dữ liệu, tránh trùng lặp dị thường, nhất quán dữ liệu. + VD Cho lược đồ quan hệ BANHANG (TênNCC, Địa chỉ, Sphẩm, giá) và tập phụ thuộc hàm F={TênNCC địa chỉ; TênNCC, sphẩm giá}. Khi đó ta có thể tách lược đồ quan hệ BANHÀNG thành 2 lược đồ quan hệ là NCC (TênNCC,Địa chỉ) tập phụ thuộc hàm F NCC = TênNCC địa chỉ và SẢNPHẨM (TênNCC,Sphẩm,giá) , Fsanpham={TênNCC, sphẩm giá} 59
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 3.2. Phép tách kết nối không tổn thất + ĐN: Phép tách R thành {R1,R2, Rn} gọi là tách kết nối không tổn thất (tách không mất thông tin - Lossless Join Decomposition – LJ) đối với tập phụ thuộc hàm F, nếu mỗi quan hệ r trên R thoả F, ta đều có r=r 1*r2* .*rn, trong đó ri = Ui(r) (ri là kết quả phép chiếu r trên Ui) + Tính chất không mất mát thông tin là cần thiết khi ta cần khôi phục quan hệ ban đầu từ các quan hệ đã tách Kiểm tra tính kết nối không tổn thất của 1 phép tách Input: Tập hữu hạn các thuộc tính U={A 1, A2, An}, tập phụ thuộc hàm F trên U và phép tách ={U1, U2, Uk}, Output: Kết luận có phải là phép tách kết nối không tổn thất hay không? Action: Lập bảng kích thước k n, trong đó k dòng lần lượt được đại diện bởi U1, U2, Uk và n cột được đại diện bởi A 1, A2, An. Tại dòng i cột j, ta ghi ký hiệu aj nếu Aj Ui, ngược lại thì ghi bij. Với mỗi phụ thuộc hàm X Y, ta xét các dòng có giá trị bằng nhau trên tập thuộc tính X, với cặp dòng như vậy ta thay ký hiệu các dòng này để chúng mang giá trị bằng nhau trên Y. Việc thay đổi được thực hiện theo quy tắc: - Nếu một trong 2 ký hiệu có dạng ai thì ký hiệu kia đổi thành ai - Nếu cả hai ký hiệu đều có dạng b ij thì lấy tuỳ ý một trong 2 ký hiệu đó gán chung cho cả hai. Lặp lại cho đến khi không còn thay đổi nào trên bảng, cuối cùng nếu có một hàng toàn ký hiệu ai thì kết luận phép tách kết nối không tổn thất, nếu không thì phép tách không là kết nối không tổn thất. VD1: quan hệ NCC(Ten, đc, sp, gia, soluong) với tập phụ thuộc hàm Ten đc, Ten,sp gia, soluong được tách làm 2 quan hệ CTY(Ten,đc) và CC(Ten,sp,gia,soluong) Thiết lập bảng ban đầu: Ten đc sp gia soluong CTY a1 a2 b13 b15 b15 CC a1 b22 a3 a4 a5 Xét phụ thuộc hàm ten đc ta thấy hàng 1 và hàng 2 cột ten cùng a1 nên trên cột đc ta đổi về cùng là a2 60
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Ta được bảng Ten đc sp gia soluong CTY a1 a2 b13 b15 b15 CC a1 a2 a3 a4 a5 Không còn biến đổi được bảng nữa ta thấy hàng 2 có toàn ký hiệu a nên phép tách này là phép tách kết nối không tổn thất Định lý 3.c: Nếu =(R1,R2) là một phép tách của R và F là tập phụ thuộc hàm thì Phép tách bảo toàn phụ thuộc là tách không mất thông tin đối với F khi và chỉ khi R1R2 R1-R2 hoặc R1R2 R2- R1 Xét lại ví dụ trên: R1R2 ={ten} R1-R2 ={đc}, rõ ràng ten đc nên phép tách kết nối không tổn thất. VD2: Cho lược đồ R(ABCDE), tập phụ thuộc hàm F gồm: A C, B C, C D, DE C, CE A Xét phép tách R thành R1(AD), R2(AB), R3(BE), R4(CDE), R5(AE) Ta có bảng khởi đầu như sau: A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b23 b24 b25 BE b31 a2 b33 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b53 b54 a5 Xét FD: A C, ta thấy hàng 1,2,5 của cột A cùng giá trị a1 ta sẽ thay thế ở cột C các hàng 1,2,5 để được cùng giá trị. Ta được bảng sau A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 b24 b25 BE b31 a2 b33 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b13 b54 a5 Xét FD: B C, hàng 2 và 3 của cột B cùng giá trị, ta thay đổi hàng 2,3 cột C để được các giá trị giống nhau A B C D E 61
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học AD a1 b12 b13 a4 b15 AB a1 a2 b13 b24 b25 BE b31 a2 b13 b34 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b13 b54 a5 Tương tự xét FD: C D, ta được bảng A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE b31 a2 b13 a4 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 b13 a4 a5 Xét FD: DE C, ta được bảng A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE b31 a2 a3 a4 a5 CDE b41 b42 a3 a4 a5 AE a1 b52 a3 a4 a5 Xét FD: CE A, ta được bảng A B C D E AD a1 b12 b13 a4 b15 AB a1 a2 b13 a4 b25 BE a1 a2 a3 a4 a5 CDE a1 b42 a3 a4 a5 AE a1 b52 a3 a4 a5 Đã xét hết các FD ta thấy hàng thứ 3 toàn là ký hiệu a i vậy phép tách kết nối không tổn thất. 3.3. Phép tách bảo toàn phụ thuộc - ĐN: Phép tách = {R1(U1), R2(U2), .Rm(Um)} của lược đồ R(U,F) được gọi là bảo toàn tập phụ thuộc hàm F nếu 62
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học m F F Ui (Phép tách đảm bảo rằng tập phụ thuộc hàm i 1 F được phủ bởi các hình chiếu Fi của nó lên Ui. - Hai tính chất kết nối không tổn thất và bảo toàn phụ thuộc là những tính chất quan trọng của phép tách lược đồ. - Ví dụ 1: Cho lược đồ quan R(ABCD) F={A B, C D} ta tách thành 2 lược đồ quan hệ R1(AB) R2(CD), kiểm tra phép tách phải là phép tách kết nối không tổn thất hay không? Và có phải là phép tách bảo toàn phụ thuộc hay không Ta thấy, phép tách chỉ tách R thành 2 quan hệ nên áp dụng định lý 3.c ta có R1R2= R1-R2. Vậy đây không là phép tách kết nối không tổn thất. Ta kiểm tra tính bảo toàn phụ thuộc. Tính F1, chiếu F lên R1 = {A B, B A} và các phụ thuộc hàm tầm thường ta không xét đến Tính F2, chiếu F lên R2={C D, D C} + Đương nhiên, ta thấy F  (F1F2) , vậy phép tách trên là bảo toàn phụ thuộc - Ví dụ 2: R(ABCDE), F={AB C, CD E} tách thành 3 lược đồ R1(AB), R2(CD), R3(DE), kiểm tra phép tách có bảo toàn phụ thuộc hay không Tính F1={A B,B A, AB A, AB B} Tính F2={C D, D C, CD D, CD C} Tính F3={D E, E D, DE E, DE D} + F (F1F2F3) nên phép tách là không bảo toàn phụ thuộc. 4. Chuẩn hoá lược đồ quan hệ 4.1. Các dạng chuẩn Việc chuẩn hoá CSDL mô hình quan hệ được E.F.Codd đưa vào năm 1972 với các dạng chuẩn được đặt tên là dạng chuẩn thứ nhất, dạng chuẩn thứ 2 và dạng chuẩn thứ 3.  Dạng chuẩn 1 - Định nghĩa 4.1: Một lược đồ quan hệ được gọi là thuộc dạng chuẩn 1 (First Normal Form – 1NF) nếu miền trị của mỗi thuộc tính đều thuộc kiểu nguyên tố, chứ không phải là một tập hợp hay một kiểu có cấu trúc phức hợp. 63
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Lược đồ quan hệ 1NF cũng được gọi là lược đồ chuẩn hoá. Thông thường sau quá trình phân tích thiết kế hệ thống thì lược đồ đã thuộc dạng chuẩn 1  Dạng chuẩn 2 - Định nghĩa Phụ thuộc hàm đầy đủ: Cho lược đồ quan hệ R(U,F), X,Y U. Ta nói rằng Y phụ thuộc hàm đầy đủ vào X nếu (X Y) F + và không có Z Y, ZX. + Nếu Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm đầy đủ thì ta nói Y phụ thuộc hàm bộ phận vào X. + Thuộc tính không khóa là thuộc tính không thuộc bất cứ khóa nào. - Định nghĩa 4.2: (Dạng chuẩn 2 – 2NF) Lược đồ quan hệ R được gọi là dạng chuẩn thứ 2 (2NF) nếu nó thuộc dạng chuẩn thứ nhất và mọi thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào khoá - Ví dụ 1: Cho lược đồ quan hệ R(SAIP) với các phụ thuộc hàm SI P và S A không là 2NF. Khoá của quan hệ là SI, A và P là 2 thuộc tính không khoá, ta thấy A chỉ phụ thuộc vào S mà không phụ thuộc I nên A phụ thuộc bộ phận vào khoá. - Ví dụ 2: Cho lược đồ quan hệ R(SAIP) với các phụ thuộc hàm SI A, SI P, R thuộc dạng chuẩn 2.  Dạng chuẩn 3 - Định nghĩa Phụ thuộc bắc cầu: Cho lược đồ quan hệ R(U,F), X là tập con của U, A là một thuộc tính thuộc U. A được gọi là phụ thuộc bắc cầu vào X trên R, nếu tồn tại một tập con Y của U sao cho X Y, Y A nhưng Y X với A XY - Định nghĩa 4.3: (Dạng chuẩn thứ 3 – 3NF): Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 3 nếu nó thuộc dạng chuẩn thứ 2 và mọi thuộc tính không khoá đều không phụ thuộc hàm bắc cầu vào khoá chính - Ví dụ: Cho lược đồ quan hệ R(SIDM) và các phụ thuộc hàm SI D, SD M, khoá là SI, rõ ràng R ở 2NF nhưng không ở 3 NF vì M phụ thuộc bắc cầu vào khóa.  Dạng chuẩn Boyce-Codd (BCNF) 64
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Dạng chuẩn thứ 3 loại bỏ những phụ thuộc hàm bắc cầu của những thuộc tính không khoá vào khoá chính. Nhưng nếu lược đồ quan hệ mà có phụ thuộc hàm bắc cầu giữa những thuộc tính khoá thì vẫn xảy ra dị thường thao tác dữ liệu. Dạng chuẩn Boyce Codd là dạng chuẩn mạnh hơn theo nghĩa loại bỏ những dị thường đó. - Định nghĩa 4.5: Lược đồ quan hệ R chuẩn hoá với tập phụ thuộc hàm F được gọi là thuộc dạng chuẩn Boyce Codd (BCNF) nếu có X A đúng trên lược đồ R và A X thì X chứa một khoá của R (nói cách khác X là siêu khoá)  Định lý: Nếu lược đồ quan hệ R với tập phụ thuộc hàm F thuộc dạng chuẩn Boyce Codd thì nó cũng thuộc dạng chuẩn ba Chứng minh: Giả sử R thuộc BCNF và X là một khoá của R. Với mỗi thuộc tính A X, ta phải chứng minh A không phụ thuộc bộ phận vào X và cũng không phụ thuộc bắc cầu vào X. Ta sẽ chứng minh bằng phản chứng - Nếu A phụ thuộc bộ phận vào X thì tồn tại Y sao cho Y X sao cho Y A, do A X nên A Y vậy Y là siêu khoá, điều này mâu thuẫn với giả thiết X là khoá, Vậy A không phụ thuộc bộ phận vào X - Nếu A phụ thuộc bắc cầu vào X thì tồn tại Y sao cho A XY, X Y,Y A và có Y X, vì R thuộc BCNF nên A Y và Y A nên Y là siêu khoá của R vậy Y X, mâu thuẫn với giả thiết. 4.2. Phép tách kết nối không tổn thất thành BCNF  Thuật toán 1 Input: Lược đồ quan hệ R và tập phụ thuộc hàm F trên R Output: Phép tách kết nối không tổn thất R với các lược đồ thành dạng chuẩn BCNF Method: Ta sẽ xây dựng phép tách  qua các bước lặp sao cho ở mỗi bước  luôn là tách kết nối không tổn thất - Ban đầu  chỉ gồm R: ={R} - Việc lặp sẽ kết thúc khi  chỉ chứa các lược đồ ở dạng chuẩn BCNF. Trong trường hợp ngược lại, ta sẽ tìm được lược đồ S=(U s,Fs) trong  không ở dạng chuẩn BCNF với phụ thuộc hàm X A được thoả trên S, X không phải là khoá của S và A X 65
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Thay thế S bởi hai lược đồ với tập thuộc tính tương ứng là XA và Us\{A}. Quay trở lại bước trên để kiểm tra xem còn lược đồ nào không ở dạng chuẩn BCNF trong  hay không  Minh họa bằng sơ đồ: R(U) X A Khoá ≠X XA U\A (nếu có dạng A Z thì X A thay bằng X Z) Chuẩn BCNF Chưa chuẩn i  Ví dụ 1: Xét lược đồ quan hệ TKB (thời khoá biểu) gồm tập U các thuộc tính: C (lớp học phần), T (giảng viên), H (giờ học), R (phòng học), S (sinh viên), G (điểm), và tập các phụ thuộc hàm: C T (mỗi lớp do một giảng viên chịu trách nhiệm) HR C, tại mỗi phòng học trong mỗi giờ học chỉ có một lớp học phần HT R, tại mỗi giờ học mỗi giảng viên chỉ có thể dạy được tại một phòng học CS G, đối với mỗi lớp học phần, mỗi sinh viên chỉ có 1 điểm đánh giá HS R, tại mỗi giờ học, mỗi sinh viên chỉ có mặt ở một phòng học Ta tìm khoá của lược đồ quan hệ này. Khoá HS Kết quả phép tách được thực hiện theo sơ đồ sau 66
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học U=CTHRSG F={C T, HR C, TH R, CS G, HS R} Khoá HS U1=CT CHRSG C T HR C, CH R, CS G, HS R Khoá: C Khoá HS U2=CHR HRSG HR C, CH R HRS G , HS R Khoá HR, HC Khoá: HS Kết quả phép tách là (CT, HRC, HRSG)  Ví dụ 2: Xét lược đồ quan hệ BANHANG với tập thuộc tính U={SPTCQ} Trong đó S : Là mã số hàng hóa cung cấp P : Là mã số mặt hàng C : Là tên thành phố mà hãng cung cấp hàng đăng ký kinh doanh S : Là thứ hạng của thành phố Q : Là số lượng hàng hóa từng loại mà mỗi hãng cung ứng F={S CT, C T, SP Q} Kết quả phép tách được thực hiện theo sơ đồ sau: U=SPTCQ F={S CT, C T, SP Q} Khoá SP CT U1=SPCQ C T S C, SP Q Khoá C Khoá: SP SC SPQ S C SP Q 67 Khoá: S Khoá SP
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Kết quả: (CT, SPQ, SC) 4.3. Phép tách bảo toàn phụ thuộc hàm thành 3NF  Thuật toán 1 không đảm bảo sinh ra một phép tách bảo toàn phụ thuộc. Không phải bất kỳ lược đồ quan hệ nào cũng có thể được tách theo thuật toán này thành các lược đồ BCNF mà vẫn bảo toàn các phụ thuộc hàm của nó. Để đảm bảo đầu ra của phép tách là bảo toàn phụ thuộc đối với mọi lược đồ đầu vào, cần yêu cầu các lược đồ thành phần đầu ra chỉ là 3NF  Thuật toán 2: Tách bảo toàn phụ thuộc đưa lược đồ về dạng chuẩn 3NF Input: Lược đồ quan hệ R(U) với tập phụ thuộc hàm F trên R. Không mất tính tổng quát giả sử F tối thiểu Output: Phép tách bảo toàn phụ thuộc cho R sao cho mỗi lược đồ thành phần là 3NF cùng với tập phụ thuộc chiếu của F lên những lược đồ thành phần này. Method: - Nếu có những thuộc tính không xuất hiện trong bất cứ một phụ thuộc hàm nào của F (cả vế trái và vế phải) thì ta phải xác định một lược đồ quan hệ gồm những thuộc tính này rồi loại chúng ra khỏi U - Nếu một trong các phụ thuộc hàm của F chứa tất cả các thuộc tính của U thì phép tách cần phải tìm chỉ gồm R. - Trong trường hợp còn lại, kết quả gồm các lược đồ ứng với tập các thuộc tính có dạng XA, với mỗi phụ thuộc hàm X A thuộc F, nếu trong F có các phụ thuộc hàm có vế trái X A1, X A2, ,X Ak thì chúng ta có thể sử dụng lược đồ ứng với tập thuộc tính XA 1A2, Ak thay cho các lược đồ dạng XAi  Ví dụ: Xét lại ví dụ 1 trong phần b Vì F ={C T, HR C, HT R, CS G, HS R} là tối thiểu nên phép tách thu được theo thuật toán 2 là =(R1,R2,R3,R4,R5) trong đó R1=(CT,{C T}) R2=(HRC,{HR C}) R3=(HTR,{HT R}) R4=(CSG,{CS G}) R5=(HSR,{HS R}) Chú ý: Để tìm một phép tách vừa LJ vừa bảo toàn phụ thuộc Bước 1: Tìm phủ tối thiểu 68
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Bước 2: Tìm tách bảo toàn phụ thuộc (Đưa về 3NF) Bước 3: Tìm trong các lược đồ con, nếu không có một lược đồ con nào chứa khoá thì thêm vào 1 quan hệ chứa khoá. Kết chương Qua nội dung chương III, chúng ta đã biết được các khái niệm khóa, phụ thuộc hàm, được giới thiệu về hệ tiên đề Armstrong và các luật suy ra từ hệ tiên đề. Chương này cũng đã giới thiệu về các phép tách, các dạng chuẩn và phương pháp đưa lược đồ về dạng chuẩn nhất định. Câu hỏi và bài tập Câu hỏi: Câu 1.Nêu các khái niệm quan hệ, các phép toán của đại số quan hệ, cho ví dụ. Câu 2. Khái niệm phụ thuộc hàm, các tính chất của phụ thuộc hàm, cho ví dụ Câu 3. Khái niệm bao đóng của tập phụ thuộc hàm, bao đóng của tập thuộc tính, giải thuật tìm bao đóng của tập thuộc tính Câu 4. Khái niệm phủ tối thiểu, giải thuật tìm phủ tối thiểu Câu 5. Nêu khái niệm khoá theo ngôn ngữ phụ thuộc hàm, các giải thuật tìm khoá Câu 6. Khái niệm phép tách lược đồ quan hệ, cho ví dụ Câu 7. Nêu phép tách kết nối không tổn thất và giải thuật kiểm tra phép tách kết nối không tổn thất, cho ví dụ Câu 8. Nêu phép tách bảo toàn phụ thuộc và giải thuật kiểm tra phép tách bảo toàn phụ thuộc, cho ví dụ Câu 9. Định nghĩa các dạng chuẩn, cho ví dụ Câu 10. Định nghĩa dạng chuẩn 3 và phép tách bảo toàn phụ thuộc hàm về các lược đồ ở dạng chuẩn 3. Câu 11. Định nghĩa dạng chuẩn BCNF và phép tách kết nối không tổn thất về các lược đồ ở dạng chuẩn BCNF. Bài tập: Bài 1: Cho lược đồ quan hệ R(U,F) với U=ABCDE, F={A C, BC D, D E, E A} Tính: + a. (AB) F; + + b. (BD) F-D F 69
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Bài 2: Cho lược đồ quan hệ R(U,F) với U=ABCDEG, F={B C, AC D, D G, AG E} cho biết các phụ thuộc hàm sau đây có thuộc F+ không? a. AB G b. BD AD Bài 3:Tìm các phủ tối thiểu của lược đồ quan hệ R(U,F) với a. U=ABCDE, F={AB C, C D, D E} b. U=ABCD, F={AB C, D B, A B, C ABD} c. U=ABEIGH, F={AB E, AG I, BE I, E G, GI H} d. U=ABCDEGH, F={AB C, B D, CD E, CE GH, G A} e. U=ABCDEG và F={AB C, C A, BC D, ACD B, D EG, BE C, CG BD, CE AG} f. U=ABCDEG và F={A C, AB C, C DG, CD G, EC AB, EG C} Bài 4: Kiểm tra tính kết nối không tổn thất. a. Cho U=ABCDE, F={C A, C D, ACD BE} =(ABC, CDE) b. Cho R(U,F) với U=ABCDE và F={A C, B C, C D, DE C, CE A}, Phép tách =(AC, CD, BE, BC, AE) c. Cho lược đồ quan hệ R(U,F) với U=ABCDE và F={A CD, B C, DE C, CE A} phép tách =(AD, AB, BE, CDE, AE) d. Cho R(U,F) với U=ABCDEHIKL và F={AB D, DE H, IK L, LB C}, Phép tách =(ABC, CDEH, EHIKL) e. Cho R(U,F) với U=ABCDEF, F={AB C, C D, D E, DE F} Phép tách =(ABC, CD, DE, DEF) Bài 5: Hãy tìm mọi khoá của mỗi lược đồ quan hệ sau: a. R(U, F) U=ABCD, F={AB C, D B, A B, C ABD} b. R(U, F) U=ABCDEG, F={AB C, C D, D E, DE G} c. R(U, F) U=ABCDEG, F={AB C, C A, BC D, ACD B, D EG, BE C, CG BD, E G} Bài 6: Kiểm tra các phép tách sau có mất thông tin không, có bảo toàn phụ thuộc không? a. Cho R(U, F) Trong đó U=ABCD, F={AB C, D B, C ABD} và phép tách =(ABC, BCD) 70
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học b. Cho R(U, F) U=ABCDEG, F={AB C, C A, BC D, ACD B, D EG, BE C, CG BD, E G} và phép tách =(ABC, BCD, DEG) Bài 7: Cho lược đồ quan hệ R(U,F) với U=ABCDE, F={AB DE, E AD, D C} a. Tìm tất cả các khoá của lược đồ quan hệ R b. Xác định R ở dạng chuẩn nào c. Kiểm tra xem phép tách =(AB, CDE, AD) có phải là tách kết nối không tổn thất hay không? d. Tìm phép tách R thành các lược đồ ở dạng chuẩn 3 với điều kiện phép tách vừa là tách kết nối không tổn thất vừa là tách bảo toàn phụ thuộc Bài 8: Cho lược đồ quan hệ R(U, F) với U=ABCDEG, F={AB C, G A, C B, ABD E} tìm phép tách kết nối không tổn thất của R thành những lược đồ BCNF Bài 9: Cho lược đồ R(U, F) với U=BCDEGIKLM và F={C BDEIK, D B, K E} Tìm phép tách vừa là kết nối không tổn thất vừa là bảo toàn phụ thuộc hàm F của R thành các lược đồ 3NF. Bài 10: Cho lược đồ quan hệ R(U,F) với U=ABCDE, F={AB C, C B, C D, D E} a. Tìm tất cả các khoá của lược đồ quan hệ R b. Xác định R ở dạng chuẩn nào c. Tách sơ đồ quan hệ trên về BCNF kết nối không tổn thất d. Tìm phép tách R thành các lược đồ ở dạng chuẩn 3 với điều kiện phép tách vừa là tách kết nối không tổn thất vừa là tách bảo toàn phụ thuộc Bài 11: Cho lược đồ quan hệ R(U,F) với U=ABCDEFGH, F={AB C, AB D, C B, EF G, E H} a. Tìm tất cả các khoá của lược đồ quan hệ R b. Xác định R ở dạng chuẩn nào c. Tách sơ đồ quan hệ trên về BCNF kết nối không tổn thất d. Tìm phép tách R thành các lược đồ ở dạng chuẩn 3 với điều kiện phép tách vừa là tách kết nối không tổn thất vừa là tách bảo toàn phụ thuộc Bài 12: Thực hiện phép tách lược đồ quan hệ R(U, F) thành các lược đồ 3NF bảo toàn phụ thuộc hàm và kết nối không mất thông tin và phép tách R thành các lược đồ ở BCNF kết nối không mất thông tin. 71
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học a. U=ABCDEGH, F={AB C, C D, D E} b. U=ABCD, F={AB C, D B, A B, C ABD} c. U=ABCDEG, F={AB C, AC D} d. U= ABCDE, F={AB C, C D, D E} e. U=ABCDEGHI, F={AB C, B D, C E} f. U=ABCDE, F={AB C, B D, C E} Bài 13: Cho lược đồ quan hệ R(U, F) U=(MaKh, TenKh, DiaChi, GioiTinh, DienThoai, MaMH, TenMH, TenMH, Mau, DonGia, DvTinh, SoLuong, MuaBan, NgayMB) F={MaKh TenKh, DiaChi, GioiTinh, DienThoai; MaMH TenMH, TenMH, Mau, DonGia, DvTinh; MaKh,MaMH SoLuong, MuaBan, NgayMB} a. Tìm mọi khoá của lược đồ quan hệ b. R ở dạng chuẩn nào? c. Tách R thành các lược đồ ở BCNF kết nối không tổn thất và tách R thành các lược đồ ở 3NF bảo toàn phụ thuộc và kết nối không tổn thất Bài 14: Cho lược đồ quan hệ R(U, F) U=MaSV, TenSV, DiaChi, GioiTinh, Lop, MaMon, TenMon, SoDVHT, DTLan1, DTLan2, DTLan3) F={MaSV TenSV, DiaChi, GioiTinh, Lop; MaMon TenMon, SoDVHT; MaSV, MaMon DTLan1, DTLan2, DTLan3} a. Tìm mọi khoá của lược đồ quan hệ b. R ở dạng chuẩn nào? c. Tách R thành các lược đồ ở BCNF kết nối không tổn thất và tách R thành các lược đồ ở 3NF bảo toàn phụ thuộc và kết nối không tổn thất 72
Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG IV: MÔ HÌNH THỰC THỂ LIÊN KẾT (Entity Relationship Model) Mô hình thực thể liên kết hay gọi tắt là mô hình E – R. Đây là mô hình dữ liệu khái niệm bậc cao hỗ trợ cho việc thiết kế cơ sở dữ liệu, nhiều công cụ thiết kế cơ sở dữ liệu đã sử dụng các khái niệm của mô hình này. 1. Mô hình dữ liệu khái niệm bậc cao và quá trình thiết kế CSDL Quá trình thiết kế cơ sở dữ liệu: Bước 1: Tập hợp các yêu cầu và phân tích: Kết quả là tập hợp các yêu cầu của người dùng được ghi ở dạng súc tích Bước 2: Thiết kế khái niệm: Lựa chọn mô hình dữ liệu, chuyển các đặc tả yêu cầu của người dùng thành một lược đồ khái niệm bao gồm mô tả chi tiết về kiểu dữ liệu, các liên kết, các ràng buộc, các chức năng được thực hiện trên dữ liệu. Bước 3: Thiết kế logic: Thiết kế cài đặt CSDL bằng một HQTCSDL. Kêt quả của bước này là một mô hình dữ liệu thể hiện của một HQTCSDL Bước 4: Thiết kế vật lý: Gồm các cấu trúc lưu trữ bên trong và kiểu tổ chức tệp cho CSDL 73