Module 5

Chapter 1: Data Mining Concepts

28.1 Overview of Data Mining Technology

Data Mining :- Data Mining means finding new patterns, rules, and useful
information automatically from very large datasets
 Example:
A bank notices unusual credit card activity —
like a person who normally spends ₹500 suddenly spending ₹50,000 in
another city

28.1.1 Data Mining versus Data Warehousing

Data Warehouse

• A data warehouse stores a large amount of clean, organized, historical data.

• It is used mainly for decision making

Data Mining

• Data mining finds hidden patterns in the data.

• It can work on:
o Operational databases (daily transactions)
o Data warehouses (summarized data)

Relationship

• Data mining works better when a data warehouse already exists, because:
o Data is already cleaned
o Data is already summarized
o Searching becomes faster

28.1.2 Data Mining as a Part of the Knowledge Discovery Process

KDD (Knowledge Discovery in Databases) is the complete process of finding useful knowledge
from data
Data mining is only ONE step of KDD.
KDD includes six steps, and mining comes near the end.
Six Steps of the KDD Process

1. Data Selection
Choose the required data from the large database.
2. Data Cleansing
Remove errors and correct wrong data.

3. Data Enrichment
Add extra useful information from outside sources.

4. Data Transformation / Encoding

Convert data into simpler, grouped, or categorized form.

5. Data Mining
Apply algorithms to find patterns, rules, and deeper knowledge.

6. Reporting & Display

Show results using:

Example: Retail Store

A retail store has customer data like:

• name
• zip code
• phone number
• item purchased
• price
• quantity

Using KDD:

• Selection → choose data for a particular region

• Cleansing → correct wrong phone numbers
• Enrichment → add customer age or income
• Transformation → group items into categories
• Data mining → find useful patterns
• Reporting → show results in charts

After this, the store discovers: Association Rule

“If a customer buys video equipment → they also buy electronic gadgets.”
Sequential Pattern
“If a customer buys a camera → 3 months later buys supplies → then likely to buy
accessories.”
Classification Tree
Group customers based on:
• purchase amount
 • frequency of visits
• type of items bought
28.1.3 Goals of Data Mining and Knowledge Discovery
Prediction in data mining is the process of analyzing existing data patterns to forecast future
events or behaviors. It helps estimate outcomes such as customer buying behavior, future
sales, or the effects of business decisions.
Example: Predicting sales under discount offers, forecasting store revenue, or using seismic
wave patterns to predict earthquakes.
Identification in data mining refers to using data patterns to detect the presence of an item,
event, or activity. It helps recognize specific behaviors or occurrences from available data.
Example: Detecting system intruders by analyzing programs executed, files accessed, and
CPU usage, or identifying the existence of a gene in biological data.
Classification in data mining is the process of dividing data into different predefined classes
or categories based on selected parameters. It helps group similar items together for better
analysis.
Example: Supermarket customers can be classified as discount-seeking shoppers, loyal
customers, brand-oriented shoppers, or infrequent shoppers. Such classification helps in
analyzing buying behavior and preparing the data for further mining.
28.1.4 Types of Knowledge Discovered during Data Mining
Knowledge refers to meaningful patterns, insights, or intelligence extracted from data after
several levels of processing. There is a natural progression from raw data → information →
knowledge as more processing and interpretation occur.
Knowledge can be categorized into two major types:
1. Deductive Knowledge
• Derived by applying predefined logical rules on existing data.
• New information is deduced based on known facts.
• Example: rule-based systems.
2. Inductive Knowledge
• The focus of data mining.
• New rules and patterns are discovered automatically from given data without
predefined logic.
• Helps in identifying unknown relationships, dependencies, and trends.
Knowledge can be represented in various forms such as rules, propositional logic, decision
trees, neural networks, semantic networks, and hierarchical class structures.
Data mining commonly discovers the following types of knowledge:
1. Association Rules
Association rules discover relationships between items in a dataset.
They show how the presence of certain items is related to other items or attribute values.
Example:
• If a woman buys a handbag, she is likely to buy shoes.
• X-ray images with characteristics a and b often also show characteristic c.
These rules are widely used in market basket analysis and medical diagnosis.
2. Classification Hierarchies
Classification aims to create a hierarchy or model that organizes data into predefined classes.
Examples:
• Credit card users classified into five creditworthiness levels.
• Store locations rated on a 1–10 scale.
• Mutual funds categorized by growth, income, or stability.
This helps understand and predict behavior based on historical data.
3. Sequential Patterns
Sequential pattern discovery identifies ordered sequences of events over time.
Example:
If a patient had cardiac surgery and later developed high blood urea, they may face kidney
failure within 18 months.
This captures temporal relationships among events, useful in healthcare, retail, and fraud
detection.
4. Patterns in Time Series
Time series patterns analyze data at regular time intervals to detect similarities or trends.
Examples:
• Stock prices of two companies showing similar trends in a year.
• Products with similar sales patterns in summer but not in winter.
• Solar wind patterns predicting changes in Earth’s atmosphere.
Such patterns help forecast, compare behaviors, and detect anomalies.
5. Clustering
Clustering groups data into similar sets where each cluster contains items sharing close
characteristics.
Examples:
 • Grouping disease treatment data based on similarity of side effects.
