Data base Management System (CY-405) - Unit 4 Short Notes

I. FOUNDATIONAL CONCEPTS & SYSTEM ARCHITECTURE

DBMS vs. Traditional File Systems

• DBMS: Software system for creating, maintaining, and accessing databases. Provides abstract view of data.

• File System: OS-based approach where data stored in isolated files with minimal structure.

• Disadvantages of File Systems:

  • Data Redundancy: Same data duplicated in multiple files.

  • Data Inconsistency: Updates not propagated to all copies.

  • Lack of Integrity: No enforced constraints (e.g., account balance > 0).

  • Security Issues: File-level access control, not fine-grained.

  • Concurrency Problems: No built-in locking; simultaneous updates cause conflicts.

  • Backup & Recovery: Manual, error-prone.

• Advantages of DBMS:

  • Data Independence: Logical/Physical separation (changes in one layer don’t affect others).

  • Reduced Redundancy: Normalization minimizes duplication.

  • Enforced Integrity: Constraints (PK, FK, CHECK) maintain accuracy.

  • Security: User authentication, authorization at object level.

  • Concurrent Access: Locking protocols prevent conflicts.

  • Backup & Recovery: Automated via logs and checkpoints.

  • Data Abstraction: Users see logical view, not physical storage.

[!TIP]

Exam Focus: Always contrast DBMS and file systems using redundancy, consistency, integrity, concurrency. Use examples like bank accounts (file system: separate files for deposits/withdrawals; DBMS: single table with constraints).

Data Abstraction & Schema Architecture

• Three-Level Architecture:

  • External Level: User views (subschemas). Multiple views per database.

  • Conceptual Level: Logical structure (entities, relationships, constraints). Single schema for all users.

  • Internal Level: Physical storage details (files, indexes, storage structures).

• Mappings:

  • External-Conceptual Mapping: Translates user view to logical schema.

  • Conceptual-Internal Mapping: Translates logical schema to physical storage.

• Instance vs. Schema:

  • Schema: Structure (tables, columns, types). Fixed design.

  • Instance: Actual data at a moment. Changes frequently.

• Intension vs. Extension:

  • Intension: Schema description (metadata). Stored in data dictionary.

  • Extension: Set of instances (current data).

[!TIP]

Common Pitfall: Confusing schema (design) with instance (data). Remember: schema is like a blueprint; instance is the built house.

Data Independence

• Logical Data Independence: Changes to conceptual schema (e.g., adding new entity) don’t affect external views or applications. Achieved via mappings.

  • Example: Add Email attribute to Student table; existing queries on Roll_no, Name unaffected.

• Physical Data Independence: Changes to internal storage (e.g., file organization, indexes) don’t affect conceptual or external levels.

  • Example: Switch from heap file to B+ tree index; queries remain same.

[!TIP]

Key Difference: Logical independence shields logical structure changes; physical independence shields storage changes.

DBMS Components & Environment

• Storage Manager:

  • File Manager: Allocates disk space, manages file structures.

  • Buffer Manager: Fetches pages from disk to memory buffer pool.

  • Authorization Manager: Grants user privileges.

• Query Processor:

  • DDL Compiler: Processes schema definitions.

  • DML Compiler: Parses queries, generates relational algebra expressions.

  • Query Optimizer: Chooses efficient execution plan.

• Transaction Manager:

  • Concurrency Control: Schedules transactions (locking, timestamp).

  • Recovery Manager: Uses logs to undo/redo after failures.

• Functions of DBA:

  • Schema definition, security, integrity, backup/recovery, performance tuning, user support.

• Categories of Database Users:

  • Naive Users: Casual end-users (forms, menus).

  • Application Programmers: Write application code (C++, Java).

  • Sophisticated Users: Write complex queries (SQL, RA).

  • DBA: Manages entire DBMS.

• Data Dictionary / System Catalog: Metadata repository (table names, column types, constraints, indexes). Stored as tables; accessed via system views (e.g., INFORMATION_SCHEMA in SQL).

Data Models Overview

[!TIP]

Exam Question: "Compare data models." Use table above. Emphasize relational for most business apps; NoSQL for scalability and unstructured data.

II. ENTITY-RELATIONSHIP (ER) MODEL & CONCEPTUAL DESIGN

ER Diagram Components

• Entity: Real-world object (e.g., Student). Represented by rectangle.

• Attributes:

  • Simple: Atomic (e.g., Roll_no).

  • Composite: Composed of sub-attributes (e.g., Address = {Street, City}).

  • Multivalued: Multiple values (e.g., Phone_No). Represented by double oval.

  • Derived: Computed from other attributes (e.g., Age from DOB). Dashed oval.

• Relationships: Association among entities (e.g., Enrolls). Represented by diamond.

  • Degree: Number of participating entities (binary, ternary, etc.).

  • Cardinality: 1:1, 1:N, M:N.

  • Relationship Attributes: Properties of relationship (e.g., Date in Enrolls).

Advanced ER Constructs

