UNIT 3: DATABASE MANAGEMENT SYSTEM - SHORT NOTES

1. INTRODUCTION & DATABASE SYSTEM CONCEPTS

DBMS vs. File System

[!TIP] Exam Focus: Always contrast data independence and integrity enforcement as key differentiators.

Data Abstraction Levels

1. Physical Level: Lowest level; describes how data is stored (blocks, records, indices, storage structures).

2. Logical Level: Describes what data is stored (entities, attributes, relationships) as seen by DBA.

3. View Level: Highest level; user-specific subset of the database (hides complexity).

Data Independence

• Physical Data Independence: Changes in storage structures (e.g., file organization, indexing) do not affect logical schema or applications.

  • Example: Switching from heap file to B⁺-tree index.

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

  • Example: Adding a new column Phone to Student table without changing existing queries.

DBMS Architecture & Components

          ┌─────────────────────────────────────────┐

          │          Application Programs           │

          └─────────────────┬───────────────────────┘

                            │

          ┌─────────────────▼───────────────────────┐

          │         Query Processor                 │

          │  • DDL Interpreter                     │

          │  • DML Compiler & Optimizer            │

          │  • Query Execution Engine              │

          └─────────────────┬───────────────────────┘

                            │

          ┌─────────────────▼───────────────────────┐

          │         Storage Manager                 │

          │  • File Manager                        │

          │  • Buffer Manager                      │

          │  • Transaction Manager                 │

          └─────────────────┬───────────────────────┘

                            │

          ┌─────────────────▼───────────────────────┐

          │         Physical Storage                │

          │  • Disk Files, Indices                  │

          └─────────────────────────────────────────┘

Database Users & DBA Roles

DBA Functions: Schema definition, storage structure & access method definition, security & authorization, integrity constraint specification, backup & recovery, tuning performance.

Data Models

[!TIP] Exam Tip: Relational is most common; NoSQL for CAP theorem (Consistency, Availability, Partition Tolerance) trade-offs.

2. ENTITY-RELATIONSHIP (ER) MODELING

ER Diagram Components

• Entity: Object with independent existence (e.g., Student, Course).

• Attribute: Property of an entity.

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

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

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

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

• Relationship: Association among entities.

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

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

Constraints

• Key Constraint: Attribute(s) uniquely identifying an entity (primary key).

• Participation Constraint:

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

  • Partial: Optional participation.

Advanced ER Concepts

• Weak Entity Set: Existence-dependent on another entity (double rectangle, partial key dashed underline).

  • Example: Dependent (Emp_ID, Dependent_Name) depends on Employee.

• Generalization/Specialization: Hierarchy where supertype (Person) generalizes subtypes (Student, Faculty).

  • Inheritance: Subtypes inherit supertype attributes.

• Aggregation: Relationship between a relationship and an entity (diamond within diamond).

  • Example: Enrollment (relationship between Student and Course) linked to Project.

ER to Relational Mapping

[!TIP] Common Pitfall: Forgetting to include foreign keys for relationship participation in mapping.

3. RELATIONAL MODEL & RELATIONAL ALGEBRA

Relational Schema & Keys

• Relation Schema: $$\displaystyle R(A_1, A_2, ..., A_n) $$ – structure (table name + attributes).

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

• Keys:

  • Super Key: Set of attributes uniquely identifying tuples (may contain extra attributes).

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

  • Primary Key: Chosen candidate key.

  • Foreign Key: Attribute(s) referencing primary key of another table; enforces referential integrity.

Difference: Schema is definition; instance is data.

Integrity Constraints

1. Domain Constraint: Attribute values must be atomic, of correct type, within domain.

2. Entity Integrity: Primary key cannot be NULL.

3. Referential Integrity: Foreign key must match primary key value or be NULL.

   • Actions on Delete/Update:

     • CASCADE: Propagate change.

     • SET NULL: Set FK to NULL.

     • RESTRICT: Prevent change.

     • NO ACTION: Same as RESTRICT (deferred check).

