\documentclass[12pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}

\newcommand{\R}{{\sf R\hspace*{-0.9ex}\rule{0.15ex}{1.5ex}\hspace*{0.9ex}}}
\newcommand{\N}{{\sf N\hspace*{-1.0ex}\rule{0.15ex}{1.3ex}\hspace*{1.0ex}}}
\newcommand{\Q}{{\sf Q\hspace*{-1.1ex}\rule{0.15ex}{1.5ex}\hspace*{1.1ex}}}
\newcommand{\C}{{\sf C\hspace*{-0.9ex}\rule{0.15ex}{1.3ex}\hspace*{0.9ex}}}

\title{The Relational Data Model: Fundamental Operations}
\author{}
\date{}

\begin{document}
\maketitle

\section{Overview}

\begin{itemize}
\item Now that we've looked at the structure of a relational database, we will look at its fundamental \emph{operations} --- that is, what you can do with that database.

\item We can think of relational operations on multiple levels:
\begin{itemize}
\item Pure mathematical abstractions: this would be the relational algebra, and if you go non-procedural, you can sort of think of the relational calculus in this manner --- ultimately these form the basis for reasoning about a relational database.

\item Programmatic interaction: when actually interacting with a real live database, we need a programming language --- and many programming languages are geared toward database operation.  These are typically categorized as \emph{query} languages; more formally there are \emph{data manipulation languages} (DMLs) and \emph{data definition languages} (DDLs).
\begin{itemize}
\item A short list of query languages: SQL, QBE, Datalog, ``pure'' languages that attempt to translate the relational algebra or calculus directly
\end{itemize}
\end{itemize}

\item For this handout, we focus on the foundation of it all: the basic operations of the relational algebra.
\end{itemize}

\section{Fundamental Operations}

\begin{itemize}
\item We have seen that a relational database is a set of relations $r$\/, each of which follows a particular relation schema $R$\/.

\item The fundamental operations define what we can do with these relations.  Note that all of these operations take relations as operands and produce relations as results --- this is the mathematical property of \emph{closure}\/.

\item Some of these operations are \emph{unary}\/: they take a single relation as an operand.  Other operations are \emph{binary}\/: they require two relation operands.
\end{itemize}

\subsection{Select}

\begin{itemize}
\item The \emph{select} operation is a unary operation on a relation $r$ that is denoted by the lowercase Greek letter sigma ($\sigma$) and includes a predicate $P$\/.  It is written as:
\[
\sigma_{P}(r)
\]
The select operation results in a new relation consisting only of the tuples $t$ in $r$ for which $P$ is true.

\item $P$ is a boolean expression that refers to attributes in $r$ and compares them either to constant values or other attributes via $=, \neq, <, \leq, >, \geq$\/.

\item Individual comparisons can be combined using logical \emph{and} ($\wedge$), \emph{or} ($\vee$), and \emph{not} ($\neg$).  These operators have the boolean meanings that you probably know and love by now.

\item You can think of the select operation as a form of \emph{horizontal partitioning} of the relation.
\end{itemize}

\subsection{Project}

\begin{itemize}
\item The \emph{project} operation is a unary operation on a relation $r$ that is denoted by uppercase Greek letter pi ($\Pi$) and includes an attribute list $A$\/.  It is written as:
\[
\Pi_{A}(r)
\]
For all tuples $t$ in $r$\/, the project operation results in a new relation consisting of $t[A]$\/.

\item $A$ is written as a comma-separated list of attributes.

\item Remember that relations are sets, so tuples $t_{1}$ and $t_{2}$ that are not equal in $r$ but have the same values for $A$ (that is, $t_{1}[A] = t_{2}[A]$) become a single tuple in $\Pi_{A}(r)$\/.

\item Remember again that the set of all relations is \emph{closed} under these operations; thus, you can \emph{compose} them as needed.  For example, a query on a MMORPG database such as ``Retrieve the names of all players who belong to server \emph{Dethecus}'' can be written as a select followed by a project (assume the relation is named $players$\/):
\[
    \Pi_{player\_name}(\sigma_{server=``Dethecus''}(players))
\]
\end{itemize}

\subsection{Union}

\begin{itemize}
\item The \emph{union} operation is a binary operation on relations $r$ and $s$ that is denoted by the same symbol as in set theory: $\cup$\/.  It is written as:
\[
r \cup s
\]
The result is a new relation such that $\forall$ $t_{r} \in r$ and $t_{s} \in s$\/, $t_{r} \in r \cup s$ and $t_{s} \in r \cup s$\/.

