Data Base Management System (IT-405) - Unit 2 Short Notes

I. INTRODUCTION & DATABASE SYSTEM ARCHITECTURE

File System vs. DBMS

[!TIP]

Exam Focus: Always contrast data independence and integrity enforcement as key differentiators. DBMS provides logical and physical data independence—changes at one schema level do not affect others.

Three-Level Architecture

• External Level (View Level): User-specific views. Multiple views possible.

• Conceptual Level (Logical Level): Global logical schema (all entities, relationships, constraints). Single schema for entire DB.

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

• Mappings:

  • External/Conceptual Mapping: Defines how user views derive from global schema.

  • Conceptual/Internal Mapping: Defines how logical schema maps to physical storage.

  Enables data independence: Changes at internal level (e.g., file organization) do not affect conceptual/external levels.

Components of DBMS

1. Storage Manager:

   • File manager, buffer manager, file organization (heap, sorted), indexing (B+ Tree, Hashing).

   • Authorization & Integrity Manager: Enforces constraints, grants privileges.

2. Query Processor:

   • DDL Interpreter: Processes schema definitions.

   • DML Compiler: Translates queries into relational algebra expressions.

   • Query Optimizer: Chooses efficient execution plan (minimizes cost).

3. Transaction Manager:

   • Concurrency control (locking, timestamp), recovery (logging, checkpoint).

Data Independence

• Physical Data Independence: Changes in storage structures (e.g., switch from heap to sorted files) do not affect conceptual/external schemas.

  Example: Adding an index on Employee(Salary) doesn’t change user queries.

• Logical Data Independence: Changes in conceptual schema (e.g., adding new attribute Employee(Email)) do not affect external views or applications.

  Example: Adding MiddleName to Student table; existing applications using FirstName, LastName remain unaffected.

Database Users & Interfaces

II. DATA MODELING & ENTITY-RELATIONSHIP (ER) MODEL

ER Model Fundamentals

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

• Attribute: Property of entity (e.g., Student(RollNo, Name)). Represented by ellipse.

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

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

  • Multivalued: Multiple values (e.g., PhoneNumbers).

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

• Relationship: Association between entities (e.g., Enrolls(Student, Course)). Represented by diamond.

• Key Constraints:

  • Super Key: Set of attributes uniquely identifying an entity (may have extra attributes).

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

  • Primary Key: Chosen candidate key (underlined in ER).

  • Composite Key: Primary key with multiple attributes.

  • Foreign Key: Attribute in one entity referencing primary key of another.

Relationship Types

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

• Cardinality:

  • 1:1: One entity associates with at most one of other.

  • 1:N: One entity associates with many of other.

  • M:N: Many-to-many (requires associative entity in relational mapping).

• Participation:

  • Total: Every entity must participate (double line).

  • Partial: Optional participation (single line).

Advanced ER Modeling

• Weak Entity Set:

  • Existence depends on another entity (owner).

  • Double rectangle for weak entity, double diamond for identifying relationship.

  • Partial key (discriminator) + owner’s key forms primary key.

• Generalization vs. Specialization:

  • Specialization (Top-down): Subset entities from superclass (e.g., Employee → Manager, Engineer).

  • Generalization (Bottom-up): Combine similar entities into superclass.

  • Both use triangle with “IS-A” hierarchy.

• Aggregation: Treats relationship as an entity (e.g., Project uses Equipment; Equipment may be shared by multiple projects). Represented by diamond within diamond.

Mapping ER to Relational Schema

[!TIP]

Exam Focus: For M:N relationships, always create a new table. For weak entities, primary key includes owner’s key.

III. RELATIONAL MODEL & RELATIONAL ALGEBRA/CALCULUS

Relational Model Concepts

• Relation Schema: R(A₁: D₁, A₂: D₂, ..., Aₙ: Dₙ) where Aᵢ are attributes, Dᵢ domains.

• Relation Instance (Table): Set of tuples at a moment.

• Keys:

  • Super Key: Uniquely identifies tuples (may contain extra attributes).

  • Candidate Key: Minimal super key.

  • Primary Key: Selected candidate key (unique, not null).

  • Foreign Key: R.A references S.B where B is PK of S. Enforces referential integrity.

