Data Base Management System (IT-405) - Unit 1 Short Notes

UNIT 1: DATABASE MANAGEMENT SYSTEM

I. INTRODUCTION TO DATABASE SYSTEMS

Data is a collection of raw facts. A Database is an organized collection of data, generally stored and accessed electronically. A Database Management System (DBMS) is software that interacts with end-users, applications, and the database itself to capture and analyze data.

File System vs DBMS

Advantages of DBMS: Reduced redundancy, improved consistency, data independence, efficient data access, enforced integrity, concurrent access control, backup/recovery, security, multiple data views.

Typical DBMS Architecture (Three-Level Architecture)

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

• Conceptual Level (Logical Level): Community view, all logical structures (tables, relationships) and constraints.

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

Components:

• Storage Manager: Manages storage allocation, file organization, indexing, and buffer management.

• Query Processor: Parses and optimizes queries, generates executable plans.

Data Independence

• Logical Data Independence: Ability to change conceptual schema without affecting external schemas or applications.

  Example: Adding a new attribute to a table doesn’t require changing existing queries that don’t use it.

• Physical Data Independence: Ability to change internal schema (storage structures, file organization) without affecting conceptual schema.

  Example: Changing from heap file to indexed file doesn’t change table structure.

Database Users & DBA Roles

• Users: Casual, naive, sophisticated, application programmers.

• DBA (Database Administrator):

  • Schema definition & modification

  • Storage structure & access method definition

  • Granting user access privileges

  • Integrity constraint specification

  • Backup and recovery

  • Tuning performance

  • Emergency operations

Database System Applications

Banking, airlines, universities, manufacturing, sales, HR, online retailers, etc.

II. DATA MODELS

Data Model: A formalism for describing data, relationships, semantics, and constraints.

Schema vs Instance:

• Schema (Intension): Logical design, structure, constraints (e.g., CREATE TABLE statement).

• Instance (Extension): Actual data at a moment in time (rows in tables).

Degree & Cardinality of Relationships:

• Degree: Number of entity sets participating (binary, ternary, etc.).

• Cardinality: Mapping constraints (1:1, 1:N, M:N).

III. ENTITY-RELATIONSHIP (ER) MODEL

Basic Concepts

• Entity: Real-world object distinguishable from others (e.g., student, course).

• Entity Type: Collection of similar entities (e.g., Student).

• Entity Set: Set of entities of a type at a point in time.

• Attributes: Properties of an entity.

  • Simple (atomic): Roll_no

  • Composite: Address (street, city, pin)

  • Multivalued: Phone_numbers (multiple values)

  • Derived: Age (from DOB)

• Relationships: Association among entities.

  • Degree: Number of entity sets (binary, ternary).

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

  • Role: Function of an entity in a relationship (e.g., Student as Enroller).

  • Participation: Total (every entity participates) or Partial.

ER Diagram Notation

• Entity: Rectangle

• Attribute: Oval (double oval for multivalued, dashed for derived)

• Relationship: Diamond

• Connecting lines: Link entities to relationships.

Weak Entity Sets

• Definition: Entity set without a primary key; existence depends on another entity (owner).

• Partial Key (Discriminator): Set of attributes that uniquely identify weak entities within an owner entity.

• Identifying Relationship: Double diamond; weak entity is connected via this to owner.

• Example: Dependent (Name, DOB) weak on Employee (Emp_ID). Partial key: Name; identifying relationship Has_Dependent.

Generalization, Specialization, Aggregation

• Generalization: Bottom-up; extract shared features to form a supertype (e.g., Car, Truck → Vehicle).

• Specialization: Top-down; create subtypes from a supertype (e.g., Employee → Clerk, Manager).

• Aggregation: Treat relationship as an entity to relate to other entities (e.g., Enrollment as entity to relate Student and Course to Instructor).

Constraints in ER Models

• Key Constraint: Unique identification.

