CS8492

Database Management Systems

7 Files
•
Updated Jan 2026
Download Progress 0/7 files
Unit 1
Notes Not downloaded 609 KB
Unit 2
Notes Not downloaded 1.1 MB
Unit 3
Notes Not downloaded 746 KB
Unit 4
Notes Not downloaded 564 KB
Unit 5
Notes Not downloaded 404 KB
Important Questions
Study Not downloaded 243 KB
Question Paper
Exam Not downloaded 4.9 MB
Academic Study Guide

Database Management Systems (DBMS) Comprehensive Academic Guide

Database Management Systems form the critical data-layer infrastructure for modern computing. This comprehensive guide covers Entity-Relationship (ER) modeling, relational algebra operations, schema normalization (1NF through BCNF), ACID transaction management, concurrency control protocols, and B+ tree physical storage indexing.

Unit-by-Unit Theoretical Revision

Unit 1: Data Models, Architecture & ER Modeling

A DBMS is a collection of software programs managing structured electronic data collections ensuring integrity, durability, and multi-user access.

  • Three-Schema Architecture: External / View Level (user views) → Conceptual / Logical Level (entities, relationships, constraints) → Internal / Physical Level (file organization, B+ trees, indexes). Ensures physical and logical data independence.
  • ER Model Concepts: Entities (strong vs weak), Attributes (simple, composite, multi-valued, derived), and Relationships (cardinality ratios: 1:1, 1:N, M:N; participation constraints: total vs partial).
  • Weak Entity Sets: Entities lacking a primary key of their own, identified using a discriminator (partial key) in conjunction with an identifying relationship and identifying owner entity.

Unit 2: Relational Model & Relational Algebra

  • Relational Model Concepts: Relations (tables), Tuples (rows), Attributes (columns), Domains (permitted atomic values), Candidate Keys, Primary Keys, and Foreign Keys (referential integrity).
  • Fundamental Relational Algebra Operations:
    • Select (σ): Unary operator filtering tuples satisfying predicate: σ_condition(R).
    • Project (Ï€): Unary operator extracting specified attribute columns, discarding duplicates: Ï€_attr_list(R).
    • Cartesian Product (×): Combines all tuples of R with all tuples of S.
    • Union (∪), Set Difference (−), and Intersection (∩): Requires union-compatible schemas.
    • Natural Join (⋈): Cartesian product followed by equality selection on shared attributes and duplicate column projection.

Unit 3: Database Design Theory & Normalization

Normalization decomposes relations with anomalies (insert, update, delete) into smaller relations preserving dependency and lossless join properties.

  • Functional Dependency (FD): X → Y holds if whenever two tuples agree on attribute set X, they must also agree on attribute set Y. Armstrong’s Axioms: Reflexivity, Augmentation, and Transitivity.
  • Normal Forms:
    • First Normal Form (1NF): All attribute values must be atomic (no repeating groups or multi-valued attributes).
    • Second Normal Form (2NF): Must be in 1NF and have no partial dependencies (no non-prime attribute depends on a proper subset of any candidate key).
    • Third Normal Form (3NF): Must be in 2NF and have no transitive dependencies. For every non-trivial FD X → Y, either X is a Superkey, or Y is a Prime attribute.
    • Boyce-Codd Normal Form (BCNF): Strictly requires that for every non-trivial FD X → Y, X must be a Superkey. Strictly stronger than 3NF; may not always preserve functional dependencies.

Unit 4: Transaction Processing & Concurrency Control

  • ACID Properties:
    • Atomicity: All-or-nothing execution guaranteed via undo-logging and rollback mechanisms.
    • Consistency: Transactions preserve database integrity constraints.
    • Isolation: Concurrent transactions execute without interfering with one another.
    • Durability: Once committed, updates survive system crashes via redo-logging (Write-Ahead Logging).
  • Serializability: A concurrent schedule is Conflict Serializable if it can be transformed into a serial schedule via non-conflicting operation swaps. Tested via Precedence Graph (Serialization Graph) acyclicity.
  • Concurrency Control Protocols:
    • Two-Phase Locking (2PL): Growing Phase (locks acquired, none released) and Shrinking Phase (locks released, none acquired). Guarantees conflict serializability. Rigorous 2PL prevents cascading rollbacks.
    • Timestamp Ordering Protocol: Ensures serializability based on read and write timestamps without deadlocks, but prone to transaction starvation.

Unit 5: Storage Structures & Physical Database Indexing

  • File Organizations: Heap files (unordered records, O(N) search), Sequential files (ordered records, binary search, expensive inserts), and Hashing.
  • Primary vs Secondary Indexes: Primary indexes built on ordered primary key fields (dense or sparse). Secondary indexes built on unordered non-key fields (must be dense).
  • B-Trees & B+ Trees: Balanced multi-way search trees. In B+ Trees, all actual data pointers reside exclusively in linked leaf nodes, making leaf level a continuous sorted linked list optimal for range queries with guaranteed O(log_B N) access time.

Database Normalization Comparison Matrix

Normal Form Prerequisite Primary Requirement / Violation Eliminated Guarantees Dependency Preservation?
1NFFlat TableAttributes contain only atomic, single valuesYes
2NF1NFNo partial dependencies (non-prime dependent on partial key)Yes
3NF2NFNo transitive dependencies (X is superkey OR Y is prime)Yes
BCNF3NFFor every FD X → Y, X must strictly be a superkeyNo (Trade-off)
4NFBCNFEliminates non-trivial Multi-Valued Dependencies (MVD)Yes

High-Frequency University Exam Questions

Q1: Distinguish between 3NF and BCNF. Provide an example where 3NF holds but BCNF is violated.

In 3NF, for any non-trivial functional dependency X → Y, either X is a superkey OR Y is a prime attribute. In BCNF, X must strictly be a superkey without exception. Consider relation R(Student, Subject, Teacher) with dependencies (Student, Subject) → Teacher and Teacher → Subject. The candidate keys are (Student, Subject) and (Student, Teacher). In Teacher → Subject, Subject is a prime attribute, so it satisfies 3NF; however, Teacher is not a superkey, thus violating BCNF.

Q2: Explain the ACID properties of a database transaction and identify how the DBMS enforces each.

Atomicity: Enforced by the Recovery Manager using transaction rollback and Undo logs. Consistency: Maintained through schema constraints (foreign keys, CHECK) and user application logic. Isolation: Enforced by the Concurrency Control manager using Two-Phase Locking (2PL) or Timestamp Ordering. Durability: Enforced by Write-Ahead Logging (WAL) and Redo logs writing transaction records to non-volatile secondary disk before committing.

Q3: Why are B+ Trees preferred over B-Trees and Binary Search Trees for database indexing?

Binary Search Trees can degrade to height O(N) and cause excessive random disk I/O. In standard B-Trees, data pointers reside in both internal and leaf nodes, reducing fan-out. B+ Trees store all actual record pointers in leaf nodes while internal nodes hold only navigational routing keys, enabling higher fan-out (thousands of keys per disk block) and lower tree height (3–4 levels). Furthermore, all leaf nodes in a B+ Tree are linked sequentially in a doubly-linked list, providing O(log N) point lookups and fast range scans.