Division (Relational Algebra)

relational-algebra

Definition

Division (Relational Algebra)

Let $R(X,Y)$ and $S(Y)$ be relations, where $S$‘s attributes $Y$ are a subset of $R$‘s. The division $R÷S$ is the largest relation over $X$ whose Cartesian product with $S$ is contained in $R$:

$$R÷S=\{t_X\mid \forall t_S\in S.(t_X,t_S)\in R\}.$$

Concretely, $t_X$ is in $R÷S$ exactly when it is paired in $R$ with every tuple of $S$. Division answers “for all” queries against the data.

Construction from Primitive Operators

Division is not primitive: it can be expressed using projection, difference, and the Cartesian product. Denoting the schema of $R$ minus the schema of $S$ as $X=\mathcal{R}-\mathcal{S}$,

$$R÷S={\Pi }_X(R)-{\Pi }_X(({\Pi }_X(R)\times S)-R).$$

The expression has four stages:

1. ${\Pi }_X(R)$ — the candidate set: every $X$-tuple that appears in $R$, with the $S$-attributes dropped.
2. ${\Pi }_X(R)\times S$ — every candidate paired with every tuple of $S$.
3. $({\Pi }_X(R)\times S)-R$ — the missing pairs: candidate–$S$ combinations that do not occur in $R$. A candidate appearing here fails the “for all” requirement for at least one $S$-tuple.
4. ${\Pi }_X(\cdots )-\cdots$ — subtract from the candidates those proven to be missing a required combination.

The candidates that survive are exactly those whose Cartesian product with $S$ is contained in $R$.

Candidate $b$ is dropped because the required pair $(b,s_2)$ is absent from $R$; candidate $a$ survives because both $(a,s_1)$ and $(a,s_2)$ occur.