The whole Database Management and Warehousing formula sheet, to print

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.

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|\le \min (|A|,|B|)$.

Every entity of $E_i$ appears in at least one instance, and each instance contains exactly one entity of $E_i$.

Both bounds can be reached: the lower one by covering every entity with as few pairs as possible, the upper one by relating every pair.

The owner's key is copied in as a foreign key, normally declared ON DELETE CASCADE so that deleting an owner removes its weak entities. No separate relation is made for the identifying relationship.

Applies to a binary many-to-many relationship. Each key column is also a foreign key.

Counts recursive M:N relationship sets too. This is the count after merging every 1:1 and 1:N relationship (identifying relationships included) into an entity's relation. Each 1:1 relationship with total participation on both sides reduces the count by one more. Assumes no specialisation or aggregation.

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.

$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$.

Keeps whole tuples satisfying the condition; schema unchanged; $|{\sigma }_{\theta }(R)|\le |R|$.

Keeps the listed columns and removes duplicate rows (set semantics). For non-empty $R$, $1\le |{\pi }_L(R)|\le |R|$, with $|{\pi }_L(R)|=|R|$ whenever the list $L$ contains a superkey.

Pairs every tuple of $R$ with every tuple of $S$. Clashing attribute names are qualified ($R.A$, $S.A$) or renamed with $\rho$.

Defined only for union-compatible relations: the same degree, with the $i$-th attributes of both having the same domain. By convention the result takes its attribute names from the first operand. Union is commutative and associative; difference is neither.

Set semantics, $R$ and $S$ union-compatible. Also $|R\cup S|=|R|+|S|-|R\cap S|$ and $|R-S|=|R|-|R\cap S|$. The upper bounds of $\cup$ and $-$ are reached when $R\cap S=\varnothing$; their lower bounds when the smaller relation is contained in the larger.

$0\le |R{\bowtie }_{\theta }S|\le |R|\cdot |S|$. An equi-join is a theta join whose condition is only equalities; it keeps both copies of the compared attributes.

$C_1,\dots ,C_m$ are the attributes with the same name in both relations, and the result has degree $\mathrm{deg}R+\mathrm{deg}S-m$. With no common attribute it equals $R\times S$; when the two schemas are identical it equals $R\cap S$. A NULL never matches, not even another NULL. Natural join is commutative and associative (up to column order).

Union-compatible relations; $|R\cap S|\le \min (|R|,|S|)$.

$R(X,Y)$ and $S(Y)$, where the attributes $Y$ of $S$ are a proper subset of those of $R$ and $X$ is the rest. The result has schema $X$ (degree $\mathrm{deg}R-\mathrm{deg}S$): the $X$-values that appear in $R$ paired with every tuple of $S$. If $S$ is empty, the formula gives $R÷S={\pi }_X(R)$.

Each $X$-value in the result needs its own $|S|$ tuples in $R$, one for each tuple of $S$, and these tuples are different for different $X$-values.

$|R\bowtie S|$ is the inner (natural) join; $u_R$ and $u_S$ are the numbers of tuples of $R$ and of $S$ that match no tuple of the other relation. Left outer adds only $u_R$, right outer only $u_S$.

If the common attributes form a key of $S$, each tuple of $R$ matches at most one tuple of $S$, so $|R\bowtie S|\le |R|$. If they are also a foreign key of $R$ referencing $S$ with no NULL in it, the size is exactly $|R|$.

${\rho }_T(R)$ is a renamed copy of $R$. The subtracted part is every $A$-value that some other value of $A$ exceeds, so what remains is the maximum value of $A$. Use $>$ in place of $<$ for the minimum. This assumes $A$ contains no NULL.

The result is the set of all tuples $t$ for which formula $P$ is true. $t$ is the only free variable of $P$; every other tuple variable must be bound by a quantifier.

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.

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.

Both SUM and COUNT here skip NULLs, so AVG divides by the number of non-NULL values, not by the number of rows; when c has NULLs, AVG(c) differs from SUM(c)/COUNT(). If every value of c is NULL (or there are no rows), SUM, AVG, MIN and MAX return NULL and COUNT(c) returns 0, while COUNT() returns the number of rows (0 only when there are no rows).

Here c_R(v) and c_S(v) are the numbers of rows of R and S with key value v. Sum over non-NULL values v only: a NULL key never satisfies equality, so it matches nothing.

A row is unmatched if no row of the other table satisfies the ON condition; rows with a NULL join key are always unmatched. Every row of R appears at least once in R LEFT JOIN S, so the left join has at least |R| rows.

x op ANY S is TRUE if the comparison is TRUE for at least one value in S; x op ALL S is TRUE if it is TRUE for every value in S. On an empty S, ANY is FALSE and ALL is TRUE.

Because NOT UNKNOWN is still UNKNOWN, a row failing both p and NOT p can exist: WHERE p OR NOT p does not return every row when p can be UNKNOWN.

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

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

Algorithm: start with result = X; repeatedly, for any FD $U\to V$ in F with $U\subseteq$ result, add $V$; stop when nothing is added.

Use the closure algorithm for both. A candidate key is a minimal superkey: removing any attribute breaks $X^{+}=R$.

A superkey is any set containing at least one candidate key. For more keys, extend by inclusion and exclusion over unions of keys. Example: keys AB, BC, BD in R(A,B,C,D) give $3\cdot 4-3\cdot 2+1=7$.

No candidate key contains another, and this bound is reached (for example, when every set of $\lfloor n/2\rfloor$ attributes is a key).