• Integrity Constraints:

  • Domain Constraint: Attribute value must be from domain.

  • Entity Integrity: PK cannot be null.

  • Referential Integrity: FK value must exist in referenced PK or be null (if allowed).

Relational Algebra Operations

Fundamental Operations (base set, all others derivable):

1. Select (σ): σ_{condition}(R) → tuples satisfying condition.

   Example: σ_{Dept='CS'}(Student).

2. Project (Π): Π_{A₁,...,Aₖ}(R) → columns specified, duplicates removed.

   Example: Π_{Name, Dept}(Student).

3. Union (∪): R ∪ S → tuples in R or S (both must be union-compatible).

4. Set Difference (−): R − S → tuples in R not in S.

5. Cartesian Product (×): R × S → concatenate every tuple of R with every tuple of S.

6. Rename (ρ): ρ_{S(R₁,...,Rₙ)}(R) → rename relation/attributes.

Additional Operations:

• Intersection (∩): R ∩ S = R − (R − S).

• Natural Join (⋈): R ⋈ S → equi-join on common attributes, duplicates removed.

  Example: Student ⋈ Enrolls on RollNo.

• Theta Join (⋈_θ): R ⋈_{A θ B} S where θ is any condition (e.g., >).

• Outer Joins:

  • Left Outer Join (⟕): All tuples from left, matched from right, nulls for unmatched.

  • Right Outer Join (⟖): Symmetric.

  • Full Outer Join (⟗): All tuples from both, nulls where unmatched.

• Division (÷): R ÷ S → tuples in R that are related to all tuples in S.

  Example: Find students taking all courses in RequiredCourses.

Relational Calculus

• Tuple Relational Calculus (TRC): { t | P(t) } where t is tuple variable, P is formula.

  Example: { t | t ∈ Student ∧ t.Dept = 'CS' }.

• Domain Relational Calculus (DRC): { ⟨x₁,...,xₙ⟩ | P(x₁,...,xₙ) } where xᵢ are domain variables.

  Example: { ⟨n⟩ | ∃d (Student(Roll, n, d, y) ∧ d='CS') }.

• Difference: RA is procedural (how to get result), Calculus is declarative (what result).

SQL Fundamentals

• DDL: CREATE TABLE R(...), ALTER TABLE R ADD/DROP COLUMN, DROP TABLE R, TRUNCATE TABLE R.

• DML: SELECT with:

  • WHERE (filter), GROUP BY (aggregation), HAVING (filter groups), ORDER BY.

  • Special Operators:

    • LIKE '%pattern%' (wildcards %, _).

    • IN (subquery) / NOT IN.

    • EXISTS / NOT EXISTS (correlated subqueries).

    • ANY/ALL (compare with set).

  • Aggregate Functions: COUNT, SUM, AVG, MIN, MAX.

  • Joins:

    
    SELECT * FROM Student S JOIN Enrolls E ON S.RollNo = E.RollNo; -- Equi-join
    
    SELECT * FROM Student NATURAL JOIN Enrolls; -- Natural join (on common attributes)
    
    SELECT * FROM Student LEFT OUTER JOIN Enrolls ON ...;
    
    

  • Subqueries: Nested in WHERE, FROM, SELECT.

Query Processing & Optimization

• Phases:

  1. Parsing: Check syntax, build parse tree.

  2. Translation: Convert parse tree to relational algebra expression.

  3. Optimization: Generate equivalent expressions with lower cost (using heuristics/cost estimation).

  4. Execution: Generate code, execute.

• Need for Optimization: Same query can have exponentially different execution times.

  Example: σ_{Dept='CS'}(Student) ⋈ Enrolls vs. Student ⋈ σ_{Dept='CS'}(Enrolls).

• Cost Measures:

  • Disk I/O: Dominant cost (seek + transfer).

  • CPU: Tuple processing.

  • Communication: Distributed DBs.

