IT Business & Disaster Recovery Planning (CY-604 (A)) - Unit 5 Short Notes

UNIT 5: IT Business & Disaster Recovery Planning - Short Notes

1. Data Warehouse Fundamentals

1.1 Definition and Need for Data Warehouse

A Data Warehouse (DW) is a subject-oriented, integrated, time-variant, and non-volatile collection of data used to support management's decision-making process.

Need:

• To support strategic decision making (long-term) vs. operational systems (short-term).

• To provide a consolidated view of organizational data from disparate sources.

• To enable historical data analysis and trend identification.

• To separate analytical processing from transactional databases, improving performance.

1.2 Characteristics of Data Warehouse

1.3 Data Warehouse Architecture and Components

Typical Architecture:

1. Data Sources: Operational databases, external data.

2. Staging Area: Temporary storage for data cleaning, transformation, and integration.

3. Data Warehouse Storage: Central repository (often relational DB) storing integrated, historical data.

4. Metadata: "Data about data" (definitions, schemas, transformation rules).

5. Access Tools: OLAP engines, reporting tools, data mining tools, client APIs.

> [!TIP] Common Exam Question: "Draw and explain data warehouse architecture." Be prepared to describe the flow: Source → Staging → DW → Access Tools, emphasizing the role of ETL and metadata.

1.4 Data Warehouse Implementation Techniques

2. Data Warehouse Schema Designs

2.1 Star Schema

• Structure: One central fact table connected to multiple denormalized dimension tables.

• Fact Table: Contains foreign keys to dimensions and measures (numerical facts like sales_amount).

• Dimension Tables: Contain descriptive attributes (e.g., dim_product(product_id, name, category, brand)).

• Advantage: Simple, optimized for query performance (fewer joins).

• Disadvantage: Data redundancy in dimensions.

2.2 Snowflake Schema

• Structure: Normalized version of star schema. Dimension tables are decomposed into multiple related tables.

• Example: dim_product → dim_product (product_id, name) + dim_category (category_id, category_name).

• Advantage: Reduces redundancy, saves storage.

• Disadvantage: More complex queries (more joins), potentially slower.

2.3 Galaxy Schema (Multidimensional Databases)

• Also called Fact Constellation Schema.

• Structure: Multiple fact tables sharing common dimension tables.

• Use Case: Complex business processes with multiple perspectives (e.g., Sales and Inventory facts sharing dim_time, dim_product).

• Advantage: Models complex scenarios efficiently.

• Disadvantage: Design and maintenance complexity.

2.4 Vertical Partitioning

• Definition: Splitting a table by columns rather than rows.

• How it's done:

  1. Group frequently accessed columns together.

  2. Group infrequently accessed or large columns (e.g., TEXT, BLOB) separately.

• Goal: Improve I/O performance by reading only necessary columns.

• Example: A customer table partitioned into customer_core (id, name, email) and customer_details (id, bio, photo).

> [!TIP] Exam Focus: Compare Star vs. Snowflake (denormalization vs. normalization). Galaxy is for multiple facts. Vertical partitioning is about columnar storage optimization.

3. OLAP (Online Analytical Processing)

3.1 OLAP vs. OLTP

3.2 Types of OLAP

3.3 ROLAP Concept with Diagram

Concept: ROLAP uses relational databases as the backend storage. Multidimensional views (cubes) are mapped to relational tables (fact and dimension tables). Queries are translated into SQL.

DiagramROLAP ARCHITECTURE

[Client Application] → [OLAP Server] → [Relational Database (Star Schema)]

          (MDX Query)       (SQL Generation)

• OLAP Server maps logical cube operations to physical SQL on the star schema.

• Advantage: Leverages mature, scalable RDBMS technology.

• Disadvantage: Query performance can be slower than MOLAP for complex aggregations.

3.4 Need and Role of MOLAP Server

Need: To achieve sub-second response times for complex analytical queries on large datasets. Role:

1. Pre-aggregation: Stores pre-computed summary data (aggregates) at all levels.

2. Multidimensional Storage: Uses array-based structures for direct access.

3. Optimized for Analysis: Efficiently handles slice-and-dice, drill-down, roll-up operations.

