UNIT 3: DATABASE MANAGEMENT SYSTEM - EXAM-FOCUSED SHORT NOTES

3.1 DATABASE FUNDAMENTALS & ARCHITECTURE

File System vs. DBMS

[!TIP] Exam Focus: Always contrast data independence (DBMS strength) vs. tight coupling (file system weakness). Mention ACID as a DBMS-specific guarantee.

Three-Level Architecture (ANSI/SPARC)

1. External Level (View Level): User-specific views. Example: Clerk sees only Emp(Dept, Salary).

2. Conceptual Level (Logical Level): Entire database structure (entities, relationships, constraints). One logical schema for all users.

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

Mappings:

• External/Conceptual Mapping: Shields users from logical changes.

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

Data Independence:

• Logical: Change conceptual schema (e.g., add Email attribute) without altering external views or applications.

• Physical: Change storage structures (e.g., switch from heap to B+ tree) without affecting conceptual schema.

Schema, Instance, Intension & Extension

• Schema (Intension): The structure (tables, columns, types, constraints). Stable.

• Instance (Extension): The actual data stored at a moment. Dynamic.

Example: Student(Roll_no INT, Name VARCHAR(50)) is the schema. The current set of student records is the instance.

Components of DBMS

1. Storage Manager: Handles file organization, indexing, buffer management.

2. Query Processor: Parses SQL, generates relational algebra, optimizes & executes.

3. Transaction Manager: Concurrency control (locking, timestamp), recovery (logs).

4. Authorization & Integrity Manager: Enforces constraints, user privileges.

5. Buffer Manager: Caches disk pages in main memory (critical for performance).

Functions of Database Administrator (DBA)

• Schema Definition: Create/modify tables, indexes.

• Storage & Parameter Tuning: Configure memory, file sizes.

• Authorization & Security: Grant/revoke user access.

• Integrity Constraint Specification: Define PRIMARY/FOREIGN keys, CHECK.

• Backup & Recovery: Schedule backups, monitor logs.

• Performance Monitoring: Tune queries, indexes.

3.2 DATA MODELING & ENTITY-RELATIONSHIP (ER) DESIGN

ER Model Fundamentals

[!TIP] Exam Tip: In ER diagrams, multi-valued attributes are shown with double ellipses. Derived attributes are shown with dashed ellipses.

Advanced ER Constructs

• Weak Entity Set: Lacks a primary key. Existence depends on owner entity. Identified by partial key + owner's key. Represented by double rectangle & identifying relationship (double diamond).

  • Example: Dependent(EmpID, Name, DOB) where EmpID is foreign key from Employee.

• Generalization: Bottom-up. Subclasses → superclass ("is-a").

• Specialization: Top-down. Superclass → subclasses. Can be total/partial, disjoint/overlapping.

• Aggregation: Relationship between a relationship and an entity (treated as a higher-level entity). Shown by a diamond surrounding a diamond.

Mapping ER to Relational Schema

3.3 RELATIONAL MODEL & RELATIONAL ALGEBRA/CALCULUS

Relational Model Concepts

• Relation Schema: R(A₁: D₁, A₂: D₂, ..., Aₙ: Dₙ) where Dᵢ is domain.

• Relation Instance: Set of tuples at a moment. No duplicate tuples.

• Keys:

  • Super Key: Any set of attributes uniquely identifying tuples.

  • Candidate Key: Minimal super key.

  • Primary Key: Chosen candidate key.

  • Foreign Key: Attribute(s) in R referencing PK of S. Enforces referential integrity.

  • Composite Key: Key with multiple attributes.

Referential Integrity: If t[R.FK] exists, then ∃ s[S.PK] such that t[R.FK] = s[S.PK]. Actions: CASCADE, SET NULL, RESTRICT.

Relational Algebra Operations

Fundamental (6):

1. Select (σ): σ_{condition}(R) → Horizontal subset.

2. Project (π): π_{A₁, A₂}(R) → Vertical subset (eliminates duplicates).

3. Union (∪): R ∪ S (R and S must be union-compatible).

4. Set Difference (-): R - S.

5. Cartesian Product (×): R × S.

6. Rename (ρ): ρ_{new}(R).

Additional:

• Set Intersection (∩): R ∩ S = R - (R - S).

• Natural Join (⋈): R ⋈ S (equality on common attributes, removes duplicates).