• Participation Constraint: Total/Partial.

• Referential Integrity: Foreign key references valid primary key.

Mapping ER Diagrams to Relational Schemas

1. Regular Entity Type: Table with all simple/composite attributes; primary key.

2. Weak Entity Type: Table with owner’s PK + partial key; PK = owner PK + partial key.

3. 1:N Relationship: Add foreign key (N-side) referencing 1-side PK.

4. M:N Relationship: New table with foreign keys from both sides; PK = combination.

5. Binary 1:1: Foreign key on either side (or merge).

6. Aggregation: New table for relationship set; include PK of aggregated entity.

7. Total Participation: May require foreign key NOT NULL or additional constraints.

8. Composite Attributes: Flatten into separate columns or single column (if simple).

IV. RELATIONAL MODEL

Relational Schema & Instance

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

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

Keys

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

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

• Primary Key: Chosen candidate key (unique, non-null).

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

• Composite Key: Primary key consisting of multiple attributes.

• Properties of Foreign Keys:

  • Value must exist in referenced primary key or be NULL (if allowed).

  • On delete/update: CASCADE, SET NULL, RESTRICT, NO ACTION.

Integrity Constraints

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

• Entity Integrity: Primary key cannot be NULL.

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

Relational Algebra Operators

Fundamental (5 operations):

1. Select (σ): σ_{condition}(R) – row filter.

2. Project (Π): Π_{A₁,...,Aₖ}(R) – column filter.

3. Union (∪): R ∪ S – tuples in R or S (both same schema).

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

5. Cartesian Product (×): R × S – concatenate every tuple of R with every of S.

Additional:

• Rename (ρ): ρ_{S}(R) or ρ_{A₁,...,Aₙ}(R).

• Joins:

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

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

  • Equi Join: Theta join with equality.

  • Outer Joins: Left (⋈ₗ), Right (⋈ᵣ), Full (⋈𝒻) – preserve non-matching tuples with NULLs.

Relational Calculus

• Tuple-Oriented (TRC): { t | P(t) } where t is tuple variable, P is formula.

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

• Domain-Oriented (DRC): { ⟨x₁,...,xₙ⟩ | P(x₁,...,xₙ) } where xᵢ domain variables.

  Example: { ⟨n⟩ | ∃s,d,y (⟨n,s,d,y⟩ ∈ Student ∧ d = 'CS') }

• Differences from Algebra:

  • Algebra: procedural (how to get result).

  • Calculus: declarative (what result).

  • Calculus may have non-terminating queries; algebra always terminates.

Relational Algebra vs Relational Calculus

• Algebra: Operational, step-by-step, procedural.

• Calculus: Declarative, logic-based.

• Equivalence: Safe relational calculus expressions ≡ relational algebra (Codd’s theorem).

V. SQL AND QUERY PROCESSING

SQL Categories

• DDL (Data Definition Language): CREATE, ALTER, DROP, TRUNCATE.

• DML (Data Manipulation Language): SELECT, INSERT, UPDATE, DELETE.

• DCL (Data Control Language): GRANT, REVOKE.

• TCL (Transaction Control Language): COMMIT, ROLLBACK, SAVEPOINT.

DDL Commands (Syntax)

CREATE TABLE table_name (

    col1 datatype constraint,

    col2 datatype,

    ...

);

ALTER TABLE table_name ADD column_name datatype;

ALTER TABLE table_name DROP COLUMN column_name;

DROP TABLE table_name;

TRUNCATE TABLE table_name; -- fast delete all rows

DML Commands

• INSERT INTO table VALUES (...);

• UPDATE table SET col = value WHERE condition;

• DELETE FROM table WHERE condition;

SQL Queries

• Basic: SELECT ... FROM ... WHERE ...

• Joins: INNER JOIN, LEFT/RIGHT/FULL OUTER JOIN, CROSS JOIN, SELF JOIN.