• Categorizing adults into groups based on likelihood of buying a new product.
• Clustering web users based on document access patterns to identify user categories.
Clustering is useful in customer segmentation, medical research, and information retrieval.

28.2 Association Rules

28.2.1 Market-Basket Model, Support, and Confidence
support is a major Association rule mining is a data mining technique used to discover
relationships between items in large datasets—especially in market basket analysis, where we
study products purchased together in stores.
Market-Basket Model

• Think of the database as many transactions.

• Each transaction is a set of items a customer buys during one visit (a shopping basket).
Example:
Transaction1:{milk,bread,juice}
Transaction2:{milk,cereal}
Transaction3:{bread,butter,juice}
Transaction 4: {milk, juice}
Association Rule Format
A rule is written like:
X⇒Y
Where:
• X = items on the left-hand side (LHS)
• Y = items on the right-hand side (RHS)
Meaning:
If a customer buys X, they are likely to also buy Y.
Example rule: milk ⇒ juice
Support and Confidence
To decide whether a rule is useful, we measure:
1. Support (prevalence)
• The percentage of transactions that contain all items in X ∪ Y.
• Measures how often the itemset appears in the database.
Example:
If {milk, juice} appears in 2 out of 4 baskets → support = 50%
2. Confidence (strength)
• Measures how often Y appears when X appears.
• Formula:
confidence(X⇒Y)=support(X∪Y)support(X)\text{confidence}(X⇒Y)=
\frac{\text{support}(X∪Y)}{\text{support}(X)}confidence(X⇒Y)=support(X)support(X∪Y)
Example:
• Milk appears in 3 baskets.
• Milk & juice appear together in 2 baskets.
confidence=2/3≈66.7%\text{confidence} = 2/3 \approx 66.7\%confidence=2/3≈66.7%
Meaning:
When milk is bought, juice is also bought 66.7% of the time.
Key Insight
Support and confidence do not always move together.
Example from text:
• milk ⇒ juice has higher support (50%) and higher confidence (66.7%)
• bread ⇒ juice has lower support (25%) and lower confidence (50%)
Goal of Association Rule Mining
To find all rules where:
• Support ≥ user-specified minimum support
• Confidence ≥ user-specified minimum confidence
This ensures rules are:
• Frequent enough
• Strong enough
The problem is thus decomposed into two sub problems:
1. Generate all itemsets that have a support that exceeds the threshold. These sets of items are
called large (or frequent) itemsets. Large means large support.
2. For each large itemset, all the rules that have minimum confidence are generated as follows:
For a large itemset X and Y subset of X, let Z = X – Y; then if Support(X) /Support(Z) >
minimum confidence, the rule Z → Y is a valid rule.
Challenge
• The number of possible itemsets grows exponentially: 2m2^m2m if there are m items.
• Supermarkets stock thousands of products → impossible to check all combinations
directly.
Optimization Principles
To reduce computation, two important properties are used:
1. Downward closure
If an itemset is frequent, all its subsets must also be frequent.
Example:
If {milk, bread, juice} is frequent,
then {milk, bread} and {bread, juice} must also be frequent.
2. Antimonotonicity
If an itemset is infrequent, then all of its supersets are also infrequent.
Meaning:
If {milk, cereal} is NOT frequent,
then {milk, cereal, juice} can’t be frequent either.
These properties help search only promising combinations instead of testing everything.
yield a small itemset.

28.2.2 Apriori Algorithm

