GATE DA & AI Engineering Database Management and Warehousing Syllabus

What distinguishes a correlated subquery from a non-correlated (nested) subquery?

A non-correlated subquery is evaluated once independently of the outer query. A correlated subquery references columns from the outer query and is re-evaluated for each outer row.

What are the four categories of integrity constraints in the relational model?

Domain constraints (valid attribute values), entity integrity (primary key not NULL), referential integrity (foreign key matches a referenced key or is NULL), and key constraints (uniqueness of candidate keys).

State the entity integrity constraint.

No attribute of a primary key may have a NULL value. This ensures every tuple in a relation can be uniquely identified.

State the referential integrity constraint.

A foreign key value in a referencing relation must either match an existing primary/candidate key value in the referenced relation or be entirely NULL. It prevents 'dangling' references.

Define a superkey, a candidate key, and a primary key.

A superkey is any set of attributes that uniquely identifies a tuple. A candidate key is a minimal superkey (no proper subset is a superkey). A primary key is the candidate key chosen to identify tuples.

Define functional dependency $X \to Y$.

In a relation, $X \to Y$ holds if every two tuples that agree on the attribute set $X$ also agree on $Y$. $X$ functionally determines $Y$; the value of $X$ uniquely determines the value of $Y$.

State Armstrong's three primary axioms (inference rules) for functional dependencies.

Reflexivity: if $Y \subseteq X$ then $X \to Y$. Augmentation: if $X \to Y$ then $XZ \to YZ$. Transitivity: if $X \to Y$ and $Y \to Z$ then $X \to Z$.

What is the attribute closure $X^{+}$ under a set of functional dependencies $F$?

$X^{+}$ is the set of all attributes functionally determined by $X$ using $F$. It is used to test whether $X$ is a superkey (when $X^{+}$ = all attributes) and whether a dependency $X \to Y$ is implied (when $Y \subseteq X^{+}$).

Define a prime and a non-prime attribute.

A prime attribute is a member of at least one candidate key. A non-prime (non-key) attribute belongs to no candidate key. These definitions are central to 2NF and 3NF.

What are the requirements for First Normal Form (1NF)?

Every attribute must contain only atomic (indivisible) values; no repeating groups, multivalued attributes, or nested relations are allowed. Each cell holds a single value.

What condition defines Second Normal Form (2NF)?

The relation is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key, i.e. no partial dependency of a non-prime attribute on part of a composite candidate key.

What condition defines Third Normal Form (3NF)?

The relation is in 2NF and has no transitive dependency of a non-prime attribute on a candidate key. Equivalently, for every FD $X \to Y$, either $X$ is a superkey or $Y$ is a prime attribute.

What is the condition for Boyce-Codd Normal Form (BCNF)?

For every non-trivial functional dependency $X \to Y$, $X$ must be a superkey. BCNF is stricter than 3NF (it drops the 'or $Y$ is prime' allowance).

Give the key difference between 3NF and BCNF and a tradeoff.

3NF allows $X \to Y$ where $Y$ is a prime attribute even if $X$ is not a superkey; BCNF does not. 3NF is always both lossless and dependency-preserving; BCNF is always lossless but may not preserve all dependencies.

What anomaly does Fourth Normal Form (4NF) address, and what is its condition?

4NF removes multivalued dependencies (MVDs). A relation is in 4NF if it is in BCNF and for every non-trivial MVD $X \twoheadrightarrow Y$, $X$ is a superkey.

What is normalization and what are its main goals?

Normalization is the process of decomposing relations to reduce redundancy and eliminate insertion, update, and deletion anomalies, while preserving data through lossless-join and (ideally) dependency-preserving decompositions.

What is the lossless-join (non-additive) property of a decomposition?

A decomposition of $R$ into $R_1$ and $R_2$ is lossless if $R_1 \bowtie R_2 = R$ exactly (no spurious tuples). It holds if $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$.

What does it mean for a decomposition to be dependency-preserving?

