\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}}}

\newcommand{\LeftOuterJoin}{\sqsupset\hspace{-0.025in}\bowtie}
\newcommand{\RightOuterJoin}{\bowtie\hspace{-0.025in}\sqsubset}
\newcommand{\FullOuterJoin}{\sqsupset\hspace{-0.025in}\bowtie\hspace{-0.025in}\sqsubset}

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

\begin{document}
\maketitle

\section{Overview}

\begin{itemize}
\item While the fundamental relational algebra operations --- select, project, union, set-difference, cartesian-product, rename --- form the basis for a broad spectrum of relational database queries and manipulations, it remains possible to define other operations over relations.

\item Some operations are just notational shortcuts --- they are completely rewritable in terms of the 6 fundamentals, but for convenience we abstract them into operations of their own.  These are the ``additional operations'' in Section~\ref{additional}\/.

\item On the other hand, the ``classical'' relational algebra itself has been extended with new operations, with new meanings and manipulations.  These are the ``extended operations'' in Section~\ref{extended}.
\end{itemize}

\section{Additional Operations}
\label{additional}

\begin{itemize}
\item ``Additional operations'' refer to relational algebra operations that can be expressed in terms of the fundamentals --- select, project, union, set-difference, cartesian-product, and rename.

\item The compositions of these operations are so lengthy, yet so common, that we define new operations for them, based on the fundamentals.  Kind of a mathematical ``syntactic sugar.''
\end{itemize}

\subsection{Set-Intersection}

\begin{itemize}
\item The \emph{set-intersection} operation is a binary operation on relations $r$ and $s$ that is denoted by the traditional intersection symbol, $\cap$\/.  $r \cap s$ results in all tuples $t$ such that $(t \in r) \wedge (t \in s)$\/.

\item Set-intersection is defined in terms of set-difference:
\[
r \cap s = r - (r - s)
\]

\item Thus, set-intersection must follow the same \emph{compatibility} rules as set-difference: same arity, corresponding domains.
\end{itemize}

\subsection{Natural-Join}

\begin{itemize}
\item The \emph{natural-join} operation is a binary operation on relations $r(R)$ and $s(S)$ that is denoted by the symbol $\bowtie$\/.  Intuitively, a natural-join ``matches'' the tuples of $r$ with the tuples of $s$ based on attributes that are both in $r$ and $s$\/.

\item If we take the relational schemas $R$ and $S$ as sets of attributes, then we can define ``attributes that are in both $r$ and $s$'' as $R \cap S = \{A_{1}, A_{2}, \ldots , A_{n}\}$\/.  With that, we can formally define $r \bowtie s$ as:
\[
r \bowtie s = \Pi_{R\ \cup\ S}(\sigma_{r.A_{1}~=~s.A_{1}\ \wedge\ r.A_{2}~=~s.A_{2}\ \wedge\ \ldots\ \wedge\ r.A_{n}~=~s.A_{n}}(r \times s))
\]

\item Note that $R\ \cup\ S$ removes duplicate attribute names, so $r \bowtie s$ will only have one attribute $A_{k}\ \forall A_{k} \in R \cap S$\/.

\item Natural join is \emph{associative} --- that is, $(a \bowtie b) \bowtie c = a \bowtie (b \bowtie c)$\/.

\item When $r$ and $s$ do not have any common attributes --- i.e., $R \cap S = \emptyset$ --- then $r \bowtie s = r \times s$\/.
\end{itemize}

\subsubsection{Theta Join}

\begin{itemize}
\item One can generalize the natural-join operation into a \emph{theta join}\/, so named because instead of the specific ``attribute-matching'' condition involved in natural-join, we allow $\theta$ to be any predicate on the attributes in $R \cup S$ for $r(R)$ and $s(S)$\/.

\item Thus, we have $r \bowtie_{\theta} s$\/, defined as:
\[
r \bowtie_{\theta} s = \sigma_{\theta}(r \times s)
\]
\end{itemize}

\subsection{Division}

\begin{itemize}
\item The \emph{division} operation is a binary operation, notated as $\div$\/, on relations $r(R)$ and $s(S)$ such that $S \subseteq R$\/.  Intuitively, division is a ``for all'' query --- it returns the tuples in $r$ that ``match'' \emph{all} of the tuples in $s$\/.