Relational Algebra Operations

Fundamental Operations:

• Select (σ): Row filter. $$\displaystyle \sigma_{dept='CS'}(Student) $$

• Project (π): Column filter. $$\displaystyle \pi_{Name, Dept}(Student) $$

• Union (∪): $R \cup S$ (union-compatible).

• Set Difference (-): $R - S$.

• Cartesian Product (×): $R \times S$.

• Rename (ρ): $$\displaystyle \rho_{new}(R) $$.

Join Operations:

• Natural Join (⋈): Equijoin on common attributes + duplicate elimination.

• Theta Join ($$\displaystyle \bowtie_\theta $$): Join with arbitrary condition.

• Equi Join: Theta join with equality.

• Outer Joins:

  • Left Outer Join: Preserve all left tuples.

  • Right Outer Join: Preserve all right tuples.

  • Full Outer Join: Preserve all tuples.

Additional Operations:

• Intersection (∩): $R \cap S$.

• Division (÷): $$\displaystyle R \div S = \pi_{A}(R) - \pi_{A}((\pi_{A}(R) \times S) - R) $$ where $R(A,B)$, $S(B)$.

• Aggregation (γ): $$\displaystyle \gamma_{Dept, \ Avg(Salary)}(Employee) $$.

Relational Calculus

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

  • Example: $$\displaystyle \{ s.Name | s \in Student \land s.Dept = 'CS' \} $$

• Domain Relational Calculus (DRC): $$\displaystyle \{ \langle x_1, ..., x_n \rangle | P(x_1, ..., x_n) \} $$.

  • Example: $$\displaystyle \{ \langle n \rangle | \exists d ( \langle n, d \rangle \in Student \land d = 'CS') \} $$

• Difference: Relational algebra is procedural (how); calculus is declarative (what).

SQL Fundamentals

DDL:

• CREATE TABLE R (A INT, B VARCHAR(20), PRIMARY KEY (A))

• ALTER TABLE R ADD COLUMN C DATE

• DROP TABLE R

• TRUNCATE TABLE R (removes all rows, fast, no rollback).

DML:

• SELECT ... FROM ... WHERE ...

• INSERT INTO R VALUES (...)

• UPDATE R SET A=... WHERE ...

• DELETE FROM R WHERE ...

Complex Queries:

• Subqueries: Nested in WHERE, FROM, SELECT.

• Set Operations: UNION/INTERSECT/EXCEPT (union-compatible).

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

• Grouping: GROUP BY Dept HAVING AVG(Salary) > 50000.

4. DATABASE DESIGN & NORMALIZATION

Functional Dependencies (FDs)

• Definition: $$\displaystyle X \rightarrow Y $$ means value of $X$ uniquely determines $Y$.

• Notation: $$\displaystyle X^+ $$ = closure of $X$ (all attributes functionally determined by $X$).

• Armstrong's Axioms:

  1. Reflexivity: If $Y \subseteq X$, then $$\displaystyle X \rightarrow Y $$.

  2. Augmentation: If $$\displaystyle X \rightarrow Y $$, then $$\displaystyle XZ \rightarrow YZ $$.

  3. Transitivity: If $$\displaystyle X \rightarrow Y $$ and $$\displaystyle Y \rightarrow Z $$, then $$\displaystyle X \rightarrow Z $$.

  \boxed{\text{Reflexivity, Augmentation, Transitivity}}

• Additional Rules:

  • Union: $$\displaystyle X \rightarrow Y $$ and $$\displaystyle X \rightarrow Z $$ ⇒ $$\displaystyle X \rightarrow YZ $$.

  • Decomposition: $$\displaystyle X \rightarrow YZ $$ ⇒ $$\displaystyle X \rightarrow Y $$ and $$\displaystyle X \rightarrow Z $$.

  • Pseudotransitivity: $$\displaystyle X \rightarrow Y $$, $$\displaystyle YZ \rightarrow W $$ ⇒ $$\displaystyle XZ \rightarrow W $$.