• Weak Entity Set: Entity without a primary key; depends on strong entity for identification. Partial key (underline dashed). Identifying relationship (double diamond).

  • Example: Dependent (Name, Age) of Employee; key = {Emp_ID, Name}.

• Generalization/Specialization:

  • Generalization: Bottom-up (specialized entities → supertype).

  • Specialization: Top-down (supertype → subtypes).

  • Constraints:

    • Total/Partial: Must all entities belong to subtype?

    • Disjoint/Overlapping: Can an entity belong to multiple subtypes?

  • Represented by triangle with lines.

• Aggregation: Relationship as an entity for higher-level relationships.

  • Example: Project uses Software; Software has Vendor. Treat Uses as entity for Project-Vendor relationship.

ER Design & Case Studies

• Design Steps:

  1. Identify entities, attributes, relationships.

  2. Determine cardinalities and participation (total/partial).

  3. Add advanced constructs (weak, generalization, aggregation).

  4. Draw ER diagram with standard notation.

• University Example:

  • Entities: Student (Roll_no, Name, Dept), Course (Cid, Title, Credits), Faculty (Fid, Name, Dept).

  • Relationships: Enrolls (M:N between Student and Course, attribute Grade), Teaches (1:N Faculty to Course).

  • Weak Entity: Project (Pid, Title) under Faculty (identifying relationship Supervises).

  • Generalization: Person → Student/Faculty (total, disjoint).

Mapping ER Diagrams to Relational Schemas

[!TIP]

Mapping Rules: Always identify primary keys first. For M:N, create new table. For generalization, prefer multiple tables for normalization.

Integrity Constraints in ER Model

• Key Constraints: Entity key uniquely identifies instances.

• Cardinality Constraints: Min/max participation (e.g., a Course must have at least 1 Faculty (1..*)).

• Referential Integrity: Foreign key values must exist in referenced table (enforced in relational mapping).

III. RELATIONAL MODEL & QUERY LANGUAGES

Relational Model Fundamentals

• Relation Schema: $$\displaystyle R(A_1: D_1, A_2: D_2, ..., A_n: D_n) $$ where $$\displaystyle A_i $$ are attributes, $$\displaystyle D_i $$ domains.

• Relation Instance: Set of tuples at a given time. Denoted $r(R)$.

• Properties of Relations:

  1. Tuples are unordered (sets).

  2. Attributes are unique within relation.

  3. Tuples are distinct (no duplicates).

  4. Attribute values are atomic (1NF).

  5. Each attribute has a domain.

Keys in Relational Model

• Super Key: Set of attributes that uniquely identifies a tuple (may have extra attributes).

• Candidate Key: Minimal super key (no proper subset is a super key).

• Primary Key: Chosen candidate key. Not NULL, unique.

• Foreign Key: Attribute(s) in one relation that references primary key of another. Enforces referential integrity.

• Composite Key: Primary key consisting of multiple attributes.

• Key Constraints: Primary key → NOT NULL + UNIQUE; Foreign key → value must exist in referenced PK or NULL (if allowed).

[!TIP]

Difference: Super key may have extra attributes; candidate key is minimal. All candidate keys are super keys, but not vice versa.

Relational Algebra Operations

• Fundamental Operations (set-based):

  • Select ($$\displaystyle \sigma_{\text{condition}}(R) $$): Horizontal subset. Example: $$\displaystyle \sigma_{\text{Dept='CS'}}(\text{Student}) $$.

  • Project ($$\displaystyle \pi_{A_1,...,A_n}(R) $$): Vertical subset (columns). Eliminates duplicates. Example: $$\displaystyle \pi_{\text{Name, Dept}}(\text{Student}) $$.

  • Union ($R \cup S$): Tuples in $R$ or $S$ (both must be union-compatible: same attributes, domains).

  • Set Difference ($R - S$): Tuples in $R$ not in $S$.

  • Cartesian Product ($R \times S$): Concatenates every tuple of $R$ with every tuple of $S$.

  • Rename ($$\displaystyle \rho_{S}(R) $$): Renames relation or attributes.

• Derived Operations:

  • Join ($$\displaystyle R \bowtie_{\text{condition}} S $$): Cartesian Product + Select.

    • Natural Join ($\bowtie$): Equijoin on all common attributes; duplicates eliminated.

    • Equi Join: Join with equality condition on specified attributes.

    • Theta Join: Join with arbitrary condition ($\theta$).

  • Intersection ($$\displaystyle R \cap S = R - (R - S) $$): Tuples in both.

  • Division ($R \div S$): Tuples in $R$ that are related to all tuples in $S$. Example: Students taking all courses in Math.

  • Outer Joins:

    • Left Outer Join ($$\displaystyle R \leftouterjoin S $$): All tuples from $R$, matched from $S$, NULLs for unmatched.

    • Right Outer Join ($$\displaystyle R \rightouterjoin S $$): All from $S$.

    • Full Outer Join: All from both.

[!TIP]

Order of Operations: Selection/Projection early to reduce size. Join order critical for performance. Use parentheses: $$\displaystyle \pi_{\text{Name}}(\sigma_{\text{Dept='CS'}}(\text{Student} \bowtie \text{Enrolls})) $$.