• Division (÷): R ÷ S finds tuples in R that match all tuples in S on common attributes.

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

• Outer Joins:

  • Left Outer Join (⟕): All tuples from left, matched from right (NULL if no match).

  • Right Outer Join (⟖): All from right.

  • Full Outer Join (⟗): All from both.

[!TIP] Expression Tree: Draw trees for complex queries. Selection (σ) and Projection (π) are pushed down early for optimization.

Relational Calculus

• Tuple Relational Calculus (TRC): { t | P(t) } where t is a tuple variable. Non-procedural.

  • Example: { t.Name | ∃s ∈ Student (s.Roll_no = t.Roll_no ∧ s.Dept = 'CS') }

• Domain Relational Calculus (DRC): { <x₁, x₂, ...> | P(x₁, x₂, ...) } where xᵢ are domain variables.

  • Example: { <n> | ∃r, d (Student(r, n, d) ∧ d = 'CS') }

• Codd's Theorem: Relational Algebra and Relational Calculus have equal expressive power.

3.4 SQL & QUERY FORMULATION

DDL Commands

CREATE TABLE Student (

    Roll_no INT PRIMARY KEY,

    Name VARCHAR(50) NOT NULL,

    Dept VARCHAR(20),

    Year INT CHECK (Year BETWEEN 1 AND 4)

);

ALTER TABLE Student ADD COLUMN Email VARCHAR(100);

ALTER TABLE Student DROP COLUMN Year;

ALTER TABLE Student MODIFY Dept VARCHAR(30);

DROP TABLE Student;

DML: SELECT Query Structure

SELECT [DISTINCT] <attribute-list>

FROM <table-list>

WHERE <condition>

GROUP BY <group-attributes>

HAVING <group-condition>

ORDER BY <attribute> [ASC|DESC];

• WHERE filters rows before grouping.

• GROUP BY creates groups.

• HAVING filters groups.

• ORDER BY sorts final result.

Special Operators

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

• IN / NOT IN: WHERE Dept IN ('CS', 'IT')

• EXISTS / NOT EXISTS: Efficient for correlated subqueries.

  
  SELECT Name FROM Student S
  
  WHERE EXISTS (
  
      SELECT * FROM Enrolls E
  
      WHERE E.Roll_no = S.Roll_no AND E.Course = 'DBMS'
  
  );
  
  

• ANY / ALL: Compare with a set. Salary > ANY (SELECT Salary FROM Prof).

Aggregate Functions

GROUP BY Rule: All non-aggregated attributes in SELECT must be in GROUP BY.

Joins in SQL

-- Inner Join (Equi/Theta)

SELECT * FROM Student S JOIN Enrolls E ON S.Roll_no = E.Roll_no;

-- Left Outer Join

SELECT * FROM Student S LEFT JOIN Enrolls E ON S.Roll_no = E.Roll_no;

-- Self Join (e.g., Employee hierarchy)

SELECT E1.Name, E2.Name AS Manager

FROM Employee E1 LEFT JOIN Employee E2 ON E1.MgrID = E2.EmpID;

-- Full Outer Join (Not in MySQL, use UNION)

SELECT * FROM S LEFT JOIN E ON ... 

UNION

SELECT * FROM S RIGHT JOIN E ON ...;

Views

• Virtual View: CREATE VIEW CS_Students AS SELECT * FROM Student WHERE Dept='CS'; (Stored query, no data storage).

• Materialized View: Physically stores result. Needs REFRESH. Faster query, slower updates.

• Updatable Views: Simple (single table, no aggregates, no DISTINCT). Complex views require INSTEAD OF triggers.

Triggers

CREATE TRIGGER UpdateTotal

AFTER INSERT ON OrderItems

FOR EACH ROW

BEGIN

    UPDATE Orders

    SET Total_Amount = Total_Amount + NEW.Quantity * NEW.Price

    WHERE OrderID = NEW.OrderID;

END;

• Timing: BEFORE / AFTER.

• Event: INSERT / UPDATE / DELETE.

• Scope: FOR EACH ROW (row-level) or FOR EACH STATEMENT.

3.5 DATABASE DESIGN & NORMALIZATION

Functional Dependencies (FDs)

• Definition: X → Y means value of X functionally determines value of Y in relation R.

