Databases

Functional dependency inference

A functional dependency X \to Y means that any two tuples that agree on every attribute in X must also agree on every attribute in Y. Inference asks which dependencies follow logically from a given set F. The standard tools are Armstrong's axioms (reflexivity, augmentation and transitivity) and their derived rules: decomposition, union and pseudotransitivity. The closure X^+ of an attribute set is the set of all attributes determined by X under F, and X \to Y is implied exactly when Y \subseteq X^+. Computing closures is therefore the fastest test in practice.

• Closure X^+ — the set of attributes determined by X. Example: if F = \{A \to B, B \to C\}, then A^+ = \{A, B, C\}, so A \to C is implied.
• Decomposition — from X \to YZ infer X \to Y. Example: A \to BC gives A \to B.
• Pseudotransitivity — from X \to Y and WY \to Z infer WX \to Z. Example: A \to B and CB \to D give CA \to D.

The whole left-hand side must be used. Several attributes together may determine what none of them determines alone, so a closure computed from one attribute can miss a dependency that a larger set reaches. For example, with A \to BC and BD \to E, the attribute A alone determines B and C, but AD is needed to reach E.

Once a candidate key is known, the superkeys can be counted. Every superset of a candidate key is a superkey, so if a candidate key has k attributes and the relation has n attributes, there are 2^{n-k} superkeys containing that key.

Dependencies are not symmetric and do not split on the left. A \to B does not imply B \to A, and XY \to ZW does not imply X \to ZW in general. Decomposition works only on the right-hand side, while pseudotransitivity lets a dependency be extended on the left.

To count useful functional dependencies, note that a pair (X,Y) of disjoint sets over n attributes assigns each attribute to X, to Y, or to neither, which gives 3^n assignments. Remove the cases with X empty (2^n) and with Y empty (2^n), then add back the case with both empty once, giving 3^n - 2 \cdot 2^n + 1. For n = 4 this is 50.

Normal form tests use the same closure machinery. A dependency X \to Y violates 3NF when X is not a superkey and some attribute of Y is not prime. Attributes that never appear on a right-hand side belong to every candidate key, which helps find the keys quickly.

To show that a claimed implication is false, build a small relation that satisfies the premises and violates the conclusion. Such a counterexample needs only a few tuples, and a statement that holds in every relation can be proved with Armstrong's rules.

The union rule is derived from the three basic axioms. From X \to Y, augmentation with X gives X \to XY, and from X \to Z, augmentation with Y gives XY \to YZ. Transitivity then yields X \to YZ. Reflexivity is not needed, while augmentation and transitivity are both necessary.

Conflict serializability

Two operations conflict when they belong to different transactions, access the same data item, and at least one of them is a write. Two reads on the same item never conflict. A schedule is conflict serializable when it is conflict equivalent to some serial schedule, that is, when every pair of conflicting operations appears in the same relative order in both.

The standard test is the precedence graph. Each transaction is a node, and an edge T_i \to T_j is drawn when an operation of T_i precedes a conflicting operation of T_j. The schedule is conflict serializable if and only if this graph has no cycle. A topological order of the acyclic graph gives an equivalent serial schedule.

• Conflict pair — R_i(x) before W_j(x) or W_i(x) before any operation of T_j on x, with i \ne j.
• Conflict equivalence — same operations, same conflicting pairs, same order.
• Serial order from a graph — any topological order, if the graph is acyclic.

A cycle is decisive: if one transaction must precede another and also follow it through a chain, no serial order exists. Schedules with a read before a write by another transaction and a write before a read in the other direction usually produce such a cycle.

Serializability and recoverability are different properties. A schedule can be conflict serializable and still be unrecoverable, when a transaction reads a value written by a transaction that has not yet committed and then commits first. Recoverability concerns commit order, while serializability concerns conflict order.

To find a serial schedule that is conflict equivalent to a given schedule, list the precedence constraints from the conflicting pairs and check each candidate order against all of them. An order that satisfies every constraint is correct, and one order that violates a single constraint is wrong.

When only some transactions conflict, the rest can be placed freely. Transactions that share no conflicting item with the others may appear anywhere, but the order between any two transactions that conflict on an item must still match the schedule.

An acyclic graph is found after writing all conflicts in both directions and noticing that every conflict points the same way. A commit or write placed after all operations of the other transaction does not create a new conflict unless the item is shared.

Relational algebra query evaluation

Relational algebra expresses a query as a tree of operators: selection \sigma, projection \pi, cross product \times, natural and theta joins \bowtie, and rename \rho. Evaluation proceeds bottom-up, and the size of each intermediate result depends on the operators used.

