GATE Database Management and Warehousing formula sheet

75 formulas in 7 topics, each with when to use it. Each is explained in the topic notes.

UPPER BOUND ON A RELATIONSHIP SET

∣ R ∣ \leq ∣ E_{1} ∣ \cdot ∣ E_{2} ∣ \dots ∣ E_{n} ∣

For an n-ary relationship set $R$ over entity sets $E_{1}, \dots, E_{n}$ . It holds because no two instances relate the same combination of entities. The bound is reached only when every combination is related.

BOUND FROM AN AT-MOST-ONE SIDE

∣ R ∣ \leq ∣ B ∣ if each b \in B appears in at most one tuple of R

In a binary 1:N relationship from A to B (each B related to at most one A), the count is at most $∣ B ∣$ . With total participation of B it equals $∣ B ∣$ . In a 1:1 relationship both sides are at-most-one, so $∣ R ∣ \leq min (∣ A ∣, ∣ B ∣)$ .

The relational model: relational algebra and tuple calculus

All 16 formulas

SUPERKEY CONDITION

K superkey of R ⟺ \forall t_{1} \neq = t_{2} \in R : t_{1} [K] \neq = t_{2} [K]

Every superset of a superkey (within the attributes of $R$ ) is a superkey, so under set semantics the set of all attributes is always a superkey. Candidate keys are the minimal superkeys.

COUNTING SUPERKEYS

one candidate key K : 2^{n - ∣ K ∣}, two candidate keys K_{1}, K_{2} : 2^{n - ∣ K_{1} ∣} + 2^{n - ∣ K_{2} ∣} - 2^{n - ∣ K_{1} \cup K_{2} ∣}

$n$ is the number of attributes of $R$ . A superkey is any attribute set that contains at least one candidate key. With two keys, inclusion-exclusion subtracts the sets counted twice: those containing $K_{1} \cup K_{2}$ .

SQL

All 7 formulas

LOGICAL EVALUATION ORDER OF A QUERY BLOCK

FROM \to WHERE \to GROUP BY \to HAVING \to SELECT \to DISTINCT \to ORDER BY

Rows are filtered by WHERE before grouping; groups are filtered by HAVING after aggregation; ORDER BY runs last and does not change which rows are returned.

BAG COUNTS FOR SET OPERATIONS

UNION ALL: INTERSECT ALL: EXCEPT ALL: m + n min (m, n) max (m - n, 0)

Here m and n are the number of copies of one particular tuple in the first and second operand. Without ALL, each of these results has at most one copy of every tuple.

Integrity constraints, functional dependencies and normal forms

All 9 formulas

ARMSTRONG'S AXIOMS (SOUND AND COMPLETE)

Reflexivity: Y \subseteq X \Rightarrow X \to Y Augmentation: X \to Y \Rightarrow X Z \to Y Z Transitivity: X \to Y, Y \to Z \Rightarrow X \to Z

Sound: they derive only FDs implied by F. Complete: they derive every FD in the closure F^+.

DERIVED RULES

Union: X \to Y, X \to Z \Rightarrow X \to Y Z Decomposition: X \to Y Z \Rightarrow X \to Y, X \to Z Pseudotransitivity: X \to Y, W Y \to Z \Rightarrow W X \to Z

All follow from the three axioms. Decomposition applies to the right side only; $X Y \to Z$ does not give $X \to Z$ .

File organisation and indexing

All 14 formulas

BLOCKING FACTOR (UNSPANNED)

b f r = ⌊ \frac{B}{R} ⌋

Records per block. The floor is essential: with unspanned records the leftover $B - b f r \cdot R$ bytes in each block are unused.

NUMBER OF DATA BLOCKS

b = ⌈ \frac{r}{b f r} ⌉

Blocks needed for $r$ records; round up because a partly filled last block still occupies a block.

Data types and data transformation: normalisation, discretisation, sampling and compression

All 14 formulas

MIN-MAX NORMALISATION TO [NEW_MIN, NEW_MAX]

v^{'} = new_{m i n} + \frac{v - min}{max - min} (new_{m a x} - new_{m i n})

Linear map of the observed range onto the target range; for [0,1] it reduces to (v - min)/(max - min). Preserves the shape of the distribution and the order of values. Undefined when max = min (all values equal).

Z-SCORE NORMALISATION

v^{'} = \frac{v - x ˉ}{σ}

Result has mean 0 and standard deviation 1 (under the same convention for sigma). Convention: use the population standard deviation (divide by n) unless the question says sample (divide by n - 1). Not bounded to a fixed range; undefined when sigma = 0. A variant divides by the mean absolute deviation s = (1/n) times the sum of |v - mean| instead of sigma; it is less affected by outliers because deviations are not squared.

Data warehouse modelling: multidimensional schemas, concept hierarchies and measures

All 8 formulas

CUBOIDS WITH NO HIERARCHIES

number of cuboids = 2^{n}

n dimensions, each with a single level (apart from 'all'). Each dimension is either present or rolled up to all.

CUBOIDS WITH EXACTLY K DIMENSIONS (NO HIERARCHIES)

(k n)

Choose which k of the n dimensions stay; summing over k = 0 to n gives 2^n.