GATE DA — Section 5

DBMS & Data Warehousing

Comprehensive reference guide covering the relational model, SQL queries, database normalization, storage indexing, and multidimensional data warehousing for GATE Data Science & AI.

Official GATE DA Syllabus: ER-model; relational model: relational algebra, tuple calculus; SQL, integrity constraints; normal forms; file organization, indexing; data types and transformation (normalization, discretization, sampling, compression); data warehouse modelling: schema for multidimensional models, concept hierarchies, measures: categorization and computations.

1. The Entity-Relationship (ER) Model

The ER model abstracts real-world semantics into entities, attributes, and relationships:

  • Entities: Strong entities possess an independent primary key. Weak entities depend on an identifying owner entity via an identifying relationship and use a partial key (discriminator).
  • Cardinality Ratios:
    • 1:1: Can be merged into a single table if both entities participate totally.
    • 1:N: Foreign key is placed on the N-side entity table referencing the primary key of the 1-side.
    • M:N: Requires a distinct relationship table whose primary key consists of the composite foreign keys of both participating entities.

2. Relational Algebra & Tuple Relational Calculus (TRC)

Relational algebra is a procedural query language operating on relations:

  • Fundamental Operators: Selection (σ_{cond}(R)), Projection (π_{cols}(R)), Cartesian Product (R × S), Set Union (R ∪ S), and Set Difference (R - S).
  • Derived Operators:
    • Natural Join (R ⋈ S): Equi-join on all common attribute names with duplicate attribute columns projected out.
    • Division (R ÷ S): Identifies tuples in R that are associated with all tuples in S (evaluates "for all" universal quantification).

3. SQL & Integrity Constraints

  • Entity Integrity: Primary keys cannot contain NULL values.
  • Referential Integrity: A foreign key value in a referencing relation must either match an existing primary key in the referenced relation or be NULL (unless declared NOT NULL). Trigger actions include ON DELETE CASCADE, ON DELETE SET NULL, and ON DELETE RESTRICT.
  • Aggregation & Subqueries: WHERE filters individual tuples prior to aggregation; HAVING filters group rows produced by GROUP BY. Correlated subqueries execute once for each outer query row.

4. Functional Dependencies & Normal Forms

Normalization eliminates insertion, update, and deletion anomalies by decomposing relations into lossless, dependency-preserving sub-relations:

Normal Form Core Requirement Eliminates
1NF All attribute values must be atomic (no repeating groups or multi-valued attributes). Nested sets/arrays
2NF In 1NF and no partial dependency: no non-prime attribute depends on a proper subset of any candidate key. Partial key redundancies
3NF In 2NF and no transitive dependency: for every non-trivial FD X → Y, either X is a superkey OR Y is a prime attribute. Transitive non-key dependencies
BCNF For every non-trivial FD X → Y, X must be a superkey. All functional redundancy

Decomposition Guarantees: Any relation can always be decomposed into 3NF with both Lossless Join and Dependency Preservation. Decompositions into BCNF are always guaranteed to be lossless, but may not always preserve all functional dependencies.

5. Storage, File Organization & Indexing

  • Primary vs. Clustered vs. Secondary:
    • Primary Index: Built on a key attribute where data file is sorted. Always sparse.
    • Clustering Index: Built on a non-key attribute where data file is sorted. One entry per distinct value.
    • Secondary Index: Built on unsorted data file. Must be dense (pointers for every record or distinct key).
  • B+ Trees: Balanced search trees where all data records/pointers reside exclusively at the leaf level. Leaves are sequentially linked with pointers, enabling extremely fast range scans (e.g., WHERE age BETWEEN 20 AND 30) with logarithmic O(\log_B N) tree depth.

6. Data Transformation & Warehousing

  • Data Transformation:
    • Min-Max Normalization: v' = \frac{v - \min}{\max - \min}(new\_max - new\_min) + new\_min.
    • Z-Score Normalization: v' = \frac{v - \mu}{\sigma}.
    • Discretization: Equal-width vs. equal-frequency binning.
  • Multidimensional Schema Models:
    • Star Schema: Central fact table surrounded by denormalized, single-table dimension entities. Maximizes query performance and simplifies joins.
    • Snowflake Schema: Dimension tables are normalized into hierarchies. Saves storage space but requires multi-table joins.
    • Fact Constellation (Galaxy Schema): Multiple fact tables share dimension tables across an enterprise.
  • OLAP Operations: Roll-up (aggregation/climbing hierarchy), Drill-down (stepping into granular details), Slice (filtering on one dimension), Dice (sub-cube on two or more dimensions), Pivot (reorienting view axes).

7. Worked Step-by-Step Examples

Worked Example 1: Finding Candidate Keys & Normal Form

Problem: Given relation R(A, B, C, D, E) with functional dependencies: F = { A → BC, CD → E, B → D, E → A }. Find the candidate keys and highest normal form.

Solution:

1. Compute attribute closure of A: A^+ = {A, B, C, D, E} → A is a candidate key.

2. Since E → A, E^+ = {E, A, B, C, D} → E is a candidate key.

3. Check CD: CD → E → A → BC → CD is a candidate key.

4. Check BC: B → D ⇒ BC → BCD → E → A → BC is a candidate key.

Prime attributes: {A, B, C, D, E} (all attributes are prime!).

Since every attribute is prime, the condition for 3NF ("either X is superkey OR Y is prime") holds trivially for all dependencies. However, in B → D, B is not a superkey, violating BCNF.

Conclusion: R is in 3NF, but not in BCNF.

8. GATE Exam Traps & Common Distractors

  • Lossless Join Test for Binary Decomposition: A decomposition of R into (R1, R2) is lossless if and only if R1 ∩ R2 → R1 OR R1 ∩ R2 → R2 in F^+.
  • COUNT(*) vs COUNT(attribute): COUNT(*) counts all rows including NULLs, while COUNT(col) ignores rows where col IS NULL.
  • Additive vs Non-Additive Measures: Sales revenue is fully additive across all dimensions. Inventory quantity is semi-additive (additive across stores, but not across time). Average unit price is non-additive.

9. Practice & Topic Tracking

Test your knowledge with exam-pattern DBMS questions:

Practice DBMS Questions or review the GATE DA Syllabus Index.