• Operation Costs (approx):

  | Operation | Cost (Block Transfers) | |-----------------|----------------------------------------------------| | Selection | O(b) (scan) or O(log_b N) (index) | | Projection | O(b) (may need duplicate elimination) | | Join | O(b_r + b_s) (index nested loop) to O(b_r * b_s) (nested loop) | | Sorting | O(b log_b b) (external sort) |

• Optimization Methods:

  • Heuristic (Rule-based):

    1. Apply selections early (reduce tuples).

    2. Project early (reduce attributes).

    3. Replace Cartesian product + selection with join.

  • Cost Estimation-Based: Use statistics (relation size, distinct values, indexes) to estimate intermediate sizes and choose plan with minimal cost.

• Role of Relational Algebra: Intermediate representation for optimization; optimizer rewrites RA expression.

[!TIP]

Exam Focus: Compare selection, projection, join costs. Know heuristic rules: “Do selection and projection as early as possible.”

IV. DATABASE DESIGN & NORMALIZATION

Functional Dependencies (FDs)

• Definition: X → Y means for any two tuples, if they agree on X, they must agree on Y. X is determinant.

• Properties (Armstrong’s Axioms):

  1. Reflexivity: If Y ⊆ X, then X → Y.

  2. Augmentation: If X → Y, then XZ → YZ.

  3. Transitivity: If X → Y and Y → Z, then X → Z.

  • Derived Rules: Union (X → Y and X → Z ⇒ X → YZ), Decomposition (X → YZ ⇒ X → Y and X → Z), Pseudotransitivity.

• Closure (X⁺): Set of attributes functionally determined by X under F.

  Algorithm: Start with X⁺ = X; repeatedly add Y if Y ⊆ X⁺ and some Z → Y with Z ⊆ X⁺.

• Canonical Cover (Minimal Cover):

  1. Decompose RHS of each FD to single attribute.

  2. Remove extraneous LHS attributes (test if X - {A} → B is implied).

  3. Remove redundant FDs (test if F - {FD} implies FD).

Anomalies in Unnormalized Databases

Normalization

Objectives: Minimize redundancy, eliminate anomalies, ensure dependency preservation (FDs enforceable without joins), and lossless join decomposition.

Steps to Convert 3NF to BCNF:

1. Identify FD X → Y violating BCNF (X not a superkey).

2. Decompose R into R₁(X ∪ Y) and R₂(R - (Y - X)).

3. Repeat until all relations satisfy BCNF.

Trade-off: BCNF may lose dependency preservation (some FDs not enforceable without joins).

Decomposition

• Lossless Join Decomposition: R decomposed into R₁, R₂ is lossless if (R₁ ∩ R₂) → R₁ or (R₁ ∩ R₂) → R₂ (using FDs).

  Test: Compute (R₁ ∩ R₂)⁺ under F; if it includes all attributes of R₁ or R₂, lossless.

• Dependency Preserving: Union of FDs from all decomposed relations implies original F.

• Achieving Both: Not always possible (BCNF may sacrifice dependency preservation). 3NF decomposition always achieves both.

Fourth Normal Form (4NF)

• Handles Multivalued Dependencies (MVD): X ↠ Y means for fixed X, Y values independent of other attributes.

  Example: Employee(EmpID, Skill, Language) with EmpID ↠ Skill and EmpID ↠ Language (skills and languages independent).

• 4NF: For every nontrivial MVD X ↠ Y, X must be a superkey.

  Decompose R into R₁(X ∪ Y) and R₂(X ∪ (R - Y)).

V. TRANSACTION MANAGEMENT

Transaction & ACID Properties

• Transaction: Logical unit of work (sequence of read/write operations) with atomicity.

• ACID:

  • Atomicity: All or nothing (COMMIT/ABORT).

    Example: Transfer fails → both accounts unchanged.

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

    Example: Account(Balance) must have Balance ≥ 0.

  • Isolation: Concurrent transactions appear serial (no interference).

    Example: Two transfers on same account don’t overwrite each other.

  • Durability: Committed changes survive system failure (written to disk).

    Example: Log flushed to disk before commit returns.

Transaction States & State Diagram

Active → Partially Committed → Committed

   ↓         ↓

   Failed ← Aborted