\item We diverge from set theory in that the union of relations only makes sense if they have \emph{compatible} schemas.  Thus, union only applies if all of the following conditions are true:
\begin{itemize}
\item $r$ and $s$ have the same \emph{arity} --- meaning that they have the same number of attributes $n$\/.  Notationally, if $A_{r}$ is the set of $r$\/'s attributes and $A_{s}$ is the set of $s$\/'s attributes, then $|A_{r}| = |A_{s}|$\/.

\item $\forall$ $1 \leq i \leq n$\/, the domain of attribute $i$ in $r$ must be the same as the domain of attribute $i$ in $s$\/.
\end{itemize}

\item Note how the requirements are essentially \emph{number of attributes} and \emph{corresponding domains}\/.  Attribute names aren't involved.
\end{itemize}

\subsection{Set-Difference}

\begin{itemize}
\item The \emph{set-difference} operation is a binary operation on relations $r$ and $s$ that is denoted by $-$\/.  It is written as:
\[
r - s
\]
The result is a new relation consisting of tuples $t$ such that $t \in r$ but $t \notin s$\/.

\item As with union, set-difference only makes sense for compatible relations: same arity, corresponding domains.
\end{itemize}

\subsection{Cartesian-Product}

\begin{itemize}
\item The \emph{Cartesian-product} operation is a binary operation on relations $r_{1}$ and $r_{2}$ that is denoted by $\times$\/.  It is written as:
\[
r_{1} \times r_{2}
\]
If $r_{1}$ has schema $R_{1}$ and $r_{2}$ has schema $R_{2}$ (that is, $r_{1}(R_{1})$ and $r_{2}(R_{2})$\/, $r = r_{1} \times r_{2}$ is a relation whose schema $R$ is the concatenation of $R_{1}$ and $R_{2}$\/.  The resulting relation $r$ contains all tuples $t$ such that $\exists$ $t_{1} \in r_{1}$ and $t_{2} \in r_{2}$ for which $t[R_{1}] = t_{1}[R_{1}]$ and $t[R_{2}] = t_{2}[R_{2}]$\/.

\item When specifying the schema for some $r_{1} \times r_{2}$ in which $r_{1}$ and $r_{2}$ have attributes of the same name, we use \emph{dot notation} to prepend the attribute name with the relation name:
\[
R_{1} = (\mbox{\emph{tom}}, \mbox{\emph{dick}}, \mbox{\emph{harry}})
\]
\[
R_{2} = (\mbox{\emph{harry}}, \mbox{\emph{hausen}})
\]
\[
R = (\mbox{\emph{tom}}, \mbox{\emph{dick}}, r_{1}.\mbox{\emph{harry}}, r_{2}.\mbox{\emph{harry}}, \mbox{\emph{hausen}})
\]

\item We can take the Cartesian product of a relation with itself.  However, we need to distinguish the attributes that came from the first ``instance'' of the relation from those that came from the second ``instance.''  For this, we \emph{rename} one of the operands, then use the same dot notation (see Section~\ref{rename}).

\item It's easy to figure out how many tuples are in $r_{1} \times r_{2}$\/: if $r_{1}$ has $n_{1}$ tuples and $r_{2}$ has $n_{2}$ tuples, then $r_{1} \times r_{2}$ has $n_{1}n_{2}$ tuples.

\item Note how the Cartesian product combines \emph{all} tuples in $r_{1}$ with \emph{all} tuples in $r_{2}$ --- not very useful.  In practice, we perform a select on the Cartesian product, choosing a condition that expresses a meaningful connection between some attribute(s) of $r_{1}$ and $r_{2}$\/:
\[
\sigma_{westplayer.player = eastplayer.player}(westplayer \times eastplayer)
\]
This Cartesian product followed by a select has a name of its own --- it is called a \emph{join}\/.  More on joins later.
\end{itemize}

\subsection{Rename}
\label{rename}

\begin{itemize}
\item Note how, while we start out with a set of named relations in a relational database, by default, the relations that are \emph{results} of relational operators don't have names.  For long sequences of operations, or for binary operations that take the same relations as operands, the \emph{rename} operation presents a solution that eliminates the ambiguity or confusion that may emerge in those situations.

\item The rename operation is denoted by the lowercase Greek letter rho ($\rho$), specifies a new name $x$\/, and accepts any relational expression $E$ as its operand:
\[
\rho_{x}(E)
\]
$E$ is \emph{any} relational expression, so $E$ covers everything from a single named relation to a complex sequence of operations on multiple relations.

\item It is possible to rename not only a relation but also its attributes.  In that case, we can provide an attribute name list $(a_{1}, a_{2}, \ldots , a_{n})$ --- where $n$ is the arity of $E$ --- along with the new relation name $x$\/:
\[
\rho_{x(a_{1}, a_{2}, \ldots , a_{n})}(E)
\]

\item A little footnote --- remember that in the pure mathematical theory of relations, attributes don't have names; they go by number, in the order that they are listed in a relation schema.  We accommodate positions by prepending a \$ sign before the position.  Thus, $\sigma_{\$2 = \$3}(r \times r)$ refers to all tuples in the Cartesian product of $r$ with itself such that the values of the second and third attributes of $r \times r$ are equal.
\begin{itemize}
\item Positional notation eliminates the need to rename, but it's hard for people to read, requiring top-of-your-head knowledge of how attributes are ordered in a schema.  So generally, we don't use positional notation.
\end{itemize}
\end{itemize}

\section{Formal Definition of Relational Algebra}

\begin{itemize}
\item We now have all of the definitions that we need to formally define relational algebra --- specifically, what comprises a valid expression in this algebra.

\item A basic expression in the relational algebra is either:
\begin{itemize}
\item A relation in a database
\item A constant (literal) relation: written as a comma-separated sequence of tuples enclosed in braces \{ \}\/.  The tuples themselves are comma-separated sequences of values, enclosed in parentheses ( ).
\end{itemize}

\item A general expression in the relational algebra is a composition of smaller subexpressions.  If $E_{1}$ and $E_{2}$ are expressions in the relational algebra, then so are these:
\[ E_{1} \cup E_{2} \]
\[ E_{1} - E_{2} \]
\[ E_{1} \times E_{2} \]
\[ \sigma_{P}(E_{1})
\mbox{ where $P$ is a predicate on the attributes of $E_{1}$}
\]
\[ \Pi_{S}(E_{1})
\mbox{ where $S$ is a list of some of the attributes of $E_{1}$}
\]
\[ \rho_{x}(E_{1})
\mbox{ where $x$ is the new name for the result of $E_{1}$}
\]

\item And that's it --- everything that you can do with relations can be decomposed ultimately into the above expressions.

\item While we're being mathematical, think about the other properties involved in an algebra:
\begin{itemize}
\item You've already seen how these operations have \emph{closure} within the set of all relations: for a unary operation $o$ and relation $r$\/, $o(r)$ is a relation, and for a binary operation $\cdot$ and relations $r_{1}$ and $r_{2}$, $r_{1} \cdot r_{2}$ is a relation.

\item Which operations are \emph{associative} --- that is, for a given operation $\cdot$\/, $(r_{1} \cdot r_{2}) \cdot r_{3} = r_{1} \cdot (r_{2} \cdot r_{3})$?

\item Are there \emph{identity elements} for these operations?  That is, for a given operation $\cdot$\/, is there a relation $r_{i}$ such that $r_{i} \cdot r = r$ and $r \cdot r_{i} = r$ $\forall$ relations $r$\/?

\item Are there \emph{inverse elements} in these operations?  That is, for a given operation $\cdot$ and $\forall$ relations $r$\/, is there a relation $r^{-1}$ such that $r \cdot r^{-1} = r_{i}$ and $r^{-1} \cdot r = r_{i}$\/?
\end{itemize}
If a binary relational operation has these properties, then you have a \emph{group} with respect to that operation and the set of all relations!

\item If you take two relational operations, say $+$ and $\cdot$\/, and the following conditions hold for relations:
\begin{itemize}
\item $+$ and $\cdot$ are closed,
\item $+$ and $\cdot$ are associative,
\item $+$ and $\cdot$ are \emph{commutative} --- that is, $r_{1} + r_{2} = r_{2} + r_{1}$ and $r_{1} \cdot r_{2} = r_{2} \cdot r_{1}$\/,
\item $\cdot$ is \emph{distributive} over $+$ --- defined as $r_{1} \cdot (r_{2} + r_{3}) = (r_{1} \cdot r_{2}) + (r_{1} \cdot r_{3})$ and $(r_{1} + r_{2}) \cdot r_{3} = (r_{1} \cdot r_{3}) + (r_{2} \cdot r_{3})$\/,
\item $+$ has an identity element and inverse elements as defined above
\end{itemize}
\ldots~you have a \emph{commutative ring}\/!

\item If the $\cdot$ operation in a commutative ring also has an identity element, then you have a \emph{commutative ring with identity}\/.

\item If the $\cdot$ operation in a ring has inverse elements for every relation except for the relation identified as the identity element for $+$\/, then you have a \emph{field}\/.

\item \emph{Why do you care?}  Once you have identified a group, ring, or field, then that opens a whole slew of known truths about those constructs (theorems, lemmas) --- and in many cases, these truths lead to powerful yet practical algorithms, optimizations, and implementations when you finally start to develop a relational database management system.
\end{itemize}
\end{document}
