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

UNIT 1: Foundations of Data Management & System Design

I. DATA WAREHOUSING FUNDAMENTALS

Data Cleaning

• Definition: The process of detecting and correcting (or removing) corrupt, inaccurate, or irrelevant data from a dataset. It is a crucial first step in the KDD (Knowledge Discovery in Databases) process to ensure data quality.

• Necessity: "Garbage in, garbage out." Analysis on dirty data yields misleading results.

• Techniques:

  • Handling Missing Data: Delete tuples/attributes, fill manually, impute using mean/median/mode, or predict using algorithms.

  • Handling Noisy Data: Binning (smoothing), regression, clustering, or outlier detection/removal.

  • Handling Inconsistent Data: Check constraints, use domain knowledge, or resolve conflicts (e.g., "M" vs "Male").

[!TIP] Exam Focus: Be ready to define data cleaning and list at least two techniques for each data problem type (missing, noisy, inconsistent).

Data Transformation

• Definition: The process of converting data from its raw source format into a suitable format for mining and warehousing.

• Methods:

  | Method | Purpose | Example | | :--- | :--- | :--- | | Smoothing | Remove noise | Binning, regression | | Attribute Construction | Create new attributes | Area = Length * Width | | Aggregation | Summarize data | Daily sales → Monthly sales | | Normalization | Scale to a small range | Min-Max, Z-score | | Discretization | Convert continuous to categorical | Age → {Youth, Adult, Senior} |

Data Warehouse (DW)

• Definition: A subject-oriented, integrated, time-variant, and non-volatile collection of data used to support management's decision-making process.

• Core Characteristics (In Detail):

  1. Subject-Oriented: Organized around key subjects (e.g., Customer, Product, Sales), not around applications.

  2. Integrated: Consolidates data from multiple, heterogeneous sources (e.g., relational DBs, flat files). Resolves naming, encoding, and format inconsistencies.

  3. Time-Variant: Data is stored with a time context. Historical data is maintained and not updated/deleted.

  4. Non-Volatile: Data is stable, read-only, and not updated by routine transactions. New data is appended.

• Architecture & Components:

  
  graph LR
  
  A[Data Sources] --> B[ETL Process];
  
  B --> C[Data Warehouse Storage];
  
  C --> D[Front-End Tools];
  
  D --> E[Users];
  
  

  • Data Sources: Operational databases, external data.

  • ETL (Extract, Transform, Load): The core process. Extracts data from sources, transforms it (cleaning, integrating), and loads it into the DW.

  • DW Storage: The repository, often using multidimensional models (star/snowflake schemas).

  • Front-End Tools: OLAP tools, data mining tools, reporting tools, dashboards.

DW Implementation Techniques

• Top-Down (Inmon): Build a comprehensive, enterprise-wide DW first (centralized, normalized), then create data marts from it. Pros: Consistent, integrated view. Cons: High initial cost, long setup time.

• Bottom-Up (Kimball): Build independent data marts first (for specific business processes), then integrate them into a DW. Pros: Faster ROI, lower initial cost. Cons: Potential for data inconsistency, integration challenges later.

• Hybrid: Combines elements of both. A central DW provides core integrated data, while departments build localized data marts.

Multidimensional Data Modeling & Schemas

• Star Schema: Simplest and most common. Consists of a single central fact table (with foreign keys to dimensions and quantitative measures) surrounded by denormalized dimension tables.

  • Fact Table: Contains metrics (e.g., Sales_Amount, Quantity).

  • Dimension Tables: Contain descriptive attributes (e.g., Product.Name, Time.Day).

  • Example: Sales(Fact) linked to Product(Dim), Store(Dim), Time(Dim).

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

  • Example: Product(Dim) → Product_Subcategory(Dim) → Product_Category(Dim).

• Galaxy Schema / Fact Constellation: A collection of multiple fact tables that share common dimension tables. Used for complex, enterprise-wide subjects.

  • Example: A Sales fact table and a Inventory fact table both share the Product and Time dimensions.

• Vertical Partitioning: Splitting a table by columns (attributes) into multiple tables.

  • Methods:

    1. Attribute Partitioning: Group frequently accessed attributes together.

    2. Table Splitting: Separate static (slow-changing) attributes from dynamic (fast-changing) ones.

II. ONLINE ANALYTICAL PROCESSING (OLAP)