• Active: Executing.

• Partially Committed: Final operation done, changes may be in buffer.

• Committed: Changes permanent (log on disk).

• Failed: Abort due to constraint violation/system crash.

• Aborted: Rolled back; may restart.

Schedules & Serializability

• Schedule (History): Order of operations from multiple transactions.

• Serial Schedule: Transactions execute one after another (no overlap). Conflict serializable if equivalent to some serial schedule.

• Conflict Serializability:

  • Two operations conflict if:

    (1) From different transactions,

    (2) Access same data,

    (3) At least one is WRITE.

  • Precedence Graph:

    Nodes = transactions. Edge Tᵢ → Tⱼ if Tᵢ writes X and Tⱼ reads/writes X later.

    Conflict serializable iff no cycle.

• View Serializability: Equivalent via view equivalence (same reads, same final writes). Harder to test (NP-complete).

• Recoverable Schedule: If Tᵢ reads X written by Tⱼ, then Tᵢ commits only after Tⱼ commits.

• Cascadeless: No transaction reads data written by uncommitted transaction.

• Strict: No transaction reads/writes data written by uncommitted transaction (uses exclusive locks until commit).

Concurrency Control

• Need: Improve throughput, resource utilization. Without control → lost update, dirty read, unrepeatable read, phantom read.

• Impact on Performance: Locking reduces concurrency (blocks transactions) but ensures correctness.

• Locking Techniques:

  • Shared (S) Lock: Multiple transactions can read (READ).

  • Exclusive (X) Lock: Exclusive access for READ/WRITE.

• Two-Phase Locking (2PL):

  • Growing Phase: Acquire locks, no release.

  • Shrinking Phase: Release locks, no acquisition.

  • Guarantees conflict serializability but not cascadeless/strict.

  • Strict 2PL: Hold all X-locks until commit (ensures strict schedule).

  • Conservative 2PL: Acquire all locks at start (prevents deadlock but reduces concurrency).

• Timestamp-Based Concurrency Control:

  • Each transaction gets timestamp TS(T) (start time).

  • Each data item X has RTS(X), WTS(X) (read/write timestamps).

  • Rules:

    • If TS(T) < WTS(X), abort T (write too old).

    • If TS(T) < RTS(X), abort T (read too old).

    • Else allow, update timestamps.

• Validation-Based (Optimistic):

  • Phases:

    1. Read: Read from DB, write to private workspace.

    2. Validation: Check if conflicts with committed transactions.

    3. Write: If valid, apply writes; else abort.

  • Validation: Tᵢ validates against transactions Tⱼ that committed during Tᵢ’s execution. Tᵢ succeeds if no Tⱼ wrote data read by Tᵢ.

• Multiple Granularity Locking (MGL):

  • Locking at hierarchical levels (database → file → page → record).

  • Intention Locks:

    • IS (Intention Shared): Some S locks on lower level.

    • IX (Intention Exclusive): Some X locks on lower level.

    • SIX (Shared + Intention Exclusive): S lock on this level, IX on lower.

  • Lock Compatibility Table: Ensures lock requests consistent with ancestors’ locks.

Deadlock Management

• Deadlock: Cycle in wait-for graph (each transaction waits for another in cycle).

• Prevention:

  • Resource Ordering: Assign global order to resources; request in order.

  • Preemption: Force abort victim transaction.

• Avoidance:

  • Wait-Die: Older transaction waits; younger transaction aborts.

  • Wound-Wait: Older transaction aborts younger; younger waits.

• Detection & Resolution:

  • Wait-For Graph: Periodic cycle detection.

  • Victim Selection: Choose transaction to abort (min cost, low progress).

  • Rollback: Abort victim, restart later.

• Blocking vs Deadlock:

  • Blocking: T₁ holds lock X needed by T₂; T₂ waits.

  • Deadlock: T₁ waits for T₂, T₂ waits for T₁ (cycle).

Recovery System

• Need: System/Media failures (power loss, disk crash).