• Subqueries: Nested in WHERE, FROM, SELECT; correlated vs uncorrelated.

• Set Operations: UNION, INTERSECT, EXCEPT (or MINUS).

• Aggregation: COUNT, SUM, AVG, MIN, MAX.

• Grouping: GROUP BY, HAVING.

Special Operators

• LIKE: Pattern matching (% wildcard, _ single char).

• ANY/SOME: Compare with any value in subquery result.

• ALL: Compare with all values.

• EXISTS: Check if subquery returns any row.

• IN: Membership test.

Views

• Definition: Virtual table based on query result.

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

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

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

Triggers

• Definition: Stored procedure that auto-executes on INSERT/UPDATE/DELETE event.

• Syntax (simplified):

  
  CREATE TRIGGER trigger_name
  
  BEFORE/AFTER INSERT/UPDATE/DELETE ON table_name
  
  FOR EACH ROW
  
  BEGIN
  
      -- SQL statements
  
  END;
  
  

• Example: Update Orders total when new OrderItem added.

Assertions

• Definition: Global constraints not tied to a single table.

• Usage: CREATE ASSERTION assertion_name CHECK (condition);

  Example: CHECK ( (SELECT COUNT(*) FROM Branch) <= 100 )

Data Dictionary & Dynamic Performance Views

• Data Dictionary: System tables storing metadata (schemas, constraints, users). Examples: INFORMATION_SCHEMA in many DBMS.

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

Query Processing Phases

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

2. Translation: Convert to relational algebra expression.

3. Optimization: Choose lowest-cost execution plan (heuristic/cost-based).

4. Execution: Run plan, produce result.

Query Optimization

• Necessity: Different equivalent algebra expressions have vastly different costs (I/O, CPU, memory).

• Heuristic-Based: Apply rules to transform query:

  • Perform selections early (reduce tuple count).

  • Project early (reduce attribute count).

  • Break down complex joins.

• Cost-Based: Estimate cost of each plan using statistics (table sizes, index availability, selectivity). Choose minimal cost.

• Measures of Query Cost:

  • Disk I/O (most significant)

  • CPU cost

  • Network communication (distributed)

  • Memory usage

• Expression Evaluation Plans: Tree of operators; each node computes intermediate result.

  Example: For σ_{dept='CS'}(Student) ⋈ Enrolls ⋈ Course, push selection before join.

Complexity Measures in Query Processing

• Time Complexity: Number of I/Os, comparisons.

• Space Complexity: Buffer requirements, temporary storage.

• Join Algorithms: Nested-loop (O(n²)), sort-merge (O(n log n)), hash join (O(n)).

VI. DATABASE DESIGN AND NORMALIZATION

Need for Normalization

Eliminate anomalies:

• Insert Anomaly: Cannot insert data without other data (e.g., can’t add a new department without an employee).

• Update Anomaly: Inconsistent updates due to redundancy (e.g., change department name in one tuple but not others).

• Delete Anomaly: Deleting data inadvertently loses other data (e.g., delete last employee in a department loses department info).

Functional Dependencies (FDs)

• Definition: X → Y means value of X uniquely determines value of Y in a relation.

• Types:

  • Trivial: Y ⊆ X (e.g., AB → A).

  • Non-Trivial: Y ⊈ X.

  • Fully Functional Dependency: X → Y and no proper subset of X determines Y (for composite keys).

• Armstrong’s Axioms (sound & complete):

  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: Union, Decomposition, Pseudotransitivity.

• Closure (X⁺): Set of attributes functionally determined by X using FDs.

  • Algorithm: Start with X⁺ = X; repeatedly add Y if Y ⊆ X⁺ for some A → Y with A ⊆ X⁺.

• Minimal Cover (Canonical Cover):

  1. Decompose RHS of each FD to single attribute.

  2. Remove extraneous LHS attributes.

  3. Remove redundant FDs.

