Function and Relation Composition

Function composition

Given functions $f$ and $g$, function composition is written $(f \circ g)(x) = f(g(x))$. If $g(x) = y$ and $f(y) = z$, then $(f \circ g)(x) = z$.

The domain of $f \circ g$ is those $x$ in the domain of $g$ for which $g(x)$ lies in the domain of $f$.

Relation composition

Given relations $R \subseteq S \times T$ and $Q \subseteq T \times U$, their composition is:

$Q \circ R \subseteq S \times U$

$Q \circ R \equiv \{(s, u) \mid \exists t \in T.\; (s, t) \in R \land (t, u) \in Q\}$

We read $Q \circ R$ as ”$Q$ after $R$”: first follow $R$ from $s$ to some $t$, then follow $Q$ from $t$ to $u$. The intermediate element $t$ is existentially quantified and does not appear in the result.

Partial functions as relations

A relation $R \subseteq S \times T$ defines a (partial) function when:

$(s, t_1) \in R \land (s, t_2) \in R \implies t_1 = t_2$

That is, each $s$ is related to at most one $t$. This is the univalence (or functional) property.

A relation uniquely defines a total function if additionally every $s \in S$ has some $t$ with $(s, t) \in R$ (the relation is left-total).

When mathematicians say “function” they typically mean a total function. A relation may give multiple answers for the same input; a partial function may give at most one; a total function gives exactly one.

Property	Relation	Partial function	Total function
Univalued (at most one output)	Not required	Required	Required
Left-total (at least one output)	Not required	Not required	Required

Composition of functions is a special case

If $R$ and $Q$ are functions (univalued and left-total), then $Q \circ R$ as defined by relation composition coincides with ordinary function composition. The existential quantification $\exists t$ is equivalent to function application because $t$ is uniquely determined.

Joins as generalised composition

If we write $Q \circ R$ in join notation, identifying the $T$-component as the join column:

$R \bowtie_{2=1} Q$

We see that joins are a generalisation of function composition. The generalisation works in two directions:

1. Functions to relations: joins cope with relations that are not univalued (multiple outputs per input) and not left-total (some inputs have no output).
2. Equi-join to natural join: generalises from joining on a positional column to joining on named attributes.

Example

Let $R(\text{student}, \text{course})$ represent enrolment, and $Q(\text{course}, \text{lecturer})$ represent who teaches each course. Then $Q \circ R$ gives $(\text{student}, \text{lecturer})$ pairs: students and the lecturers of courses they take.

In SQL:

SELECT R.student, Q.lecturer
FROM R
JOIN Q ON R.course = Q.course;

If a student takes multiple courses, they appear with multiple lecturers. If a course has no lecturer (not left-total), the student for that course contributes no row to the result under an inner join.

Summary

• Function composition: $(f \circ g)(x) = f(g(x))$.
• Relation composition: $Q \circ R = \{(s, u) \mid \exists t.\; (s, t) \in R \land (t, u) \in Q\}$.
• Functions are univalued relations; total functions are also left-total.
• Function composition is a special case of relation composition.
• Joins ($R \bowtie Q$) are a generalisation of relation composition, further generalised by named attributes and outer join variants.