TRƯỜNG ĐẠI HỌC HÀNG HẢI KHOA CÔNG NGH Ệ THÔNG TIN BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO Biên soạn: Th.S Nguyễn Trung Đức Hải Phòng – 2008 http://www.ebook.edu.vn BỘ GIAO THÔNG VẬN TẢI TRƯỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: HỆ THỐNG THÔNG TIN KHOA: CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO TÊN HỌC PHẦN MÃ HỌC PHẦN TRÌNH ĐỘ ĐÀO TẠO DÙNG CHO SV NGÀNH : CƠ SỞ DỮ LIỆU NÂNG CAO : 17406 : ĐẠI HỌC CHÍNH QUY : CƠNG NGHỆ THƠNG TIN HẢI PHỊNG - 2008 http://www.ebook.edu.vn Tên học phần: Cơ sở liệu nâng cao Bộ môn phụ trách giảng dạy: Hệ thống Thông tin Mã học phần: 17406 TS tiết 45 Lý thuyết 30 Thực hành/Xemina 15 Tự học Loại học phần: Khoa phụ trách: CNTT Tổng số TC: Bài tập lớn Đồ án môn học Điều kiện tiên quyết: Sinh viên phải học thi đạt học phần sau đăng ký học học phần này: Cơ sở liệu Mục tiêu học phần: Cung cấp kiến thức nâng cao mơ hình sở liệu quan hệ, phương pháp thiết kế sở liệu khác Nội dung chủ yếu: Giới thiệu hệ quản trị liệu; Các mơ hình mạng, mơ hình phân cấp; Điều khiển tương tranh hệ quản trị sở liệu; An toàn xử lý sai sót; Mơ hình sở liệu hướng đối tượng; Mơ hình sở liệu phân tán Nội dung chi tiết: PHÂN PHỐI SỐ TIẾT TÊN CHƯƠNG MỤC TS LT TH BT KT Chương Hệ quản trị sở liệu lịch sử phát 3 triển 1.1 Quan niệm CSDL 1.2 Ứng dụng hệ quản trị CSDL 1.3 Lịch sử hệ quản trị liệu Chương Mơ hình mạng, mơ hình phân cấp 3 2.1 Mơ hình mạng 2.1.1 Giới thiệu 2.1.2 Các khái niệm 2.2 Mơ hình phân cấp 2.2.1 Giới thiệu 2.2.2 Các khái niệm Chương Thiết kế sở liệu khái niệm 3 3.1 Giới thiệu 3.2 Trừu tượng hoá thiết kế CSDL 3.3 Các thuộc tính tương xứng lớp 3.4 Các mơ hình liệu 3.5 Mơ hình thực thể quan hệ Chương Điều khiển khai thác tương tranh 3 4.1 Giới thiệu 4.2 Một số khái niệm 4.3 Đặc tính khai thác khơng xung đột 4.3.1 Một số khái niệm 4.3.2 Khai thác có thứ tự 4.3.3 Đồ thị thứ tự thực giao tác Chương An toàn liệu xử lý sai sót 3 5.1 An tồn CSDL 5.1.1 Phạm vi an toàn liệu 5.1.2 Các yêu cầu bảo vệ CSDL 5.1.3 Các dạng sai sót 5.2 Các điều khiển an toàn liệu 5.2.1 Điều khiển luồng thông tin http://www.ebook.edu.vn TÊN CHƯƠNG MỤC 5.2.2 Điều khiển suy diễn 5.2.3 Điều khiển truy nhập Chương Đánh giá câu hỏi 6.1 Phân tích câu hỏi 6.1.1 Phân tích cú pháp 6.1.2 Phân tích ngữ nghĩa 6.2 Cấu trúc đại số câu hỏi 6.2.1 Cây đại số quan hệ 6.2.2 Các luật biến đổi đại số quan hệ 6.2.3 Các bước tối ưu đại số quan hệ 6.3 Phân rã câu hỏi Chương Cơ sở liệu hướng đối tượng 7.1 Giới thiệu hướng đối tượng 7.1.1 Các khái niệm hướng đối tượng 7.1.2 Mơ hình hố việc phân tích hướng đối tượng 7.1.3 Mơ hình hóa liệu 7.2 Ngun tác mơ hình hướng đối tượng 7.2.1 Mơ hình hố đối tượng 7.2.2 Phương pháp 7.2.3 Xác định dạng liệu 7.2.4 Các liên kết thừa kế lớp 7.2.5 Đa cấu áp đặt 7.2.6 Xác định tập đối tượng 7.2.7 Khía cạnh động 7.2.8 Lược đồ CSDL hướng đối tượng 7.3 Tính bền vững các đối tượng 7.3.1 CSDL hướng đối tượng 7.3.2 Quản lý tính bền vững 7.3.3 Kế thừa tính bền vững 7.3.4 Tính bền vững tham chiếu 7.3.5 Tích hợp với ngơn ngữ lập trình 7.4 Đại số với đối tượng phức tạp 7.4.1 Mở rộng đại số quan hệ theo đường dẫn phương pháp 7.4.2 Các phép tốn đại số 7.4.3 Các phép tốn nhóm 7.4.4 Đồ thị phép toán Chương Cơ sở liệu phân tán 8.1 Cấu trúc CSDL phân tán 8.2 Đánh giá CSDL phân tán 8.3 Thiết kế CSDL phân tán 8.3.1 Bản liệu 8.3.2 Chia nhỏ liệu 8.4 Tính thơng suốt tính tự trị CSDL phân tán 8.5 Xử lý câu hỏi 8.6 Khơi phục sai sót CSDL phân tán PHÂN PHỐI SỐ TIẾT TS LT TH BT KT 12 15 Nhiệm vụ sinh viên: Tham dự buổi học lý thuyết thực hành, làm tập giao, làm kiểm tra kỳ thi kết thúc học phần theo quy định http://www.ebook.edu.vn Tài liệu học tập: Nguyễn Xuân Huy, Giáo trình sở liệu, Đại học Quốc Gia Hà Nội, 2000 Nguyễn Xuân Huy-Lê Hoài Bắc, Bài tập sở liệu, Nhà xuất Thống kê, 2003 Phạm Hữu Khang, Đoàn Thiện Ngân, Quản trị SQL Server 2000, Nhà xuất Thống kê, 2004 Hình thức tiêu chuẩn đánh giá sinh viên: - Hình thức thi: thi viết - Tiêu chuẩn đánh giá sinh viên: dựa thái độ tham dự buổi học lý thuyết thực hành, kết làm tập giao, kiểm tra kỳ thi kết thúc học phần Thang điểm: Thang điểm chữ A,B,C,D,F Điểm đánh giá học phần: Z=0,3X+0,7Y Bài giảng tài liệu thức thống Bộ môn Hệ thống Thông tin, Khoa Công nghệ Thông tin dùng để giảng dạy cho sinh viên Ngày phê duyệt: Trưởng Bộ môn / / http://www.ebook.edu.vn MỤC LỤC Chương Hệ quản trị sở liệu 1.1 Quan niệm CSDL 1.2 Các khả hệ quản trị sở liệu Chương Cơ sở liệu hướng đối tượng 2.1 Nhu cầu hệ thống sở liệu hướng đối tượng 2.1.1 Các đối tượng phức tạp 2.1.2 Quản lý tri thức 2.1.3 Quản trị liệu phân tán 10 2.1.4 Nhu cầu hệ thống sở liệu hướng đối tượng 10 2.2 Khái niệm hướng đối tượng 11 2.2.1 Đối tượng 12 2.2.2 Lớp đối tượng 12 2.2.3 Cá thể 13 2.2.4 Kế thừa 13 2.3 Cơ sở liệu hướng đối tượng 13 2.4 Thiết kế sở liệu hướng đối tượng 14 2.4.1 Phân lớp 14 2.4.2 Tổng quát hóa đặc biệt hóa 14 2.4.3 Gộp 15 2.5 Xây dựng sở liệu hướng đối tượng 15 Chương Cơ sở liệu phân tán 17 3.1 Các phương pháp phân tán liệu 17 3.1.1 Khái niệm phân tán liệu 17 3.1.1.1 Các lý phân mảnh 17 3.1.1.2 Các kiểu phân mảnh 17 3.1.1.3 Mức độ phân mảnh 19 3.1.1.4 Quy tắc phân mảnh đắn 19 3.1.1.5 Các kiểu cấp phát 19 3.1.1.6 Các yêu cầu thông tin 19 3.1.2 Phân mảnh ngang 20 3.1.2.1 Yêu cầu thông tin phân mảnh ngang 20 3.1.2.2 Phân mảnh ngang nguyên thủy 21 3.1.2.3 Phân mảnh ngang dẫn xuất 23 3.1.3 Phân mảnh dọc 24 3.1.4 Cấp phát 24 3.2 Kiểm soát liệu ngữ nghĩa 26 3.2.1 Quản lý khung nhìn 26 3.2.1.1 Khung nhìn quản lý tập trung 26 3.2.1.2 Cập nhật qua khung nhìn 26 3.2.1.3 Khung nhìn sở liệu phân tán 27 3.2.2 An toàn liệu 27 3.2.2.1 Kiểm soát cấp quyền tập trung 27 3.2.2.2 Kiểm soát cấp quyền phân tán 28 3.3 Quản lý giao dịch điểu khiền đồng thời phân tán 28 3.3.1 Các khái niệm giao dịch 28 3.3.1.1 Tính nguyên tử 29 3.3.1.2 Mục liệu 29 http://www.ebook.edu.vn 3.3.1.3 Khóa 30 3.3.1.4 Kiểm sốt hoạt động đồng thời khóa 30 3.3.1.5 Khóa sống (livelock) 31 3.3.1.6 Khóa “cứng” (deadlock) 31 3.3.1.7 Tính khả lịch biểu 32 3.3.1.8 Bộ xếp lịch 33 3.3.1.9 Nghi thức 33 3.3.2 Mơ hình giao dịch đơn giản 33 3.3.2.1 Ý nghĩa giao dịch – hàm đặc trưng 33 3.3.2.2 Kiểm tra tính khả đồ thị có hướng 35 3.3.3 Nghi thức khóa pha 35 3.3.4 Mô hình khóa đọc khóa ghi 36 3.3.4.1 Ý nghĩa giao dịch với khóa đọc khóa ghi 36 3.3.4.2 Đồ thị hóa giao dịch Rlock Wlock 36 Chương Hệ trợ giúp định 38 4.1 Giới thiệu hệ trợ giúp định 38 4.2 Thiết kế sở liệu cho hệ trợ giúp định 39 4.2.1 Thiết kế logic 39 4.2.2 Thiết kế vật lý 40 4.3 Kho liệu kho liệu chuyên đề 40 4.3.1 Kho liệu 41 4.3.2 Kho liệu chuyên đề 41 4.3.3 Các lược đồ chiều 42 4.4 Xử lý phân tích trực tuyến 43 4.4.1 Giới thiệu 43 4.4.2 Bảng chéo 43 4.4.3 Cơ sở liệu nhiều chiều 44 4.5 Khai phá liệu 44 http://www.ebook.edu.vn Chương Hệ quản trị sở liệu 1.1 Quan niệm Cơ sở liệu Cơ sở liệu (CSDL) gì? Định nghĩa: Một sở liệu (Database) tập hợp có cấu trúc liệu tác nghiệp lưu trữ lại hệ ứng dụng cụ thể sử dụng Ngày CSDL tồn hầu hết ứng dụng, ví dụ: - Ứng dụng quản lý kho hàng; - Hệ thống đặt chỗ máy bay; - Quản lý nguồn nhân lực… Hệ quản trị sở liệu gì? Định nghĩa: Hệ quản trị sở liệu (Database Management System - DBMS) hệ thống phần mềm cho phép tạo lập CSDL điều khiển truy nhập CSDL Hệ sở liệu gì? Hệ CSDL hệ thống bao gồm thành phần: - CSDL hợp nhất: CSDL hệ có hai tính chất tối thiểu hóa dư thừa chia sẻ - Những người sử dụng: Người sử dụng hệ người có nhu cầu truy nhập vào CSDL, bao gồm tất người sử dụng cuối, người viết chương trình ứng dụng người điều khiển toàn hệ thống hay gọi người quản trị CSDL - Phần mềm quản trị CSDL - Phần cứng hệ bao gồm thiết bị nhớ thứ cấp sử dụng để lưu trữ CSDL 1.2 Các khả hệ quản trị CSDL Có hai khả cho phép phân biệt hệ quản trị CSDL với kiểu hệ thống lập trình khác: - Khả quản lý liệu tồn lâu dài; - Khả truy nhập khối lượng liệu lớn cách hiệu Đặc điểm thứ có CSDL tồn thời gian dài, nội dung CSDL liệu mà hệ quản trị CSDL truy nhập quản lý Đặc điểm thứ hai phân biệt hệ quản trị với hệ thống xử lý tệp quản lý liệu tồn lâu dài nói chung khơng cung cấp truy nhập nhanh chóng đến phận liệu tùy ý Các khả hệ quản trị CSDL hầu hết cần thiết khối lượng liệu cần lưu trữ lớn, khối lượng liệu nhỏ kỹ thuật truy nhập đơn giản, chẳng hạn quét liệu thích hợp Khi xem xét hai đặc điểm hệ quản trị CSDL bản, cịn số khả khác mà thấy hầu hết hệ quản trị CSDL thương mại, là: - Hỗ trợ mơ hình liệu hay trừu tượng tốn học mà qua người sử dụng quan sát liệu http://www.ebook.edu.vn - Đảm bảo tính độc lập liệu hay bất biến chương trình ứng dụng thay đổi cấu trúc mơ hình liệu - Hỗ trợ ngôn ngữ cấp cao định cho phép người sử dụng định nghĩa cấu trúc liệu, truy nhập liệu thao tác liệu - Quản trị giao dịch, có nghĩa khả cung cấp truy cập đồng thời, đắn CSDL từ nhiều người sử dụng thời điểm - Điều khiển truy cập, có nghĩa khả hạn chế truy nhập đến liệu người sử dụng không cấp phép khả kiểm tra tính đắn liệu - Phục hồi liệu, có nghĩa khả phụ hồi, khơng làm mát liệu lỗi hệ thống http://www.ebook.edu.vn Chương Cơ sở liệu hướng đối tượng 2.1 Nhu cầu hệ thống CSDL hướng đối tượng Nhìn chung hệ quản trị CSDL quan hệ sử dụng nhiều chưa đáp ứng hết yêu cầu thực Bên cạnh mơ hình quan hệ, mơ hình mạng phân cấp tồn Một số hạn chế hệ quản trị CSDL quan hệ 2.1.1 Các đối tượng phức tạp Một cách hình thức, đối tượng nhằm xác định cấu trúc phức tạp Ví dụ: Các đối tượng có cấu trúc phức tạp thường thấy siêu văn bản, lược đồ, ảnh hay chương trình Sự phức tạp đối tượng thể qua: - Cấu trúc đối tượng; - Mơ hình hóa đối tượng; - Ngơn ngữ hỏi đối tượng Bình thường, CSDL quan hệ xử lý loại liệu quen thuộc số, chữ, ngày tháng, logic Với loại liệu này, chưa thể thể loại liệu định tính hay danh sách Chính người ta địi hỏi mơ hình hóa đối tượng phức tạp xử lý chúng hệ quản trị nhờ ngơn ngữ chương trình Các đối tượng phức tạp coi kí tự, liệu phức Trong chương trình, chúng mơ tả theo kiểu đặc biệt Giải pháp đụng chạm đến khái niệm quan trọng khác tượng dư thừa mã mô tả đối tượng phức tạp chương trình ứng dụng, đụng chạm đến phụ thuộc chương trình/dữ liệu Như việc xử lý liệu phức, có kích thước lớn theo giải pháp khơng hiệu Hơn nữa, cấu trúc liệu đơn giản, khơng thể dùng cho mơ hình hóa đối tượng phức tạp, thí dụ đối tượng hệ thống phân cấp hay đồ thị Ví dụ 2.1 Một đối tượng phức tạp, chẳng hạn CAD, thường phân rã đặt quan hệ nhỏ; mà thơng tin ngữ nghĩa sẵn có vấn đề bị chia nhỏ ra, phân tán dạng giá trị quan hệ Điều khiến người sử dụng phải nhìn giới tốn theo cách nhìn CSDL quan hệ Để khôi phục ngữ nghĩa ban đầu, không tránh việc yêu cầu phép kết nối quan hệ, phép tốn tốn tài ngun để thực Ngồi việc mơ hình hóa, việc truy vấn CSDL thơng qua ngơn ngữ cần phải xem xét Khó có ngơn ngữ lý tưởng đối tượng phức tạp Cũng sử dụng ngơn ngữ lập trình để giải gặp khó khăn khác biệt kiểu liệu cách khai thác liệu ngơn ngữ lập trình ngơn ngữ CSDL Ngơn ngữ truy vấn CSDL dựa sở tập hợp, ngơn ngữ lập trình dựa thủ tục Các ứng dụng CSDL nhìn nhận theo hai khía cạnh: - Khía cạnh tĩnh: thể qua liệu - Khía cạnh động: thể qua phép xử lý tác động lên liệu Người ta thấy đối tượng hệ quản trị CSDL quan hệ xử lý đặc biệt liệu tĩnh Phần tác động chúng, tức hoạt động, mô tả riêng biệt thông qua chương trình ứng dụng tác động lên liệu Người lập trình phải biết cấu trúc quan hệ đối tượng, lẽ hệ quản trị CSDL quan hệ không đáp ứng nhu cầu đối tượng động 2.1.2 Quản lý tri thức 30 http://www.ebook.edu.vn Để quản lý hoạt động đồng thời, CSDL phải phân nhỏ thành mục liệu, đơn vị liệu cần truy xuất có điều khiển Bản chất kích thước mục liệu nhà thiết kế hệ thống chọn lựa Chẳng hạn mơ hình liệu quan hệ, chọn mục lớn quan hệ, mục nhỏ hay thành phần Chúng ta chọn lựa mục có kích thước trung gian, khối quan hệ Kích thước mục liệu hệ thống sử dụng gọi độ mịn hệ thống Một hệ thống gọi hạt mịn, sử dụng mục liệu nhỏ hệ thống hạt thơ sử dụng mục liệu lớn Phương pháp thông dụng để điều khiển việc truy xuất mục sử dụng khóa Bộ quản lý khóa thành phần hệ quản trị chịu trách nhiệm theo dõi xem mục I có giao dịch đọc ghi vào phần I hay khơng Nếu có quản lý khóa ngăn cản khơng cho giao dịch khác truy xuất I trường hợp truy xuất gây xung đột Chọn chế độ hạt thơ làm giảm tổng chi phí cần để trì khóa, cần chỗ để lưu khóa, tiết kiệm thời gian hệ thống phải thực hành động đóng mở khóa Tuy nhiện độ hạt mịn cho phép nhiều giao dịch hoạt động song song, xác xuất giao dịch yêu cầu khóa mục thấp 3.3.1.3 Khóa Như khẳng định, khóa đặc quyền truy xuất mục liệu mà quản lý khóa trao cho giao dịch hay thu hồi lại Có thể có nhiều kiểu khóa, ví dụ khóa đọc, khóa ghi… Thơng thường thời điểm, có tập mục bị khóa, quản lý khóa lưu khóa hành bảng khóa vơi mẫu tin: (I, L, T) – giao dịch T có khóa kiểu L mục I 3.3.1.4 Kiểm sốt hoạt động đồng thời khóa Để thấy nhu cầu phải sử dụng khóa xem xét ví dụ sau đây: Xét hai giao dịch T1 T2 Mỗi giao dịch truy xuất mục liệu A giả sử mang giá trị nguyên, cộng thêm vào A hai giao dịch thực chương trình P P: Begin Read A A=A+1 Write A End Chúng ta thực hai giao dịch T1 T2 sau: A csdl 5 5 6 T1 Read A A=A+1 Write A T2 Read A A = A + Write A A vùng làm việc T1 5 6 6 A vùng làm việc T2 5 6 Giá trị A tồn CSDL, với giao dịch P đọc A vào vùng làm việc, cộng vào giá trị ghi kết vào CSDL Chúng ta nhận thấy rằng, hai giao dịch cộng thêm vào A, giá trị A CSDL tăng Giải pháp thông dụng cho vấn đề trình bày ví dụ cung cấp khóa A Trước đọc A, giao dịch T phải khóa A lại, ngăn cản không cho giao dịch khác truy xuất A T hoàn tất xong thao tác A Hơn T khóa mục A trước A 31 http://www.ebook.edu.vn khơng bị khóa giao dịch khác Nếu A bị khóa, T phải đợi đến giao dịch mở khóa cho A Vậy để ngăn cản trường hợp đáng tiếc xẩy ta phải dùng khóa Như chương trình giao dịch phải có khóa mở khóa Ta giả sử khóa phải đặt mục trước đọc hay ghi nó, thao tác khóa hành động hàm đồng hóa Nghĩa giao dịch khóa mục khóa, khơng thể tiến hành khóa giải phóng lệnh mở khóa thực giao dịch giữ khóa Ta giả sử giao dịch mở khóa khóa Một lịch biểu chứa cá thao tác nhiều giao dịch tuân theo quy tắc khóa gọi hợp lệ Ví dụ: Chương trình P ví dụ viết lại với khóa sau: P: begin Lock A Read A A=A+1 Write A Unlock A End Giả sử T1 T2 hai giao dịch thực P Nếu T1 bắt đầu trước, yêu cầu khóa A Giả sử khơng có giao dịch khóa, quản lý khóa cho khóa mục A Bây có T1 truy xuất A, T2 bắt đầu trước T1 chấm dứt T2 thực lệnh khóa A, hệ thống buộc T2 phải đợi Chi T1 thực lệnh Unlock A, hệ thống cho phép T2 tiến hành Kết điều bất thường không xảy ra; T1 T2 hoàn tất trước giao dịch bắt đầu, kết chung chúng cộng vào A 3.3.1.5 Khóa sống (livelock) Hệ thống quản lý khóa trao buộc khóa mục liệu hoạt động cách tùy tiện Giả sử ví dụ trên, T1 giải phóng khóa A, T2 đợi nhận khóa, giao dịch T3 khác xin khóa A, T3 trao khóa trước T2 Tương tự sau T3 mở khóa cho A lại có giao dịch T4 xin khóa A… Và T2 phải đợi lâu không nhận khóa A Tình gọi khóa sống Vậy khóa sống mục A giao dịch T T khơng khóa A A ln bị khóa giao dịch khác Rất nhiều giải pháp nhà thiết kế hệ điều hành đề xuất để giải vấn đề khóa sống, ví dụ giao dịch khóa mục phải đăng ký thứ tự, quản lý khóa trao quyền khóa mục A mục khơng bị khóa theo thứ tự xác định trước 3.3.1.6 Khóa “cứng” (deadlock) Một vấn đề khác xẩy điều khiển hoạt động đồng thời, vấn đề khóa “cứng” (deadlock) Đó giao dịch khóa chéo lẫn mục cần để hồn thiện giao dịch Ví dụ: Giả sử có hai giao dịch đồng thời T1 T2 sau: http://www.ebook.edu.vn T1: begin Lock A Lock B Unlock A Unlock B end 32 T2:begin Lock B Lock A Unlock B Unlock A end Giả sử T1 T2 thực lúc T1 yêu cầu khóa A trao quyền khóa A, cịn T2 u cầu trao quyền khóa B Do T1 u cầu khóa B phải đợi vị T2 khóa B Tương tự T2 yêu cầu khó A, buộc phải đợi T1 khóa A Kết khơng giao dịch tiếp tục hoạt động được, giao dịch phải đợi cho giao dịch mở khóa, chúng phải đợi chẳng nhận khó yêu cầu Như khóa “cứng” tình mà thành viên Ti tập giao dịch T = {T1, T2,…, TN} đợi nhận khóa mục bị khóa giao dịch khác tập T Bởi giao dịch tập T đợi, nói khơng thể mở khóa cho mục mà giao dịch khác cần, tất tiếp tục đợi mãi Một số giải pháp cho vấn đề khóa “cứng”: Yêu cầu giao dịch phải đưa tất yêu cầu khóa lúc, quản lý khóa trao tất khóa cho chúng được, không trao cho giao dịch đợi hay nhiều khóa giữ giao dịch khác Gán thứ tự tuyến tính cho mục, buộc tất giao dịch phải xin khóa theo thứ tự Một cách khác nhằm xử lý khóa “cứng” khơng ngăn cản chúng Và sau khoảng thời gian định ,hệ thống kiểm tra yêu cầu khóa tìm xem có xảy khóa “cứng” hay khơng Nếu sử dụng đồ thị chờ đợi, với nút cá giao dịch cung T1  T2 biểu thị cho T2 đợi nhận khóa mục T1 giữ Thế chu trình đồ thị chờ biểu thị cho khóa “cứng”, khơng có chu trình kết luật khơng có khóa “cứng” Nếu khóa “cứng” phát hiện, hệ thống phải khởi động lại tác dụng CSĐL giao dịch khóa “cứng” phải bỏ Q trình hủy bỏ tái khởi động gặp rắc rối cách thức giao dịch ghi vào CSDL trước chúng hồn thành 3.3.1.7 Tính khả lịch biểu Giả sử có tập giao dịch T = {T 1, T2,…, TN} Chúng ta thấy giao dịch thực theo thứ tự đó, giao dịch nối tiếp giao dịch cố tranh chấp chắn không xẩy CSDL có kết Giả sử có tập giao dịch T = {T1, T2,…, TN}, tương ứng với T ta có N! lịch biểu khác Bởi giả sử hoạt động giao dịch đồng thời l đắn tác dụng cảu giống tác dụng có lịch biểu Chúng ta định nghĩa lịch biểu S cho tập cá giao dịch T thứ tự (có thể xen kẽ) bước giao dịch (khóa, đọc, ghi, …) thực Các bước giao dịch cho phải xuất lịch biểu theo thứ tự xảy giao dịch 33 http://www.ebook.edu.vn Vậy lịch biểu S tập giao dịch T gọi hợp lệ đắn bước giao dịch Ti cho phải xuất lịch biểu S theo thứ tự xảy giao dịch Ti bước giao dịch tuân theo quy tắc khóa Một lịch biểu S giao dịch T hoán vị bước Ti  T Giả sử T có k bước nên có k! hoán vị khác bước Vậy với tập giao dịch T ta có k! lịch biểu S khác Tuy nhiên số có nhiều lịch biểu vô nghĩa không đắn không hợp lệ Việc quản lý giao dịch quản lý lịch biểu đắn hợp lệ tương đơn với lịch biểu Lịch biểu gọi khả tác dụng giống với tác dụng lịch biểu ngược lại gọi bất khả Hai lịch biểu gọi tương đương chúng cho kết giống 3.3.1.8 Bộ xếp lịch Chúng ta nhận thấy thực hoạt động đồng thời giao dịch gây t ình trạng khóa sống, khóa “cứng” vấn đề bất khả Để loại bỏ vấn đền này, dùng xép lịch nghi thức Bộ xếp lịch thành phần hệ thống CSDL, có vai trị làm trọng tài phân xử u cầu có xung đột Chẳng hạn biết cách loại bỏ khác sống xép lịch “đến trước phục vụ trước” Một xếp lịch xử lý khóa “cứng” tính bất khả cách” Buộc giao dịch phải đợi, chẳng hạn khóa yêu cầu phải giải phóng Buộc giao dịch ngừng lại tái khởi động 3.3.1.9 Nghi thức Chúng ta sử dụng cơng cụ khác để xử lý khóa gài tính bất khả Cơng cụ nghi thức mà tất giao dịch phải tuân theo Một nghi thức, theo nghĩa tổng quát nhất, hạn chế chuỗi bước mà giao dịch thực 3.3.2 Mơ hình giao dịch đơn giản 3.3.2.1 Ý nghĩa giao dịch – hàm đặc trưng Về nguyên tắc, ý nghĩa giao dịch T i tác dụng chương trình P tương ứng CSDL Về hình thức, gán hàm f đặc trưng cho cặp Lock A Unlock A Hàm f nhận đối giá trị tất mục bị khóa giao dịch T trước mở khóa cho A, giá trị f giá trị A sau mở khóa A Chú ý giao dịch có nhiều hàm mục A, khóa mở khóa mục A nhiều lần Vậy gọi A0 giá trị ban đầu A trước giao dịch bắt đầu thực hiện, giá trị hàm f(A0,….) sau Unlock A giá trị A Một cách tổng quát gọi A giá trị mục A trước lock A giá trị A sau Unlock A f(A,…) ta ký hiệu: lock A….unlock A f(A,…) Các giá trị mà A nhận thực giao dịch công thức xây dựng cách áp dụng hàm cho giá trị ban đầu mục 34 http://www.ebook.edu.vn Hai công thức khác coi giá trị khác Hai lịch biểu tương đương công thức cho giá trị cuối mục giống hai lịch biểu Ta xét ví dụ sau: T1: begin Lock A Lock A Unlock A f1(A,B) Unlock B f2(A,B) End T2: begin Lock B Lock C Unlock B f3(B,C) Lock A Unlock C f4(A,B,C) Unlock A f5(A,B,C) End T3: begin Lock A Lock B Unlock C f6(A,C) Unlock A f7(A,C) End Chúng ta có ba giao dịch hàm đặc trưng có liên quan với cặp Lock – Unlock; hàm xuất dòng với Unlock Chẳng hạn f 1, nhận A B làm đối số, mục Lock A – Unlock A T1 Hàm f3 nhận B C làm đối số T2 mở khóa B, Lock B – Unlock B có B C Hình sau trình bày lịch biểu giao dịch tác dụng chúng mục A, B, C Bước 10 11 12 13 14 Thao tác T1:Lock A T2: Lock B T2: Lock C T2: UnLock B T1: Lock B T1: UnLock A T2: Lock A T2: UnLock C T2: UnLock A T3: Lock A T3: Lock C T1: UnLock B T3: UnLock C T3: UnLock A A A0 A0 A0 A0 A0 f1(A0,f3(B0,C0)) f1(A0,f3(B0,C0)) f1(A0,f3(B0,C0)) (ii) (ii) (ii) (ii) (ii) (iv) B B0 B0 B0 f3(B0,C0) f3(B0,C0) f3(B0,C0) f3(B0,C0) f3(B0,C0) f3(B0,C0) f3(B0,C0) f3(B0,C0) f2(A0,f3(B0,C0)) f2(A0,f3(B0,C0)) f2(A0,f3(B0,C0)) C C0 C0 C0 C0 C0 C0 C0 (i) (i) (i) (i) (i) (iii) (iii) Ký hiệu: (i) = f4(f1(A0,f3(B0,C0)),B0,C0) (ii) = f5(f1(A0,f3(B0,C0)),B0,C0) (iii) = f6((ii), (i)) (iv) = f7((ii),(i)) Chúng ta nhận xét lịch biểu khơng có đặc tính khả Thật vậy, giả sử khả Thế T1 thực trước T2 lịch biểu tuần tự, giá trị cuối B là: f3(f2(A0,B0),C0) f2(A0, f3(B0,C0)) Chúng ta thấy giả thiết công thức hàm f sinh giá trị mấu chốt lập luận, điều xẩy chẳng hạn tồn tại: f3(f2(A0,B0),C0) = f3(A0,f3(B0,C0)) Trong trường hợp kết luận lịch biểu bất khả Cần lưu ý phép kiểm tra tính khả hàm đặc trưng phương pháp phức tạp với tập nhiều giao dịch nhiều thao tác phép kiểm tra phương pháp 35 http://www.ebook.edu.vn yếu hai cơng thức hàm đặc trưng khác giá trị chúng giống 3.3.2.2 Kiểm tra tính khả đồ thị có hướng Để xác định xếp lịch đúng, phải chứng minh lịch biểu S cho phép có đặc tính khả Vì cần có phép kiểm tra đơn giản tính khả lịch biểu Thuật tốn 3.3 Kiểm tra tính khả lịch biểu S Vào: Một lịch biểu S tập giao dịch T 1, T2,…, Tk Ra: Khẳng định S có khả hay khơng Nếu có đưa lịch biểu tương đương với S Phương pháp: Xây dựng đồ thị có hướng G (được gọi đồ thị hóa) có nút giao dịch Ti Để xác định cung đồ thị G, gọi (a 1, a2,…, aN) tập bước S Trong thao tác có dạng Tj: Lock A Tj: Unlock A Nếu aj thao tác kiểu Unlock A tìm thao tác ap sau aj có dạng Ts: Lock A Nếu có cặp thao tác s  j, vẽ cung từ Tj đến Ts (Tj  Ts) Cung có ý nghĩa lịch biểu tương đương với S, Tj phải thực trước trước Ts Nếu G có chu trình S bất khả tuần tự, ngược lại G khơng có chu trình S khả tìm thứ tự tuyến tính cho giao dịch cho Ti trình gọi xếp topo đồ thị G sau: Sắp xếp Topo đồ thị có hướng G khơng có chu trình Ta biết G phải có nút T j khơng có cung đến, khơng G có chu trình Liệt kê Tj loại Tj khỏi G Sau lặp lại q trình đồ thị cịn lại khơng cịn nút Thứ tự nút liệt kê danh sách thứ tự giao dịch Thứ tự tạo nên lịch biểu tương dương với S 3.3.3 Nghi thức khóa pha Chúng ta cần phải hiểu rõ điều kiện để lịch biểu khả nhằm tìm xếp lịch nghi thức, đảm bảo lịch biểu mà cho phép khả Nghi thức gọi nghi thức hai phai, giao dịch thực tất thao tác khóa trước tất thao tác mở khóa Các giao dịch tuân thủ theo nghi thức gọi giao dịch hai pha: pha đầu khóa pha thứ hai pha mở khóa Nghi thức hai pha có đặc điểm tập giao dịch tuân theo nghi thức có lịch biểu khả Trước tiên chứng minh nghi thức hai pha bảo đảm tính khả Định lý 3.1 Nếu S lịch biểu giao dịch hai pha S khả Chứng minh: Giả sử khẳng định không Vậy đồ thị G lịch biểu S có chu trình Ti1  Ti2 …  Tin  Ti1 36 http://www.ebook.edu.vn Do có thao tác khóa Ti2 sau thao tác mở khóa T i1, thao tác kho Ti3 sau thao tác mở khóa T i2… Cuối thao tác khóa Ti1 sau thao tác mở khóa Ti1 Điều mâu thuẫn với giả thiết Ti1 giao dịch hai pha Vậy khẳng định 3.3.4 Mơ hình khóa đọc khóa ghi Nếu phân biệt truy xuất đọc truy xuất đọc – ghi, phát triển mơ hình chi tiết cho giao dịch loại đọc ghi Trong số trường hợp mơ hình cho phép sử dụng số hoạt động đồng thời bị cấm ví dụ nhiều giao dịch giữ khóa đọc mục A Chúng ta phân biệt hai loại khóa Khóa đọc Rlock Một giao dịch T đọc mục A thực lệnh Rlock A, ngăn không cho giao dịch khác ghi giá trị lên A, nhiên giao dịch khác giữ khóa đọc A lúc với T 2.Khóa ghi Wlock Khi giao dịch muốn thay đổi giá trị mục A lấy khóa ghi cách thực lệnh Wlock A, giao dịch giữ khóa ghi mục, giao dịch khác khơng thể lấy khóa đọc khóa ghi mục Như khóa đọc mục A cám giao dịch khác ghi liệu vào a, cịn khóa ghi mục cấm giao dịch khác ghi đọc mục A 3.3.4.1 Ý nghĩa giao dịch với khóa đọc khóa ghi Chúng ta giả sử lần áp dụng khóa ghi cho mục A có hàm kèm với khóa tạo giá trị cho A; hàm phụ thuộc vào tất mục bị khóa trước mở khóa A Tuy nhiên giả sử khóa đọc A khơng làm thay đổi A Giả sử mục A có giá trị ban đầu A tác dụng lịch biểu CSDL diễn tả công thức hàm đặc tưng f, giá trị mục ghi lần giao dịch Tuy nhiên có giao địch đọc mục khơng ghi đọc số mục sau ghi vào lần cuối cùng, giá trị mà mục có giao dịch đọc xử lý giá trị cũ Vì nói hai lịch biểu tương đương nếu: Chúng sinh giá trị cho mục Mỗi khóa đọc áp dụng giao dịch hai lịch biểu vào lúc mục bị khóa có giá trị 3.3.4.2 Đồ thị hóa giao dịch Rlock Wlock Chúng ta xét điều kiện mà đó, từ ý nghĩa giao dịch lịch biểu, ta suy giao dịch phải trước giao dịch khác lịch biểu tương đương Giả sử có lịch biểu S khóa ghi mục A giao dịch T 1, gọi f hàm kèm với khóa ghi Sau T1 mở khóa A, gọi T2 giao dịch nhận khóa đọc A trước giao dịch khác nhân khóa ghi A Chắc chắn T phải thực trước T2 lịch biểu tương đương với S Nếu khơng T2 đọc tía trì A khơng chứa hàm f Tương tự, T3 giao dịch sau T1 nhận khóa ghi A T1 phải thực trước T3 37 http://www.ebook.edu.vn Bây ta giả sử T4 giao dịch nhận khóa đọc A trước T1 khóa ghi A Nếu T1 xuất trước T4 lịch biểu T4 đọc giá trị A có chứa hàm f, cịn lịch biểu S, giá trị đọc T4 không chứa f Vì vậy, T4 phải thực trước T1 lịch biểu tương đương với S Suy luận không thê thực S hai giao dịch nhần khóa đọc mục A theo thứ tự giao dịch phải xuất theo thứ tự lịch biểu Đúng thứ tự tương đối khóa đọc khơng tạo sẹ khác biệt giá trị tạo giao dịch thực đồng thời Thuật tốn 3.4 Kiểm tra tính khả lịch biểu với khóa đọc/ghi Vào: Một lịch biểu S cho tập giao dịch T 1, T2,…, TN Ra: Khẳng định S có khả hay không, đưa lịch biểu tương ứng Phương pháp: Chúng ta xây dựng đồ thị G sau Các nút tương ứng giao dịch Các cung xác định quy tắc sau: Giả sử S, giao dịch T i nhận khóa đọc khóa A T j giao dịch khóa ghi A, i  j Khi đặt cung từ Ti đến Tj Giả sử S, giao dịch Ti khóa ghi A Gọi Tm với m  i giao dịch khác khóa đọc A sau Ti mở khóa A trước giao dịch khác khóa ghi A Chúng ta vẽ mộ cung từ T i đến Tm Nếu G có chu trình thi S bất khả tuần tự, ngược lại xếp topo G thứ tự cho giao dịch http://www.ebook.edu.vn 38 Chương Hệ trợ giúp định 4.1 Giới thiệu hệ trợ giúp định Các hệ thống trợ giúp định hệ thống giúp việc quản lý xác định vấn đề, định cách thông minh Hệ thống cần đến lý thuyết tối ưu, lý thuyết hành vi quản lý, điều khiển trình thống kê… Cuối năm 60, người ta dùng máy tính q trình định ban đầu tự động hóa cơng việc lập báo cáo đơi lúc tính tốn, phân tích Các hệ thống gọi hệ thống định quản lý, sau xây dựng thành hệ thống thông tin quản lý Vào năm 70, người ta phát triển ngôn ngữ hỏi, xây dựng ngôn ngữ số hệ thống trợ giúp định chuyên dùng Các hệ thống bước cho phép người dùng có kĩ truy vấn trực tiếp liệu, tự hình thành câu hỏi liên quan đến kinh doanh mà không cần đến trợ giúp chuyên gia tin học Ngày sản phẩn ngôn ngữ hỏi SQL dùng cách rộng rãi, ý tượng xử lý tách biệt, tức việc chếp liệu từ môi trường hoạt động sang môi trường khác, quan trọng Ý tưởng cho phép người ta thao tác với liệu trích theo yêuc cầu mà khơng cần q trình suy luận mơi trường hoạt động Đương nhiên trình định, người ta sử dụng phần chiết suất liệu không cần tất Khác với hệ thống CSDL, hệ thống trợ giúp định chưa có lý thuyết riêng hồn chỉnh Người ta thường u cầu mơ hình logic hệ thống hệ trợ giúp uyết định Nhưng khơng phân biệt rõ mơ hình logic với mơ hình vật lý Các khía cạnh trợ giúp định Các CSDL trợ giúp định thể đặc tính đặc biệt đọc CSDL Tuy điều không áp đặt cho tất hệ thống trợ giúp định Do vậy, phép toán xử lý liệu cập nhật liệu, sử dụng; người ta thường tải lại liệu hay làm tươi liệu thay cho việc cập nhật trực tiếp Đôi bảng trung gian, người ta thực phép tốn cập nhật liệu, q trình định bình thường khơng cập nhật CSDL trợ giúp định Có sáu đặc tính hệ thống trợ giúp định, ba đặc tính đầu liên quan đến khía cạnh logic ba đặc tính cịn lại liên quan đến khía cạnh vật lý Các khái niệm dòng, cột dùng theo nghĩa CSDL quan hệ Các cột dùng theo nghĩa tổ hợp nhiều thuộc tính Nói chung hệ trợ giúp định khơng đề cập đến tính tồn vẹn liệu, liệu coi Các khóa thường mang yếu tố thời gian Kích thước CSDL có xu hướng ngày lớn Các bảng chi số dùng CSDL thường có kích thước lớn nặng nề 39 http://www.ebook.edu.vn CSDL thường sử dụng nhiều loại dư thừa liệu, dư thừa hệ thống kiểm soát Các câu hỏi hệ thống trợ giúp định có đặc tính riêng, thường phức tạp Tính phức tạp biểu thức logic Các câu hỏi trợ giúp định thường yêu cầu biểu thức phức tạp câu lệnh dẫn đến khó viết, khó hiểu Tính phức tạp phép toán kết nối quan hệ Các câu hỏi trợ giúp định thường truy cập nhiều loại kiện Trong CSDL chuẩn hóa câu hỏi loại thường yêu cầu nhiều phép kết nối Do vậy, người thiết kế thường phải phi chuẩn CSDL cách tiến hành trước số phép kết nối bảng Tính phức tạp hàm số Các câu hỏi hệ trợ giúp định thường sử dụng hàm thống kê, hàm toán học Chỉ số hệ thống đáp ứng loại câu hỏi dạng Thường người thiết kế cho phép câu hỏi gọi đến đoạn chương trình viết ngơn ngữ lập trình ngơn ngữ khai thác liệu khác Tính phức tạp phân tích Để trả lời câu hỏi hệ trợ giúp định, người ta cần phải sử dụng nhiêu câu hỏi Điều gây khó khăn cho người sử dụng hệ thống 4.2 Thiết kế CSDL cho hệ trợ giúp định Việc thiết kế CSDL cho hệ trợ giúp định thực qua hai bước bước thiết kế logic thiết kế vật lý: Thiết kế logic: tập trung vào việc chỉnh lý quan niệm theo lý thuyết quan hệ Các bảng liệu ứng với quan hệ Người ta xác định miền ứng với kiểu liệu, xác định mối liên kết cột cảu bảng Tiếp theo việc chuẩn hóa bảng xác định điều kiện ràng buộc liệu Bước thiết kế vật lý: tập trung vào tính hiệu lưu trữ hiệu suất hệ thống Về nguyên tắc, người ta lựa chọn cách tổ chức liệu nào, việc chuyển hóa mơ hình logic sang mơ hình vật lý theo đại số quan hệ hợp lý 4.2.1 Thiết kế logic Các quy luật thiết kế logic không phụ thuộc vào việc sử dụng CSDL, tức không phụ thuộc vào loại ứng dụng CSDL Do thiết kế cho hệ thống tác nghiệp hay cho hệ trợ giúp định sau: Tổ hợp cột phụ thuộc: Các câu hỏi trợ giúp định thường xử lý tổ hợp cột, không dùng cột đơn Có thể gọi tổ hợp cột cột tổ hợp Theo quan điểm thiết kế logic, cột tổ hợp có tư cách cột bình tưhờng Điều có tác dụng giảm số phụ thuộc hàm cột đơn Việc dẫn đến thiết kế logic đơn giản hơn, tạo thuận lợi kiểu liệu người dùng xác định Các ràng buộc tính toàn vẹn: hệ trợ giúp định hệ thống cho phép đọc liệu tính tồn vẹn liệu kiểm tra lúc tải liệu lược đồ logic người ta không đặt điểm kiểm tra tính tốn vẹn Các khóa thời gian: Các CSDL tác nghiệp thường cần liệu Các CSDL trợ giúp đinh thường cần đến liệu lịch sử, nên người ta cần tính đến việc đánh dấu thời gian hầu hết liệu hay vài liệu Để quản lý mốc thời gian, thuộc tính 40 http://www.ebook.edu.vn khóa cần đánh dấu thời gian Việc làm cần trình thiết kế logic lưu ý xác định phụ thuộc hàm cột đánh dấu cột bảng 4.2.2 Thiết kế vật lý CSDL hệ thống trợ giúp định có xu hướng nặng nề, kích thước lớn, địi hỏi nhiều loại dư thừa liệu có kiểm sốt người ta thương đề cập khái niệm phân đoạn số hoá Việc phân đoạn nhằm vào CSDL lơn, chia bảng liệu tập phần, hay đoạn rời nhau, phù hợp với công việc lưu trữ vật lý Công việc giúp người ta quản lý trả lời câu hỏi bảng dễ Điển hình đoạn liệu gắn với số tài nguyên tin học phần cứng, thời gian, xử lý trung tâm Điều giảm thiểu cạnh tranh tài nguyên đoạn liệu Việc dùng bảng số giảm thời gian vào/ra cần truy cập liệu Nhiều sản phẩm hệ quản trị CSDL cung cấp cho người dùng loại số cân đối, có nhiều loại số khác dùng hệ thống trợ giúp định bảng bit, hàm băm Dư thừa liệu có điều khiển cơng cụ quan trọng để giảm thao tác vào/ra tối thiểu hố nội dung Tính dư thừa liệu hệ quản trị CSDL quản lý mà người dùng không cần quan tâm: Quản lý liệu quản lý Quản lý liệu suy diễn bên cạnh liệu Thông thường người ta sử dụng bảng tổng hợp /hoặc cột thu cách tính tốn hay suy diễn 4.3 Kho liệu kho liệu chuyên đề Các hệ thống điều hành thường xuyên yêu cầu chặt chẽ hiệu suất, kích thước giao tác, tính hoạt động theo kế hoạch, tính ứng dụng cao Ngược lại hệ thống trợ giúp định có yêu cầu đa dạng hiệu suất, trước cơng việc làm, kích thước giao tác lơn, sử dụng tuỳ theo cảm tính người quản lý Những khác biệt gây nên khơng khó khăn cho việc tích hợp xử lý điều hành với việc trợ giúp định hệ thống đơn mà phải đáp ứng yêu cầu kế hoạch, quản lý tài nguyên, điều chỉnh hiệu suất hệ thống Do vậy, người quản trị hệ thống điều hành thường miễn cưỡng chấp nhận hoạt động trợ giúp định hệ thống họ Phần đề cập quan tâm hệ trợ giúp định Đó việc truy cập liệu từ nhiều nguồn khác nhau, từ nhiều hệ thống điều hành khác Những liệu dùng để định lưu trữ theo cách thức riêng kho liệu Hình 4.1 Kiến trúc tổng quan kho liệu Môi trường trợ giúp định CSDL Tác nghiệp Trích liệu Làm liệu Chuyển hoá liệu Tải liệu Làm tươi liệu Kho liệu http://www.ebook.edu.vn 41 4.3.1 Kho liệu Thuật ngữ kho liệu dùng từ cuối năm 80 kỷ XX Kho liệu dùng cho công tác định quản lý, tập hợp liệu thay đổi theo thời gian, không cho phép cập nhật, tích hợp hướng chủ đề Khái niệm khơng thể cập nhật giải thích kĩ bổ sung, liệu không thay đổi, bị xố Lí đề xuất khái niệm kho liệu là: Người ta cần sử dụng nguồn liệu đơn, sạch, bền vững để trợ giúp việc định Hệ thống trợ giúp định không chịu tác động hệ thống điều hành Đ/N Kho liệu (dataware house) Kho liệu nơi chứa liệu có yếu tố thời gian, khơng bị thay đổi, hướng chủ đề, dùng để trợ giúp việc định Đ/N Kho liệu xí nghiệp (Enterprise datawarehouse) Kho liệu xí nghiệp kho liệu tích hợp, tập trung, nguồn liệu điều khiển dùng cho việc định người sử dụng Mục đích kho liệu định, nên tăng cường chức năgn hỏi liệu kích thước kho liệu thường có xu hướng lớn Đ/N Tính hạn chế phạm vi Tính hạn chế phạm vi xét nhiều yếu tố cho phép xét yếu tố mà không quan tâm đến yếu tố khác, tức giả thiết yếu tố khác khơng thay đổi Người ta thấy có số vấn đề dẫn đến việc khảo sát dùng khả hạn chế phạm vi hệ trợ giúp định - Các sai sót thiết kế CSDL; - Sự khơng hiệu phép tốn quan hệ; - Khả không đủ mạnh hệ quản trị CSDL theo mơ hình quan hệ; - Các lỗi thiết kế kiến trúc làm hạn chế khả hệ thống 4.3.2 Kho liệu chuyên đề Các kho liệu nhằm cung cấp nguồn đơn chất liệu dùng cho hoạt động trợ giúp đinh Tuy nhiên, kho liệu trở nên thông dụng, người ta thấy người sử dụng thường thực thao tác phân tích liệu báo cáo phần nhỏ kho liệu Hơn người sử dụng hay lặp lại thao tác phần nhỏ kho liệu Việc thực nhiều lần thao tác tồn kho liệu khơng hiệu quả, người ta cần đến loại kho liệu chuyên dụng, người sử dụng xây dựng theo u cầu xử lý riêng Có việc truy cập liệu đồng với kho liệu nhanh Đ/N Kho liệu chuyên đề (data mart) Kho liệu chun đề có vai trị kho liệu, liệu cho phép cập nhật dùng cho trợ giúp định với mục đích đặc biệt Kho liệu chuyên đề kho liệu hạn chế, gồm liệu tuyển chọn tổng hợp từ kho liệu xí nghiệp Để tạo kho liệu chuyên đề, người ta thường theo ba cách tiếp cận sau: Trích liệu từ kho liệu Các liệu trích từ kho liệu để đạt suất phục vụ cao có tính hạn chế phạm vi Thơng thường liệu trích tải vào CSDL có 42 http://www.ebook.edu.vn lược đồ vật lý gần giống với phần ứng dụng kho liệu Do tính đặc biệt kho liệu chuyên đề so với kho liệu, lược đồ vật lý liệu đơn giản Tạo kho liệu chuyên đề riêng biệt Tiếp cận xuất phát từ tính đơn thể kho liệu, khơng trích liệu từ kho liệu không truy cập kho liệu vài nguyên nhân Coi kho liệu chuyên đề tảng kho liệu Một vài phát triển hệ thống trợ giúp định xây dựng kho liệu chuyên đề trước tiên, cần thiết Kho liệu tao cách tập hợp kho liệu chuyên đề Đ/N Tính chia hạt Tính chia hạt liệu đề cập khả lưu trữ phần tử nhỏ cảu liệu gộp CSDL Liên quan đến việc thiết kế kho liệu chuyên đề, người ta nhận thấy yếu tố quan trọng CSDL trợ giúp định tính chia nhỏ thành hạt CSDL Sớm hay mn kho liệu dùng để định yêu cầu truy cập liệu chi tiết nhất, nên yêu cầu chi thành hạt kho liệu không gây vấn đề lớn kho liệu chuyên đề Nếu kho liệu chuyên đề xây dựng cách trích liệu từ kho liệu mà ứng dụng có nhu cầu thường xuyên liệu mức hạt hay khơng, việc trích liệu cập nhật liệu mức hạt tốn nhiều 4.3.3 Các lược đồ chiều Các hệ thống trợ giúp định thường cần đến kết phân tích lịch sử giao dịch tác nghiệp Thông tin lưu tệp truy cập Do nhu cầu, đến lúc người ta cần trực tiếp truy cập thông tin theo số góc cạnh cần quan tâm Chẳng hạn thông tin sản lượng rượu vang, người ta cần biết sản lượng, người sản xuất,về tuổi rượu… Để trợ giúp nhu cầu truy cập này, người ta dùng CSDL có nhiều bảng tra cứu Cơ sỏ liệu có tệp liệu trung tâm chứa cá liệu hoạt động tác nhiều bảng tra cứu sản lượng, người sản xuất, tuổi rượu Các bảng tựa bảng số chúng có trỏ trỏ đến ghi tệp liệu, khác với bảng số chỗ người dùng co thể tác động đến bảng tra cứu theo cách tường minh bảng tra cứu mang thơng tin phụ, chẳng hạn địa nhà sản xuất Các tổ chức nhiều bảng tra cứu có ưu điểm so với việc dùng tệp tra cứu, không gian nhớ lẫn thời gian vào/ra Khi dùng tiếp cận sỏ liệu quan hệ, tệp liệu tệp tra cứu trở thành bảng, tức ảnh tệp; trỏ tệp tra cứu trở thành khố bảng tra cưu; tên tệp liệu trở thành cá khố ngồi bảnh ảnh tệp liệu Trường hợp điển hình khố khố ngồi số hố Theo phương thức này, ảnh tệp liệu gọi bảng kiện ảnh tệp tra cứu gọi bảng chiều Thiết kế tổng thể phù hợp gọi lược đồ hình sao, hay lược đồ chiều, thiết kế thực thể quan hệ người ta nới rộng bảng kiện, để nối với cá bảng chiều Ví dụ CSDL RUOU(TenRuou, NhaSX, NamSX, SoLuong) thuộc tính NamSX mơ tả khoảng từ năm t1 đến năm t2 Theo thuật ngữ lược đồ hình bảng RUOU gọi bảng kiện bảng SanXuat(Nam, NamBD, NamKT) gọi bảng chiều Ruou TenRuou Lúa Thăng Long NhaSX Hà Nội Hà Nội NamSX 1980 1990 SoLuong 200 300 SanXuat Nam 1980 1990 NamBD NamKT 1980 1985 1986 1992 Đ/N Lược đồ hình Lược đồ hình thiết kế CSDL đơn giản, liệu chiều tách khỏi liệu kiện Mơ hình chiều tên gọi khác lược đồ hình 43 http://www.ebook.edu.vn Câu hỏi CSDL theo lược đồ hình cần đến bảng chiều để phát tất tổ hợp khố ngồi cần thiết, dùng tổ hợp để truy cập bảng kiện Giả sử việc truy cập bảng chiều truy cập bảng kiện thể gọn câu hỏi đơn, cách tốt để thực câu hỏi thước theo kết nối hình Kết nối hình chiến thuật đặc biệt để thực phép kết nối thực theo hai bước Tiến hành phép tích đề bảng chiều Lưu ý tối ưu hoá câu hỏi, người ta thường tránh sử dụng phép tích đề Trong trường hợp này, bảng kích thước nhỏ tham giá trước vào phép tích đề Dùng kết tích đề để quản lý bảng kiện theo kĩ thuật số hoá Kĩ thuật số hoá cho phép chiến thuật hiệu Một biến dạng lược đồ hình lược đồ hoa tuyết, thực việc chuẩn hoá bảng chiều Đ/N Lược đồ hoa tuyết Lược đồ hoa tuyết biến dạng lược đồ hình sao, bảng chuẩn hố 4.4 Xử lý phân tích trực tuyến 4.4.1 Giới thiệu Thuật ngữ xử lý phân tích trực luyến OLAP nhằm vào q trình tương tác với hệ thống, bao gồm thao tác tạo mới, quản lý, phân tích lập báo cáo liệu, thông qua câu lệnh yêu cầu tìm kiếm, xử lý liệu bảng liệu nhiều chiều Đ/N Xử lý phân tích trực tuyến Xử lý phân tích trực tuyến mở rộng lĩnh vực CSDL quan hệ để trợ giúp mô hình kinh doanh Quá trình OLAP dùng qui luật để truy cập nhanh tiện lợi đến liệu cho hệ thống quản lý thông tin hay trợ giúp định OLAP việc sử dụng tập công cụ đồ hoạ để người dụng thấy nhiều chiều liệu, cho phép phân tích liệu Q trình phân tích u cầu gộp liệu, theo nhiều cách, tuỳ theo cách thức nhóm liệu khác Một khía cạnh xử lý phân tích trực tuyến số khả nhóm liệu nhiều lên nhanh, người dùng cần xem xét tất khả 4.4.2 Bảng chéo Các kết q trình phân tích trực tuyến đưa thường khơng theo dạng bảng quan hệ, mà theo bảng hai chiều, gọi bảng chéo Xét câu hỏi “Tìm tổng số rượu công ty rượu cung cấp bảng đây: Ruou Ten Lúa Vang Vang Lúa CongTy Hà Nội Hà Nội Huda Huế Hà Bắc Nam 1980 1995 1990 1990 SoLuong 200 350 450 320 Người ta xây dựng bảng gọi bảng chéo để thể câu trả lời Bảng chéo khác với bảng quan hệ chỗ, số cột phụ thuộc vào liệu thực, tức cấu trúc bảng lẫn ý nghĩa dòng phụ thuộc vào giá trị thực liệu Do bảng chéo quan hệ, mà báo cáo có hình thức ma trận hai chiều Ví dụ: Lúa Vang Tổng Hà Nội 200 350 550 Huda Huế 450 450 http://www.ebook.edu.vn Hà Bắc Tổng 320 520 800 44 320 1320 4.4.3 CSDL nhiều chiều Quá trình xử lý phân tích trực tuyến đặt mơi trường quan hệ, q trình gọi OLAP quan hệ viết tắt ROLAP Trong thực tế nhiều người nhận thấy có cách tiếp cận tốt hơn, OLAP nhiều chiều viết tắt MOLAP MOLAP cần đến CSDL nhiều chiều Việc lưu trữ gọi lưu trữ theo quan niệm Để hình dung thấy nhiều chiều, hệ thống thực tế tổ chức vật lý MOLAP gần với tổ chức logic Hệ quản trị CSDL trường hợp gọi hệ quản trị CSDL nhiều chiều Các CSDL thể bảng hai, ba chiều 4.5 Khai phá liệu Khai phá liệu, mục đích nhìn vào phân đáng quan tâm liệu, phần dùng để thiết lập chiến lược kinh doanh hay để xác định hành vi khác thường Đ/N Khai phá liệu Khai phá liệu q trình trích thông tin dùng được, chưa biết trước từ CSDL lơn, dùng thông tin để định Các công cụ khai phá liệu dùng kĩ thuật thống kê khối lượng liệu lớn để tìm phần liệu cần thiết Các CSDL khai phá liệu thường lớn, có xu hướng đơn giản hoá thuật toán Một số thuật ngữ dùng khai phá liệu “dân số” để thao tác thực bảng liệu, “luật liên kết” để phụ thuộc liệu xét giao tác… Luật liên kết phát áp dụng phép toán gộp phù hợp Một số qui luật khác xác định luật “tương quan tuần tự”, luật “phân loại” ... GIAO THÔNG VẬN TẢI TRƯỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: HỆ THỐNG THÔNG TIN KHOA: CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO TÊN HỌC PHẦN MÃ HỌC PHẦN TRÌNH ĐỘ ĐÀO TẠO DÙNG CHO SV NGÀNH : CƠ SỞ... CƠ SỞ DỮ LIỆU NÂNG CAO : 17406 : ĐẠI HỌC CHÍNH QUY : CƠNG NGHỆ THƠNG TIN HẢI PHỊNG - 2008 http://www.ebook.edu.vn Tên học phần: Cơ sở liệu nâng cao Bộ môn phụ trách giảng dạy: Hệ thống Thông. .. đăng ký học học phần này: Cơ sở liệu Mục tiêu học phần: Cung cấp kiến thức nâng cao mơ hình sở liệu quan hệ, phương pháp thiết kế sở liệu khác Nội dung chủ yếu: Giới thiệu hệ quản trị liệu; Các