• Closure Algorithm:

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

• Minimal Cover (Canonical Cover):

  1. Right-hand side single attribute.

  2. Remove extraneous LHS attributes.

  3. Remove redundant FDs.

Normal Forms

Normalization Process

1. To 2NF: Remove partial dependencies → decompose into smaller relations.

2. To 3NF: Remove transitive dependencies.

3. To BCNF: For each FD $$\displaystyle X \rightarrow Y $$ where $X$ not a superkey, decompose $R$ into $$\displaystyle R_1(X,Y) $$ and $$\displaystyle R_2(X, \text{other attributes}) $$.

4. To 4NF: For MVD $X \twoheadrightarrow Y$ with $X$ not a superkey, decompose into $$\displaystyle R_1(X,Y) $$ and $$\displaystyle R_2(X, \text{other attributes}) $$.

[!TIP] Key Insight: BCNF may lose dependency preservation; 3NF always preserves dependencies but may have redundancy.

Decomposition

• Lossless Join Decomposition: $R$ decomposed into $$\displaystyle R_1, R_2 $$ is lossless if $$\displaystyle R_1 \cap R_2 \rightarrow R_1 $$ or $$\displaystyle R_1 \cap R_2 \rightarrow R_2 $$ (using FDs).

  • Test: Compute $$\displaystyle (R_1 \cap R_2)^+ $$ under $F$; must include either $$\displaystyle R_1 $$ or $$\displaystyle R_2 $$.

• Dependency Preserving: Union of projected FDs on $$\displaystyle R_i $$ must imply original $F$.

• Trade-off: BCNF decomposition may not preserve dependencies; 3NF decomposition preserves dependencies but may not be lossless? Actually, 3NF decomposition can be both lossless and dependency preserving.

5. TRANSACTION MANAGEMENT

Transaction Concepts

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

• ACID Properties:

  • Atomicity: All or nothing. $\boxed{\text{Commit or Abort}}$

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

  • Isolation: Concurrent transactions do not interfere (as if serial).

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

• Transaction States:

  
  Active → Partially Committed → Committed
  
     ↓           ↓
  
   Failed ← Aborted ← Terminated
  
  

Schedules & Serializability

• Serial Schedule: Transactions execute sequentially (no overlap).

• Non-Serial Schedule: Transactions overlap; may cause anomalies.

• Conflict Serializability:

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

  • Precedence Graph: Nodes = transactions; edge $$\displaystyle T_i \rightarrow T_j $$ if $$\displaystyle T_i $$ conflicts with $$\displaystyle T_j $$ and $$\displaystyle T_i $$ comes before $$\displaystyle T_j $$.

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

• View Serializability: More general; harder to test; requires view equivalence to some serial schedule.

Concurrency Control

• Locking Techniques:

  • Shared (S) Lock: Read lock; multiple transactions can hold.

  • Exclusive (X) Lock: Write lock; exclusive access.

• Two-Phase Locking (2PL):

  1. Growing Phase: Acquire locks, no release.

  2. Shrinking Phase: Release locks, no acquisition.

  • Guarantees conflict serializability.

  • Rigorous 2PL: All locks held until commit (prevents cascading abort).

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

• Deadlock Handling:

  • Prevention: Impose ordering on lock acquisition (wait-die, wound-wait).

  • Avoidance: Wait-for graph analysis; rollback victim.

  • Detection & Resolution: Periodic wait-for graph cycle detection; choose victim (youngest transaction).

• Timestamp Ordering:

  • Each transaction $$\displaystyle T_i $$ gets timestamp $$\displaystyle TS(T_i) $$.

  • Read/Write rules: If $$\displaystyle TS(T_i) < RTS(X) $$ or $WTS(X)$, abort/restart $$\displaystyle T_i $$.