Relational Calculus

• Tuple Relational Calculus (TRC):

  • $\{ t \mid P(t) \}$ where $t$ is tuple variable, $P$ is formula.

  • Example: $$\displaystyle \{ s.\text{Name} \mid s \in \text{Student} \land s.\text{Dept} = \text{'CS'} \} $$.

  • Safe Queries: Finite result (domain of all attributes restricted to database).

• Domain Relational Calculus (DRC):

  • $$\displaystyle \{ \langle x_1,...,x_n \rangle \mid P(x_1,...,x_n) \} $$ where $$\displaystyle x_i $$ are domain variables.

  • Example: $$\displaystyle \{ \langle n \rangle \mid \exists d (\langle r,n,d \rangle \in \text{Student} \land d = \text{'CS'}) \} $$.

• Comparison:

  • TRC: Tuple-oriented; DRC: Domain-oriented.

  • Both non-procedural; safe queries equivalent to RA (Codd’s theorem).

SQL (Structured Query Language)

• DDL:

  
  CREATE TABLE Student(Roll_no INT PRIMARY KEY, Name VARCHAR(50), Dept VARCHAR(10));
  
  ALTER TABLE Student ADD COLUMN Age INT;
  
  DROP TABLE Student;
  
  TRUNCATE TABLE Student; -- removes all rows, keeps structure
  
  

• DML:

  • SELECT:

    
    SELECT Name FROM Student WHERE Dept = 'CS' AND Marks > 80;
    
    SELECT Dept, AVG(Marks) FROM Student GROUP BY Dept HAVING AVG(Marks) > 75;
    
    

  • INSERT: INSERT INTO Student VALUES (1, 'Alice', 'CS', 85);

  • UPDATE: UPDATE Student SET Marks = Marks + 5 WHERE Dept = 'CS';

  • DELETE: DELETE FROM Student WHERE Marks < 40;

• Subqueries:

  • IN: SELECT Name FROM Student WHERE Dept IN (SELECT Dept FROM Faculty WHERE Rank='Prof');

  • EXISTS: SELECT Name FROM Student S WHERE EXISTS (SELECT * FROM Enrolls E WHERE S.Roll_no = E.Roll_no AND E.Cid='CS101');

  • ANY/ALL: SELECT Name FROM Student WHERE Marks > ANY (SELECT Marks FROM Student WHERE Dept='ECE');

• Joins:

  
  -- INNER JOIN
  
  SELECT S.Name, E.Course FROM Student S JOIN Enrolls E ON S.Roll_no = E.Roll_no;
  
  -- LEFT OUTER JOIN
  
  SELECT S.Name, E.Course FROM Student S LEFT JOIN Enrolls E ON S.Roll_no = E.Roll_no;
  
  -- SELF JOIN (e.g., employee-manager)
  
  SELECT E1.Name, E2.Name AS Manager FROM Employee E1 LEFT JOIN Employee E2 ON E1.Manager_ID = E2.Emp_ID;
  
  

• Views:

  
  CREATE VIEW CS_Students AS SELECT Roll_no, Name FROM Student WHERE Dept='CS';
  
  -- Updateable view: single table, no aggregates, all NOT NULL columns included.
  
  -- Materialized view: stored physically; `CREATE MATERIALIZED VIEW ... REFRESH ...`.
  
  

• Triggers:

  
  CREATE TRIGGER UpdateTotal AFTER INSERT ON OrderItems
  
  FOR EACH ROW
  
  BEGIN
  
    UPDATE Orders SET Total_Amount = Total_Amount + NEW.Amount 
  
    WHERE Order_ID = NEW.Order_ID;
  
  END;
  
  

  Types: BEFORE/AFTER, ROW/STATEMENT.

• Integrity Constraints:

  • PRIMARY KEY, FOREIGN KEY ... REFERENCES ... ON DELETE CASCADE, UNIQUE, NOT NULL, CHECK (Marks BETWEEN 0 AND 100), ASSERTION (global, e.g., CREATE ASSERTION ... CHECK (NOT EXISTS (...))).

[!TIP]

SQL Pitfalls:

• NULL handling: WHERE Marks > 80 excludes NULLs; use IS NULL.

• Subquery with IN vs EXISTS: EXISTS stops at first match; IN may process all.

• View updates: Not allowed if view has aggregates, joins, or DISTINCT.

IV. DATABASE DESIGN & NORMALIZATION

Functional Dependencies (FDs)

• Definition: $$\displaystyle X \rightarrow Y $$ means for any two tuples, if they agree on $X$, they agree on $Y$. $X$ (determinant) → $Y$ (dependent).

• Armstrong’s Axioms (sound and complete):

  1. Reflexivity: If $Y \subseteq X$, then $$\displaystyle X \rightarrow Y $$.

  2. Augmentation: If $$\displaystyle X \rightarrow Y $$, then $$\displaystyle XZ \rightarrow YZ $$.

  3. Transitivity: If $$\displaystyle X \rightarrow Y $$ and $$\displaystyle Y \rightarrow Z $$, then $$\displaystyle X \rightarrow Z $$.

