UNIT 5: DATABASE MANAGEMENT SYSTEM

Comprehensive Short Notes Based on RGPV Past Papers (Jun 2025–Jun 2022)

1. Introduction to Database Systems

Core Definitions

• Data: Raw facts representing real-world entities (e.g., student name, roll number).

• Database: Organized collection of structured data stored electronically.

• DBMS: Software system that defines, creates, maintains, and controls access to a database (e.g., Oracle, MySQL).

File System vs DBMS

Advantages of DBMS

• Reduced data redundancy & inconsistency.

• Data sharing among multiple users/applications.

• Integrity constraints enforce business rules.

• Backup, recovery, and crash protection.

• Concurrent access with isolation.

• Data abstraction via three-level architecture.

Disadvantages of File-Based Systems

• Data redundancy → inconsistency.

• Program-data dependence (changes in file structure break programs).

• Limited concurrent access.

• No security or integrity enforcement.

• No efficient querying or indexing.

Applications

• Banking (transactions, accounts).

• Airlines (reservations, scheduling).

• Universities (student records, course registration).

• Healthcare (patient records, appointments).

[!TIP]

Exam Focus: Compare File System vs DBMS using a table (frequently asked). Highlight data independence and integrity constraints as key differentiators.

2. DBMS Architecture and Data Models

Three-Level Architecture

1. External Level (View Level): User-specific views of the database.

2. Conceptual Level (Logical Level): Entire database structure (entities, relationships, constraints).

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

Mappings:

• External-Conceptual Mapping: Shields users from changes in logical structure.

• Conceptual-Internal Mapping: Shields logical design from physical storage changes.

Schemas vs Instances

• Schema (Intension): Logical design (structure) of the database (e.g., Student(Roll_no, Name, Dept)).

• Instance (Extension): Actual data stored at a moment (set of tuples).

Data Independence

• Logical Data Independence: Changes to conceptual schema (e.g., adding a new attribute) do not affect external schemas or applications.

• Physical Data Independence: Changes to internal schema (e.g., file organization, indexes) do not affect conceptual or external schemas.

DBMS Components

• Storage Manager: Handles file storage, buffer management, file organization.

• Query Processor: Parses queries, optimizes execution plans.

• Transaction Manager: Concurrency control, recovery (ACID).

• Catalog Manager: Stores metadata (data dictionary).

Data Models Overview

Database Users & Tools

• DBA (Database Administrator): Manages DBMS, security, backup, performance tuning.

• Designers: Create conceptual/logical schemas (ER modeling, normalization).

• End-Users: Query data via applications or SQL interfaces.

• Application Programmers: Write programs that interact with DBMS.

Data Dictionary & System Catalog

• Data Dictionary: Metadata about database objects (tables, columns, types).

• System Catalog: Stored in DBMS, queried via system tables (e.g., INFORMATION_SCHEMA).

Dynamic Performance Views

• Oracle-specific views (e.g., V$SESSION, V$SQL) for real-time monitoring of performance metrics.

[!TIP]

Exam Focus: Three-level architecture and data independence are high-frequency topics. Draw and explain the architecture with mappings.

3. Entity-Relationship (ER) Modeling

Basic Elements

• Entity: Real-world object with independent existence (e.g., Student, Course).

• Attribute: Property of an entity (e.g., Roll_no, Name).

• Relationship: Association among entities (e.g., Enrolls between Student and Course).

Attribute Types

Relationship Types

• One-to-One (1:1): One entity instance associated with at most one of another.

• One-to-Many (1:M): One entity instance associated with many of another (most common).

• Many-to-Many (M:N): Multiple instances on both sides; requires associative entity.

Weak vs Strong Entity Sets

• Strong Entity: Has a primary key (e.g., Student with Roll_no).

• Weak Entity: No primary key; depends on strong entity for existence (e.g., Dependent of Employee). Uses partial key + foreign key to owner.

Specialization & Generalization

• Specialization: Top-down process (superclass → subclasses).

• Generalization: Bottom-up process (subclasses → superclass).

• Both use disjoint (subclasses non-overlapping) or overlapping constraints.