Apriori example (min support = 0.5) — step by step
Given: 4 transactions (items include milk, bread, juice, cookies, eggs, coffee). Minimum
support = 0.5 (i.e., an itemset must appear in at least 2 of the 4 transactions).
1. Scan once to count single items → candidate 1-itemsets (C1).
Counts/supports found:
o milk: 0.75 (3/4)
o bread: 0.5 (2/4)
o juice: 0.5 (2/4)
o cookies: 0.5 (2/4)
o eggs: 0.25 (1/4)
o coffee: 0.25 (1/4)
 2. Prune C1 to get frequent 1-itemsets (L1).
Keep items with support ≥ 0.5 → L1 = {milk, bread, juice, cookies}. (eggs and coffee
removed)
3. Generate candidate 2-itemsets (C2) from L1.
Combine L1 items pairwise: {milk,bread}, {milk,juice}, {bread,juice},
{milk,cookies}, {bread,cookies}, {juice,cookies}.
(We do not include pairs with eggs/coffee because those singletons were pruned.)
4. Scan and count supports for each C2.
Supports: 0.25, 0.5, 0.25, 0.25, 0.5, 0.25 respectively.
5. Prune C2 → frequent 2-itemsets (L2).
Keep pairs with support ≥ 0.5 → L2 = {{milk,juice}, {bread,cookies}}.
6. Attempt to create candidate 3-itemsets (C3) from L2.
To form a 3-item candidate, all its 2-item subsets must be frequent (downward closure).
Example: {milk,juice,bread} would need {milk,bread} to be in L2 — but {milk,bread}
is not in L2.
Therefore no valid 3-item candidates can be formed.
7. Terminate.
Final frequent itemsets are L1 = {{milk}, {bread}, {juice}, {cookies}} and L2 =
{{milk,juice}, {bread,cookies}}.

Three improved algorithms — simple summaries

1) Sampling algorithm — idea & steps
• Idea: work on a random sample of the database to find candidate frequent itemsets,
then verify them on the full database.
• Steps:
1. Take a random sample of transactions.
2. Run Apriori (or similar) on the sample to get candidate itemsets.
3. Scan the full DB once to compute exact supports only for those candidates.
• Pros: much faster because heavy work done on smaller data.
 • Cons: may miss some frequent itemsets (false negatives) unless sample is
large/carefully chosen.

28.2.4 Frequent-Pattern (FP) Tree and FP-Growth Algorithm

Motivation
Apriori generates candidate itemsets repeatedly — example:
• With 1000 frequent 1-itemsets, Apriori generates
(10002)=499,500\binom{1000}{2} = 499,500(21000)=499,500 candidate 2-itemsets
plus many more for 3-, 4-itemsets.

➡ This becomes computationally expensive.

FP-Growth avoids generating candidates by using a compressed tree representation of the
database.
Goal:
Convert the transaction database into a compact prefix-tree storing only frequent items.
Step 1: First database scan
• Count support (occurrence frequency) of each item
• Remove all items whose support < minimum support
Example (min support = 2):

Item Support

milk 3

bread 2

cookies 2

juice 2

Only these items appear in FP-Tree.

Step 2: Sort items in descending frequency order
Order for insertion:
milk > bread > cookies > juice
• This ordering is fixed and used in every transaction because:
• keeps tree compact
• ensures common prefixes merge
Step 3: Second database scan — Build FP-Tree
Start with a Null root node.
For each transaction:
 1. Remove infrequent items
2. Reorder remaining items using global order
3. Insert into tree
FP-Tree Insertion Logic
Suppose sorted transaction T = {milk, bread, cookies}
Starting at root:
1. Check if root has child “milk”
o If yes → increment its count
o If no → create new node (milk:1)
2. Move to milk node
Check if milk has child “bread”
o If yes → increment its count
o If no → create bread:1 node
3. Move to bread node
Continue same process for cookies
Paths merge when transactions share prefixes, reducing memory.
Item Header Table
Built alongside FP-Tree.
For each frequent item it stores:
• item name
• total support count
• link pointer to first occurrence of that item in tree
Occurrences of same item are linked like a linked list, enabling quick tree traversal.
Example entry:

Item Support Node Link → first node

Illustrating FP-Tree Meaning

