UNIT 1: Database Management System - Comprehensive Short Notes

(Aligned with RGPV CY-405 Past Paper Analysis)

I. Foundations of DBMS

DBMS vs Traditional File Systems

Advantages of DBMS:

• Reduced Redundancy: Single storage, multiple views.

• Data Integrity: Constraints (domain, referential).

• Security: Authentication, authorization.

• Concurrent Access: Locking, timestamp protocols.

• Backup & Recovery: ACID transactions, logs.

• Data Abstraction: Three-level architecture.

DBMS Architecture (Three-Level Schema)

External Level (User Views)

    ↑

Conceptual Level (Logical Schema - Community View)

    ↑

Internal Level (Physical Storage - OS/File System)

• External Schema/View: User-specific logical views. CREATE VIEW.

• Conceptual Schema: Global logical structure (tables, constraints). Single copy.

• Internal Schema: Physical storage details (files, indexes, RAID).

• Mappings:

  • External-Conceptual: Multiple-to-one.

  • Conceptual-Internal: One-to-one.

• DBA Functions: Schema definition, security, backup, performance tuning.

Data Independence

• Logical Data Independence: Changes to conceptual schema (e.g., add table) do not affect external schemas/applications.

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

Example: Adding an index (physical) doesn't change table structure (logical).

Schema vs Instance

• Schema (Intension): Structure/design of database (tables, columns, types). Fixed.

• Instance (Extension): Actual data stored at a moment. Changes with INSERT/UPDATE/DELETE.

Categories of Database Users

1. End Users: Casual (ad-hoc queries), Naïve (forms), Sophisticated (complex queries).

2. Application Programmers: Write application code (C++, Java) using embedded SQL/ODBC/JDBC.

3. DBA (Database Administrator): Manages DBMS (security, backup, tuning, schema design).

II. Data Modeling and ER Diagrams

ER Model Basics

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

• Attribute: Property of entity (e.g., Roll_no). Represented by ellipse.

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

• Key Attribute: Underlined ellipse.

Types of Attributes

Types of Relationships & Cardinality

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

• Cardinality:

  • 1:1 (One-to-One): One entity associates with at most one of other.

  • 1:M (One-to-Many): One entity associates with many of other.

  • M:N (Many-to-Many): Many entities associate with many of other.

Representation: Lines with 1, N, or M near entities.

Weak vs Strong Entity Sets

Generalization, Specialization, Aggregation

• Generalization: Bottom-up (lower entities → higher superclass). "Is-a".

• Specialization: Top-down (superclass → lower subclasses). "Is-a".

• Aggregation: Relationship as an entity (has its own relationships). "Has-a".

Example: Enrollment (relationship) aggregated with Course to model Offers.

ER Diagram: Indian Movies (Past Paper Example)

[Movie]───(Shot_At)───[Location]

   │

   ├──(Has_Actor)───[Actor]───(Works_In)───[Movie]

   ├──(Directed_By)───[Director]

   ├──(Produced_By)───[Producer]

   └──(In_Language)───[Language]

• Movie (Movie_ID, Title, Year) – Strong Entity.

• Location (Loc_ID, City, State) – Strong Entity.

• Actor (Actor_ID, Name, DOB) – Strong Entity.

• Relationships: Shot_At (M:N), Has_Actor (M:N), Directed_By (M:1), In_Language (M:1).

Mapping ER to Relational Schema

III. Relational Model

Relational Schema & Instance

• Schema: R(A₁: D₁, A₂: D₂, ..., Aₙ: Dₙ) where R = relation name, Aᵢ = attribute, Dᵢ = domain.

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

Types of Keys

Integrity Constraints

1. Domain Constraint: Attribute value must be from domain (type, range).

2. Entity Integrity: PRIMARY KEY cannot be NULL.

3. Referential Integrity: Foreign key value must:

   • Equal to a primary key value in referenced table, OR

   • Be NULL (if allowed).