Aggregation

• Treats a relationship as an entity for higher-level relationships (e.g., Enrolls as entity for Proficiency relationship).

ER Diagram Notations

• Rectangle: Entity.

• Ellipse: Attribute (underlined for key).

• Diamond: Relationship.

• Double rectangle: Weak entity.

• Double diamond: Aggregation.

• Lines: Connect entities to relationships (with cardinality ratios).

Mapping ER to Relational Schema

1. Strong Entity: Table with all simple/composite attributes; primary key from key attribute(s).

2. Weak Entity: Table with partial key + foreign key to owner; primary key = (foreign key, partial key).

3. 1:1 Relationship: Merge into one table or add foreign key to either side (preferably with total participation).

4. 1:M Relationship: Add foreign key on the “many” side.

5. M:N Relationship: Create new table with foreign keys from both entities; primary key = combination of FKs.

6. Specialization:

   • Option 1: Separate table for each subclass with PK = PK of superclass.

   • Option 2: Single table with discriminator attribute (type).

7. Aggregation: Treat relationship as entity; create table for relationship set.

Integrity Constraints in ER

• Key Constraints: Unique identification of entities.

• Participation Constraints: Total (every entity participates) vs Partial.

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

[!TIP]

Exam Focus: Mapping ER to relational schema is crucial. Practice with examples: University (Student, Course, Enrolls), Hospital (Patient, Doctor, Treatment).

4. Relational Model

Relational Schema & Instance

• Schema: R(A₁, A₂, ..., Aₙ) where R is relation name, Aᵢ are attributes.

• Instance: Set of tuples (rows) at a given time.

Types of Keys

Integrity Constraints

• Entity Integrity: Primary key cannot be NULL.

• Referential Integrity: Foreign key value must match primary key value in referenced table or be NULL.

• Domain Integrity: Attribute values within defined domain (type, range, NOT NULL).

Relational Algebra Operations
Fundamental Operations

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

2. Projection (π): π_{A₁,...,Aₖ}(R) → specific attributes, duplicates removed.

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

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

5. Cartesian Product (×): R × S → all concatenations of tuples from R and S.

6. Rename (ρ): ρ_{new}(R) → rename relation or attributes.

Join Operations

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

• Theta Join (⋈_θ): R ⋈_θ S → join with general condition θ.

• Equi Join: Theta join with equality only.

• Outer Joins:

  • Left Outer Join: All tuples from left, NULL for non-matching right.

  • Right Outer Join: All tuples from right, NULL for non-matching left.

  • Full Outer Join: All tuples from both, NULL where no match.

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⟩ | ∃s, d (⟨s, n, d⟩ ∈ Student ∧ d = 'CS') }.

Relational Algebra vs Calculus

• Algebra: Procedural (how to compute).

• Calculus: Declarative (what to compute).

• Relational Completeness: All queries expressible in relational calculus can be expressed in relational algebra.

Degree & Cardinality

• Degree: Number of attributes in a relation (arity).

• Cardinality: Number of tuples in an instance.

[!TIP]

Exam Focus: Relational algebra queries are common (use Sailor/Reserves or Student/Course schemas). Practice σ, π, ⋈, and outer joins.

5. SQL and Query Languages

SQL Categories

• DDL (Data Definition Language): Define/modify schema.

  • CREATE TABLE, ALTER TABLE, DROP TABLE, TRUNCATE, RENAME.

• DML (Data Manipulation Language): Query/modify data.

  • SELECT, INSERT, UPDATE, DELETE.

• DCL (Data Control Language): Access control.

  • GRANT, REVOKE.

• TCL (Transaction Control Language): Manage transactions.

  • COMMIT, ROLLBACK, SAVEPOINT.

SELECT Query Syntax

SELECT [DISTINCT] columns

FROM tables

[WHERE condition]

[GROUP BY columns]

[HAVING condition]

[ORDER BY columns [ASC|DESC]];

Aggregate Functions

• COUNT(*), SUM(column), AVG(column), MIN(column), MAX(column).

• Used with GROUP BY; HAVING filters groups.

Set Operators