• Optimistic Concurrency Control:

  • Phases: Read (execute without locks), Validation (check conflicts), Write (commit if valid).

  • Suitable for low-conflict workloads.

• Multiple Granularity Locking:

  • Intention Locks: IS (intention shared), IX (intention exclusive), SIX (shared with intention exclusive).

  • Allows locking at coarse (database) or fine (tuple) granularity.

Recovery System

• Database Logs (Write-Ahead Logging - WAL):

  • Record changes before writing to disk: <T_i, X, old_value, new_value>.

• Recovery Strategies:

  • Deferred Update: Apply changes to disk only at commit (log used for undo).

  • Immediate Update: Changes written to disk immediately (log used for redo/undo).

• Checkpoints:

  • Periodic checkpoint: Write all dirty buffers to disk, log <CKPT>.

  • Reduces recovery time; only consider transactions after last checkpoint.

• Recovery Algorithm (Immediate Update):

  1. Analysis: Identify transactions to undo (failed) and redo (committed but not on disk).

  2. Redo: Repeat all updates from log (including uncommitted? Actually, redo all updates from last checkpoint).

  3. Undo: Rollback failed transactions (backward using log).

• Shadow Paging:

  • Maintain two copies: current and shadow.

  • Updates on current; commit by swapping pointers.

  • No undo log needed; but copy overhead.

[!TIP] ACID vs. Transaction States: Atomicity ensured by undo/redo; Durability by WAL.

6. QUERY PROCESSING & OPTIMIZATION

Query Processing Steps

1. Parsing & Translation: Parse query, check syntax, translate to relational algebra.

2. Optimization: Generate efficient execution plan (choose algorithms, order of operations).

3. Evaluation: Execute plan using query execution engine.

Query Optimization

• Need: Reduce I/O, CPU, communication cost; critical for large databases.

• Cost-Based Optimization:

  • Measures: Disk accesses (most expensive), CPU, network.

  • Statistics: Relation sizes, attribute value distributions, indices.

  • Selectivity: Fraction of tuples satisfying condition.

  • Cost Estimation: Use statistics to estimate intermediate result sizes.

• Heuristic-Based Optimization (Rules):

  1. Perform selection and projection as early as possible.

  2. Replace Cartesian product + selection with join.

  3. Push selections and projections down the expression tree.

  4. Identify and compute most restrictive operations first.

• Expression Trees: Represent relational algebra expressions; equivalent transformations reduce cost.

Join Algorithms

Sorting in Query Processing

• External Sorting: For large relations not fitting in memory.

  • Multi-way Merge Sort:

    1. Create sorted runs (read chunks into memory, sort, write).

    2. Merge runs using $k$-way merge (with $k-1$ buffers).

7. STORAGE & INDEXING

File Organization

Indexing Techniques

• Dense Index: Index entry for every record.

• Sparse Index: Index entry for every block (or page).

• Primary Index: On primary key; sparse (if ordered file).

• Secondary Index: On non-key attribute; dense.

• Clustering Index: Order of data matches index order (at most one per table).

• Non-Clustering Index: Data order independent; may cause many I/Os.

B⁺ Trees vs. B Trees

Hashing

• Static Hashing: Fixed number of buckets; overflow chains for collisions.

  • Disadvantage: Bucket overflow with growth; performance degrades.

• Extendable Hashing (Dynamic):

  • Directory of pointers to buckets; directory doubles when bucket overflows.

  • Global Depth: Directory size; Local Depth: Bucket split threshold.

• Linear Hashing:

  • Progressive splitting; no directory; uses hash function $$\displaystyle h_i(key) = key \mod (2^i \cdot b) $$.

RAID Levels

\boxed{\text{RAID 5: } \text{Storage Efficiency} = \frac{n-1}{n} \text{ for } n \text{ disks}}

Bitmap Indexing

• Structure: Bit vector for each distinct value; 1 if tuple has value, 0 otherwise.

