Data base Management System (CY-405) - Unit 2 Short Notes

UNIT 2: DATABASE MANAGEMENT SYSTEM – COMPREHENSIVE SHORT NOTES

1. INTRODUCTION & DBMS FUNDAMENTALS

DBMS vs. File System

A Database Management System (DBMS) is software for storing, retrieving, and managing data in a structured way, providing an abstract view of data. In contrast, a file system manages data as unstructured files in directories.

Advantages of DBMS:

• Data Independence: Changes in physical storage don’t affect logical schema.

• Reduced Redundancy: Avoids duplicate data via normalization.

• Controlled Redundancy: Strategic duplication for performance (e.g., denormalization).

• Data Integrity: Enforces constraints automatically.

• Security: Access control, authentication, auditing.

• Concurrent Access: Multi-user transactions with isolation.

• Backup & Recovery: Crash recovery, transaction rollback/redo.

Database System Architecture

• Three-Level Architecture (ANSI/SPARC):

  • External Level: User views (subschemas).

  • Conceptual Level: Global logical structure (all users' view).

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

• Mappings: Connect levels (e.g., External–Conceptual, Conceptual–Internal). Enable data independence.

• Components:

  • Storage Manager: File organization, indexing, buffer management.

  • Query Processor: Parsing, optimization, execution.

  • Transaction Manager: Concurrency control, recovery.

  • Authorization & Integrity Manager: Constraint checking.

• Database Administrator (DBA): Schema design, security, backup, performance tuning, user management.

Data Models & Schema

• Types:

  • Relational: Tables (most common).

  • Hierarchical: Tree structure (parent-child).

  • Network: Graph structure (sets/records).

  • Object-Oriented: Objects with encapsulation, inheritance.

  • NoSQL: Document, Key-Value, Column, Graph.

• Schema vs. Instance:

  • Schema (Intension): Logical design (tables, columns, types).

  • Instance (Extension): Actual data at a moment.

• Data Independence:

  • Logical: Change conceptual schema without affecting external views or applications.

  • Physical: Change storage without affecting conceptual schema.

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

Database Users & Interfaces

• Naive Users: Casual end-users (forms, menus).

• Application Programmers: Write applications (embedded SQL, ODBC/JDBC).

• Sophisticated Users: Write complex queries (SQL, relational calculus).

• DBA: System administrators (privileged interfaces).

2. DATA MODELING: ENTITY-RELATIONSHIP (ER) MODEL

Basic Concepts

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

• Entity Type/Set: Collection of similar entities (e.g., all Students).

• Attributes:

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

  • Composite: Multi-part (e.g., Address = {Street, City}).

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

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

• Relationships: Association among entities (e.g., Enrolls).

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

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

  • Role Names: Distinguish roles in recursive relationships (e.g., Manager–Employee).

Constraints

• Participation:

  • Total: Every entity participates (double line).

  • Partial: Some entities may not participate.

• Mapping Cardinalities:

  • 1:1: One entity relates to at most one in other set.

  • 1:N: One entity relates to many in other set.

  • M:N: Many-to-many (requires separate relationship table).

• Weak vs. Strong Entities:

  • Strong: Has primary key (underline).

  • Weak: No key; uses partial key + identifying relationship (double diamond) + owner entity.

Extended Features

• Generalization (top-down): Subclasses inherit from superclass (e.g., Vehicle → Car, Truck).

• Specialization (bottom-up): Defining subclasses within a superclass.

• Constraints on Generalization:

  • Disjoint: Subclasses disjoint (no overlap).

  • Overlapping: Subclasses may overlap.

  • Total: Every superclass entity must be in some subclass.

  • Partial: Some superclass entities may not be in any subclass.

• Aggregation: Treats relationship as higher-level entity (e.g., Enrolls(Student, Course) → Offered(Course, Semester)).

ER to Relational Mapping

Example Mapping (University):

Entities: Student(roll_no, name), Course(course_id, title)

Relationship Enrolls (M:N) → Enrolls(roll_no, course_id, grade).

3. RELATIONAL MODEL & RELATIONAL ALGEBRA

Concepts

• Relation Schema: $$\displaystyle R(A_1, A_2, ..., A_n) $$ with attribute domains.

• Relation Instance: Set of tuples at a given time.

• Properties:

  • Tuples unordered (sets).

  • Attributes unordered.

  • All values atomic (1NF).

  • Unique relation name.

  • Each tuple unique (via key).

Keys & Integrity

• Super Key: Set of attributes uniquely identifying tuples.

• Candidate Key: Minimal super key.

• Primary Key: Chosen candidate key (unique, NOT NULL).

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

• Integrity Constraints:

  • Entity Integrity: PK NOT NULL, unique.

  • Referential Integrity: FK value must exist in referenced PK or be NULL.

  • Domain Constraints: Attribute values within domain.

  • User-defined: CHECK constraints.

  • Assertions: Database-wide conditions (rarely used).

  • Triggers: Procedural code on events (INSERT/UPDATE/DELETE).

Relational Algebra Operations

Fundamental (6 operations):

1. Select (σ): Row filter.

   $$\displaystyle \sigma_{\text{condition}}(R) $$

2. Project (Π): Column filter.

   $$\displaystyle \Pi_{A_1, A_2}(R) $$

3. Union (∪): Tuples in either R or S (both same schema).

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

5. Cartesian Product (×): All pair combinations.

6. Rename (ρ): Rename relation/attributes.

   $$\displaystyle \rho_{S(A_1, A_2)}(R) $$

Additional:

• Intersection (∩): $$\displaystyle R \cap S = R - (R - S) $$

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

• Division (÷): Find tuples in R that relate to all tuples in S.

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

• Outer Joins:

  • Left Outer Join ($$\displaystyle \bowtie_L $$): All left tuples, NULL for non-matching right.

  • Right Outer Join ($$\displaystyle \bowtie_R $$): All right tuples, NULL for non-matching left.

  • Full Outer Join ($$\displaystyle \bowtie_F $$): All tuples from both, NULL where no match.

Expression Trees: Operators as nodes, operands as leaves. Bottom-up evaluation.

Relational Calculus

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

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

• Safe Expressions: Finite results (no unrestricted quantification).

• Equivalence: Relational algebra and safe relational calculus have same expressive power (Codd’s theorem).

4. SQL & QUERY PROCESSING

DDL (Data Definition Language)

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;

DROP TABLE Student;

TRUNCATE TABLE Student; -- Removes all rows, resets identity.

DML (Data Manipulation Language)

Basic SELECT:

SELECT DISTINCT dept FROM Student WHERE year = 3;

Special Operators:

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

• BETWEEN: Range inclusive.

• IN: Membership in set.

• EXISTS: Subquery returns rows.

• ANY/ALL: Comparison with any/all values in subquery.

Aggregate Functions:

SELECT dept, COUNT(*) AS num, AVG(salary) 

FROM Employee 

GROUP BY dept 

HAVING AVG(salary) > 50000;

Subqueries:

• Non-correlated: Executed once.

• Correlated: References outer query; executed per outer row.

Joins:

-- Equi-join

SELECT * FROM Student S JOIN Enrolls E ON S.roll_no = E.roll_no;
-- Natural join (implicit on same-named columns)

SELECT * FROM Student NATURAL JOIN Enrolls;
-- Self-join

SELECT A.name, B.name FROM Student A, Student B WHERE A.advisor_id = B.roll_no;
-- Outer joins

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

Advanced SQL

• Views:

  
  CREATE VIEW CS_Students AS
  
  SELECT roll_no, name FROM Student WHERE dept = 'CS'
  
  WITH CHECK OPTION; -- Ensures inserts/updates through view satisfy WHERE.
  
  

  • Updatable if: Single table, no aggregates/DISTINCT, all NOT NULL columns included.

• Triggers:

  
  CREATE TRIGGER update_total AFTER INSERT ON OrderItems
  
  FOR EACH ROW
  
  BEGIN
  
      UPDATE Orders SET total = total + NEW.amount 
  
      WHERE order_id = NEW.order_id;
  
  END;
  
  

  • Row-level: Per affected row.

  • Statement-level: Per SQL statement.

• Indexes:

  
  CREATE INDEX idx_dept ON Student(dept);
  
  

  • Speeds up search; slows down updates.

• Hierarchical Queries (Oracle):

  
  SELECT * FROM Employee
  
  START WITH manager_id IS NULL
  
  CONNECT BY PRIOR emp_id = manager_id;
  
  

Query Processing & Optimization

Phases:

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

2. Translation: Parse tree → relational algebra expression.

3. Optimization: Choose lowest-cost evaluation plan.

4. Execution: Run plan via code generator.

Need for Optimization: Reduce I/O, CPU, communication cost. Critical for large databases.

Cost Measures:

• I/O Cost: Block transfers (dominant).

• CPU Cost: Tuple processing.

• Communication Cost: Distributed DBs.

• Response Time: Wall-clock time.

Optimization Approaches:

• Heuristic (Rule-based):

  • Push selections (σ) and projections (Π) early.

  • Replace Cartesian product + selection with join.

  • Combine consecutive selections: $$\displaystyle \sigma_{c1}(\sigma_{c2}(R)) = \sigma_{c1 \land c2}(R) $$.

• Cost-Based:

  • Use statistics (table sizes, distinct values, indexes).

  • Generate equivalent expressions → estimate cost → choose minimal.

  • Expression Trees: Reorder operations (commutativity, associativity).

Example:

Query: SELECT name FROM Student WHERE dept='CS' AND year=3

Heuristic: Apply σ before Π.

Cost-based: Use index on (dept, year) if available.

5. DATABASE DESIGN & NORMALIZATION

Functional Dependencies (FDs)

• Definition: $$\displaystyle X \rightarrow Y $$ means for any two tuples, if $X$ values equal, then $Y$ values equal.

• Armstrong’s Axioms (sound & complete):

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

• Inference 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 ($$\displaystyle X^+ $$): Attributes functionally determined by $X$ using FDs.

  • Algorithm: Start $$\displaystyle X^+ = X $$; repeatedly add $Y$ if $$\displaystyle Y \subseteq X^+ $$ for some FD $$\displaystyle Z \rightarrow Y $$ with $$\displaystyle Z \subseteq X^+ $$.

• Minimal Cover ($$\displaystyle F_c $$):

  1. Ensure RHS single attribute.

  2. Remove extraneous LHS attributes.

  3. Remove redundant FDs.

  Example: $$\displaystyle AB \rightarrow C $$, $$\displaystyle B \rightarrow D $$, $$\displaystyle A \rightarrow B $$ → minimal: $$\displaystyle A \rightarrow B $$, $$\displaystyle B \rightarrow D $$, $$\displaystyle AB \rightarrow C $$.

Normal Forms

• Prime Attribute: Part of any candidate key.

• Non-prime Attribute: Not part of any candidate key.

Decomposition

• Lossless-Join Decomposition: $R$ decomposed 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 $$ (using FDs).

• Dependency-Preserving: $$\displaystyle F^+ = (F_1 \cup F_2)^+ $$ where $$\displaystyle F_i $$ are FDs in $$\displaystyle R_i $$.

• Steps to 3NF/BCNF:

  1. Find minimal cover $$\displaystyle F_c $$.

  2. For each FD $$\displaystyle X \rightarrow A $$ in $$\displaystyle F_c $$, create relation $$\displaystyle R_i = X \cup A $$.

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

  4. (BCNF) May lose dependencies; 3NF guarantees preservation.

Anomalies in Unnormalized DB

• Insertion Anomaly: Cannot insert data without other data.

  Example: Insert new course without student.

• Update Anomaly: Inconsistent updates due to redundancy.

  Example: Change instructor name in multiple rows.

• Deletion Anomaly: Deleting data loses other data.

  Example: Delete last student in course → lose course info.

• Normalization eliminates anomalies by organizing attributes into tables based on FDs.

6. STORAGE, INDEXING & FILE ORGANIZATION

File Organization

Indexing

• Purpose: Speed up search (avoid full scan).

• Types:

  • Primary vs Secondary: Primary index on sorted PK; secondary on non-key.

  • Clustering vs Non-clustering: Clustering index orders data by key (one per table); non-clustering separate.

  • Dense vs Sparse: Dense: entry for every search key value; Sparse: for some values (e.g., primary index on sorted file).

  • Single-level vs Multi-level: Multi-level (e.g., B+ tree) reduces I/O.

B⁺ Trees

• Structure:

  • All leaves at same level; contain data pointers.

  • Internal nodes: $n$ pointers, $n-1$ keys (separator values).

  • Order $d$: Min $d$ pointers (except root), max $2d$ pointers.

• Search: Start at root, follow pointers.

• Insertion: Insert in leaf; split if overflow → propagate up.

• Deletion: Merge/redistribute; may propagate up.

• Advantages: Balanced, logarithmic height, efficient inserts/deletes.

Bitmap Indexing

• Concept: Bit vector for each distinct value (1 if present, 0 otherwise).

• Use Cases: Low-cardinality attributes (gender, status).

• Operations: Fast AND/OR via bitwise ops.

• Space: Efficient for sparse data.

Hashing Techniques

• Static Hashing:

  • Hash function $$\displaystyle h(k) \rightarrow $$ bucket (fixed number).

  • Overflow: Chaining or open addressing.

  • Drawback: Bucket overflow; cannot grow/shrink dynamically.

• Extendable Hashing:

  • Directory: Array of pointers to buckets.

  • Global depth $i$: $$\displaystyle 2^i $$ buckets.

  • Local depth $j$: Bucket split when full; if $$\displaystyle j < i $$, adjust directory; if $$\displaystyle j = i $$, double directory.

  • Splitting: Rehash bucket contents with one more bit.

• Linear Hashing:

  • No directory; overflow pages.

  • Split pointer rounds: When overflow, split next bucket in round-robin.

  • Gradual growth.

RAID Levels

7. TRANSACTION MANAGEMENT

Transaction Concept

• Transaction: Logical unit of work (READ/WRITE operations). Must be atomic.

• States:

  1. Active: Executing.

  2. Partially Committed: Final operation done, changes in buffer.

  3. Committed: Changes written to disk (durable).

  4. Failed: Abort due to error.

  5. Aborted: Rolled back; may restart.

  6. Terminated: End state.

• State Diagram:

  Active → Partially Committed → Committed

  Active → Failed → Aborted → (Restart) Active or Terminated.

ACID Properties

• Atomicity: All or nothing. Implemented via undo (rollback).

• Consistency: Preserves integrity constraints (user/DBMS responsibility).

• Isolation: Concurrent transactions don’t interfere (via concurrency control).

• Durability: Committed changes survive failures (via redo logging).

Example: Transfer $100 from A to B.

Atomicity: Either both debit A and credit B, or neither.

Isolation: Concurrent transfer from A shouldn’t see intermediate state.

Schedules & Serializability

• Schedule (History): Order of operations from multiple transactions.

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

• Non-serial Schedule: Interleaved operations (higher concurrency).

• Conflict Serializability:

  • Conflict: Two operations from different transactions on same data, at least one is write.

  • Conflict-equivalent: Same order of conflicting operations.

  • Testing: Build precedence graph (Ti → Tj if Ti’s op conflicts with Tj’s earlier op).

    Serializable iff no cycle.

• View Serializability: Equivalent if:

  1. Same initial reads.

  2. Same final writes.

  3. Same read-from relationships.

  (Harder to test; not used in practice.)

• Schedule Types:

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

  • Cascadeless: No transaction reads data written by uncommitted transaction.

  • Strict: No write-read/write-write conflicts until writer commits (most restrictive).

8. CONCURRENCY CONTROL

Need & Problems

• Need: Maximize concurrency while maintaining consistency.

• Problems without control:

  • Lost Update: Overlapping writes (T1 and T2 both update same item, last wins).

  • Dirty Read: Read uncommitted data (T1 updates, T2 reads, T1 aborts).

  • Unrepeatable Read: Inconsistent reads within transaction (T1 reads X, T2 updates X, T1 reads X again → different).

  • Phantom Read: New rows appear in range query (T1 reads set, T2 inserts, T1 reads again → new rows).

Locking-Based Protocols

• Lock Modes:

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

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

• Two-Phase Locking (2PL):

  • Growing Phase: Acquire locks (no release).

  • Shrinking Phase: Release locks (no acquire).

  • Guarantees: Conflict serializability.

  • Variants:

    • Rigorous 2PL: All locks held till commit (strict, prevents cascading abort).

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

• Lock Manager: Maintains lock table (data item, lock mode, transaction list). Handles lock requests (grant/queue/wait).

Deadlock Management

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

• Prevention:

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

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

  • Resource Ordering: Assign global order to resources; request in order.

• Detection:

  • Wait-For Graph (WFG): Nodes = transactions; edge Ti→Tj if Ti waits for Tj.

  • Periodic cycle detection → deadlock exists.

• Resolution: Victim selection (abort one transaction). Criteria: least progress, youngest, fewest updates.

Other Techniques

• Timestamp Ordering:

  • Each transaction gets timestamp $TS(T)$.

  • Read: If $$\displaystyle TS(T) < W\_timestamp(X) $$, reject; else read, set $$\displaystyle R\_timestamp(X) = max(R\_timestamp(X), TS(T)) $$.

  • Write: If $$\displaystyle TS(T) < R\_timestamp(X) $$ or $$\displaystyle TS(T) < W\_timestamp(X) $$, reject; else write, set $$\displaystyle W\_timestamp(X) = TS(T) $$.

  • Thomas’s Write Rule: Ignore outdated writes ($$\displaystyle TS(T) < W\_timestamp(X) $$) without abort.

• Optimistic (Validation) Protocols:

  • Phases:

    1. Read: Transaction reads, writes to local workspace.

    2. Validation: Check if conflicts with committed transactions.

    3. Write: If validated, apply updates; else abort.

  • Validation Test: For Ti, ensure no Tj (committed during Ti) with:

    (Tj writes item read by Ti) OR (Tj reads item written by Ti) OR (Tj writes item written by Ti).

• Multiple Granularity Locking:

  • Hierarchy: Database → Segment → Page → Record → Field.

  • Intention Locks:

    • IS: Intention to set S lock on lower level.

    • IX: Intention to set X lock on lower level.

    • SIX: S lock on this level, IX on lower.

  • Protocol: To lock a node, must have compatible intention lock on ancestors.

9. RECOVERY SYSTEM

Storage & Failure Types

• Volatile Storage: RAM (lost on crash).

• Non-volatile Storage: Disk, flash (persistent).

• Failure Types:

  • Transaction Failure: Logical error, abort.

  • System Crash: Power loss, OS crash (volatile loss).

  • Disk Failure: Physical damage (non-volatile loss).

  • Media Failure: Disk crash; requires backup.

Database Logs

• Purpose: Record all changes for recovery.

• Log Records:

  • <Begin T>

  • <T, X, old_value, new_value> (update)

  • <Commit T>

  • <Abort T>

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

• Force/Steal Policies:

  • Force: All updates written at commit (slow commit, fast recovery).

  • No-force: Updates may stay in buffer after commit (fast commit, recovery needs redo).

  • Steal: Buffer pages may be written before commit (need undo).

  • No-steal: Buffer pages not written until commit (no undo needed).

Recovery Techniques

• Immediate Update:

  • Changes written to DB before commit.

  • Recovery: From last checkpoint, undo loser transactions (write old values), redo winners (write new values).

  • Uses log with before/after images.

• Deferred Update:

  • Changes written only at commit.

  • Recovery: From last checkpoint, redo committed transactions (no undo needed).

  • Simpler but slower commits.

Checkpointing

• Purpose: Reduce recovery time (limit log scan).

• Mechanism:

  1. Flush all dirty buffers to disk.

  2. Write <Checkpoint> record to log (list of active transactions).

• Recovery: Start from last checkpoint; redo all transactions after checkpoint; undo losers.

Buffer Management

• Buffer Pool: Memory area for disk pages.

• Replacement Policies:

  • LRU (Least Recently Used): Evict least recently accessed.

  • MRU (Most Recently Used): Evict most recent (good for repeated scans).

  • Clock: Approximation of LRU.

• Dirty Bit: Indicates modified page; flush on eviction if dirty.

10. DISTRIBUTED DATABASES

Concepts & Architecture

• Definition: Database spread across multiple sites, connected via network.

• Motivations: Local autonomy, reliability (no single point failure), scalability, performance (data locality).

• Architecture: Each site has local DBMS; coordinated by distributed DBMS.

Data Distribution & Replication

• Fragmentation:

  • Horizontal: Subsets of rows (by condition).

  • Vertical: Subsets of columns (projection).

  • Hybrid: Mixed (first horizontal, then vertical).

• Replication: Copy data at multiple sites.

  • Advantages: Availability, read performance.

  • Disadvantages: Update overhead, consistency challenges.

• Transparency:

  • Location: Users unaware of data location.

  • Replication: Users unaware of copies.

  • Fragmentation: Users unaware of fragmentation.

Challenges

• Distributed Query Processing:

  • Minimize communication cost (transfer data between sites).

  • Strategies: Move computation to data, semijoin reduction.

• Distributed Transaction Management:

  • 2-Phase Commit (2PC):

    1. Prepare: Coordinator asks all participants to prepare (vote commit/abort).

    2. Commit/Abort: If all vote commit, coordinator sends commit; else abort.

    • Drawback: Blocking (if coordinator fails, participants wait).

• Concurrency Control:

  • Distributed Locking: Centralized or distributed lock manager (e.g., two-phase locking with lock requests across sites).

  • Timestamp: Global timestamp generator (e.g., physical clock + site ID).

• Recovery:

  • Distributed Logging: Each site logs locally; coordinated checkpoint.

  • Failure Handling: Site failures, network partitions (use voting, consensus).

• Network Partitions: Split-brain problem; need agreement protocols (e.g., Paxos, Raft).

11. ADVANCED TOPICS & EMERGING TRENDS

Object-Oriented DBMS (OODBMS)

• vs RDBMS:

  | Feature | RDBMS | OODBMS | |-------------------|----------------------------|-----------------------------| | Data Model | Tables, rows, columns. | Objects, classes, inheritance. | | Complex Data | Normalized, limited types. | Native support (arrays, nested). | | Methods | Separate (application). | Encapsulated in objects. | | Schema | Fixed, rigid. | Flexible, evolvable. | | Query Language| SQL (declarative). | OQL (object-oriented). | | Performance | Good for simple queries. | Better for complex objects. | | Use Cases | Business apps, transactions.| CAD, multimedia, scientific. |

• Strengths: Handles complex data, inheritance, avoids impedance mismatch.

• Weaknesses: Less mature, no standard, weaker ad-hoc query support.

NoSQL Databases

• Characteristics:

  • Schema-less (dynamic columns).

  • Horizontal scaling (sharding).

  • BASE model (Basic Availability, Soft state, Eventual consistency) vs ACID.

  • CAP Theorem: Consistency, Availability, Partition Tolerance – pick two.

• Types:

  • Document: JSON/BSON (MongoDB). Flexible schema.

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

  • Column-Family: Wide-column (Cassandra, HBase). Scalable writes.

  • Graph: Nodes/edges (Neo4j). Relationship-heavy queries.

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

• Disadvantages: Weak consistency, limited transactions, no joins (denormalize).

Other Special Topics

• Data Dictionary / System Catalog:

  • Stores metadata (schemas, constraints, user info).

  • Queried via system tables (e.g., INFORMATION_SCHEMA in SQL).

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

• Web & Mobile Databases:

  • Access Patterns: REST APIs, GraphQL.

  • Synchronization: Offline support, conflict resolution (e.g., Couchbase Mobile).

• Oracle Application Express (APEX):

  • Low-code web app development on Oracle DB.

  • Built-in components, SQL-centric.

• Complex Data Types:

  • Spatial: GIS data (PostGIS).

  • Temporal: Time-series, valid time.

  • Multimedia: Images, video (BLOBs, indexing).

• XML & Semi-structured Data:

  • XQuery: Query XML documents.

  • XPath: Navigate XML tree.

  • Storage: Shredded (relational) or native XML DB.

KEY FORMULAS & THEOREMS

\boxed{X^+ = \text{closure of } X \text{ under } F}

\boxed{\text{Lossless: } R_1 \bowtie R_2 = R \iff (R_1 \cap R_2 \rightarrow R_1) \lor (R_1 \cap R_2 \rightarrow R_2)}

\boxed{\text{2PL ensures conflict serializability.}}

\boxed{\text{WAL: Log record written before data page.}}

\boxed{\text{RAID } n \text{ uses } n \text{ disks with parity for fault tolerance.}}

Exam Tips:

• ER Diagrams: Always label entities, attributes (underline PK), relationships (cardinality, participation). Weak entity → double rectangle, identifying relationship → double diamond.

• Normalization: Identify FDs first. For 2NF, check partial dependencies on proper subset of candidate key. BCNF stricter than 3NF.

• Relational Algebra: Use expression trees; remember division for “for all” queries.

• SQL: GROUP BY with aggregates; HAVING filters groups; EXISTS vs IN (NULL handling).

• Serializability: Draw precedence graph; cycle → not serializable.

• 2PL: Growing phase (acquire all locks), shrinking phase (release). Rigorous 2PL holds locks till commit → strict schedule.

• Recovery: Checkpoint reduces log scan. Immediate update needs undo/redo; deferred needs only redo.

• Hashing: Extendable hashing uses directory with global/local depth; linear hashing uses split pointer.

• Distributed DB: 2PC blocking problem; fragmentation vs replication trade-offs.