• UNION: Combines results, removes duplicates.

• INTERSECT: Common tuples.

• EXCEPT (or MINUS in Oracle): Tuples in first but not second.

• All require union-compatible relations (same degree, compatible domains).

Joins

• INNER JOIN: SELECT * FROM A INNER JOIN B ON A.id = B.id;

• LEFT JOIN: SELECT * FROM A LEFT JOIN B ON A.id = B.id;

• RIGHT JOIN: SELECT * FROM A RIGHT JOIN B ON A.id = B.id;

• FULL OUTER JOIN: SELECT * FROM A FULL OUTER JOIN B ON A.id = B.id;

• SELF JOIN: Join table with itself (e.g., employee-manager).

• CROSS JOIN: Cartesian product (SELECT * FROM A CROSS JOIN B;).

Subqueries

• Non-correlated: Executed once, result used by outer query.

• Correlated: Executed for each outer row, references outer query columns.

• Operators: IN, NOT IN, ANY, ALL, EXISTS, NOT EXISTS.

Special Operators

• LIKE: Pattern matching (% = any string, _ = single char).

• ANY/ALL: Compare with set (e.g., salary > ANY (SELECT salary FROM ...)).

• EXISTS: Check if subquery returns rows (efficient for correlated subqueries).

Views

• Creation: CREATE VIEW view_name AS SELECT ...;

• Updatable Views: Single table, no aggregates, no DISTINCT, key preserved.

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

Triggers

• Stored procedures activated on INSERT/UPDATE/DELETE.

• Syntax (Oracle example):

  
  CREATE TRIGGER trig_name
  
  AFTER INSERT ON OrderItems
  
  FOR EACH ROW
  
  BEGIN
  
    UPDATE Orders 
  
    SET total_amount = total_amount + :NEW.amount
  
    WHERE order_id = :NEW.order_id;
  
  END;
  
  

Assertions & Constraints

• CHECK: Domain constraint (CHECK (salary > 0)).

• UNIQUE: Ensure uniqueness (allow NULL).

• NOT NULL: Disallow null values.

• Assertions: Schema-level CHECK (rarely used).

Hierarchical Queries (Oracle)

• CONNECT BY PRIORE child = parent to traverse tree.

• START WITH specifies root.

  Example:

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

SQL Examples from Past Papers

• Employee/Department Schema:

  
  -- Employees in CS department
  
  SELECT Name FROM Student WHERE Dept = 'CS';
  
  
  
  -- Employees with salary between 10000 and 20000
  
  SELECT * FROM Emp WHERE Salary BETWEEN 10000 AND 20000;
  
  
  
  -- Second highest salary
  
  SELECT MAX(Salary) FROM Emp 
  
  WHERE Salary < (SELECT MAX(Salary) FROM Emp);
  
  
  
  -- Departments with no employees
  
  SELECT Dname FROM Dept 
  
  WHERE Dname NOT IN (SELECT Dname FROM Emp);
  
  

[!TIP]

Exam Focus: Joins (especially LEFT/RIGHT/FULL OUTER), subqueries (correlated vs non-correlated), and aggregate functions with GROUP BY/HAVING are frequently tested.

6. Database Design and Normalization

Need for Normalization

• Minimize redundancy.

• Avoid insertion, update, deletion anomalies.

• Ensure data consistency.

Anomalies

Functional Dependencies (FDs)

• Definition: X → Y means attribute set X uniquely determines attribute set Y in relation R.

• Properties:

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

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

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

  • Union: If X → Y and X → Z, then X → YZ.

  • Decomposition: If X → YZ, then X → Y and X → Z.

  • Pseudotransitivity: If X → Y and YZ → W, then XZ → W.

FD Closure (F⁺)

Set of all FDs implied by F. Algorithm:

1. Start with X⁺ = X.

2. Repeatedly add attribute A to X⁺ if there exists FD Y → A with Y ⊆ X⁺.

3. Stop when no more attributes can be added.

Armstrong’s Axioms

• Reflexivity, Augmentation, Transitivity (sufficient to prove all other properties).

Minimal Cover of FDs