\item Formally, $r \div s$ is a relation with schema $R - S$ whose tuples $t$ satisfy both of these conditions:
\begin{enumerate}
\item $t \in \Pi_{R-S}(r)$
\item $\forall\ t_{s} \in s,\ \exists\ t_{r} \in r$ that satisfies both of:
\begin{enumerate}
\item $t_{r}[S] = t_{s}[S]$
\item $t_{r}[R-S] = t$
\end{enumerate}
\end{enumerate}

\item Division can also be defined in terms of the relational algebra.  Again, we start with $r(R)$ and $s(S)$ with $S \subseteq R$\/:
\begin{equation}
\label{division}
r \div s\ =\ \Pi_{R-S}(r)\ -\ \Pi_{R-S}((\Pi_{R-S}(r) \times s) - \Pi_{R-S,S}(r))
\end{equation}

\item This is quite an eyeful, so we break it down like this:
\begin{itemize}
\item First, we take $\Pi_{R-S}(r)$\/.  This defines the relation for the first condition of the formal definition: $t \in \Pi_{R-S}(r)$\/, or the tuples in $r$ with their $s$\/-shared attributes removed.

\item Now, from this, we perform set-difference using:
\[
\Pi_{R-S}((\Pi_{R-S}(r) \times s) - \Pi_{R-S,S}(r))
\]

\item So these tuples are removed from $\Pi_{R-S}(r)$\/.  What are these tuples exactly?  We start with $\Pi_{R-S}(r) \times s$\/: it takes all of the tuples in $r$ and removes any attributes that $r$ shares with $s$\/, then pairs those tuples with \emph{every} tuple in $s$\/.

\item $\Pi_{R-S,S}(r)$ just rearranges the attributes in $r$ so that the attributes that are in $r$ alone are listed first, followed by the attributes that $r$ shares with $s$\/.  This ensures that the relation of the first difference term, $\Pi_{R-S}(r) \times s$\/, is compatible with $\Pi_{R-S,S}(r)$ (same arity, corresponding domains).

\item So, the set-difference operation can take place, and the result would be the $r$\/-to-$s$ tuple matchups that are \emph{not} in $r$\/.

