Data Warehousing and Mining

Data Warehouse Definition (W.H. Inmon):

A Data Warehouse is a subject-oriented, integrated, time-variant, and non-volatile collection of data in support of management’s decision-making process.

1. Subject-Oriented: Organized around high-level business entities (e.g. customers, sales, loans) rather than operational transactions.
2. Integrated: Consolidates heterogeneous operational data sources into unified data formats, codes, and naming conventions.
3. Time-Variant: Every record explicitly carries a timestamp, maintaining multi-year historical trend data.
4. Non-Volatile: Historical records are read-only; they are never updated or deleted in place, preserving auditability.

OLTP vs. OLAP:

Data Marts:

A specialized, departmental subset of an enterprise data warehouse focused on a single business function (e.g. Marketing, Finance).

• Dependent Data Mart: Sourced directly from a centralized enterprise data warehouse (EDW), guaranteeing corporate data consistency and single source of truth.
• Independent Data Mart: Built directly from operational source systems without an EDW. Cheaper and faster to build initially, but leads to inconsistent, redundant departmental data silos.

Support & Confidence in Association Rules ($X \implies Y$):

1. Support ($s$): The proportion of total transactions in dataset $D$ that contain both itemsets $X$ and $Y$:

   Swipe to see the full formula↔

   $$\text{Support}(X \implies Y) = P(X \cup Y) = \frac{\text{Count}(X \cup Y)}{|D|}$$
2. Confidence ($c$): The conditional probability that a transaction contains itemset $Y$, given that it contains itemset $X$:

   Swipe to see the full formula↔

   $$\text{Confidence}(X \implies Y) = P(Y \mid X) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} = \frac{\text{Count}(X \cup Y)}{\text{Count}(X)}$$

Four Core OLAP Cube Operations:

1. Roll-up (Drill-up): Performs aggregation on data by climbing up a concept hierarchy (e.g. Day $\to$ Month $\to$ Quarter $\to$ Year) or by reducing dimensions.
2. Drill-down (Roll-down): Navigates from less detailed data to more detailed data (e.g. Year $\to$ Quarter $\to$ Month $\to$ Day) to reveal granular root causes.
3. Slice and Dice:
   • Slice: Selects a single dimension value to produce a 2D sub-cube.
   • Dice: Selects a sub-cube by applying selection conditions on two or more dimensions.
4. Pivot (Rotate): Rotates the visual axes of the data cube to view data from alternative analytical perspectives.

Inmon vs. Kimball Data Warehouse Architectures:

Inmon (Top-Down):   [Sources] -> [ETL] -> [Normalized EDW (3NF)] -> [Dependent Data Marts] -> [Users]
Kimball (Bottom-Up): [Sources] -> [ETL] -> [Conformed Dimensional Data Marts (Star)] -> [Users]

---

The ETL (Extract, Transform, Load) Pipeline:

ETL is the foundational data integration pipeline that populates and maintains the data warehouse from operational source systems.

---

1. Extract:

• Techniques: Full extraction (bulk snapshot) or Incremental Change Data Capture (CDC) via database transaction logs, triggers, or timestamp delta queries (WHERE updated_at > last_sync).

2. Transform (The Heavy-Lifting Engine):

• Data Cleansing: Stripping whitespace, repairing invalid formatting, handling nulls/missing values.
• Deduplication: Merging duplicate customer accounts across CRM and legacy billing.
• Data Standardization: Mapping heterogeneous codes (e.g. M/F, 1/0, Male/Female $\to$ Male/Female).
• Surrogate Key Generation: Assigning system-generated sequential integer keys to isolate the warehouse from operational natural key changes.
• Aggregation & Derived Metrics: Precomputing daily/monthly store sales summaries.

3. Load:

• Initial Load: One-time bulk ingestion of all historical corporate data, often disabling indexes and foreign key constraints to maximize load throughput.
• Incremental Load: Scheduled delta batches (hourly, nightly) updating fact tables and managing Slowly Changing Dimensions (SCD Type 1, 2, or 3).

Star Schema vs. Snowflake Schema vs. Fact Constellation:

Star Schema:            Snowflake Schema:             Fact Constellation:
  [Dim: Time]             [Dim: Day] -> [Month] -> [Year]   [Fact: Sales]   [Fact: Shipping]
       │                            │                             │                │
[Fact: Sales] ── [Dim: Store]  [Fact: Sales] ── [Dim: Product]    └─ [Dim: Date] ──┘
       │                            │                  │              (Shared Conformed)
  [Dim: Product]              [Dim: Store]        [Category]

---

1. Star Schema:
   • Central Fact table surrounded by radial, single-tier denormalized Dimension tables.
   • Pros: Simple intuitive queries; minimal SQL joins (single-level join between fact and dimension); fastest OLAP query response.
   • Cons: Data redundancy within dimension tables (e.g. city/state repeated across store rows).
