Chapter 3�Data Warehousing and Analytical Processing

1

Outline

• Data warehouse
• Data warehouse modeling: schema and measures
• OLAP operations
• Data cube computation
• Data cube computation methods

2

Outline

• Data warehouse
• Data warehouse: what and why?
• Architecture of data warehouses: enterprise data warehouses and data marts
• Data lakes
• Data warehouse modeling: schema and measures
• OLAP operations
• Data cube computation
• Data cube computation methods

3

What is a Data Warehouse?

• Defined in many different ways, but not rigorously
• A decision support database that is maintained separately from the organization’s operational database
• Support information processing by providing a solid platform of consolidated, historical data for analysis
• “A data warehouse is a subject-oriented, integrated, time-variant, and nonvolatile collection of data in support of management’s decision-making process.”—W. H. Inmon
• Data warehousing:
• The process of constructing and using data warehouses

4

Data Warehouse—Subject-Oriented

• Organized around major subjects, such as customer, product, sales
• Focusing on the modeling and analysis of data for decision makers, not on daily operations or transaction processing
• Provide a simple and concise view around particular subject issues by excluding data that are not useful in the decision support process

5

Data Warehouse—Integrated

• Constructed by integrating multiple, heterogeneous data sources
• relational databases, flat files, on-line transaction records
• Data cleaning and data integration techniques are applied.
• Ensure consistency in naming conventions, encoding structures, attribute measures, etc. among different data sources
• Ex. Hotel price: differences on currency, tax, breakfast covered, and parking
• When data is moved to the warehouse, it is converted

6

Data Warehouse—Time Variant

• The time horizon for the data warehouse is significantly longer than that of operational systems
• Operational database: current value data
• Data warehouse data: provide information from a historical perspective (e.g., past 5-10 years)
• Every key structure in the data warehouse
• Contains an element of time, explicitly or implicitly
• But the key of operational data may or may not contain “time element”

​

7

Data Warehouse—Nonvolatile

• Independence
• A physically separate store of data transformed from the operational environment
• Static: Operational update of data does not occur in the data warehouse environment
• Does not require transaction processing, recovery, and concurrency control mechanisms
• Requires only two operations in data accessing:
• initial loading of data and access of data

8

OLTP vs. OLAP

• OLTP: Online transactional processing
• DBMS operations
• Query and transactional processing
• OLAP: Online analytical processing
• Data warehouse operations
• Drilling, slicing, dicing, etc.

​

9

Why a Separate Data Warehouse?

• High performance for both systems
• DBMS— tuned for OLTP: access methods, indexing, concurrency control, recovery
• Warehouse—tuned for OLAP: complex OLAP queries, multidimensional view, consolidation
• Different functions and different data:
• missing data: Decision support requires historical data which operational DBs do not typically maintain
• data consolidation: DS requires consolidation (aggregation, summarization) of data from heterogeneous sources
• data quality: different sources typically use inconsistent data representations, codes and formats which have to be reconciled
• Note: There are more and more systems which perform OLAP analysis directly on relational databases

10

Data Warehouse: A Multi-Tiered Architecture

• Top Tier: Front-End Tools
• Middle Tier: OLAP Server
• Bottom Tier: Data Warehouse Server
• Data

11

Three Data Warehouse Models

• Enterprise warehouse
• Collects all of the information about subjects spanning the entire organization
• Data Mart
• A subset of corporate-wide data that is of value to a specific groups of users
• Its scope is confined to specific, selected groups, such as marketing data mart
• Independent vs. dependent (directly from warehouse) data mart
• Virtual warehouse
• A set of views over operational databases
• Only some of the possible summary views may be materialized

12

Extraction, Transformation, and Loading (ETL)

• Data extraction
• get data from multiple, heterogeneous, and external sources
• Data cleaning
• detect errors in the data and rectify them when possible
• Data transformation
• convert data from legacy or host format to warehouse format
• Load
• sort, summarize, consolidate, compute views, check integrity, and build indicies and partitions
• Refresh
• propagate the updates from the data sources to the warehouse

13

Metadata Repository

• Meta data is the data defining warehouse objects. It stores:
• Description of the structure of the data warehouse
• schema, view, dimensions, hierarchies, derived data defn, data mart locations and contents
• Operational meta-data
• data 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 summarization
• The mapping from operational environment to the data warehouse
• Data related to system performance
• warehouse schema, view and derived data definitions
• Business data
• business terms and definitions, ownership of data, charging policies

14

Data Lake