• Database Log:

  • Sequential file of log records (<T, X, old, new>).

  • Types:

    • Update: T writes X (old → new).

    • Commit/Abort: T commits/aborts.

    • Checkpoint: Snapshot of active transactions and dirty pages.

  • Importance:

    • Undo: Roll back uncommitted transactions (use old values).

    • Redo: Reapply committed transactions (use new values).

• Recovery Techniques:

  • Deferred Database Modification:

    • Writes made only at commit to DB.

    • Log: (T, X, new) only.

    • Recovery: Redo all committed transactions.

  • Immediate Database Modification:

    • Writes made as soon as operation executes (to DB & log).

    • Log: (T, X, old, new).

    • Recovery: Undo uncommitted (backward using old), Redo committed (forward using new).

• Checkpointing:

  • Purpose: Reduce recovery time (no need to scan entire log).

  • Checkpoint Record: Lists all active transactions and dirty buffer pages (modified but not written to disk).

  • Recovery: Start from last checkpoint; redo committed after checkpoint, undo uncommitted after checkpoint.

VI. STORAGE, INDEXING & FILE ORGANIZATION

File Organization & Access Methods

Indexing

• Purpose: Speed up queries without scanning entire table.

• Types:

  | Type | Key | Order | Example | |------------------------|----------------------------------|---------------------|---------------------------------| | Primary Index | PK (unique) | Sorted | Clustered index on RollNo. | | Secondary Index | Non-key attribute | May not be sorted | Index on Student(Dept). | | Clustering Index | Data stored in index order | Sorted | Table physically sorted on Dept. | | Non-clustering Index| Index separate from data | Sorted | Index file points to random data blocks. | | Dense Index | Entry for every search key | Sorted | Every RollNo has index entry. | | Sparse Index | Entry for some keys (e.g., block) | Sorted | Index entry per data block. |

[!TIP]

Primary index is always clustering and sparse (on PK, sorted data). Secondary index is usually non-clustering and dense.

B+ Tree Index

• Structure:

  • All leaves at same level; linked for range queries.

  • Internal nodes: (K₁, P₁, K₂, P₂, ..., Kₙ, Pₙ) where Kᵢ keys, Pᵢ pointers.

  • Leaves: (K₁, RID₁), (K₂, RID₂), ... (RID = record pointer).

• Properties:

  • Order d: Min d pointers, max 2d pointers (except root).

  • Height: O(log_d N) → fast search (O(log N) I/Os).

  • Insert/Delete: Split/merge nodes, propagate changes upward.

• Search: Start at root, follow pointers until leaf.

• Insert: Find leaf, insert; if overflow (2d+1 keys), split into two, promote median to parent.

• Delete: Find leaf, remove; if underflow (< d keys), merge/redistribute with sibling.

Hashing Techniques

• Static Hashing:

  • Buckets = h(K) mod N (N fixed).

  • Overflow: Linked list in bucket (performance degrades with collisions).

• Extendable Hashing:

  • Directory: Array of pointers to buckets.

  • Global depth i: Directory size 2ⁱ.

  • Local depth j: Bucket split count (≤ global depth).

  • Split: When bucket overflows, increase local depth; if j = i, double directory (increase global depth).

  • Advantage: No overflow chains; directory grows on demand.

• Linear Hashing:

  • No directory; use hash function hᵢ(K) = h(K) mod 2ⁱ * 2ⁱ (split round-robin).

  • Split: When bucket overflows, split next bucket in order.

  • Search: Use current i and split pointer s.

RAID (Redundant Array of Independent Disks)

Bitmap Indexing

• Use Case: Low-cardinality attributes (e.g., Gender, MaritalStatus).

• Structure: Bit vector per distinct value.

  Example: Gender (M/F):

  M: 1010... (1 if tuple is Male), F: 0101....

• Query: Bitwise AND/OR for conditions.

  Example: Gender='M' AND Dept='CS' → M_bitvector AND CS_bitvector.

• Pros: Fast set operations, efficient for OLAP.

• Cons: High space for high-cardinality; costly updates.

VII. ADVANCED TOPICS & EMERGING CONCEPTS

Distributed Databases