4. Assertions: General predicates (CREATE ASSERTION). Example: CHECK (dept_count > 0).

Relational Algebra Operations

Basic Operators:

• Selection (σ): σ_{condition}(R) – Rows satisfying condition.

• Projection (Π): Π_{A₁, A₂}(R) – Specific columns (duplicates removed).

• Set Operations: ∪, ∩, − (require union-compatible).

• Cartesian Product (×): R × S – Concatenates every row of R with every row of S.

• Rename (ρ): ρ_{S(A₁,...,Aₙ)}(R) – Renames relation/attributes.

Join Operations:

• Theta Join (⋈ₜₕ): R ⋈ₜₕ S – Cartesian product + selection (σ_{R.A θ S.B}(R × S)).

• Equi Join: Theta join with = only.

• Natural Join (⋈): Equi join on all common attributes + duplicate elimination.

• Outer Joins:

  • Left Outer Join (⋈ₗ): All tuples from left, NULL for unmatched right.

  • Right Outer Join (⋈ᵣ): All tuples from right, NULL for unmatched left.

  • Full Outer Join (⋈ₓ): All tuples from both, NULL where unmatched.

Additional Operators:

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

  • Use: "Find students who have taken all courses."

  • Formula: Π_{R-S}(R) − Π_{R-S}((Π_{R-S}(R) × S) − R).

Relational Calculus

• Tuple Relational Calculus (TRC): { t | P(t) } – Set of tuples t satisfying formula P.

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

• Domain Relational Calculus (DRC): { ⟨x₁,...,xₙ⟩ | P(x₁,...,xₙ) } – Set of domain tuples.

  • Example: { ⟨sname⟩ | ∃did (Student(sname, sid, did) ∧ Dept(did, 'CS')) }.

Safe Expressions: Finite result set (use only from given relations).

SQL: DDL & DML

DDL:

CREATE TABLE Student(Roll_no INT PRIMARY KEY, Name VARCHAR(50), Dept VARCHAR(10));

ALTER TABLE Student ADD COLUMN Marks INT;

DROP TABLE Student;

DML:

SELECT * FROM Student WHERE Dept = 'CS'; -- Selection

SELECT DISTINCT Dept FROM Student; -- Projection

SELECT * FROM Student, Course WHERE Student.Dept = Course.Dept; -- Cartesian + Selection (Join)

Special Operators:

• LIKE '%pattern%' – Pattern matching.

• ANY/ALL – Comparison with set.

• EXISTS – Subquery returns at least one row.

• IN – Value in set.

Aggregate Functions:

SELECT Dept, COUNT(*), AVG(Marks) FROM Student GROUP BY Dept HAVING AVG(Marks) > 75;

Subqueries: Nested SELECT in WHERE/FROM/SELECT.

Views

• Definition: Virtual table from SELECT query. CREATE VIEW CS_Students AS SELECT * FROM Student WHERE Dept='CS';.

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

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

Triggers

• Definition: Procedural code auto-executed on INSERT/UPDATE/DELETE.

• Syntax (Oracle):

CREATE TRIGGER trig_name

BEFORE UPDATE ON Orders

FOR EACH ROW

BEGIN

  INSERT INTO AuditLog VALUES (:OLD.OrderID, SYSDATE);

END;

Components: Event, Condition, Action.

IV. Database Design and Normalization

Functional Dependencies (FDs)

• Definition: X → Y (X functionally determines Y). For any two tuples, if X values equal, then Y values equal.

• Armstrong's Inference Rules:

  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, X → Z ⇒ X → YZ), Decomposition (X → YZ ⇒ X → Y, X → Z), Pseudotransitivity.

FD Closure (X⁺)

• Set of attributes functionally determined by X using FDs.

• Algorithm: Start X⁺ = X. Repeatedly add Y if X⁺ → Y in F. Until no change.

Candidate Keys from FD Set