4. Provides OLAP Engine: Implements MDX (Multidimensional Expressions) query language.

3.5 OLAP Servers Overview

• Function: Middleware between client tools and data storage. Implements OLAP operations.

• Key Capabilities:

  • Cube Management: Creation, storage, and management of multidimensional cubes.

  • Query Processing: Translates MDX to native storage access (SQL for ROLAP, array access for MOLAP).

  • Aggregation Management: Pre-computes and manages aggregate tables/arrays.

  • Security & Metadata: Manages access control and cube metadata.

3.6 Data Cubes Computation Process

Goal: Pre-compute all possible aggregate queries (GROUP BY on all dimension combinations). Naive Approach: For n dimensions, compute $$\displaystyle 2^n $$ group-by queries (including base table). Computationally expensive. Efficient Techniques:

1. Caching/Indexing: Store computed aggregates and index them.

2. Partial Computation: Compute only frequently used aggregates (e.g., using a lattice).

3. Shared Computation: Reuse intermediate results (e.g., computing (A,B) and (A,C) can help compute (A,B,C)).

4. Shell-based: Use a shell fragment to represent shared computations.

> [!TIP] Know the trade-off: Pre-computation (MOLAP) vs. On-the-fly computation (ROLAP).

4. ETL (Extract, Transform, Load) Processes

4.1 Data Cleaning Techniques

• Missing Value Handling:

  • Ignore tuple (if few).

  • Fill with global constant, mean/median/mode.

  • Use regression/classification to predict.

• Noise Smoothing: Binning (sorting, partitioning), regression, clustering.

• Outlier Detection: Statistical methods (z-score, IQR), clustering, box plots.

• Duplicate Detection: Record linkage, similarity measures (e.g., Jaccard, edit distance).

• Consistency Checking: Enforce integrity constraints (e.g., age > 0).

4.2 Data Transformation Methods

4.3 Data Integration

• Schema Integration:

  • Schema Matching: Identify equivalent fields (e.g., cust_id vs customer_id).

  • Schema Mapping: Define transformation rules.

