A data warehouse's star schema is typically denormalised, in contrast to an OLTP schema, chiefly because:

The warehouse is read/aggregated far more than written, so fewer joins per analytical query matters more than write-time redundancy

Denormalisation is required by SQL itself

OLTP databases cannot be normalised at all

Denormalisation eliminates the need for a fact table

In association rule mining, the CONFIDENCE of the rule 'A → B' measures:

The fraction of transactions containing A that also contain B

The fraction of all transactions containing both A and B

The total number of transactions in the dataset

Whether A causes B in a strict causal sense

Clustering, as distinct from classification, is characterised by:

No labelled training data — groups are discovered by similarity, not assigned to predefined categories

Always requiring exactly two clusters

Being usable only on numeric data

A Support Vector Machine (SVM) classifier chooses the separating hyperplane that:

Maximises the margin to the nearest points of each class

Minimises the number of training examples used

Is chosen entirely at random among all separating hyperplanes

Is always the same as the decision tree's root split

K-Nearest Neighbour (KNN) is described as a 'lazy' learning algorithm because:

It does no explicit model-fitting during training and defers all computation to query time

It is always slower than every other classifier at training time

It is a clustering algorithm, not a classifier

In the MapReduce programming model, the Map phase:

Runs only after the Reduce phase completes

Requires a single, non-distributed machine

Which of the following are recognised NoSQL data models? (More than one option may be correct.)

Strictly normalised third-normal-form relational tables only

Data Warehousing, Data Mining, Big Data and NoSQL

This chapter covers the analytics side of Unit 4, which has no GATE CS equivalent: data warehousing and OLAP for structured historical analysis, the classification/clustering/association techniques of data mining (which genuinely reach into machine-learning territory and must be grounded correctly rather than name-listed), and Big Data/NoSQL systems built for volumes and shapes of data a relational engine was never designed for.

Data Warehousing, Concept Hierarchies, OLAP and OLTP

OLTP versus OLAP
Property	OLTP (operational)	OLAP (analytical)
Purpose	Day-to-day transactions: insert, update, short reads	Historical, aggregated analysis for decision-making
Schema	Highly normalised (3NF/BCNF), minimising redundancy for fast, safe writes	Denormalised star/snowflake schema — a central fact table with numeric measures, joined to surrounding dimension tables
Typical operation	A single row insert/update	Roll-up/drill-down/slice/dice across a concept hierarchy (e.g. day → month → year)

🎯 Why a warehouse is denormalised on purpose

Normalisation minimises redundancy and update anomalies, which matters when data is being WRITTEN constantly (OLTP). A warehouse is instead READ far more than written (loaded periodically via ETL — extract, transform, load — rather than updated transactionally), so the priority flips: a denormalised star schema trades some redundancy for far fewer joins per analytical query, which is exactly what makes aggregate queries over millions of rows fast enough to be useful.

Data Mining: Association Rules, Classification and Clustering

Association rule mining finds patterns of the form 'if A then B' in transaction data, evaluated by SUPPORT (fraction of all transactions containing both A and B — how common the pattern is) and CONFIDENCE (fraction of transactions containing A that ALSO contain B — how reliable the rule is once A is present); the classic Apriori algorithm exploits the fact that any subset of a frequent itemset must itself be frequent to prune the search space.
Classification (SUPERVISED — trained on labelled examples) assigns a new instance to one of a fixed set of predefined categories: decision trees, Naive Bayes and Support Vector Machines are standard classifiers, each evaluated by accuracy on held-out (test) data rather than on the data it was trained on.
Clustering (UNSUPERVISED — no labels given) groups instances by similarity alone, discovering categories rather than being told them — k-means (partition-based, needs k chosen in advance) and hierarchical clustering (builds a dendrogram, no k needed upfront) are the two standard families; the fundamental line to hold is that classification needs labelled training data and clustering does not.

Regression, SVM, KNN, HMM and Link/Sequence/Social-Network Analysis