• Selection estimate — for an equality A = c on a uniformly distributed attribute with d values, the selectivity is 1/d. For a conjunction of independent conditions the selectivities multiply.
• Disjunction — under independence, the selectivity of c_1 \lor c_2 is s_1 + s_2 - s_1 s_2. Example: with n = 1000 tuples, s_1 = 0.1 and s_2 = 0.25, the estimate is 1000 \times 0.325 = 325 tuples.
• Expected output — the number of tuples is n times the selectivity of the whole condition.

The estimate uses probabilities of the attribute values as stated, so the range of values matters. When a condition covers a fraction of the range, the fraction is the count of matching values divided by the count of all values.

A theta join of a relation with a renamed copy of itself, using a strict inequality on one attribute, keeps each pair in which one value is strictly larger. Projecting the key of the first copy therefore returns every key that has at least one strictly smaller partner, and the only excluded value is the minimum. Using > instead of \ge matters, because equality would keep the minimum as well.

For a join followed by a selection that compares attributes from both relations, first find all matching pairs under the equijoin condition, including repeated matches when the join attribute repeats, and then apply the comparison to each pair. A tuple that fails the comparison is removed even though its join condition holds.

With only selection, projection, cross product and rename, a query asking for at least k tuples with a common property needs k renamed copies of the relation. These copies are formed with k-1 cross products, distinctness is enforced by selections such as \neq, and a final projection gives the answer. Fewer cross products cannot provide k distinct tuples.

SQL SELECT with joins

A SELECT query combines a join or a nested subquery with a filter, grouping and aggregation. Joins match tuples on equal values of attributes, while a subquery expresses a condition on a set of tuples. Some constructs look similar but behave differently, so the exact meaning must be checked.

• EXISTS — true when the subquery returns at least one row. It is often written as a correlated subquery that refers to an outer alias.
• NOT EXISTS over EXCEPT — the outer row qualifies when the set on the left of EXCEPT is empty, that is, when every element is also present in the set on the right. This pattern tests that a row covers a complete set.
• NATURAL JOIN — joins on all columns that have the same name in both tables. An unexpected common column changes the result.
• COUNT — counts rows; comparing it with zero is equivalent to EXISTS in a correlated subquery.
• Non-SQL functions — SIZEOF and similar names are not standard SQL, so a query using them is invalid.

A correlated NOT EXISTS over EXCEPT is a division-like condition: the outer row is kept only when the required set is fully covered. Such a query returns rows where the subquery is empty, so it is necessary to check which items the outer row must match.

A nested IN subquery can contain a multi-table join, and the outer query then selects rows whose key appears in the inner result. An aggregate such as MIN applied in the outer query is computed over the rows that survive the IN filter, so the final value depends on both levels.

When several conditions must be tested for the same student, an EXISTS condition or a count greater than zero each returns a qualifying row once. A join with a filter on the other table may return duplicate names if the join produces several rows for one student, so duplicates are avoided only when the filtered key identifies at most one row. A NATURAL JOIN is valid here only because the two tables share just the key attribute.

B+ tree node occupancy rules

A B+ tree of order m keeps every node except the root at least half full. An internal node other than the root has at least \lceil m/2 \rceil children, and a leaf other than the root holds at least \lceil (m-1)/2 \rceil keys. The root is exempt from this lower bound, so it may hold just one key, or it may be a leaf with few keys.

In a B+ tree, a key k in an internal node separates subtrees: the pointer between two keys k_1 and k_2 leads to keys in the interval [k_1, k_2), so a separator key belongs to the subtree on its right.

• Leaf split — when a leaf overflows, it is split, and the smallest key of the new right node is copied up into the parent. The copy remains in the leaf.
• Internal split — the middle key is pushed up into the parent and does not remain in either half.
• Root split — creates a new root, and the height of the tree increases by one.

The lower occupancy rule therefore applies to every node except the root, and an insertion that splits a node may change which node holds a particular separator.

When a full leaf receives a new key, it splits and one key is copied up. If the parent is also full, the parent splits and pushes its middle key up. Only a split of the root increases the height, and each split adds nodes, so the node count grows with each level of splitting.

To find the smallest key of the parent of a particular leaf, trace the parent after insertion. The copied key from a leaf split or the pushed key from an internal split determines which key begins the right half, so the separator that opens the subtree containing the key is the answer.

Lossless join decomposition

A decomposition of a relation R into R_1, \dots, R_k is lossless when the natural join of the projections equals R for every legal instance. A decomposition that cannot recover the original tuples is lossy, and extra spurious tuples may appear.

For a binary decomposition R = R_1 \cup R_2, the standard test is that the common attributes R_1 \cap R_2 functionally determine all attributes of R_1, or all attributes of R_2. If the common attributes are empty, the join is a cross product, so the decomposition is lossy unless one piece is trivial. For more than two pieces, the tableau chase is used: rows are built from distinguished and nondistinguished symbols, equated through the functional dependencies, and the decomposition is lossless exactly when some row becomes fully distinguished.