• A data lake is a centralized repository storing all structured and unstructured data at any scale in an organization
• Data is stored as is, without having to first structure the data, and run different types of analytics—from dashboards and visualizations to big data processing, real-time analytics, and machine learning to guide better decision

​

15

Layers of Storage

16

Conceptual Architecture

17

(Enterprise) Data Organization

18

Structured data

Unstructured data

Unstructured data with schema

Extraction

Parsing

Schema

Schema inference

Schema inference

Import

Analytics

Data lake

Data Lake Challenges

• Many data sets, hundreds of thousands and more
• Complicated queries: keyword queries, finding joinable data sets, finding features, …
• Core task in building data lake: meta data management

​

19

Data Cleaning in Data Lakes

• Data cleaning is the No. 1 most cited task in data lake
• Over 85% considered it either major or critical to the business

20

Evolving Data in Data Lakes

• Many duplicates as data sets are often being copied for new projects
• Data sets are constantly being updated, having their schema altered, being derived into new ones, and disappearing/reappearing
• Data set versioning is to maintain all versions of datasets for storage cost-saving, collaboration, auditing, and experimental reproducibility

​

21

Diversity in Data Lakes

• Dataset formats in the open world can be highly heterogeneous
• Ingestion and extraction is the task of bringing structured datasets into data lake
• Ingest already-structured data sets
• Extract structured data from unstructured and semi-structured data sources
• Data Integration is the task of finding joinable or union-able tables or of on-demand population a schema with all data from the lake that conforms to the schema
• Example: enrich Electronic Health Records (EPR) using data from various non-standard personal health record data sets for better predicting health risks
• Joining or “union-ing” tables from different data sets and sources

​

22

Common Tasks in Building Data Lakes

• Ingestion
• Extraction (Type Inference)
• Metadata Management
• Cleaning
• Integration
• Discovery
• Versioning

​

23

Metadata Management in Data Lakes: Ideas

• Enrich data and meta data with semantic information, support template-based queries on metadata
• Extract deeply embedded metadata and contextual metadata to support topic-based discovery
• Integrate metadata about data, users, and queries, and support visual analytics

​

24

Two Purposes and Ecosystems

• Analytic use cases: decision support based on data
• Data warehouses
• Structured data, SQL/Python
• Operational use cases: data intelligence in applications
• Data lakes
• Raw data, Java/Scala, Python, R, and SQL
• Potential convergence of data warehouses and data lakes

​

25

Data Lakehouses

• “A data lakehouse is a new, open data management architecture that combines the flexibility, cost-efficiency, and scale of data lakes with the data management and ACID transactions of data warehouses, enabling business intelligence (BI) and machine learning (ML) on all data.” (Databricks)

26

Lakehouses

• Transaction support
• Schema enforcement and governance
• BI support
• Decoupling between storage and compute
• Open storage formats
• Support for diverse data types, ranging from unstructured to structured
• Support for diverse workloads: data science, machine learning, SQL and analytics
• End-to-end streaming: real-time reports

​

​

27

Data Fabric and Data Virtualization

• “Data fabric is an architecture that facilitates the end-to-end integration of various data pipelines and cloud environments through the use of intelligent and automated systems” (IBM)
• A holistic and unified data architecture that enables organizations to manage data across their entire ecosystem, regardless of the source, format, location, or technology
• A data fabric provides a single point of access to all data, while abstracting away the underlying complexity and heterogeneity of the data landscape

28

Data Mesh

• A data mesh creates multiple domain-specific systems, each specialized according to its functions and uses, thus bringing data closer to consumers
• Data Mesh is a specific architecture pattern focused on data management

29

Data Virtualization

• “Data virtualization is one of the technologies that enables a data fabric approach. Rather than physically moving the data from various on-premises and cloud sources using the standard ETL (extract, transform, load) processes, a data virtualization tool connects to the different sources, integrating only the metadata required and creating a virtual data layer”
• Data Virtualization can be a component or a layer in a data fabric architecture

30

Outline

• Data warehouse
• Data warehouse modeling: schema and measures
• Data cube: a multidimensional data model
• Schemas for multidimensional data models: stars, snowflakes, and fact constellations
• Concept hierarchies
• Measures: categorization and computation
• OLAP operations
• Data cube computation
• Data cube computation methods

31

From Tables and Spreadsheets to Data Cubes