2. Snowflake Schema:
   • Dimension tables are completely or partially normalized into sub-dimension hierarchies (e.g. Product $\to$ Subcategory $\to$ Category).
   • Pros: Eliminates data redundancy; saves disk storage space; easier dimension maintenance.
   • Cons: Requires complex multi-table SQL joins, degrading analytical query performance.
3. Fact Constellation (Galaxy Schema):
   • Multiple fact tables sharing common, standardized conformed dimensions (e.g. Date, Customer shared between Sales Fact and Shipping Fact).
   • Essential for enterprise-scale dimensional bus modeling.

7-Stage Knowledge Discovery in Databases (KDD) Process:

[Raw Data] ──► 1. [Data Cleaning] ──► 2. [Data Integration] ──► 3. [Data Selection]
                                                                        │
[Actionable Knowledge] ◄── 7. [Evaluation] ◄── 6. [Data Mining] ◄── 4. [Transformation]

---

1. Data Cleaning: Removes noisy data, outliers, and handles missing values.
2. Data Integration: Merges multiple heterogeneous operational databases, flat files, and external APIs into a unified dataset.
3. Data Selection: Retrieves data relevant to the specific business analysis goal from the warehouse database.
4. Data Transformation: Consolidates data into formats appropriate for mining via normalization, binning/discretization, feature selection, and aggregation.
5. Data Mining (Core Intelligent Step): Applies advanced computational algorithms (Apriori, Decision Trees, K-Means, Neural Networks) to extract latent patterns.
6. Pattern Evaluation: Evaluates candidate patterns against interestingness thresholds (support, confidence, lift), filtering out trivial or redundant findings.
7. Knowledge Presentation (Visualization): Presents discovered insights to executives using charts, 3D surface plots, and executive dashboards for commercial decision-making.

Apriori Algorithm & The Apriori Property:

In a dataset with $d$ unique items, the total number of candidate itemsets is $2^d - 1$. For $d=100$, evaluating all $2^{100} \approx 1.26 \times 10^{30}$ itemsets by brute force is computationally impossible.

---

The Apriori Property (Downward Closure Property):

“All non-empty subsets of a frequent itemset must also be frequent.” Conversely: “If an itemset is infrequent, all of its supersets will inevitably be infrequent and must be pruned immediately.”

Mathematically:

---

Algorithmic Execution ($k$-itemset generation):

1. Join Step ($L_{k-1} \bowtie L_{k-1}$): Generates candidate $k$-itemsets $C_k$ by joining frequent $(k-1)$-itemsets $L_{k-1}$ that share the first $k-2$ items in lexicographical order.
2. Prune Step: For every candidate $c \in C_k$, verify whether any $(k-1)$-subset of $c$ is not in $L_{k-1}$. If any subset is infrequent, prune $c$ from $C_k$ immediately without scanning the database.
3. Scan Database: Scan the transaction database only to count frequencies of the remaining pruned candidate set $C_k$, retaining those meeting minimum support threshold to form $L_k$.

DBSCAN Density-Based Clustering:

DBSCAN locates dense clusters separated by low-density regions, governed by two hyperparameters: $\varepsilon$ (Epsilon: neighborhood radius) and $\text{MinPts}$ (minimum points required within radius).

---

Point Classifications:

1. Core Point: A point $p$ that contains at least $\text{MinPts}$ points within its $\varepsilon$-neighborhood ($|N_\varepsilon(p)| \ge \text{MinPts}$).
2. Border Point: A point that is not a core point, but falls within the $\varepsilon$-neighborhood of a core point.
3. Noise (Outlier) Point: A point that is neither a core point nor a border point.

---

DBSCAN vs. K-Means:

• Arbitrary Shapes: DBSCAN effortlessly discovers complex non-spherical clusters (e.g. concentric circles, elongated ribbons), whereas K-Means assumes convex spherical clusters.
• Cluster Count ($K$): DBSCAN determines the optimal number of clusters automatically from density distributions; K-Means requires specifying $K$ upfront.
• Outlier Handling: DBSCAN explicitly isolates noise points as outliers; K-Means forces every outlier into its nearest centroid, distorting cluster boundaries.

Step-by-Step Apriori Algorithm Trace:

Total transactions $N = 8$. Minimum Support Count $= 8 \times 37.5\% = \mathbf{3}$. Minimum Confidence $= \mathbf{70\%}$.

---

Part (a): Apriori Iterations

Iteration 1:

• Scan database for $C_1$ counts:
  • $\{\text{Bread}\}: 6$
  • $\{\text{Milk}\}: 6$
  • $\{\text{Butter}\}: 3$
  • $\{\text{Diaper}\}: 5$
  • $\{\text{Beer}\}: 4$
  • $\{\text{Eggs}\}: 2$ (Pruned: $< 3$)
  • $\{\text{Cola}\}: 3$
