CƠ SỞ DỮ LIỆU NÂNG CAO 1. Thông tin về giảng viên − Họ và tên: Dư Phương Hạnh − Chức danh, học hàm, học vị: ThS − Thời gian, địa điểm làm việc: Từ 8g đến 16h30g, P305, nhà E3, Khoa công nghệ thông tin, Đại học công nghệ, ĐHQGHN, 144 Xuân Thuỷ, Cầu Giấy, Hà Nội. − Địa chỉ liên hệ: P305, nhà E3, Khoa công nghệ thông tin, trường Đại học công nghệ, ĐHQGHN, 144 Xuân Thuỷ, Cầu Giấy, Hà Nội − Điện thoại: 7547813 Email: hanhdp@vnu.edu.vn. − Các hướng nghiên cứu chính: Cơ sở dữ liệu, Khai phá dữ liệu. Thông tin về các giảng viên khác − TS Nguyễn Tuệ, Khoa CNTT, E3, ĐHCN, ĐHQGHN, 144, Xuân Thuỷ, Cầu Giấy, Hà Nội. ĐT: 7547813. − TS. Nguyễn Ngọc Hóa, Khoa CNTT, E3, ĐHCN, ĐHQGHN, 144, Xuân Thuỷ, Cầu Giấy, Hà Nội. ĐT: 7547813. 2. Thông tin chung về môn học − − − − − − − − Tên môn học: Mã môn học: Số tín chỉ: Môn học: Cơ sở dữ liệu nâng cao Bắt buộc: Lựa chọn:  02  Các môn học tiên quyết: Nhập môn cơ sở dữ liệu, Nguyên lý hệ điều hành. Các môn học kế tiếp: Các yêu cầu đối với môn học (nếu có): Giờ tín chỉ đối với các hoạt động: • Nghe giảng lý thuyết: 20 • Làm bài tập trên lớp: 6 • Thảo luận: 4 • Thực hành ở PTN: 0 • Hoạt động theo nhóm: 0 • Tự học: 0 − Địa chỉ Khoa/ bộ môn phụ trách môn học: Bộ môn Các hệ thống thông tin, P304-305 nhà E3, ĐHQGHN, 144 đường Xuân Thuỷ, Cầu Giấy, Hà Nội. 3. Mục tiêu của môn học − Về kiến thức: Cung cấp cho sinh viên những kiến thức bổ sung về cơ sở dữ liệu bao gồm quy trình xây dựng một cơ sở dữ liệu thực tiễn, việc lưu giữ cơ sở dữ liệu trên bộ nhớ ngoài, việc thực hiện và tối ưu các truy vấn, kiểm tra cạnh tranh. − Về kỹ năng: Sinh viên có khả năng sử dụng hệ quản trị cơ sở dữ liệu SQL server để thực hàng các nội dung được học. 4. Tóm tắt nội dung môn học − − − − Giới thiệu các bước xây dựng một cơ sở dữ liệu thực tế Các phương tiện lưu giữ cơ sở dữ liệu và kỹ thuật tổ chức các file Quá trình xử lý truy vấn và tối ưu truy vấn Kiểm tra cạnh tranh 5. Nội dung chi tiết môn học Chương 1. Các bước xây dựng một cơ sở dữ liệu thực tế 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. Nghiên cứu ban đầu cơ sở dữ liệu Thiết kế cơ sở dữ liêu Cài đặt và nhập Kiểm tra và tính toán Thao tác Bảo trì và nâng cấp Chương 2. Lưu trữ cơ sở dữ liệu ở bộ nhớ ngoài 2.1. Các công cụ lưu trữ 2.1.1. Phân cấp bộ nhớ 2.1.2. Các công cụ lưu trữ phụ 2.2. Đặt các file lên đĩa từ 2.2.1. Bản ghi và các kiểu bản ghi 2.2.2. Các file, bản ghi có độ dài cố định và độ dài thay đổi 2.2.3. Phân khối các bản ghi và cách tổ chức kéo dài và không kéo dài 2.3. Phân phối các khối file trên đĩa 2.3.1. Đầu file 2.3.2. Các thao tác trên các file 2.3.3. Các file với các bản ghi không có thứ tự (heap file) 2.3.4. Các file với các bản ghi có thứ tự 2.3.5. Các kỹ thuật băm 2.4. Các cấu trúc chỉ mục 2.4.1. Các kiểu chỉ mục có thứ tự mức đơn 2.4.2. Chỉ mục chính 2.4.3. Chỉ mục cụm 2.4.4. Chỉ mục phụ 2.4.5. Cây cân bằng ( B-tree) Chương 3. Xử lý và tối ưu truy vấn 3.1. Các bước xử lý một truy vấn 3.2. Chuyển truy vấn SQL thành đại số quan hệ 3.3. Các thuật toán cơ bản thực hiện các phép toán của truy vấn 3.3.1. Sắp xếp ngoài 3.3.2. Thực hiện phép chọn 3.3.3. Thực hiện phép nối 3.3.4. Thực hiện phép chiếu và các phép toán tập hợp 3.3.5. Thực hiện các phép toán kết tập 3.3.6. Thực hiện phép nối ngoài 3.3.7. Các phép toán kết tập sử dụng đường ống (pipe) 3.4. Tối ưu truy vấn bằng phương pháp dự đoán ( heuristic) 3.4.1. Cây truy vấn và đồ thị truy vấn 3.4.2. Các biến đổi tương đương trong đại số quan hệ 3.4.3. Thuật toán tối ưu 3.5. Tối ưu truy vấn dựa trên chi phí 3.5.1. Các thành phần chi phí cho việc thực hiện truy vấn 3.5.2. Thông tin danh mục trong việc sử dụng các hàm giá 3.5.3. Một số hàm giá đối với các phép toán đại số quan hệ Chương 4. Kiểm tra cạnh tranh 4.1. Theo thứ tự và lập lịch thứ tự 4.1.1. Lập lịch 4.1.2. Lập lịch theo thứ tự 4.1.3. Lập lịch sắp thứ tự được 4.1.4. Hiệu quả của ngữ nghĩa giao tác 4.1.5. Ký hiệu đối với các giao tác và lập lịch 4.2. Va chạm – Tính xếp hàng theo thứ tự 4.2.1. Các va chạm 4.2.2. Đồ thị ưu tiên và đối với Va chạm- tính xếp hành theo thứ tự 4.2.3. Vì sao kiểm tra đồ thị ưu tiên làm việc 4.3. Áp đặt tính xếp hàng có thứ tự bằng các khoá 4.3.1. Khoá 4.3.2. Bộ lập lịch khoá 4.3.3. Khoá 2 pha 4.4. Các hệ thống khoá với nhiều kiểu khoá 4.4.1. Các khoá chia sẻ và riêng biệt 4.4.2. Ma trận tương hợp 4.4.3. Các khoá nâng cấp 4.4.4. Các khoá cập nhật 4.4.5. Các khoá gia tăng 4.5. Một kiến trúc cho một bộ lập lịch khoá 4.5.1. Một bộ lập lịch chèn các hành động khoá 4.5.2. Bảng khoá 4.6. Quản trị phân cấp của các phần tử cơ sở dữ liệu 4.6.1. Các khoá với nhiều hạt 4.6.2. Các khoá cảnh báo 4.6.3. Ảo ảnh và điều khiển phép chèn một cách đúng đắn 4.7. Giao thức cây 4.7.1. Động cơ cho khoá đựa trên cây 4.7.2. Các quy tắc đối với việc truy cập đến các dữ liệu có cấu trúc cây 4.7.3. Vì sao giao thức cây làm việc 4.8. Kiểm tra cạnh tranh bằng timestamps 4.8.1. Timestamps 4.8.2. Các ứng xử không có thứ tự vật lý 4.8.3. Vấn đề với dữ liệu rác 4.8.4. Các quy tắc đối với việc lập lịch dựa trên timestamps 4.8.5. Timestamps nhiều phiên bản 4.8.6. Timestamps và khoá 4.9. Kiểm tra cạnh tranh bằng xác nhận hợp lệ 4.9.1. Kiến trúc của một bộ lập lịch dựa trên xác nhận hợp lệ 4.9.2. Các quy tắc xác nhận hợp lệ 4.9.3. So sánh ba cơ cấu kiểm tra cạnh tranh. 6. Học liệu 6.1. Học liệu bắt buộc [1] Nguyễn Tuệ, Giáo trình nhập môn hệ cơ sở dữ liệu [2] Peter Rob, Carlos Coronel. Database system: Design, implementation and management. Wadsworth Publishing Company, 1993 6.2. Học liệu tham khảo [3] Ramez Elmarsi, Shamkant B Navathe. Fundamentals of Database Systems, Addison -Wesley ,2000 [4] Hector Garcia-Molina, Jeffrey D.Ullman, Jennifer Widom. Database System : The Complete book. Prentice Hall, 2002 7. Hình thức tổ chức dạy học 7.1. Lịch trình chung Hình thức tổ chức dạy học môn học Lên lớp Nội dung (ND) Lý thuyết Bài tập Thảo luận Thực hành, thí nghiệm, điền dã ... Tự học, tự nghiên cứu Tổng ND 1: Các bước xây dựng một cơ sở dữ liệu thực tế 2.0 ND 2: Lưu trữ cơ sở dữ liệu trên bộ nhớ ngoài 4.0 0.5 4.5 ND 3: Các cấu trúc chỉ mục 2.0 0.5 2.5 ND 4: Xử lý truy vấn 2.0 1.0 3.0 ND 5: Tối ưu truy vấn bằng phương pháp dự đoán 2.0 0.5 1.0 3.5 ND 6: Tối ưu truy vấn dựa trên chi phí 2.0 0.5 1.0 3.5 ND 7: Thi giữa kỳ 0.5 0.5 ND8: Kiểm tra cạnh tranh: theo thứ tự và lập lịch thứ tự 2.0 2.0 2.0 1.0 1.0 5.0 ND9: Kiểm tra cạnh tranh: Các kỹ thuật kiểm tra cạnh tranh 2.5 ND10: Ôn tập thi cuối kỳ 1.0 Cộng 20 0.5 1.0 3.5 1.0 6 4 30 7.2. Lịch trình tổ chức dạy học cụ thể Nội dung 1, tuần 1: Các bước xây dựng một cơ sở dữ liệu thực tế Hình thức tổ chức dạy học Thời gian, Nội dung chính địa điểm Lý thuyết Từ ...... đến Tại GĐ2 Yêu cầu SV chuẩn bị 6 bước xây dựng một cơ sở dữ liệu thực tế: - Nghiên cứu ban đầu - Thiết kế - Cài đặt và nhập - Kiểm tra và tính toán - Thao tác - Bảo trì, nâng cấp Bài tập Bài tập minh họa 6 bước nêu trên Thảo luận Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện hoặc ở nhà Tham khảo thêm các bước xây dựng một hệ thống thông tin (system development life cycle – SDLC) Ghi chú Nội dung 2, tuần 2+3: Lưu trữ cơ sở dữ liệu trên bộ nhớ ngoài Hình thức tổ chức dạy học Lý thuyết Thời gian, Nội dung chính địa điểm Từ ...... đến Tại GĐ2 - Các công cụ lưu trữ: + Phân cấp bộ nhớ + Các công cụ lưu trữ phụ - Đặt các file lên đĩa từ + Bản ghi và các kiểu bản ghi + Các file, bản ghi có độ dài cố định và độ dài thay đổi + Phân khối các bản ghi và cách tổ chức kéo dài và không kéo dài - Phân phối các khối file trên đĩa + Đầu file + Các thao tác trên các file + Các file với các bản ghi không có thứ tự (heap file) + Các file với các bản ghi có thứ tự - Các kỹ thuật băm + Băm trong + Băm ngoài đối với các file trên Yêu cầu SV chuẩn bị Ghi chú đĩa + Các kỹ thuật băm cho phép mở rộng file động Bài tập Từ ...... đến Tại GĐ2 Thảo luận Bài tập minh họa cho các nội dung trên Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà Đây là một nội dung khó, sinh viên cần tự đọc thêm các tài liệu bổ trợ, kể cả tài liệu về nguyên lý hệ điều hành nếu cần thiết, để có thể nắm vững các kiến thức được đề cập trong nội dung này Nội dung 3, tuần 4: Các cấu trúc chỉ mục Hình thức tổ chức dạy học Lý thuyết Thời gian, Nội dung chính địa điểm Từ ...... đến Tại GĐ2 Các cấu trúc chỉ mục: - các kiểu chỉ mục có thứ tự mức đơn; - chỉ mục chính; Yêu cầu SV Chuẩn bị Ghi chú - chỉ mục cụm; - chỉ mục phụ; - cây cân bằng (Btree) Bài tập Từ ...... đến Tại GĐ2 Thảo luận Các bài tập minh họa cho các cấu trúc chỉ mục nêu trên Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà Tham khảo thêm các cấu trúc chỉ mục khác thuộc họ cây B-tree, chẳng hạn cây B+, R-tree… Nội dung 4, tuần 5: Xử lý truy vấn. Hình thức tổ chức dạy học Lý thuyết Thời gian, Nội dung chính địa điểm Từ ...... đến Tại GĐ2 - Các bước xử lý một truy vấn - Chuyển truy vấn SQL thành đại số quan hệ - Các thuật toán cơ bản thực hiện các phép toán của truy vấn + Sắp xếp ngoài + Thực hiện phép Yêu cầu SV Chuẩn bị Ghi chú chọn + Thực hiện phép nối + Thực hiện phép chiếu và các phép toán tập hợp + Thực hiện các phép toán kết tập + Thực hiện phép nối ngoài + Các phép toán kết tập sử dụng đường ống (pipe) Bài tập Từ ...... đến Tại GĐ2 Thảo luận Các bài tập minh họa cho nội dung xử lý truy vấn Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà Nắm vững các bước xử lý truy vấn và các thuật toán được sử dụng để thực hiện các phép toán của truy vấn. Đây là nền tảng quan trọng để bắt đầu nội dung sau: tối ưu hóa truy vấn. Nội dung 5, tuần 6: Tối ưu truy vấn bằng phương pháp dự đoán Hình thức tổ chức Thời gian, Nội dung chính Yêu cầu SV Ghi dạy học Lý thuyết địa điểm Từ ...... đến Tại GĐ2 Chuẩn bị chú - Tối ưu truy vấn bằng phương pháp dự đoán (heuristic) + Cây truy vấn và đồ thị truy vấn + Các biến đổi tương đương trong đại số quan hệ + Thuật toán tối ưu Bài tập Từ ...... đến Bài tập minh họa tương ứng Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà Đọc thêm tài liệu để nắm vững phương pháp heuristic trong tối ưu hóa truy vấn Nội dung 6, tuần 7: Tối ưu truy vấn dựa trên chi phí Hình thức tổ chức dạy học Lý thuyết Thời gian, Nội dung chính địa điểm Từ ...... đến Tại GĐ2 - Tối ưu truy vấn dựa trên chi phí + Các thành phần chi phí cho việc Yêu cầu SV Chuẩn bị Ghi chú thực hiện truy vấn + Thông tin danh mục trong việc sử dụng các hàm giá + Một số hàm giá đối với các phép toán đại số quan hệ Bài tập Từ ...... đến Bài tập minh họa tương ứng Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà - Đọc thêm tài liệu để nắm vững phương pháp tối ưu hóa truy vấn dựa trên chi phí - So sánh các phương pháp Nội dung 7, tuần 8: Thi giữa kỳ (60’) Hình thức tổ chức dạy học Lý thuyết Thời gian, Nội dung chính địa điểm Từ ...... đến Tại GĐ2 Bài tập Từ ...... đến 6 nội dung đã học ở trên Yêu cầu SV chuẩn bị Ghi chú Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Ôn tập 6 nội dung đã học ở trên Tại thư viện, ở nhà Nội dung 8, tuần 9: Kiểm tra cạnh tranh: theo thứ tự và lập lịch thứ tự Hình thức tổ chức dạy học Lý thuyết Thời gian, địa điểm Từ ...... đến Tại GĐ2 Nội dung chính - Theo thứ tự và lập lịch thứ tự - Va chạm – Tính xếp hàng theo thứ tự + Đồ thị ưu tiên và đối với Va chạmtính xếp hành theo thứ tự - Áp đặt tính xếp hàng có thứ tự bằng các khoá + Bộ lập lịch khoá + Khoá 2 pha - Các hệ thống khoá với nhiều kiểu khoá + Các khoá chia sẻ và riêng biệt + Ma trận tương hợp Yêu cầu SV chuẩn bị Ghi chú + Các khoá nâng cấp + Các khoá cập nhật + Các khoá gia tăng - Kiến trúc cho một bộ lập lịch khoá - Quản trị phân cấp của các phần tử cơ sở dữ liệu - Giao thức cây + Động cơ cho khoá đựa trên cây + Các quy tắc đối với việc truy cập đến các dữ liệu có cấu trúc cây Bài tập Từ ...... đến Các bài tập minh họa tương ứng Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà Đây là một nội dung dài và tương đối phức tạp, yêu cầu sinh viên đọc thêm tài liệu tham khảo để củng cố kiến thức liên quan đến các nội dung kể trên Nội dung 9, tuần 10: Kiểm tra cạnh tranh: Các kỹ thuật kiểm tra cạnh tranh Hình thức tổ chức dạy học Lý thuyết Thời gian, địa điểm Nội dung chính Từ ...... - Kiểm tra cạnh tranh bằng timestamps đến Tại GĐ2 Bài tập Từ ...... đến Yêu cầu SV chuẩn bị Ghi chú - Kiểm tra cạnh tranh bằng xác nhận hợp lệ Các bài tập minh họa tương ứng Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà - Đọc thêm tài liệu để nắm vững các khái niệm và cơ chế kiểm tra cạnh tranh -So sánh các cơ cấu kiểm tra cạnh tranh. Nội dung 10, tuần 11: Ôn tập thi cuối kỳ Hình thức tổ chức dạy học Lý thuyết Thời gian, địa điểm Nội dung chính Từ ...... Toàn bộ các nội Yêu cầu SV chuẩn bị Ghi chú đến dung đã học ở trên Tại GĐ2 Bài tập Từ ...... đến Tại GĐ2 Thảo luận Từ ...... đến Tại GĐ2 Thực hành, thí nghiệm, điền dã, … Tự học, tự nghiên cứu Tại thư viện, ở nhà 8. Chính sách đối với môn học và các yêu cầu khác của giảng viên Yêu cầu và cách thức đánh giá, sự hiện diện trên lớp, mức độ tích cực tham gia các hoạt động trên lớp, các qui định về thời hạn, chất lượng các bài tập, bài kiểm tra…. − Chuẩn bị tốt các phần được giao tự học. − Có mặt trên lớp ít nhất là 21/30 giờ học − Bắt buộc tham dự bài kiểm tra giữa kỳ (điều kiện tham gia thi cuối kỳ). 9. Phương pháp, hình thức kiểm tra - đánh giá kết quả học tập môn học 9.1. Kiểm tra đánh giá định kỳ Nội dung STT Trọng số (%) [1] Kiểm tra - đánh giá giữa kỳ 30 [2] Thi cuối kỳ 70 Ghi chú 9.2. Tiêu chí đánh giá các loại bài tập 1. Bài tập về lý thuyết − − − − Trình bày tốt bản chất vấn đề yêu cầu, có mở rộng: Trình bày đúng bản chất vấn đề yêu cầu: Trình bày được vấn đề ở mức trung bình: Trình bày chưa đúng bản chất, nội dung: 100% số điểm của bài tập 80-90% 50-70% 0-40% 2. Bài tập về ứng dụng: − Làm tốt cả diễn giải và đáp số theo đáp án: − Viết đúng diễn giải, sai đáp số: − Chỉ viết được diễn giải: − Chỉ biết công thức, thay số đúng: − Làm sai, không làm được: − 9.3. Lịch thi, kiểm tra (kể cả thi lại) STT Nội dung thi, kiểm tra Lịch thi 100% 80-90% 60% 50% 0-40% Lịch kiểm tra Ghi chú 1. Nội dung 1 đến 6 Kiểm tra giữa kỳ (60 phút) 2. Toàn bộ 9 nội dung Thi cuối kỳ Theo lịch chung của Trường Thi lại Theo lịch chung của Trường 3.