UNIT 2: IT BUSINESS & DISASTER RECOVERY PLANNING

(Based on Analysis of Provided Historical Exam Questions)

I. DATA WAREHOUSING FUNDAMENTALS

Data Warehouse (DW) Definition & Core Characteristics

A subject-oriented, integrated, time-variant, and non-volatile collection of data in support of management's decision-making process.

[!TIP] Exam Focus: Be prepared to define each characteristic with a brief example.

DW Architecture & Components

A typical architecture is a multi-tiered system:

1. Data Sources: Operational databases, external sources, legacy systems.

2. Staging Area: Temporary storage for data extraction, cleaning, and transformation (ETL process).

3. Data Warehouse: Central repository storing integrated, historical data, often in dimensional models (star/snowflake).

4. Metadata: "Data about the data." Defines source, structure, lineage, and meaning of warehouse data.

5. Access Tools: Front-end tools for users (OLAP tools, data mining tools, query/reporting tools, dashboards).

DiagramSEARCH: "data warehouse architecture diagram three tier"

DW Implementation Techniques

• Top-Down (Inmon Approach): Build a centralized, enterprise-wide data warehouse first, then create data marts from it. Emphasizes integration.

• Bottom-Up (Kimball Approach): Build dependent data marts first for specific business processes, then integrate them into a data warehouse. Faster initial ROI.

• Hybrid Approach: Combines elements of both.

Data Warehouse Schemas

• Star Schema: Simplest and most common. Consists of a single Fact Table (central, containing foreign keys to dimensions and quantitative measures) connected to multiple Denormalized Dimension Tables (each with a primary key). Optimized for query performance.

• Snowflake Schema: An extension of the star schema where dimension tables are normalized into multiple related tables. Reduces redundancy but increases join complexity, potentially slowing queries.

• Galaxy Schema / Fact Constellations: Used for complex, large data warehouses. Contains multiple fact tables that share common dimension tables. Represents a collection of star schemas.

[!TIP] High-Frequency: Be ready to draw and compare Star vs. Snowflake vs. Galaxy schemas. Galaxy is for multidimensional databases with multiple fact tables.

II. ONLINE ANALYTICAL PROCESSING (OLAP)

OLAP vs. OLTP

OLAP Types & Servers

• MOLAP (Multidimensional OLAP): Uses proprietary multidimensional storage (arrays). Fast query performance due to pre-aggregation. Limited by data volume ("sparsity problem"). Need: For high-speed analysis of summarized data.

• ROLAP (Relational OLAP): Uses relational DBMS. Stores data in normalized tables. Handles large data volumes efficiently. Queries can be slower due to complex joins.

  
  DiagramCANVAS: "ROLAP Architecture Diagram: Client -> OLAP Server -> Relational DB (with fact & dimension tables in 3NF)"
  
  

• HOLAP (Hybrid OLAP): Combines MOLAP and ROLAP. Stores aggregated data in multidimensional format and detailed data in relational tables.

OLAP Operations & Data Cubes

A Data Cube is a multidimensional logical view of data (e.g., dimensions: Product, Store, Time; measure: Sales).

• Roll-up (Drill-up): Aggregation up a hierarchy (e.g., City -> State -> Country).

• Drill-down (Roll-down): Moving down a hierarchy to finer detail (e.g., Year -> Quarter -> Month).

• Slice: Selecting a single dimension value, creating a sub-cube (e.g., Sales[Time="2023"]).

• Dice: Selecting a range of values on multiple dimensions, creating a sub-cube.

• Pivot (Rotate): Reorienting the cube to view data from a different perspective (changing dimensions on axes).

Data Cubes Computation Process

1. Identify Dimensions & Measures: Define the axes (dimensions) and the quantitative facts (measures).

2. Identify Hierarchies: Define aggregation levels for each dimension (e.g., Time: Day < Month < Quarter < Year).

3. Compute Aggregates: Calculate all possible aggregate values (group-bys) based on the lattice of the cube's dimensions and hierarchies. This can be done via:

   • Full Cube Computation: Computing all possible group-bys. Expensive.

   • Partial Cube Computation / Iceberg Cube: Computing only aggregates above a minimum support threshold.

   • Smart Algorithms: Using techniques like sorting, hashing, and array indexing to avoid repeated scans.