• Trivial FD: Y ⊆ X (e.g., AB → A). Non-trivial: Y ⊈ X.

• 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.

  • Additional Rules:

    • Union: X → Y and X → Z ⇒ X → YZ.

    • Decomposition: X → YZ ⇒ X → Y and X → Z.

    • Pseudotransitivity: X → Y and YZ → W ⇒ XZ → W.

Attribute Closure (X⁺)

Algorithm to find all attributes functionally determined by X.

1. Start: result = X

2. Repeat: For each FD Y → Z in F, if Y ⊆ result, then result = result ∪ Z

3. Until no change.

Uses: Find candidate keys (X⁺ = all attributes), check if FD X → A is implied (if A ∈ X⁺).

Canonical/Minimal Cover

1. Decompose RHS of each FD to single attribute.

2. Remove extraneous LHS attributes (test if (X - A)⁺ under F contains A).

3. Remove redundant FDs (test if FD is implied by others).

Normal Forms & Anomalies

Steps to 3NF/BCNF Decomposition:

1. Find minimal cover F.

2. For each FD X → A in F, create relation Rᵢ = X ∪ A.

3. If no relation contains a candidate key of R, create one.

4. BCNF Check: If any relation violates BCNF (X → A but X not superkey), decompose that relation on X → A.

Lossless Join Condition: Decomposition {R₁, R₂} of R is lossless iff (R₁ ∩ R₂) → R₁ or (R₁ ∩ R₂) → R₂ holds in F⁺.

Dependency Preserving: Decomposition is dependency preserving if F⁺ = (F₁ ∪ F₂ ∪ ...)⁺ where Fᵢ are FDs on Rᵢ.

4NF & Multi-valued Dependencies (MVD)

• MVD: X ↠ Y means for one X value, there is a set of independent Y values. (Notation: double arrow).

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

• Example: Student(Roll_no, Course, Hobby). If hobbies independent of courses, Roll_no ↠ Course and Roll_no ↠ Hobby. If Roll_no is key, it's 4NF. If not, decompose.

3.6 TRANSACTION MANAGEMENT

Transaction & States

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

• States:

  
  Active → Partially Committed → Committed
  
       ↓
  
      Failed → Aborted (→ Rollback → Active)
  
  

  State Diagram: Active (executing) → Partially Committed (end, before commit) → Committed. Any failure → Failed → Aborted → Rollback → Active (restart).

ACID Properties

Schedules & Serializability

• Schedule: Order of operations from multiple transactions.

• Serial Schedule: Transactions execute one after another. Always conflict-serializable.

• Non-serial Schedule: Transactions interleaved. May be serializable (equivalent to some serial order).

• Conflict Serializability:

  • Conflicting Operations: From different T, access same item, at least one is write.

  • Precedence Graph: Nodes = T. Edge Tᵢ → Tⱼ if Tᵢ's op conflicts with earlier Tⱼ's op.

  • Test: Schedule is conflict-serializable iff precedence graph is acyclic.

• View Serializability: More general. Requires:

  1. Same initial reads.

  2. Same final writes.

  3. Same read-from relationships.

Recovery (Log-Based)

• Write-Ahead Logging (WAL): Before modifying a page, log record (T, X, old, new) must be on disk.

• Log Record Types: BEGIN, UPDATE (old, new), COMMIT, ABORT.

• Recovery Strategies:

  • Deferred Update: Apply changes to DB only at commit. Recovery: redo committed T.

  • Immediate Update: Apply changes immediately. Recovery: undo uncommitted T, redo committed T.

• Checkpoint:

  1. Flush all modified buffers to disk.

  2. Write <checkpoint L> to log, where L = list of active T at checkpoint.

  3. Recovery starts from last checkpoint. Only T in L (uncommitted at checkpoint) need undo; committed T after checkpoint need redo.

3.7 CONCURRENCY CONTROL

Problems in Concurrent Execution

Locking Protocols

• Lock Modes:

  • Shared (S): Read lock. Multiple T can hold S-lock on same item.

  • Exclusive (X): Write lock. Only one T can hold X-lock.

