Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục

Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục, trình bày các nội dung chính như sau: Chỉ mục dựa trên cây; Chỉ mục bitmap. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục KHO DỮ LIỆU VÀKINH DOANH THÔNG MINH Bài 5: Lập chỉ mục Nội dung Chỉ mục dựa trên cây Chỉ mục bitmap 2 Chỉ mục• Tại sao phải lập index? – Xem xét một bảng dữ liệu 100 GB; với tốc độ đọc 100 MB/s, cần 17 phút để quét qua toàn bảng – Câu truy vấn về số lượng máy S500 bán được ở Đức tháng trước • Áp dụng ràng buộc (sản phẩm, vị trí) khối lượng phải chọn sẽ giảm mạnh – Nếu bảng có 30 vị trí, 10000 sản phẩm và 24 tháng, khối lượng lựa chọn là 1/30 * 1/ 10000 * 1/24 = 0,00000014 – Như vậy chúng ta đọc 100 GB để lấy ra 1,4KB 3 Chỉ mục• Giảm số lượng các khối (trang/page) phải đọc với chỉ mục 4 Chỉ mục dựa trên Tree• B-Tree – Cấu trúc dữ liệu để lưu trữ dữ liệu được sắp xếp – Cấu trúc gồm các node 5 Cấu trúc cây• Tìm kiếm trong các hệ CSDL – B-Tree cho phép tìm kiếm với chi phí cỡ logarith 6 Cây cấu trúc• Tìm kiếm trong DW – Dữ liệu là đa chiều, tuy nhiên B-Tree chỉ hỗ trợ tìm kiếm 1 chiều – Liệu có thể mở rộng chức năng của cây để hỗ trợ dữ liệu đa chiều? 7 Cấu trúc cây• Ý tưởng cơ bản của các cây đa chiều – Mô tả tập điểm theo vùng hình học, chứa bó cụm của các điểm dữ liệu – Khi tìm kiếm, chỉ một số cụm được quan tâm chứ không phải mọi điểm – Các cụm/Cluster có thể chứa nhau, dẫn đến cấu trúc phân cấp 8 Cấu trúc cây• Các tiêu chuẩn khác nhau cho các cấu trúc cây – Cấu trúc phân cụm • Phân mảnh toàn không gian • Chỉ nhóm dữ liệu địa phương – Sự chồng xếp các cụm • Các cụm giao nhau • Các cụm tách biệt nhau – Sự cân bằng • Cân bằng • Không cân bằng 9 Cấu trúc cây• Lưu trữ đối tượng – Các đối tượng có thể ở lá hay node trong – Các đối tượng chỉ ở lá• Dạng hình học – Hình học cầu – Hình học khối 10 R-Tree• R-Tree (Guttman, 1984) là một mở rộng đa chiều của B-Tree – Thường sử dụng cho các ứng dụng có số chiều thấp (khoảng 10 chiều), như các hệ thống thông tin địa lý• Phiên bản mở rộng hơn: R+-Tree, R*-Tree, X-Tree – Lên tới hơn 20 chiều đối với các dữ liệu phân phối đều 11 Cấu trúc R-Tree• Cấu trúc chỉ mục động (có thể insert, update và delete)• Cấu trúc dữ liệu – Các trang dữ liệu/data page là các node lá và lưu các dữ liệu điểm cụm/cluster points và dữ liệu đối tượng – Các trang thư mục/directory page là các node trong và lưu các thực thể thư mục – Dữ liệu đa chiều được cấu trúc sử dụng MBR (hình chữ nhật bao tối thiểu/Minimum Bounding Rectangle) 12Thí dụ R-Tree 13 Các tính chất của R-Tree• Lập các nhóm địa phương là các cụm• Các cụm có thể chồng nhau – Mức chồng nhau càng cao, hiệu quả của index càng thấp• Cấu trúc cây có chiều cao cân bằng – Tất cả các con của 1 node có cùng số lượng con cháu• Các đối tượng chỉ được lưu ở node lá – Node trong dùng để di chuyển trong cây• MBR thể hiện hình học 14 Các thuộc tính của R-Tree• Root có ít nhất 2 con• Mỗi nút trong có giữa m và M con• M và là các tham số xác định trước• Tất cả các lá của cây ở cùng 1 mức• Tất cả các lá có giữa m và M bản ghi chỉ mục• Các node trong: (I, child-pointer) với I là hình chữ nhật bao nhỏ nhất mà chứa hình chữ nhật của các node con• Các node lá: (I, tuple-id) với I là hình chữ nhật bao nhỏ nhất chứa các đối tượng dữ liệu (với ID tuple-id) 15 Các phép toán trên R-Tree• Các phép toán cơ bản để sử dụng và quản lý R-Tree gồm: – Search – Insert – Update – Delete – Splitting 16 Tìm kiếm trong R-Tree• Cây được tìm kiếm đệ quy từ root tới lá – 1 path được chọn – Nếu bản ghi không được tìm thấy, nhánh tiếp theo sẽ được tìm• Lựa chọn path tùy ý 17 Thí dụ• Kiểm tra chỉ 7 node thay vì 12 18 Tìm kiếm trong R-Tree• Không đảm bảo hiệu năng tốt• Trong trường hợp tồi nhất phải tìm tất cả các path (do sự chồng nhau của các MBR)• Thuật toán tìm kiếm cố gắng loại bỏ các vùng không liên quan càng nhiều càng tốt (“tỉa”) 19 Thuật toán tìm kiếm• Tất cả các thực thể chỉ mục giao với hình chữ nhật tìm kiếm được duyệt – Tìm kiếm trên các node trong • Kiểm tra sự giao cắt của các MBR với truy vấn • Với các MBR giao cắt, tìm kiếm trên tất cả các con của nó – Tìm kiếm trên các node lá • Kiểm tra tất cả các điểm dữ liệu để xác định xem nó có giao với truy vấn không • Tìm kiếm đối trượng chính xác trong tập kết quả 20 ...