III. DATA MINING OVERVIEW

Definition, Goals, and Process

• Definition: The process of discovering interesting, non-trivial, implicit, and previously unknown knowledge from large amounts of data.

• Goals: Prediction (e.g., will a customer churn?), description (e.g., what are the typical customer segments?), pattern discovery.

• Context: Part of the larger KDD (Knowledge Discovery in Databases) process.

• KDD Process: Selection -> Preprocessing -> Transformation -> Data Mining -> Interpretation/Evaluation.

Data Mining Task Primitives

1. Task-Relevant Data: Specifying the portion of the database to be mined (e.g., relevant attributes, time period).

2. Background Knowledge: Concepts, hierarchies, constraints (e.g., "Age > 18 is Adult").

3. Interestingness Measures: Metrics to evaluate discovered patterns (e.g., support, confidence, lift for association rules; accuracy for classification).

4. Presentation/Discovery: How results are visualized or reported (e.g., rules, trees, clusters, graphs).

Role of Data Mining Engine in KDD Process

The core algorithm module that executes the data mining function (e.g., runs Apriori, ID3, k-means) on the preprocessed and transformed data. It takes the task primitives as input and produces patterns.

Types of Data on Which Data Mining is Applied

• Relational databases

• Transactional databases

• Data warehouses

• Flat files

• Advanced: Stream data, temporal data, spatial data, text, web data, graphs.

IV. DATA PREPROCESSING

Data Cleaning

• Missing Data: Handle by ignoring tuples, filling with mean/median/mode, using ML algorithms to predict, or treating "missing" as a separate value.

• Noisy Data: Use smoothing techniques (binning, regression, clustering), or outlier detection/removal.

• Inconsistency Resolution: Resolve conflicts in naming, coding, or derived values (e.g., "M" vs "Male").

Data Transformation Methods

• Smoothing: Remove noise (see above).

• Attribute Construction: Create new attributes from existing ones (e.g., BMI = weight/height²).

• Aggregation: Summarize data (e.g., daily sales to monthly sales).

• Normalization: Scale attribute values to a small, specified range (e.g., min-max normalization to [0,1], z-score normalization to mean=0, std=1).

$$ x' = \frac{x - \min(X)}{\max(X) - \min(X)} \quad \text{(Min-Max)} $$

$$ x' = \frac{x - \mu}{\sigma} \quad \text{(Z-Score)} $$

• Discretization: Convert continuous attributes to categorical (e.g., age to "Youth", "Adult", "Senior").

Data Integration & Reduction

• Vertical Partitioning: Splitting a table by columns into smaller, related tables. A table is partitioned vertically if each partition contains a subset of the attributes (columns) and the same set of tuples (rows) but with a different key.

  • How it is done: Identify groups of attributes that are often accessed together (e.g., personal info vs. transaction history). Create separate tables with a common primary key.

  • Goal: Improve I/O performance and cache efficiency for queries that access only specific attribute groups.

V. ASSOCIATION RULE MINING

Basic Concepts

• Itemset: A set of items (e.g., {Bread, Milk}).

• Support (σ): Fraction of transactions containing the itemset.

$$ \text{support}(X) = \frac{\text{number of transactions containing } X}{\text{total number of transactions}} $$

• Confidence (c): Conditional probability that a transaction containing X also contains Y.

$$ \text{confidence}(X \rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} $$

• Frequent Itemset: An itemset with support ≥ min_support threshold.

• Strong Association Rule: A rule with support ≥ min_support and confidence ≥ min_confidence.

Apriori Algorithm

Principle: All non-empty subsets of a frequent itemset must themselves be frequent (Apriori property). Uses a "candidate generation & test" approach.

1. Find Frequent 1-itemsets (L1) by scanning DB and counting.

2. k=2: Generate candidate 2-itemsets (C2) from L1. Prune candidates with infrequent subsets. Scan DB to find L2 from C2.

3. k>2: Generate Ck from Lk-1 (join step). Prune candidates with any (k-1)-subset not in Lk-1. Scan DB to find Lk.

4. Stop when no new frequent itemsets are found.

5. Generate Rules from frequent itemsets (for each subset A of itemset S, if confidence(A -> S-A) >= min_conf, output rule).

[!TIP] Common Pitfall: Apriori can generate a huge number of candidates and requires multiple full database scans.