OLAP vs. OLTP

OLAP Operations

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

• Drill-down (Roll-down): Navigation down the hierarchy (e.g., Year → Quarter → Month → Day).

• Slice-and-Dice: Slice: Select a single dimension value (e.g., Time = "2024"). Dice: Select a sub-cube by specifying ranges on multiple dimensions.

• Pivot (Rotate): Reorient the cube to view data from a different perspective (e.g., swapping rows and columns).

OLAP Architectures & Servers

• MOLAP (Multidimensional OLAP):

  • Need: For maximum query performance on dense, stable data.

  • Explanation: Uses a proprietary multidimensional array storage (not relational). Data is pre-aggregated and stored in an optimized cube format. Extremely fast for slice-and-dice and drill-down.

  • Diagram Concept: [Client] → [OLAP Server (MOLAP)] → [Multidimensional Storage]

• ROLAP (Relational OLAP):

  • Concept: Uses relational DBMS (RDBMS) and SQL to store and manage multidimensional data. Fact and dimension tables are stored as relational tables. Aggregations are computed on-the-fly or stored as summary tables.

  • Diagram Concept: [Client] → [OLAP Server (ROLAP)] → [Relational DB (Star Schema)]

  • Pros: Handles large, sparse data; leverages mature RDBMS technology. Cons: Slower than MOLAP for complex queries.

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

• OLAP Server Types: The server is the middleware between the client tools and the database. It understands SQL and MDX (Multidimensional Expressions) and manages the cube operations.

Data Cube Computation

• Process: Pre-computing and storing all possible aggregate values (group-bys) for a data cube to enable fast query response.

• Methods for Efficient Computation:

  1. Multi-way Array Aggregation: For dense cubes, computes aggregates by traversing the multidimensional array in a specific order to minimize recomputation.

  2. BUC (Bottom-Up Cube): Computes cubes by partitioning data and computing aggregates in a bottom-up (from all to none) order, allowing early pruning.

  3. Star-Cubing: Integrates iceberg cube computation with Apriori-like pruning. Computes only iceberg cubes (cubes where measure meets a minimum threshold).

  4. Using Indexes & Materialized Views: In ROLAP, creating indexes on dimension tables and materializing common aggregate views.

III. DATA MINING OVERVIEW

Definition and Scope

• Definition: The process of discovering interesting patterns and knowledge from large amounts of data. The data can be stored in databases, data warehouses, or other repositories.

• Pros:

  • Automated discovery of hidden patterns.

  • Prediction of future trends and behaviors.

  • Improved decision-making.

• Cons:

  • Can be expensive and complex.

  • Risk of finding spurious patterns (false discoveries).

  • Privacy and ethical concerns.

KDD Process (Knowledge Discovery in Databases)

A high-level process of which data mining is a step.

1. Selection: Integrate and select the target dataset from the data warehouse or other sources.

2. Preprocessing: Clean the data (handle missing values, noise, outliers).

3. Transformation: Convert data into suitable formats (normalization, aggregation, discretization).

4. Data Mining: Apply core algorithms to discover patterns (classification, clustering, association).

5. Interpretation/Evaluation: Interpret mined patterns, validate their usefulness, and transform them into knowledge.

Role of Data Mining Engine: The core algorithmic module in step 4. It executes the chosen data mining task (e.g., runs the Apriori algorithm).

Data Mining Task Primitives

1. Task-relevant data: The subset of the database to be analyzed.

2. Background knowledge: Domain knowledge, constraints, or ontologies used to guide the search.

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

4. Representation of results: Desired form of output (e.g., rules, trees, clusters).

5. Visualization: Tools for presenting mined patterns.

Types of Data for Mining

• Relational: Standard database tables.

• Transactional: Databases of transactions (e.g., market baskets).

• Data Warehouse: Integrated, subject-oriented repositories.

• Advanced:

  • Stream: Continuous, rapid data streams (e.g., sensor data).

  • Time-Series: Data points indexed in time order.

  • Spatial: Data with spatial/geographic attributes.

  • Text: Unstructured text documents.

  • Web: Data from the web (hyperlinks, content, usage logs).

  • Graph: Data represented as nodes and edges (social networks).

IV. ASSOCIATION RULE MINING

Concept and Boolean Association Rules