• Derived Rules: Union, Decomposition, Pseudotransitivity.

• FD Closure ($$\displaystyle X^+ $$): Set of attributes functionally determined by $X$.

  • Algorithm: Start with $$\displaystyle X^+ = X $$. Repeatedly add $Y$ if there exists FD $$\displaystyle Y' \rightarrow Y $$ with $$\displaystyle Y' \subseteq X^+ $$.

  • Example: Given $$\displaystyle F = \{A \rightarrow B, B \rightarrow C, C \rightarrow D\} $$, compute $$\displaystyle A^+ $$: start $A$, add $B$ ($$\displaystyle A \rightarrow B $$), add $C$ ($$\displaystyle B \rightarrow C $$), add $D$ ($$\displaystyle C \rightarrow D $$). So $$\displaystyle A^+ = \{A,B,C,D\} $$.

• Minimal Cover ($$\displaystyle F_c $$):

  1. Each FD has single attribute on RHS.

  2. No extraneous attribute on LHS (remove $A$ from $X$ if $$\displaystyle (X - \{A\})^+ $$ still contains $Y$).

  3. Remove redundant FDs (check if $F - \{f\}$ implies $f$).

  • Example: $$\displaystyle F = \{AB \rightarrow C, B \rightarrow C\} $$ → minimal: $$\displaystyle \{B \rightarrow C\} $$ (since $$\displaystyle AB \rightarrow C $$ redundant if $$\displaystyle B \rightarrow C $$).

[!TIP]

FD Closure: Use iterative method. For candidate keys, find $X$ such that $$\displaystyle X^+ $$ contains all attributes.

Normal Forms

[!TIP]

Hierarchy: BCNF ⊆ 3NF ⊆ 2NF ⊆ 1NF. BCNF stricter than 3NF. 4NF handles MVDs (multi-valued facts independent of each other).

Normalization Process

1. To 2NF: For each partial dependency $$\displaystyle X \rightarrow A $$ where $X$ is proper subset of candidate key, decompose into $R1(X, A)$ and $R2(\text{remaining attributes})$.

2. To 3NF/BCNF: For each FD $$\displaystyle X \rightarrow Y $$ where $X$ not super key:

   • 3NF: Allow if $Y$ is prime attribute (part of some candidate key). Use synthesis algorithm.

   • BCNF: Always decompose: $R1(X \cup Y)$, $R2(X \cup (\text{attributes} - Y))$.

3. Repeat until all relations in desired normal form.

Database Anomalies

• Insertion Anomaly: Cannot insert data without other data. Example: Cannot add new Course without an EnrollNo in $R(\text{EnrollNo}, \text{Course}, \text{Instructor})$.

• Deletion Anomaly: Deleting data loses other info. Example: Deleting last EnrollNo for a Course loses Instructor.

• Update Anomaly: Inconsistent updates. Example: Instructor for a Course stored in multiple tuples; update one but not others.

• Normalization Eliminates Anomalies: By decomposing into smaller relations with minimal dependencies.

Decomposition

• Lossless Join Decomposition: $R$ decomposed into $R1, R2$ is lossless if $$\displaystyle R1 \cap R2 \rightarrow R1 $$ or $$\displaystyle R1 \cap R2 \rightarrow R2 $$ (using FDs). Test via chase algorithm.

• Dependency Preserving: Union of FDs from all $$\displaystyle R_i $$ implies original $F$. Not always possible with BCNF.

• Importance: Avoids anomalies, ensures data consistency, improves storage efficiency.

[!TIP]

Decomposition Check: For lossless, ensure common attributes determine one of the relations. For dependency preserving, check if all FDs can be enforced locally.

V. TRANSACTION MANAGEMENT & CONCURRENCY CONTROL

Transaction Concept

• Transaction: Logical unit of work (sequence of read/write operations). Must be atomic (all or nothing).

• ACID Properties:

  • Atomicity: Either all operations commit or abort (rollback).

  • Consistency: Preserves database integrity constraints (from one consistent state to another).

  • Isolation: Concurrent transactions don’t interfere (as if executed serially).

  • Durability: Once committed, changes survive system crashes (written to disk).

• Transaction States:

  1. Active: Executing.

  2. Partially Committed: Operations done, commit pending.

  3. Committed: Successfully completed.

  4. Failed: Abort needed (constraint violation, crash).

  5. Aborted: Rolled back; may be restarted.

• State Diagram: Active → Partially Committed → Committed; Active/Partially Committed → Failed → Aborted → (Restart) → Active.

Schedules & Serializability

• Schedule: Order of operations from multiple transactions.

• Serial Schedule: Transactions execute one after another (no overlap). Always correct but poor concurrency.

• Non-Serial Schedule: Transactions overlap. May cause inconsistencies (lost update, dirty read, etc.).

