foundations of computational agents
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.