• Concept: Discovering interesting relationships (associations) between items in large datasets. Classic example: Market Basket Analysis.

• Boolean Association Rules: Rules where each item appears as a binary presence/absence (e.g., {Bread, Milk} → {Butter}).

• Key Measures:

  • Support (supp(X)): Fraction of transactions containing itemset X.

$$supp(X) = \frac{| \{ t \in T : X \subseteq t \} |}{|T|}$$

*   **Confidence (conf(X→Y)):** Conditional probability that Y is purchased given X is purchased.

$$conf(X \rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)}$$

*   **Interestingness (Lift):** Measures correlation. `Lift > 1` indicates positive correlation.

$$lift(X \rightarrow Y) = \frac{conf(X \rightarrow Y)}{supp(Y)}$$

Apriori Algorithm

• Core Principle: "All non-empty subsets of a frequent itemset must also be frequent." (Anti-monotone property).

• Steps:

  1. Find Frequent Itemsets: Use iterative, level-wise search.

     • k=1: Scan DB to find frequent 1-itemsets (L1).

     • k>1: Generate candidate Ck from L(k-1) (join step). Prune candidates with infrequent subsets. Scan DB to count Ck and form Lk.

  2. Generate Rules: For each frequent itemset L (size ≥ 2), generate all non-empty subsets. For each subset A, form rule A → (L-A) if conf(A→L-A) ≥ min_conf.

• Example:

  • Min. Support = 50%, Min. Confidence = 70%.

  • DB: T1:{A,B,C}, T2:{A,B}, T3:{A,C}, T4:{B,C}.

  • L1: {A}(75%), {B}(75%), {C}(75%).

  • C2: {A,B}, {A,C}, {B,C}. All have support 50% → L2 = all three.

  • Rule from {A,B,C}: {A,B}→{C} (conf=50%/75%=66.7% < 70% → reject).

FP-Growth Algorithm

• Explanation: An efficient method that avoids candidate generation of Apriori.

• Process:

  1. Scan DB once to find frequent items (support ≥ min_sup). Build FP-tree:

     • Root is null.

     • Nodes are items with counts.

     • Paths represent transactions; prefix-sharing compresses tree.

     • Maintain item-header table with links to nodes of same item.

  2. Mine FP-tree recursively:

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

     • Build conditional FP-tree from this base.

     • Recursively mine the conditional tree to find frequent patterns ending with i.

• Example: For DB above, FP-tree has paths: A:3 → B:2, A:1 → C:1, B:1 → C:1. Mining from C yields pattern {A,B,C} directly.

Efficiency Improvements for Apriori

1. Hashing: Use hash tables during candidate generation to prune early.

2. Partitioning: Partition DB into chunks. Find local frequent itemsets, then global ones (any global frequent must be local frequent in some partition).

3. Transaction Reduction: Remove transactions that don't contain any frequent items.

4. Sampling: Work on a random sample; may miss some global frequent items but is fast.

5. Dynamic Item Counting: Add counts during database scan, not just at the end.

Specialized Association Mining

• Time Series Mining Association Rules: Mining associations in data where time is a critical dimension (e.g., stock prices, sensor readings). Requires handling temporal ordering, time gaps, and trends. Rules like "If stock X rises for 3 days, then stock Y rises the next day".

V. CLUSTERING ANALYSIS

Definition of Clustering

• 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. An unsupervised learning task (no pre-defined labels).

Major Clustering Methods

• Partitioning Methods:

  • Goal: Partition n objects into k clusters.

  • k-means:

    • Algorithm: (1) Choose k centroids randomly. (2) Assign each point to nearest centroid. (3) Recompute centroids as mean of assigned points. (4) Repeat (2)-(3) until convergence.

    • Pros: Simple, fast for large datasets. Cons: Sensitive to outliers, requires k, assumes spherical clusters.

  • k-medoids (PAM): Uses actual data points as cluster centers (medoids) instead of means. More robust to noise.

• Hierarchical Methods:

  • Agglomerative (Bottom-up): Start with each object as its own cluster. Repeatedly merge the two closest clusters until one cluster remains or a stopping condition.

  • Divisive (Top-down): Start with all objects in one cluster. Repeatedly split clusters until each object is alone or a stopping condition.

  • Key: Requires a linkage criterion (single, complete, average) to measure cluster distance.