• Example:

  F = { A → BC, B → C, AB → C }

  Minimal cover: { A → B, A → C, B → C } (AB → C redundant).

Normal Forms

1NF: Domain atomicity (no repeating groups). All relational schemas are in 1NF if domains are atomic.

2NF: 1NF + every non-prime attribute fully functionally dependent on candidate key (no partial dependency on composite key).
Example: Enroll(Stud_ID, Course, Grade, Course_Name)

FDs: Stud_ID, Course → Grade, Course_Name and Course → Course_Name.

Partial: Course → Course_Name (depends on part of key). Not in 2NF.

Decompose: Enroll(Stud_ID, Course, Grade), Course(Course, Course_Name).

3NF: 2NF + no non-prime attribute transitively dependent on candidate key.

For every FD X → A, either:

• X is a superkey, or

• A is a prime attribute (part of some candidate key).
  Example: Emp(Emp_ID, Name, Dept, Dept_Location)

FDs: Emp_ID → Name, Dept; Dept → Dept_Location.

Transitive: Emp_ID → Dept → Dept_Location. Not in 3NF.

Decompose: Emp(Emp_ID, Name, Dept), Dept(Dept, Dept_Location).

BCNF (Boyce-Codd NF): For every non-trivial FD X → Y, X must be a superkey.

Stricter than 3NF; handles anomalies not covered by 3NF.
Example: Teach(Prof, Course, Time)

FDs: Prof → Course (each prof teaches one course), Course → Time (each course at fixed time).

Candidate keys: {Prof, Time}, {Course, Time}.

FD Course → Time: Course not a superkey. Not BCNF.

Decompose: Prof_Course(Prof, Course), Course_Time(Course, Time).

4NF: Deals with Multi-Valued Dependencies (MVDs).

MVD X ↠ Y means for one X value, multiple independent Y values.
4NF: For every non-trivial MVD X ↠ Y, X is a superkey.
Example: Employee(Emp_ID, Skill, Language)

An employee has multiple skills and multiple languages independently.

MVDs: Emp_ID ↠ Skill, Emp_ID ↠ Language.

If Emp_ID is key, it’s in 4NF. If not, decompose.

5NF (PJ/NF): Deals with Join Dependencies; every join dependency is implied by candidate keys. Rarely used.

Decomposition

• Lossless Join: R₁ ⋈ R₂ = R (no spurious tuples).

  Condition: R₁ ∩ R₂ → R₁ or R₁ ∩ R₂ → R₂ (common attributes form a superkey in at least one).

• Dependency Preserving: Union of FDs in decomposed schemas implies original FDs.

  Not always possible; BCNF may not preserve dependencies.

• Properties: Lossless is mandatory; dependency preserving desirable for efficient constraint checking.

Steps to Convert 3NF to BCNF

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

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

3. Recursively apply to R₁ and R₂ if not BCNF.

4. Ensure lossless join (always satisfied by this algorithm).

Identifying Highest Normal Form

1. Find candidate keys.

2. Check each FD: if LHS is superkey → OK for BCNF; else if RHS is prime → OK for 3NF; else check partial/transitive dependencies for 2NF/1NF.

VII. TRANSACTION MANAGEMENT

Transaction Concept

A transaction is a logical unit of work (sequence of operations) that must be atomic (all or nothing).
Example: Bank transfer: debit(A), credit(B).

ACID Properties

• Atomicity: Transaction completes fully or not at all.

  Implementation: Log-based recovery (undo on abort).

• Consistency: Transaction preserves database consistency (integrity constraints).

  Example: Transfer maintains total sum of accounts.

• Isolation: Concurrent transactions don’t interfere (as if executed serially).

  Implementation: Locking, timestamp ordering.

• Durability: Once committed, effects persist despite failures.

  Implementation: Write-ahead logging (WAL), stable storage.

Transaction States

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

   │   Active    │

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

         │ partially committed

         ▼

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