• Redundancy Detection:

  • Correlation Analysis: For numerical attributes (Pearson's $r$).

  • Chi-Square Test: For categorical attributes.

• Conflict Resolution: Handle naming, structure, and data value conflicts.

4.4 Data Preprocessing for Warehousing

• Data Sourcing: Identify and connect to all relevant sources.

• Data Extraction: Pull data from sources (full/incremental).

• Data Transport: Move to staging area (consider network, volume).

• Staging Area Operations: Clean, transform, integrate, and validate.

• Load to DW: Load processed data into fact/dimension tables (full/refresh/incremental).

5. Data Mining Overview

5.1 Definition and Scope of Data Mining

Definition: The process of discovering interesting, non-trivial, previously unknown, and potentially useful patterns from large datasets. Scope: Includes tasks like classification, clustering, association, prediction, anomaly detection. It is a core step in the KDD process.

5.2 Pros and Cons of Data Mining

5.3 KDD Process and Role of Data Mining Engine

KDD (Knowledge Discovery in Databases) Process:

1. Selection: Target data from sources.

2. Preprocessing: Cleaning, integration, transformation.

3. Transformation: Convert to format suitable for mining (e.g., normalization).

4. Data Mining: Apply algorithms to find patterns (this is the core engine step).

5. Interpretation/Evaluation: Evaluate patterns for validity, usefulness.

6. Knowledge Presentation: Visualize results (reports, charts).

Role of Data Mining Engine: The algorithmic core in step 4. It takes preprocessed data and applies specific techniques (e.g., Apriori, decision trees) to generate candidate patterns.

5.4 Data Mining Task Primitives (Task Specification)

A task primitive is a user-specified input to define a data mining task. The five primitives are:

1. Task-Relevant Data: Subset of database (attributes, tuples).

2. Background Knowledge: Domain knowledge, constraints (e.g., taxonomies).

3. Interestingness Measures: Metrics to evaluate patterns (e.g., support, confidence, accuracy).

4. Pattern Types: The kind of pattern sought (e.g., association, classification model, cluster).

5. Visualization/Representation: How results should be presented.

5.5 Types of Data for Data Mining Applications

6. Association Rule Mining

6.1 Basic Concepts and Measures

• Association Rule: $$\displaystyle X \rightarrow Y $$ (where $$\displaystyle X \cap Y = \emptyset $$). "If X is purchased, then Y is purchased."

• Support ($\sigma$): Fraction of transactions containing $X \cup Y$.

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

• Confidence ($\gamma$): Conditional probability of Y given X.

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

• Frequent Itemset: An itemset with support ≥ min_sup.

• Strong Rule: A rule with confidence ≥ min_conf and support ≥ min_sup.

6.2 Boolean Association Rule Mining

• Input: Categorical/binary attributes. Each transaction is a set of attribute=value pairs.

• Goal: Find rules like (age=Youth) ∧ (income=High) → (buys_computer=Yes).

• Approach: Convert each categorical attribute into binary items (one-hot encoding). Then apply standard frequent itemset mining (Apriori, FP-growth).

6.3 Apriori Algorithm (with example)

Key Principle (Apriori Property): All subsets of a frequent itemset must be frequent. (If {A,B} is frequent, then {A} and {B} must be frequent).

Steps:

1. Find frequent 1-itemsets (L₁) by scanning DB, counting support.

2. For k = 2, 3, ... until Lₖ is empty:

   a. Candidate Generation: Generate Cₖ (candidate k-itemsets) by joining Lₖ₋₁ with itself.

   b. Prune: Remove candidates with any (k-1)-subset not in Lₖ₋₁.

   c. Counting: Scan DB, count support of candidates in Cₖ.

   d. Frequent Itemsets: Lₖ = {candidates in Cₖ with support ≥ min_sup}.

3. Generate Rules: For each frequent itemset l, generate all non-empty subsets. For each subset s, rule $$\displaystyle s \rightarrow (l-s) $$ if confidence ≥ min_conf.

Example: min_sup=2, min_conf=70%.

Transactions:

1. {A,B,C}

2. {A,C}

3. {A,B,D}

4. {B,C,E}

• L₁: {A:3, B:3, C:3, D:1, E:1} → Frequent: {A,B,C}

• C₂: {A,B}, {A,C}, {B,C}

• L₂: {A,B}:2, {A,C}:3, {B,C}:2 → All frequent.

• C₃: {A,B,C} (from joining {A,B} & {A,C} & {B,C})

• L₃: {A,B,C}:2 → Frequent.

• Rules from {A,B,C}:

  • A∧B → C: conf = 2/2 = 100% (strong)

  • A∧C → B: conf = 2/3 ≈ 67% (not strong)

  • B∧C → A: conf = 2/2 = 100% (strong)

6.4 FP-growth Algorithm (with example)

Idea: Avoid candidate generation and multiple scans. Use a compact FP-tree (Frequent Pattern tree).

Steps:

1. Scan DB once to find frequent 1-itemsets (L₁). Order them by descending frequency.

2. Build FP-tree:

   • Start with empty root.

   • For each transaction, sort frequent items in L₁ order, insert into tree (share prefixes).

   • Nodes store item name, count, link to next same item.

3. Mine FP-tree recursively:

   • For each item in header table (starting from least frequent):

     a. Construct conditional pattern base (prefix paths to that item).

     b. Build conditional FP-tree from base.

     c. If conditional FP-tree has single path, generate patterns directly; else, recursively mine.

   • Combine suffix item with patterns from conditional tree.

Example (simplified):

Transactions (min_sup=3):

1. {A,B,C}

2. {A,B,C,D}

3. {A,B,D}

4. {A,C,D}

5. {B,C,D}

• L₁: A:4, B:3, C:4, D:4 → Order: C, A, D, B (or similar freq order).

• FP-tree built with ordered items.

• Mining starts from B (least frequent in header). Conditional pattern base for B: paths ending with B. Build conditional tree, find frequent patterns like {A,B}, {C,B}, etc.

6.5 Techniques to Improve Apriori Efficiency

1. Hashing: Use hash table to prune candidates during candidate generation (hash-based Apriori).

2. Transaction Reduction: Remove transactions that don't contain any frequent items (after L₁).

3. Partitioning: Split DB into partitions. Find local frequent itemsets, then global (must be frequent in at least one partition).

4. Sampling: Run Apriori on a random sample; verify candidates on full DB.

5. Dynamic Item Set Counting: Add candidates dynamically during a single scan (DIC algorithm).

6. Using FP-tree: FP-growth itself avoids candidate generation.

6.6 Time Series Mining Association Rules

• Data: Sequence of values over time (e.g., stock prices, sensor readings).

• Challenges: Temporal ordering, high dimensionality, trends, seasonality.

• Approach:

  1. Discretization: Convert time series to symbolic sequences (e.g., SAX - Symbolic Aggregate approXimation).

  2. Window-Based: Extract subsequences using sliding windows.

  3. Apply Standard ARM: Mine frequent itemsets (symbols or words) from these sequences.

  4. Rule Form: Patterns like "After a 'peak' followed by 'dip', a 'rise' often follows."

• Applications: Stock movement patterns, medical diagnosis (EEG), equipment failure prediction.

7. Classification

7.1 Learning Phase in Classification

Definition: The phase where a classifier (model) is built from a training dataset (labeled tuples). Process:

1. Training Set: Set of instances $$\displaystyle \{(x_i, y_i)\} $$ where $$\displaystyle x_i $$ is feature vector, $$\displaystyle y_i $$ is class label.

2. Model Induction: Algorithm learns a mapping $$\displaystyle f: X \rightarrow Y $$ by identifying patterns/relationships between features and class.

3. Output: A classification model (e.g., decision tree, rule set, Bayesian network).

4. Goal: Model should generalize well to unseen data (avoid overfitting).

7.2 Decision Tree Induction Algorithm

Goal: Build a tree where internal nodes are tests on attributes, branches are outcomes, leaves are class labels. Popular Algorithms: ID3 (C4.5), CART. Key Steps (ID3 example):

1. Start with all training instances at root.

2. Select Best Attribute: Use information gain (based on entropy).

   • Entropy($S$): $$\displaystyle -\sum_{i=1}^{c} p_i \log_2 p_i $$ (purity measure).

   • Gain($S, A$): $$\displaystyle \text{Entropy}(S) - \sum_{v \in \text{values}(A)} \frac{|S_v|}{|S|} \text{Entropy}(S_v) $$.

3. Split dataset on chosen attribute.

4. Recurse on each split subset until:

   • All instances in node belong to same class (pure).

   • No more attributes to split.

   • No instances left (use majority class).

5. Pruning (post-pruning) to avoid overfitting.

Example: Predict buys_computer from age, income, student, credit_rating.

7.3 Rule-Based Classification Algorithms

Approach: Learn a set of IF-THEN rules from data. Methods:

1. Direct Rule Extraction: From decision trees (each root-to-leaf path → rule).

2. Sequential Covering (Separate-and-Conquer):

   • Learn-One-Rule: Start with empty rule, greedily add conditions (conjunctions) to maximize coverage/precision.

   • Remove Covered: Remove instances covered by the rule.

   • Repeat until all instances covered or stopping criterion.

   • Algorithms: RIPPER, CN2.

3. Association Rule Mining for Classification (CBA):

   • Generate class association rules (CARs) with high confidence.

   • Build classifier from CARs.

Rule Quality: Coverage (fraction of training data covered), Accuracy (fraction of covered instances correctly classified).

7.4 Bayesian Classification

Naïve Bayes Classifier:

• Based on Bayes' Theorem: $$\displaystyle P(Y|X) = \frac{P(X|Y) P(Y)}{P(X)} $$.

• Assumption: Conditional Independence of features given the class.

$$P(X|Y) = \prod_{i=1}^{n} P(x_i|Y)$$

• Classification: For a new instance $$\displaystyle x = (x_1, ..., x_n) $$, compute $$\displaystyle P(Y=y|X=x) \propto P(Y=y) \prod_{i} P(x_i|Y=y) $$. Predict class with highest posterior probability.

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

• Disadvantages: Independence assumption often violated; zero-probability problem (handled by Laplace smoothing).

7.5 Probabilistic Classifiers

• Definition: Classifiers that output probability estimates for class membership, not just a class label.

• Examples:

  • Naïve Bayes: Directly outputs $P(Y|X)$.

  • Logistic Regression: Models $$\displaystyle P(Y=1|X) = \frac{1}{1+e^{-(\beta_0 + \beta^T X)}} $$.

  • Bayesian Networks: Graphical models representing conditional dependencies; inference yields probabilities.

• Use: When you need confidence scores, for cost-sensitive decisions, or as input to ensemble methods.

7.6 Classifier Accuracy Verification Process

Goal: Estimate how well the model will perform on unseen data. Methods:

1. Holdout Method:

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

   • Train on training, evaluate on test.

   • Accuracy = (correctly classified test instances) / (total test instances).

2. Cross-Validation (k-fold):

   • Partition data into k equal-sized folds.

   • For i=1 to k: Train on all folds except i, test on fold i.

   • Average accuracy over k runs. (Common: 10-fold CV).

3. Bootstrap:

   • Sample n instances with replacement from original data (size n) to form training set.

   • Test on instances not in bootstrap sample (~36.8%).

   • Repeat many times, average accuracy. Metrics: Accuracy, Precision, Recall, F1-score, Confusion Matrix.

> [!TIP] Know the difference between training accuracy (overfits) and test accuracy (generalization). Cross-validation is the most robust common method.

8. Clustering

8.1 Definition and Clustering Methods Overview

Definition: The task of grouping a set of objects such that objects in the same group (cluster) are more similar to each other than to those in other groups. Unsupervised learning (no class labels). Main Categories:

• Partitioning: Divide objects into k clusters (e.g., k-means).

• Hierarchical: Create a tree of clusters (e.g., AGNES, DIANA).

• Density-Based: Connect dense regions (e.g., DBSCAN).

• Grid-Based: Quantize space into grids (e.g., STING).

• Model-Based: Assume data fits a model (e.g., Gaussian Mixture Models).

8.2 Hierarchical Clustering: Top-down vs. Bottom-up

8.3 Other Clustering Methods

• Partitioning (k-means):

  • Input: k (number of clusters).

  • Steps: Initialize centroids → Assign points to nearest centroid → Recompute centroids → Repeat until convergence.

  • Distance: Typically Euclidean.

  • Pros: Simple, fast for large datasets.

  • Cons: Needs k, sensitive to outliers, assumes spherical clusters.

• Density-Based (DBSCAN):

  • Key Parameters: eps (neighborhood radius), MinPts (minimum points in neighborhood).

  • Concepts: Core point (≥MinPts in eps-neighborhood), border point (in neighborhood of core), noise.

  • Process: Start with arbitrary point, find all density-reachable points → form cluster. Repeat for unvisited points.

  • Pros: Finds arbitrarily shaped clusters, robust to outliers, no need for k.

  • Cons: Sensitive to eps/MinPts, struggles with varying densities.

9. Specialized Data Mining Applications

9.1 Web Usage Mining

• Goal: Discover patterns from web log data (server logs, browser logs, proxies).

• Data Sources: Server access logs, user sessions, cookies.

• Process:

  1. Preprocessing: Data cleaning, user identification, session identification, path completion.

  2. Pattern Discovery: Apply clustering, association, sequential pattern mining, classification.

• Applications:

  • Personalization: Recommend products/content.

  • Site Redesign: Improve navigation, structure.

  • Business Intelligence: Understand customer behavior, marketing effectiveness.

  • Anomaly Detection: Identify fraud, security threats.

9.2 Text Mining

• Goal: Discover patterns, trends, and knowledge from unstructured text.

• Key Steps:

  1. Text Preprocessing: Tokenization, stop-word removal, stemming/lemmatization.

  2. Feature Extraction: Convert text to numerical vectors (Bag-of-Words, TF-IDF).

  3. Mining Tasks:

     • Text Categorization/Classification: (e.g., spam detection).

     • Clustering: Group similar documents.

     • Topic Modeling: (e.g., LDA - Latent Dirichlet Allocation).

     • Sentiment Analysis: Positive/negative/neutral opinion mining.

     • Information Extraction: Named entity recognition, relation extraction.

• Challenges: High dimensionality, synonymy, polysemy.

9.3 Spatial Mining

• Goal: Discover patterns in spatial data (data with geographic/location attributes).

• Spatial Data Types: Points, lines, polygons, raster images.

• Spatial Relationships: Topological (adjacent, contains), directional (north of), distance-based.

• Tasks:

  • Spatial Classification: Use spatial attributes (e.g., predict land use type).

  • Spatial Clustering: (e.g., DBSCAN for geographic hotspots).

  • Spatial Association Rules: Rules with spatial predicates (e.g., near, intersects).

  • Spatial Trend Detection: How attribute changes over space (e.g., pollution gradient).

• Applications: GIS, urban planning, environmental monitoring, location-based services.

9.4 Data Prediction

• Definition: Using historical data to forecast future or unknown values.

• Primary Techniques:

  1. Regression: Predict continuous value.

     • Linear Regression: $$\displaystyle y = \beta_0 + \beta_1 x_1 + ... + \epsilon $$.

     • Polynomial, Logistic (for classification).

  2. Time Series Forecasting: Predict future points in a sequence.

     • Models: ARIMA, Exponential Smoothing, LSTM (deep learning).

     • Components: Trend, Seasonality, Cyclical, Irregular.

  3. Classification: Predict categorical class label (covered in Section 7).

• Process: Historical data → Model building (train) → Forecast/predict → Evaluate accuracy (MSE, MAE, RMSE).

• Applications: Sales forecasting, stock prices, demand planning, risk assessment.

10. Object-Oriented Concepts and Databases

10.1 Fundamental OO Characteristics

10.2 Object-Oriented Approach vs. Procedural Programming

10.3 Managing Complexity in Large Systems with OO

• Modularity: System decomposed into objects with well-defined responsibilities (high cohesion, low coupling).

• Abstraction: Hide implementation details behind interfaces; developers work at higher level.

• Encapsulation: Protects object integrity; changes within an object don't ripple through system.

• Inheritance & Reuse: Extend existing classes rather than rewrite; promotes consistent design.

• Polymorphism: Write generic code that works with objects of different types (via superclass/interface references).

• Design Patterns: Reusable solutions to common design problems (e.g., Singleton, Observer, Factory).

10.4 OO Models and UML Diagrams (Class Diagram)

UML (Unified Modeling Language): Standard notation for visualizing, specifying, constructing, documenting OO systems. Key Diagrams:

• Class Diagram: Static structure of system. Shows:

  • Classes: Rectangles with name, attributes, operations.

  • Relationships:

    • Association: Structural link (e.g., Customer places Order). Can have multiplicity (1, *, 0..1).

    • Aggregation: "Has-a" (whole-part), hollow diamond on whole side (e.g., Department has Professors).

    • Composition: Strong ownership, filled diamond (e.g., Car has Engine; engine lifecycle tied to car).

    • Inheritance (Generalization): Solid line with hollow arrowhead from subclass to superclass.

    • Dependency: Using relationship, dashed arrow (e.g., Report depends on Database).

• Other Diagrams: Sequence (interaction over time), Use Case (functionality), State Machine, Activity.

10.5 Object-Oriented Design (OOD) and Implementation Process

1. Object-Oriented Analysis (OOA): Understand problem domain. Identify objects, classes, relationships, use cases. Output: Analysis Model (conceptual).

2. Object-Oriented Design (OOD): Design solution. Refine classes, define attributes, methods, interfaces, architectural patterns. Create design models (class diagrams, sequence diagrams). Focus on how to build.

3. Implementation (Coding): Translate design into source code in OO language. Create classes, implement methods.

4. Testing: Unit testing (individual classes/objects), integration testing (object interactions), system testing.

5. Deployment & Maintenance: Deploy system; maintain/evolve by adding new objects/classes.

10.6 Query Languages for Object-Oriented Databases vs. SQL

> [!TIP] OODB Key Advantage: Seamlessly models complex real-world entities (with identity, complex relationships, behavior) without impedance mismatch. SQL requires joins and foreign keys.