• Density-Based (e.g., DBSCAN): Forms clusters based on density of points. Can find arbitrarily shaped clusters and handle noise (outliers).

• Grid-Based (e.g., STING): Quantizes the object space into a finite number of cells forming a grid structure. Clustering is performed on the grid cells.

• Model-Based: Assumes data is generated by a mixture of probability distributions (e.g., Gaussian Mixture Models). Uses statistical methods to find best-fit model.

VI. CLASSIFICATION & PREDICTION

Classification Process

1. Learning (Training) Phase: Build a model (classifier) by analyzing a set of training data where class labels are known.

2. Classification Phase: Use the trained model to predict the class label for new, unseen data.

Decision Tree Induction

• Algorithm (e.g., ID3, C4.5, CART): A greedy, top-down, recursive partitioning method.

  1. Start with all training data at the root.

  2. Select the best attribute to split on (using attribute selection measure).

  3. Create a branch for each value of that attribute.

  4. Partition data accordingly and repeat recursively for each branch until:

     • All instances in a branch belong to the same class (pure leaf).

     • No more attributes to split on.

     • No instances left.

• Attribute Selection Measures:

  • Entropy (H): Measures impurity/uncertainty of a set S.

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

    where `p_i` is proportion of class `i` in `S`.

*   **Information Gain (IG):** Reduction in entropy after splitting on attribute `A`.