1. Find attributes not on RHS of any FD → must be in every key.

2. Compute closure of these attributes.

3. If closure = all attributes, it's a candidate key.

4. Else, add minimal attributes from RHS to get closure = full set.

Normal Forms

Decomposition

• Lossless Join Decomposition: R decomposed into R₁, R₂ if R₁ ⋈ R₂ = R.

  • Condition: (R₁ ∩ R₂) → R₁ OR (R₁ ∩ R₂) → R₂.

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

Goal: Decompose to BCNF/4NF losslessly and preserve dependencies if possible.

Normalization Process (Example)

Given R(A, B, C, D) with FDs: {A → B, B → C, C → D}.

1. 1NF: Assume atomic.

2. 2NF: A → B (partial? if composite key). If key=A, then 2NF satisfied.

3. 3NF: B → C (transitive: A→B→C). Decompose:

   • R1(A, B), R2(B, C, D).

4. BCNF: In R2, B → C, D but B not key. Decompose R2:

   • R21(B, C), R22(B, D).

   • Final: R1(A,B), R21(B,C), R22(B,D) – BCNF, lossless, not dependency preserving (lost C→D).

V. Transaction Management

Transaction & ACID Properties

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

• ACID:

  • Atomicity: All or nothing. COMMIT or ABORT.

  • Consistency: Preserves integrity constraints.

  • Isolation: Concurrent transactions don't interfere.

  • Durability: Committed changes permanent (survive failures).

Transaction States

[Active] → [Partially Committed] → [Committed]

    ↓           ↓

[Failed] → [Aborted] → (Restart)

State Diagram: Active (executing) → Partially Committed (end transaction) → Committed (changes permanent). Any failure → Failed → Aborted (rollback).

Schedules

• Serial Schedule: Transactions execute sequentially.

• Non-Serial Schedule: Transactions interleave operations.

• Conflict Serializable: Schedule equivalent to some serial schedule (no cycles in precedence graph).

• View Serializable: Equivalent to serial schedule by view equivalence (same read-from, same final writes).

Serializability Testing (Precedence Graph)

1. Nodes = transactions.

2. Edge Tᵢ → Tⱼ if Tᵢ writes X and Tⱼ reads X, or Tᵢ reads/writes X and Tⱼ writes X.

3. Conflict Serializable iff graph is acyclic.

Concurrency Control

Two-Phase Locking (2PL):

• Growing Phase: Acquire locks, no release.

• Shrinking Phase: Release locks, no acquire.

• Guarantees: Conflict serializability.

• Variants:

  • Strict 2PL: Hold exclusive locks until commit/abort.

  • Rigorous 2PL: Hold all locks until commit/abort (prevents cascading abort).

Timestamp-Based Concurrency Control:

• Each transaction gets timestamp TS(T).

• Read/Write Rules:

  • If TS(T) < R-TS(X) → T too old, abort.

  • If TS(T) < W-TS(X) → T too old, abort.

  • Else, read/write, update R-TS(X)/W-TS(X).

• Advantage: No deadlocks.

Optimistic Concurrency Control (Validation-Based):

1. Read Phase: Read, write to local copies.

