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

UNIT 5: Database Management System - Comprehensive Short Notes

1. Introduction to Database Systems

File System vs DBMS

Advantages of DBMS: Reduced redundancy, improved consistency, enhanced security, concurrent access, crash recovery, data independence, and efficient query processing.

Database System Architecture: Three-Level Architecture

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

• Conceptual Level (Logical Level): Single integrated view of entire database (logical structure, constraints). Describes what data is stored.

• Internal Level (Physical Level): Physical storage details (files, indexes, storage structures). Describes how data is stored.

Mappings:

• External-Conceptual Mapping: Translates user views to conceptual schema.

• Conceptual-Internal Mapping: Translates conceptual schema to internal storage.

Purpose: Achieves data independence—changes at one level don’t affect others.

Data Independence

• Logical Data Independence: Changes to conceptual schema (e.g., adding attributes) don’t affect external schemas or applications. Achieved via view mechanism.

• Physical Data Independence: Changes to internal schema (e.g., file organization, indexes) don’t affect conceptual or external schemas. Achieved via mapping.

Components of DBMS

1. Storage Manager: Handles storage, file organization, indexing, buffering.

2. Query Processor: Parses, optimizes, and executes queries.

3. Transaction Manager: Concurrency control, recovery.

4. Catalog Manager: Stores metadata (data dictionary).

5. Authorization Manager: Security and access control.

Database Administrator (DBA)

• Functions:

  • Installation & Configuration

  • Security & Authorization (grant/revoke privileges)

  • Backup & Recovery (schedule checkpoints, maintain logs)

  • Performance Tuning (index creation, query optimization)

  • Schema Design & Modification

  • User Support & Training

  • Capacity Planning

Types of Database Users

• Naïve Users: End-users who use applications (no SQL knowledge).

• Application Programmers: Write application programs (embedded SQL).

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

• Database Administrators (DBA): Manage the DBMS.

• System Analysts: Design databases (ER modeling).

2. Data Modeling and Entity-Relationship (ER) Model

ER Model Basics

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

• Attribute: Property of an entity (e.g., Student.Name). Represented by ellipse.

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

Types of Attributes

Types of Keys

• Super Key: Set of attributes that uniquely identifies a tuple.

• Candidate Key: Minimal super key (no subset uniquely identifies).

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

• Foreign Key: Attribute(s) in one relation referencing primary key of another. Enforces referential integrity.

Entity Sets

• Strong Entity: Has primary key (e.g., Student(Roll_no, Name)).

• Weak Entity: Lacks primary key; depends on strong entity (identifying relationship). Represented by double rectangle and double diamond. Partial key (discriminator) + owner’s key forms primary key.

Relationship Sets

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

• Cardinality:

  • 1:1: One entity associates with at most one of other.

  • 1:M: One entity associates with many of other.

  • M:N: Many-to-many.

• Participation:

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

  • Partial: Some entities may not participate (single line).

Extended ER Features

• Generalization: Bottom-up; multiple subclasses generalize to superclass (e.g., Car, Truck → Vehicle). "IS-A" relationship.

• Specialization: Top-down; superclass divided into subclasses (e.g., Employee → Manager, Engineer).

• Aggregation: Treating relationship as an entity (e.g., Project uses Employee via Works_On; Works_On can have attribute Hours). Represented by diamond within diamond.

Mapping ER Diagrams to Relational Schema

3. Relational Model and Query Languages

3.1 Relational Model Concepts

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

• Relation: Table (set of tuples) at a given time.

• Tuple: Row in a table.

• Attribute: Column.

Integrity Constraints:

• Domain Constraint: Attribute values must be from domain.

• Entity Integrity: Primary key cannot be null.

• Referential Integrity: Foreign key must match primary key in referenced table or be null.

Relational Algebra Operations (set-oriented, procedural):

• Select (σ): σ_{condition}(R) – rows satisfying condition.

• Project (Π): Π_{A₁,...,Aₖ}(R) – specific columns.