The FP-Tree compactly represents the database:
• Common prefixes (e.g., items bought together often) share paths
• Node counts represent how many transactions share that prefix
Example:
Interpretation:
• milk appears 3 times
• milk → bread prefix appears twice
• milk → cookies appears twice
Mining FP-Tree — FP-Growth
Once FP-Tree is built, frequent itemsets are mined without candidate generation.
Divide-And-Conquer Strategy
FP-Growth works bottom-up:
1. Start from least frequent item
2. Build conditional pattern base
= all paths in the FP-Tree leading to that item
3. Convert to a conditional FP-Tree
4. Recurse to mine smaller trees
Example
Order of mining:
juice → cookies → bread → milk
Mining “juice”
Find all transactions ending in juice:
milk→juice
cookies → juice
Construct conditional tree showing:
{milk:1}, {cookies:1}
Produces frequent itemsets:
{juice}
{milk, juice}
Next, mine “cookies”, and so on.
Why FP-Growth is Efficient
• Database compression avoids repeated scanning
• Tree structure avoids storing redundant item combination
• No expensive candidate generation
• Recursive mining reduces problem into smaller parts

➡ Overall, FP-Growth is much faster than Apriori for dense datasets.

Final Concept Summary
FP-Tree:
• Built from frequent 1-itemsets only
• Items sorted by frequency
• Recursively inserted — shared prefixes merge
• Header table links all nodes of same item
FP-Growth:
• Mines FP-Tree recursively
• Uses conditional pattern bases + conditional FP-Trees
• Generates frequent patterns without candidate explosion

28.2.5 Partition Algorithm

Apriori needs multiple database scans and may struggle with very large data.
Partitioning helps by:
• breaking the database into smaller pieces
• finding frequent itemsets locally first.
• reducing candidate sets before global verification
Step 1: Divide the Database
• Split the database into non-overlapping partitions
Example: 1 million records → 10 partitions of 100,000 each. Each partition must fit in
main memory so it can be processed quickly.
Step 2: Process Each Partition Separately
For each partition:
1. Treat it like a mini-database
2. Run Apriori (or FP-growth) on it
 3. Find all local frequent itemsets (those meeting minimum support in that partition)
The minimum support threshold is interpreted relative to the partition size
(not the full database).
Step 3: Merge Local Results
After processing all partitions:
Take the union of all local frequent itemsets This forms the global candidate itemset list. Any
itemset that is globally frequent must appear as locally frequent in at least one partition. This
ensures no true frequent itemset is ever lost — no false negatives.
Step 4: Global Verification
Now scan the entire database once more.
• Count support of each global candidate itemset
• Keep only those that meet the original minimum support threshold
This final scan eliminates false positives
(local frequent itemsets that were not frequent in the full database)
After pass two, we obtain, The complete list of global frequent itemsets.
Advantages
Only 2 passes over the whole database. Each partition is scanned just once per local pass.
Works well for large datasets Natural fit for parallel / distributed processing
Example:
• Each partition can be processed on separate servers
• Local results merged afterward

28.3 Classification
Classification is a process where we teach a system to recognize and separate data into fixed
categories. Because the categories are already known, this is called supervised learning.
To do this, we first use a set of training data where each record already shows which category
it belongs to (called the class label). The system studies this data and learns patterns to build a
model—often as a decision tree or a set of rules.
Once the model is created, it can be used to classify new, unseen data. Important things to
consider include how accurately the model predicts results, how fast it runs, and whether it can
handle large amounts of data.
We will look at classification using decision trees.
A decision tree is like a flowchart that shows the rules used to classify data.
For example, from the tree you can see a rule like:
• If a customer is married and earns ≥ 50K, then she is a good credit risk.
Each path from the top of the tree (root) to the bottom (leaf) represents a rule for one of the
classes.
To build a decision tree, we start with all training examples at the root.
The data is then split step-by-step based on selected attributes.
At each step, the algorithm chooses the attribute that best separates the data—often using a
measure like information gain.

Before we illustrate Algorithm 28.3, we will explain the information gain measure
in more detail.
Why use entropy?
Entropy helps measure how mixed or pure a set of training samples is.
• If all samples belong to one class → entropy is low (pure).
• If samples are mixed across different classes → entropy is high (impure).
The goal is to reduce uncertainty, so we pick the attribute that gives the largest drop in
entropy, meaning it separates the classes best.

Expected information (entropy) for the whole dataset