$$IG(S,A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$

    ID3 uses IG. **C4.5** uses **Gain Ratio** (IG / intrinsic info) to correct IG's bias towards many-valued attributes.

*   **Gini Index (CART):** Measures impurity. Used for binary splits.

$$Gini(S) = 1 - \sum_{i=1}^{c} p_i^2$$

    Choose attribute that minimizes weighted sum of Gini of child nodes.

Rule-Based Classification

• If-Then Rules: IF <condition> THEN <class>.

• Rule Extraction from Decision Trees: One rule for each path from root to leaf. Conjunction of attribute tests along the path forms the IF condition; leaf class is the THEN part.

• Rule Induction Algorithms: Separate-and-conquer (e.g., RIPPER) directly induces rules without first building a tree.

Bayesian Classification

• Bayesian Theorem:

$$P(H|E) = \frac{P(E|H) \cdot P(H)}{P(E)}$$

Where `H` is hypothesis (class), `E` is evidence (attribute values).

• Naive Bayes Classifier:

  • Assumption: Conditional Independence – given the class, the values of attributes are independent.

  • Calculation: For a tuple X = (x1, x2, ..., xn), compute:

$$P(class_i | X) \propto P(class_i) \prod_{k=1}^{n} P(x_k | class_i)$$

*   Predict class with highest posterior probability.

*   *Pros:* Simple, fast, works well with high-dimensional data. *Cons:* Independence assumption often unrealistic.

Probabilistic Classifiers

• Concept: Classifiers that output a probability distribution over possible classes, not just a single label.

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

Classifier Evaluation

• Metrics (from Confusion Matrix):

  | Metric | Formula | Meaning | | :--- | :--- | :--- | | Accuracy | $$\displaystyle \frac{TP+TN}{Total} $$ | Overall correctness | | Precision | $$\displaystyle \frac{TP}{TP+FP} $$ | Of predicted positives, how many are correct? | | Recall (Sensitivity) | $$\displaystyle \frac{TP}{TP+FN} $$ | Of actual positives, how many found? | | Specificity | $$\displaystyle \frac{TN}{TN+FP} $$ | Of actual negatives, how many found? | | F-measure | $$\displaystyle 2 \times \frac{Precision \times Recall}{Precision + Recall} $$ | Harmonic mean of Precision & Recall |

• Evaluation Methods:

  • Holdout: Split data into train/test sets (e.g., 70%/30%).

  • Cross-Validation (k-fold): Partition data into k folds. Train on k-1, test on 1. Repeat k times. Average results.

  • Bootstrap: Sample n instances with replacement from original data (size n). Train on bootstrap sample, test on out-of-bag samples.

VII. ADVANCED & SPECIALIZED DATA MINING APPLICATIONS

• Web Usage Mining: Discovery of user behavior patterns from web logs (clickstreams). Used for personalization, site redesign, marketing.

• Text Mining: Extraction of patterns from unstructured text (documents, emails). Tasks: text categorization, clustering, summarization, sentiment analysis.

• Spatial Mining: Discovery of patterns in spatial databases (data with spatial/geographic attributes). Includes spatial association, clustering, and classification.

VIII. OBJECT-ORIENTED ANALYSIS & DESIGN (OOAD) FOUNDATIONS

Fundamental OO Concepts

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

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

• Polymorphism: Ability of different classes to respond to the same message (method call). Two main types:

  • Compile-time (Overloading): Same method name, different parameters.

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

• Abstraction: Hiding complex implementation details, exposing only essential features. Achieved via abstract classes and interfaces.

Object-Oriented Approach vs. Procedural

How OO Manages Complexity in Large Systems

1. Decomposition: Breaks system into manageable, independent objects.

2. Encapsulation: Hides internal complexity; objects interact via well-defined interfaces.

3. Abstraction: Models real-world entities at appropriate levels of detail.

4. Inheritance & Reuse: Builds new classes from existing ones, reducing redundancy.

5. Modularity: Changes in one object have limited impact on others.

Unified Modeling Language (UML)

• Primary Goals: Provide a standard visual notation for modeling object-oriented software systems. Facilitate communication among stakeholders, aid in documentation, and support system design.

• Relationship Among Models:

  • Structural Models: Describe system's static structure (e.g., Class Diagrams, Object Diagrams).

  • Behavioral Models: Describe dynamic behavior (e.g., Sequence Diagrams, Use Case Diagrams, Activity Diagrams).

  • Architectural Models: Describe high-level organization (e.g., Component Diagrams, Deployment Diagrams).

  • All models are connected; a class diagram defines structure, sequence diagrams show interaction based on that structure.

Class Diagrams: Terms and Concepts

• Class: Rectangle with three compartments: Name, Attributes, Operations.

• Attributes: Properties of a class (e.g., -accountNumber: String).

• Operations: Methods/behaviors (e.g., +deposit(amount: double): void).

• Association: Relationship between classes (line). Can have multiplicity (1, 0..1, 1..*, *, etc.).

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

• Dependency: Dashed arrow showing a "uses" relationship (change in one class affects another).

• Example:

  
  [Customer] "1" ---- "0..*" [Order]
  
  (Association)
  
  [Order] "1" ---- "1..*" [OrderItem]
  
  [Vehicle] <|-- [Car]
  
  (Generalization)
  
  

Object-Oriented Design (OOD)

• Definition: The process of defining the architecture, components, interfaces, and logic for an object-oriented system to satisfy specified requirements.

• Process: Typically involves:

  1. Conceptual Modeling: Identify key objects and relationships (CRC cards).

  2. System Architecture: Define high-level layers and subsystems.

  3. Class Design: Detail classes, attributes, methods, and collaborations.

  4. Design Patterns: Apply reusable solutions (e.g., Singleton, Observer).

  5. Iterative Refinement: Validate against requirements and constraints.

Translating OOD into Implementation

1. Map Design to Programming Language: Choose OO language (Java, C++, Python). Map classes to language constructs.

2. Implement Interfaces & Inheritance: Code superclasses first, then subclasses, overriding methods as needed.

3. Implement Associations: Typically via object references (pointers) as attributes. Manage multiplicities (e.g., 1..* often a List).

4. Implement Error Handling & Persistence: Add exception handling, database access code (ORM).

5. Refactor: Improve code structure without changing behavior.

Object-Oriented Languages & Comparison

• Characteristics: Support classes, objects, inheritance, polymorphism, encapsulation.

• vs. Procedural (C, Pascal): Focus on procedures operating on global/shared data. Data and code are separate.

• vs. Functional (Haskell, Lisp): Focus on immutable data and pure functions (no side effects). Computation is evaluation of expressions.

Object-Oriented Databases (OODB) & Query Languages

• OODB: Stores objects directly, preserving their structure, relationships, and behavior (methods). Suited for complex data (CAD, multimedia).

• OQL (Object Query Language): Standard query language for OODBs (like SQL for RDBs).

  • Syntax: SELECT <attributes> FROM <class/collection> [WHERE <condition>].

  • Key Difference from SQL: Can navigate object relationships directly (e.g., SELECT c.name FROM Customer c WHERE c.orders.amount > 1000). Handles complex objects, inheritance, and methods.