\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: Structure}
\author{}
\date{}

\begin{document}
\maketitle

\section{Overview}

\begin{itemize}
\item By far the most likely data model in which you'll implement a database application today.

\item Of historical interest: the relational model is not the first implementation data model.  Prior to that were the network data model, exemplified by CODASYL, and the hierarchical model, implemented by IBM's IMS.

\item Also of historical interest: when object-oriented programming gained prominence, there were many attempts to replace a relational database with an \emph{object database}\/, but generally they did not fare well.  Today, object-oriented concepts co-exist with underlying relational databases through \emph{object-relational mapping} algorithms.

\item Salient features of the relational model:
\begin{itemize}
\item Conceptually simple; the fundamentals are intuitive and easy to pick up.

\item Powerful underlying theory: the relational model is the only database model that is powered by formal mathematics, which results in excellent dividends when developing database algorithms and techniques.

\item Easy-to-use database language: though not formally part of the relational model, part of its success is due to SQL, the de facto language for working with relational databases.
\end{itemize}
\end{itemize}

\section{Structure}

\begin{itemize}
\item A relational database is a collection of \emph{tables}\/.

\begin{itemize}
\item Each table has a unique name.
\item Each table consists of multiple \emph{rows}\/.
\item Each row is a set of values that by definition are \emph{related} to each other in some way; these values conform to the \emph{attributes} or \emph{columns} of the table.
\item Each attribute of a table defines a set of permitted values for that attribute; this set of permitted set is the \emph{domain} of that attribute.
\end{itemize}

\item This definition of a database table originates from the pure mathematical concept of a \emph{relation}\/, from which the term ``relational data model'' originates.

\begin{itemize}
\item Formally, for a table $r$ with $n$ attributes $a_{1}~\ldots~a_{n}$, each attribute $a_{k}$ has a domain $D_{k}$, and any given row of $r$ is an $n$-tuple $(v_{1},~\ldots~, v_{n})$ such that $v_{k} \in D_{k}$\/.

\item Thus, any instance of table $r$ is a subset of the Cartesian product $D_{1} \times \cdots \times D_{n}$\/.

\item We require that a domain $D_{k}$ be \emph{atomic} --- that is, we do not consider the elements of $D_{k}$ to be breakable into subcomponents.

\item A possible member of any domain is \emph{null} --- that is, an unknown or non-existent value; in practice, we try to avoid the inclusion of \emph{null} in our databases because they can cause a number of practical issues.
\end{itemize}

\item This definition is virtually identical to the pure mathematical definition of a relation --- the main difference is that, for a database, we assign names to the table's attributes, where mathematical relations only label their attributes by their integer indices $1~\ldots~n$\/.

\item To avoid jargon proliferation, we will stick with the more formal terms ``relation'' for table and ``tuple'' for row --- which is why we used $r$ to represent a table above instead of $t$\/.

\item More notation:

\begin{itemize}
\item Given a tuple $t$ that belongs to a relation $r$\/, we can say that $t \in R$ since after all $r$ is a set of tuples.

\begin{itemize}
\item By ``set of tuples'' we do mean the mathematical concept of a set; thus order doesn't matter.

\item Two relations $r$ and $s$ are the same as long as they have the same attributes $a_{1}~\ldots~a_{n}$ with domains $D_{1}~\ldots~D_{n}$ and contain as elements the same tuples with the same values, regardless of the order in which these tuples appear.
\end{itemize}

\item To talk about a specific attribute $a_{k}$ of $t$, we write $t[a_{k}]$\/.

\item This notation also applies to a set of attributes $A$ --- the notation $t[A]$ refers to the ``sub-tuple'' of $t$ consisting only of the attributes in $A$\/.

\item Alternatively, $t[k]$ can refer to that same attribute of $t$\/, as long as we are consistent about how attributes are ordered in the relation.
\end{itemize}
\end{itemize}

\subsection{Schemas and Instances}

\begin{itemize}
\item Just as with classes and instances in the object-oriented world, a similar dichotomy exists between a \emph{database schema} and a \emph{database instance}\/.
\begin{itemize}
\item The \emph{schema} refers to the database's design or definition --- what relations it contains, what attributes these relations have, and to what domains these attributes belong.

\item An \emph{instance} of the database is a specific snapshot of the data in that database at a given point in time.
\end{itemize}

\item Ditto with \emph{relation schemas} --- lists of attributes and their corresponding domains --- and \emph{relation instances}\/.
\begin{itemize}
\item The SKS convention is to use names with an initial uppercase letter to represent a relation schema, and all-lowercase for a relation instance (or, simply, a relation).

\item The notation $r(R\_schema)$ indicates that the relation $r$ conforms to a schema $R\_schema$\/.
\end{itemize}
\end{itemize}