Suppose:
• There are s total training samples.
• Class attribute has n different classes (v₁, v₂, ..., vₙ).
• sᵢ samples belong to class vᵢ.
Then:
• The probability that a random sample belongs to class vᵢ is
pᵢ = sᵢ / s.
Using these probabilities, entropy tells us how much information is needed to classify a
sample.
[Link] start with 6 training records
• 3 records have class yes
• 3 records have class no
So the initial entropy = I(3,3) = 1 bit
(This means the data is equally mixed — high uncertainty.)
2. We calculate entropy for each attribute to see which splits the data best
We compute entropy per value of the attribute and then average.
3. Attribute: Married
• For Married = yes → entropy = 0.92
• For Married = no → entropy = 0.92
• Weighted average → E(Married) = 0.92
So information gain = 1 – 0.92 = 0.08
(Small improvement)
4. Attribute: Salary
• After calculation → E(Salary) = 0.33
• Gain = 1 – 0.33 = 0.67
(This is the highest gain)
5. Attribute: Account Balance
• E = 0.92
• Gain = 0.08
(Not useful)
6. Attribute: Age
• E = 0.54
• Gain = 0.46
(Better than Married, but less than Salary)
7. Choose attribute with highest gain

✔ Salary wins (Gain = 0.67)

So Salary becomes root node of the decision tree.
8. Create branches for Salary values
• < 20K → all records = class no → leaf node
• ≥ 50K → all records = class yes → leaf node
 • 20K–50K → mixed records → continue splitting
9. For 20K–50K group (2 records remaining)
We recompute gains for remaining attributes:
• Gain(Married) = 0
• Gain(Acct_balance) = 1
• Gain(Age) = 1
Two attributes tie — choose either.
10. Choose Age (as example)
It becomes next node.
11. Split based on Age
• < 25 → one record → leaf node
• ≥ 25 → one record → leaf node
12. Tree is complete
Final decision tree classifies all training examples.
This process shows how decision trees select attributes based on information gain,
splitting data until pure class groups are formed.

28.4 Clustering
• Classification needs training data where classes (like good/bad risk) are already
known → this is called supervised learning.
• But sometimes we do not know the group labels.
We still want to group similar records together.
This is called clustering → an example of unsupervised learning.
Where clustering is useful?
• Businesses grouping customers with similar buying behavior.
• Medicine grouping patients who react similarly to drugs.
No predefined categories exist — the algorithm discovers the groups.
What does clustering do?
• It creates clusters (groups) where:
o Members inside a cluster are similar
o Members across clusters are different
o Clusters do not overlap (usually disjoint)
How do we measure similarity?
• Clustering depends on a similarity measure.
• When data values are numeric, distance-based similarity is commonly used.
• One common method is Euclidean distance (straight-line distance).
Example idea: distance between two records
• Suppose each data record has n attributes.
• For two records (rj and rk), attribute values are:
o On the ith attribute → rji and rki
• The Euclidean distance helps measure how far apart or close these two records are.
• The Euclidean distance between points rj and rk in n-dimensional space is calculated
as:

The smaller the distance between two points, the greater is the similarity as we think of them.
A classic clustering algorithm is the k-means algorithm, Algorithm 28.4.

The algorithm described is k-means clustering. Here’s how it works step by step:
1. Pick starting points: Randomly choose kkk records to be the initial “centroids” (the
center points) of kkk clusters.
2. Assign records to clusters: For each record in the dataset, find which centroid it is
closest to, and put the record in that cluster.
3. Update the centroids: After all records are assigned, calculate the new mean (average)
of each cluster. This becomes the new centroid.
4. Repeat: Go back to step 2 and reassign records to the cluster with the closest centroid.
Then update the centroids again.
5. Stop: Keep repeating until the clusters don’t change much or the overall error is as
small as possible. The error measures how far each record is from its cluster’s centroid.
In even simpler terms:
 • Pick cluster centers randomly.
• Put each point in the nearest cluster.
• Move the cluster centers to the average of their points.
• Repeat until things don’t change much.
The error is just the total distance of all points from their cluster centers. The algorithm tries
to make this as small as possible. For clusters C1, …, Ck with means m1, …, mk, the error is
defined as:

We have 2 clusters (k = 2).

The algorithm randomly picks record 3 to start cluster C1 and record 6 to start cluster C2.
First Round
Each remaining record is checked to see which cluster it is closest to:
• If it is closer to C1 → put it in C1
• If it is closer to C2 → put it in C2
Example:
• Record 1 is closer to C1 → goes to C1
• Record 2 is closer to C2 → goes to C2
• Record 4 is closer to C1 → goes to C1
• Record 5 is closer to C1 → goes to C1
Then we calculate the new centers (the average position of all points in each cluster):
• New center of C1 = (33.75, 8.75)
• New center of C2 = (52.5, 25)
Second Round
We repeat the process:
• Check all records again with the new centers
• This time:
 o Records 1, 4, 5 go to C1
