Database Management and Warehousing

Section 5 of the GATE Data Science and Artificial Intelligence (DA) paper: how data is modelled, queried, stored efficiently, reshaped for analysis, and finally organised at the scale a warehouse needs. The section runs as a pipeline — an ER model turned into relations, relations queried through algebra, calculus and SQL under integrity constraints and normal forms, files organised and indexed for fast retrieval, values transformed for downstream analysis, and finally reorganised into a warehouse schema built for the very different question a warehouse answers: not 'what is this record', but 'what does this measure look like, sliced along every dimension at once'.

1. The ER model, and mapping it to the relational model

The Entity-Relationship (ER) model describes a database at the design stage in terms three things: entities (a 'Student' or a 'Course', each a thing worth recording), attributes (a Student's name or roll number), and relationships connecting entity sets (a Student 'enrols in' a Course). Mapping this to the relational model gives one table per strong entity set, with its attributes as columns and a key as the primary key; a weak entity set additionally carries the key of the strong entity it depends on.

How a relationship set maps depends on its cardinality. A one-to-many relationship can be folded into the 'many' side as a foreign key with no separate table needed. A many-to-many relationship, however, cannot be represented that way without losing information — it needs its own table, carrying a foreign key to each participating entity set (plus any attributes of the relationship itself), because a single foreign-key column on either entity could only ever record one partner at a time.

⚠️ Do not fold a many-to-many relationship into either entity's table
Adding a single 'course_id' column to the Student table to record enrolment looks tidy but is wrong the moment a student enrols in a second course — the column has nowhere to put the second value. This is exactly the redundancy and update anomaly that a separate junction (enrolment) table exists to prevent, and it is one of the concrete failures normal forms are built to rule out.

2. Relational algebra, tuple calculus and SQL

Relational algebra is procedural: a query is an explicit sequence of operators — σ (select rows by a condition), π (project columns), ⋈ (join two relations on a condition), ∪/∩/− (set union, intersection, difference), and ρ (rename) — applied in a stated order. Tuple relational calculus is declarative: a query states what the answer must satisfy ('the set of tuples t such that...') without saying how to compute it. SQL is the language actually used, and it is declarative in the same sense as tuple calculus — a SELECT statement describes the desired result, and the database engine decides how to execute it, typically by compiling the query down into something equivalent to a relational-algebra expression.

  • Every tuple-calculus expression has an equivalent relational-algebra expression and vice versa — the two are formally equivalent in expressive power, which is exactly why a declarative SQL query can always be compiled down to a procedural algebra plan.
  • A join (⋈) is not a primitive operator in the strictest sense — it can always be written as a selection over a Cartesian product, but it is given its own symbol because that combination is by far the most common query shape.
ℹ️ Integrity constraints are declared once, in the schema, not in every query
A primary-key constraint (uniqueness plus not-null) and a foreign-key constraint (every referenced value must actually exist in the referenced table) are enforced by the database engine on every insert and update, not something a query has to re-check each time — the point of declaring them in the schema is that the guarantee holds regardless of which query, or which application, is writing to the table.

3. Normal forms

A relation in First Normal Form (1NF) has only atomic (indivisible) attribute values — no repeating groups or lists inside a single cell. Second Normal Form (2NF) additionally removes partial dependency: every non-key attribute must depend on the whole of a composite primary key, not just part of it. Third Normal Form (3NF) additionally removes transitive dependency: a non-key attribute may not depend on another non-key attribute. Boyce-Codd Normal Form (BCNF) is stricter still — every determinant (the left side of a functional dependency) must be a candidate key, with no exceptions carved out for the case 3NF still allows.

⚠️ Decomposing to BCNF can lose dependency preservation
Every relation can be decomposed losslessly into BCNF, but that decomposition is not guaranteed to preserve every original functional dependency — a dependency can end up spanning two different tables after the split, so checking it again requires an expensive join that was never needed before decomposition. 3NF is deliberately less strict than BCNF precisely so it can always be achieved while preserving both the lossless-join property and every functional dependency at once — a trade-off worth naming exactly because it looks like BCNF is simply 'more normalised' with no downside.

4. File organization, indexing and data types

A heap (pile) file simply appends new records with no order at all, so insertion is cheap but finding a record by key means scanning the whole file, O(n). A sorted sequential file supports binary search on the key, O(log n), but insertion means shifting records to keep the order, which is expensive. A hashed file maps a key directly to a storage location via a hash function, giving near-O(1) lookup by that key at the cost of losing any usable order for range queries.

An index is a separate, auxiliary structure that speeds up lookup on a column without reorganising the data file itself. A primary index is built on the field the file is physically sorted by (at most one per file); a secondary index can be built on any other field, and typically needs one entry per record rather than one per block. A B+ tree index — the standard choice in practice — keeps all actual data pointers at the leaf level with internal nodes holding only routing keys, so a lookup, an ordered range scan and an insertion are all O(log n) even as the tree grows.

5. Data transformation: normalization, discretization, sampling, compression

⚠️ This 'normalization' is not the normal-forms 'normalization' three sections ago
The syllabus reuses one English word for two unrelated ideas. Schema normalization (Section 3) restructures tables to remove redundancy by applying normal forms. Data normalization, here, rescales a numeric attribute's values onto a common range or distribution — min-max scaling maps values onto, say, [0, 1], and z-score standardization rescales to zero mean and unit variance — so that no attribute dominates a downstream analysis (e.g. a distance-based method) purely because of the units it happens to be measured in. One removes redundancy in a schema; the other removes an accidental scale advantage in the data itself, and neither operation touches what the other one does.

Discretization replaces a continuous attribute's values with a small number of labelled ranges or bins (e.g. age becomes 'young', 'middle-aged', 'senior'), useful for algorithms that expect categorical input or for making a pattern easier to read. Sampling selects a representative subset of the data to work with when the full dataset is too large to process directly — the accuracy of any conclusion then depends on how representative the sample actually is. Compression re-encodes data into a smaller representation, either losslessly (the original can be exactly reconstructed) or lossily (some detail is discarded permanently in exchange for a smaller size).

6. Data warehouse modelling

A data warehouse is modelled for analytical queries across many dimensions rather than for the transactional inserts and updates a normalized operational database is built for. A star schema puts numeric measures (e.g. quantity sold, revenue) in a single central fact table, surrounded by denormalized dimension tables (product, store, time, customer) that each describe one axis along which the measure can be sliced; a snowflake schema further normalizes those dimension tables into sub-tables, trading some query simplicity for reduced redundancy.

A concept hierarchy orders a dimension's values from finer to coarser granularity — day → month → quarter → year for time, or city → state → country for geography — and it is exactly what lets an OLAP query roll up (aggregate to a coarser level) or drill down (break out to a finer one) along that dimension. Measures themselves are categorised by how they behave under aggregation: additive measures (like sales revenue) can be summed across every dimension; semi-additive measures (like an account balance) can be summed across some dimensions but not time, since a month's balance is not the sum of its daily balances; and non-additive measures (like a ratio, e.g. a profit margin) cannot be meaningfully summed across any dimension at all and must be recomputed from summed components instead.

🎯 Why the fact table is deliberately denormalized
An operational database is normalized to keep every update fast and every fact stored exactly once, because it is written to constantly. A warehouse is written to in scheduled batches and read constantly by analytical queries that would otherwise need to join a dozen normalized tables just to answer 'total revenue by region last quarter' — so it deliberately trades some redundancy and update cost for query speed, which is the opposite priority for the opposite workload.

Key takeaways

  • A many-to-many relationship needs its own table carrying a foreign key to each participating entity; folding it into either entity's table loses information the moment one side participates more than once.
  • Relational algebra (procedural), tuple calculus (declarative) and SQL (declarative, compiled to an algebra plan) are formally equivalent notations for the same query language.
  • Higher normal forms remove more redundancy; BCNF is stricter than 3NF, and decomposing all the way to BCNF can fail to preserve every original functional dependency, which 3NF is deliberately designed to always preserve.
  • A B+ tree index turns a linear file scan into an O(log n) lookup, ordered range scan and insertion all at once, which is why it is the standard indexing structure in practice.
  • Data-preprocessing 'normalization' (min-max/z-score scaling of numeric values) and schema 'normalization' (removing redundancy via normal forms) are unrelated operations that this section's own syllabus line happens to share one word for.
  • A warehouse's star schema keeps measures in a central, deliberately denormalized fact table surrounded by dimension tables, and a concept hierarchy on a dimension is what lets an OLAP query roll up or drill down along it.

Practice questions (14)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. A many-to-many relationship set between two entity sets maps, in the relational model, to a table that carries

    1. only the primary key of one of the two entities
    2. a foreign key to only one of the two participating entities
    3. foreign keys to both participating entities, plus any attributes of the relationship itself
    4. no foreign keys at all
    Show answer

    Answer: C — foreign keys to both participating entities, plus any attributes of the relationship itself

    A single foreign key on either entity's own table could only ever record one partner at a time, so the many-to-many relationship needs its own table referencing both sides.

  2. Which pair correctly matches a relational-algebra operator to what it does?

    1. σ selects rows satisfying a condition
    2. π joins two relations on a condition
    3. ⋈ renames a relation or its attributes
    4. ρ removes duplicate rows from the result
    Show answer

    Answer: A — σ selects rows satisfying a condition

    σ (select) filters rows by a condition; π projects columns; ⋈ joins; ρ renames — the other three options each name the wrong operator for the job described.

  3. Which of the following are true of relational algebra, tuple calculus and SQL?

    1. Tuple relational calculus is declarative — it states what to retrieve, not how to compute it
    2. Relational algebra is procedural — an ordered sequence of operators applied step by step
    3. SQL is purely procedural and can never be described as declarative
    4. Every relational-algebra expression has an equivalent tuple-calculus expression
    Show answer

    Answer: A — Tuple relational calculus is declarative — it states what to retrieve, not how to compute it; B — Relational algebra is procedural — an ordered sequence of operators applied step by step; D — Every relational-algebra expression has an equivalent tuple-calculus expression

    SQL's SELECT statements describe the desired result rather than the steps to compute it, which makes SQL declarative like tuple calculus, not procedural — the third option is the false one here.

  4. A relation that is in Second Normal Form (2NF) but not Third Normal Form (3NF) contains

    1. a partial dependency of a non-key attribute on part of a composite key
    2. a transitive dependency of one non-key attribute on another non-key attribute
    3. a repeating group inside a single cell
    4. no candidate key at all
    Show answer

    Answer: B — a transitive dependency of one non-key attribute on another non-key attribute

    2NF already rules out partial dependency (option 1) and 1NF already rules out repeating groups (option 3); what 3NF additionally removes over 2NF is exactly transitive dependency.

  5. Decomposing a relation all the way to Boyce-Codd Normal Form (BCNF) can fail to preserve

    1. atomicity of attribute values
    2. the lossless-join property
    3. every original functional dependency
    4. referential integrity between the decomposed tables
    Show answer

    Answer: C — every original functional dependency

    BCNF decomposition is always achievable losslessly, but it is not guaranteed to be dependency-preserving; a dependency can end up spanning two tables after the split, which is exactly the trade-off 3NF is designed to avoid.

  6. In a B+ tree index of order (maximum fan-out) 4, what is the maximum number of child pointers an internal node can have?

    Numerical answer — type the value.

    Show answer

    Answer: 4

    The order of a B+ tree is defined as the maximum number of children an internal node may have, so order 4 means at most 4 child pointers per internal node.

  7. Assuming a good hash function and a low collision rate, which file organization gives the fastest access to a record given its key?

    1. Heap (pile) file
    2. Unsorted sequential file
    3. Hashed file
    4. Sorted sequential file with no index
    Show answer

    Answer: C — Hashed file

    A hashed file maps the key directly to a storage location, giving near-O(1) access; the other three organizations need either a full scan or a logarithmic search at best.

  8. Min-max scaling and z-score standardization are both examples of, in the data-transformation sense this section uses,

    1. schema normalization to Third Normal Form
    2. data normalization, rescaling values onto a common range or distribution
    3. discretization of a continuous attribute
    4. concept-hierarchy construction for a data warehouse
    Show answer

    Answer: B — data normalization, rescaling values onto a common range or distribution

    Both rescale a numeric attribute's values (onto [0,1], or to zero mean and unit variance) rather than restructuring a schema — this is data normalization in the preprocessing sense, distinct from schema normalization via normal forms.

  9. Replacing a continuous attribute's values with a small number of labelled ranges, such as 'low', 'medium' and 'high', is called

    1. discretization
    2. sampling
    3. compression
    4. normalization
    Show answer

    Answer: A — discretization

    Discretization is exactly the operation of binning a continuous attribute's range into a small number of labelled categories.

  10. In a star schema for a retail sales data warehouse, numeric measures such as quantity sold and revenue are stored in the

    1. dimension tables
    2. fact table
    3. staging table
    4. concept hierarchy
    Show answer

    Answer: B — fact table

    The fact table is the central table holding the numeric measures, surrounded by dimension tables that describe the axes (time, product, store) along which those measures can be sliced.

  11. A concept hierarchy such as day → month → quarter → year primarily lets an OLAP query

    1. normalize the schema to BCNF
    2. roll up or drill down between finer and coarser granularity along that dimension
    3. discretize a continuous attribute for the very first time
    4. enforce a foreign-key constraint between fact and dimension tables
    Show answer

    Answer: B — roll up or drill down between finer and coarser granularity along that dimension

    A concept hierarchy orders a dimension's values from fine to coarse, and it is exactly that ordering an OLAP query walks up (roll up) or down (drill down) to aggregate or break out data.

  12. Which normal form requires every determinant (the left side of a functional dependency) to be a candidate key, with no exception carved out?

    1. First Normal Form (1NF)
    2. Second Normal Form (2NF)
    3. Third Normal Form (3NF)
    4. Boyce-Codd Normal Form (BCNF)
    Show answer

    Answer: D — Boyce-Codd Normal Form (BCNF)

    BCNF is stricter than 3NF precisely because it drops the exception 3NF allows (a determinant that is part of some candidate key but not one itself), requiring every determinant to be a candidate key outright.

  13. Which of the following are goals a good decomposition of a relation is expected to preserve?

    1. The lossless-join property
    2. Every original functional dependency
    3. Maximum possible redundancy across the resulting tables
    4. Atomicity of every attribute value
    Show answer

    Answer: A — The lossless-join property; B — Every original functional dependency; D — Atomicity of every attribute value

    Decomposition aims to reduce redundancy, not maximise it — the third option describes the opposite of what normalization is for, while the other three are genuine goals a good decomposition preserves.

  14. When an insertion causes a B+ tree node to overflow beyond its capacity, the standard response is to

    1. discard the tree entirely and rebuild it from scratch
    2. split the node in two and push (or copy) a separating key up into the parent
    3. silently drop the new key instead of inserting it
    4. convert the entire index into a hashed file organization
    Show answer

    Answer: B — split the node in two and push (or copy) a separating key up into the parent

    An overflowing B+ tree node splits into two nodes, with a key pushed up to the parent to route between them — repeated up the tree if the parent itself then overflows, which is what keeps the tree balanced and lookups at O(log n).