• Advantages: Fast set operations (AND, OR, NOT) via bitwise operations; efficient for low-cardinality attributes (e.g., gender, status).

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

8. DISTRIBUTED DATABASES

Concepts & Architecture

• Data Fragmentation:

  • Horizontal: Subsets of tuples (by range or condition).

  • Vertical: Subsets of attributes (projection).

  • Mixed: Hybrid.

• Data Replication: Copies at multiple sites; replica transparency hides replication from users.

• Distributed Query Processing: Decompose query into subqueries for fragments; combine results.

Challenges

Distributed Transaction Management

• Two-Phase Commit (2PC):

  1. Prepare Phase: Coordinator asks all participants to prepare (vote yes/no).

  2. Commit/Rollback Phase: If all yes, coordinator sends commit; else abort.

  • Blocking: Participants may block if coordinator fails.

  • Three-Phase Commit (3PC): Non-blocking variant with pre-commit phase.

9. ADVANCED TOPICS & EMERGING TRENDS

Object-Oriented DBMS (OODBMS)

• Concepts: Objects, classes, inheritance, methods, encapsulation.

• Comparison with RDBMS:

  | Aspect | RDBMS | OODBMS | |------------------|------------------------------------|-------------------------------------| | Data Model | Tables, rows | Objects, classes | | Inheritance | Not native (emulated) | Native | | Complex Data | Limited (BLOB) | Native (multimedia, CAD) | | Query Language| SQL (declarative) | OQL (object-oriented) | | Performance | Mature, optimized for joins | Better for complex objects | | Use Case | Business transactions | Engineering, multimedia, scientific |

NoSQL Databases

• Characteristics: Schema-less, horizontal scaling, BASE (Basically Available, Soft state, Eventual consistency), CAP theorem trade-offs.

• Types:

  • Document: JSON/BSON documents (MongoDB).

  • Key-Value: Simple pairs (Redis, Dynamo).

  • Column-Family: Column-oriented (Cassandra, HBase).

  • Graph: Nodes, edges (Neo4j, Amazon Neptune).

• Advantages over RDBMS: Scalability, flexibility, performance for specific workloads.

Advanced SQL Features

• Triggers:

  • Stored procedures activated by events (INSERT/UPDATE/DELETE).

  • Row-level: Execute per row; Statement-level: Execute per statement.

  • Syntax: CREATE TRIGGER ... BEFORE/AFTER ... ON table ... FOR EACH ROW ...

• Views:

  • Virtual View: Stored query; no data storage.

  • Materialized View: Stored result; refreshed periodically.

  • Updatable View: Simple views (single table, no aggregates) can be updated.

• Assertions: Global constraints (rarely implemented).

  • CREATE ASSERTION ... CHECK (NOT EXISTS (SELECT ...))

• CHECK Constraints: Column-level or table-level domain constraints.

System Catalog & Metadata

• Data Dictionary: Stores metadata (schema, constraints, user info, statistics).

• Dynamic Performance Views: Real-time statistics (e.g., V$ views in Oracle).

Oracle Application Express (APEX)

• Low-code web development environment for Oracle DB.

• Allows building web apps directly in database with PL/SQL.

10. FREQUENTLY ASKED SHORT NOTE TOPICS

Database Anomalies

• Insertion Anomaly: Cannot insert data without other data (e.g., insert Student without Course in unnormalized table).

• Deletion Anomaly: Deleting data causes loss of other data (e.g., delete last Student in Course loses Course info).

• Update Anomaly: Inconsistent updates due to redundancy (e.g., Dept name stored in multiple Student rows; update one but not others).

• Normalization eliminates anomalies by decomposing tables.

Lossless Join Decomposition

• Decomposition of $R$ into $$\displaystyle R_1, R_2 $$ is lossless if $$\displaystyle R_1 \bowtie R_2 = R $$.

• Test: $$\displaystyle R_1 \cap R_2 \rightarrow R_1 $$ or $$\displaystyle R_1 \cap R_2 \rightarrow R_2 $$ must hold in $$\displaystyle F^+ $$.