• Conflict Serializability:

  • Two operations conflict if they access same data and at least one is write.

  • Precedence Graph (Serializability Graph): Nodes = transactions. Edge $$\displaystyle T_i \rightarrow T_j $$ if $$\displaystyle T_i $$ has operation that conflicts with earlier $$\displaystyle T_j $$ operation.

  • Test: Schedule is conflict serializable iff graph is acyclic. Equivalent serial order = topological order.

• View Serializability:

  • Two schedules view-equivalent if:

    1. Same initial reads.

    2. Same final writes.

    3. Same read-from relationships.

  • Harder to test; more schedules are view serializable than conflict serializable.

• Recoverable Schedule: If $$\displaystyle T_i $$ reads data written by $$\displaystyle T_j $$, then $$\displaystyle T_i $$ commits only after $$\displaystyle T_j $$ commits. Prevents dirty reads.

Concurrency Control

• Need: Prevent anomalies (lost update, dirty read, unrepeatable read, phantom read).

• Locking-Based Protocols:

  • Lock Modes:

    • Shared (S): Read lock; multiple transactions can hold S-lock.

    • Exclusive (X): Write lock; only one transaction, no other locks.

  • Two-Phase Locking (2PL):

    • Growing Phase: Transaction acquires locks (no releases).

    • Shrinking Phase: Transaction releases locks (no acquisitions).

    • Guarantees conflict serializability.

    • Problems: Deadlocks possible; not cascade-free (if $$\displaystyle T_i $$ aborts, $$\displaystyle T_j $$ may have read dirty data).

  • Conservative (Static) 2PL: Transaction acquires all locks at start (wait if any locked). No deadlocks but low concurrency.

  • Rigorous 2PL: Release all locks at commit/abort (strict 2PL). Ensures cascade-free and recoverable schedules.

  • Lock Manager: Handles lock_request(T, item, mode) and unlock(T, item). Queues requests; grants if compatible.

• Timestamp-Based Concurrency Control:

  • Each transaction $$\displaystyle T_i $$ gets timestamp $$\displaystyle TS(T_i) $$ (start time).

  • Each data item $X$ has read-timestamp $RTS(X)$ and write-timestamp $WTS(X)$.

  • Rules:

    • If $$\displaystyle T_i $$ reads $X$: if $$\displaystyle TS(T_i) < WTS(X) $$, abort (too late); else allow, update $$\displaystyle RTS(X) = \max(RTS(X), TS(T_i)) $$.

    • If $$\displaystyle T_i $$ writes $X$: if $$\displaystyle TS(T_i) < RTS(X) $$ or $$\displaystyle TS(T_i) < WTS(X) $$, abort; else write, set $$\displaystyle WTS(X) = TS(T_i) $$.

  • Advantage: No deadlocks; Disadvantage: More aborts (older transactions may starve).

• Validation-Based (Optimistic) Concurrency Control:

  • Phases:

    1. Read Phase: Transaction reads, writes to local workspace.

    2. Validation Phase: Check if transaction conflicts with committed ones during its execution.

    3. Write Phase: If valid, write changes; else abort.

  • Validation: Use timestamp or serialization graph test. Low overhead if conflicts rare.

• Multiple Granularity Locking (MGL):

  • Lock hierarchies: Database > Table > Page > Row.

  • Intention Locks:

    • IS (Intention Shared): Some sub-objects locked S.

    • IX (Intention Exclusive): Some sub-objects locked X.

    • SIX (Shared + Intention Exclusive): Sub-objects locked S, but some sub-objects locked X.

  • Protocol: To lock a node, must have compatible lock on parent (e.g., to lock row S, must have IS on table). Allows coarse-grained locking without excessive locking.

Deadlocks

• Definition: Cycle of transactions waiting for locks held by each other.

• Detection:

  • Wait-For Graph (WFG): Nodes = transactions; edge $$\displaystyle T_i \rightarrow T_j $$ if $$\displaystyle T_i $$ waiting for lock held by $$\displaystyle T_j $$.

  • Periodically check for cycles. If cycle, select victim (lowest cost to abort).

• Prevention:

  • Wait-Die: Older transaction waits; younger transaction aborts (waits if older, dies if younger).

  • Wound-Wait: Older transaction wounds (forces abort) younger; younger waits.

  • Both use timestamps to break symmetry.

• Resolution: Abort victim, rollback, restart after delay.

• Blocking vs. Deadlock:

  • Blocking: $$\displaystyle T_i $$ waiting for lock held by $$\displaystyle T_j $$; $$\displaystyle T_j $$ will eventually release.

  • Deadlock: Circular wait; no progress possible.

[!TIP]

2PL vs. Deadlock: 2PL can cause deadlocks. Use timeout or detection. Rigorous 2PL prevents cascading aborts.

VI. QUERY PROCESSING & OPTIMIZATION

Query Processing Phases

1. Parsing & Translation:

   • Syntax/semantic check.

   • Translate SQL to relational algebra (internal representation).

2. Optimization:

   • Choose lowest-cost execution plan from many equivalent RA expressions.