\item If we then remove the $s$ attributes from that relation, resulting in $\Pi_{R-S}((\Pi_{R-S}(r) \times s) - \Pi_{R-S,S}(r))$\/, we now have the tuples in $r$ for which at least one tuple in $s$ does \emph{not} match.  Since $r \div s$ is about tuples in $r$ that have a corresponding match for \emph{all} tuples in $s$\/, then these are precisely the tuples that we \emph{don't} want, and so we subtract them from $\Pi_{R-S}(r)$\/.
\end{itemize}

\item Phew!  When all is said and done, just remember that division, $r \div s$\/, is all about ``for all'' --- tuples in $r$ that match \emph{all} tuples in $s$\/.
\end{itemize}

\subsection{Assignment}

\begin{itemize}
\item You've probably gotten a sense, particularly with division, that relational algebra feels a lot like programming: there are many steps to some expressions, with intermediate or temporary relations along the way.

\item For this very reason, we have the \emph{assignment} operation, which works a lot like assignments in a programming language.  It is notated with the left-pointing arrow $\gets$\/:
\[
variable \gets E
\]
where $E$ is any relational algebra expression.

\item The assignment operation is more of a notational convenience rather than a real relational operation --- it helps human beings with writing out complex relational expressions in steps so that they can be more easily understood.

\item Revisiting the breakdown of the division operation, we can use assignment to rewrite (\ref{division}) this way:
\[
temp1 \gets \Pi_{R-S}(r)
\]
\[
temp2 \gets \Pi_{R-S}((temp1 \times s) - \Pi_{R-S,S}(r))
\]
\[
r \div s = temp1 - temp2
\]
\end{itemize}

\section{Extended Operations}
\label{extended}

\begin{itemize}
\item In this section, we discuss ``extended'' operations --- new operations that introduce new concepts beyond what can be built from the fundamental relational operations.

\item While they are technically ``extensions'' to the algebra, they still follow the mathematical rigor and precision that allow us to draw sweeping and powerful conclusions from simpler concepts.
\end{itemize}

\subsection{Generalized Projection}

\begin{itemize}
\item The \emph{generalized-projection} operation extends the fundamental projection operation by allowing arithmetic (or, in the most general case, overall transformative) functions in the projection's attribute list.  It is still denoted with $\Pi$\/, but now the straight-up attribute list $A$ has changed into an expression list $F_{1}, F_{2}, \ldots\ , F_{n}$\/:
\[
\Pi_{F_{1}, F_{2}, \ldots\ , F_{n}}(E)
\]
$E$ is any relational algebra expression, which is of course a relation.  $F_{k}$ may be any expression involving constant values and the attributes of $E$\/'s resultant relation schema.

\item By default, new attributes resulting from evaluating $F_{k}$ have no name.  We can use the fundamental rename operation to give it a name:
\[
\rho_{x(a_{1}, a_{2}, \ldots , a_{n})}(\Pi_{F_{1}, F_{2}, \ldots\ , F_{n}}(E))
\]

\item \ldots~but that can be too verbose or redundant, so as a notational convenience, we can prepend an \emph{as new\_name} suffix to $F_{k}$\/:
\[
\Pi_{F_{1}\ as\ a_{1}, F_{2}\ as\ a_{2},\ \ldots\ , F_{n}\ as\ a_{n}}(E)
\]

\item Note how generalized projection doesn't add a completely new operation per se --- it just adds new functionality to the fundamental projection operation.
\end{itemize}

\subsection{Aggregate Functions}

\begin{itemize}
\item An \emph{aggregate function} takes a collection of values and returns a single value as its result.  Examples of aggregate functions include:
\begin{description}
\item[sum] takes a collection of numerical values and adds them up.
\item[avg] also takes a collection of numerical values and returns their mean.
\item[count] returns how many items are in a given collection.
\item[min] returns the minimum value in a collection.
\item[max] returns the maximum value in a collection.
\end{description}

\item Of course one can define all kinds of other possible aggregate functions --- median and standard deviation come to mind.

\item Note how we say \emph{collection} of values, not a \emph{set}\/; this is a deliberate choice, because an individual value may occur multiple times within that collection.  However, as with sets, the order in which values appear does not matter.  This type of collection is formally known as a \emph{multiset}\/.

\begin{itemize}
\item Sometimes, you \emph{do} want the aggregate function to ignore duplicates --- for instance if you want to count the number of individual values in a relation.  In this case, the suffix \emph{-distinct} may be used to indicate that the aggregate function removes duplicates before performing its calculation.  This is primarily a notational convenience; for all intents and purposes, \emph{count} and \emph{count-distinct} are just different aggregate functions, the way \emph{sum} is different from \emph{avg}\/.
\end{itemize}

\item An aggregate function is notated using a ``calligraphic G:'' $\mathcal{G}_{F(A)}$\/.  The subscript $F(A)$ represents the specific aggregate function $F$ to be applied, along with the attribute $A$ on which to perform the function:
\begin{equation}
\label{aggregate}
\mathcal{G}_{F(A)}(E)
\end{equation}
As before, $E$ represents any relational algebra expression, and of course, $A$ is part of $E$\/'s list of attributes.

\item A frequent aggregate function parameter is the attribute in $E$ over which the aggregate function is to be applied.  For instance, in a relation containing cities and their populations, the total population would be written as:
\[
\mathcal{G}_{sum(population)}(city)
\]

\item The result of $\mathcal{G}_{F(A)}(E)$ is a relation with a single attribute, containing a single tuple that holds the result of the aggregate function.
\end{itemize}

\subsubsection{Groups}

\begin{itemize}
\item The expression in (\ref{aggregate}) performs the aggregate function over the entire relation represented by $E$\/.  Sometimes, we want to perform the aggregation multiple times over separate sets of tuples in $E$\/.  These separate sets are called \emph{groups}.

\item Typically, groups are specified as a list of attributes $G_{1}, G_{2},\ \ldots\ , G_{n}$\/, meaning that, for a given relation, tuples should first be ``clustered'' into partitions such that these tuples share the same values for $G_{1}, G_{2},\ \ldots\ , G_{n}$\/.  The aggregate function should then be applied to each cluster:
\[
_{G_{1}, G_{2},\ \ldots\ , G_{n}}\mathcal{G}_{F(A)}(E)
\]

\item With groups, the resulting aggregate relation would have as many tuples as there were groups in the original, partitioned relation.
\end{itemize}

\subsubsection{General Form of the Aggregation Operation}

\begin{itemize}
\item As a final extension, we note that we can perform more than one aggregate function $F_{i}(A_{i})$ over the groups in a relational algebra expression.  Thus, the general form of the \emph{aggregation} operation is:
\[
_{G_{1}, G_{2},\ \ldots\ , G_{n}}\mathcal{G}_{F_{1}(A_{1}), F_{2}(A_{2}),\ \ldots\ , F_{m}(A_{m})}(E)
\]

\item The resulting relation in an aggregation operation has a schema consisting of the attributes $G_{1}, G_{2},\ \ldots\ , G_{n}$ plus one attribute for each aggregate function $F_{i}$\/.  A tuple in this relation has the form $(g_{1}, g_{2},\ \ldots\ , g_{n}, a_{1}, a_{2}\ \ldots\ , a_{m})$ where each $a_{i}$\/, $1 \leq i \leq m$\/, is the result of $F_{i}(A_{i})$ applied to the multiset defined by the group $(g_{1}, g_{2},\ \ldots\ , g_{n})$\/.
\end{itemize}

\subsection{Outer Join}

\begin{itemize}
\item In a perfect world, we would have data for everyone and everything, and all relations would be complete in terms of their data and data that refers to other relations.  In that perfect world, natural join ($\bowtie$) pretty much takes care of our relation-connection needs.

\item But it isn't a perfect world.  One thing that natural join does, by its own definition, is drop any tuples from either relation that does not match a tuple from the other relation (i.e., no shared attributes with the same values).  In some cases, this is appropriate, but in others, we don't want to lose data.

\item Enter the \emph{outer join}\/.  An outer-join operation does the same thing as natural join, except that it \emph{preserves} tuples without a match in the other relation.  The tuple that does not have a match uses $null$ values to populate the attributes from the second relation.

\item There are three types of outer join, based on which non-matching tuples ``stick around'' after the operation:
\begin{itemize}
\item \emph{Left outer join}\/, written as $r \LeftOuterJoin s$\/, keeps the non-matching tuples in $r$ and uses $null$ values for the attributes that come from $s$\/.

\item \emph{Right outer join}\/, written as $r \RightOuterJoin s$\/, keeps the non-matching tuples in $s$ and uses $null$ values for the attributes that come from $r$\/.

\item \emph{Full outer join}\/, written as $r \FullOuterJoin s$\/, keeps the non-matching tuples from both $r$ and $s$\/, and uses $null$ values for the attributes that come from the ``other'' relation.
\end{itemize}

\item Fun fact: outer join is actually expressible in terms of the fundamental relational operations.  For example, left outer join can be rewritten as:
\[
r \LeftOuterJoin s = (r \bowtie s) \cup ((r - \Pi_{R}(r \bowtie s)) \times \{(null,\ \ldots\ , null)\})
\]
Here, $\{(null,\ \ldots\ , null)\}$ is a constant (literal), single-tuple relation with schema $S - R$\/.

\item Can you see how the other outer joins can be rewritten in terms of the more fundamental operations (hint hint)?
%\[
%r \RightOuterJoin s = (r \bowtie s) \cup (\{(null,\ \ldots\ , null)\} \times (s - \Pi_{R}(r \bowtie s)))
%\]
%Here, $\{(null,\ \ldots\ , null)\}$ is a constant (literal), single-tuple relation with schema $R - S$\/.
%\[
%r \FullOuterJoin s = (r \LeftOuterJoin s) \cup (r \RightOuterJoin s)
%\]
\end{itemize}

\subsection{Null Values}

\begin{itemize}
\item The outer-join operations bring the notion of $null$ values into the relational algebra.  How does one deal with such values formally?

\item In reality, there are a lot of plausible approaches for handling $null$\/.  If we stick to the definition of $null$ as an \emph{unknown or non-existent value}\/, we can establish the following:
\begin{itemize}
\item Any arithmetic operations involving $null$ must return $null$\/.

\item Comparing anything to $null$ really doesn't have much meaning, so we create a new ``boolean value'' in this case --- $unknown$\/, meaning that we really can't say whether a comparison to $null$ is true or false.

\item By defining the new boolean value $unknown$\/, we need to determine how $unknown$ interacts with the other boolean values, \emph{true} and \emph{false}\/, in terms of the boolean operations $\wedge$\/, $\vee$\/, and $\neg$\/.  These definitions are actually fairly intuitive, if you think about it:
\[
true \wedge unknown = unknown
\]
\[
false \wedge unknown = false
\]
\[
unknown \wedge unknown = unknown
\]
\[
true \vee unknown = true
\]
\[
false \vee unknown = unknown
\]
\[
unknown \vee unknown = unknown
\]
\[
\neg unknown = unknown
\]
\end{itemize}

\item With the effect of $null$ defined at the value level, we then consider how $null$ (and its sister value $unknown$\/) should affect relational operations:
\begin{description}
\item[select] When $P$ in $\sigma_{P}(E)$ is $unknown$ for a particular tuple, then the tuple does not get included in the result.

\item[join] Because joins (natural, outer) come down to a selection on a Cartesian product, then the behavior of the select operation determines the behavior of the joins.  Essentially, since all comparisons against $null$ are $unknown$\/, then tuples with $null$ values in the common attributes won't be included in the join result.

\item[project] The main issue with $null$ and projection is what to do with potentially duplicate tuples --- that is, are tuples with the same non-null attributes, and with $null$ everywhere else, to be considered as duplicates and therefore ``unified'' in the projection result?  In this case, we say yes: tuples with the same non-null attributes and nulls everywhere else \emph{are} duplicates, and so only one of these tuples gets included in the projection.

\item[union, intersection, difference] We apply the same $null$ handling with these operations as we did with projection, since this was based on the premise of not having duplicates in a set.

\item[generalized projection] Calculated or derived attributes follow the above guidelines for calculations when $null$ is involved; otherwise this is just like ``standard'' projection.

\item[aggregation] Same logic as with projection: tuples with matching $null$ and non-null values in the same grouping attributes will end up in their own group.

However, instead of propagating $null$ in the actual aggregate function calculations, we choose to remove them from the multiset before applying the aggregate function.  After all, it wouldn't make sense to say that the count of a particular attribute in a relation is $null$ just because one of its tuples has a $null$ in that attribute.
\end{description}
\end{itemize}

\section{Modification of the Database}

\begin{itemize}
\item So far, all of the operations that we have discussed ``derive'' new relations from others, but don't actually modify or alter the original relations.

\item How does one specify operations that \emph{change} relations ``in place?''

\item The general guideline is to use the assignment operator, but to make assignments to \emph{existing} relations instead of designating new temporary variables.
\end{itemize}

\subsection{Deletion}

\begin{itemize}
\item Deletion of tuples is effectively a set-difference operation that is ``permanent.''  Thus, we can write deletion as:
\[
r \gets r - E
\]
$E$ in this case is any relational algebra expression that determines the tuples that are to be removed from $r$\/.
\end{itemize}

\subsection{Insertion}

\begin{itemize}
\item Similarly to deletion, insertion of tuples can be viewed as a union operation that is made permanent.  Thus, insertion is:
\[
r \gets r \cup E
\]
$E$ once more is a relational algebra expression that determines the tuples to be set-unioned with (thus ``inserted into'') $r$\/.

\item Note how this definition includes plain old data loading without any problems --- in that case, $E$ is simply a constant or literal relation.
\end{itemize}

\subsection{Updating}

\begin{itemize}
\item An \emph{update} modification changes one or more values \emph{within} a tuple.  Once more, we find that updating is just a persistent version of another relational operation, this time generalized projection:
\[
r \gets \Pi_{F_{1}, F_{2},\ \ldots\ , F_{n}}(r)
\]

\item Specifically, the function $F_{i}$ may be just the $i$\/th attribute of $r$ if it doesn't need to be updated, or otherwise an expression involving constants and the attributes of $r$ if the $i$\/th attribute is involved in the update.

\item The schema of the generalized-projection operation must also match the current schema of $r$\/, so in all likelihood we will perform attribute-level renames to ensure this match.

\item Of course, performing the generalized projection on $r$ will modify all tuples in $r$\/, which isn't always what we want.  To update only the tuples in $r$ that satisfy a predicate $P$\/, we say:
\[
r \gets \Pi_{F_{1}, F_{2},\ \ldots\ , F_{n}}(\sigma_{P}(r)) \cup (r - \sigma_{P}(r))
\]
This restricts the generalized-projection operation only to the tuples for which $P$ is true, then includes all other untouched tuples.
\end{itemize}

\end{document}