1. Each FD has a single attribute on RHS.

2. No extraneous attributes on LHS (remove attribute A from X if X - {A} → Y still holds).

3. Remove redundant FDs.

Normal Forms

Multi-Valued Dependencies (MVD)

• X →→ Y means that for a given X, the set of Y values is independent of other attributes.

• Example: Student(Roll_no, Course, Hobby) → Roll_no →→ Course and Roll_no →→ Hobby (courses and hobbies independent).

Decomposition

• Lossless Join Decomposition: R decomposed into R₁, R₂ if R₁ ∩ R₂ → R₁ or R₁ ∩ R₂ → R₂.

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

• Steps to Convert 3NF to BCNF:

  1. Find FD X → Y where X is not a superkey.

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

  3. Repeat for R₁ and R₂ until all relations are BCNF.

Normalization Example (Jun 2025 Paper)

Given: Employee(Emp_ID, Name, Dept, Salary, Project_ID, Project_Name, Manager_ID)

• FDs: Emp_ID → Name, Dept, Salary, Project_ID, Project_Name, Manager_ID; Project_ID → Project_Name, Manager_ID; Dept → Manager_ID? (Assume).

• 2NF: If composite key? Here Emp_ID is key → already 2NF.

• 3NF: Check transitive: Emp_ID → Dept, Dept → Manager_ID → transitive dependency. Decompose:

  Emp(Emp_ID, Name, Dept, Salary, Project_ID)

  Project(Project_ID, Project_Name, Manager_ID)

  Dept(Dept, Manager_ID)

• BCNF: In Dept, Dept → Manager_ID but Dept not superkey? If Dept is key, then BCNF. Otherwise decompose further.

Determining Highest Normal Form

Check each FD against normal form conditions.

Example: R(A,B,C,D,E,F,G,H) with FDs:

AB → CD, D → EG, F → H, C → EF, H → A, G → B, A → B.

• Candidate keys? Compute closure.

• Check for partial, transitive dependencies, etc.

[!TIP]

Exam Focus: Normalization (1NF to BCNF) with FDs is heavily tested. Practice converting relations to 2NF/3NF/BCNF. Know lossless join and dependency preserving decomposition.

7. Query Processing and Optimization

Phases of Query Processing

1. Parsing & Translation:

   • Parse query, check syntax.

   • Translate to internal representation (e.g., relational algebra tree).

2. Optimization:

   • Generate logically equivalent expressions.

   • Choose execution plan with lowest estimated cost.

3. Execution:

   • Execute plan using algorithms (e.g., nested loop join, hash join).

Why Optimization?

• Different evaluation orders have vastly different costs (I/O, CPU).

• Example: π_{name}(σ_{dept='CS'}(Student) ⋈ Course)

  • Bad: Join all, then select, then project.

  • Good: Select first (reduces tuples), then join, then project.

Cost Measures

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

• CPU Cost: Tuple processing, comparison.

• Communication Cost: In distributed DBs (data transfer between sites).

Optimization Techniques

• Heuristic-Based (Rule-Based):

  • Push selections (σ) and projections (π) down the tree.

  • Perform most restrictive operations first.

  • Replace Cartesian product + selection with join.

• Cost-Based:

  • Use statistics: |R| (tuples), B(R) (pages), V(A,R) (distinct values of attribute A).

  • Estimate cost of each plan using formulas.

  • Choose plan with minimal cost.

Expression Evaluation Plans

• Tree structure with operators as nodes.

• Order of operations affects intermediate result sizes.

Select, Project, Join Algorithms

• Selection:

  • Linear Scan: Read all pages.

  • Index Scan: Use index if available (cost = index height + tuples).

• Projection: Duplicate elimination (sorting or hashing).

• Join:

  • Nested Loop Join: O(|R| × |S|) I/O.

  • Block Nested Loop: O(B(R) + B(R)×B(S)).

  • Index Join: Use index on join attribute.

  • Sort-Merge Join: Sort both on join key, then merge (O(B(R)logB(R) + B(S)logB(S))).

  • Hash Join: Hash both tables, then join buckets (O(B(R) + B(S)) if memory sufficient).