2. Validation Phase: Check if T's read set overlaps with write set of committed T' (with TS(T') < TS(T)).

   • If conflict, abort.

3. Write Phase: If validated, write to database.

Deadlock

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

• Prevention: Order resources, pre-declare locks, no wait-die/wound-wait.

• Detection: Wait-for graph cycle detection.

• Resolution: Victim selection (abort youngest/lowest cost transaction).

Recovery

Database Logs:

• Types:

  • Update Log: (X, old, new) before/after image.

  • Compensation Log (CL): For undo.

• Importance: Atomicity, durability, recovery.

Recovery Techniques:

• Deferred Database Modification: Write changes only at commit. Undo not needed; if abort, ignore local writes.

• Immediate Database Modification: Write as soon as operation executes. Need undo (using old values) and redo (using new values).

Checkpoint:

• Periodically force all modified buffers to disk, write checkpoint record to log.

• Recovery from checkpoint: Only consider transactions active after last checkpoint.

Shadow Paging:

• Maintain shadow copy of database pages.

• Transaction writes to new pages; update page table at commit.

• No undo log; abort = discard new pages.

• No redo; commit = switch page table.

VI. Query Processing and Optimization

Phases of Query Processing

1. Parsing: Syntax/semantic check → parse tree.

2. Translation: Parse tree → relational algebra expression.

3. Optimization: Choose lowest-cost execution plan.

4. Execution: Generate code/interpret plan; fetch results.

Query Optimization Necessity

• Relational algebra expressions are equivalent but have different costs.

• Example: σ_{A=5}(R ⋈ S) vs σ_{A=5}(R) ⋈ S – push selection before join to reduce intermediate size.

Cost Estimation Measures

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

• CPU Cost: Tuple processing, comparison.

• Network Cost: Distributed queries.

Cost Formula: Total Cost = (I/O Cost × Disk Seek/Transfer Time) + (CPU Cost × CPU Time per Tuple).

Heuristic vs Cost-Based Optimization

• Heuristic Rules:

  1. Apply selection and projection early (reduce tuple/attribute count).

  2. Perform most restrictive operations first.

  3. Projection before Cartesian product.

• Cost-Based: Enumerate equivalent expressions, estimate cost using statistics (cardinality, distinct values), choose minimum.

Complexity of Operations (Big O)

VII. Storage and Indexing

File Organization Methods

Indexing Concepts

• Primary Index: On primary key, clustered (data order = index order). One per table.

• Clustering Index: On any key with data sorted on that key. Data order = index order.

• Secondary Index: Non-clustered; data order ≠ index order. May have dense (entry per record) or sparse (entry per block).

Dense vs Sparse: Dense has entry for every record; sparse has entry for every data block.

B-trees vs B+ trees

Hashing Techniques

• Static Hashing: Fixed number of buckets. bucket = h(key) mod N.

  • Problem: Bucket overflow (chaining/overflow pages); poor space utilization.

• Extendable Hashing:

  • Directory of pointers to buckets.

  • Local depth (bucket), global depth (directory).

  • Split bucket when overflow; may double directory.

• Linear Hashing:

  • No directory; split buckets in order.

  • Overflow chains; split when overflow.

  • Split pointer rounds.

Bitmap Indexing

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

• Bitmap: Bit vector per distinct value (1 = present, 0 = absent).

• Operations: AND, OR, NOT (bitwise) – fast.

Example: Gender='M' ∧ Dept='CS' → bitwise AND of two bitmaps.

RAID Levels

VIII. Distributed and Advanced Databases

Distributed Database Concepts

• Fragmentation:

  • Horizontal: Subsets of tuples.

  • Vertical: Subsets of attributes.

  • Hybrid: Both.

• Replication: Copy fragments at multiple sites.

• Transparency:

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

  • Replication Transparency: Users don't know replicas.

  • Location Transparency: Users don't know site names.

Challenges in DDBMS

• Data Distribution: Fragmentation, replication, consistency.

• Concurrency Control: Distributed locking, timestamp (needs global ordering).

• Recovery: Commit protocols (2-phase commit), distributed logging.

• Heterogeneity: Different DBMS, OS, networks.

NoSQL Databases

OODBMS vs RDBMS

IX. Additional Topics (High-Frequency from Past Papers)

Data Dictionary & Dynamic Performance Views

• Data Dictionary: System catalog storing metadata (tables, columns, constraints, users). Read-only.

• Dynamic Performance Views (Oracle): V$ views (e.g., V$SESSION, V$SQL) – real-time performance stats.

Assertions

• Definition: General integrity constraints not tied to single table.

• Syntax: CREATE ASSERTION name CHECK (condition);

• Example: CREATE ASSERTION dept_count CHECK (10 <= (SELECT COUNT(*) FROM Dept));

Rarely used; triggers often替代.

Hierarchical Queries (Oracle CONNECT BY)

SELECT employee_id, manager_id, LEVEL

FROM employees

START WITH manager_id IS NULL

CONNECT BY PRIOR employee_id = manager_id;

• LEVEL: Pseudocolumn for depth.

• PRIOR: Specifies parent-child relationship.

Aggregation in ER Model

• Aggregation: Relationship between an entity set and a relationship set (treats relationship as an entity).

• Use: When a relationship needs to participate in another relationship.

Example: Enrollment (relationship between Student and Course) participates in Offers (relationship with Semester).

Multiple Granularity Locking

• Lock Modes: IS (intent shared), IX (intent exclusive), S, X.

• Protocol:

  • To lock a node in S/X, must have IS/IX on parent.

  • To lock child in S/X, parent must be IS/IX.

• Allows: Fine-grained locking without checking all descendants.

Validation-Based Protocols (Optimistic)

• Phases: Read (collect reads/writes), Validate (check conflicts), Write (apply changes).

• Validation Test: For Tᵢ starting after Tⱼ committed:

  • Tᵢ's read set ∩ Tⱼ's write set = ∅ AND

  • Tᵢ's write set ∩ (Tⱼ's read ∪ write set) = ∅.

• Cost: Low overhead, good for low conflict workloads.

Complexity Measures in Query Optimization

• I/O Complexity: Number of block transfers.

• CPU Complexity: Tuple comparisons, hash calculations.

• Network Complexity: Data shipped in distributed queries.

Goal: Minimize total cost; I/O usually dominates.

BOXED KEY FORMULAS & THEOREMS

1. FD Closure Algorithm:

   
   X⁺ ← X
   
   repeat
   
     for each FD Y → Z in F:
   
       if Y ⊆ X⁺ then X⁺ ← X⁺ ∪ Z
   
   until no change
   
   

2. Lossless Join Condition:

$$(R_1 \cap R_2) \rightarrow R_1 \quad \text{OR} \quad (R_1 \cap R_2) \rightarrow R_2$$

3. Division Operation:

$$R \div S = \Pi_{R-S}(R) - \Pi_{R-S}((\Pi_{R-S}(R) \times S) - R)$$

4. 2PL Guarantee: If schedule follows 2PL, it is conflict serializable.

5. Timestamp Ordering:

   • Read: TS(T) < R-TS(X) → abort; else read.

   • Write: TS(T) < W-TS(X) → abort; else write.

6. B+ tree Order:

   • Leaf Nodes: ⌊(n×F)/2⌋ ≤ keys ≤ n×F (F = fill factor).

   • Internal Nodes: ⌈n/2⌉ ≤ pointers ≤ n.

[!TIP] Exam Focus Areas (Based on Past Papers):

• 7-mark questions: DBMS vs File Systems, ER Diagrams (University/Hospital/Indian Movies), Normalization (FDs, 2NF/3NF/BCNF), ACID & Transaction States, 2PL & Deadlock, Relational Algebra (Selection/Projection/Join), Serializability (Precedence Graph).

• Short Notes (5m): Assertions, Hierarchical Queries, MVD/4NF, Views, Triggers, RAID, Hashing (Extendable/Linear), OODBMS vs RDBMS, Distributed DB Challenges.

• SQL Queries: Always practice subqueries, joins, aggregate functions, GROUP BY/HAVING.

• Normalization: Be ready to identify FDs, find candidate keys, convert to 2NF/3NF/BCNF step-by-step.

• Concurrency: Draw state diagram, explain 2PL variants, solve conflict serializability with precedence graph.

• ER to Relational Mapping: Weak entities, M:N relationships, total participation – rules must be memorized.