For the relation R on which F is given, it is enough to test the FDs of F after splitting right sides into single attributes. For a part $R_i$ of a decomposition, test the FDs of $F^{+}$ that lie inside $R_i$ (the projection), not just those of F.

Conditions: $R_1\cup R_2=R$ and F is the only set of constraints. The common attributes must be a superkey of at least one of the two parts. For more than two parts, use the tableau (chase) test.

Practical test for each $X\to Y$ in F: set $Z=X$, and repeat $Z\leftarrow Z\cup ((Z\cap R_i{)}^{+}\cap R_i)$ for every $R_i$, with closures computed using F, until Z stops growing. The FD is preserved if $Y\subseteq Z$.

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

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

Applies only to the field the file is sorted on, and counts block accesses, not record comparisons. This is the usual convention in problems; the strict worst case of binary search is $\lfloor {\log }_{2}b\rfloor +1$, which is one more only when $b$ is a power of 2. Follow the convention the question states.

Entries per index block, where an entry is a key plus a block pointer (replace $P$ by $P_r$ if the entries hold record pointers).

Dense: one entry per record. Sparse primary index: one entry per data block. A clustering index on a field with $d$ distinct values needs $\lceil d/bf{r}_i\rceil$ blocks.

Binary search over the $b_i$ index blocks (same convention as for a sorted file), plus one access to fetch the data block. A non-key secondary index with a level of indirection adds one more access for the block of record pointers.

$fo=bf{r}_i$ is the fan-out, $r_1$ the number of first-level entries and $b_1=\lceil r_1/fo\rceil$ the number of first-level blocks. The first form is valid for $b_1\ge 1$ (for $b_1=1$, $t=1$); the second for $r_1\ge 2$.

Largest $p$ satisfying this; internal nodes hold $p$ block pointers and $p-1$ keys.

Largest number of keys $q$ in a leaf, where the extra $P$ is the next-leaf pointer.

Each key in a B-tree node carries a record pointer, so one node type serves internal nodes and leaves.

Max: every node full, so $p^{h-1}$ leaves of $q$ keys. Min: the root has 2 children and every other internal node $\lceil p/2\rceil$, giving $2\lceil p/2{\rceil }^{h-2}$ leaves, each with $\lceil q/2\rceil$ keys.

Max: all $(p^h-1)/(p-1)$ nodes full with $p-1$ keys each. Min: the root has 1 key (2 children) and every other node $\lceil p/2\rceil -1$ keys.

One block per level down to the leaf, plus one to read the data record. Leaves holding the record itself need only $h$.

$d$ is the global depth and $d^{\prime }$ a bucket's local depth.

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).

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.

Moves the decimal point; j is fixed by the value of largest absolute magnitude. Result lies strictly inside (-1, 1). Examples: max|v| = 986 gives j = 3; max|v| = 1000 gives j = 4.

Bins have the same width and usually unequal counts. Convention here: left-closed, right-open, with the last bin closed so the maximum belongs to it.

Sort the data and put n/k consecutive values in each bin; widths differ. If k does not divide n, bin sizes are floor(n/k) or ceil(n/k) and the question must say which bins take the extra values. Tied values may need to share a bin.

D_1 and D_2 are the tuples with attribute value at most, and above, the candidate split point T; p_i is the fraction of a set in class i. Choose the T that minimises Info_T(D), which is the same as maximising the information gain Entropy(D) - Info_T(D). Apply recursively to each part until a stopping rule is met.

Sample of n distinct tuples from N, all subsets equally likely.

n independent draws, each tuple chosen with probability 1/N per draw; N^n ordered outcomes.

By linearity of expectation over the N tuples. The limit is the bootstrap fact: a with-replacement sample of size N contains about 63.2% of the distinct tuples, and about 36.8% never appear.

Stratum h of size N_h receives a share of the total sample n in proportion to its size; round so that the n_h sum to n.

When N = nk exactly, every tuple has inclusion probability 1/k = n/N, but only k distinct samples are possible.

A ratio above 1 means the data shrank. Space saving = 1 - compressed/original.

For an alphabet of m >= 2 distinct symbols. A Huffman code never needs more bits per symbol on average than this, and needs fewer for some unequal frequency distributions (not all: probabilities 0.3, 0.3, 0.2, 0.2 give Huffman lengths 2, 2, 2, 2).

p_i is the probability (relative frequency) of symbol i and l_i its code length in bits. No lossless symbol-by-symbol prefix code averages below H; Huffman's code is optimal among them and reaches H exactly when every p_i is a power of 1/2.

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

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

L_i is the number of distinct levels of dimension i, excluding the virtual top level 'all'; the +1 accounts for 'all'. A cuboid picks one level (or 'all') per dimension, so this holds for a total order and for a lattice; in a lattice count every level once (day, week, month gives L = 3).

Both counts include the grand total ().

c_i is the number of distinct values of dimension i at its lowest level; this is an upper bound that is reached only if every combination occurs.

Each dimension contributes its c_i values or the single value 'all' (written *). Counts every cell of every cuboid, assuming all combinations are non-empty. With hierarchies, replace c_i + 1 by 1 plus the total number of distinct values over all levels of dimension i.

s_j and n_j are the sum and count of partition j. The average of the partition averages differs from this in general; it is guaranteed to equal it only when all n_j are equal.

Needs only count N, sum and sum of squares, each distributive, so variance is algebraic with M = 3. Population variance (divide by N).