Sorting in Query Processing

• External sorting for large relations:

  • Pass 0: Read M pages, sort in memory, write ⌈B(R)/M⌉ sorted runs.

  • Subsequent passes: Merge M-1 runs at a time.

  • Number of passes = ⌈log_{M-1}(⌈B(R)/M⌉)⌉.

Indexing & Performance

• Indexes speed up selections and joins (especially equality).

• Clustering index (primary) vs non-clustering (secondary).

Complexity Measures

• Time complexity of operations:

  • Selection: O(B(R)) (linear scan), O(log B(R)) (index).

  • Join: O(|R|×|S|) (nested loop), O(B(R) + B(S)) (hash join).

[!TIP]

Exam Focus: Query optimization (heuristic vs cost-based) and join algorithms are key. Compare sort-merge vs hash join with cost formulas.

8. Transaction Management

Transaction Concept

• Logical unit of work (e.g., transfer money from A to B).

• Must be atomic (all or nothing).

ACID Properties

Transaction States

1. Active: Executing.

2. Partially Committed: Final operation executed, changes temporary.

3. Committed: Changes permanent.

4. Failed: Error occurs, cannot proceed.

5. Aborted: Rolled back, may be restarted.

Schedules

• Serial: Transactions execute one after another.

• Non-serial: Operations interleaved.

Serializability

• Conflict Serializability:

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

  • Precedence Graph: Nodes = transactions, edge Ti → Tj if Ti’s operation precedes conflicting Tj’s.

  • Schedule is conflict-serializable iff graph is acyclic.

• View Serializability: More complex; equivalent if:

  1. Same initial reads.

  2. Same final writes.

  3. Same read-from relationships.

Recoverable Schedules

• If Tj reads data written by Ti, then Tj commits only after Ti commits.

Cascadeless & Strict Schedules

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

• Strict: No transaction writes data written by uncommitted transaction (stronger).

Transaction Example (Jun 2023 Paper)

T1: Transfer ₹1000 from A to B.

T2: Transfer 10% from A to B.

Initial: A=2000, B=3000.

Concurrent schedule:

T1: R(A), R(B), A:=A-1000, B:=B+1000, W(A), W(B)

T2: R(A), A:=A*0.9, W(A), R(B), B:=B+A_old, W(B)

Final values depend on interleaving; may violate consistency.

[!TIP]

Exam Focus: ACID properties with examples, conflict serializability (precedence graph), and recoverable/cascadeless schedules are common.

9. Concurrency Control

Need for Concurrency Control

• Prevent inconsistencies when multiple transactions execute concurrently.

Concurrency Problems

Locking Techniques

• Lock Modes:

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

  • Exclusive (X): For writing; only one transaction can hold X-lock.

• Two-Phase Locking (2PL):

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

  • Shrinking Phase: Transaction releases locks (no new acquires).

  • Ensures conflict serializability.

  • Variants:

    • Rigorous 2PL: All locks (S and X) held until commit (strict).

    • Conservative 2PL: Acquire all locks at start (no waiting).

Deadlock

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

• Prevention:

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

  • Preemption: Force transaction to release locks (e.g., youngest aborted).

• Avoidance:

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

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

• Detection & Resolution:

  • Wait-For Graph: Nodes = transactions, edge Ti → Tj if Ti waits for Tj. Cycle = deadlock.

  • Resolution: Choose victim (e.g., youngest, least progress) to abort.

Timestamp-Based Concurrency Control

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

• Each data item X has:

  • RTS(X): Read timestamp (largest TS of any transaction that read X).

  • WTS(X): Write timestamp (largest TS of any transaction that wrote X).

• Protocol:

  • Transaction Ti wants to read X: if TS(Ti) < WTS(X), abort (younger reads older write).

  • Transaction Ti wants to write X: if TS(Ti) < RTS(X) or TS(Ti) < WTS(X), abort.

• Ensures conflict serializability in timestamp order.

Validation-Based (Optimistic) Concurrency Control

• Read Phase: Transaction reads data, writes to local buffer (no locks).

