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.
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 theN-side entity table referencing the primary key of the1-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 inRthat are associated with all tuples inS(evaluates "for all" universal quantification).
- Natural Join (
3. SQL & Integrity Constraints
- Entity Integrity: Primary keys cannot contain
NULLvalues. - 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 declaredNOT NULL). Trigger actions includeON DELETE CASCADE,ON DELETE SET NULL, andON DELETE RESTRICT. - Aggregation & Subqueries:
WHEREfilters individual tuples prior to aggregation;HAVINGfilters group rows produced byGROUP 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 logarithmicO(\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.
- Min-Max Normalization:
- 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
Rinto(R1, R2)is lossless if and only ifR1 ∩ R2 → R1ORR1 ∩ R2 → R2inF^+. - COUNT(*) vs COUNT(attribute):
COUNT(*)counts all rows includingNULLs, whileCOUNT(col)ignores rows wherecol 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.