• A data warehouse is based on a multidimensional data model which views data in the form of a data cube
• A data cube, such as sales, allows data to be modeled and viewed in multiple dimensions
• Dimension tables, such as item (item_name, brand, type), or time(day, week, month, quarter, year)
• Fact table contains measures (such as dollars_sold) and keys to each of the related dimension tables
• Data cube: A lattice of cuboids
• In data warehousing literature, an n-D base cube is called a base cuboid
• The top most 0-D cuboid, which holds the highest-level of summarization, is called the apex cuboid
• The lattice of cuboids forms a data cube.

32

Data Cube: A Lattice of Cuboids

33

time,item

time,item,location

time, item, location, supplier

Conceptual Modeling of Data Warehouses

• Modeling data warehouses: dimensions & measures
• Star schema: A fact table in the middle connected to a set of dimension tables
• Snowflake schema: A refinement of star schema where some dimensional hierarchy is normalized into a set of smaller dimension tables, forming a shape similar to snowflake
• Fact constellations: Multiple fact tables share dimension tables, viewed as a collection of stars, therefore called galaxy schema or fact constellation

34

Star Schema: An Example

35

Sales Fact Table

time_key

item_key

branch_key

location_key

units_sold

dollars_sold

avg_sales

Measures

Snowflake Schema: An Example

36

Sales Fact Table

time_key

item_key

branch_key

location_key

units_sold

dollars_sold

avg_sales

Measures

Fact Constellation: An Example

37

Sales Fact Table

time_key

item_key

branch_key

location_key

units_sold

dollars_sold

avg_sales

Measures

Shipping Fact Table

time_key

item_key

shipper_key

from_location

to_location

dollars_cost

units_shipped

A Concept Hierarchy for a Dimension (location)

38

all

Europe

North_America

Mexico

Canada

Spain

Germany

Vancouver

M. Wind

L. Chan

...

...

...

...

...

...

all

region

office

country

Toronto

Frankfurt

city

Data Cube Measures: Three Categories

• Distributive: if the result derived by applying the function to n aggregate values is the same as that derived by applying the function on all the data without partitioning
• E.g., count(), sum(), min(), max()
• Algebraic: if it can be computed by an algebraic function with M arguments (where M is a bounded integer), each of which is obtained by applying a distributive aggregate function
• avg(x) = sum(x) / count(x)
• Is min_N() an algebraic measure? How about standard_deviation()?
• Holistic: if there is no constant bound on the storage size needed to describe a subaggregate.
• E.g., median(), mode(), rank()

39

Multidimensional Data

• Sales volume as a function of product, month, and region

40

Dimensions: Product, Location, Time

Hierarchical summarization paths

A Sample Data Cube

41

Total annual sales

of TVs in U.S.A.

Cuboids Corresponding to the Cube

42

all

product

date

country

product,date

product,country

date, country

product, date, country

0-D (apex) cuboid

1-D cuboids

2-D cuboids

3-D (base) cuboid

Outline

• Data warehouse
• Data warehouse modeling: schema and measures
• OLAP operations
• Typical OLAP operations
• Indexing OLAP data: bitmap index and join index
• Storage implementation: column-based databases
• Data cube computation
• Data cube computation methods

43

Online Analytic Processing (OLAP)

• Conceptually, we may explore all possible subspaces for interesting patterns
• Some fundamental problems in analytics and data mining
• What patterns are interesting?
• How can we explore all possible subspaces systematically and efficiently?
• Aggregates and group-bys are frequently used in data analysis and summarization
• SELECT time, altitude, AVG(temp)
• FROM weather GOUP BY time, altitude;
• In TPC, 6 standard benchmarks have 83 queries, aggregates are used 59 times, group-bys are used 20 times
• Online analytical processing (OLAP): the techniques that answer multi-dimensional analytical (MDA) queries efficiently

44

OLAP Operations