The union of the functional dependencies enforceable on the individual decomposed relations is equivalent to (has the same closure as) the original set $F$, so all FDs can be checked without performing a join.

List the three data anomalies that normalization eliminates.

Insertion anomaly (cannot add data without unrelated data), deletion anomaly (deleting a row loses unrelated facts), and update anomaly (redundant copies must all be updated consistently).

What is discretization in data preprocessing, and why is it used?

Discretization transforms continuous numeric attributes into a finite set of intervals/labels (bins). It is used to reduce data size, handle noise, and enable algorithms that require categorical input (e.g. some classification methods).

Distinguish supervised from unsupervised discretization.

Supervised discretization uses class label information to choose split points (e.g. entropy/information-gain-based binning). Unsupervised discretization ignores class labels (e.g. equal-width or equal-frequency binning).

Compare equal-width binning and equal-frequency (equal-depth) binning.

Equal-width divides the range into $k$ intervals of identical width $\frac{\max - \min}{k}$, sensitive to outliers and skew. Equal-frequency places approximately the same number of data points in each bin, giving uneven widths but balanced counts.

What is sampling in the context of data warehousing/mining, and why is it used?

Sampling selects a representative subset of the data to reduce the volume processed. It is a data-reduction technique allowing the cost of an algorithm to be sublinear in the size of the full dataset while approximating its behavior.

Differentiate sampling with replacement (SRSWR) from sampling without replacement (SRSWOR).

In sampling without replacement (SRSWOR) each selected tuple is removed and cannot be picked again. In sampling with replacement (SRSWR) a selected tuple is returned to the pool and may be chosen multiple times.

What is stratified sampling and when is it preferred?

The data is partitioned into homogeneous groups (strata) and samples are drawn from each stratum, often proportionally. It is preferred for skewed/imbalanced data to ensure all classes/groups are represented.

What is the difference between lossless and lossy compression?

Lossless compression allows exact reconstruction of the original data (e.g. run-length, Huffman coding). Lossy compression discards information so reconstruction is approximate (e.g. JPEG, wavelet/PCA truncation), trading fidelity for higher compression.

Name two common dimensionality-reduction techniques used for data compression and their basis.

Principal Component Analysis (PCA), which projects data onto orthogonal principal components capturing maximum variance, and the Discrete Wavelet Transform (DWT), which transforms data and retains the largest coefficients.

In data warehousing, what is a star schema?

A multidimensional model with a single central fact table containing measures and foreign keys, linked to a set of denormalized dimension tables. The diagram resembles a star; it favors query simplicity and performance over normalization.

How does a snowflake schema differ from a star schema?

In a snowflake schema the dimension tables are normalized into multiple related tables (hierarchies split out), reducing redundancy and storage but requiring more joins, which can slow queries compared to the denormalized star schema.

What is a fact constellation (galaxy) schema?

A schema in which multiple fact tables share common dimension tables. It models several interrelated subjects/data marts and is also called a galaxy schema.

What is a concept hierarchy in a data warehouse, and give an example?

A concept hierarchy maps low-level concepts to higher-level, more general ones, enabling roll-up and drill-down. Example for location: street $\to$ city $\to$ state $\to$ country.

What are the three categories of measures in a data cube, based on the aggregate function used?

Distributive (e.g. $\text{COUNT}$, $\text{SUM}$, $\text{MIN}$, $\text{MAX}$ — computable from partitions), Algebraic (e.g. $\text{AVG}=\frac{\text{SUM}}{\text{COUNT}}$, computed from a bounded number of distributive functions), and Holistic (e.g. $\text{MEDIAN}$, $\text{MODE}$, $\text{RANK}$ — no constant-size sub-aggregate).

Why is the AVG measure classified as algebraic rather than distributive in OLAP?

Because $\text{AVG}$ cannot be aggregated directly from partial averages, but it can be computed from two distributive measures: $\text{AVG} = \frac{\text{SUM}}{\text{COUNT}}$. An algebraic measure is obtained by an algebraic function over a bounded number of distributive measures.