• Union (∪): R ∪ S – tuples in R or S (both must be union-compatible).

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

• Cartesian Product (×): R × S – concatenate all tuples.

• Rename (ρ): ρ_{S}(R) – rename relation/attributes.

• Joins:

  • Natural Join (⋈): R ⋈ S – equijoin on common attributes; duplicates eliminated.

  • Theta Join (⋈_{θ}): R ⋈_{A θ B} S – join on condition θ.

  • Equi Join: Theta join with equality.

  • Outer Joins:

    • Left Outer Join (⟕): All tuples from left, matched from right (nulls for unmatched).

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

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

3.2 SQL

Categories:

• DDL: CREATE, ALTER, DROP.

• DML: SELECT, INSERT, UPDATE, DELETE.

• DCL: GRANT, REVOKE.

• TCL: COMMIT, ROLLBACK, SAVEPOINT.

Advanced SQL:

• Subqueries: Nested SELECT (correlated vs. uncorrelated).

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

• Set Operations: UNION, INTERSECT, EXCEPT (all eliminate duplicates; use ALL to retain).

• Aggregation: GROUP BY, HAVING (filter groups).

• Functions:

  • Aggregate: SUM(), AVG(), COUNT(), MIN(), MAX().

  • String: CONCAT(), SUBSTRING(), UPPER().

  • Date/Time: NOW(), DATEDIFF(), EXTRACT().

Views:

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

• Advantages: Security (restrict access), simplify complex queries, logical data independence.

• Updatable Views: Simple views (single table, no aggregates, no DISTINCT) can be updatable; otherwise, use INSTEAD OF triggers.

Triggers:

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

• Syntax:

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

• Use Cases: Audit logging, enforce complex constraints, maintain summary tables.

Assertions and Constraints:

• Assertions: Global constraints (e.g., CHECK (count_employees < 1000)). Rarely used.

• Constraints: PRIMARY KEY, FOREIGN KEY, UNIQUE, CHECK, NOT NULL.

Hierarchical Queries (Oracle-specific):

• CONNECT BY PRIOR for tree-structured data (e.g., organizational chart).

• START WITH defines root(s).

Special Operators:

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

• IN: Membership test.

• EXISTS: Checks subquery result existence (correlated subqueries).

• ANY/ALL: Comparison with set (e.g., salary > ANY (subquery)).

4. Database Design and Normalization

4.1 Functional Dependencies (FDs)

• Definition: X → Y means Y is functionally determined by X (for any two tuples, if X values equal, then Y values equal).

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

• Non-Trivial FD: Y ⊈ X.

• Completely Non-Trivial: X ∩ Y = ∅.