o Records 2, 3, 6 go to C2
New centers become:
• C1 = (28.3, 6.7)
• C2 = (51.7, 21.7)
Third Round
We check again, but now:
• All records stay in the same clusters
So the algorithm stops — it has converged, meaning nothing changes anymore.

BIRCH Algorithm Explained Simply

Traditional clustering assumed all data fits in memory, but new huge databases break this
assumption.
What BIRCH does:

✔ It combines hierarchical clustering (tree-based structure) + other clustering techniques.

✔ It works efficiently on very large datasets.

It uses two main settings:
1. Amount of available memory
2. Maximum cluster radius (size limit)
o If the radius limit is large → fewer, bigger clusters
o If small → many smaller clusters
How it operates:
• Records are read one by one
• Inserted into a tree model that keeps clustering structure
• Each record goes to the closest leaf cluster (based on distance)
If inserting a record makes the cluster too large: The cluster may split, More memory may be
used If memory becomes too full: The radius limit is increased, Some clusters merge to reduce
number of stored clusters
Why is BIRCH good?

✔Very efficient, Works for large datasets, Running time grows linearly with number of records
 Module 5
Chapter 2: Overview of Data
Warehousing and OLAP
29.1 INTRODUCTION, DEFINITIONS, AND TERMINLOGY
1. What is a Data Warehouse?
A data warehouse is a large collection of integrated, historical data used mainly for decision
support and analytical processing.
While a traditional database stores current operational data, a data warehouse organizes data
for long-term analysis, strategic planning, and management decisions.
W.H. Inmon’s Classic Definition
A data warehouse is a subject-oriented, integrated, nonvolatile, time-variant collection of data
in support of management’s decisions. This definition highlights four characteristics:
a) Subject-Oriented
Organized around major subjects like Customers, Products, Sales, Revenue Focused on
analysis, not processing transactions
b) Integrated
Data is cleaned and standardized from multiple sources:
→ Databases, files, ERP systems, CRM systems Ensures consistent naming, measurements,
formats
c) Nonvolatile
Data is read-only Loaded periodically (daily/weekly/monthly No frequent updates or deletes
Provides stable data for analysis
d) Time-Variant
Stores historical data, not just current values Allows trend analysis (e.g., sales over 5 years)
2. Why Data Warehouses Exist
Organizations need:
Historical analysis
Better decision-making
Cleaned and consolidated data from different sources
Fast retrieval for reports and dashboards
Traditional OLTP databases cannot support complex analytical queries. Data warehouses fill
this gap.
3. OLTP vs OLAP
FeatureOLTP (Operational DB) OLAP (Data Warehouse)
Purpose Daily operations Decision
Support
Daata Current Historical

Queries simple Long, complex

Short,
Operations Insert, update, delete Read-only
analysis
Users Clerks, customers Managers,
analysts
Speed Optimized for Optimized for reading
writing

4. OLAP (Online Analytical Processing)

OLAP is used for multi-dimensional analysis of data.
Key Features
Quick querying, Drill-down (detailed view), Roll-up (summary view), Slice and dice (view
data from different angles), Supports dashboards, cubes, pivot tables
Useful for:
✔ Market analysis

✔ Trend predictions

✔ Business strategy planning

