Relations are common in AI and database systems. The relational algebra defines operations on relations and is the basis of relational databases.

A scope $S$ is a set of variables. A tuple $t$ on scope $S$ has a value on each variable in its scope. A variable can be seen as a function on tuples; one that returns the value for that variable for that tuple. We write $X(t)$ to be the value of tuple $t$ on variable $X$. The value of $X(t)$ must be in $dom(X)$. This is like the mathematical notion of tuple, except the index is given by a variable, not by an integer.

A relation is a set of tuples, all with the same scope. A relation is often given a name. The scope of the tuples is often called the relation scheme. A relational database is a set of relations. A scheme of a relational database is the set of pairs of relation names and relation schemes.

A relation with scope $X_1,\mathrm{\dots },X_n$ can be seen as a Boolean factor on $X_1,\mathrm{\dots },X_n$, where the true elements are represented as tuples.

Often a relation is written as a table.

If $r$ is a relation with scheme $S$, and $c$ is a condition on the variables in $S$, the selection of $c$ in $r$, written ${\sigma }_c(r)$, is the set of tuples in $r$ for which $c$ holds. The selection has the same scheme as $r$.

If $r$ is a relation with scheme $S$, and $S_0\subseteq S$, the projection of $r$ onto $S_0$, written ${\pi }_{S_0}(r)$, is the set of tuples of $r$ where the scope is restricted to $S_0$.

If two relations are on the same scheme, the union, intersection, and set difference of these are defined as the corresponding operations on the set of tuples.

If $r_1$ and $r_2$ are two relations, the natural join of $r_1$ and $r_2$, written $r_1\bowtie r_2$, is a relation where

• •

  the scheme of the join is the union of the scheme of $r_1$ and the scheme of $r_2$

• •

  a tuple is in the join if the tuple restricted to the scope of $r_1$ is in the relation $r_1$ and the tuple restricted to the scope of $r_2$ is in the relation $r_2$.