FP-Growth Algorithm

Principle: Avoid candidate generation. Uses a compact data structure called FP-tree.

1. Scan DB once to find frequent 1-itemsets (L1).

2. Build FP-tree:

   • Order frequent items in each transaction by descending frequency (from L1).

   • Insert ordered transaction into a prefix tree (trie), incrementing node counts. Share common prefixes.

3. Mine FP-tree recursively:

   • For each frequent item i (starting from least frequent), construct conditional pattern base (paths from root to nodes with i).

   • Build conditional FP-tree from conditional pattern base.

   • Recursively mine conditional FP-trees to generate all frequent itemsets containing i.

[!TIP] Exam Key: FP-Growth is faster than Apriori as it uses a compressed tree structure and requires only two database scans.

Techniques to Improve Efficiency of Apriori

• Hashing: Use hash tables to quickly count candidate itemsets and prune based on hash buckets.

• Partitioning: Split DB into partitions. Find local frequent itemsets in each partition, then global candidates. Requires only two scans.

• Reduction of Candidate Generation: Use advanced pruning techniques.

• Sampling: Run on a random sample, then verify candidates on full DB (risk of missing itemsets).

• Parallel & Distributed Mining: Distribute the workload.

VI. CLASSIFICATION

Learning Phase in Classification (Model Construction)

1. Training: A learning algorithm analyzes a training dataset (tuples with known class labels).

2. Model Building: The algorithm constructs a model (e.g., decision tree, classification rules, probabilistic model) that captures the relationship between attribute values and the class label.

3. Model Representation: The model is stored in a form suitable for prediction (e.g., tree structure, set of IF-THEN rules, probability tables).

Decision Tree Induction Algorithm (e.g., ID3/C4.5)

• Tree Structure: Internal nodes test an attribute, branches represent test outcomes, leaf nodes hold class labels.

• Splitting Criteria: Choose the attribute that best separates the classes.

  • ID3: Uses Information Gain (based on Entropy).

$$ \text{Entropy}(S) = -\sum_{i=1}^{c} p_i \log_2 p_i $$

$$ \text{Gain}(S, A) = \text{Entropy}(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} \text{Entropy}(S_v) $$

*   **C4.5:** Uses **Gain Ratio** to overcome bias of Information Gain towards many-valued attributes.

$$ \text{Gain Ratio}(S, A) = \frac{\text{Gain}(S, A)}{\text{SplitInfo}(S, A)} $$

• Pruning: To avoid overfitting.

  • Pre-pruning (Early stopping): Stop tree growth based on criteria (e.g., min samples per leaf, max depth).

  • Post-pruning: Build full tree, then remove branches that do not improve accuracy on a validation set (e.g., error-based pruning).

Rule-Based Classification Algorithms

• Sequential Covering: Iteratively learns a rule, removes covered examples, repeats.

  1. Start with empty rule IF THEN.

  2. Add conditions to the rule's antecedent to maximize information gain or accuracy.

  3. When rule is sufficiently accurate, add it to rule set.

  4. Remove examples covered by the rule. Repeat until all examples covered or stopping condition.

• RIPPER (Repeated Incremental Pruning to Produce Error Reduction): An optimized sequential covering algorithm with explicit pruning.

Bayesian Classification (Naive Bayes)

• Bayes' Theorem:

$$ P(C|X) = \frac{P(X|C) \cdot P(C)}{P(X)} $$

where `C` is class, `X = (x1, x2, ..., xn)` is attribute vector.

• Naive Assumption: Attributes are conditionally independent given the class.

$$ P(X|C) = P(x_1|C) \cdot P(x_2|C) \cdot ... \cdot P(x_n|C) $$

• Classifier: Assigns class c that maximizes P(c) * Π P(xi|c).

• Advantage: Simple, fast, works well with high-dimensional data.

Probabilistic Classifiers

Classifiers that output a probability distribution over possible classes, not just a single label. They estimate P(C|X).

• Examples: Naive Bayes, Logistic Regression, Bayesian Networks.

• Benefit: Provides confidence measure for predictions.

Classifier Evaluation & Verification

• Accuracy: (Number of correct predictions) / (Total predictions).

• Holdout Method: Split data into training set and test set (e.g., 2/3 train, 1/3 test).