5. DSS (Decision Support Systems)
Decision Support Systems help managers make: Strategic decisions, Long-term planning.
6. Data Mining
Data mining discovers hidden patterns, correlations, and predictions from large datasets.
Examples:
Identifying buying patterns
Predicting customer churn
Fraud detection
29.2 Characteristics of Data Warehouses
To distinguish a data warehouse from traditional databases, the following properties are
essential.
1. Multidimensional View of Data
A data warehouse supports multidimensional analysis using “data cubes”.
Dimensions may include:
Time Product Geography Customer Salesperson
2. Large Volume of Data
Data warehouses store very large datasets (terabytes → petabytes).
Used for: Trend analysis Pattern extraction Business intelligence
3. Nonvolatile Data
Data is not modified once entered
Only periodic refresh/update occurs
Supports stable analytical queries
4. Time-Variant
Data warehouse stores snapshots of data at different time intervals.
Enables
Time-series analysis Yearly, monthly, weekly comparisons Forecasting
5. Read/Append Access
Warehouse does not support regular OLTP operations.
Only: Bulk insert Periodic load Queries for analysis
6. Integrated Data
Data from multiple sources is cleaned and merged.
Cleaning includes:
Removing duplicates
Standardizing formats
Handling missing data
Resolving naming conflicts
Architecture of a Data Warehouse
The architecture consists of 3 main stages:
1. Data Sources
Data originates from:
Operational databases (OLTP)
Flat files
Logs
ERP/CRM systems
External sources (market data, sensors)
2. ETL Process (Extract → Transform → Load)
Extract
Pull data from multiple databases and files
Transform
Clean
Filter
Convert formats
Merge
Apply business rules
Load
Insert processed data into warehouse tables
ETL tools also perform preprocessing, as shown in the diagram.
3. Data Warehouse Storage
Consists of:
a) Data Repository
Stores actual data in structured, multidimensional form.
b) Metadata Repository
Stores data about:
Source of data Meaning Transformations applied Refresh schedules
4. Front-End Tools
Tools interacting with the warehouse:
OLAP tools → analytical querying
DSS tools → decision making
EIS/MIS → reports for executives
Data mining → knowledge discovery

Characteristics of an OLAP System (Codd & Salley)

OLAP systems must support:
1. Multidimensional view
2. Unlimited dimensions and aggregation levels
3. Cross-dimensional analysis
4. Sparse matrix handling
5. Client/server architecture
6. Multiuser support
7. Accessibility
8. Transparency
9. Intuitive data manipulation
10. Inductive (patterns) and deductive (queries) analysis
11. Flexible reporting
Types of Data Warehouses
1. Enterprise Data Warehouse (EDW)
Covers entire organization
Most comprehensive
Very expensive
Long implementation time
Petabytes of data
2. Virtual Data Warehouse
Does not store data physically
Uses views on operational databases
Faster & cheaper
Limited functionality
3. Logical Data Warehouse
Uses data federation
Combines multiple systems logically
No need for central storage
Easier to maintain
4. Data Marts
Small-scale warehouse
Focused on a single department
(HR, Finance, Sales, Marketing)
Cheaper and faster to develop
Can be independent or dependent on EDW
Other Related Terms
Operational Data Store (ODS)
Intermediate storage
Used before cleansing and integration
Short-term data
Not suitable for long-term analysis
Analytical Data Store (ADS)
Refined, cleaned data
Used specifically for analysis
Often created from ODS
29.3 Data Modeling for Data Warehouses
What Is a Data Warehouse?
A central repository of integrated, historical data Supports analysis, reporting, and business
intelligence Uses multidimensional modeling for fast querying, Organizes data into
dimensions and facts

• Data represented as multidimensional cubes Each axis =

dimension
• Example: Product, Region, Fiscal Quarter
• Cells contain numerical values (ex: sales revenue)

• Can extend to more than 3 dimensions → hypercubes

• Dimensions Example Common corporate data warehouse dimensions: Products,
Fiscal periods (quarters/years) Regions, These provide multiple perspectives for
analysing data.
Slice and Dice: Slice: 2D view of the cube, Example: Product × Region (Figure 29.2)
Dice: Choose specific ranges across multiple dimensions, Used to focus on specific
aspects of data.
Pivot (Rotation): Changes the orientation of the data cube, Shows data by different
combinations of dimensions
Example: Rotate to show:
Rows: Region
Columns: Fiscal Quarter
Third dimension: Product
Makes analysis more flexible and intuitive
Visual: Figure 29.4 (pivoted cube)

Roll-Up (Aggregation)

• Moves up the hierarchy

• Combines detailed data → larger categories
• Weeks → Quarters → Years
• Products → Product Categories
• Used for summary reporting
 Drill-Down (Disaggregation)

• Opposite of roll-up
• Moves down the hierarchy
• From high-level summaries → fine-grained details
o Country → Region → Subregion → Zip code

• Product line → Product type → Style → Sub-style

Key Components of Multidimensional

Two main table types:

Dimension Tables
Describe entities
Attributes like Product Name, Region Name,
etc.
Fact Tables
Contain measured values
Link to dimensions with foreign keys
Fact Table Example
Fact Table: Business Results
Columns: Product Quarter Region Revenue
 Visual: Figure 29.7 (Fact + Dimension tables)
