Các data cube tạo điều kiện thuận lợi cho việc xử lý phân tích trực tuyến dữ liệu đa chiều. “Nhưng làm thế nào chúng ta có thể tính toán trước các data cube để chúng tiện dụng và sẵn sàng cho việc xử lý truy vấn?” Phần này trái ngược việc vật chất hóa toàn bộ hình khối (tức là tính toán trước) với các chiến lược khác nhau để vật liệu hóa một phần hình khối. Để có sự hoàn chỉnh, chúng ta bắt đầu bằng việc xem xét các thuật ngữ cơ bản liên quan đến các data cube. Chúng tôi cũng giới thiệu một ký hiệu ô lập phương rất hữu ích để mô tả các phương pháp tính toán Cube.
Các bài viết liên quan:
Full Cube, Iceberg Cube, Closed Cube và Cube Shell
Hình dưới cho thấy một data cube 3-D cho các kích thước A, B và C, và một số liệu tổng hợp, M. Các thước đo thường được sử dụng bao gồm count (), sum (), min (), max () và tổng bán hàng(). Một data cube là một mạng lưới các Cube. Mỗi hình khối đại diện cho một nhóm. ABC là hình lập phương có cả ba kích thước. Ở đây, số đo tổng hợp, M, được đưa vào cho mỗi sự kết hợp có thể có của ba dimensions.
Hình khối cơ sở là hình khối ít tổng quát nhất trong số các hình khối trong data cube. Hình khối khái quát nhất là hình khối chóp, thường được biểu diễn như tất cả. Nó chứa một giá trị nó tổng hợp số đo M cho tất cả các bộ giá trị được lưu trữ trong khối cơ sở. Để đi sâu vào data cube, chúng ta di chuyển từ khối chóp xuống dưới trong mạng tinh thể. Để cuộn lên, chúng tôi di chuyển từ hình khối cơ sở lên trên. Với mục đích thảo luận của chúng ta trong chương này, chúng ta sẽ luôn sử dụng thuật ngữ data cube để chỉ một mạng hình khối hơn là một Cube riêng lẻ.
Mạng các hình khối tạo nên một data cube 3-D với các kích thước A, B và C cho một số đo tổng hợp, M.
Một ô trong hình khối cơ sở là một cell base. Một ô từ một khối non base là một ô tổng hợp. Một ô tổng hợp tổng hợp trên một hoặc nhiều dimensions, trong đó mỗi dimensions tổng hợp được biểu thị bằng dấu ∗ trong ký hiệu ô. Giả sử chúng ta có một data cube n chiều.
Gọi a (a1, a2,…, An, mesule) là một ô từ một trong các Cube tạo nên data cube. Chúng ta nói rằng a là một ô m chiều (tức là từ một Cube m chiều) nếu có đúng m (m, n) giá trị trong số a1, a2 ,. . . , an không có *. Nếu m = n thì a là một ô cơ sở; nếu không, nó là một ô tổng hợp (tức là, trong đó m <n).
Ô cơ sở và tổng hợp. Hãy xem xét một data cube với dimensions tháng, thành phố và nhóm khách hàng cũng như đo lường doanh số bán hàng. (Jan,, *, 2800) và (Chicago, 1200) là các ô 1-D; (Jan, Business, 150) là ô 2-D; và (Jan, Chicago, Business, 45) là ô 3-D.
Ở đây, tất cả các ô cơ sở là 3-D, trong khi các ô 1-D và 2-D là các ô tổng hợp.
Mối quan hệ cha – con có thể tồn tại giữa các ô. Trong data cube n chiều, ô i-D a = (a1, a2,…, An, Measure a) là tổ tiên của ô j-D b = (b1, b2,.., Bn, Measure b) và b là con của a, nếu và chỉ khi (1) i <j, và (2) với 1 ≤ k ≤ n, ak = bk bất cứ khi nào ak / = ∗. Cụ thể, ô a được gọi là cha của ô b và b là con của a, nếu và chỉ khi j = i + 1.
Tổ tiên và các tế bào con cháu. Tham chiếu đến Ví dụ trên, ô 1-D a (Jan,,, 2800) và ô 2-D b (Jan,, Business, 150) là tổ tiên của ô 3-D c (Jan, Chicago, Business, 45); c là hậu duệ của cả a và b; b là cha mẹ của c; và c là con của b.
Để đảm bảo OLAP nhanh, đôi khi cần tính toán trước toàn bộ Cube (tức là tất cả các ô của tất cả các Cube cho một data cube nhất định). Phương pháp tính toán cube full được nêu trong Phần sau. Tuy nhiên, tính toán full Cube là cấp số nhân với số kích thước. Tức là, một data cube có n kích thước chứa 2n Cube. Thậm chí còn có nhiều hình khối hơn nếu chúng ta xem xét phân cấp khái niệm cho mỗi kích thước.1 Ngoài ra, kích thước của mỗi hình khối phụ thuộc vào số lượng các kích thước của nó. Do đó, việc tính toán trước toàn bộ Cube có thể yêu cầu một lượng lớn bộ nhớ và thường là quá nhiều.
Tuy nhiên, các thuật toán tính toán cube full là rất quan trọng. Các Cube riêng lẻ có thể được lưu trữ trên bộ lưu trữ thứ cấp và được truy cập khi cần thiết. Ngoài ra, chúng ta có thể sử dụng các thuật toán như vậy để tính toán các hình khối nhỏ hơn, bao gồm một tập con của tập hợp kích thước đã cho hoặc một phạm vi nhỏ hơn của các giá trị có thể có đối với một số kích thước.
Trong những trường hợp này, hình lập phương nhỏ hơn là hình lập phương đầy đủ cho tập con kích thước và / hoặc giá trị dimensions đã cho. Sự hiểu biết thấu đáo về các phương pháp tính toán cube full sẽ giúp chúng tôi phát triển các phương pháp hiệu quả để tính toán Cube từng phần. Do đó, điều quan trọng là phải khám phá các phương pháp có thể mở rộng để tính toán tất cả các Cube tạo nên một data cube, nghĩa là để hiện thực hóa đầy đủ. Các phương pháp này phải tính đến lượng bộ nhớ chính có hạn để tính toán Cube, tổng kích thước của data cube được tính toán, cũng như thời gian cần thiết để tính toán như vậy.
Hiện thực hóa một phần các data cube mang lại sự cân bằng thú vị giữa không gian lưu trữ và thời gian phản hồi cho OLAP. Thay vì tính toán toàn bộ Cube, chúng ta chỉ có thể tính toán một tập hợp con của các Cube dữ liệu hoặc các ống con bao gồm các tập hợp con của các ô từ các Cube khác nhau.
Nhiều ô trong một Cube thực sự có thể ít hoặc không được nhà phân tích dữ liệu quan tâm. Nhớ lại rằng mỗi ô trong một khối đầy đủ ghi lại một giá trị tổng hợp chẳng hạn như số hoặc tổng. Đối với nhiều ô trong một Cube, giá trị đo sẽ bằng không. Khi tích của các thẻ số đối với các kích thước trong một hình lập phương lớn so với số lượng các bộ giá trị khác không được lưu trữ trong hình lập phương, thì chúng ta nói rằng hình lập phương đó thưa thớt. Nếu một hình lập phương chứa nhiều hình lập phương thưa thớt, chúng ta nói rằng hình lập phương đó là hình lập phương thưa thớt.
Trong nhiều trường hợp, một lượng lớn không gian của Cube có thể bị chiếm dụng bởi một số lượng lớn các ô có giá trị số đo rất thấp. Điều này là do các ô hình khối thường được phân bố khá thưa thớt trong một không gian đa chiều.
Ví dụ, một khách hàng có thể chỉ mua một vài mặt hàng trong một cửa hàng tại một thời điểm. Một sự kiện như vậy sẽ chỉ tạo ra một vài ô trống, để trống hầu hết các ô hình khối khác. Trong những tình huống như vậy, sẽ hữu ích nếu chỉ cụ thể hóa những ô đó trong một hình khối (từng nhóm) với giá trị đo trên một số ngưỡng tối thiểu.
Chẳng hạn, trong một data cube dành cho bán hàng, chúng tôi có thể chỉ muốn thực hiện hóa những ô có số lượng 10 (tức là, trong đó ít nhất 10 bộ tồn tại cho tổ hợp dimensions nhất định của ô) hoặc chỉ những ô đó đại diện cho doanh số 100 đô la. Điều này không chỉ tiết kiệm thời gian xử lý và không gian đĩa mà còn dẫn đến phân tích tập trung hơn. Các ô không thể vượt qua ngưỡng có thể là quá nhỏ để đảm bảo phân tích thêm.
Những cube được thực hiện một phần như vậy được gọi là iceberg cubes. Ngưỡng tối thiểu được gọi là ngưỡng hỗ trợ tối thiểu, gọi tắt là ngưỡng hỗ trợ tối thiểu (min sup). Bằng cách vật chất hóa chỉ một phần nhỏ các ô trong một data cube, kết quả được coi là “phần nổi của iceberg cube”, trong đó “iceberg cube” là khối đầy tiềm năng bao gồm tất cả các ô.
Ví dụ Iceberg cube :
compute cube sales iceberg as select month, city, customer group, count(*) from salesInfo cube by month, city, customer group having count(*) >D min sup
Câu lệnh tính toán Cube chỉ định tính toán trước của khối iceberg cube, iceberg cube bán hàng, với dimensions tháng, thành phố và nhóm khách hàng và số đo tổng hợp (). Các bộ giá trị đầu vào nằm trong mối quan hệ salesInfo. Mệnh đề Cube xác định rằng các tổng hợp (từng nhóm) sẽ được tạo thành cho mỗi tập con có thể có của các kích thước đã cho.
Nếu chúng ta tính toán cube full, mỗi nhóm sẽ tương ứng với một Cube trong mạng tinh thể data cube. Ràng buộc được chỉ định trong mệnh đề có được gọi là điều kiện iceberg cube. Ở đây, số đo iceberg cube là count (). Lưu ý rằng khối iceberg cube được tính ở đây có thể được sử dụng để trả lời từng truy vấn theo nhóm trên bất kỳ tổ hợp nào của các kích thước được chỉ định của biểu mẫu có đếm (*)> v, trong đó v min sup. Thay vì count (), điều kiện tảng băng có thể chỉ định các số đo phức tạp hơn chẳng hạn như average ().
Nếu chúng ta bỏ qua mệnh đề có, chúng ta sẽ có một cube full. Hãy gọi đây là Cube bán hàng. Khối iceberg cube, tảng băng bán hàng, loại trừ tất cả các ô của khối bán hàng có số lượng nhỏ hơn min sup. Rõ ràng, nếu chúng ta đặt mức hỗ trợ tối thiểu là 1 trong tảng băng bán hàng, Cube thu được sẽ là khối hoàn chỉnh, khối bán hàng.
Một cách tiếp cận ngây thơ để tính toán một khối băng trôi trước tiên sẽ là tính toán cube full và sau đó cắt bỏ các ô không thỏa mãn điều kiện iceberg cube. Tuy nhiên, điều này vẫn rất tốn kém. Một cách tiếp cận hiệu quả là chỉ tính toán trực tiếp khối băng trôi mà không tính toàn khối.
Việc giới thiệu các khối iceberg cube sẽ giảm bớt gánh nặng của việc tính toán các ô tổng hợp tầm thường trong một data cube. Tuy nhiên, chúng tôi vẫn có thể kết thúc với một số lượng lớn các ô không quan tâm để tính toán.
Ví dụ: giả sử rằng có 2 ô cơ sở cho cơ sở dữ liệu 100 dimen, được ký hiệu là (a1, a2, a3,…, A100): 10, (a1, a2, b3,.., B100) : 10, trong đó mỗi ô có số lượng ô là 10. Nếu hỗ trợ tối thiểu được đặt thành 10, sẽ vẫn có một số ô có thể tính toán và lưu trữ, mặc dù hầu hết chúng không thú vị.
Ví dụ: có 2101 – 6 ô tổng hợp riêng biệt, 2 ô như {(a1, a2, a3, a4,…, A99, ∗): 10 ,. . . , (a1, a2,, a4,…, a99, a100): 10 ,. . . , (a1, a2, a3,…,): 10, nhưng hầu hết chúng không chứa nhiều thông tin mới.
Nếu chúng ta bỏ qua tất cả các ô tổng hợp có thể nhận được bằng cách thay thế một số hằng số bằng ∗ trong khi vẫn giữ nguyên giá trị số đo, thì chỉ còn lại ba ô riêng biệt: (a1, a2, a3,.., A100): 10, (a1, a2, b3,…, b100): 10, (a1, a2,…,): 20. Tức là, trong số 2101 4 ô cơ sở và tổng hợp riêng biệt, chỉ có ba ô thực sự cung cấp thông tin có giá trị.
Ba ô kín tạo thành mạng tinh thể của một hình lập phương khép kín.
Để nén một data cube một cách có hệ thống, chúng ta cần đưa ra khái niệm về vùng phủ kín. Một ô, c, là một ô đóng nếu không tồn tại ô, d, sao cho d là sự đặc biệt hóa (con) của ô c (tức là, trong đó d nhận được bằng cách thay thế trong c bằng một giá trị khác), và d có cùng giá trị số đo với c. Cube closed là data cube chỉ bao gồm các ô đã đóng.
Ví dụ: ba ô dẫn xuất trong đoạn trước là bao đóng của data cube cho tập dữ liệu {(a1, a2, a3,…, A100): 10, (a1, a2, b3, …, b100):10. Chúng tạo thành mạng tinh thể của một hình lập phương khép kín. Các ô không kín khác có thể bắt nguồn từ các ô đóng tương ứng của chúng trong mạng tinh thể này. Ví dụ: “(a1, ∗, ∗,…, ∗): 20” có thể được bắt nguồn từ “(a1, a2, ∗,…, ∗): 20” vì ô trước là ô không khép kín tổng quát của cái sau. Tương tự, chúng ta có “(a1, a2, b3,…,): 10.”
Một chiến lược khác để thực hiện hóa từng phần là chỉ tính toán trước các Cube đưa vào một số lượng nhỏ kích thước chẳng hạn như ba đến năm. Các Cube này tạo thành một vỏ khối cho data cube tương ứng. Các truy vấn về sự kết hợp bổ sung của các dimensions sẽ phải được tính toán nhanh chóng. Ví dụ: chúng ta có thể tính toán tất cả các hình khối có ba chiều hoặc nhỏ hơn trong một data cube n chiều, dẫn đến một khối hình khối có kích thước là 3. Tuy nhiên, điều này vẫn có thể dẫn đến một số lượng lớn các Cube để tính toán, đặc biệt khi n là lớn. Ngoài ra, chúng ta có thể chọn chỉ tính toán trước các phần hoặc các mảnh của vỏ hình khối dựa trên các Cube quan tâm.
Các chiến lược chung cho tính toán data cube
Có một số phương pháp để tính toán data cube hiệu quả, dựa trên các loại khối khác nhau được mô tả . Nói chung, có hai cấu trúc dữ liệu cơ bản được sử dụng để lưu trữ cube. Việc triển khai OLAP quan hệ (ROLAP) sử dụng bảng quan hệ, trong khi mảng đa chiều được sử dụng trong OLAP đa chiều (MOLAP). Mặc dù ROLAP và MOLAP có thể khám phá các kỹ thuật tính toán Cube khác nhau, nhưng một số “thủ thuật” tối ưu hóa có thể được chia sẻ giữa các biểu diễn dữ liệu khác nhau. Sau đây là các kỹ thuật tối ưu hóa chung để tính toán hiệu quả các data cube.
Kỹ thuật tối ưu hóa 1:
Sắp xếp, băm và nhóm. Các thao tác sắp xếp, băm và nhóm nên được áp dụng cho các thuộc tính dimensions để sắp xếp lại và phân cụm các bộ giá trị liên quan.
Trong tính toán Cube, tổng hợp được thực hiện trên các bộ giá trị (hoặc ô) có chung một bộ giá trị dimensions. Do đó, điều quan trọng là phải khám phá các hoạt động sắp xếp, băm và nhóm để truy cập và nhóm các dữ liệu đó lại với nhau để tạo điều kiện thuận lợi cho việc tổng hợp các tổng hợp đó.
Ví dụ: để tính tổng doanh số bán hàng theo chi nhánh, ngày và mặt hàng, có thể hiệu quả hơn nếu sắp xếp các bộ giá trị hoặc ô theo nhánh, sau đó theo ngày, sau đó nhóm chúng theo tên mặt hàng. Việc triển khai hiệu quả các hoạt động như vậy trong các tập dữ liệu lớn đã được nghiên cứu rộng rãi trong cộng đồng nghiên cứu cơ sở dữ liệu. Việc triển khai như vậy có thể được mở rộng sang tính toán data cube.
Kỹ thuật này cũng có thể được mở rộng hơn nữa để thực hiện chia sẻ sắp xếp (tức là chia sẻ chi phí sắp xếp trên nhiều hình khối khi sử dụng phương pháp dựa trên sắp xếp) hoặc để phân chia theo hình thức phân vùng chia sẻ (tức là chia sẻ chi phí phân vùng trên nhiều hình khối khi băm thuật toán dựa trên được sử dụng).
Kỹ thuật tối ưu hóa 2:
Tổng hợp đồng thời và lưu vào bộ nhớ đệm của các kết quả trung gian. Trong tính toán Cube, sẽ hiệu quả hơn khi tính các tổng mức cao hơn từ các tổng mức thấp hơn đã được tính toán trước đó, thay vì từ bảng dữ kiện cơ sở. Hơn nữa, việc tổng hợp đồng thời từ các kết quả tính toán trung gian được lưu trong bộ nhớ cache có thể dẫn đến việc giảm các hoạt động xuất / nhập đĩa (I / O) tốn kém.
Ví dụ: để tính toán doanh số bán hàng theo chi nhánh, chúng ta có thể sử dụng các kết quả trung gian thu được từ việc tính toán Cube cấp thấp hơn, chẳng hạn như doanh số bán hàng theo chi nhánh và ngày. Kỹ thuật này có thể được mở rộng hơn nữa để thực hiện quét phân bổ (tức là tính toán cùng lúc nhiều Cube nhất có thể để phân bổ số lần đọc đĩa).
Kỹ thuật tối ưu hóa 3:
Tổng hợp từ con nhỏ nhất khi tồn tại nhiều hình khối con. Khi tồn tại nhiều hình khối con, thường sẽ hiệu quả hơn để tính toán hình khối mẹ mong muốn (tức là tổng quát hơn) từ hình khối con nhỏ nhất, đã được tính toán trước đó.
Để tính toán Cube bán hàng, Cbranch, khi tồn tại hai Cube đã tính toán trước đó, ví dụ: C{branch, year} và C{branch, item}, rõ ràng là tính toán Cbranch từ cái trước hơn là từ cái sau nếu có là nhiều mặt hàng khác biệt hơn so với các năm riêng biệt.
Nhiều kỹ thuật tối ưu hóa khác có thể cải thiện hơn nữa hiệu quả tính toán. Ví dụ: các thuộc tính kích thước chuỗi có thể được ánh xạ tới các số nguyên với các giá trị khác nhau, từ 0 đến bản số của thuộc tính.
Trong tính toán khối iceberg cube, kỹ thuật tối ưu hóa sau đây đóng một vai trò đặc biệt quan trọng.
Kỹ thuật tối ưu hóa 4:
Phương pháp cắt tỉa Apriori có thể được khám phá để tính toán các khối băng trôi một cách hiệu quả. Thuộc tính Apriori, 3 trong ngữ cảnh data cube, phát biểu như sau: Nếu một ô nhất định không đáp ứng mức hỗ trợ tối thiểu, thì không có phần nào giảm dần của ô (tức là ô chuyên biệt hơn) sẽ đáp ứng mức hỗ trợ tối thiểu. Thuộc tính này có thể được sử dụng để giảm đáng kể việc tính toán các khối iceberg cube.
Hãy nhớ lại rằng đặc điểm kỹ thuật của khối tảng băng chứa một điều kiện iceberg cube, đó là một hạn chế đối với các tế bào được vật chất hóa. Một điều kiện tảng băng phổ biến là các ô phải đáp ứng ngưỡng hỗ trợ tối thiểu chẳng hạn như số hoặc tổng tối thiểu.
Trong tình huống này, thuộc tính Apriori có thể được sử dụng để loại bỏ việc khám phá các con cháu của tế bào. Ví dụ: nếu số lượng ô, c, trong Cube nhỏ hơn ngưỡng hỗ trợ tối thiểu, v, thì số lượng ô con của bất kỳ ô con nào của c trong Cube cấp thấp hơn không bao giờ được lớn hơn hoặc bằng v, và do đó có thể được cắt tỉa. Nói cách khác, nếu một điều kiện (ví dụ: điều kiện tảng băng được chỉ định trong mệnh đề có) bị vi phạm đối với một số ô c, thì mọi con cháu của c cũng sẽ vi phạm điều kiện đó. Các biện pháp tuân theo đặc tính này được gọi là antimonotonic.
4 Hình thức cắt tỉa này đã được thực hiện phổ biến trong khai thác mẫu thường xuyên, nhưng cũng hỗ trợ tính toán data cube bằng cách cắt giảm yêu cầu về thời gian xử lý và dung lượng đĩa. Nó có thể dẫn đến một phân tích tập trung hơn vì các ô không thể vượt qua ngưỡng không có khả năng lãi.
Trong các phần tiếp theo, chúng tôi giới thiệu một số phương pháp phổ biến để tính toán Cube hiệu quả nhằm khám phá các chiến lược tối ưu hóa này.
Phương pháp tính toán Cube dữ liệu
Tính toán data cube là một nhiệm vụ thiết yếu trong việc triển khai Data Warehouse. Việc tính toán trước tất cả hoặc một phần của data cube có thể làm giảm đáng kể thời gian phản hồi và nâng cao hiệu suất của quá trình xử lý phân tích trực tuyến. Tuy nhiên, việc tính toán như vậy là một thách thức vì nó có thể yêu cầu thời gian tính toán và không gian lưu trữ đáng kể. .
Tổng hợp mảng nhiều đường cho tính toán toàn Cube
Phương thức tổng hợp mảng nhiều chiều (hay đơn giản là MultiWay) tính toán một data cube full bằng cách sử dụng một mảng nhiều chiều làm cấu trúc dữ liệu cơ bản của nó. Đây là cách tiếp cận MOLAP điển hình sử dụng địa chỉ mảng trực tiếp, trong đó các giá trị dimensions được truy cập thông qua vị trí hoặc chỉ mục của các vị trí mảng tương ứng của chúng. Do đó, MultiWay không thể hình thành bất kỳ thứ tự sắp xếp lại dựa trên giá trị nào như một kỹ thuật tối ưu hóa. Một cách tiếp cận khác được phát triển cho việc xây dựng cube dựa trên mảng, như sau:
Phân chia mảng thành nhiều phần.
Chunk là một khối con đủ nhỏ để vừa với bộ nhớ có sẵn để tính toán khối. Chunking là một phương pháp để chia một mảng n chiều thành các phần nhỏ n chiều, trong đó mỗi phần được lưu trữ dưới dạng một đối tượng trên đĩa. Các phần được nén để loại bỏ không gian lãng phí do các ô mảng trống. Một ô trống nếu nó không chứa bất kỳ dữ liệu hợp lệ nào (tức là số ô của nó là 0). Ví dụ: “chunkID offset” có thể được sử dụng như một cơ chế định địa chỉ ô để nén cấu trúc mảng thưa thớt và khi tìm kiếm các ô trong một đoạn. Một kỹ thuật nén như vậy rất mạnh trong việc xử lý các khối thưa thớt, cả trên đĩa và trong bộ nhớ.
Tính toán tổng hợp bằng cách truy cập (tức là truy cập các giá trị tại) các ô hình khối.
Thứ tự các ô được truy cập có thể được tối ưu hóa để giảm thiểu số lần mỗi ô phải được truy cập lại, do đó giảm chi phí truy cập bộ nhớ và lưu trữ. Bí quyết là khai thác thứ tự này để các phần của các ô tổng hợp trong nhiều hình khối có thể được tính toán đồng thời và tránh mọi việc truy cập lại các ô không cần thiết.
Kỹ thuật phân khúc này liên quan đến việc “chồng chéo” một số phép tính tổng hợp; do đó, nó được gọi là tập hợp mảng nhiều đường. Nó thực hiện tổng hợp đồng thời, tức là nó tính các tổng hợp đồng thời trên nhiều chiều.
Chúng tôi giải thích cách tiếp cận này để xây dựng hình khối dựa trên mảng bằng cách xem xét một ví dụ cụ thể.
Ví dụ: Tính toán Cube nhiều mảng. Hãy xem xét một mảng dữ liệu 3-D chứa ba kích thước A, B và C. Mảng 3-D được phân chia thành các phần nhỏ dựa trên bộ nhớ. Trong ví dụ này, mảng được chia thành 64 phần như thể hiện trong Hình 45.
Phân vùng A được tổ chức thành bốn phân vùng có kích thước bằng nhau: a0, a1, a2 và a3. Kích thước B và C được tổ chức tương tự nhau thành bốn phân vùng. Chunks 1, 2 ,. . . , 64 tương ứng với các ống con a0b0c0, a1b0c0 ,. . . , a3b3c3, tương ứng. Giả sử rằng bản số của các kích thước A, B và C lần lượt là 40, 400 và 4000. Do đó, kích thước của mảng cho mỗi dimensions, A, B và C, cũng tương ứng là 40, 400 và 4000. Do đó, kích thước của mỗi phân vùng trong A, B và C lần lượt là 10, 100 và 1000. Việc thực hiện đầy đủ data cube tương ứng liên quan đến việc tính toán tất cả các khối xác định khối này. cube full thu được bao gồm các Cube sau:
Hình 45: Mảng 3-D cho các kích thước A, B và C, được tổ chức thành 64 phần. Mỗi đoạn đủ nhỏ để vừa với bộ nhớ có sẵn để tính toán Cube. Dấu ∗ cho biết các phần từ 1 đến 13 đã được tổng hợp cho đến nay trong quá trình này.
- Cube cơ sở, được ký hiệu là ABC (từ đó tất cả các Cube khác được tính trực tiếp hoặc gián tiếp). Cube này đã được tính toán và tương ứng với mảng 3-D đã cho.
- Các hình lập phương 2-D, AB, AC và BC, tương ứng với từng nhóm
- AB, AC và BC. Các Cube này phải được tính toán.
- Các Cube 1-D, A, B và C, tương ứng với từng nhóm của A, B và C. Các Cube này phải được tính toán.
- Cube 0-D (đỉnh), được biểu thị bằng tất cả, tương ứng với group-by (); nghĩa là, không có từng nhóm ở đây. Cube này phải được tính toán. Nó chỉ bao gồm một giá trị. Giả sử, nếu số đo data cube là số đếm, thì giá trị được tính chỉ đơn giản là tổng số của tất cả các bộ giá trị trong ABC.
BUC: Tính toán các khối iceberg cube từ Apex Cuboid trở xuống
BUC là một thuật toán để tính toán các khối băng trôi và thưa thớt. Không giống như MultiWay, BUC xây dựng Cube từ khối chóp về phía Cube cơ sở. Điều này cho phép BUC chia sẻ chi phí phân vùng dữ liệu. Trình tự xử lý này cũng cho phép BUC cắt tỉa trong quá trình xây dựng, sử dụng thuộc tính Apriori.
Hình 5.5 cho thấy một mạng lưới các Cube, tạo nên một data cube 3-D với các kích thước A, B và C. Cube đỉnh (0-D), đại diện cho khái niệm tất cả (tức là, (,,)), là đỉnh của mạng tinh thể. Đây là mức tổng hợp hoặc khái quát nhất. Hình lập phương cơ sở 3-D, ABC, nằm ở đáy của mạng tinh thể. Đây là mức tổng hợp ít nhất (chi tiết nhất hoặc chuyên biệt nhất). Cách biểu diễn này của một mạng hình khối, với đỉnh ở trên cùng và đáy ở dưới, thường được chấp nhận trong Data Warehouse. Nó hợp nhất các khái niệm về chi tiết (nơi chúng ta có thể di chuyển từ ô được tổng hợp cao đến các ô thấp hơn, chi tiết hơn) và cuộn lên (nơi chúng tôi có thể di chuyển từ các ô chi tiết, cấp thấp sang các ô cấp cao hơn, tổng hợp hơn).
BUC là viết tắt của “Bottom-Up Construction”. Tuy nhiên, theo quy tắc mạng được mô tả trước đây và được sử dụng trong suốt cuốn sách này, thứ tự xử lý BUC thực sự là từ trên xuống! Các tác giả BUC xem một mạng lưới các hình khối theo thứ tự ngược lại, với hình khối đỉnh ở dưới cùng và hình khối cơ sở ở trên cùng. Theo quan điểm đó, BUC thực hiện xây dựng từ dưới lên. Tuy nhiên, bởi vì chúng tôi áp dụng thế giới quan ứng dụng trong đó khoan xuống đề cập đến việc khoan từ hình khối chóp xuống phía dưới hình khối cơ sở, quá trình thăm dò của BUC được coi là từ trên xuống. Sự thăm dò của BUC để tính toán data cube 3-D được thể hiện trong Hình 47.
Hình 47: Khám phá của BUC để tính toán data cube 3-D. Lưu ý rằng tính toán bắt đầu từ khối chóp.
Thuật toán BUC được trình bày ở trang tiếp theo. Đầu tiên chúng tôi đưa ra một giải thích về thuật toán và sau đó tiếp theo là một ví dụ. Ban đầu, thuật toán được gọi với quan hệ đầu vào (tập hợp các bộ giá trị). BUC tổng hợp toàn bộ đầu vào (dòng 1) và ghi tổng kết quả (dòng 3). (Dòng 2 là một tính năng tối ưu hóa sẽ được thảo luận ở phần sau trong ví dụ của chúng ta.) Đối với mỗi chiều d (dòng 4), đầu vào được phân vùng trên d (dòng 6). Trả về từ Partition (), dataCount chứa tổng số bộ giá trị cho mỗi giá trị riêng biệt của dimensions d. Mỗi giá trị riêng biệt của d tạo thành phân vùng riêng của nó. Dòng 8 lặp qua mỗi phân vùng. Dòng 10 kiểm tra phân vùng để được hỗ trợ tối thiểu. Nghĩa là, nếu số lượng bộ giá trị trong phân vùng thỏa mãn (tức là) hỗ trợ tối thiểu, thì phân vùng sẽ trở thành quan hệ đầu vào cho một lệnh gọi đệ quy được thực hiện tới BUC, tính toán khối iceberg cube trên các phân vùng cho các kích thước từ d 1 đến numDims (dòng 12). Lưu ý rằng đối với một cube full (tức là, trong đó hỗ trợ tối thiểu trong mệnh đề có là 1), điều kiện hỗ trợ tối thiểu luôn được thỏa mãn. Do đó, lời gọi đệ quy giảm xuống một mức sâu hơn vào mạng tinh thể. Trở lại từ cuộc gọi đệ quy, chúng tôi tiếp tục với phân vùng tiếp theo cho d. Sau khi tất cả các phân vùng đã được xử lý, toàn bộ quá trình được lặp lại cho mỗi kích thước còn lại.
Hiệu suất BUC nhạy cảm với thứ tự của các kích thước và độ lệch trong dữ liệu. Tốt nhất, các dimensions phân biệt nhất nên được xử lý trước. Kích thước phải được xử lý theo thứ tự giảm dần số lượng. Cardinality càng cao, các phân vùng càng nhỏ, và do đó sẽ có nhiều phân vùng hơn, do đó cung cấp cho BUC cơ hội lớn hơn để cắt tỉa. Tương tự, kích thước càng đồng đều (tức là có ít độ lệch hơn), thì càng tốt cho việc cắt tỉa.
Đóng góp chính của BUC là ý tưởng chia sẻ chi phí phân vùng. Tuy nhiên, không giống như MultiWay, nó không chia sẻ việc tính toán tổng hợp giữa nhóm mẹ và nhóm con. Ví dụ, việc tính Cube AB không giúp ích được gì cho ABC. Sau này cần phải được tính toán cơ bản từ đầu.
Star-Cubing: Tính toán khối iceberg cube sử dụng cấu trúc cây sao động
Trong phần này, chúng tôi mô tả thuật toán Star-Cubing để tính toán các khối băng trôi. Star-Cubing kết hợp những điểm mạnh của các phương pháp khác mà chúng tôi đã nghiên cứu cho đến thời điểm này. Nó tích hợp tính toán khối từ trên xuống và từ dưới lên và khám phá cả tổng hợp đa chiều (tương tự như MultiWay) và cắt tỉa giống Apriori (mô phỏng với BUC). Nó hoạt động từ một cấu trúc dữ liệu được gọi là cây sao, thực hiện nén dữ liệu không mất dữ liệu, do đó giảm thời gian tính toán và yêu cầu bộ nhớ.
Thuật toán Star-Cubing khám phá cả mô hình tính toán từ dưới lên và từ trên xuống như sau: Theo thứ tự tính toán toàn cục, nó sử dụng mô hình từ dưới lên. Tuy nhiên, nó có một lớp con bên dưới dựa trên mô hình từ trên xuống, khám phá khái niệm về dimensions được chia sẻ, như chúng ta sẽ thấy trong phần sau. Việc tích hợp này cho phép thuật toán tổng hợp trên nhiều dimensions trong khi vẫn phân chia từng nhóm mẹ và cắt bỏ từng nhóm con không thỏa mãn điều kiện iceberg cube.
Cách tiếp cận của Star-Cubing được minh họa trong Hình 48 cho phép tính data cube 4-D. Nếu chúng ta chỉ theo dõi mô hình từ dưới lên (tương tự như MultiWay), thì các Cube được Star-Cubing đánh dấu là cắt tỉa sẽ vẫn được khám phá. Star-Cubing có thể cắt các hình khối được chỉ định vì nó xem xét các kích thước được chia sẻ. ACD / A có nghĩa là hình lập phương ACD có chung kích thước A, ABD / AB có nghĩa là hình lập phương ABD có chung kích thước AB, ABC / ABC có nghĩa là hình lập phương ABC có chung kích thước ABC, v.v. Điều này xuất phát từ sự khái quát rằng tất cả các hình lập phương trong cây con bắt nguồn từ ACD đều bao gồm kích thước A, tất cả những hình lập phương có gốc tại ABD bao gồm kích thước AB và tất cả những hình lập phương có gốc tại ABC đều bao gồm kích thước ABC (mặc dù chỉ có một hình lập phương như vậy). Chúng tôi gọi những dimensions chung này là dimensions dùng chung của những cây con cụ thể đó.
Sự ra đời của các dimensions dùng chung tạo điều kiện thuận lợi cho việc tính toán được chia sẻ. Vì kích thước chia sẻ được xác định sớm trong quá trình mở rộng cây, chúng ta có thể tránh đưa ra chúng sau này. Ví dụ, AB hình khối kéo dài từ ABD trong Hình 48 sẽ thực sự bị cắt bớt vì AB đã được tính trong ABD / AB.
Hình 48: Star-Cubing: tính toán từ dưới lên với sự mở rộng từ trên xuống của các dimensions được chia sẻ.
Phần mở rộng từ AD cũng sẽ bị cắt bớt vì nó đã được tính toán trong ACD/A.
Các kích thước được chia sẻ cho phép chúng ta thực hiện việc cắt tỉa giống như Apriori nếu số đo của một khối băng trôi, chẳng hạn như số đếm, là phản đơn âm. Nghĩa là, nếu giá trị tổng hợp trên một dimen được chia sẻ không thỏa mãn điều kiện iceberg cube, thì tất cả các ô giảm dần từ dimensions được chia sẻ này cũng không thể thỏa mãn điều kiện iceberg cube. Các ô này và con cháu của chúng có thể được cắt bớt vì theo định nghĩa, các ô con này chuyên biệt hơn (tức là chứa nhiều dimensions hơn) so với những tế bào trong (các) dimensions được chia sẻ. Số lượng bộ giá được bao phủ bởi các ô con sẽ nhỏ hơn hoặc bằng số bộ giá trị được bao phủ bởi các dimensions được chia sẻ. Do đó, nếu giá trị tổng hợp trên một dimensions được chia sẻ không đáp ứng được điều kiện iceberg cube, thì các ô con cháu cũng không thể đáp ứng điều kiện đó.
Tính toán trước Shell Fragments cho OLAP có chiều cao nhanh
Nhắc lại lý do mà chúng tôi quan tâm đến các data cube tính toán trước: Các data cube tạo điều kiện thuận lợi cho OLAP nhanh trong không gian dữ liệu đa chiều. Tuy nhiên, một data cube full có kích thước cao cần không gian lưu trữ lớn và thời gian tính toán không thực tế. Các khối iceberg cube cung cấp một giải pháp thay thế khả thi hơn, như chúng ta đã thấy, trong đó phép tính iceberg cube được sử dụng để chỉ định việc tính toán chỉ một tập hợp con của các ô đầy đủ của Cube. Tuy nhiên, mặc dù một iceberg cube nhỏ hơn và cần ít thời gian tính toán hơn so với khối đầy đủ tương ứng của nó, nó không phải là một giải pháp cuối cùng.
Đầu tiên, việc tính toán và bảo quản khối băng trôi vẫn có thể tốn kém. Đối với bài kiểm tra, nếu ô hình khối cơ sở, (a1, a2,.., A60), vượt qua ngưỡng hỗ trợ tối thiểu (hoặc ngưỡng iceberg cube), nó sẽ tạo ra 260 ô hình khối băng trôi. Thứ hai, rất khó để xác định một ngưỡng iceberg cube thích hợp. Đặt ngưỡng quá thấp sẽ dẫn đến một khối lớn, trong khi đặt ngưỡng quá cao có thể làm mất hiệu lực của nhiều ứng dụng hữu ích. Thứ ba, một khối iceberg cube không thể được cập nhật từng bước. Khi một ô tổng hợp giảm xuống dưới ngưỡng iceberg cube và bị cắt bỏ, giá trị đo lường của nó sẽ bị mất. Bất kỳ cập nhật gia tăng nào sẽ yêu cầu tính toán lại các ô từ đầu. Đây là điều cực kỳ không mong muốn đối với các ứng dụng lớn trong cuộc sống thực, nơi mà dữ liệu mới được bổ sung gia tăng là tiêu chuẩn.
Một giải pháp khả thi, đã được thực hiện trong một số hệ thống Data Warehouse thương mại, là tính toán một vỏ hình khối mỏng. Ví dụ: chúng ta có thể tính toán tất cả các hình khối có ba chiều hoặc nhỏ hơn trong một data cube 60 chiều, dẫn đến một khối hình lập phương có kích thước là 3. Tập hợp các Cube thu được sẽ yêu cầu ít tính toán hơn nhiều và tính toán tuổi hơn data cube 60 chiều đầy đủ. Tuy nhiên, có hai nhược điểm của cách tiếp cận này. Đầu tiên, chúng ta vẫn cần tính 60 + 60 + 60 = 36.050 Cube, mỗi ô có nhiều ô.
Thứ hai, vỏ hình khối như vậy không hỗ trợ OLAP chiều cao vì (1) nó không hỗ trợ OLAP trên bốn chiều trở lên và (2) nó thậm chí không thể hỗ trợ khoan dọc theo ba chiều, chẳng hạn như, chẳng hạn (A4, A5 , A6), trên một tập dữ liệu con được chọn dựa trên các hằng số được cung cấp trong ba chiều khác, chẳng hạn như (A1, A2, A3), vì điều này về cơ bản yêu cầu tính toán hình khối 6-D tương ứng. (Lưu ý rằng không có ô nào trong hình khối (A4, A5, A6) được tính cho bất kỳ tập hợp hằng số cụ thể nào, chẳng hạn như (a1, a2, a3), được liên kết với các kích thước (A1, A2, A3).)
Thay vì tính toán một vỏ Cube, chúng ta chỉ có thể tính toán các phần hoặc các đoạn của nó. Phần này thảo luận về cách tiếp cận phân mảnh vỏ để xử lý truy vấn OLAP. Nó dựa trên quan sát chính sau đây về OLAP trong không gian chiều cao. Mặc dù một data cube có thể chứa nhiều dimensions, nhưng hầu hết các hoạt động OLAP chỉ được thực hiện trên một số nhỏ dimensions tại một thời điểm. Nói cách khác, truy vấn OLAP có khả năng bỏ qua nhiều dimensions (tức là coi chúng là không liên quan), sửa một số dimensions (ví dụ: sử dụng hằng số truy vấn làm phần khởi tạo) và chỉ để lại một số dimensions được thao tác (để khoan, xoay, v.v. .). Điều này là do không thực tế cũng như không có kết quả đối với bất kỳ ai tuân theo sự thay đổi của hàng nghìn ô liên quan đến hàng chục chiều đồng thời trong một không gian chiều cao cùng một lúc.
Thay vào đó, sẽ tự nhiên hơn trước tiên là xác định vị trí một số Cube mà bạn quan tâm và sau đó đi sâu theo một hoặc hai chiều để xem xét sự thay đổi của một vài kích thước liên quan. Hầu hết các nhà phân tích sẽ chỉ cần kiểm tra, tại bất kỳ thời điểm nào, sự kết hợp của một số nhỏ dimensions. Điều này ngụ ý rằng nếu tổng hợp đa chiều có thể được tính toán nhanh chóng trên một số nhỏ kích thước bên trong không gian chiều cao, chúng ta vẫn có thể đạt được OLAP nhanh chóng mà không cần hiện thực hóa data cube chiều cao ban đầu. Việc tính toán toàn bộ Cube (hoặc thường xuyên, thậm chí cả khối iceberg cube hoặc vỏ khối) có thể là quá mức.
Thay vào đó, một mô hình tính toán bán trực tuyến với một số tiền xử lý nhất định có thể đưa ra một giải pháp khả thi hơn. Với một hình khối cơ sở, một số tính toán chuẩn bị nhanh có thể được thực hiện trước (tức là ngoại tuyến). Sau đó, một truy vấn có thể được tính toán trực tuyến bằng cách sử dụng dữ liệu được xử lý trước.
Cách tiếp cận phân mảnh vỏ tuân theo một chiến lược tính toán bán trực tuyến như vậy. Nó liên quan đến hai thuật toán: một để tính toán các mảnh vỡ hình khối và một để xử lý truy vấn với các mảnh hình lập phương. Phương pháp tiếp cận phân mảnh vỏ có thể xử lý cơ sở dữ liệu có kích thước cao và có thể nhanh chóng tính toán trực tuyến các khối cục bộ nhỏ. Nó khám phá cấu trúc dữ liệu chỉ mục ngược, cấu trúc phổ biến trong hệ thống thông tin dựa trên Web và truy xuất thông tin.
Ý tưởng cơ bản là như sau. Với một tập dữ liệu chiều cao, chúng tôi phân chia các kích thước thành một tập hợp các đoạn kích thước rời rạc, chuyển đổi từng đoạn thành biểu diễn chỉ số đảo ngược tương ứng của nó và sau đó tạo các đoạn vỏ hình khối trong khi vẫn giữ các chỉ số đảo ngược được liên kết với các ô hình khối. Bằng cách sử dụng các mảnh vỏ của Cube được đặt sẵn, chúng tôi có thể tự động lắp ráp và tính toán các ô hình khối của data cube được yêu cầu trực tuyến. Điều này được thực hiện hiệu quả bằng cách thiết lập các hoạt động giao cắt trên các chỉ số đảo ngược.
Đối với các tập dữ liệu lớn, kích thước phân mảnh là 2 hoặc 3 thường dẫn đến các yêu cầu lưu trữ hợp lý cho các phân mảnh vỏ và cho thời gian phản hồi truy vấn nhanh. Truy vấn với các đoạn shell nhanh hơn đáng kể so với việc trả lời các truy vấn bằng cách sử dụng các data cube được tính toán trước được lưu trữ trên đĩa. So với tính toán cube full, Frag-Shells được khuyến nghị nếu có ít hơn bốn kích thước được yêu cầu. Nếu không, các thuật toán hiệu quả hơn, chẳng hạn như Star-Cubing, có thể được sử dụng để tính toán Cube trực tuyến nhanh chóng.