• Validation Phase: Check if conflicts with committed transactions.

  • If Ti’s read set overlaps with Tj’s write set (Tj committed during Ti’s execution), Ti aborts.

• Write Phase: If valid, write changes; else abort and restart.

• Suitable for low-conflict workloads.

Multiple Granularity Locking (MGL)

• Lock at different levels: database → table → page → row.

• Intention Locks:

  • IS (Intention Shared): Indicates S-lock at lower level.

  • IX (Intention Exclusive): Indicates X-lock at lower level.

  • SIX (Shared with Intention Exclusive): S-lock at current level, X-lock at lower level.

• Lock Compatibility: IS/IX compatible with S/IX at higher levels.

Impact on Transaction Performance

• Locking reduces concurrency (waiting).

• Deadlocks cause aborts/restarts.

• Timestamp/optimistic avoid deadlocks but may increase aborts.

Comparison of Techniques

[!TIP]

Exam Focus: Two-phase locking (2PL) and deadlock handling (prevention, detection) are essential. Draw wait-for graph for deadlock detection.

10. Database Recovery

Database Logs

• Record all changes to database.

• Types:

  • Update Logs: Before-image and after-image (for undo/redo).

  • Compensation Logs: For undo operations (in ARIES).

• Log Records:

  • <BEGIN T>: Transaction start.

  • <T, X, old_value, new_value>: Update.

  • <COMMIT T>: Commit.

  • <ABORT T>: Abort.

• Log Maintenance:

  • Immediate: Write log record to stable storage before data change (write-ahead logging, WAL).

  • Deferred: Write log after data change (rare).

Recovery Strategies

• Deferred Database Modification:

  • Changes written only at commit.

  • Recovery: Redo all committed transactions (no undo needed).

• Immediate Database Modification:

  • Changes written as they occur.

  • Recovery: Undo uncommitted transactions, Redo committed transactions.

Checkpoints

• Purpose: Reduce recovery time by limiting log scan.

• How: Periodically:

  1. Flush all dirty pages to disk.

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

• Recovery starts from last checkpoint.

Recovery Algorithm (Immediate Modification)

1. Analysis Phase:

   • Find last checkpoint.

   • Identify set U of uncommitted transactions (active at crash).

   • Identify set D of dirty pages (modified by transactions in U).

2. Redo Phase:

   • Scan log forward from checkpoint.

   • For each update <T, X, old, new>, if X ∈ D or T committed, redo new.

3. Undo Phase:

   • Scan log backward from end.

   • For each update by T ∈ U, undo old.

   • Write compensation log records.

Shadow Paging

• Maintain two copies: current and shadow.

• On transaction start, shadow = copy of current.

• Changes made to current only.

• On commit:

  1. Flush all modified pages of current to disk.

  2. Update pointer to make current the new shadow.

• No logs needed, but high overhead (copy entire pages).

Log-Based Recovery Protocol

• Use write-ahead logging (WAL): log record written before data page.

• Ensures durability and atomicity via undo/redo.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics)

• Advanced method:

  • Analysis: Build dirty page table and transaction table.

  • Redo: Repeat history (reapply all updates).

  • Undo: Roll back loser transactions in reverse order.

• Uses compensation log records (CLRs) to record undo actions.

[!TIP]

Exam Focus: Recovery phases (analysis, redo, undo) and checkpoints are important. Compare deferred vs immediate modification.

11. Storage and Indexing

File Organization Methods

Indexing

• Purpose: Speed up query processing (reduce I/O).

• Primary Index: On sequential file, sparse (one entry per block).

• Secondary Index: On any file, dense (entry per record) or sparse.

• Clustering Index: Determines physical order of data (one per table).

• Non-clustering Index: Logical order, data stored separately.

Dense vs Sparse Indexes

• Dense: Entry for every record (search fast, large index).

• Sparse: Entry for every block (smaller, but extra I/O to find record).

Single-level vs Multilevel Indexes

• Single-level: Direct index on data (may be large).

• Multilevel: Index on index (e.g., B⁺-tree). Reduces I/O (root in memory).

B-trees & B⁺-trees