Star Schema
Fact table at the center
Surrounded by denormalized dimension tables
Simple, fast for queries
Most popular schema in data warehousing

Snowflake Schema
Variation of star schema
Normalized dimension tables
Reduces redundancy
More complex joins

Fact Constellation: Also called Galaxy Schema, Multiple fact tables Shared dimension
tables, Useful for enterprise-wide warehouses
Example:
Fact Table 1: Business
Results
Fact Table 2: Business
Forecast Shared
Dimension: Product
 Indexing in Data Warehouses: Index types for fast querying:
Bitmap Indexes
🞇 One bit vector per attribute value
🞇 Excellent for low-cardinality data (e.g., car size)
🞇 Efficient for comparisons and aggregations
Join Indexes
🞇 Speed up joins between fact & dimension tables
🞇 Store tuple IDs for matching dimension values
Advantages:
🞇 Fast filtering
🞇 Fast combining (AND, OR operations)

Summary Data Storage

🞇 Data warehouses often store:
🞇 Pre-computed summaries
🞇 e.g., quarterly revenue by product line
🞇 Level encodings
🞇 e.g., weekly, monthly, annual marker, Provides faster reporting with
predictable
queries.

Master Data Management (MDM)

🞇 Ensures consistency of critical entities:
🞇 Customers
🞇 Regions
🞇 Products
🞇 Dimension tables = master data
🞇 Designers must cleanse, harmonize, and standardize across systems

29.4 Building a dataware house

•A data warehouse must support ad hoc queries and decision-making.

•The design depends on the future usage of the warehouse.

Steps in Acquiring Data for a Data Warehouse

[Link] Data
•From multiple heterogeneous sources (databases, files, market data, etc.).

[Link] Data for Consistency

•Standardize names, meanings, domains.

•Resolve differences in calendars, units, codes

[Link] the Data Remove errors, duplicates, incomplete records. Most time-consuming step.
Correction returned to source is called Backflushing.
[Link] Data to Warehouse Model Convert data to match the warehouse’s schema (relational →
multidimensional).
[Link] Data into Warehouse Load huge volumes of data using batch/ incremental updates.
Must consider: update frequency, downtime, dependencies, storage, partitioning.
Data Loading Order Data may come from multiple sources and time zones. Correct loading
order prevents integrity violations.
Master data (Customer, Product) before transaction data.
Invoice data after loading billing data

Metadata in a Data Warehouse

•Technical metadata
•Acquisition details, storage, access structures, operations.
•Business metadata
•Meaning, rules, policies, organizational info.
Distributed & Federated Warehouses
•Distributed Warehouse
•Replication, partitioning, high availability, load balancing.
•Federated Warehouse
•Autonomous data warehouses connected together.
•Each has its own metadata repository

29.5 Typical Functionality of a Data Warehouse

Typical Functionality of a Data Warehouse
•Data warehouses support advanced analysis using:

•Roll-up: Summarizes data from detailed → higher level.

•Drill-down: Shows more detailed, fine-level data.

•Pivot (Rotate): Changes the data viewing orientation (rows ↔ columns).

•Slice and Dice: Select specific dimension values and view data subsets.

•Sorting: Orders data on any attribute.

•Selection: Filters data based on conditions. Derived attributes: New values computed from
existing data.

OLAP Types:
•ROLAP: Uses relational databases for OLAP.

•MOLAP: Uses multidimensional cubes.

•HOLAP: Hybrid of ROLAP + MOLAP (faster + detailed drill-through).

29.6 DATA WAREHOUSE VS VIEWS

2.7 DIFFICULTIES OF IMPLEMENTING DATA WAREHOUSES

Difficulties of Implementing Data Warehouses

[Link] & Administration

ChallengesRequires huge planning, design, and project [Link]-consuming

to build enterprise-level data [Link] administration due to size and continuous
evolution.

2. Data Quality Issues

Ensuring accuracy, consistency, and cleaning of data is [Link] different
data formats, definitions, and identifiers is challenging.

3. Usage & Growth Management

•Usage projections must be conservative and updated [Link] must scale as
data volume and user queries grow.

4. Technological Changes
Hardware, software, and user requirements change over [Link] warehouse must
support modular design for future upgrades.

5. Need for Skilled Team

Requires broader skills than normal database administration.
Needs technical + business knowledge, coordination across departments.

6. Complex Management
Selecting the right tools, architecture, and administration team is difficult.
Managing a large organizational data warehouse is a continuous task.

END