CS145 Lecture Notes -- Data Warehousing and Data Mining

OLTP: On-Line Transaction Processing

• Short transactions, both queries and updates (e.g., update account balance, enroll in course)
• Queries are simple (e.g., find account balance, find grade in course)
• Queries and updates touch small portion of data (e.g., examples above)
• Updates are frequent (e.g., movie tickets, seat reservations, shopping carts)

• Long transactions, usually complex queries (e.g., all statistics about all sales, grouped by dept and month)
• Queries touch large portion of the data (e.g., as above)
• "Data mining" operations
• Infrequent updates

Data Warehousing

(system figure)

=> Extremely popular in large corporations today. Many have spent millions in data warehousing projects.

Example: Wal-Mart

• All distributor, store, and sales information copied into warehouse. Used to make store layout and supplier decisions. Hundreds of terabytes of data.

Example: Victoria's Secret

• All sales information copied into warehouse. Used to supply appropriate merchandise (current and future) to appropriate outlets. Warehouse project paid off in 1-2 years.

1. Extracting data from operational sources in useful format
   (add to figure)

2. Transforming, "cleaning" ("scrubbing"), and possibly summarizing operational data
   (add to figure)

3. Integrating data from multiple sources
   (add to figure)

4. Keeping warehouse up-to-date as source data changes

Data at Warehouse

• Fact data: sales transactions, flight arrivals, course enrollments
  Updated frequently, often append-only, very large

• Dimension data: store items, store customers, students, courses
  Updated infrequently, not as large

Star Schema

  Sales(StoreID, ItemID, CustID, qty, price)  // fact table
  Store(StoreID, city, state)
  Item(ItemID, name, brand, color, size)
  Customer(CustID, name, address)

• Dimension attributes: foreign keys to dimension tables

• Dependent attributes: all others, often aggregated in queries

  SELECT *
  FROM   Sales, Store, Item, Customer
  WHERE  Sales.StoreID = Store.StoreID
  AND    Sales.ItemID = Item.ItemID
  AND    Sales.CustID = Customer.CustID

1. Do all or part of star join
2. Filter interesting tuples based on fact and/or dimension data
3. Group by one or more dimensions
4. Aggregate the result

• OLAP queries can be extremely slow
• New kinds of indexes
• New query processing techniques
• Systems make extensive use of materialized views

Question: Why are materialized views appropriate in this setting?

Data Cubes

• Dimension data forms axes of "cube"
• Fact data in cells
• Aggregated data on sides, edges, and corners

(diagram)

• If dimension attributes are not a key, cells must aggregate (e.g., sum of qty*price)
• "Date" often used to create a key: Sales(StoreID,ItemID,CustID,date,qty,price)

Question: Is date a dimension or dependent attribute?

Queries can "slice and dice", "drill down and roll up"

• Slice: Select on one or more dimensions
  (e.g., only store S2, only stores in California)

• Dice: Partition or group on one or more dimensions
  (e.g., stores by state, items by color)

• Drill down ("de-aggregate"): Examining summary data, break it out by dimension attribute
  Example: Looking at sum of all California sales, break it out by store

• Roll up ("aggregate"): Examining data, summarize along some dimension
  Example: Looking at data grouped by item and customer, aggregate so only grouped by customer

• Data cube can be huge
• Also can be sparse
• Can compute in advance, compute on demand, or some combination

Relational representation of cube

Example:

• (store123, *, cust456, $1000)
  $1000 is sum of price for all items bought by Customer cust456 at store store123
  Face of cube

• (*, item789, *, $10,000)
  $10,000 is sum of price for item item789 bought by any customer at any store
  Edge of cube

• (*, *, *, $1,000,000)
  $1,000,000 is sum of price in entire database
  Corner of cube

• CUBE() enables efficient data cube operations built easily on top of conventional relational DBMS.

• Can write the same queries without CUBE(), "smart" OLAP system would figure out how to use it.

Data Mining

• Often performed over data warehouses
• Both less structured and less ad-hoc than OLAP queries

  Purchase(salesID, item)
  ...
  (3, bread)
  (3, milk)
  (3, eggs)
  (3, beer)
  (4, beer)
  (4, chips)
  ....

  {L1,L2,...,Ln} -> R

Example:

  {bread, milk} -> eggs
  {diapers}     -> beer

Question: Can we write a SQL query to find association rules?

Question: What can we write it in?

• Support: {L1,L2,...,Ln} must appear frequently
  Support = #sales containing {L1,L2,...,Ln} / total #sales

• Confidence: probability that R appears if {L1,L2,...,Ln} does
  Confidence = #sales containing {L1,L2,...,Ln,R} / #sales containing {L1,L2,...,Ln}

• Quickly find association rules over extremely large data sets
  (e.g., all Wal-Mart sales for a year).

• Allow user to tune support and confidence.

• Classification trees (= decision trees)
  Buyers(<attributes>, purchase)
  Want to predict purchase from <attributes>

• Clustering
  Buyers(<attributes>)
  Automatically group buyers into N similar types

• Top-N items
  Purchase(salesID, item)
  What were the N most often purchased items? (salesID irrelevant)
  Question: Can we write it in SQL?