Data analysis and data mining: OLAP, star schema, association rules

The last topic of the semester is seeing the database not as a “system that keeps records” but as a “system that helps make decisions”. It has two parts. The first is the data warehouse and OLAP: summarizing large data along different dimensions. The second is data mining: finding patterns in data that a human eye could not find. In the final exam this topic usually brings concept questions and small calculations: compute support and confidence, how many rows ROLLUP produces, what the entropy is, one iteration of k-means. What you need to know:

1. OLTP does the daily work, OLAP does the analysis. That is why their designs differ.
2. Star schema: a fact table in the middle, dimension tables around it.
3. ROLLUP produces $n+1$ and CUBE produces $2^n$ grouping sets.
4. Confidence is not symmetric. Lift tells how much better the rule is than independence.
5. Classification has labels, clustering does not.

OLTP, OLAP and the data warehouse

The university database we have built so far was an OLTP (online transaction processing) system. A student registers for a course, a grade is entered, credits are updated. Each transaction touches a few rows, hundreds happen per second, and normalized tables (weeks 9-11) prevent update anomalies.

The question of the rector’s office is different: “How has each department’s average performance changed each semester over the last five years?” This is an OLAP (online analytical processing) query. It reads millions of rows, groups and sums them. It updates nothing.

A data warehouse is a store where data from different sources is collected in a single schema, over a long period, in a form suitable for analysis. Data is moved from the sources to the warehouse with ETL: extract, transform (bring units, codes and names to a single form, clean dirty data), load. The warehouse is usually updated in nightly batches.

Star schema

As an example, let us analyze the sales of campus cafeterias. The measures of a sale event are quantity and amount. The context that describes this event is the dimensions: which item, which cafeteria, which month.

              dim_item(item_id, item_name, category)
                          |
 dim_date(date_id, month) -- fact_sales(date_id, store_id, item_id, qty, amount) -- dim_store(store_id, campus)

(The lines in the middle are foreign key links.) Dimension tables: dim_item = {1 Tost Food, 2 Simit Food, 3 Cay Drink, 4 Kahve Drink}, dim_store = {K1 Galata, K2 Rumeli}, dim_date = {1 Sep, 2 Oct}. The fact table:

In a star schema, each dimension is a single table and is not normalized: the category name repeats inside dim_item. In a snowflake schema, dimensions are normalized too; for example, the category moves into a separate dim_category table. A snowflake saves space, but adds extra joins to queries.

PITFALL · the fact table is not small. Students often write “dimension tables are large, the fact table is small”. The opposite is true. Every sale is a fact row, and they reach millions. The number of products or stores, on the other hand, is limited.

Data cube and OLAP operations

If you think of three dimensions (item category, campus, month) as axes, the sales settle in the cells of a cube. This is called a data cube. Each cell is the total for one combination. When you add an “all” (ALL) value to each dimension, three dimensions with two values each give $(2+1)^3 = 27$ cells.

Pivot result (amount):

A pivot is written in SQL with CASE: SUM(CASE WHEN month = 'Sep' THEN amount END) AS Sep.

ROLLUP, CUBE and GROUPING SETS

In standard SQL (after SQL:1999) there are GROUP BY extensions to get several grouping levels in one query:

SELECT campus, category, SUM(amount) AS total
FROM fact_sales f JOIN dim_item i USING (item_id) JOIN dim_store s USING (store_id)
GROUP BY ROLLUP (campus, category);

ROLLUP(campus, category) is the union of these three grouping sets: (campus, category), (campus), (). The aggregated column appears as NULL in the result:

CUBE(campus, category) is all four sets: (category) is added to those of ROLLUP, and two more rows come: (NULL, Drink, 2400) and (NULL, Food, 2400). A total of 9 rows. General rule: for $n$ attributes, ROLLUP produces $n+1$ and CUBE produces $2^n$ sets. With a form like GROUPING SETS ((campus), (category)) you can also choose the sets you want by hand.

SQLite does not support these extensions. If you write GROUP BY ROLLUP(campus), you get the error “no such function: ROLLUP”. We produce the same result with UNION ALL:

SELECT campus, category, SUM(amount) FROM ... GROUP BY campus, category
UNION ALL
SELECT campus, NULL, SUM(amount) FROM ... GROUP BY campus
UNION ALL
SELECT NULL, NULL, SUM(amount) FROM ...;