• Roll up (drill-up): summarize data by climbing up hierarchy or by dimension reduction
• (Day, Store, Product type, SUM(sales) 🡪 (Month, City, *, SUM(sales))
• Drill down (roll down): reverse of roll-up, from higher level summary to lower level summary or detailed data, or introducing new dimensions

​

45

http://www.tutorialspoint.com/dwh/images/rollup.jpg

Other Operations

• Dice: pick specific values or ranges on some dimensions
• Pivot: “rotate” a cube – changing the order of dimensions in visual analysis

​

46

http://en.wikipedia.org/wiki/File:OLAP_pivoting.png

http://www.tutorialspoint.com/dwh/images/dice.jpg

47

Typical OLAP Operations

OLAP Query Example

• In a table about medicine trials (age, gender, …, succeed, …), find the total number of succeeding trials
• Method 1: scan the table once
• Method 2: build a B+ tree index on attribute succeed, still need to access all records of succeeding trails
• Can we get the count without scanning many records, even not all records of succeeding trails?

​

48

Bitmap Index

• For n records, a bitmap index has n bits and can be packed into ⎡n /8⎤ bytes and ⎡n /32⎤ words
• From a bit to the row-id: the j-th bit of the p-th byte 🡪 row-id = p*8 +j
• Counting using bitmap index
• Shcount[] contains the number of bits in the entry subscript
• Example: shcount[01100101]=4
• count = 0;
• for (i = 0; i < SHNUM; i++)
• count += shcount[B[i]];

​

49

Indexing OLAP Data Using Bitmap Indices

50

Advantages of Bitmap Index

• Efficient in space
• Ready for logic composition
• C = C1 AND C2
• Bitmap operations can be used
• Bitmap index only works for categorical data with low cardinality
• Naively, we need 50 bits per entry to represent the state of a customer in US
• How to represent a sale in dollars?

​

51

Bit-Sliced Index

• A sale amount can be written as an integer number of pennies, and then be represented as a binary number of N bits
• 32 bits is good for up to $42,949,672.95, appropriate for many stores
• A bit-sliced index is N bitmaps
• Tuple j sets in bitmap k if the k-th bit in its binary representation is on
• The space costs of bit-sliced index is the same as storing the data directly
• SELECT SUM(sales) FROM Sales WHERE C;
• Tuples satisfying C is identified by a bitmap B
• Direct access to rows to calculate SUM: scan the whole table once
• B+ tree: find the tuples from the tree
• Projection index: only scan attribute sales
• Bit-sliced index: get the sum from ∑(B AND Bk)*2k

​

52

Indexing OLAP Data Using Bit-sliced Indices

53

Indexing OLAP Data: Join Indices

• Join index: JI(R-id, S-id) where R (R-id, …)  S (S-id, …)
• Traditional indices map the values to a list of record ids
• It materializes relational join in JI file and speeds up relational join
• In 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 product
• A 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 dimensions

54

Join Index Example

55

Horizontal versus Vertical Storage

• A fact table for data warehousing is often fat
• Tens of even hundreds of dimensions/attributes
• A query is often about only a few attributes
• Horizontal storage: tuples are stored one by one
• Vertical storage: tuples are stored by attributes

​

56

Column-based Storage

57

Query Answering Using Vertical Storage

• Find the information of tuple t
• Typical in OLTP
• Horizontal storage: get the whole tuple in one search
• Vertical storage: search 100 lists
• Find SUM(a₁₀₀) GROUP BY {a₂₂, a₈₃}
• Typical in OLAP
• Horizontal storage (no index): search all tuples O(100n), where n is the number of tuples
• Vertical storage: search 3 lists O(3n), 3% of the horizontal storage method
• Projection index: vertical storage

​

58

Outline

• Data warehouse
• Data warehouse modeling: schema and measures
• OLAP operations
• Data cube computation
• Terminology of data cube computation
• Data cube materialization: ideas
• OLAP server architectures: ROLAP vs. MOLAP vs. HOLAP
• General strategies for data cube computation
• Data cube computation methods

59

Data Cube: A Lattice of Cuboids

60

Data Cube: A Lattice of Cuboids

• Base vs. aggregate cells
• Ancestor vs. descendant cells
• Parent vs. child cells

​

• (*,*,*)
• (*, milk, *, *)
• (*, milk, Urbana, *)
• (*, milk, Chicago, *)
• (9/15, milk, Urbana, *)
• (9/15, milk, Urbana, Dairy_land)

61

OLAP Server Architectures

• Relational OLAP (ROLAP)
• Use relational or extended-relational DBMS to store and manage warehouse data and OLAP middle ware
• Include optimization of DBMS backend, implementation of aggregation navigation logic, and additional tools and services
• Greater scalability
• Multidimensional OLAP (MOLAP)
• Sparse array-based multidimensional storage engine
• Fast indexing to pre-computed summarized data
• Hybrid OLAP (HOLAP) (e.g., Microsoft SQLServer)
• Flexibility, e.g., low level: relational, high-level: array
• Specialized SQL servers (e.g., Redbricks)
• Specialized support for SQL queries over star/snowflake schemas

62

Cube Materialization: Full Cube vs. Iceberg Cube

• Full cube vs. iceberg cube

compute cube sales iceberg as

select month, city, customer group, count(*)

from salesInfo

cube by month, city, customer group

having count(*) >= min support

• Compute only the cells whose measure satisfies the iceberg condition
• Only a small portion of cells may be “above the water’’ in a sparse cube
• Ex.: Show only those cells whose count is no less than 100

​

63

iceberg condition

Why Iceberg Cube?

• Advantages of computing iceberg cubes
• No need to save nor show those cells whose value is below the threshold (iceberg condition)
• Efficient methods may even avoid computing the un-needed, intermediate cells
• Avoid explosive growth
• Example: a cube with 100 dimensions
• Suppose it contains only 2 base cells: {(a₁, a₂, a₃, …., a₁₀₀), (a₁, a₂, b₃, …, b₁₀₀)}
• How many aggregate cells if “having count >= 1”? Answer: (2¹⁰¹ ─ 2) ─ 4 (Why?!)
• What about the iceberg cells, (i,e., with condition: “having count >= 2”)? Answer: 4 (Why?!)

64

Is Iceberg Cube Good Enough? Closed Cube & Cube Shell

• Let cube P have only 2 base cells: {(a1, a2, a3 . . . , a100):10, (a1, a2, b3, . . . , b100):10}
• How many cells will the iceberg cube contain if “having count(*) ≥ 10”? Answer: 2101 ─ 4 (still too big!)
• Close cube:
• A cell c is closed if there exists no cell d, such that d is a descendant of c, and d has the same measure value as c
• Ex. The same cube P has only 3 closed cells: {(a1, a2, *, …, *): 20, (a1, a2, a3 . . . , a100): 10, (a1, a2, b3, . . . , b100): 10}
• A closed cube is a cube consisting of only closed cells
• Cube Shell: The cuboids involving only a small # of dimensions, e.g., 2
• Idea: Only compute cube shells, other dimension combinations can be computed on the fly

65

Q: For (A₁, A₂, … A₁₀₀), how many combinations to compute?

Roadmap for Efficient Computation

• General computation heuristics (Agarwal et al.’96)
• Computing full/iceberg cubes: 3 methodologies
• Bottom-Up: Multi-Way array aggregation (Zhao, Deshpande & Naughton, SIGMOD’97)
• Top-down: BUC (Beyer & Ramarkrishnan, SIGMOD’99)
• Integrating Top-Down and Bottom-Up: Star-cubing algorithm (Xin, Han, Li & Wah: VLDB’03)
• High-dimensional OLAP:
• A Shell-Fragment Approach (Li, et al. VLDB’04)
• Computing alternative kinds of cubes:
• Partial cube, closed cube, approximate cube, ……

66

Efficient Data Cube Computation: General Heuristics

• Aggregates may be computed from previously computed aggregates, rather than from the base fact table
• Smallest-child: computing a cuboid from the smallest, previously computed cuboid
• Cache-results: caching results of a cuboid from which other cuboids are computed to reduce disk I/Os
• Amortize-scans: computing as many as possible cuboids at the same time to amortize disk reads
• Share-sorts: sharing sorting costs cross multiple cuboids when sort-based method is used
• Share-partitions: sharing the partitioning cost across multiple cuboids when hash-based algorithms are used
• Sorting, hashing, and grouping operations are applied to the dimension attributes in order to reorder and cluster related tuples

67

Example: General Heuristics

68

S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan, S. Sarawagi. On the computation of multidimensional aggregates. VLDB’96

Outline

• Data warehouse
• Data warehouse modeling: schema and measures
• OLAP operations
• Data cube computation
• Data cube computation methods
• Multiway array aggregation for full cube computation
• BUC: computing iceberg cubes from the apex cuboid downward
• Precomputing shell fragments for fast high-dimensional OLAP
• Efficient processing of OLAP queries using cuboids

69

Multi-Way Array Aggregation

• Array-based “bottom-up” algorithm (from ABC to AB,…)
• Using multi-dimensional chunks
• Simultaneous aggregation on multiple dimensions
• Intermediate aggregate values are re-used for computing ancestor cuboids
• Cannot do Apriori pruning: No iceberg optimization
• Pros and cons
• Efficient for computing the full cube for a small number of dimensions
• If there are a large number of dimensions, “top-down” computation and iceberg cube computation methods (e.g., BUC) should be used

​

70

Cube Computation: Multi-Way Array Aggregation (MOLAP)

• Partition arrays into chunks (a small subcube which fits in memory).
• Compressed sparse array addressing: (chunk_id, offset)
• Compute aggregates in “multiway” by visiting cube cells in the order which minimizes the # of times to visit each cell, and reduces memory access and storage cost

71

What is the best traversing order to do multi-way aggregation?

Multi-way Array Aggregation (3-D to 2-D)

• Keep the smallest plane in main memory, fetch and compute only one chunk at a time for the largest plane
• The planes should be sorted and computed according to their size in ascending order

72

• How to minimizes the memory requirement and reduced I/Os?

Entire AB plane

One column of AC plane

One chunk of BC plane

4x4x4 chunks

A: 40, B: 400, C: 4000

Multi-Way Array Aggregation (2-D to 1-D)

73

Same methodology for computing 2-D and 1-D planes

Cube Computation: Computing in Reverse Order

• BUC (Beyer & Ramakrishnan, SIGMOD’99)
• BUC: acronym of Bottom-Up (cube) Computation
• (Note: It is “top-down” in our view since we put Apex cuboid on the top!)
• Divides dimensions into partitions and facilitates iceberg pruning
• If a partition does not satisfy min_sup, its descendants can be pruned
• If minsup = 1 Þ compute full CUBE!
• No simultaneous aggregation

​

74

BUC: Partitioning and Aggregating

• Usually, entire data set cannot fit in main memory
• Sort distinct values
• partition into blocks that fit
• Continue processing
• Optimizations
• Partitioning
• External Sorting, Hashing, Counting Sort
• Ordering dimensions to encourage pruning
• Cardinality, Skew, Correlation
• Collapsing duplicates
• Cannot do holistic aggregates anymore!

75

High-Dimensional OLAP?—The Curse of Dimensionality

• High-D OLAP: Needed in many applications
• Science and engineering analysis
• Bio-data analysis: thousands of genes
• Statistical surveys: hundreds of variables
• A curse of dimensionality: A database of 600k tuples. Each dimension has cardinality of 100 and zipf of 2
• None of the previous cubing method can handle high dimensionality!
• Iceberg cube and compressed cubes: only delay the inevitable explosion
• Full materialization: still significant overhead in accessing results on disk
• A shell-fragment approach: X. Li, J. Han, and H. Gonzalez, High-Dimensional OLAP: A Minimal Cubing Approach, VLDB'04

76

Fast High-D OLAP with Minimal Cubing

• Observation: OLAP occurs only on a small subset of dimensions at a time
• Semi-Online Computational Model
• Partition the set of dimensions into shell fragments
• Compute data cubes for each shell fragment while retaining inverted indices or value-list indices
• Given the pre-computed fragment cubes, dynamically compute cube cells of the high-dimensional data cube online
• Major idea: Tradeoff between the amount of pre-computation and the speed of online computation
• Reducing computing high-dimensional cube into precomputing a set of lower dimensional cubes
• Online re-construction of original high-dimensional space
• Lossless reduction

77

Computing a 5-D Cube with 2-Shell Fragments

• Example: Let the cube aggregation function be count

​

​

​

​

​

​

​

• Divide the 5-D table into 2 shell fragments:
• (A, B, C) and (D, E)
• Build traditional invert index or RID list

78

Shell Fragment Cubes: Ideas

• Generalize the 1-D inverted indices to multi-dimensional ones in the data cube sense
• Compute all cuboids for data cubes ABC and DE while retaining the inverted indices
• Ex. shell fragment cube ABC contains 7 cuboids:
• A, B, C; AB, AC, BC; ABC
• This completes the offline computation

79

Shell Fragment Cubes: Example of Ideas

• ID_Measure Table
• If measures other than count are present, store in ID_measure table separate from the shell fragments

​

80

Shell-fragment AB

Shell Fragment Cubes: Size and Design

81

Use Frag-Shells for Online OLAP Query Computation

82

ABC Cube

DEF Cube

D Cuboid

EF Cuboid

DE Cuboid

Dimensions

Processing query in the form: <a₁, a₂, …, a_n: M>

Online Query Computation with Shell-Fragments

• A query has the general form: <a1, a2, …, an: M>
• Each ai has 3 possible values (e.g., <3, ?, ?, *, 1: count> returns a 2-D data cube)
• Instantiated value
• Aggregate * function
• Inquire ? Function
• Method: Given the materialized fragment cubes, process a query as follows
• Divide the query into fragments, same as the shell-fragment
• Fetch the corresponding TID list for each fragment from the fragment cube
• Intersect the TID lists from each fragment to construct instantiated base table
• Compute the data cube using the base table with any cubing algorithm

83