• Two-Phase Locking (2PL):

  1. Growing Phase: T acquires locks (no release).

  2. Shrinking Phase: T releases locks (no new acquires).

  • Guarantees Conflict Serializability.

  • Strict 2PL: All exclusive locks held until commit/abort. Prevents cascading aborts.

  • Cascadeless 2PL: S-locks released early, X-locks held until commit. Prevents dirty reads.

  2PL is necessary but not sufficient for cascadeless/strict schedules. Strict 2PL ensures recoverable & cascadeless schedules.

Deadlock Management

• Deadlock: Circular wait. T1 waits for T2, T2 waits for T1.

• Prevention: Force one of Coffman conditions to fail.

  • Wait-Die: Older T waits, younger T aborts (uses timestamps).

  • Wound-Wait: Older T aborts younger T, younger T waits.

• Avoidance: Wait-for Graph (WFG). If adding edge creates cycle → abort victim.

• Detection & Resolution: Periodic WFG construction. If cycle → select victim (least cost to abort), rollback victim.

• Blocking vs. Deadlock: Blocking is temporary (T waiting for lock held by active T). Deadlock is permanent circular wait.

Alternative Concurrency Control

• Timestamp Ordering (TS):

  • Each T gets unique timestamp TS(T).

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

  • Protocol: If T wants to read/write X:

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

    • Else, allow & set RTS(X)=TS(T) or WTS(X)=TS(T).

  • Thomas's Write Rule: Ignore outdated writes (TS(T) < WTS(X)) instead of aborting (allows some non-serial schedules).

• Optimistic (Validation-Based):

  • Phase 1 (Read): T reads & writes to private workspace.

  • Phase 2 (Validation): Check if T's reads conflict with earlier committed T. Three tests (serializable if passes).

  • Phase 3 (Write): If validated, write changes to DB; else abort.

  • Best for low-conflict workloads.

• Multiple Granularity Locking (MGL):

  • Lock Hierarchy: Database → File → Page → Record.

  • Intention Locks: Indicate T intends to get S/X lock at lower level.

    • IS (Intention Shared): Will request S-lock on some descendant.

    • IX (Intention Exclusive): Will request X-lock on some descendant.

    • SIX (Shared + Intention Exclusive): S-lock on node, IX on descendants.

  • Compatibility Table: Governs which locks can coexist on same node.

3.8 QUERY PROCESSING & OPTIMIZATION

Steps in Query Processing

1. Parsing: Syntax check, build parse tree.

2. Translation: Parse tree → Relational Algebra expression tree.

3. Optimization: Choose lowest-cost evaluation plan.

4. Execution: Execute plan using algorithms (nested loops, hash join, etc.).

Query Optimization

• Necessity: Exponential number of equivalent expressions. Small change → huge cost difference.

• Heuristic Rules (Rule-Based):

  1. Perform selection (σ) as early as possible (reduces tuples).

  2. Perform projection (π) as early as possible (reduces attributes).

  3. Combine cascading selections: σ_{c1}(σ_{c2}(R)) → σ_{c1∧c2}(R).

  4. Replace Cartesian Product + Selection with Join if possible.

  5. Move projections down (but keep needed attributes for joins).

• Cost-Based Optimization:

  • Cost Metrics: I/O cost (disk pages read/written), CPU cost (tuple comparisons), Memory cost, Network cost (distributed).

  • Statistics Needed: nᵣ = # tuples in R, bᵣ = # pages in R, V(A, R) = # distinct values of A in R.

  • Selectivity (sel): Fraction of tuples satisfying condition. sel = 1 / max(V(A,R), 1) for equality.

  • Cost Estimation: Use formulas for each operator (e.g., selection using index vs. full scan).

Operation Cost Comparison

3.9 STORAGE, INDEXING & FILE ORGANIZATION

File Organization Methods

Hashing Techniques

• Static Hashing:

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

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

  • Problem: If N too small → long chains; if too large → wasted space.

• Extendable Hashing:

  • Directory: Array of pointers to buckets. Size 2^d (global depth d).

  • Local Depth: Per bucket. Split when bucket overflows.

  • Splitting: If bucket with local depth l overflows, double directory if l == d. Split bucket, redistribute records using d+1 bits.

  • Advantage: Grows dynamically, minimal overflow.

• Linear Hashing:

  • No directory. Buckets numbered 0,1,2,...

  • Split Round: When bucket i overflows, split it and create new bucket at end. Next split round: split bucket (i mod 2^r).

  • Hash Functions: h₀, h₁, h₂, .... Use hᵣ after 2^r splits.