3. Execution:

   • Execute plan using query execution engine (operators: scan, join, aggregate).

Query Optimization

• Necessity: Queries on large databases; poor choices can mean hours vs. seconds.

• Cost Measures:

  • I/O Cost: Disk page reads/writes (dominant).

  • CPU Cost: Tuple processing, comparisons.

  • Network Cost: Distributed queries.

  • Estimated using statistics (table sizes, distinct values, indexes).

• Heuristic-Based Optimization (rule-based):

  • Selection Pushdown: Apply σ as early as possible to reduce tuple count.

  • Projection Pushdown: Apply π early to reduce attribute count.

  • Combine Selections: $$\displaystyle \sigma_{c1}(\sigma_{c2}(R)) = \sigma_{c1 \land c2}(R) $$.

  • Order of Joins: Perform most selective joins first.

• Cost Estimation-Based Optimization:

  • Generate multiple equivalent plans.

  • Estimate cost for each using statistics (e.g., number of tuples after selection: $$\displaystyle | \sigma_{\text{condition}}(R) | \approx |R| \times \text{selectivity} $$).

  • Choose minimal cost plan.

  • Expression Trees: Different join orders yield different costs. Use dynamic programming (System R) or greedy algorithms.

• Comparison of Operations:

  | Operation | I/O Cost | CPU Cost | Notes | |-----------|----------|----------|-------| | Selection | Low if indexed; else full scan | O(n) | Push down early. | | Join | High (nested loop: O(|R|×|S|); hash/merge join: O(|R|+|S|)) | High | Choose based on sizes; indexes help. | | Sorting | O(n log n) I/O (external sort) | O(n log n) | Needed for ORDER BY, GROUP BY, merge join. |

[!TIP]

Optimization Example: Query SELECT Name FROM Student S JOIN Enrolls E ON S.Roll_no=E.Roll_no WHERE E.Cid='CS101'.

Bad plan: Join first (large intermediate), then select.

Good plan: Select on Enrolls first (σ_{Cid='CS101'}), then join with Student.

VII. STORAGE, FILE ORGANIZATION & INDEXING

File Organization Methods

Indexing Techniques

• Purpose: Speed up search, selection, join, ordering.

• Dense Index: Index entry for every search key value (in data file). Smaller than data file? Not necessarily.

• Sparse Index: Index entry for some key values (e.g., first record in block). Smaller, faster.

• Primary Index: Index on primary key; usually clustering (data stored in index order). One per table.

• Secondary Index: Index on non-key attribute; non-clustering (data not in index order). May have multiple.

• Clustering Index: Data file physically ordered by index key. One per table (like primary index).

• Non-Clustering Index: Index separate from data; data not ordered by key. Multiple allowed.

• Multilevel Indices:

  • Single-level: Index on disk; root in memory? Not scalable.

  • Multilevel: Top levels in memory (buffer), lower on disk. B+ trees are multilevel.

Hashing Techniques

• Static Hashing:

  • Hash function $h(k)$ maps key to bucket (fixed number $N$).

  • Overflow Handling: Chaining (linked list in bucket) or open addressing.

  • Inner Attributes: Attributes used in hash function (e.g., Roll_no).

  • Outer Attributes: Attributes stored with record but not in hash function.

  • Problem: Bucket overflow if $N$ too small; cannot easily change $N$.

• Extendable Hashing:

  • Directory: Array of pointers to buckets. Each entry has local depth $d$.

  • Bucket Splitting: When bucket overflows, split and possibly double directory (increase global depth $D$).

  • Example: $$\displaystyle h(k) = k \mod 2^D $$. Initially $$\displaystyle D=1 $$, 2 buckets. Bucket 0 overflows → split, increase $D$ to 2, directory size 4.

  • Advantage: No overflow; dynamic growth.

• Linear Hashing:

  • No directory; buckets in file.

  • Split bucket $i$ when overflow, using $$\displaystyle h_i(k) = k \mod (N + i) $$.

  • Incremental splitting; no directory overhead.

  • Split pointer rounds robin.

• Comparison:

  | Technique | Directory | Bucket Splitting | Overflow | |-----------|-----------|------------------|----------| | Static | No | No | Yes (chaining) | | Extendable | Yes | Yes (per bucket) | No | | Linear | No | Yes (round-robin) | No |

Bitmap Indexing

• For low-cardinality attributes (e.g., Gender, Marital_Status).

• For each attribute value, a bit vector: 1 if tuple has value, 0 otherwise.

• Operations: Fast AND/OR (bitwise AND/OR). Efficient for complex WHERE clauses.

• Disadvantage: High storage for high-cardinality; updates expensive.

RAID (Redundant Array of Independent Disks)

[!TIP]

RAID 5 most common: balances performance, capacity, reliability. RAID 0 for speed, RAID 1 for safety.

VIII. RECOVERY SYSTEMS

Failure Types

• Transaction Failure: Logical error (constraint violation, divide by zero). Local to transaction.

• System Crash: Power loss, software error. Memory lost; disk intact.

• Media Failure: Disk crash, corruption. Need backup.