│ Partially Committed│

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

      │ commit/abort

      ▼

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

│   Committed │

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

      │

      ▼

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

│   Terminated│

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

• Failed: Transaction cannot proceed (e.g, integrity violation, deadlock).

• Aborted: Rollback; may restart.

Schedules

• Serial: Transactions execute one after another.

• Non-Serial: Transactions interleave operations.

• Serializable: Non-serial schedule equivalent to some serial schedule (conflict or view equivalent).

Serializability

• Conflict Serializability:

  • Two operations conflict if they belong to different transactions and access same data, with at least one write.

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

  • Schedule is conflict-serializable iff graph is acyclic.

• View Serializability: More complex; schedule must have same view of data as some serial schedule (reads-from, final write).

Recoverable Schedules

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

• Cascading Abort: Ti aborts because Tj (which Ti read from) aborts. Causes multiple rollbacks.

• Cascadeless (Strict): No transaction reads data written by uncommitted transaction. Prevents cascading aborts.

Recovery Techniques

• Log-Based Recovery:

  • Write-Ahead Logging (WAL): Log record written to stable storage before actual data.

  • Log Records: <T, X, old, new> for update; <T, start>, <T, commit>, <T, abort>.

• Deferred Database Modification:

  • Write updates to log only; apply to database only at commit time.

  • Rollback: ignore log (no partial writes).

• Immediate Database Modification:

  • Write updates to database as they occur (using WAL).

  • Rollback: use log to undo changes (backward pass).

• Checkpoints:

  • Purpose: Reduce recovery time; limit log scanning.

  • How: Periodically, write all modified buffers to disk, log <checkpoint L> where L is list of active transactions.

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

• Shadow Paging:

  • Maintain two copies: shadow (consistent) and current.

  • Updates made to current pages; on commit, swap pointers.

  • No undo log needed; abort = discard current.

  • Example: Page table with shadow pointer; new pages allocated for current; commit updates pointer.

VIII. CONCURRENCY CONTROL

Need for Concurrency Control

Allow multiple transactions to execute concurrently to:

• Increase throughput (resource utilization).

• Reduce waiting time.

But must prevent:

• Lost updates

• Dirty reads

• Unrepeatable reads

• Phantom reads

Locking Protocols

• Exclusive Lock (X): For write; no other lock allowed.

• Shared Lock (S): For read; multiple S allowed, but no X.

• Two-Phase Locking (2PL):

  • Growing Phase: Acquire locks (no release).

  • Shrinking Phase: Release locks (no acquire).

  • Guarantees conflict serializability.

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

  • Conservative 2PL: Acquire all locks at start (no deadlock, but low concurrency).

• Multiple Granularity Locking:

  Lock at different levels (database, table, page, row, attribute).

  Use intention locks (IS, IX, SIX) to allow hierarchical locking.

Deadlock

• Definition: Cycle of transactions waiting for each other’s locks.

• Prevention:

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

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

  • Resource Ordering: Impose total order on resources; request in order.

• Avoidance:

  • Wait-for Graph: Detect cycle periodically; abort victim.

  • Timeout: Abort if wait exceeds threshold.

• Detection & Resolution:

  • Build wait-for graph; if cycle, choose victim (least cost, youngest, etc.) to abort.

Timestamp-Based Concurrency Control

• Each transaction gets unique 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).

• Rules:

  • Transaction Ti wants to read X: if TS(Ti) < WTS(X) → Ti too old, abort (wound); else allow, update RTS(X).

  • Transaction Ti wants to write X: if TS(Ti) < RTS(X) or TS(Ti) < WTS(X) → abort; else write, set WTS(X)=TS(Ti).

• Ensures serializability (timestamp order) but may cause many restarts.

Validation-Based (Optimistic) Concurrency Control

Assumes conflicts rare; execute without locks, validate at commit.