• B-tree: Balanced tree, all nodes at same level.

  • Node structure: [P₀, K₁, P₁, K₂, ..., Pₖ₋₁, Kₖ, Pₖ] where Kᵢ keys, Pᵢ pointers.

  • Search: O(logₖ n) where k = fanout.

  • Insertion: Split node if full, propagate up.

  • Deletion: Merge or redistribute.

• B⁺-tree:

  • All data in leaf nodes; internal nodes only keys.

  • Leaves linked sequentially (fast range queries).

  • More efficient for databases than B-tree.

Hashing Techniques

• Static Hashing:

  • Fixed number of buckets B.

  • Hash function h(key) → bucket.

  • Overflow buckets for collisions.

  • Inner attribute: Hash key.

  • Outer attribute: Non-key used for overflow.

• Extendable Hashing:

  • Directory with pointers to buckets.

  • Directory size 2^d, bucket split when overflow.

  • Global depth d, local depth per bucket.

  • Example: Roll numbers hashed, directory doubles when needed.

• Linear Hashing:

  • Incremental splitting without directory.

  • Round-robin splitting of buckets.

Bitmap Indexing

• Bit vector for each attribute value (1 if present, 0 otherwise).

• Efficient for low-cardinality attributes (e.g., gender, status).

• Fast set operations (AND, OR, NOT) via bitwise operations.

RAID (Redundant Array of Independent Disks)

Heap Files

• Advantages: Simple, fast inserts, no maintenance.

• Disadvantages: Slow searches (full scan), no order, no clustering.

[!TIP]

Exam Focus: B⁺-trees (structure, search, insertion, deletion) and hashing (extendable hashing with directory) are important. Compare dense vs sparse indexes.

12. Distributed Databases

Concepts & Architecture

• Data spread across multiple sites (geographically dispersed).

• Appears as single database to users.

• Architecture: Local DBMS at each site + global DBMS for transparency.

Data Fragmentation

• Horizontal: Subsets of rows (e.g., Employee split by region).

• Vertical: Subsets of columns (e.g., Employee split into (ID, Name) and (Dept, Salary)).

• Hybrid: Combination of both.

Data Replication

• Copies of data at multiple sites.

• Strategies:

  • Full replication: All sites have full copy.

  • Partial replication: Subset of data replicated.

• Transparency: Users unaware of location/replication (location transparency, replication transparency).

Distributed Query Processing

1. Translation: Query → distributed relational algebra.

2. Fragmentation & Location: Replace global relations with fragment relations, note sites.

3. Global Optimization: Choose sites for operations to minimize communication (e.g., ship fragments to common site).

4. Local Optimization: Each site optimizes its subquery.

Distributed Transaction Management

• Atomicity: All sites commit or abort.

• Commit Protocols:

  • Two-Phase Commit (2PC):

    • Phase 1 (Prepare): Coordinator asks all participants to prepare.

    • Phase 2 (Commit/Abort): If all ready, commit; else abort.

    • Blocking: Participants may wait indefinitely if coordinator fails.

  • Three-Phase Commit (3PC):

    • CanCommit?, PreCommit, DoCommit.

    • Non-blocking but assumes no failures during commit phase.

• Concurrency Control:

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

  • Timestamp Ordering: Global timestamps.

  • Optimistic: Validation across sites.

• Recovery:

  • Each site has local logs and checkpoints.

  • Global recovery coordinates using 2PC outcomes.

Challenges

• Heterogeneity: Different DBMSs, data models.

• Distribution: Network latency, failures.

• Integrity: Constraints across sites (hard to enforce).

• Security: Multiple sites increase exposure.

Examples

• Distributed banking (ATMs across branches).

• Global airline reservation (flights, hotels, cars).

[!TIP]

Exam Focus: Data fragmentation (horizontal/vertical), 2PC protocol, and distributed query processing steps are key.

13. Advanced Topics and Emerging Trends

Object-Oriented DBMS (OODBMS) vs RDBMS

NoSQL Databases

• Characteristics:

  • Schema-less (dynamic columns).

  • Horizontal scaling (sharding).

  • BASE properties (Basically available, Soft state, Eventual consistency).

  • High performance for specific workloads.