Database Logs

• Structure: Sequence of log records: <T, X, old, new> for write; <T, X> for commit/abort.

• Write-Ahead Logging (WAL) Protocol:

  • Log record for $X$ must be written to disk before $X$ is written to disk.

  • Ensures durability: if crash after data write but before log flush, changes lost (but transaction not committed).

• Importance: Basis for undo/redo during recovery.

Recovery Strategies

• Deferred Database Modification:

  • Transaction writes changes to private workspace (not disk).

  • At commit, write all changes to disk at once.

  • Recovery: No redo needed (committed changes not on disk? Actually, after commit, changes written; if crash before commit, nothing to do). But if crash during commit? Need careful. Usually: undo uncommitted transactions from log (before commit).

• Immediate Database Modification:

  • Transaction writes changes to disk immediately (with WAL: log flushed first).

  • Recovery:

    • Redo: Reapply all updates from committed transactions (since they may not be on disk).

    • Undo: Rollback uncommitted transactions (reverse their updates).

  • Uses log with <T, X, old, new>.

Checkpoints

• Purpose: Reduce recovery time; avoid scanning entire log.

• Implementation:

  1. Flush all modified buffer pages to disk.

  2. Write <CHECKPOINT> log record with list of active transactions.

  3. Force log to disk.

• How Checkpoints Work:

  • During recovery, start from last checkpoint.

  • Redo: All transactions after checkpoint (committed or not) may need redo (since their updates may not be on disk).

  • Undo: Only transactions active at checkpoint that did not commit need undo.

  • Significantly reduces log scan.

Shadow Paging

• Mechanism: Two page tables: current and shadow.

  • Transaction uses current; shadow is consistent copy.

  • On commit:

    1. Flush all modified data pages to disk (in new locations).

    2. Flush current page table to disk (becomes new shadow).

    3. Atomic switch: shadow pointer points to new current.

  • Recovery: If crash before commit, shadow unchanged; after commit, both consistent.

• Example:

  • Initial: shadow = current = P1.

  • T modifies page A: copy A to new page A', update current to point to A'.

  • Commit: flush A', write current to disk → new shadow.

• Advantage: No undo/redo; atomic commit.

• Disadvantage: Copying page tables; space overhead (need free pages).

[!TIP]

WAL vs. Shadow Paging: WAL uses log (sequential writes); shadow paging uses copy-on-write (random I/O). WAL more common; shadow paging in some NoSQL (e.g., copy-on-write B-trees).

IX. DISTRIBUTED DATABASES

Concepts & Challenges

• Data Fragmentation:

  • Horizontal: Rows split by condition (e.g., Student by Dept).

  • Vertical: Columns split (e.g., Student personal vs. academic).

  • Hybrid: Combination.

• Data Replication: Copies at multiple sites. Improves availability, read performance; complicates updates.

• Transparency:

  • Fragmentation Transparency: Users don’t know data is fragmented.

  • Replication Transparency: Users don’t know copies exist.

  • Location Transparency: Users don’t know site of data.

• Challenges:

  • Network delays, site failures, distributed transactions, concurrency control complexity, data consistency.

Distributed Query Processing & Optimization

• Goal: Minimize data transfer across network.

• Steps:

  1. Parse query to distributed RA.

  2. Fragment queries: Push selections/projections to fragment sites.

  3. Data localization: Execute operations at site where data resides.

  4. Transfer minimal results to coordinator for final operations.

• Optimization: Cost model includes network cost (tuples transferred). Use semi-join to reduce transfer.

Distributed Transaction Management

• Two-Phase Commit (2PC):

  • Coordinator manages distributed transaction $T$.

  • Phase 1 (Prepare): Coordinator asks all participants to prepare (can commit?). Participants write <prepare T> to log, lock resources, reply YES/NO.

  • Phase 2 (Commit/Abort): If all YES, coordinator writes <commit T>, sends commit; else abort. Participants acknowledge.

  • Blocking: If coordinator crashes, participants may wait indefinitely (in prepared state).

• Three-Phase Commit (3PC):

  • Adds Pre-Commit phase after prepare.

  • Participants acknowledge pre-commit.

  • If coordinator crashes, participants can timeout and commit/abort based on state.

  • Non-blocking but assumes no network partitions (violates CAP?).

Concurrency Control & Recovery in DDBMS

• Challenges:

  • Network delays affect lock timing.

  • Site failures: need global recovery (coordinator may fail).

• Solutions:

  • Distributed Locking: Centralized (single lock manager) or distributed (two-phase locking across sites). May cause deadlocks across sites.

  • Timestamp with voting: Each site has timestamp; global order by max timestamp.

  • Recovery: Each site uses local logs; coordinator coordinates global commit/abort. Need presumed abort or presumed commit protocols to simplify.

X. ADVANCED & SPECIAL TOPICS

Views

• Definition: Virtual table defined by query. CREATE VIEW ViewName AS SELECT ....

• Usage: Simplify complex queries, provide security (restrict columns/rows), logical independence.