• Frequent 1-Itemsets ($L_1$):

  Swipe to see the full formula↔

  $$\{\text{Bread}: 6\}, \; \{\text{Milk}: 6\}, \; \{\text{Butter}: 3\}, \; \{\text{Diaper}: 5\}, \; \{\text{Beer}: 4\}, \; \{\text{Cola}: 3\}$$

---

Iteration 2:

• Generate $C_2$ pairs from $L_1$ and count occurrences in DB:
  • $\{\text{Bread, Milk}\}: 4 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Bread, Butter}\}: 2 < 3$
  • $\{\text{Bread, Diaper}\}: 4 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Bread, Beer}\}: 3 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Bread, Cola}\}: 1 < 3$
  • $\{\text{Milk, Butter}\}: 3 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Milk, Diaper}\}: 3 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Milk, Beer}\}: 2 < 3$
  • $\{\text{Milk, Cola}\}: 2 < 3$
  • $\{\text{Butter, Diaper}\}: 0$
  • $\{\text{Butter, Beer}\}: 0$
  • $\{\text{Butter, Cola}\}: 1$
  • $\{\text{Diaper, Beer}\}: 4 \ge 3 \implies \mathbf{L_2}$
  • $\{\text{Diaper, Cola}\}: 2 < 3$
  • $\{\text{Beer, Cola}\}: 1 < 3$
• Frequent 2-Itemsets ($L_2$):

  Swipe to see the full formula↔

  $$\{\text{Bread, Milk}: 4\}, \; \{\text{Bread, Diaper}: 4\}, \; \{\text{Bread, Beer}: 3\}, \; \{\text{Milk, Butter}: 3\}, \; \{\text{Milk, Diaper}: 3\}, \; \{\text{Diaper, Beer}: 4\}$$

---

Iteration 3:

• Candidate Generation $C_3$ from $L_2$: Joining $\{\text{Bread, Diaper}\}$, $\{\text{Bread, Beer}\}$, and $\{\text{Diaper, Beer}\}$ yields:

  Swipe to see the full formula↔

  $$C_3 = \{\text{Bread, Diaper, Beer}\}$$
  (Subsets: $\{\text{Bread, Diaper}\}, \{\text{Bread, Beer}\}, \{\text{Diaper, Beer}\}$ all belong to $L_2$. Pruning passes).
• Count Support in DB: Occurs in T200, T400, T800 $\implies \text{Count} = \mathbf{3} \ge 3$.
• Frequent 3-Itemsets ($L_3$):

  Swipe to see the full formula↔

  $$\{\text{Bread, Diaper, Beer}: 3\}$$
• No candidates can be formed for $C_4$. Algorithm terminates.

---

Part (b): Association Rule Generation from {Bread, Diaper, Beer} (Count = 3)

Non-empty subsets: $\{\text{Bread}\}, \{\text{Diaper}\}, \{\text{Beer}\}, \{\text{Bread, Diaper}\}, \{\text{Bread, Beer}\}, \{\text{Diaper, Beer}\}$.