• Ensures no spurious tuples after join.

Dependency Preserving Decomposition

• Decomposition preserves dependencies if union of projected FDs on $$\displaystyle R_i $$ implies original $F$.

• Important for efficient constraint checking.

Serializability

• Conflict Serializability: Uses precedence graph; sufficient condition.

• View Serializability: Equivalent view of serial schedule; more general but NP-complete to test.

• Recoverable Schedule: If $$\displaystyle T_i $$ reads $$\displaystyle T_j $$’s write, then $$\displaystyle T_i $$ commits only after $$\displaystyle T_j $$ commits.

Two-Phase Locking (2PL)

• Protocol: Growing phase (acquire locks) → Shrinking phase (release locks).

• Guarantees: Conflict serializability.

• Drawback: May cause deadlocks; not cascade-free (unless rigorous 2PL).

Deadlock

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

• Prevention: Wait-die (older waits, younger aborts), wound-wait (older aborts younger).

• Detection: Wait-for graph cycle detection.

• Resolution: Choose victim (rollback youngest transaction).

Multi-valued Dependency (MVD) & 4NF

• MVD: $X \twoheadrightarrow Y$ means for one $X$ value, set of $Y$ values independent of other attributes.

  • Example: In Student(USN, Hobby, Language), USN →→ Hobby and USN →→ Language (independent).

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

• Decomposition: $R(X,Y,Z)$ with $X \twoheadrightarrow Y$ → $$\displaystyle R_1(X,Y) $$ and $$\displaystyle R_2(X,Z) $$ (lossless).

Join Dependency & 5NF

• Join Dependency (JD): $$\displaystyle * (R_1, ..., R_n) $$ means $$\displaystyle R = R_1 \bowtie ... \bowtie R_n $$.

• 5NF (PJ/NF): Every non-trivial JD is implied by candidate keys.

• Rare; used for complex constraints not captured by FDs or MVDs.

Shadow Paging

• Idea: Maintain two page tables: current and shadow.

• Update: Modify current pages; new pages allocated; old pages unchanged.

• Commit: Atomically switch current page table pointer to shadow.

• Recovery: On crash, discard current; use shadow (consistent).

• Drawback: Copying page table; space overhead.

Timestamp-based Concurrency Control

• Each transaction $$\displaystyle T_i $$ gets timestamp $$\displaystyle TS(T_i) $$.

• Read Rule: If $$\displaystyle TS(T_i) < WTS(X) $$, abort $$\displaystyle T_i $$; else set $$\displaystyle RTS(X) = max(RTS(X), TS(T_i)) $$.

• Write Rule: If $$\displaystyle TS(T_i) < RTS(X) $$ or $$\displaystyle TS(T_i) < WTS(X) $$, abort $$\displaystyle T_i $$; else set $$\displaystyle WTS(X) = TS(T_i) $$.

• No deadlocks; but may cause many restarts.

Optimistic Concurrency Control

• Phases:

  1. Read: Transaction reads/writes local copies; no locks.

  2. Validation: Check if conflicting transactions committed since read.

     • If conflict, abort.

  3. Write: If validated, apply writes to database.

• Suitable for low-conflict, read-heavy workloads.

Validation-based Protocols

• Same as optimistic CC; validation checks serializability condition.

• Timestamp Validation: Use timestamps to order transactions.

Multiple Granularity Locking

• Lock Modes: IS, IX, S, SIX, X.

• Intention Locks: Indicate intention to acquire finer-grained locks.

  • To lock a row in S mode, must have IS lock on table.

• Protocol: Lock compatibility matrix; lock conversion allowed only from IS to S or IX to X.

Checkpointing in Recovery

• Purpose: Reduce recovery time; limit log scanning.

• Implementation:

  • Write all dirty buffers to disk.

  • Write <CKPT> log record with list of active transactions.