Regression predicts a CONTINUOUS numeric output (a house's price) rather than a discrete category, which is the line that separates it from classification — the same supervised-learning machinery (fit a model to labelled training data) is aimed at a different kind of target.
Support Vector Machine (SVM): a classifier that finds the hyperplane MAXIMISING the margin (perpendicular distance) to the nearest points of each class (the support vectors) — among all hyperplanes that separate the classes correctly, the max-margin one generalises best to unseen data, and the kernel trick extends this to data that is not linearly separable in its original space.
K-Nearest Neighbour (KNN): a LAZY (instance-based) classifier — it does no explicit training/model-fitting at all, and instead, at query time, finds the k closest training points to the new instance (by some distance metric) and votes their labels; k is a hyperparameter, and too small a k overfits to noise while too large a k blurs the decision boundary.
Hidden Markov Model (HMM): models a sequence generated by an unobserved (hidden) Markov chain of states, where each hidden state emits an OBSERVABLE symbol with some probability — used wherever the true underlying state is not directly seen but its effects are (speech recognition, part-of-speech tagging, DNA sequence analysis); the Viterbi algorithm finds the most likely hidden state sequence given the observations.
Summarisation, dependency modeling, link analysis, sequential-pattern analysis, social network analysis: summarisation compresses a dataset into a compact characteristic description; dependency modeling captures significant probabilistic dependencies among variables; link analysis studies the graph structure of relationships (PageRank being the canonical example); sequential-pattern analysis finds frequently-occurring ORDERED subsequences (as distinct from plain association rules, which ignore order); social network analysis applies graph-theoretic measures (centrality, community detection) to networks of people/entities.

Big Data Systems: Hadoop, MapReduce, HDFS and NoSQL

Big Data is conventionally characterised by the 'V's — Volume, Velocity, Variety (and often Veracity, Value) — data too large, too fast-arriving, or too unstructured for a single relational server to handle economically. Hadoop's core is two parts: HDFS (Hadoop Distributed File System) stores very large files by splitting them into blocks replicated across many commodity machines (tolerating individual machine failure without data loss), and MapReduce is a programming model that processes this distributed data in two user-defined phases — a MAP phase that transforms input records independently and in parallel into key-value pairs, and a REDUCE phase that aggregates all values sharing the same key — with the framework itself handling parallelisation, fault tolerance and moving computation to where the data already sits (rather than moving huge data to a central compute node).

⚠️ NoSQL is not 'no schema' or 'no query capability'

'NoSQL' commonly stands for 'Not Only SQL' rather than a literal absence of query languages, and covers several distinct data models rather than one: KEY-VALUE stores (simplest — a map from key to opaque value, e.g. Redis), DOCUMENT stores (semi-structured documents, typically JSON, e.g. MongoDB), COLUMN-FAMILY stores (optimised for very wide, sparse tables, e.g. Cassandra) and GRAPH databases (nodes and edges as first-class citizens, e.g. Neo4j, for relationship-heavy queries). Most NoSQL systems trade strict ACID transactions and rigid schema for horizontal scalability and flexible/evolving structure — the CAP theorem (a distributed system can guarantee at most two of Consistency, Availability and Partition tolerance at once) is the standard theoretical framing for why this trade-off is unavoidable at scale.

Key takeaways

OLTP (normalised, write-optimised) and OLAP (denormalised star schema, read/aggregate-optimised) serve opposite purposes; a warehouse is loaded via ETL, not updated transactionally.
Association rules are measured by support and confidence; classification (labelled, discrete output) differs from regression (labelled, continuous output) and both differ from clustering (unlabelled).
SVM maximises the margin to the nearest points of each class; KNN is a lazy, instance-based classifier with no explicit training phase; HMM models sequences from an unobserved state chain via observable emissions.
Hadoop's HDFS stores data across replicated blocks on commodity machines; MapReduce processes it via independent Map and aggregating Reduce phases, moving computation to the data.
NoSQL means 'Not Only SQL' and covers key-value, document, column-family and graph data models, trading strict ACID/rigid schema for horizontal scale — a CAP-theorem trade-off.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A data warehouse's star schema is typically denormalised, in contrast to an OLTP schema, chiefly because:
1. The warehouse is read/aggregated far more than written, so fewer joins per analytical query matters more than write-time redundancy
2. Denormalisation is required by SQL itself
3. OLTP databases cannot be normalised at all
4. Denormalisation eliminates the need for a fact table
Show answer
Answer: A — The warehouse is read/aggregated far more than written, so fewer joins per analytical query matters more than write-time redundancy
A warehouse's dominant workload is aggregate analytical queries, not frequent single-row writes, so trading some redundancy for far fewer joins is the right cost trade-off — the opposite of an OLTP schema's priorities.
In association rule mining, the CONFIDENCE of the rule 'A → B' measures:
1. The fraction of transactions containing A that also contain B
2. The fraction of all transactions containing both A and B
3. The total number of transactions in the dataset
4. Whether A causes B in a strict causal sense
Show answer
Answer: A — The fraction of transactions containing A that also contain B
Confidence is P(B|A) computed over the transaction data — how reliable the rule is once A is known to be present — which is distinct from support, P(A∩B), which measures how common the pattern is overall.
Clustering, as distinct from classification, is characterised by:
1. No labelled training data — groups are discovered by similarity, not assigned to predefined categories
2. Always requiring exactly two clusters
3. Being usable only on numeric data
4. Being identical to regression
Show answer
Answer: A — No labelled training data — groups are discovered by similarity, not assigned to predefined categories
Clustering is unsupervised — no labelled examples are given, and the algorithm discovers group structure from similarity alone, unlike classification, which is trained on examples already labelled with the correct category.
A Support Vector Machine (SVM) classifier chooses the separating hyperplane that:
1. Maximises the margin to the nearest points of each class
2. Minimises the number of training examples used
3. Is chosen entirely at random among all separating hyperplanes
4. Is always the same as the decision tree's root split
Show answer
Answer: A — Maximises the margin to the nearest points of each class
Among all hyperplanes that correctly separate the two classes, the one maximising the margin (distance to the nearest points, the support vectors) is chosen because it generalises best to data not seen during training.
K-Nearest Neighbour (KNN) is described as a 'lazy' learning algorithm because:
1. It does no explicit model-fitting during training and defers all computation to query time
2. It is always slower than every other classifier at training time
3. It requires no data at all
4. It is a clustering algorithm, not a classifier
Show answer
Answer: A — It does no explicit model-fitting during training and defers all computation to query time
Unlike an eager learner (e.g. a decision tree or SVM, which build an explicit model during training), KNN simply stores the training data and does its actual work — finding the k nearest neighbours — only when a query arrives.
In the MapReduce programming model, the Map phase:
1. Transforms input records independently and in parallel into key-value pairs
2. Aggregates all values sharing the same key
3. Runs only after the Reduce phase completes
4. Requires a single, non-distributed machine
Show answer
Answer: A — Transforms input records independently and in parallel into key-value pairs
Map transforms records into key-value pairs independently and in parallel across the cluster; it is the subsequent Reduce phase that aggregates values sharing a key, and the whole model is designed for distributed, not single-machine, execution.
Which of the following are recognised NoSQL data models? (More than one option may be correct.)
1. Key-value stores
2. Document stores
3. Graph databases
4. Strictly normalised third-normal-form relational tables only
Show answer
Answer: A — Key-value stores; B — Document stores; C — Graph databases
Key-value, document and graph stores (alongside column-family stores) are the standard NoSQL data models; rigid third-normal-form relational tables are exactly the traditional model NoSQL systems depart from.
Name the theorem stating that a distributed system can guarantee at most two of Consistency, Availability and Partition tolerance simultaneously.
Numerical answer — type the value.
Show answer
Answer: CAP theorem
The CAP theorem is the standard theoretical framing for why most distributed NoSQL systems consciously relax strict consistency (choosing AP) or availability (choosing CP) rather than promising all three at once.