\subsection{Keys: Super, Candidate, Primary, Foreign}

\begin{itemize}
\item Since a tuple $t$ is completely defined by its values $(v_{1}~\ldots~v_{n})$\/, there is no way to differentiate between $t = (v_{1}~\ldots~v_{n})$ and $t' = (v'_{1}~\ldots~v'_{n})$ if $v_{k} = v'_{k}$ $\forall$ $1 \leq k \leq n$\/.  In the relational model, two such tuples are one and the same.

\item Thus, we need a value-based way for differentiating tuples in a relation.  Values or sets of values that distinguish one tuple from another are called \emph{keys}\/.

\item A \emph{superkey} is a set of one or more attributes that uniquely identify a tuple in a relation.  The superkey can range from a single attribute, if no two tuples will ever have the same value for that attribute, to the entire tuple.  As long as the set of attributes will distinguish tuples from each other, then it is a superkey.
\begin{itemize}
\item Thus, if $K$ is a superkey, then any superset of $K$ up to the entire attribute set is also a superkey.

\item More formally, if $R$ is a relation schema, then a subset $K$ of $R$ is a superkey for $R$ if, for a relation $r(R)$ and tuples $t_{1}$ and $t_{2}$ in $r$\/, $t_{1} \neq t_{2}$ $\rightarrow$ $t_{1}[K] \neq t_{2}[K]$\/.

\item In practice, a superkey is not very useful; we need a stricter definition for a key, which is\dots
\end{itemize}

\item A \emph{candidate key} is a ``minimal superkey'' --- it is a superkey for which no proper subset is also a superkey.
\begin{itemize}
\item Note that there can still be more than one candidate key for a relation, consisting of different subsets of attributes whose combined values will be unique for all tuples.
\end{itemize}

\item So we finally narrow things down to the \emph{primary key}\/: the primary key is a candidate key that has been chosen by the database designer as the principal means for identifying tuples in a relation.

\item One of the key guidelines (ha!  no pun intended, I think\ldots) that makes a candidate key particularly suited for elevation to the status of ``the one'' primary key is that the value of the candidate key should never, or very rarely, change.

\item Say you have two relation schemas $R_{1}$ and $R_{2}$ and these schemas share some subset of attributes.  If $K_{p}$ is the primary key of $R_{2}$ and $K_{p} \subseteq R_{1}$ as well --- in other words, $R_{1}$\/'s attributes include the primary key of $R_{2}$ --- then $K_{p}$ is a \emph{foreign key} from $R_{1}$ referencing $R_{2}$\/.
\begin{itemize}
\item $R_{1}$\/, the relation that contains the foreign key, is the \emph{referencing relation}\/.

\item $R_{2}$\/, the relation for which $K_{p}$ is a primary key, is the \emph{referenced relation}\/.

\item In practice, specifying a foreign key places a \emph{constraint} on the data that any $r_{1}(R_{1})$ and $r_{2}(R_{2})$ may contain: that is, $\forall$ tuples $t_{1} \in r_{1}$\/, there \emph{must} be a tuple $t_{2} \in r_{2}$ such that $t_{1}[P_{k}] = t_{2}[P_{k}]$\/.

\item Quick --- clearly there is only one such tuple $t_{2}$\/.  Why? 
\end{itemize}
\end{itemize}

\section{Relational Schema Diagram Notation}

\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=6in]{SampleRelationalSchemaDiagram.pdf} 
   \caption{Sample relational schema diagram for our sample document management database application.}
   \label{sampleSchemaDiagram}
\end{figure}

\begin{itemize}
\item A relational database schema can be depicted pictorially through a \emph{relational schema diagram}\/.  Yes, it's yet another notation like E-R and UML, but this notation is very focused and specific to the relational data model:
\begin{itemize}
\item Relations are drawn as boxes with the relation name above the box.
\item A relation's attributes are listed within its box.
\item The attributes that belong to the relation's primary key (if it has one) are listed first, with a line separating this primary key from the other attributes and their background shaded in gray.
\item Foreign key dependencies are illustrated as arrows from the foreign key attributes of the referencing relation to the primary key attributes of the referenced relation.
\end{itemize}

\item Figure~\ref{sampleSchemaDiagram} illustrates a possible relational schema diagram for our sample document management database application, with the \emph{id} attribute for each class serving as the primary key for the corresponding table and foreign key attributes added to represent the associations between classes.

\item Note how we have added another relation to represent the association between documents and keywords --- this is a standard technique for expressing a many-to-many relationship in terms of the relational data model.

\item How about a 1-to-many relationship --- can you see from the diagram how that kind of relationship gets mapped to the relational model?
\end{itemize}

\end{document}