• Phases:

  1. Read Phase: Read/write to local copies; writes not applied to DB.

  2. Validation Phase: Check if Ti’s reads were consistent (no other transaction wrote/read same data and committed after Ti started).

  3. Write Phase: If validated, apply writes; else abort.

• Validation Test: For Ti, ensure no Tj (with TS(Tj) < TS(Ti)) wrote data that Ti read, or Ti wrote data that Tj read/wrote.

Impact of Concurrency Control on Transaction Performance

• Locking: Can cause blocking, deadlocks; reduces concurrency.

• Timestamp: May cause many restarts (starvation possible).

• Optimistic: Best for low-conflict workloads; overhead for validation.

• Trade-off: Higher isolation (e.g., serializable) → lower concurrency.

Multiple Granularity Concurrency Control Scheme

• Granularity Levels: Database > Table > Page > Row > Attribute.

• Intention Locks:

  • IS (Intention Shared): Transaction intends to set S lock on some lower level.

  • IX (Intention Exclusive): Intends to set X lock.

  • SIX (Shared + Intention Exclusive): S on current level, IX on lower.

• Lock Compatibility Matrix governs requests.

IX. STORAGE AND INDEXING

File Organization Methods

• Heap Files: Unordered; simplest, fast insert, slow search (full scan).

• Sorted Files: Sorted on one attribute; fast range queries, binary search; slow insert (maintain order).

• Hashing: Hash function maps key to bucket; fast equality search, slow range, overflow handling.

Indexing

• Purpose: Speed up search, join, aggregation.

• Types:

  • Primary Index: On primary key; dense (every key has entry) or sparse (only some keys).

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

  • Clustering Index: Data stored in index order (one per table); physical order matches index.

  • Non-Clustering Index: Index separate from data; data not in index order.

Hashing Techniques

• Static Hashing: Fixed number of buckets; overflow chains for collisions; poor if distribution skews.

• Extendable Hashing:

  • Directory of pointers to buckets; directory size doubles when bucket overflows and prefix bits exhausted.

  • Inner attribute: Hash value bits.

  • Outer attribute: Directory index (prefix of hash).

  • Example: 3-bit hash, directory size 8; bucket splits when full, may increase global depth.

• Linear Hashing:

  • No directory; overflow handled by splitting next bucket in round-robin.

  • Split pointer tracks next bucket to split.

  • Uses modulo with varying number of buckets.

Bitmap Indexing

• Concept: For each attribute value, create bit vector (1 if tuple has value, 0 otherwise).

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

• Advantages: Fast set operations (AND/OR via bitwise), compact storage.

• Disadvantages: High maintenance on update, poor for high-cardinality.

RAID (Redundant Array of Independent Disks)

Single vs Multilevel Indices

• Single-Level: One index structure; may be large.

• Multilevel: Index on index (e.g., B+ tree root, intermediate, leaves).

  Reduces search cost (logarithmic); outer index sparse, inner dense.

X. DISTRIBUTED DATABASES

Concepts

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

• Replication: Copy data at multiple sites (improves availability, read performance).

• Transparency:

  • Location Transparency: Users don’t know where data stored.

  • Replication Transparency: Users unaware of copies.

  • Fragmentation Transparency: Users see integrated view.

Challenges

• Data Distribution: Fragmentation, allocation, replication.

• Concurrency Control: Distributed locking, timestamp, deadlock (global vs local).

• Recovery: Logging across sites; commit protocols (2-phase commit).

• Distributed Query Processing: Optimize for data locality, minimize communication.

• Distributed Transaction Management:

  • 2-Phase Commit (2PC):

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

    2. Commit/Abort: If all yes, commit; else abort.

    Blocks if coordinator/participant fails; uses stable storage.

Distributed vs Centralized DBMS

• Distributed: Data spread across sites; autonomy, scalability, reliability; complex.

• Centralized: Single site; simpler, but single point of failure, limited scalability.