• Cross-Validation (k-fold): Partition data into k subsets. Use k-1 for training, 1 for testing; repeat k times. Average accuracy.

• Confusion Matrix: For binary classification:

  | | Predicted: Yes | Predicted: No | | :--- | :--- | :--- | | Actual: Yes | TP (True Positive) | FN (False Negative) | | Actual: No | FP (False Positive) | TN (True Negative) |

• Key Metrics:

  • Precision (Positive Predictive Value): TP / (TP + FP) (Of those predicted positive, how many are correct?)

  • Recall (True Positive Rate): TP / (TP + FN) (Of all actual positives, how many were found?)

  • F1-Score: Harmonic mean of Precision and Recall: 2 * (Precision * Recall) / (Precision + Recall).

VII. CLUSTERING

Definition and Purpose

Partitioning a dataset into groups (clusters) such that data points in the same cluster are highly similar to each other, but dissimilar to points in other clusters. Unsupervised learning (no class labels).

Important Clustering Methods

• Partitioning (e.g., k-means): Partitions n objects into k clusters (k ≤ n). Optimizes an objective function (e.g., sum of squared errors).

• Density-based (e.g., DBSCAN): Clusters are dense regions separated by sparse regions. Can find arbitrarily shaped clusters and handle noise.

• Grid-based: Objects are mapped into a grid structure. Clustering operations are performed on the grid cells (fast, independent of data size).

Hierarchical Clustering

Produces a tree-like structure (dendrogram) of clusters.

• Agglomerative (Bottom-up): Starts with each object as a singleton cluster. Iteratively merges the two closest clusters until one cluster remains or a stopping condition.

  • Linkage Criteria:

    • Single Link: Min distance between clusters (chaining effect).

    • Complete Link: Max distance between clusters (compact clusters).

    • Average Link: Average distance between clusters.

    • Ward's Method: Minimizes total within-cluster variance.

• Divisive (Top-down): Starts with all objects in one cluster. Iteratively splits clusters until each object is in its own cluster or a stopping condition.

[!TIP] High-Frequency: Differentiate Agglomerative (Bottom-up) vs. Divisive (Top-down):

| Aspect | Agglomerative (Bottom-up) | Divisive (Top-down) |

| :--- | :--- | :--- |

| Approach | Start with n clusters, merge. | Start with 1 cluster, split. |

| Computational Cost | Generally lower (O(n² log n)). | Higher (often O(2ⁿ)). |

| Merging/Splitting | Greedy, irreversible. | Can be more global, but complex. |

| Common Use | More popular, intuitive. | Less common due to complexity. |

VIII. SPECIALIZED DATA MINING APPLICATIONS

• Web Usage Mining: Discovery of user usage patterns from web logs. Techniques: Session identification, path analysis, association rule mining on page views.

• Text Mining: Discovery of patterns from unstructured text data. Techniques: Text preprocessing (tokenization, stemming), vector space model, topic modeling (LDA), sentiment analysis.

• Spatial Mining: Discovery of patterns from spatial databases (data with implicit/ explicit location). Techniques: Spatial association rules, spatial clustering (e.g., DBSCAN variants), spatial classification.

IX. OBJECT-ORIENTED ANALYSIS & DESIGN (OOAD) FUNDAMENTALS

Fundamental OO Characteristics (4 Pillars)

1. Encapsulation: Bundling data (attributes) and methods (operations) that operate on the data into a single unit (class). Hiding internal state using access modifiers (private, public). Example: A BankAccount class with private balance and public deposit(), withdraw() methods.

2. Inheritance: Mechanism where a new class (subclass/child) acquires properties and behaviors of an existing class (superclass/parent). Promotes code reuse and establishes a hierarchy. Example: Vehicle -> Car, Truck.

3. Polymorphism: Ability of different classes to respond to the same message (method call) in different ways.

   • Compile-time (Overloading): Multiple methods with same name but different parameters in same class.

   • Runtime (Overriding): Subclass provides a specific implementation of a method defined in its superclass.

4. Abstraction: Hiding complex implementation details and showing only essential features. Defining abstract classes/interfaces that specify what a class does, not how. Example: A Shape interface with area() method; Circle and Rectangle implement it differently.

OO Approach vs. Procedural Programming

How OO Approach Manages Complexity in Large Systems