• Recovery: Start from last checkpoint; redo committed transactions after checkpoint; undo active transactions at checkpoint.

RAID Technology

• See Section 7 table.

Hashing Techniques

• Static Hashing: Fixed buckets; overflow chains.

• Extendable Hashing: Directory with global depth; bucket split doubles directory.

• Linear Hashing: Progressive splitting; no directory; uses $$\displaystyle h_i(key) = key \mod (2^i \cdot b) $$.

Bitmap Indexing

• See Section 7.

Entity Integrity vs. Referential Integrity

• Entity Integrity: Primary key cannot be NULL.

• Referential Integrity: Foreign key must reference existing primary key or be NULL; actions on delete/update.

Data Dictionary & System Catalog

• Data Dictionary: Metadata repository (tables, columns, types, constraints, users).

• System Catalog: DBMS-specific tables storing metadata (e.g., INFORMATION_SCHEMA in SQL).

• Dynamic Performance Views: Real-time statistics (e.g., V$SESSION in Oracle).

Triggers

• Types:

  • Row-level: Execute per affected row (FOR EACH ROW).

  • Statement-level: Execute once per statement.

  • Before/After: Timing relative to event.

• Use Cases: Auditing, enforcing complex constraints, maintaining summary tables.

• Syntax: CREATE TRIGGER trig_name BEFORE INSERT ON table FOR EACH ROW BEGIN ... END;

Views

• Virtual View: Defined by query; no storage; CREATE VIEW view_name AS SELECT ....

• Materialized View: Stored result; CREATE MATERIALIZED VIEW ... REFRESH ....

• Updatable Views: Simple views (single table, no aggregates, no DISTINCT) can be updated; otherwise WITH CHECK OPTION.

Expression Evaluation Plan in Query Optimization

• Expression Tree: Nodes = operators; leaves = relations.

• Plan: Choose order of operations, algorithms for each operator.

• Heuristics: Push selections/projections down; compute smallest intermediate results first.

Complexity Measures in Query Optimization

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

• CPU Cost: Tuple processing, comparisons.

• Network Cost: Distributed queries.

• Selectivity: Fraction of tuples satisfying condition; affects intermediate result size estimation.

Components of DBMS (Detailed)

1. Storage Manager:

   • File Manager: Allocates disk space.

   • Buffer Manager: Caches pages in memory; implements buffer replacement (LRU, etc.).

   • File Organization: Heap, sorted, hash.

   • Index Manager: Creates/maintains indices.

2. Query Processor:

   • DDL Interpreter: Processes schema definitions.

   • DML Compiler: Translates DML to query evaluation plan.

   • Query Optimizer: Chooses efficient plan.

   • Execution Engine: Executes plan.

3. Transaction Manager:

   • Concurrency Control: Locking, timestamp.

   • Recovery Manager: Logs, checkpoints, undo/redo.

Recoverability of Schedules

• Recoverable Schedule: If $$\displaystyle T_i $$ reads $$\displaystyle T_j $$’s write, then $$\displaystyle T_i $$ commits only after $$\displaystyle T_j $$ commits.

• Cascadeless Schedule: No transaction reads another’s uncommitted write.

• Strict Schedule: No transaction reads/writes another’s uncommitted write (only S locks held until commit).

• Importance: Prevents dirty reads, cascading aborts; ensures atomicity.

Final Exam Strategy:

1. Definitions first – always start with clear definitions (e.g., ACID, normalization forms).

2. Diagrams – draw ER diagrams, precedence graphs, B⁺ trees when asked.

3. Examples – illustrate every concept with a small example (e.g., FD closure, relational algebra).

4. Comparisons – use tables for vs. questions (DBMS vs File System, BCNF vs 3NF).

5. Formulas – box key formulas (Armstrong’s Axioms, closure algorithm, RAID efficiency).

6. Algorithms – pseudo-code for closure, 2PL, recovery phases.

7. Common Pitfalls – note where students err (e.g., confusing partial vs transitive dependency).