Bài giảng Kho dữ liệu và khai phá dữ liệu - Chương 4: Giới thiệu chung về kho dữ liệu - Hà Quang Thụy

ountryTorontoFrankfurtcity08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 235Khung nhìn của các KDL và các kiến trúcSpecification of hierarchiesSchema hierarchyday Phụ thuộc (trực tiếp từ KDL)Kho ảo (Virtual warehouse)Một tập khung nhìn trên CSDL tác nghiệpChỉ một bộ phận khung tím tắt khả nang có thể hữu hình08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 349Phát triển KDL: Một tiếp cận đề cửĐịnh nghĩa một mô hình dữ liệu hãng mức caoData MartData MartDistributed Data MartsKDL đa mứcKDL toàn bộ hãngLàm mịn mô hìnhLàm mịn mô hình08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 350Kiến trúc phục vụ OLAPOLAP quan hệ (Relational ROLAP) Dùng CSDL quan hệ hoặc quan hệ mở rộng để lưu trữ và quản lý KDL và phần mềm lớp giữa để hỗ trợ các bộ phận bị thiếu hụt.Bao gói tối ưu hóa lớp trong (backend) của DBMS, thi hành tổ hợp lôgic dẫn đường và các tiện ích và dịch vụ bổ sung.Tính khả cỡ lớn hơnOLAP đa chiều (Multidimensional MOLAP) Hệ thống lưu giữ đa chiều theo mảng (kỹ thuật ma trận thưa)Đánh chỉ mục nhanh tới dữ liệu mô tả (tóm tắt) được tính toán trướcOLAP lai – kết hợp (Hybrid HOLAP)Mềm dẻo cho người dùng, chẳng hạn, mức thấp: quan hệ, mức cao: mảngPhục vụ SQL đặc tảHỗ trợ đặc biệt truy vấn SQL trên các sơ đồ SAO/BÔNG TUYẾTMô hình dữ liệu đa chiềuKhuynh hướng suy nghĩ của người quản lý kinh doanh: “nhiều chiều” (multidimensionally). Ví dụ, khuynh hướng mô tả những gì mà công ty làm:“Chúng tôi kinh doanh các sản phẩm trong nhiều thị trường khác nhau, và chúng tôi đánh giá hiệu quả thực hiện của chúng tôi qua thời gian”.Người thiết kế DWH thường lắng nghe cẩn thận và thêm vào các nhấn mạnh đặc biệt:“Chúng tôi kinh doanh các sản phẩm trong nhiều thị trường khác nhau, và chúng tôi đánh giá hiệu quả thực hiện của chúng tôi qua thời gian”.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3Mô hình dữ liệu đa chiều (2) Trực giác: việc kinh doanh như một khối (cube) dữ liệu: Mỗi nhãn trên mỗi cạnh của khối. Điểm trong khối là các giao điểm của các cạnh. Với mô tả kinh doanh ở trênCạnh là Sản phẩm, Thị trường, và Thời gian. “hiểu” và “tưởng tượng” rằng: điểm trong khối là các độ đo hiệu quả kinh doanh, kết hợp các giá trị Sản phẩm, Thị trường và Thời gian. Mô phỏng các chiều trong kinh doanh 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3XỬ LÝ PHÂN TÍCH TRỰC TUYẾNHệ thống OLAP (On_Line Analysis Processing - Xử lý phân tích trực tuyến)HT quản lý dữ liệu giàu năng lực cho phép phân tích dữ liệu: cắt lát (slice) dữ liệu theo nhiều cạnh khác nhau,khoan xuống (drill down) mức chi tiết hơncuộn lên (roll up) mức tổng hợp hơn. Bản chất cốt lõi của OLAP dữ liệu được lấy ra từ KDL hoặc từ Datamart (kho dữ liệu chủ đề)dữ liệu được chuyển thành mô hình đa chiềudữ liệu được lưu trữ trong một kho dữ liệu đa chiều.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3XỬ LÝ PHÂN TÍCH TRỰC TUYẾNĐối tượng chính của OLAP là khối (cube): một sự biểu diễn đa chiều của dữ liệu chi tiết và tổng thể.Nhắc lại: Khối bao gồm một bảng sự kiện (Fact), một/nhiều bảng chiều (Dimensions), các đơn vị đo (Measures) và các phân hoạch (Partitions).Khối (Cube) : Khối là phần tử chính trong xử lý phân tích trực tuyến, là tập con (subset) dữ liệu từ kho dữ liệu, được tổ chức và tổng hợp trong các cấu trúc đa chiềuChiều (Dimension): Chiều là cách mô tả chủng loại, theo đó các dữ liệu số trong khối được phân bố để phân tích. Đơn vị đo lường (Measures): Đơn vị đo của khối là cột trong bảng Fact. Các đơn vị đo xác định những giá trị số từ bảng Fact, được tổng hợp phân tích như định giá, trị giá, hoặc số lượng bán.Các phân hoạch (Partitions) : Tất cả các khối đều có tối thiểu một phân hoạch để chứa dữ liệu của nó; một phân hoạch đơn được tự động tạo ra khi khối được định nghĩa. 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3Các yêu cầu OLAPĐưa ra tập yêu cầu như một chuẩn mực mà các mô hình dữ liệu đa chiều và các ngôn ngữ truy vấn của OLAP phải đáp ứng.Những yêu cầu này xuất phát từ những thiết kế chủ yếu tổng quát đã thành công với mô hình quan hệ và từ những nét đặc thù của các ứng dụng OLAP: 1. Các nguyên tắc thiết kế chung2. Cấu trúc phức tạp của các chiều 3. Các ô giá trị có cấu trúc phức tạp (về độ đo)4. Các truy vấn điển hình08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CÁC NGUYÊN TẮC THIẾT KẾ CHUNGHình thức thực hiện độc lập: Một mô hình chuẩn phải trong suốt về quan niệm.không chứa bất kỳ 1 chi tiết nào của sự thực hiện. đặc biệt quan trọng trong ứng dụng OLAP như một số hệ thông đã có (gọi là hệ thống ROLAP) thực hiện đa chiều hoá bằng cách sắp đặt mô hình đa chiều logic tới một mô hình quan hệ.Ở đây, tầng quan hệ xem như cấu trúc vật lý lưu trữ dữ liệuCó sự tách biệt giữa cấu trúc và nội dung: Cho phép tách biệt của cấu trúc dữ liệu (tức là khối đa chiều và chiều của các khối đó) và các nội dung (tức là các giá trị ô)Sự mô tả ngôn ngữ truy vấn: Tương tự SQL: ngôn ngữ truy vấn đa chiều cho phép tối ưu hoá các truy vấn và dữ liệu độc lập.Một phép toán logic hay phép toán đại số cho phép các sự tối ưu hoá được xem xét tới cho mục đích này.Một phần yêu cầu chung, các ứng dụng OLAP phải có một số yêu cầu đặc biệt mà không áp dụng cho các lĩnh vực khác của ứng dụng phân tích đa chiều (Ví dụ phân tích hình ảnh, GIS, PACS).08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CẤU TRÚC PHỨC TẠP CHIỀUVí dụ: Nhà máy ô tô muốnPhân tích việc sửa chữa phương tiệnĐể cải tiến sản phẩm, mô tả hợp đồng bảo hiểm mới và đánh giá chất lượng của gara.vấn đề phân tích chính là sửa chữa phương tiện.Các chiều đặc trưng của ứng dụng này là các phương tiện được sửa chữa ví dụ ô tô của ông Simpsongara đã sửa chữa ví dụ, Munich, Main Street 5, và ngày sửa chữa27-6.Các chiều này trải dài trên khối không gian 3 chiều.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CẤU TRÚC PHỨC TẠP CHIỀU(2)Mảng chiều của không gian dữ liệu đa chiều chỉ được cấu trúc bởi các đường được mô tả theo chỉ số (thường mang giá trị nguyên). ứng dụng OLAP: các chỉ số này không đủ do từ khung nhìn của người dùng cuối OLAP, các yếu tố (ví dụ tương ứng) của một chiều OLAP (các chiều thành viên) là không thẳng hàng (ví dụ garage). Tuỳ thuộc vào thứ bậc chứa trong các tầng mà xây dựng các chiều. Mỗi tầng thứ bậc chứa một tập các thành viên.Một ở tầng L1 có thể cuộn lên tầng L2. Ý nghĩa của mối quan hệ nàytầng L2 đưa ra một sự phân loại về khái niệm của L1.Việc mô tả thứ bậc rất cần thiết cho mô hình có cấu trúc tầng. rất cần thiết xác định xem yếu tố nào của tầng thấp sẽ tương đương với yếu tố nào ở tầng cao.Cấu trúc này: cấu trúc thành viên.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CẤU TRÚC PHỨC TẠP CHIỀU (3) Các thứ bậc được sử dụng trong cấu trúc các chiều Cả cấu trúc thành viên và cấu trúc tầng của một chiều: như dùng đồ thị vẽ các thành viên, tầng: nút; quan hệ: cạnh.Hình vẽ: đồ thị thành viên là một cấu trúc cây. Trường hợp đặc biệt: các tầng có thứ tự thẳng hàng nhau do quan hệ với bên trên.Thông thường: cấu trúc thành viên và cấu trúc tầng được mô tả bởi các đồ thị không chu trình. 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CẤU TRÚC PHỨC TẠP Ô GIÁ TRỊNội dung tại một ô của khối đa chiềuđược xây dựng bởi nhiều cách tính khác nhau.một ô có thể chứa một vài độ đo được tạo ra từ một bản ghi. ứng dụng OLAP thường chứa đựng một số lượng lớn các độ đo.các độ đo không là nguyên tử được ước lượng từ các độ đo khác (độ đo nguyên tử/độ đo nhận được) ở trong khối. Phụ thuộc vào các công thức tính toán nhận được từ các độ đo để mô tả các thứ bậc trong các độ đo nguyên tử.Xử lý độ đo phức hợp trong phạm vi tập hợp Vấn đề cần được quan tâm đến.Sự ước lượng của tập hợp các chức năng có thể mang ý nghĩa đầy đủ cho tất cả mọi độ đo 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3CẤU TRÚC PHỨC TẠP Ô GIÁ TRỊ (2) Khái niệm độ đo tương tự với khái niệm khung nhìn trong hệ thống quan hệ Mô tả các độ đo nhận được Cách thức tính toán: một phần của lược đồ cơ sở dữ liệu. Các độ đo nhận được và các độ đo nguyên tửđược xử lý bằng các ngôn ngữ truy vấn.Ngôn ngữ truy vấn cũng có thể hỗ trợ các tính toán đặc biệt được mô tả trong truy vấn đó 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TRUY VẤN ĐIỂN HÌNHCác truy vấn OLAP điển hình chọn từ không gian chiều (hầu hết là 2 chiều). Để hạn chế các chiều của khối kết quả, xác định các tầng có thể được tính toán (ví dụ năm = 1997). Mỗi chiều của một tầng được đưa ra bởi các chiều khácdo sự hạn chế hay bởi trạng thái của một kết quả yêu cầuví dụ: đưa ra cho mỗi tháng. Giới hạn có thể được tạo thành theo công thức sử dụng độ đo trong các vị từví dụ số lượng người lớn hơn 308 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TRUY VẤN ĐIỂN HÌNH (2)Một môi trường OLAP còn được mô tả bởi truy cập dữ liệu.Người dùng tạo các truy vấn sử dụng công thức phụ thuộc vào kết quả của các truy vấn trước đóví dụ chia các giá trị của năm 1997 theo tháng.Thao tác thông thường là thao tác đi xuống /đi lên dùng cấu trúc chiều.Phụ thuộc vào kiểu phân tích mà người dùng muốnChức năng phân tích đặc biệt trở nên cần thiếtVí dụ cho phân tích ABC.Thực tiễn, ngôn ngữ truy vấn có thể kết hợp các hàm người dùng. 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TRUY VẤN ĐIỂN HÌNH (3)Lược đồ đa chiều của ví dụ sử dụng ký hiệu ME/R Ví dụ: Truy vấn: ”Đưa ra trung bình của tổng giá trị mỗi tháng của gara ở Baravia theo loại gara trong suốt năm 1997”.Truy vấn này có nhiều cách hiểu, giả sử hiểu theo nghĩa:Truy vấn hạn chế trên chiều năm (năm =1997) và vùng địa lý (vùng=Baravia). Truy vấn chứa thao tác đi lên từ ngày tới tháng sử dụng phép tính tổng như là một tập hợp các hàm (thực tế chỉ theo một phương tiện sửa chữa), truy vấn liên quan tới tất cả phương tiện sửa chữa cả tháng) 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3Các phương pháp tiếp cận Agrawal, Gupta, Sarawagi Cabibbo, Torlone Li, Wang Gyssens, Lakshmanan Lehner Vassiliadis 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3 TIẾP CẬN CỦA Agrawal, Gupta, SarawagiPhương pháp [AGS97]biểu diễn mô hình dữ liệu đa chiều và các phép toán đại số.tổ chức dữ liệu trong một /nhiều khối lập phương ảo.Giá trị của tất cả các ô có thể là một bộ n hoặc nằm trong tập hợp {0,1}.Ô mang giá trị “1” nghĩa là tổ hợp các giá trị của chiều không gian này tồn tại. Một bộ n biểu diễn một bản ghi có n đơn vị.Ô không mang nội dung được gán giá trị “0”.Chiều không gian không có cấu trúc hoặc thứ tự và các nhân tố được biểu diễn bằng tên.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TIẾP CẬN CỦA Agrawal, Gupta, Sarawagi (2)Phương pháp [AGS97]Trong khối lập phương C có k chiều với n bộ, giá trị của một ô được định nghĩa bằng bộ ba giá trị (D, E(C), N), trong đó D là tập hợp gồm k tên của chiều không gian đó. Mỗi chiều không gian có một miền domi. E(C) là hàm ánh xạ dom1x...x domk đến một bộ n (các giá trị của ô nằm trong khối lập phương C) hoặc đến {0, 1}. N là một bộ n, chứa tên các thành phần của bộ n nằm trong khối lập phương. 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TIẾP CẬN CỦA Cabibbo, TorloneMô hình đa chiều và ngôn ngữ mô tả tương ứng dựa trên tính toán logic ([CT97])Mô hình dữ liệu đa chiều được định nghĩa bằng bảng f như cấu trúc dữ liệu cơ bản.Bảng f là bảng quan hệ chứa một bộ vì mỗi ô trong khối lập phương dữ liệu đều chứa một giá trị.Chiều không gian được định nghĩa bằng cấu trúc đồ thị (DAG) bao gồm các tầng không gian.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3 TIẾP CẬN CỦA Cabibbo, Torlone (2)Một chiều không gianđược định nghĩa là một bộ gồm 3 giá trị (L, ≤, R-UP).L là tập xác định các tầng được sắp xếp theo thứ tự nhỏ đến lớn (ví dụ: gara ≤ vùng).R-UP là tập các hàm định nghĩa ánh xạ từ nhân tố nằm ở tầng thấp đến nhân tố nằm ở tầng cao hơn. (ví dụ gara A, B và C thuộc vùng Bavaria).Mỗi tầng l ϵ L được ánh xạ đến một tập các giá trị gọi là miền của L (ví dụ: dom(gara) = {A, B, C...})Bảng f n chiều: mô hình thực thể trung tâm có dạng như sau: f[A1:l1, .... An:ln]:l0.f là tên của bảng f,li (0≤i≤n) là tên của tầng không gian và Aj (l≤j≤n) là tên của một thuộc tính.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TIẾP CẬN CỦA LI WANGMô hình dữ liệu đa chiều dành cho các ứng dụng OLAP:Cốt lõi của phương pháp này là ngôn ngữ truy vấn đại số, còn gọi là đại số nhóm. Khái niệm cơ bản là một khối lập phương đa chiều chứa các quan hệ, các chiều không gian. Đối với mỗi tổ hợp chiều không gian, có một dữ liệu vô hướng tương ứng đại diện cho một thuộc tính đơn lẻ. một mô hình khái niệm biểu diễn tốt qua nhiều công cụ mạnhcần mở rộng để cung cấp thêm nhiều giá trị phức tạp thay vì chỉ một giá trị vô hướng đơn.cho phép lập mô hình các sự kiện phức tạp trong một khối lập phương thay vì nhiều khối lập phương trên cùng chiều không gian08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TIẾP CẬN CỦA Gyssens, LakshmananPhương pháp Gyssens và Lakshmanan [GL97]giới thiệu khái niệm mô hình dữ liệu đa chiều cho ứng dụng OLAP. Ưu điểm chính là khả năng tách biệt cấu trúc và nội dung. Đưa ra các phép toán đại số và phép tính toán tương đương cho mô hình. Một cơ sở dữ liệu dạng bảng đa hướng là tập hợp các bảng. Gợi nhớ đến lược đồ hình sao, tuy nhiên, ở mức khái niệmChứa các toán tử đại số gồm lựa chọn, chiếu, đổi tên, hợp, phân đoạn, tách biệt, tích Đề-các, các toán tử xây dựng cấu trúc (trải (thêm chiều không gian), gấp (xóa chiều không gian)), phân loại và tóm tắt.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TIẾP CẬN CỦA Lehner [LRT97] mở rộng mô hình đa chiều, cung cấp:2 cơ chế cấu trúc trực giao cho các chiều: sự phân loại các cấp bậc và các đặc trưng. một ngôn ngữ truy vấn (gọi là CQL) dành cho mô hình dữ liệu đa chiều.gồm một mô tả chính thức các mô hình dữ liệu đa chiều cùng với các hỗ trợ mở rộng này và một đại số thao tác dữ liệu.Các mức chiều được sắp xếp thứ tựCân bằng các cấp bậc cây cấu trúc có thể được mô hình hóa.Cấu trúc chiều chỉ được mô tả một cách không chính thức08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TiẾP CẬN CỦA Vassiliadis [Vas98]Mục đích:cung cấp một mô hình gồm các toán tử OLAP tự nhiên (như silicing và drilling) như các toán tử. đưa ra mô hình dữ liệu chính thức và một đại số có thứ tự: đại số quan hệ thích hợp với các cấu trúc dữ liệu mảng tự nhiên.Định nghĩa cơ bản của chiều giống với mô hình MD [CT97]. Một chiều được định nghĩa như một lưới (H, ). H = {DL1,,DLm} là một tập các mức với tên miền dom(DLi) ứng với mỗi mức DLi. Một thuộc tính đặc biệt là cách sử dụng các chiều đa giá trị chiều gồm nhiều hơn một thành viên.Cho phép toán tử chiều tinh vi. Quan hệ ≤ xác định thứ tự bộ phận các mức chiều.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3TiẾP CẬN CỦA VassiliadisMỗi chiều gồm một tập đường dẫn chiều với chỉ một yếu tố duy nhất nếu không đa chiều cấp bậc được định nghĩa trong chiều đó)Các mức chiều của các chiều khác nhau phải được tháo rời ra.một thuộc tính đặc biệt của công việc: toán tử drill-down hiển thị rõ ràng trong mô hình của chúng. Trong khi cube đúng như một toán tử không được rõ ràng trong hầu hết các mô hình, một toán tử tương đương cũng được giơi thiệu trong [Leh98].08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 3So sánh08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 308 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 376Chương 3: Cơ sở về kho dữ liệuKhái niệm kho dữ liệuMô hình dữ liệu đa chiềuKiến trúc kho dữ liệuThi hành kho dữ liệuTừ xây dựng kho dữ liệu tới KPDLSự phát triển mới của công nghệ khối dữ liệu08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 377HiỆU LỰC TÍNH TOÁN KHỐI DỮ LiỆUKhối dữ liệu dược nhìn như dàn các cuboids cuboid thấp nhất là cuboid cơ sởcuboid cao nhất (apex) chứa chỉ một ôSố lượng cuboids trong 1 khối n-chiều với Li mức:Sự thực hiện của khối dữ liệuThực hiện ở mọi (cuboid) (thực hiện hoàn toàn), không (không thực hiện) hoặc bộ phận (thực hiện bộ phận)Lựa chọn các cuboids để thực hiệnDựa theo kích thước, sự phân bổ, tần suất truy nhập vv.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 378Tính toán khốiĐịnh nghĩa khối và tính toán khối trong DMQLdefine cube sales[item, city, year]: sum(sales_in_dollars)compute cube salesBiến đổi vào ngôn ngữ kiểu SQL (với toán tử mới cube by, xem Gray và cộng sự ’96)SELECT item, city, year, SUM (amount)FROM SALESCUBE BY item, city, yearCần tính theo các Group-Bys sau đây(date, product, customer),(date,product),(date, customer), (product, customer),(date), (product), (customer)() (item)(city)()(year)(city, item)(city, year)(item, year)(city, item, year)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 379Tính toán khối: Phương pháp theo ROLAPCác phương pháp tính toán khối hiệu quảROLAP-based cubing algorithms (Agarwal et al’96)Array-based cubing algorithm (Zhao et al’97)Bottom-up computation method (Beyer & Ramarkrishnan’99)H-cubing technique (Han, Pei, Dong & Wang:SIGMOD’01)Thuật toán khối dựa theo ROLAP (Agarwal et al’96)Áp dụng các thao tác sorting, hashing, and grouping tới các thuộc tính chiều theo tứ tự để sắp lạii và phân cụm các bộ liên quanGộp nhóm được thi hành theo tống hợp con như “bước gom nhóm thành phần”Tổng hợp được tính toán từ các tống hợp tính toán có sẵn hớn là từ bảng sự kiện08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 380Tính toán khối: Phương pháp theo ROLAP (2)Phương pháp dựa trên Hash/sort (Agarwal et. al. VLDB’96)Smallest-parent: tính toán một cuboid từ khối được tính toán trước, nhỏ nhấtCache-results: kết quả lưu giữ của một cuboid từ đó các cuboids khác được tính nhằm rút gọn I/O đĩaAmortize-scans: tính toán được nhiều có thể được cuboids tại cùng một thời điểm để hoàn trả đọc đĩaShare-sorts: chia sẽ giá sắp xếp cuboids phức khi dùng phương pháp dựa theo sắp xếpdShare-partitions: chia sẽ giá phân hoạch dọc theo cuboids phức khi dùng thuật toán dựa theo băm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 381Tổng hợp mảng đa cách cho tính toán khốiPhân các mảng thành các khúc (các khối con có thể đặt vào bộ nhớ trong). Địa chỉ mảng rời rạc đwocj nén: (chunk_id, offset)Tính tổng hợp theo “multiway” qua thăm ô cube theo tứh tạ mà cực tiếu số lần thăm mỗi ô, và thu gọn giá truy nhập và lưu trữ bộ nhớWhat is the best traversing order to do multi-way aggregation?AB29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3CB442856402452362060Example 3-D data array of A, B, C08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 382AB29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C442856402452362060BTổng hợp mảng đa cách cho tính toán khối08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 383AB29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C442856402452362060BTổng hợp mảng đa cách cho tính toán khối08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 384Method: the planes should be sorted and computed according to their size in ascending order.See the details of Example 3-D data array of A, B, CIdea: keep the smallest plane in the main memory, fetch and compute only one chunk at a time for the largest planeLimitation of the method: computing well only for a small number of dimensionsIf there are a large number of dimensions, “bottom-up computation” and iceberg cube computation methods can be exploredTổng hợp mảng đa cách cho tính toán khối08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 385Chỉ mục dữ liệu OLAP: Chỉ mục BitmapIndex on a particular columnEach value in the column has a bit vector: bit-op is fastThe length of the bit vector: # of records in the base tableThe i-th bit is set if the i-th row of the base table has the value for the indexed columnnot suitable for high cardinality domainsBase tableIndex on RegionIndex on Type08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 386Chỉ mục dữ liệu OLAP: kết nối chỉ mụcJoin index: JI(R-id, S-id) where R (R-id, )  S (S-id, )Traditional indices map the values to a list of record idsIt materializes relational join in JI file and speeds up relational join — a rather costly operationIn data warehouses, join index relates the values of the dimensions of a start schema to rows in the fact table.E.g. fact table: Sales and two dimensions city and productA join index on city maintains for each distinct city a list of R-IDs of the tuples recording the Sales in the city Join indices can span multiple dimensions08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 387Xử lý hiệu quả câu hỏi OLAPDetermine which operations should be performed on the available cuboids:transform drill, roll, etc. into corresponding SQL and/or OLAP operations, e.g, dice = selection + projectionDetermine to which materialized cuboid(s) the relevant operations should be applied.Exploring indexing structures and compressed vs. dense array structures in MOLAP08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 388Kho chứa MetadataMeta data is the data defining warehouse objects. It has the following kinds Description of the structure of the warehouseschema, view, dimensions, hierarchies, derived data defn, data mart locations and contentsOperational meta-datadata lineage (history of migrated data and transformation path), currency of data (active, archived, or purged), monitoring information (warehouse usage statistics, error reports, audit trails)The algorithms used for summarizationThe mapping from operational environment to the data warehouseData related to system performancewarehouse schema, view and derived data definitionsBusiness databusiness terms and definitions, ownership of data, charging policies08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 389Công cụ và tiện ích có sẵn KDLData extraction:get data from multiple, heterogeneous, and external sourcesData cleaning:detect errors in the data and rectify them when possibleData transformation:convert data from legacy or host format to warehouse formatLoad:sort, summarize, consolidate, compute views, check integrity, and build indicies and partitionsRefreshpropagate the updates from the data sources to the warehouse08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 390Chương 3: Cơ sở về kho dữ liệuKhái niệm kho dữ liệuMô hình dữ liệu đa chiềuKiến trúc kho dữ liệuThi hành kho dữ liệuTừ xây dựng kho dữ liệu tới KPDLSự phát triển mới của công nghệ khối dữ liệu08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 391Thăm dò theo phát hiện các khối dữ liệuHypothesis-drivenThăm dò theo người dùng, không gian tìm kiếm lớnDiscovery-driven (Sarawagi, et al.’98)Dẫn dường hiệu quả khối dữ liệu OLAP lớnTính toán được độ đo biểu lộ loại trừ, hướng người dùng vào phân tích dữ liệu, tại mọimức của tổng hợpLoại trừ: khác biệt đáng kể từ giá trị được đoán trước, dựa theo mô hình thống kêDốc trực quan như màu nền được dùng để phản ánh độ loại trừ của mỗi ô08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 392Kiểu loại trừ cad tính toán chúngTham sốSelfExp: chụp các ô liên quan tới các ô khác cùngmức tổng hợpInExp: chụp phía dưới của ôPathExp: chụp phía dưới của ô theo mỗi đường khoan xuốngTính toán chỉ số loại trừ (thiết đặt mô hình và tính các giá trị SelfExp, InExp, and PathExp) có thể gối vào xây dựng khốiLoại từ tự chính có thể được bảo quản, chỉ mục và tìm kiếm như một tổng hợp tính toán trước08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 393Ví dụ: Khối dữ liệu theo phát hiện08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 394Complex Aggregation at Multiple Granularities: Multi-Feature CubesMulti-feature cubes (Ross, et al. 1998): Compute complex queries involving multiple dependent aggregates at multiple granularitiesEx. Grouping by all subsets of {item, region, month}, find the maximum price in 1997 for each group, and the total sales among all maximum price tuplesselect item, region, month, max(price), sum(R.sales)from purchaseswhere year = 1997cube by item, region, month: Rsuch that R.price = max(price)Continuing the last example, among the max price tuples, find the min and max shelf live, and find the fraction of the total sales due to tuple that have min shelf life within the set of all max price tuples08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 395Cube-Gradient (Cubegrade)Analysis of changes of sophisticated measures in multi-dimensional spacesQuery: changes of average house price in Vancouver in ‘00 comparing against ’99Answer: Apts in West went down 20%, houses in Metrotown went up 10%Cubegrade problem by Imielinski et al.Changes in dimensions  changes in measuresDrill-down, roll-up, and mutation08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 396From Cubegrade to Multi-dimensional Constrained Gradients in Data CubesSignificantly more expressive than association rulesCapture trends in user-specified measuresSerious challengesMany trivial cells in a cube  “significance constraint” to prune trivial cellsNumerate pairs of cells  “probe constraint” to select a subset of cells to examineOnly interesting changes wanted “gradient constraint” to capture significant changes08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 397MD Constrained Gradient Minin