1. Rule 1: $\{\text{Bread, Diaper}\} \implies \{\text{Beer}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{\text{Support}(\text{Bread, Diaper, Beer})}{\text{Support}(\text{Bread, Diaper})} = \frac{3}{4} = \mathbf{75\%} \ge 70\% \implies \textbf{STRONG RULE}$$
2. Rule 2: $\{\text{Bread, Beer}\} \implies \{\text{Diaper}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{\text{Support}(\text{Bread, Diaper, Beer})}{\text{Support}(\text{Bread, Beer})} = \frac{3}{3} = \mathbf{100\%} \ge 70\% \implies \textbf{STRONG RULE}$$
3. Rule 3: $\{\text{Diaper, Beer}\} \implies \{\text{Bread}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{\text{Support}(\text{Bread, Diaper, Beer})}{\text{Support}(\text{Diaper, Beer})} = \frac{3}{4} = \mathbf{75\%} \ge 70\% \implies \textbf{STRONG RULE}$$
4. Rule 4: $\{\text{Bread}\} \implies \{\text{Diaper, Beer}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{3}{\text{Support}(\text{Bread})} = \frac{3}{6} = 50\% < 70\% \implies \text{Rejected}$$
5. Rule 5: $\{\text{Diaper}\} \implies \{\text{Bread, Beer}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{3}{\text{Support}(\text{Diaper})} = \frac{3}{5} = 60\% < 70\% \implies \text{Rejected}$$
6. Rule 6: $\{\text{Beer}\} \implies \{\text{Bread, Diaper}\}$

   Swipe to see the full formula↔

   $$\text{Confidence} = \frac{3}{\text{Support}(\text{Beer})} = \frac{3}{4} = \mathbf{75\%} \ge 70\% \implies \textbf{STRONG RULE}$$

---

Part (c): Lift Calculation for {Diaper, Beer} => {Bread}

• $\text{Confidence}(\{\text{Diaper, Beer}\} \implies \{\text{Bread}\}) = \frac{3}{4} = 0.75$

• $\text{Support}(\{\text{Bread}\}) = \frac{6}{8} = 0.75$

  Swipe to see the full formula↔

  $$\text{Lift} = \frac{0.75}{0.75} = \mathbf{1.00}$$

• Commercial Interpretation: A Lift of exactly $1.00$ indicates statistical independence. The occurrence of purchasing Diapers and Beer together provides zero incremental predictive lift on whether the customer will buy Bread, as Bread has an identical 75% baseline probability across the entire supermarket regardless.

Retail Enterprise Data Warehouse Blueprint:

---

Part (a): Star Schema Dimensional Model for Daily Retail Sales

  [Dim_Customer] (SCD Type 2)           [Dim_Time]
  ├── customer_key (PK)                 ├── time_key (PK)
  ├── customer_id (NK)                  ├── date, day_of_week
  ├── full_name, phone                  ├── month, quarter, year
  ├── loyalty_tier, address             └── nepali_bs_date, is_holiday
  ├── start_date, end_date, is_current            │
             │                                    │
             └───────────────┐    ┌───────────────┘
                             ▼    ▼
                 ┌─────────────────────────────┐
                 │       Fact_DailySales       │
                 ├─────────────────────────────┤
                 │ sales_fact_id (PK)          │
                 │ customer_key (FK)           │
                 │ time_key (FK)               │
                 │ store_key (FK)              │
                 │ product_key (FK)            │
                 │ invoice_number (Degenerate) │
                 │ ── Measures ──              │
                 │ quantity_sold (Additive)    │
                 │ unit_selling_price          │
                 │ gross_revenue (Additive)    │
                 │ discount_amount (Additive)  │
                 │ vat_amount (13%) (Additive) │
                 │ net_revenue (Additive)      │
                 │ unit_cost, profit_margin    │
                 └─────────────────────────────┘
                             ▲    ▲
             ┌───────────────┘    └───────────────┐
             │                                    │
  [Dim_Store]                               [Dim_Product]
  ├── store_key (PK)                        ├── product_key (PK)
  ├── store_id (NK), store_name             ├── product_id (NK), barcode
  ├── city, district, province              ├── brand_name, category
  ├── total_square_footage                  ├── pack_size, uom
  └── store_manager_name                    └── standard_cost, list_price

• Slowly Changing Dimension (SCD Type 2) on Dim_Customer: When a customer moves from Pokhara to Kathmandu, rather than overwriting the record (Type 1), the system updates the existing row’s end_date = '2026-03-12' and sets is_current = FALSE. A new row is inserted with customer_key = 10842, city = 'Kathmandu', start_date = '2026-03-13', and is_current = TRUE. This preserves historical sales attribution accuracy for Pokhara store sales.

---

Part (b): Multi-Tiered Architecture Diagram

[POS Terminals: 40 Stores] [E-Commerce Web/App] [ERP / Supplier Inventory]
             │                     │                       │
             └─────────────────────┼───────────────────────┘
                                   │ (Nightly Batch / Real-Time Kafka CDC)
                      [Staging Area & ODS]
                   (Data Cleaning, Deduplication,
                    Surrogate Key Assignment)
                                   │
              [Enterprise Data Warehouse (EDW)]
             (PostgreSQL / Snowflake / BigQuery)
                                   │
         ┌─────────────────────────┴─────────────────────────┐
         ▼                                                   ▼
[MOLAP / Tabular Cubes]                           [Departmental Data Marts]
(Precomputed Aggregations: Sales, Finance)        (Procurement, Marketing, Loyalty)
         │                                                   │
         └─────────────────────────┬─────────────────────────┘
                                   │
             [Executive Dashboards & BI Analytics]
            (PowerBI, Metabase, Automated Restock Alerts)

---

Part (c): Three High-ROI Data Mining Applications:

1. Market Basket Analysis (Apriori / Association Mining):
   • Discovers frequently co-purchased items (e.g. Chiura and Mutton during Dashain) to optimize physical grocery aisle layouts and automated checkout bundle discounts.
2. Customer Churn & Loyalty Prediction (Random Forest / XGBoost):
   • Identifies high-value loyalty members whose shopping frequency has decreased by 30% over the last 45 days, automatically triggering personalized SMS discount vouchers.
3. Automated Inventory Demand Forecasting (Prophet / LSTM):
   • Forecasts daily store-level demand for perishable produce, accounting for seasonal festivals and local holidays, reducing stockouts by 35% and spoilage waste by 22%.