foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
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.
The following is a tabular depiction of a relation, ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}$:
$\begin{array}{cccc}{C}{}{o}{}{u}{}{r}{}{s}{}{e}\hfill & {Y}{}{e}{}{a}{}{r}\hfill & {S}{}{t}{}{u}{}{d}{}{e}{}{n}{}{t}\hfill & {G}{}{r}{}{a}{}{d}{}{e}\hfill \\ {c}{}{s}{}{322}\hfill & {2008}\hfill & {f}{}{r}{}{a}{}{n}\hfill & {77}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {b}{}{i}{}{l}{}{l}{}{i}{}{e}\hfill & {88}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {j}{}{e}{}{s}{}{s}\hfill & {78}\hfill \\ {c}{}{s}{}{444}\hfill & {2008}\hfill & {f}{}{r}{}{a}{}{n}\hfill & {83}\hfill \\ {c}{}{s}{}{322}\hfill & {2009}\hfill & {j}{}{o}{}{r}{}{d}{}{a}{}{n}\hfill & {92}\hfill \end{array}$
The heading gives the scheme, namely ${\mathrm{\{}}{C}{\mathit{}}{o}{\mathit{}}{u}{\mathit{}}{r}{\mathit{}}{s}{\mathit{}}{e}{\mathrm{,}}{Y}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathrm{,}}{S}{\mathit{}}{t}{\mathit{}}{u}{\mathit{}}{d}{\mathit{}}{e}{\mathit{}}{n}{\mathit{}}{t}{\mathrm{,}}{G}{\mathit{}}{r}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{e}{\mathrm{\}}}$, and every other row is a tuple. The first tuple, call it ${{t}}_{{\mathrm{1}}}$ is defined by ${C}{\mathit{}}{o}{\mathit{}}{u}{\mathit{}}{r}{\mathit{}}{s}{\mathit{}}{e}{\mathit{}}{\mathrm{(}}{{t}}_{{\mathrm{1}}}{\mathrm{)}}{\mathrm{=}}{c}{\mathit{}}{s}{\mathit{}}{\mathrm{322}}$, ${Y}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathit{}}{\mathrm{(}}{{t}}_{{\mathrm{1}}}{\mathrm{)}}{\mathrm{=}}{\mathrm{2008}}$, ${S}{\mathit{}}{t}{\mathit{}}{u}{\mathit{}}{d}{\mathit{}}{e}{\mathit{}}{n}{\mathit{}}{t}{\mathit{}}{\mathrm{(}}{{t}}_{{\mathrm{1}}}{\mathrm{)}}{\mathrm{=}}{f}{\mathit{}}{r}{\mathit{}}{a}{\mathit{}}{n}$, ${G}{\mathit{}}{r}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{e}{\mathit{}}{\mathrm{(}}{{t}}_{{\mathrm{1}}}{\mathrm{)}}{\mathrm{=}}{\mathrm{77}}$.
The order of the columns and the order of the rows is not significant.
If $r$ 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}$.
Suppose ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}$ is the relation given in Example A.2.
The relation ${{\sigma}}_{{G}{\mathit{}}{r}{\mathit{}}{a}{\mathit{}}{d}{\mathit{}}{e}{\mathrm{>}}{\mathrm{79}}}{\mathit{}}{\mathrm{(}}{e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}{\mathrm{)}}$ selects those tuples in ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}$ where the grade is over 79. This is the relation:
$\begin{array}{cccc}{C}{}{o}{}{u}{}{r}{}{s}{}{e}\hfill & {Y}{}{e}{}{a}{}{r}\hfill & {S}{}{t}{}{u}{}{d}{}{e}{}{n}{}{t}\hfill & {G}{}{r}{}{a}{}{d}{}{e}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {b}{}{i}{}{l}{}{l}{}{i}{}{e}\hfill & {88}\hfill \\ {c}{}{s}{}{444}\hfill & {2008}\hfill & {f}{}{r}{}{a}{}{n}\hfill & {83}\hfill \\ {c}{}{s}{}{322}\hfill & {2009}\hfill & {j}{}{o}{}{r}{}{d}{}{a}{}{n}\hfill & {92}\hfill \end{array}$
The relation ${{\pi}}_{{\mathrm{\{}}{S}{\mathit{}}{t}{\mathit{}}{u}{\mathit{}}{d}{\mathit{}}{e}{\mathit{}}{n}{\mathit{}}{t}{\mathrm{,}}{Y}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathrm{\}}}}{\mathit{}}{\mathrm{(}}{e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}{\mathrm{)}}$ specifies what years students were enrolled:
$\begin{array}{cc}{S}{}{t}{}{u}{}{d}{}{e}{}{n}{}{t}\hfill & {Y}{}{e}{}{a}{}{r}\hfill \\ {f}{}{r}{}{a}{}{n}\hfill & {2008}\hfill \\ {b}{}{i}{}{l}{}{l}{}{i}{}{e}\hfill & {2009}\hfill \\ {j}{}{e}{}{s}{}{s}\hfill & {2009}\hfill \\ {j}{}{o}{}{r}{}{d}{}{a}{}{n}\hfill & {2009}\hfill \end{array}$
Notice how the first and the fourth tuple of ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}$ become the same tuple in the projection; they represent the same function on ${\mathrm{\{}}{S}{\mathit{}}{t}{\mathit{}}{u}{\mathit{}}{d}{\mathit{}}{e}{\mathit{}}{n}{\mathit{}}{t}{\mathrm{,}}{Y}{\mathit{}}{e}{\mathit{}}{a}{\mathit{}}{r}{\mathrm{\}}}$.
If two relations 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}$.
Consider the relation ${a}{\mathit{}}{s}{\mathit{}}{s}{\mathit{}}{i}{\mathit{}}{s}{\mathit{}}{t}{\mathit{}}{e}{\mathit{}}{d}$:
$\begin{array}{ccc}{C}{}{o}{}{u}{}{r}{}{s}{}{e}\hfill & {Y}{}{e}{}{a}{}{r}\hfill & {T}{}{A}\hfill \\ {c}{}{s}{}{322}\hfill & {2008}\hfill & {y}{}{u}{}{k}{}{i}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {s}{}{a}{}{m}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {c}{}{h}{}{r}{}{i}{}{s}\hfill \\ {c}{}{s}{}{322}\hfill & {2009}\hfill & {y}{}{u}{}{k}{}{i}\hfill \end{array}$
The join of ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}$ and ${a}{\mathit{}}{s}{\mathit{}}{s}{\mathit{}}{i}{\mathit{}}{s}{\mathit{}}{t}{\mathit{}}{e}{\mathit{}}{d}$, written ${e}{\mathit{}}{n}{\mathit{}}{r}{\mathit{}}{o}{\mathit{}}{l}{\mathit{}}{l}{\mathit{}}{e}{\mathit{}}{d}{\mathrm{\bowtie}}{a}{\mathit{}}{s}{\mathit{}}{s}{\mathit{}}{i}{\mathit{}}{s}{\mathit{}}{t}{\mathit{}}{e}{\mathit{}}{d}$ is the relation:
$\begin{array}{ccccc}{C}{}{o}{}{u}{}{r}{}{s}{}{e}\hfill & {Y}{}{e}{}{a}{}{r}\hfill & {S}{}{t}{}{u}{}{d}{}{e}{}{n}{}{t}\hfill & {G}{}{r}{}{a}{}{d}{}{e}\hfill & {T}{}{A}\hfill \\ {c}{}{s}{}{322}\hfill & {2008}\hfill & {f}{}{r}{}{a}{}{n}\hfill & {77}\hfill & {y}{}{u}{}{k}{}{i}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {b}{}{i}{}{l}{}{l}{}{i}{}{e}\hfill & {88}\hfill & {s}{}{a}{}{m}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {j}{}{e}{}{s}{}{s}\hfill & {78}\hfill & {s}{}{a}{}{m}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {b}{}{i}{}{l}{}{l}{}{i}{}{e}\hfill & {88}\hfill & {c}{}{h}{}{r}{}{i}{}{s}\hfill \\ {c}{}{s}{}{111}\hfill & {2009}\hfill & {j}{}{e}{}{s}{}{s}\hfill & {78}\hfill & {c}{}{h}{}{r}{}{i}{}{s}\hfill \\ {c}{}{s}{}{322}\hfill & {2009}\hfill & {j}{}{o}{}{r}{}{d}{}{a}{}{n}\hfill & {92}\hfill & {y}{}{u}{}{k}{}{i}\hfill \end{array}$
Note how in the join, the information about ${c}{\mathit{}}{s}{\mathit{}}{\mathrm{444}}$ was lost, as there was no TA in that course.