• Updateable Views:

  • Single base table, no aggregates, DISTINCT, GROUP BY, or set operations.

  • All NOT NULL columns of base table included.

  • Updates mapped to base table.

• Non-Updateable Views: Most views (joins, aggregates). Some updatable via INSTEAD OF triggers.

• Materialized vs. Virtual:

  • Virtual: Query rewritten to base tables; no storage.

  • Materialized: Stored physically; need REFRESH (on commit or demand). Faster queries, stale data.

Triggers

• Definition: Stored procedure that executes automatically on event (INSERT, UPDATE, DELETE).

• Syntax (SQL standard):

  
  CREATE TRIGGER trigger_name
  
  BEFORE/AFTER INSERT/UPDATE/DELETE ON table
  
  [FOR EACH ROW]
  
  [WHEN (condition)]
  
  BEGIN
  
    -- action
  
  END;
  
  

• Types:

  • Row-level: Executes per affected row (FOR EACH ROW).

  • Statement-level: Executes once per statement.

• Use Cases: Audit trails, enforce complex integrity, maintain summary tables, replicate data.

• Caution: Can cause cascading triggers; performance overhead.

NoSQL Databases

• Characteristics:

  • CAP Theorem: Consistency, Availability, Partition Tolerance — pick two.

  • Schema-flexible (dynamic columns).

  • Horizontal scalability (sharding).

  • BASE model (Basically Available, Soft state, Eventual consistency).

• Types:

  | Type | Data Model | Example | Use Case | |------|------------|---------|----------| | Document | JSON/BSON documents | MongoDB | Content management, catalogs | | Key-Value | Key → Value (blob) | Redis, Dynamo | Caching, sessions | | Graph | Nodes, edges, properties | Neo4j | Social networks, recommendations | | Column-Family | Column families (wide rows) | Cassandra, HBase | Time series, IoT |

• Advantages over RDBMS: Scale-out, flexible schema, high throughput for unstructured data.

• Disadvantages: Limited ACID (eventual consistency), no standard query language, joins expensive.

Data Dictionary & System Catalogs

• Data Dictionary: Metadata repository (tables, columns, types, constraints, indexes, users, privileges).

• System Catalogs: Tables storing dictionary (e.g., INFORMATION_SCHEMA in SQL, DBA_, ALL_, USER_ views in Oracle).

• Dynamic Performance Views: Real-time statistics (e.g., V$SESSION in Oracle). Used by DBA for monitoring.

• Functions: Schema definition, integrity enforcement, query optimization (statistics), security.

Assertions & Domain Constraints

• Domain Constraints: Attribute domain (data type, range). Enforced via CHECK or DOMAIN (SQL).

  
  CREATE DOMAIN PositiveInt AS INT CHECK (VALUE > 0);
  
  CREATE TABLE Product(Price PositiveInt);
  
  

• Assertions: Global constraints across tables.

  
  CREATE ASSERTION CheckSalary 
  
  CHECK (NOT EXISTS (SELECT * FROM Employee E1, Employee E2 
  
                     WHERE E1.Salary > 2*E2.Salary AND E1.Dept = E2.Dept));
  
  

  Rarely used; often enforced via triggers or application logic.

Hierarchical Queries

• CONNECT BY (Oracle): Query hierarchical data (e.g., organization chart).

  
  SELECT employee_id, manager_id, LEVEL 
  
  FROM employees 
  
  START WITH manager_id IS NULL 
  
  CONNECT BY PRIOR employee_id = manager_id;
  
  

  LEVEL pseudo-column, PRIOR for parent-child.

Oracle Application Express (APEX)

• Low-code web development platform for Oracle DB.

• Browser-based; builds web apps on Oracle data.

• Features: SQL/PLSQL integration, responsive UI, security, deployment.

• Used for rapid internal apps, dashboards.

Complexity Measures in Query Processing

• I/O Complexity: Number of disk page reads/writes (dominant).

• CPU Complexity: Tuple operations (comparisons, projections).

• Network Complexity: Data transferred in distributed queries.

• Time Complexity: Big O notation for algorithms (e.g., sort: $O(n \log n)$, join: $$\displaystyle O(n^2) $$ nested loop vs $O(n)$ hash join).

• Space Complexity: Buffer memory needed.

Components of DBMS (Detailed)

1. Storage Manager:

   • File Manager (disk allocation).

   • Buffer Manager (buffer pool, replacement policies LRU, Clock).

   • Disk Manager (read/write pages).

2. Query Processor:

   • DDL Compiler → System catalog.

   • DML Compiler → RA expression.

   • Query Optimizer → Execution plan.

   • Query Executor → Operators (scan, join, aggregate).

3. Transaction Manager:

   • Scheduler (concurrency control).

   • Recovery Manager (log, checkpoint, undo/redo).

4. Authorization Manager: Grants/revokes privileges.

5. Buffer Manager: Critical for performance; uses buffer pool with replacement.

[!TIP]

Exam Focus: Know components and their functions. Buffer manager reduces I/O via caching. Query optimizer chooses best plan based on cost.