Index Structures

• Dense Index: Entry for every search key value (in data file). Faster search, larger index.

• Sparse Index: Entry for each data block (only first key in block). Smaller index, requires data access for non-first keys.

• Multi-level Index: Index on index. Top levels sparse, leaf level dense/sparse.

• B⁺ Tree:

  • Structure: All leaves at same level. Internal nodes: (P₁, K₁, P₂, K₂, ..., Pₙ) where Pᵢ pointers, Kᵢ keys. n between ⌈m/2⌉ and m (order).

  • Search: Start at root, follow pointers.

  • Insertion: Insert in leaf. If overflow → split leaf, propagate up (may increase height).

  • Deletion: Merge/redistribute. May decrease height.

  • Advantages: Balanced, supports range queries, efficient insert/delete.

Bitmap Indexing

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

• Structure: One bit-vector per distinct value. Bit i = 1 if tuple i has that value.

• Operations: AND/OR → bitwise AND/OR. Fast for multiple conditions.

• Use Case: Data warehousing, OLAP queries with many WHERE clauses on few distinct values.

RAID Levels

3.10 ADVANCED & SPECIAL TOPICS

Distributed Databases

• Concepts:

  • Fragmentation: Horizontal (rows), Vertical (columns), Mixed.

  • Replication: Copy of fragment at multiple sites. Transparency: Users see single DB.

  • Allocation: Where fragments/replicas stored.

• Challenges:

  • Distributed Query Processing: Minimize data transfer (semi-join, Bloom filter).

  • Distributed Transaction: 2PC (Two-Phase Commit) for atomicity across sites.

  • Concurrency Control: Distributed locking, timestamp with global coordinator.

  • Recovery: Logs at each site. Failure of coordinator/site complex.

NoSQL Databases

• Characteristics: Schema-flexible, horizontal scaling, BASE (Basic Availability, Soft state, Eventual consistency) vs. ACID.

Object-Oriented DBMS (OODBMS)

• Concepts: Objects, Classes, Inheritance, Complex objects (nested), Methods.

• vs. RDBMS:

  | Feature | RDBMS | OODBMS | |-------------------|------------------------------------|-------------------------------------| | Data Model | Tables, rows, columns | Objects, classes | | Complex Data | Normalized, joins needed | Nested objects, direct references | | Inheritance | Not native (mapped to tables) | Native | | Schema | Fixed schema | Schema-flexible | | Query Language| SQL (declarative) | OQL (object-oriented) | | Use Case | Structured data, transactions | CAD, multimedia, complex hierarchies|

Miscellaneous Important Topics

• Data Dictionary / System Catalog: Metadata repository (tables, columns, types, constraints, users, privileges). Queried via system tables (INFORMATION_SCHEMA in SQL).

• Integrity Constraints:

  • Domain: CHECK (age>0).

  • Entity Integrity: PRIMARY KEY NOT NULL.

  • Referential Integrity: FOREIGN KEY ... REFERENCES.

  • User-defined: ASSERTION (global), TRIGGER.

• Assertions: Database-wide constraints. CREATE ASSERTION chk_salary CHECK (NOT EXISTS (SELECT * FROM Employee WHERE Salary<0));

• Web & Mobile Databases: Challenges: intermittent connectivity, security, synchronization, limited resources. Solutions: local storage (SQLite), sync frameworks.

• Hierarchical Queries (Oracle CONNECT BY):

  
  SELECT * FROM Employee
  
  START WITH ManagerID IS NULL
  
  CONNECT BY PRIOR EmpID = ManagerID;
  
  

• Oracle APEX: Low-code web development platform for Oracle DB. Builds apps on top of Oracle DB.

• Complexity Measures: Query optimization cost model: Cost = I/O_cost + CPU_cost + Network_cost. Often dominated by I/O (disk accesses).

Final Exam Strategy:

1. Draw diagrams for ER, B+ Tree, State Diagram, Precedence Graph.

2. Show step-by-step for normalization, closure, serializability test.

3. Write SQL for all DDL/DML, especially joins, subqueries, aggregates.

4. Compare & contrast (File System vs DBMS, 2PL vs Timestamp, OODBMS vs RDBMS).

5. Define & explain with examples: ACID, FD, MVD, Anomalies, Views, Triggers.