XI. ADVANCED AND SPECIAL TOPICS

NoSQL Databases

• Characteristics:

  • Non-relational, schema-flexible, horizontal scalability, BASE (Basically Available, Soft state, Eventual consistency).

• Types:

  • Document (MongoDB): JSON-like documents.

  • Key-Value (Redis): Simple pairs.

  • Column (Cassandra): Column families.

  • Graph (Neo4j): Nodes, edges, properties.

• Advantages over RDBMS: Scale-out, unstructured data, high write throughput, flexible schema.

Object-Oriented DBMS (OODBMS) vs DBMS

Web and Mobile Databases

• Concepts: Sync with central DB, offline access, data compression, security (encryption).

• Challenges: Limited resources, intermittent connectivity, data consistency, security.

Hierarchical Queries

• Concept: Query hierarchical data (tree structure) using parent-child relationships.

• Example (Oracle): CONNECT BY PRIOR clause.

  
  SELECT ... FROM table
  
  START WITH condition
  
  CONNECT BY PRIOR child = parent;
  
  

Complex SQL Queries

• Nth Maximum Salary:

  
  SELECT DISTINCT Salary FROM Employee E1
  
  WHERE N = (SELECT COUNT(DISTINCT Salary) FROM Employee E2 WHERE E2.Salary > E1.Salary);
  
  

• Gross Salary (with allowances): SELECT Emp_ID, Salary + Allowance AS Gross FROM ...

Database Anomalies (Detailed)

• Insert Anomaly: Cannot insert entity without another (e.g., new department without employee).

• Update Anomaly: Inconsistent updates due to redundancy (e.g., department name stored in multiple rows).

• Delete Anomaly: Deleting entity loses unrelated data (e.g., delete last employee loses department).

Data Dictionary

• Role: Metadata repository (schemas, constraints, users, statistics).

• Components: System tables (e.g., sys.tables, INFORMATION_SCHEMA.COLUMNS).

• Dynamic Performance Views: Real-time stats (e.g., V$SESSION, sys.dm_exec_requests).

Exam Tips & Common Pitfalls:

• Keys: Distinguish super key (any unique set), candidate key (minimal), primary key (chosen candidate), foreign key (reference). Composite key = primary key with multiple attributes.

• Normalization:

• 2NF: No partial dependency on composite candidate key.

• 3NF: No transitive dependency (non-prime → non-prime).

• BCNF: Every determinant is a superkey.

• 4NF: No non-trivial MVD unless determinant is superkey.

• Relational Algebra vs Calculus: Algebra is procedural (step-by-step operators); calculus is declarative (logic formulas). Safe calculus ≡ algebra.

• ACID: Atomicity (all/nothing), Consistency (rules), Isolation (no interference), Durability (persist after commit).

• 2PL: Growing (acquire) then shrinking (release); ensures conflict serializability but not cascadeless.

• Serializability: Conflict (precedence graph acyclic); View (same read-from, final write). Conflict is stricter.

• Recovery: WAL ensures durability; checkpoints reduce log scanning; immediate modification uses undo/redo; deferred uses only redo.

• Hashing: Static (fixed buckets), Extendable (directory with global/local depth), Linear (round-robin split).

• Mapping ER to Relational:

• Weak entity: owner’s PK + partial key.

• M:N relationship: new table with two FKs.

• Aggregation: new table for relationship as entity.

• Total participation: may require NOT NULL on FK.

• SQL Joins:

• INNER JOIN: only matching rows.

• LEFT JOIN: all left rows, NULL for non-matching right.

• FULL OUTER JOIN: all rows from both, NULL where no match.

• NATURAL JOIN: equijoin on all common attribute names.

• FD Closure: Use iterative algorithm; add attributes if FD’s LHS ⊆ current closure.

• Deadlock: Prevention (resource ordering), avoidance (wait-die/wound-wait), detection (wait-for graph).