• Types:

  • Document: JSON/BSON documents (MongoDB).

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

  • Column: Column families (Cassandra).

  • Graph: Nodes and edges (Neo4j).

• Advantages over RDBMS:

  • Scalability (distributed by design).

  • Flexibility (no fixed schema).

  • Performance for unstructured/semi-structured data.

Web and Mobile Databases

• Issues:

  • Connectivity (intermittent).

  • Security (data in transit/at rest).

  • Synchronization (offline changes).

  • Limited resources (mobile).

• Technologies:

  • SQLite (embedded mobile DB).

  • Cloud sync (Firebase, Couchbase Mobile).

  • RESTful APIs for web access.

Oracle Application Express (APEX)

• Low-code development platform for Oracle DB.

• Web-based, no client install.

• Rapid application development with wizards, drag-and-drop.

• Built on Oracle DB, uses PL/SQL.

Data Warehousing & OLAP

• Data Warehouse: Central repository of integrated data from multiple sources (ETL process).

• OLAP (Online Analytical Processing): Multidimensional queries (slice, dice, pivot).

• Schemas:

  • Star: Fact table + dimension tables.

  • Snowflake: Normalized dimensions.

Big Data & Databases

• Hadoop: HDFS (storage), MapReduce (processing).

• Spark: In-memory processing, faster than MapReduce.

• HBase: NoSQL database on Hadoop (column-family).

Cloud Databases

• DBaaS (Database as a Service): Managed by cloud provider (e.g., AWS RDS, Azure SQL).

• Benefits: Scalability, high availability, managed maintenance.

• Challenges: Security, vendor lock-in, network latency.

[!TIP]

Exam Focus: NoSQL vs RDBMS comparison, CAP theorem (if mentioned), and cloud databases are trending.

14. Database Administration and Tools

DBA Functions

1. Design & Implementation: Schema design, DBMS selection.

2. Security & Authorization: User accounts, privileges (GRANT/REVOKE).

3. Backup & Recovery: Strategies (full, incremental), testing recovery.

4. Performance Tuning: Indexing, query optimization, hardware.

5. Data Dictionary Management: Maintain metadata.

6. User Support: Training, troubleshooting.

Data Security & Authorization

• Authentication: User identification (passwords, biometrics).

• Authorization: Access control via privileges:

  • GRANT SELECT ON table TO user;

  • REVOKE UPDATE ON table FROM user;

• Views: Restrict access to subset of data.

• Encryption: Data at rest (TDE) and in transit (SSL/TLS).

Backup & Recovery Strategies

• Backup Types:

  • Full: Entire database.

  • Incremental: Changes since last full/incremental.

  • Differential: Changes since last full.

• Recovery: Restore from backup + apply logs (point-in-time recovery).

Performance Tuning

• Indexing: Add indexes on frequent query columns.

• Query Optimization: Rewrite inefficient queries, update statistics.

• Hardware: Faster disks (SSD), more memory.

• Configuration: Buffer pool size, log file size.

Data Dictionary Management

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

• Stores metadata: tables, columns, data types, constraints, users.

Dynamic Performance Views

• Oracle-specific: V$SESSION, V$SQL, V$SYSTEM_EVENT.

• Real-time metrics for monitoring (wait events, SQL execution stats).

Database Monitoring Tools

• Oracle: Enterprise Manager (OEM), SQL Developer.

• SQL Server: SQL Server Profiler, Activity Monitor.

• MySQL: SHOW PROCESSLIST, Performance Schema.

• General: Nagios, Zabbix (system-level).

[!TIP]

Exam Focus: DBA responsibilities and backup strategies are common. Know GRANT/REVOKE syntax and dynamic performance views (Oracle V$).

Final Note: These notes synthesize high-frequency exam topics from RGPV past papers (2022–2025). Focus on definitions, comparisons, SQL queries, normalization steps, ACID, concurrency control, and recovery algorithms. Use diagrams for ER, B⁺-tree, and three-level architecture in exams.

\boxed{\text{End of Unit 5 Notes}}