• Decomposition: Breaks a complex system into smaller, manageable objects.

• Abstraction: Hides implementation details behind well-defined interfaces.

• Encapsulation: Protects object integrity; localizes changes.

• Inheritance & Polymorphism: Promotes code reuse and extensibility without modifying existing code (Open/Closed Principle).

X. UNIFIED MODELING LANGUAGE (UML) & OBJECT-ORIENTED DESIGN

Primary Goals of UML

1. To provide a standard notation for visualizing, specifying, constructing, and documenting software artifacts.

2. To be general-purpose and applicable to various domains and processes.

3. To be language-independent (though often used with Java, C++, etc.).

Class Diagrams: Terms and Concepts

A static structure diagram showing system's classes, attributes, operations, and relationships.

• Class: Rectangle with three compartments: Name, Attributes (with visibility + public, - private, # protected), Operations (methods).

• Relationships:

  • Association: Structural relationship between classes (e.g., Professor teaches Course). Shown as a solid line.

  • Aggregation: A special form of association representing a whole-part relationship where the part can exist independently. Hollow diamond on the whole side.

  • Composition: Strong form of aggregation where the part cannot exist independently of the whole. Filled diamond on the whole side.

  • Generalization (Inheritance): "Is-a" relationship. Solid line with a hollow arrowhead pointing to the superclass.

  • Dependency: A using relationship where a change in one element (client) may affect another (supplier). Dashed arrow from client to supplier.

[!TIP] Exam Focus: Be able to draw a class diagram for a given scenario (e.g., University with Professor, Course, Student). Distinguish clearly between Aggregation vs. Composition.

Models Available in OO Languages & Their Relationships

UML 2.x defines 14 diagram types, key ones:

1. Use Case Diagram: Captures functional requirements (actors, use cases).

2. Class Diagram: Static structure (as above).

3. Sequence Diagram: Shows interactions between objects over time (lifelines, messages).

4. State Machine Diagram: Models state changes of a single object in response to events.

5. Activity Diagram: Models workflow or business process (like a flowchart).

6. Component Diagram: Shows physical components (files, libraries) and their dependencies.

7. Deployment Diagram: Shows physical deployment of software artifacts on hardware nodes.

Inter-relationship: Models describe the system at different levels of abstraction and from different perspectives. Use case diagrams drive the design (class, sequence diagrams). Class diagrams define the static structure. Sequence/activity/state diagrams define dynamic behavior. Component/deployment diagrams define physical architecture.

Object-Oriented Design (OOD)

• Definition: The process of creating an object-oriented model of a system that meets the specified requirements. It defines the logical structure (classes, relationships) and dynamic behavior (interactions) before implementation.

• Process: Typically involves: Identifying objects & classes -> Defining relationships (assoc, inher) -> Defining attributes & operations -> Establishing interfaces -> Iterative refinement.

XI. OBJECT-ORIENTED IMPLEMENTATION & DATABASES

Translating OOD into Implementation

1. Mapping Classes to Code: Each class becomes a class/struct in the implementation language (e.g., Java, C++).

2. Mapping Attributes: Class attributes become member variables/fields with appropriate data types.

3. Mapping Operations: Class operations become member functions/methods.

4. Mapping Relationships:

   • Association: Implemented as a reference/pointer to another object (or a collection for multiplicities >1).

   • Inheritance: Implemented using language-specific keywords (extends in Java, : in C++).

   • Composition/Aggregation: Implemented as member object references (composition often by value, aggregation by reference).

5. Frameworks & Patterns: Use established OO frameworks (e.g., Spring) and design patterns (e.g., Singleton, Observer) to implement common structures.

OO Languages vs. Procedural/Functional Languages

Query Languages for Object-Oriented Databases (OODB)

• Concept: Extend SQL-like syntax to handle complex objects, nested structures, inheritance, and methods.

• Example: OQL (Object Query Language): Standardized query language for OODBs.

  • Syntax resembles SQL but navigates object structures.

  • Supports path expressions: SELECT name FROM Person WHERE address.city = "Bhopal"

  • Can invoke methods: SELECT s.enrollCourses() FROM Student s

Comparison: OODB Query Language vs. SQL (Relational)

[!TIP] Key Difference: OODB queries navigate the object network; SQL joins relational tables.