PITFALL · NULL can mean two things. The NULL in a ROLLUP row means “aggregated over this column”. But if there is a real NULL category in the data, the two get mixed. Standard SQL provides the GROUPING(category) function for this: it returns 1 in a total row and 0 in a normal row.

Data mining: association rules

Data mining is the automatic discovery of useful and unexpected patterns in large data. The main tasks are association rules, classification, clustering, regression and outlier detection.

An association rule has the form “whoever buys X also buys Y”: $X \Rightarrow Y$. 8 receipts from the cafeteria:

Three measures:

$supp(X) = \frac{\text{number of transactions containing }X}{N} \qquad conf(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)} \qquad lift(X \Rightarrow Y) = \frac{conf(X \Rightarrow Y)}{supp(Y)}$

Support is symmetric, confidence is not. Lift is symmetric again: $lift = \frac{supp(X \cup Y)}{supp(X)\,supp(Y)}$. If lift > 1, X increases the probability of Y. If lift < 1, it decreases it: a customer who buys tost buys less cay than average.

Apriori

Counting all item combinations is exponentially expensive. Apriori is based on this principle: every subset of a frequent set is also frequent. Conversely: a candidate with an infrequent subset is dropped without needing to be counted. With a minimum support count of 2:

C1 counts : cay 5, kahve 3, simit 4, su 2, tost 4          → L1 = all
C2 counts : cay+kahve 0, cay+simit 4, cay+su 1, cay+tost 2, kahve+simit 0,
            kahve+su 1, kahve+tost 2, simit+su 1, simit+tost 1, su+tost 0
L2        : {cay,simit}:4, {cay,tost}:2, {kahve,tost}:2
C3 candidate: {cay,simit,tost} → {simit,tost} infrequent, PRUNED
              {cay,kahve,tost} → {cay,kahve} infrequent, PRUNED
C3 empty  → stop

Rules are generated from frequent sets and filtered with a minimum confidence threshold. For example, with a threshold of 0.75, from the set {cay, simit} both cay ⇒ simit (0.8) and simit ⇒ cay (1.0) pass.

Classification and decision trees

Classification is learning a model from training data with known labels (supervised learning) and predicting the class of a new record: “Will this student pass the course?” A decision tree splits the data at each node on an attribute. Which attribute to choose is decided with entropy:

$H(S) = -\sum_i p_i \log_2 p_i \qquad Gain(S, A) = H(S) - \sum_v \frac{|S_v|}{|S|} H(S_v)$

In a training set of 10 students, 5 passed and 5 failed: $H = 1$ (the most mixed case). Of the 5 with attendance ‘yes’, 4 passed, and of the 5 with ‘no’, 1 passed. The entropy of each branch is $-0.8\log_2 0.8 - 0.2\log_2 0.2 = 0.722$, and the gain is $1 - 0.722 = 0.278$. In this data the study time (high/low) gives the same 4-to-1 and 1-to-4 distribution, so its gain is also 0.278. In a tie, either can be chosen. For another comparison: the entropy of a node with 3 passed and 1 failed is 0.811, and that of 2 to 2 is 1. A pure (single-class) node has entropy 0, and the tree makes a leaf there.

Clustering and k-means

Clustering groups similar records without labels (unsupervised). The best-known algorithm is k-means:

1. Choose k centroids.
2. Assign each point to the nearest centroid.
3. Move each centroid to the mean of its own cluster.
4. Repeat 2 and 3 until the assignments stop changing.

Points A(1,2), B(2,1), C(2,3), D(8,8), E(9,7), F(7,9), k = 2, initial centroids c1 = (1,2), c2 = (2,3):

iter 1: A→c1 (d²: 0 / 2)   B→c1 (2 / 4)   C→c2 (2 / 0)   D,E,F→c2
        c1 = (1.5, 1.5)    c2 = ((2+8+9+7)/4, (3+8+7+9)/4) = (6.5, 6.75)
iter 2: d² for C: 2.5 to c1, 34.3125 to c2 → C moves to c1
        c1 = (1.67, 2)     c2 = (8, 8)
iter 3: no assignment changed → stop.  SSE = 2.667 + 4 = 6.667

The k-means result depends on the initial centroids. A bad start can take longer or get stuck in a bad local minimum. In practice the algorithm is run several times with different starts, and the result with the smallest SSE is chosen.

Common mistakes