• Chase — a procedure applying functional dependencies to a tableau to equate symbols.
• Lossless test (binary) — intersection determines one of the two pieces.
• Dependency preservation — a different property, which a lossless decomposition need not have.

If two pieces of a decomposition share no attribute, the join produces every combination of tuples, so information is lost. Checking the chase or the intersection rule decides the case.

For a binary split, the common attribute of the two pieces is a key of one piece, so the decomposition is lossless. When a schema such as name determining every other attribute is split into two pieces both containing name, the pieces are in BCNF as well, and the join recovers the original relation.

Foreign key constraints

A foreign key is a set of attributes in a referencing relation whose values must either be null or match the values of a candidate key, usually the primary key, of a referenced relation. A relation may contain any number of foreign keys, and a foreign key may refer to tuples of the same relation, as in a manager column that points to another employee row. Foreign key constraints preserve referential integrity.

When a table has a foreign key column, grouping by that column gives one group per referenced row. In SQL, the WHERE clause is applied to rows before GROUP BY, and a subquery that does not refer to the outer query is evaluated only once for the whole table. A scalar subquery such as an average over all rows therefore gives one value for every group, not one value per group.

ER diagram modeling of relationships

An entity-relationship diagram models entities, their attributes, and the relationships between them. A relationship is a named association drawn as a diamond between the entity sets that participate in it, and the cardinality and participation constraints describe how many entities take part. Each sentence of a specification usually corresponds to one relationship set between the entity sets named in it.

• Binary relationship — a diamond connecting two entity sets.
• Attribute versus relationship — an attribute describes a single entity, so a link between two entities must be a relationship and not an attribute.
• Total participation — every entity of a set must take part in the relationship, drawn as a double line.

To check a diagram, map each sentence to its participants and verify that each relationship connects the right entity sets. A diagram that introduces an entity not in the specification, or that leaves a relationship without a participating entity, is wrong.

A weak entity set has no key of its own. It is identified through a relationship with an owner entity set, and every weak entity must participate in that identifying relationship, so its participation is total. The owner entity set need not participate totally, because an owner may exist with no dependent weak entity.

Relational calculus query expression

A tuple relational calculus query has the form \{t \mid P(t)\}, where t is a tuple variable and P is a formula built from atoms t \in R, comparisons such as t.A = c, and quantifiers. Variables introduced by \exists are bound, and the free variable that appears in the output determines which relation the result comes from.

• Range of the output variable — the output variable must range over the relation that contains the attributes being returned.
• Join through a shared condition — a bound variable ranging over another relation is connected to the output variable by an equality of attributes, such as p.A = t.B.
• Selection on constants — a condition such as t.name = c restricts the bound variable.

In a query that returns attributes of one relation while filtering through another, the connecting equality must be stated explicitly. Omitting it returns too many tuples, and ranging the output variable over the wrong relation makes the query invalid.

A variable shared between two atoms expresses an equijoin. When one attribute of the first relation must equal an attribute of the second, the corresponding relational algebra form is a join on that equality followed by a projection of the output attributes. Joining on the wrong attribute pair, such as a first attribute with a second attribute, gives a different expression.

Crash recovery with logging

In a log-based recovery scheme, changes are written to a durable log before they reach the database, following the write-ahead logging rule. Recovery after a failure consists of a redo pass that reapplies logged changes and an undo pass that rolls back uncommitted transactions. During undo, the system writes compensation log records, which record that an action has been reversed and let recovery skip work already done.

• Checkpoint — a record that limits how far back the log scan must go. Without a checkpoint, recovery scans the log from the beginning.
• Idempotence — repeating recovery yields the same database state because redo and undo are designed to be safe to repeat.
• Repeated crash — the log is durable, so a crash during recovery leaves the log intact and recovery restarts from the same records.

When a crash occurs during recovery and no new checkpoint has been taken, the second recovery reads the same log records and reconstructs the same redo and undo work. Compensation records and the redo rules keep the database consistent, so the system can recover again rather than stopping.

Extendible hashing directory splitting

Extendible hashing uses the low-order bits of a key to index a directory. A bucket is split only when it overflows, and a split uses the next bit that the bucket has not yet used. In a variant that stores each directory entry as a binary tree, the first split at an entry uses the bit just above the directory bits, and deeper nodes use further bits.

• Directory bits — the number of least significant bits used to index the main table.
• Split on collision — a node is subdivided only when a new key lands in a full position with the same bits.
• Order dependence — because splits happen only on collisions, the sequence of insertions determines which nodes exist.