• Concepts:

  • Fragmentation:

    • Horizontal: Tuples split (e.g., Student(North), Student(South)).

    • Vertical: Attributes split (e.g., Student_Personal(Roll, Name), Student_Academic(Roll, Dept)).

    • Hybrid: Combination.

  • Replication: Copy fragments at multiple sites (improves availability, read performance).

• Challenges:

  • Data Distribution: Transparency (location, replication, fragmentation).

  • Concurrency Control: Distributed locking (2PL with distributed deadlock detection), timestamp.

  • Recovery: Two-Phase Commit (2PC) for atomic commit across sites:

    1. Prepare: Coordinator asks all sites if ready.

    2. Commit/Abort: If all ready, commit; else abort.

  • Distributed Query Processing: Optimize for data locality, minimize communication.

• Distributed Transaction Management: 2PC ensures atomicity across sites but blocking (coordinator failure).

Object-Oriented DBMS (OODBMS) vs. RDBMS

NoSQL Databases

• Characteristics:

  • Schema-less, horizontal scaling, BASE (Basic Availability, Soft state, Eventual consistency).

  • High write throughput, distributed by design.

• Types:

  • Document: JSON/BSON documents (e.g., MongoDB).

  • Key-Value: Simple (key, value) pairs (e.g., Redis).

  • Column-Family: Column-oriented (e.g., Cassandra).

  • Graph: Nodes/edges (e.g., Neo4j).

Triggers in SQL

• Definition: Stored procedure that automatically executes on INSERT/UPDATE/DELETE.

• Syntax:

  
  CREATE TRIGGER trigger_name
  
  BEFORE/AFTER INSERT/UPDATE/DELETE ON table
  
  FOR EACH ROW
  
  BEGIN
  
    -- SQL statements (can reference OLD, NEW)
  
  END;
  
  

• Use Cases:

  • Maintain summary tables (e.g., update TotalSales after OrderItems insert).

  • Enforce complex integrity constraints.

  • Audit logs.

Views

• Definition: Virtual table from SELECT query. Stored as query, not data.

• Creation: CREATE VIEW ViewName AS SELECT ....

• Updatability:

  • Simple views (single table, no aggregates, no DISTINCT) are updatable.

  • Complex views require INSTEAD OF triggers.

• Benefits: Security (restrict columns/rows), simplify queries, logical independence.

Data Dictionary / System Catalog

• Purpose: Metadata repository (schema, constraints, user info, statistics).

• Contents:

  • Table/column names, types, sizes.

  • Indexes, views, constraints.

  • User privileges, statistics (for optimizer).

• Access: System tables (e.g., INFORMATION_SCHEMA in SQL).

Assertions

• Definition: Global constraints (not tied to single tuple/table).

  Example: “Total number of employees in a department ≤ 100.”

• Syntax: CREATE ASSERTION AssertName CHECK (condition).

• Rarely used (performance overhead; often enforced via triggers).

Web & Mobile Databases

• Challenges:

  • Intermittent connectivity: Sync mechanisms.

  • Limited resources: Battery, storage, CPU.

  • Security: Data encryption, secure transmission (HTTPS).

  • Concurrency: Offline edits → conflict resolution (last-write-wins, merging).

Hierarchical Queries (Oracle CONNECT BY)

• Purpose: Query hierarchical data (e.g., organization chart).

• Syntax:

  
  SELECT ... FROM table
  
  START WITH condition
  
  CONNECT BY PRIOR child = parent;
  
  

• Pseudocolumns: LEVEL (depth), SYS_CONNECT_BY_PATH (path string).

Oracle Application Express (APEX)

• Definition: Low-code web development platform for Oracle DB.

• Features:

  • Browser-based, no client install.

  • Rapid app development (forms, reports, charts).

  • Integrated with Oracle DB (PL/SQL backend).

• Use: Build internal DB-driven web apps quickly.

[!TIP]

Exam Focus:

• Distributed DB: Always mention 2PC for atomic commit.

• NoSQL: Know BASE vs ACID, and types (Document, Key-Value, etc.).

• Triggers: Distinguish BEFORE (validate/modify) vs AFTER (audit).

• Views: Updatability conditions (single table, no aggregates).