Armstrong’s Axioms (sound and 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 Rules:

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

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

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

Attribute Closure (X⁺):

• Compute set of attributes functionally determined by X using FDs.

• Algorithm:

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

• Use: Test if X is a super key (if X⁺ contains all attributes), check FD implication.

Canonical Cover / Minimal Cover:

• Eliminate redundant FDs and extraneous attributes.

• Steps:

  1. Decompose RHS: X → ABC becomes X → A, X → B, X → C.

  2. Remove extraneous LHS attributes: For each FD X → A, check if (X − {attr}) → A is implied by F. Remove if yes.

  3. Remove redundant FDs: For each FD, check if it’s implied by others; remove if yes.

4.2 Normal Forms

Goal: Eliminate redundancy and anomalies (insertion, deletion, update).

4.3 Decomposition

• Lossless Join Decomposition: Decomposing R into R₁, R₂ ensures R = R₁ ⋈ R₂.

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

  Testing: Compute (R₁ ∩ R₂)⁺ w.r.t. FDs; check if it contains all attributes of R₁ or R₂.

• Dependency Preserving Decomposition: Union of projected FDs on each Ri should imply original FDs. Not always possible (e.g., BCNF decomposition may lose dependencies).

• Decomposition Algorithms:

  • To 2NF: For each partial dependency X → A (X proper subset of candidate key), decompose into (X ∪ A) and (original attributes − A).

  • To 3NF/BCNF: For each FD X → Y where X not super key, decompose into (X ∪ Y) and (R − Y). For BCNF, repeat until all FDs satisfy BCNF.

5. Transaction Management

Transaction Definition and Properties (ACID)

• Transaction: Logical unit of work (sequence of read/write operations) with ACID properties:

  • Atomicity: All or nothing. Either all operations commit or abort (rollback).

  • Consistency: Preserves database consistency (integrity constraints). Transaction maps consistent state to another.

  • Isolation: Concurrent transactions don’t interfere (equivalent to serial execution).

  • Durability: Once committed, effects persist despite failures (written to disk).

Transaction States

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

          │   Active    │

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

                │

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

          │ Partially   │

          │ Committed   │

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

                │

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

          │  Committed  │

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

                │

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

          │  Terminated │

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

• Active: Executing.

• Partially Committed: Final operation executed, before commit.

• Committed: Successfully completed.

• Failed: Aborted due to constraint violation or system failure.

• Aborted: Rolled back; may be restarted.

• Terminated: Either committed or aborted.

Schedules

• Serial Schedule: Transactions execute sequentially (no overlap). Always conflict-serializable.

• Non-Serial Schedule: Transactions overlap (concurrent). May cause inconsistencies.

• Conflict Serializability: Two schedules equivalent if order of conflicting operations (same transaction, same data item, at least one write) is same.

• View Serializability: Equivalent if:

  1. Same initial reads.

  2. Same final writes.

  3. Same read-from relationships.

Testing Serializability: Precedence Graph

• Nodes: Transactions.

• Edges: Tᵢ → Tⱼ if Tᵢ has a conflicting operation before Tⱼ on same data item.

• Schedule is conflict-serializable iff graph is acyclic.

• Serial order: Topological sort of graph.

Recoverable Schedules

• Recoverable: If Tⱼ reads data written by Tᵢ, then Tⱼ commits only after Tᵢ commits.

• Cascading Abort: Tⱼ aborts because Tᵢ (which wrote data read by Tⱼ) aborts.

• Strict Schedule: No transaction reads or writes data item until last transaction that wrote it has committed/aborted. Prevents cascading abort.

6. Concurrency Control

Need for Concurrency Control

• Prevent:

  • Lost Update: Two transactions overwrite each other’s updates.

  • Dirty Read: Read uncommitted data (may be rolled back).

  • Unrepeatable Read: Inconsistent reads within same transaction.

  • Phantom Read: New rows appear/disappear on repeated query.

Locking Techniques

• Shared (S) Lock: For reading; multiple transactions can hold S-lock simultaneously.

• Exclusive (X) Lock: For writing; only one transaction can hold X-lock; incompatible with all others.

• Lock Compatibility Matrix:

Two-Phase Locking (2PL)

• Growing Phase: Transaction acquires locks (no release).

• Shrinking Phase: Transaction releases locks (no new acquisitions).

• Guarantees: Conflict-serializable schedule.

• Variants:

  • Basic 2PL: Release locks after commit/abort.

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

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

Deadlock

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

• Prevention:

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

  • Preemption: Force transaction to release locks (risky).

  • Timeout: Abort if wait exceeds threshold.

• Avoidance:

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

  • Wound-Wait: Older transaction forces younger to abort (wounds); younger waits.

• Detection: Wait-For Graph (WFG) – nodes = transactions, edge Tᵢ → Tⱼ if Tᵢ waits for Tⱼ. Cycle = deadlock.

• Resolution: Choose victim (e.g., youngest, least progress) and abort/rollback.

Timestamp-Based Concurrency Control

• Each transaction gets unique timestamp TS(T) (increasing).

• Each data item Q has:

  • RTS(Q) = timestamp of last read.

  • WTS(Q) = timestamp of last write.

• Protocol:

  • T wants to read Q: if TS(T) < WTS(Q), abort T (older write); else allow, set RTS(Q) = max(RTS(Q), TS(T)).

  • T wants to write Q: if TS(T) < RTS(Q) or TS(T) < WTS(Q), abort T; else write, set WTS(Q) = TS(T).

• Guarantees: Conflict-serializable (order by timestamps). No deadlocks (no waiting).

Validation-Based (Optimistic) Concurrency Control

• Phases:

  1. Read Phase: Transaction reads/writes local copies (no locks).

  2. Validation Phase: Check if T conflicts with committed transactions during its execution.

  3. Write Phase: If validated, write updates; else abort.

• Validation Tests (serializable if):

  • TS(T) > finish_TS(all Tᵢ that wrote data read by T) (basic).

  • More efficient: TS(T) > start_TS(Tᵢ) for all Tᵢ that wrote data read by T.

• Use: Low conflict environments.

Multiple Granularity Locking

• Granularity Levels: Database → File → Page → Record → Field.

• Intention Locks: Indicate intention to acquire locks at finer levels.

  • IS (Intention Shared): Intention to set S-lock on some lower node.

  • IX (Intention Exclusive): Intention to set X-lock on some lower node.

  • SIX (Shared with Intention Exclusive): S-lock on node, IX on some children.

• Lock Compatibility (with intention locks):

• Protocol: To lock a node, must have compatible lock on all ancestors (e.g., to lock a record with X, must have IX on its page, IX on its file, etc.).

7. Database Recovery

Need for Recovery

System failures (power loss, disk crash, software errors) can leave database in inconsistent state. Recovery restores to consistent state.

Database Logs

• Write-Ahead Logging (WAL): Before modifying a page on disk, corresponding log record must be written to stable storage.

• Log Records:

  • <T, X, v> (update): Transaction T changed X from v to new value.

  • <T, X, old, new> (compensating).

  • <T, start>, <T, commit>, <T, abort>.

• Log Sequence Number (LSN): Monotonically increasing; each log record points to previous LSN of same transaction.

Recovery Techniques

• Deferred Database Modification:

  • Transaction writes updates to private workspace (not to disk).

  • On commit, writes all updates to disk at once (no immediate writes).

  • Recovery: For committed T after last checkpoint, redo all its writes. No undo needed (uncommitted changes never on disk).

• Immediate Database Modification:

  • Transaction writes updates to disk immediately (using WAL).

  • Recovery: Both redo (reapply committed writes) and undo (rollback uncommitted writes using compensating log records).

Checkpoints

• Purpose: Reduce recovery time; avoid scanning entire log.

• Implementation:

  • Flush all dirty buffers to disk.

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

• Recovery from Checkpoint:

  • Find last checkpoint.

  • Analysis: Determine set S of transactions that committed after checkpoint (need redo) and set U of uncommitted (need undo).

  • Redo: Reapply all writes of transactions in S (idempotent).

  • Undo: Rollback all transactions in U (backward using log).

Recovery Process (Immediate Modification)

1. Analysis: Scan log forward from last checkpoint; build transaction table (status, lastLSN) and dirty page table (recLSN). Identify Winner (committed) and Loser (uncommitted) transactions.

2. Redo: Scan log forward from smallest recLSN in dirty page table; reapply all update log records (idempotent check: if pageLSN ≥ logLSN, skip).

3. Undo: Scan log backward; for each Loser transaction, generate CLR (Compensating Log Record) and undo changes (write CLR to log). Repeat until all losers undone.

Shadow Paging

• Concept: Maintain two copies of database: shadow (consistent) and current (being modified).

• Pages: Allocator assigns page numbers; shadow pages never modified.

• Transaction T:

  • Copy all pages T will modify → new pages (current).

  • Update new pages.

  • On commit: atomically switch page table pointer from shadow to current (single write).

  • On abort: discard current pages; shadow unchanged.

• Advantages: No undo/redo logs; recovery simple (just use shadow).

• Disadvantages: Copying overhead; poor space utilization; not suitable for large transactions.

8. Query Processing and Optimization

Query Processing Steps

1. Parsing: Syntax/semantic check; generate parse tree.

2. Translation: Convert parse tree to initial query plan (relational algebra expression).

3. Optimization: Transform plan to efficient equivalent (heuristic/cost-based).

4. Execution: Generate code (interpretive or compiled) and execute.

Query Optimization

• Necessity: Poor queries can be orders of magnitude slower (e.g., Cartesian product vs. indexed join).

• Goals: Minimize total cost (I/O, CPU, communication).

• Heuristic Optimization: Apply transformation rules to improve plan without cost estimation.

  • Selection Pushdown: Apply σ as early as possible (reduce intermediate size).

  • Projection Pushdown: Apply Π as early as possible (reduce width).

  • Join Ordering: Perform most restrictive joins first (smallest intermediate).

• Cost-Based Optimization:

  • Estimate cost of each plan using statistics (relation size, attribute distinctness, indexes).

  • Use dynamic programming or exhaustive search for join order.

  • Cost Metrics:

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

    • CPU Cost: Tuple processing (comparisons, projections).

    • Network Cost: For distributed queries.

Expression Evaluation Plans

• Trees: Relational algebra operators as nodes; leaves are base relations.

• Join Algorithms:

  • Nested-Loop Join:

    
    for each tuple t in R:
    
      for each tuple s in S:
    
        if t joins s then output
    
    

    Cost: b_R + n_R * b_S (block transfers). Use index on S if available.

  • Hash Join:

    • Partition R and S on hash of join attribute into B-1 buckets (B = buffer pages).

    • Read each bucket pair into memory, build hash table on smaller, probe with larger.

    • Cost: 3(b_R + b_S) (read/write partitions). Requires b_R + b_S ≤ B² for 1-pass.

  • Sort-Merge Join:

    • Sort R and S on join attribute.

    • Merge sorted lists (like merge sort).

    • Cost: 2 b_R log_{f}(b_R) + 2 b_S log_{f}(b_S) + b_R + b_S (f = fan-in). Efficient if already sorted.

Implementation of Operations

• Select (σ):

  • If index on condition attribute → index scan (cost: log_b N for B+ tree).

  • Else → full table scan.

• Project (Π): Eliminate duplicates via sorting or hashing.

• Join: Choose algorithm based on sizes, indexes, available memory.

9. Storage, Indexing, and File Organization

9.1 File Organization

9.2 Indexing

• Dense Index: Index entry for every search-key value (in data file).

• Sparse Index: Index entry for some values (e.g., first value in block).

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

• Secondary Index: On non-key attribute; dense (may have duplicates).

• Clustering Index: Data file sorted on index key; one per table.

• Non-Clustering Index: Data file not sorted; multiple possible.

B+ Tree Index (most common):

• Structure:

  • All leaves at same level; linked for range queries.

  • Internal nodes: (P₁, K₁, P₂, K₂, ..., Pₘ) where Pᵢ are pointers, Kᵢ keys.

  • Order n: Max n pointers per node; min ⌈n/2⌉ (except root).

• Search: Start at root, traverse to leaf.

• Insert:

  1. Find leaf.

  2. Insert key; if overflow, split leaf and propagate up (may increase height).

• Delete:

  1. Find leaf, remove key.

  2. If underflow, borrow from sibling or merge (may decrease height).

• Advantages: Balanced, efficient for range queries, minimal I/O.

Bitmap Index:

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

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

• Operations: Fast AND/OR via bitwise operations.

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

9.3 Hashing

• Static Hashing:

  • Fixed number of buckets B.

  • Hash function h(key) → [0, B-1].

  • Overflow Handling:

    • Chaining: Overflow buckets linked list.

    • Open Addressing: Probe for next bucket (linear, quadratic).

• Dynamic Hashing:

  • Extendable Hashing:

    • Directory of pointers to buckets; directory size 2^d (d = global depth).

    • Each bucket has local depth l.

    • Split bucket when overflow; if l < d, split directory; else increase d and split all pointers.

  • Linear Hashing:

    • Progressive splitting; no directory.

    • Bucket i splits when overflow, using h_new(key).

    • Round-robin splitting; maintain split pointer N.

• Hash Functions: Uniform distribution, fast computation (e.g., modulo, multiplicative).

9.4 RAID (Redundant Array of Independent Disks)

10. Advanced Database Topics

10.1 Distributed Databases

• Concepts:

  • Fragmentation:

    • Horizontal: Rows split (by range/hash).

    • Vertical: Columns split (must include primary key).

    • Hybrid: Both.

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

  • Transparency:

    • Location Transparency: Users unaware of data location.

    • Fragmentation Transparency: Users query global schema.

    • Replication Transparency: Users unaware of copies.

• Distributed Query Processing:

  • Query Decomposition: Break global query into subqueries for sites.

  • Data Localization: Transfer subqueries to data sites.

  • Result Merging: Combine results.

• Distributed Transaction Management:

  • Two-Phase Commit (2PC):

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

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

    • Blocks during prepare; vulnerable to coordinator failure (need recovery protocol).

• Concurrency & Recovery:

  • Concurrency: Distributed locking (2PL with lock manager at each site; deadlock detection global).

  • Recovery: Each site has local log; global commit protocol ensures atomicity.

• Challenges:

  • Heterogeneity: Different DBMS, OS, networks.

  • Autonomy: Sites may control own data.

  • Network Failures: Partitioning.

  • Distributed Deadlocks: More complex detection.

10.2 Object-Oriented and NoSQL Databases

• OODBMS vs RDBMS:

  | Feature | RDBMS | OODBMS | |-------------------|------------------------------------|-------------------------------------| | Data Model | Tables, rows, columns. | Objects, classes, inheritance. | | Complex Data | Normalized; joins for relationships. | Direct object storage; OIDs. | | Schema | Fixed schema; rigid. | Flexible schema (open). | | Query Language| SQL (declarative). | OQL (object-oriented) or programmatic. | | Use Cases | Structured data, transactions. | CAD, multimedia, complex hierarchies. | | Performance | Good for set operations. | Good for traversing object graphs. |

• NoSQL Databases:

  • Types:

    • Document: JSON/BSON documents (e.g., MongoDB).

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

    • Column-Family: Column-oriented (e.g., Cassandra).

    • Graph: Nodes/edges (e.g., Neo4j).

  • Characteristics:

    • Schema-less or flexible schema.

    • Horizontal scaling (sharding).

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

    • CAP Theorem: In distributed systems, can only guarantee two of:

      • Consistency (all nodes see same data).

      • Availability (every request succeeds).

      • Partition Tolerance (system works despite network partitions).

  • Advantages over RDBMS:

    • Scalability for big data.

    • Flexible schema for evolving data.

    • High write throughput.

    • Suitable for unstructured/semi-structured data.

10.3 Other Topics

• Data Warehousing & OLAP:

  • Data Warehouse: Integrated, subject-oriented, time-variant, non-volatile collection for decision support.

  • ETL: Extract, Transform, Load.

  • OLAP: Multidimensional analysis (cubes, roll-up, drill-down).

  • Star Schema: Fact table (measures) + dimension tables.

• Web & Mobile Databases:

  • Challenges: Limited resources, intermittent connectivity, security.

  • Solutions: Replication, caching, sync protocols, lightweight DBs (SQLite).

• XML & Databases:

  • XML Databases: Native (e.g., eXist-db) or relational with XML extensions.

  • XQuery: Query language for XML.

  • Mapping: XML ↔ relational (SQL/XML, XQuery).

• Big Data & Database Systems:

  • Hadoop Ecosystem: HDFS (storage), MapReduce (processing), HBase (NoSQL).

  • Spark: In-memory processing.

  • NewSQL: Combines SQL and NoSQL scalability (e.g., Google Spanner).

• Database Security & Authorization:

  • Authentication: Passwords, biometrics.

  • Authorization: GRANT, REVOKE (privileges: SELECT, INSERT, etc.).

  • Views: Restrict access.

  • Encryption: Data at rest/in transit.

  • Auditing: Track access.

• Oracle Application Express (APEX):

  • Low-code web development platform for Oracle DB.

  • Browser-based; generates SQL/PLSQL.

  • Rapid application development for database-centric apps.

11. Miscellaneous and Short Note Topics

Database Anomalies

• Insertion Anomaly: Cannot insert data without other data (e.g., can’t add a course without a student).

• Deletion Anomaly: Deleting data inadvertently loses other data (e.g., delete last student in course → course info lost).

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

Views

• Virtual View: Not stored; computed on query (CREATE VIEW ... AS SELECT).

• Materialized View: Stored physically; refreshed periodically/on-demand. Faster query, but stale data, storage overhead.

• Updatable Views: Simple views (single table, no aggregates, distinct) allow INSERT/UPDATE/DELETE; else need INSTEAD OF triggers.

Triggers vs Constraints

Data Dictionary and System Catalog

• Data Dictionary: Metadata about database objects (tables, columns, indexes, constraints). Stored in system tables (e.g., INFORMATION_SCHEMA in SQL).

• System Catalog: DBMS-specific metadata (e.g., Oracle’s DBA_TABLES, USER_TAB_COLUMNS).

• Uses: Query optimization, authorization, user queries.

Dynamic Performance Views (Oracle)

• V$ Views: Real-time performance statistics (e.g., V$SESSION, V$SQL, V$SYSTEM_EVENT).

• GV$ Views: Global (RAC) versions.

• Use: Monitoring, tuning, troubleshooting.

Complex Queries

• Nth Maximum:

  
  SELECT DISTINCT salary FROM employee E1 
  
  WHERE N-1 = (SELECT COUNT(DISTINCT salary) FROM employee E2 WHERE E2.salary > E1.salary);
  
  

• Correlated Subquery: Subquery referencing outer query (executed per outer row).

  Example: Find employees with salary above department average.

Integrity Constraints Implementation

• Domain: CHECK or domain types.

• Entity: PRIMARY KEY (unique, not null).

• Referential: FOREIGN KEY with ON DELETE/UPDATE CASCADE/SET NULL.

• User-defined: CHECK with subqueries or functions.

Expression Trees for Relational Algebra

• Nodes: Operators (σ, Π, ⋈, ∪, −).

• Leaves: Relations or constants.

• Example: Π_{name}(σ_{dept='CS'}(Employee)) →

  
        Π
  
        |
  
        σ
  
        |
  
     Employee
  
  

• Cost Estimation: Estimate cardinality at each node using statistics (selectivity, distinct values).

Comparison of Data Models

Exam Tips:

• Transaction Management: Always draw state diagram for ACID questions. Use precedence graph for serializability.

• Normalization: Show step-by-step decomposition with FDs and keys.

• Concurrency: Compare locking vs. timestamp protocols; draw wait-for graph for deadlock detection.

• Recovery: Memorize analysis-redo-undo phases; know WAL rule.

• SQL: Practice correlated subqueries, hierarchical queries (CONNECT BY), and set operations.

• Indexing: Compare B+ tree vs. hash; know dense vs. sparse.

• ER Modeling: Map all constructs (weak entity, aggregation) to relational schema correctly.

• Common Pitfalls:

• Confusing 3NF and BCNF (BCNF requires determinant to be super key).

• Forgetting that outer joins can produce NULLs.

• Misunderstanding lossless join condition (common attributes must be super key in at least one decomposed relation).

• Assuming 2PL prevents deadlocks (it doesn’t; rigorous 2PL can deadlock).

• Overlooking that materialized views need refresh mechanisms.

\boxed{\text{End of Unit 5 Notes}}