diff --git a/Presentation/View_Updating.tex b/Presentation/View_Updating.tex new file mode 100644 index 0000000..12db2a6 --- /dev/null +++ b/Presentation/View_Updating.tex @@ -0,0 +1,1829 @@ +\documentclass{beamer} + + +\usepackage[no-math]{fontspec} +\usepackage{xunicode} +\usepackage{xltxtra} +\usepackage{bm} +\usepackage{tikz} +\usepackage{graphicx} +\usepackage{relalg} +\usepackage{booktabs} +\usepackage{mathtools} +\usepackage{hyperref} + + +% Beamer setup +\usefonttheme{structurebold} +\useinnertheme{rectangles} +\usenavigationsymbolstemplate{} +\setbeamertemplate{footline}[frame number] + + +% TikZ setup +\usetikzlibrary{positioning} +\usetikzlibrary{graphs} +\usetikzlibrary{decorations.pathreplacing} +\usetikzlibrary{calc} +\usetikzlibrary{arrows} + + +% fontspec setup +\defaultfontfeatures{Mapping=tex-text} +\setmainfont{Minion Pro} +\setsansfont[Scale=MatchUppercase,BoldFont={Open Sans}]{Open Sans Light} +\setmonofont[Scale=MatchLowercase]{Letter Gothic 12 Pitch} + + +% graphicx setup +\graphicspath{{images/}} + + +% custom macros +% "empty" arrow tip +\pgfarrowsdeclare{:}{:}{}{} +% custom bar arrow tip, offset from end of line (use "empty" tip at line ends if no >) +\tikzset{crossbar/.tip={|[scale width=1.75,sep=0.25em]}} +% various edge styles for TikZ +\tikzset{ + function/.style={arrows={->}}, + injection/.style={arrows={<-}}, + total/.style={arrows={:{crossbar}-}}, + surjection/.style={arrows={-{crossbar}:}}, + bijection/.style={arrows={<{crossbar}-{crossbar}>}}, + projection/.style={arrows={:{crossbar}-{crossbar}>}}, + projection left/.style={arrows={:{crossbar}-{crossbar}>},edge label={\scriptsize\(\RelProject\)}}, + projection right/.style={arrows={:{crossbar}-{crossbar}>},edge label'={\scriptsize\(\RelProject\)}}, + selection left/.style={arrows={<-{crossbar}>},edge label={\scriptsize\(\RelRestrict\)}}, + selection right/.style={arrows={<-{crossbar}>},edge label'={\scriptsize\(\RelRestrict\)}}, + funcdep left/.style={arrows={:{crossbar}-{crossbar}>},edge node={node[sloped,midway,above] {\scriptsize\emph{key}}}}, + funcdep right/.style={arrows={:{crossbar}-{crossbar}>},edge node={node[sloped,midway,below] {\scriptsize\emph{key}}}}, + surtotal/.style={arrows={:{crossbar}-{crossbar}:}}, + input keep/.style={structure,thick}, + input delete/.style={structure!40,thick,dashed}, + output/.style={alert,thick}, + output temp/.style={alert,thick,dashed}, + path 1/.style={green!60!black,thick}, + path 2/.style={orange,thick}, + invisible/.style={opacity=0}, + visible on/.style={alt=#1{}{invisible}}, + input on/.style={alt=#1{input keep}{}}, + output on/.style={alt=#1{output}{}}, + alt/.code args={<#1>#2#3}{\alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}}} +} + +% projection and selection edge annotations for TikZ +\newcommand{\ProjectionAnnotation}[3][]{% + \path (#2) to node[above,#1] {\scriptsize\(\RelProject\)} (#3);% +} +\newcommand{\SelectionAnnotation}[3][]{% + \path (#2) to node[above,#1] {\scriptsize\(\RelRestrict\)} (#3);% +} + + +\newcounter{constraint} + +% misc +\newcommand{\todo}[1]{\textbf{!!TODO!!} {[#1]}} + +% commonly used elements +\newcommand{\identifier}[1]{\ensuremath{\mathit{#1}}} +\newcommand{\LS}{\identifier{LS}} +\newcommand{\NLS}{\identifier{NLS}} +\newcommand{\LSsub}{\identifier{L}} +\newcommand{\NLSsub}{\identifier{N}} +\newcommand{\ST}{\identifier{ST}} +\newcommand{\SC}{\identifier{SC}} +\newcommand{\STsub}{\identifier{T}} +\newcommand{\SCsub}{\identifier{C}} +\newcommand{\TC}{\identifier{TC}} +\newcommand{\TCsub}{\identifier{C}} +\newcommand{\Sno}{\identifier{Sno}} +\newcommand{\Sname}{\identifier{Sname}} +\newcommand{\Status}{\identifier{Status}} +\newcommand{\City}{\identifier{City}} + +\newcommand{\Type}[1]{\ensuremath{T_{#1}}} +\newcommand{\TT}[1]{\ensuremath{T_{\{#1\}}}} + +\newcommand{\CityLondon}{\ensuremath{\{\City\colon\allowbreak\text{`\emph{London}'}\}}} +\newcommand{\TCityMinusLondon}{\ensuremath{\Type{\City} \setminus \CityLondon}} +\newcommand{\TSSC}{\ensuremath{\Type{\Sname} \times \Type{\Status} \times \Type{\City}}} +\newcommand{\TSSL}{\ensuremath{\Type{\Sname} \times \Type{\Status} \times \CityLondon}} +\newcommand{\TSSNL}{\ensuremath{\Type{\Sname} \times \Type{\Status} \times (\TCityMinusLondon)}} + +\newcommand{\TLSPlusNLS}{\ensuremath{\Type{\LS} + \Type{\NLS}}} +\newcommand{\TTLSPlusNLS}{\ensuremath{\TT{\LS} + \TT{\NLS}}} +\newcommand{\TLSPlusNLSsub}{\ensuremath{\Type{\LSsub} + \Type{\NLSsub}}} +\newcommand{\TTLSPlusNLSsub}{\ensuremath{\TT{\LSsub} + \TT{\NLSsub}}} + +\newcommand{\StackTLSPlusNLS}{\ensuremath{\begin{array}{c}\Type{\LS}\,+ \\ \Type{\NLS}\end{array}}} +\newcommand{\StackTTLSPlusNLS}{\ensuremath{\begin{array}{c}\TT{\LS}\,+ \\ \TT{\NLS}\end{array}}} +\newcommand{\StackTLSPlusNLSsub}{\ensuremath{\begin{array}{c}\Type{\LSsub}\,+ \\ \Type{\NLSsub}\end{array}}} +\newcommand{\StackTTLSPlusNLSsub}{\ensuremath{\begin{array}{c}\TT{\LSsub}\,+ \\ \TT{\NLSsub}\end{array}}} +\newcommand{\StackTSSC}{\ensuremath{\begin{array}{c}\Type{\Sname}\,\times \\ \Type{\Status} \times \Type{\City}\end{array}}} +\newcommand{\StackTSSL}{\ensuremath{\begin{array}{c}\Type{\Sname} \times \Type{\Status}\,\times \\ \CityLondon\end{array}}} +\newcommand{\StackTSSNL}{\ensuremath{\begin{array}{c}\Type{\Sname} \times \Type{\Status}\,\times \\ (\TCityMinusLondon)\end{array}}} +\newcommand{\StackTCityMinusLondon}{\ensuremath{\begin{array}{c}\Type{\City}\,\setminus \\ \CityLondon\end{array}}} + +\newcommand{\schema}[1]{\ensuremath{\mathcal{S}_{#1}}} + +% dominates +\newcommand{\Dominates}[2]{\ensuremath{#2 \preceq #1}} +\newcommand{\Equivalent}[2]{\ensuremath{#1 \equiv #2}} + +% SIG notation (in text) +\newcommand{\Sedge}[1]{\ensuremath{\sigma_{\textrm{#1}}}} +\newcommand{\SedgeP}[1]{\ensuremath{\sigma_{\textrm{#1}}^{'}}} + +\newcommand{\medmid}{\raise.125ex\hbox{\scalebox{1}[0.75]{$\mid$}}} + +% General SIG edges for use in formulas. +% Adapted from: http://tex.stackexchange.com/questions/96330/adding-symbols-at-the-ends-of-a-horizontal-line +\makeatletter +\newlength{\@annotskipleft} +\newlength{\@annotskipright} +% #1 = left edge component +% #2 = right edge component +% #3 = left bar annotation +% #4 = right bar annotation +\newcommand\@sig@edge[4]{% + \let\@middle\joinrel% + \ifx#1\relbar% + \@annotskipleft=.3em% + % scrunch up the bare line so it's similar length to \long...arrow + \ifx#2\relbar\def\@middle{\joinrel\joinrel\relbar\joinrel\joinrel}\fi% + \else% + % arrows need a little more clearance + \@annotskipleft=.4em% + \fi% + \ifx#2\relbar\@annotskipright=.3em\else\@annotskipright=.4em\fi% + \mathrel{\ooalign{$#1\@middle#2$\cr\hskip\@annotskipleft$#3$\hfil$#4$\hskip\@annotskipright\cr}}% +} + +% 0 = nothing +% 1 = bar +% 2 = arrowhead +% 3 = both +\def\@sigedge#1#2{% + \ifcase\numexpr#1*4+#2\relax% + \@sig@edge{\relbar}{\relbar}{}{}\or % 00 = ----- + \@sig@edge{\relbar}{\relbar}{}{\medmid}\or % 01 = ---+- + \@sig@edge{\relbar}{\rightarrow}{}{}\or % 02 = ----> + \@sig@edge{\relbar}{\rightarrow}{}{\medmid}\or % 03 = ---+> + \@sig@edge{\relbar}{\relbar}{\medmid}{}\or % 10 = -+--- + \@sig@edge{\relbar}{\relbar}{\medmid}{\medmid}\or % 11 = -+-+- + \@sig@edge{\relbar}{\rightarrow}{\medmid}{}\or % 12 = -+--> + \@sig@edge{\relbar}{\rightarrow}{\medmid}{\medmid}\or % 13 = -+-+> + \@sig@edge{\leftarrow}{\relbar}{}{}\or % 20 = <---- + \@sig@edge{\leftarrow}{\relbar}{}{\medmid}\or % 21 = <--+- + \@sig@edge{\leftarrow}{\rightarrow}{}{}\or % 22 = <---> + \@sig@edge{\leftarrow}{\rightarrow}{}{\medmid}\or % 23 = <--+> + \@sig@edge{\leftarrow}{\relbar}{\medmid}{}\or % 30 = <+--- + \@sig@edge{\leftarrow}{\relbar}{\medmid}{\medmid}\or % 31 = <+-+- + \@sig@edge{\leftarrow}{\rightarrow}{\medmid}{}\or % 32 = <+--> + \@sig@edge{\leftarrow}{\rightarrow}{\medmid}{\medmid} % 33 = <+-+> + \fi% +} + +\newcommand{\sigedge}[1]{\ensuremath{\@sigedge#1}} +\makeatother + +\newcommand{\Edge}{\sigedge{00}} +\newcommand{\Total}{\sigedge{10}} +\newcommand{\Surjective}{\sigedge{01}} +\newcommand{\SurTotal}{\sigedge{11}} +\newcommand{\Functional}{\sigedge{02}} +\newcommand{\Injective}{\sigedge{20}} +\newcommand{\Bijective}{\sigedge{33}} + +% Hack to get the overset symbols to appear at the right height. +% \smash removes the spacing around the operator, hence \mathop. +\newcommand{\LabelledEdge}[2]{\mathop{\overset{\raisebox{0.3em}{\scriptsize\ensuremath{#2}}}{\smash[t]{#1}}}} +\newcommand{\ProjectionEdge}{\LabelledEdge{\sigedge{13}}{\RelProject}} +\newcommand{\SelectionEdge}{\LabelledEdge{\sigedge{23}}{\RelRestrict}} +\newcommand{\TrivialProjection}{\ensuremath{\LabelledEdge{\Bijective}{\RelProject}}} +\newcommand{\TrivialSelection}{\ensuremath{\LabelledEdge{\Bijective}{\RelRestrict}}} +\newcommand{\KeyEdge}{\ensuremath{\LabelledEdge{\sigedge{13}}{\mathit{key}}}} + +% Constraints. +\newcommand{\Constraint}[2][]{C\ensuremath{_{#2}\ifx&\else^{#1}\fi}} +\newenvironment{ConstraintList}[1][]{% + \begin{list}{% + \bfseries% + \ifx&% + \Constraint{\ensuremath{\bm{\arabic{constraint}}}}% + \else% + \Constraint[\ensuremath{\bm{#1}}]{\ensuremath{\bm{\arabic{constraint}}}}% + \fi% + }% + {\usecounter{constraint}}% +}{\end{list}} + + +% Draw a grid to aid TikZ picture drawing/debugging. +\newcommand{\DrawGridTikZ}[2]{% + \begin{scope}[color=lightgray] + \draw[thin,step=1mm] (0.0,0.0) grid (#1,#2);% + \draw[thick,step=1cm] (-0.1,-0.1) grid (#1+0.1,#2+0.1);% + \pgftext[top,at={\pgfxy(0.0,-0.2)}]{\tiny 0}% + \pgftext[right,at={\pgfxy(-0.2,0.0)}]{\tiny 0}% + \foreach \x in {1,...,#1} {\pgftext[top,at={\pgfxy(\x,-0.2)}]{\tiny\x}}% + \foreach \y in {1,...,#2} {\pgftext[right,at={\pgfxy(-0.2,\y)}]{\tiny\y}}% + \end{scope} +} + + +% Sometimes we want to put a comment in tiny text on the next line, but the default line skip +% will insert too much vertical space. Put a \tinyskip at the end of the line instead. +\def\tinyskip{\\[-0.33\baselineskip]} + + +% Bold-face text using the structure colour. +\newcommand<>{\structurebf}[1]{\structure#2{\textbf{#1}}} + + +% preamble +\title{Characterising relational view updates \\ using relative information capacity} +\author{\large Nigel Stanger \\[0.75cm] + \hspace*{0.5cm} + \includegraphics[scale=0.2]{Business_School_LS_ID_crop} + \hspace*{0.57cm} + \rule{1pt}{1.482cm} + \hspace*{0.46cm} + \rmfamily\small + \raisebox{0.4cm}{\shortstack[l]{Department of \\ Information Science}} +} +\date{February 1, 2017} + + +\begin{document} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \thispagestyle{empty} + \titlepage +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \centering + \begin{tikzpicture} + \node (book) {\includegraphics[height=8cm,keepaspectratio]{Date-ViewUpdatingandRelationalTheory-large.png}}; + \node[anchor=north] (url) at (book.south) {\tiny\href{http://shop.oreilly.com/product/0636920028437.do}{http://shop.oreilly.com/product/0636920028437.do} (2013)}; + \node (date) [below=0.8cm of book.east] {\includegraphics[height=2.2cm,keepaspectratio]{date.png}}; + \only<2->{\fill[fill,yellow,semitransparent] (-0.25,-0.75) rectangle (2.55,-0.4);} +% \DrawGridTikZ{7.0}{8.0} + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Some quick terminology} + + \begin{columns} + \begin{column}{0.4\textwidth} + \centering + \includegraphics[width=0.95\columnwidth,keepaspectratio]{Date-SQLandRelationalTheory.png} + + \tiny\href{http://shop.oreilly.com/product/0636920022879.do}{http://shop.oreilly.com/product/0636920022879.do} \\ + (second edition, 2011) + + \note<1>[item]{This is the second edition; the third edition is now available.} + \end{column} + \begin{column}{0.6\textwidth} + \structurebf{Value vs.\ variable} + \begin{itemize} + \item a value is immutable (“2”) + \item a variable contains a value + \item[\(\Rightarrow\)] \emph{relation} value, variable (\emph{relvar}) + \end{itemize} + \medskip + + \structurebf{Relation \alert<2>{heading} \& \alert<3>{body}} + \medskip + + {\scriptsize + \begin{tabular}{c|l|l|r|l|} + \cline{2-5} + \textbf{S} & \textbf{\alert<2>{Sno}} & \textbf{\alert<2>{Sname}} & \textbf{\alert<2>{Status}} & \textbf{\alert<2>{City}} \\ + \cline{2-5} + & \alert<3>{S1} & \alert<3>{Smith} & \alert<3>{20} & \alert<3>{London} \\ + & \alert<3>{S2} & \alert<3>{Jones} & \alert<3>{30} & \alert<3>{Paris} \\ + \cline{2-5} + \end{tabular}} + \bigskip + + \structurebf{Type (\(\bm{\Type{x}}\))} + \begin{itemize} + \item (finite) set of values that something (\(x\)) can take + \end{itemize} + \medskip + + \structurebf{Date doesn’t believe in nulls}\tinyskip + {\tiny (but it doesn’t really matter here)} + \end{column} + \end{columns} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{More on types} + + \structurebf{Attribute type (\(\bm{\Type{A}}\))} + \begin{itemize} + \item set of all possible values that \(A\) can take + \item[=] \(\{v_{1}\text{,}\, v_{2}\text{,}\, \dotsc\text{,}\, v_{m}\}\) {\tiny (for finite \(m\))} + \end{itemize} + \medskip + + \structurebf{Tuple type (\(\bm{\TT{R}}\)) of relvar \(\bm{R}\)} + \begin{itemize} + \item set of all possible tuple values with \(R\)’s heading + \item[=] Cartesian product of \(R\)’s attribute types + \item[=] \(\Type{A_{1}} \times \Type{A_{2}} \times \dotsb \times \Type{A_{n}}\) + \end{itemize} + \medskip + + \structurebf{Relation type (\(\bm{\Type{R}}\)) of relvar \(\bm{R}\)} + \begin{itemize} + \item set of all possible relation values with \(R\)’s heading + \item[=] every possible combination of elements of \(\TT{R}\) + \end{itemize} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Date’s (hoary and clichéd) suppliers-and-parts schema} + + \structurebf{\(\bm{S\{\Sno\text{,}\, \Sname\text{,}\, \Status\text{,}\, \City\}}\)} + + \begin{quote} + \upshape + Supplier \(\Sno\) is under contract, is named \(\Sname\), has status \(\Status\), and is located in city \(\City\) + \end{quote} + \bigskip + + \structurebf{\(\bm{P\{\mathit{Pno}\text{,}\, \mathit{Pname}\text{,}\, \mathit{Colour}\text{,}\, \mathit{Weight}\text{,}\, \City\}}\)} + + \begin{quote} + \upshape + Part \(\mathit{Pno}\) is used in the enterprise, is named \(\mathit{Pname}\), has colour \(\mathit{Colour}\), and weight \(\mathit{Weight}\) + \end{quote} + \bigskip + + \structurebf{\(\bm{SP\{\Sno\text{,}\, \mathit{Pno}\text{,}\, \mathit{Qty}\}}\)} + + \begin{quote} + \upshape + Supplier \(\Sno\) supplies (ships) part \(\mathit{Pno}\) in quantity \(\mathit{Qty}\) + \end{quote} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{The view update problem} + + \centering + \Large + \begin{tikzpicture}[every edge/.style={draw,semithick}] + \node (vdb) {\(V(\mathit{DB})\)}; + \node (db) [below=18mm of vdb] {\(\mathit{DB}\vphantom{(')}\)}; + + \node (vdbp) [right=4cm of vdb] {\(V(\mathit{DB}')\)}; + \node (uvdb) [left=-1mm of vdbp] {\(U(V(\mathit{DB})) \stackrel{?}{=}\)}; + + \node (dbp) at (db -| vdbp) {\(\mathit{DB}\smash[t]{'}\vphantom{()}\)}; + \node (tudb) [left=-1mm of dbp] {\(T(U)(\mathit{DB}) =\)}; + + \graph{ + { (db), (dbp) } -> [edge label={\(V\)},swap] { (vdb), (vdbp) }; + + (vdb) -> [edge node={node (u) [above=-0.6mm] {\(U\)}}] (uvdb); + (db) -> [edge node={node (tu) [above=-0.6mm] {\(T(U)\)}}] (tudb); + + (u) -> [double equal sign distance=2pt,-implies,edge label={\(T\)}] (tu); + }; + \end{tikzpicture} + \\ + \tiny Keller (1985) \emph{Algorithms for translating view updates to database updates for views involving selections, projections, and joins} + + \note<1>{Keller: “The user specifies update \(U\) against the view of the database, \(V(\mathit{DB})\). The view update translator \(T\) supplies the database update \(T(U)\), which results in \(DB'\) when applied to the database. The new view state is \(V(\mathit{DB}')\). This translation has no side effects in the view if \(V(\mathit{DB}') = U(V(\mathit{DB}))\), that is, if the view has changed precisely in accordance with the user’s request.”} + + \bigskip + \normalsize + + \begin{uncoverenv}<2-> + \structurebf{Problem:} there are often multiple update translations \(T(U)\) that produce the effect of \(U\) but have quite different effects on \(\mathit{DB}\). + \bigskip + + How do we choose? + \end{uncoverenv} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{The view update problem} + + \begin{columns} + \begin{column}[T]{0.45\textwidth} + \footnotesize\color{gray!70} + \begin{tabular}{|l|l|r|l|} + \multicolumn{4}{l}{\textbf{S}} \\ + \hline + \textbf{Sno} & \textbf{Sname} & \textbf{Status} & \textbf{City} \\ + \hline + S1 & Smith & 20 & London \\ + S2 & Jones & 30 & Paris \\ + S3 & Blake & 30 & Paris \\ + \only<1-2,4->{S4} & \only<1-2,4->{Clark} & \only<1-2,4->{20} & \only<1-2,4,6>{London}\only<5>{\alert{???}}\only<7->{\alert{Paris}} \\ + S5 & Adams & 30 & Athens \\ + \hline + \end{tabular} + \end{column} + \begin{column}[T]{0.45\textwidth} + \footnotesize + \begin{tabular}{|l|l|r|l|} + \multicolumn{4}{l}{\(\bm{\text{\textbf{LS}} = \RelRestrict_{\text{\textbf{City}} = \text{\textbf{`London'}}} \,\text{\textbf{S}}}\)} \\ + \hline + \textbf{Sno} & \textbf{Sname} & \textbf{Status} & \textbf{City} \\ + \hline + S1 & Smith & 20 & London \\ + \only<1-2,4,6>{S4} & \only<1-2,4,6>{Clark}& \only<1-2,4,6>{20} & \only<1-2,4,6>{London} \\ + \hline + \end{tabular} + \end{column} + \end{columns} + \bigskip + + \structurebf{Delete S4 from LS?} + + \begin{enumerate} + \item<2-> Delete S4 from S. + \item<4-> Change S4’s city to anything other than London. + \end{enumerate} + \bigskip + + \begin{uncoverenv}<6-> + \structurebf{What if we instead \emph{change} S4’s city to Paris in LS?} + \begin{itemize} + \item<7->[\(\Rightarrow\)] changing S4’s city to Paris in S + \item<7-> side effect: some changes behave like deletes! + \end{itemize} + \end{uncoverenv} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{The view update problem} + + \tiny + \begin{columns} + \begin{column}[T]{0.35\textwidth} + \color{gray!70} + \begin{tabular}{|l|l|r|l|} + \multicolumn{4}{l}{\textbf{S}} \\ + \hline + \textbf{Sno} & \textbf{Sname} & \textbf{Status} & \textbf{City} \\ + \hline + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} \\ + S2 & Jones & 30 & Paris \\ + S3 & Blake & 30 & Paris \\ + S4 & Clark & 20 & London \\ + S5 & Adams & 30 & Athens \\ + \hline + \end{tabular} + \bigskip + + \begin{tabular}{|l|l|r|} + \multicolumn{3}{l}{\textbf{SP}} \\ + \hline + \textbf{Sno} & \textbf{Pno} & \textbf{Qty} \\ + \hline + \only<1-2,4,6,8-9>{S1}\only<5>{\alert{S3}}\only<7>{\alert{S6}} & \only<1-2,4-9>{P1} & \only<1-2,4-9>{300} \\ + S1 & P2 & 200 \\ + S1 & P3 & 400 \\ + S1 & P4 & 200 \\ + S1 & P5 & 100 \\ + S1 & P6 & 100 \\ + S2 & P1 & 300 \\ + S2 & P2 & 400 \\ + S3 & P2 & 200 \\ + S4 & P2 & 300 \\ + S4 & P4 & 300 \\ + S4 & P5 & 400 \\ + \hline + \end{tabular} + \bigskip\medskip + + \color{black} + \end{column} + \begin{column}[T]{0.55\textwidth} + \begin{tabular}{|l|l|r|l|l|r|} + \multicolumn{4}{l}{\(\bm{\mathsf{SSP} = \mathsf{S} \RelNaturalJoin \mathsf{SP}}\)} \\ + \hline + \textbf{Sno} & \textbf{Sname} & \textbf{Status} & \textbf{City} & \textbf{Pno} & \textbf{Qty} \\ + \hline + \only<1-2,4,6,8-9>{S1}\only<5>{\alert{S3}}\only<7>{\alert{S6}} & \only<1-2,4,6-9>{Smith}\only<5>{\alert{Blake}} & \only<1-2,4,6-9>{20}\only<5>{\alert{30}} & \only<1-2,4,6-9>{London}\only<5>{\alert{Paris}} & \only<1-2,4-9>{P1} & \only<1-2,4-9>{300} \\ + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} & \only<1-9>{P2} & \only<1-9>{200} \\ + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} & \only<1-9>{P3} & \only<1-9>{400} \\ + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} & \only<1-9>{P4} & \only<1-9>{200} \\ + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} & \only<1-9>{P5} & \only<1-9>{100} \\ + \only<1-6,8-9>{S1}\only<7>{\alert{S6}} & \only<1-9>{Smith} & \only<1-9>{20} & \only<1-9>{London} & \only<1-9>{P6} & \only<1-9>{100} \\ + S2 & Jones & 30 & Paris & P1 & 300 \\ + S2 & Jones & 30 & Paris & P2 & 400 \\ + S3 & Blake & 30 & Paris & P2 & 200 \\ + S4 & Clark & 20 & London & P4 & 300 \\ + S4 & Clark & 20 & London & P5 & 400 \\ + S4 & Clark & 20 & London & P2 & 200 \\ + \hline + \end{tabular} + \bigskip + + \scriptsize + \structurebf{Delete first row of SSP?} + + \begin{enumerate} + \item<2-> Delete \(\text{SP}\{\text{S1}\text{,}\, \text{P1}\text{,}\, \text{300}\}\). + \item<4-|alert@8> Change supplier number in \(\text{SP}\{\text{S1}\text{,}\, \text{P1}\text{,}\, \text{300}\}\). + \item<6-|alert@8> Change S1’s supplier number in S. + \item<9-> Delete S1 from S. {\tiny (nuclear option)} + \end{enumerate} + \uncover<8>{\tiny\alert{\beamerbutton{technically correct}}} + + \uncover<11>{\structurebf{Changes are even more problematic}} + \end{column} + \end{columns} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Date's solution} + + \begin{itemize} + + \item Explicitly specify \emph{all} constraints in advance.\tinyskip + {\tiny (``metadata approach'' with similar issues to many earlier attempts)} + + \item Automatically generate \emph{compensatory rules} from constraints.\tinyskip + {\tiny (kind of like declarative triggers)} + + \item No problem if original and view schemas are \emph{information equivalent}. + {\tiny (no hidden information)} + \begin{itemize} + + \item[] ``…if and only if the constraints that apply to [schema \(\schema{1}\)] and [schema \(\schema{2}\)] are such that every proposition that can be represented by [\(\schema{1}\)] can be represented by [\(\schema{2}\)] and vice versa''\\ + \hfill{\tiny Date (2013) \emph{View Updating \& Relational Theory}} + + \end{itemize} + \medskip + + \item[BUT:] Still potential for ambiguity when views hide information.\tinyskip + {\tiny(i.e., no longer information equivalent)} + \medskip + + \item Date’s approach involves “\emph{…a clear element of pragma…}”.\tinyskip + {\tiny (essentially he argues for “common sense” ambiguity resolution)} + + \end{itemize} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Relative information capacity} + \framesubtitle{} + + \begin{itemize} + + \item “Information content” of a schema. {\tiny (including constraints)} + + \item Determines set of all valid instances of a schema. + + \item Can only be compared, not quantitatively measured. + \begin{description} + \item[equivalence] \(\Equivalent{\schema{1}}{\schema{2}}\) + \item[dominance] \(\Dominates{\schema{2}}{\schema{1}}\) + \end{description} + + \item Mappings between schemas can preserve: + \begin{description} + \item[information] information capacity increases (\(\Rightarrow\Dominates{\schema{2}}{\schema{1}}\)) + \item[equivalence] information capacity stays the same (\(\Rightarrow\Equivalent{\schema{1}}{\schema{2}}\)) + \end{description} + + \end{itemize} + + \flushright\tiny + Hull (1986) \emph{Relative information capacity of simple relational database schemata} \\ + Miller (1993) \emph{The use of information capacity in schema integration and translation} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Schema intension graphs (SIGs)} + + \structurebf{Nodes = typed domains (sets of values)} + \begin{itemize} + \item simple + \item constructed (\(\times\), \(+\)) + \end{itemize} + \medskip + + \structurebf{Edges = associations between domains} {\tiny (binary relations)} + \begin{itemize} + \item Simple constraints: + \begin{itemize} + \item total (\(A \Total B\)): defined for all \(a \in A\) + \item surjective (\(A \Surjective B\)): defined for all \(b \in B\) + \item functional (\(A \Functional B\)): \(a\) maps to at most one \(b\) + \item injective (\(A \Injective B\)): \(b\) maps to at most one \(a\) + \item bijective (\(A \Bijective B\)): all four + \end{itemize} + \item Selection (\(A \SelectionEdge B\)): \(B\) is a subset of \(A\). {\tiny (\(\Rightarrow B\) is a specialisation or subtype of \(A\))} + \item Projection (\(A \ProjectionEdge B\)): \(B\) is a projection of \(A\). {\tiny (\(\Rightarrow A\) is a constructed tuple type)} + \end{itemize} + + \flushright\tiny + Miller (1994) \emph{Schema equivalence in heterogeneous systems: Bridging theory and practice} \\ + Miller (1994) \emph{Schema intension graphs: A formal model for the study of schema equivalence} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame<1-2>[label=frame.SIG.example] +{ + \frametitle{Example SIG for relvar \(\bm{S\{\Sno\text{,}\, \Sname\text{,}\, \Status\text{,}\, \City\}}\)} + \framesubtitle{\uncover<3>{\hyperlink{frame.SIG.Sone}{\beamerreturnbutton{Back}}}} + + \centering\Large + \begin{tikzpicture}[level distance=18mm] + \node (TS) {\(\Type{S}\)}; + \node (TTS) [right=1.5cm of TS] {\(\TT{S}\)} + [sibling distance=4.5cm] + child[arrows={<{crossbar}-{crossbar}>}] {node (TSno) {\(\Type{\Sno}\)}} + child[arrows={:{crossbar}-{crossbar}>}] {node (TSSC) {\(\TSSC\)} + [sibling distance=22mm] + child[arrows={:{crossbar}-{crossbar}>}] {node (TSname) {\(\Type{\Sname}\)}} + child[arrows={:{crossbar}-{crossbar}>}] {node (TStatus) {\(\Type{\Status}\)}} + child[arrows={:{crossbar}-{crossbar}>}] {node (TCity) {\(\Type{\City}\)}}}; + + \node (TTSexpansion) [right=-2mm of TTS,visible on=<2>,alert] {\tiny\(= \Type{\Sno} \times \Type{\Sname} \times \Type{\Status} \times \Type{\City}\)}; + + % TS to T{S} + \draw[arrows={:{crossbar}-{crossbar}:}] (TS) to (TTS); + + % FD + \draw[arrows={:{crossbar}-{crossbar}>}] (TSno) to node[below=-2pt] {\scriptsize\emph{key}} (TSSC); + + % projection edges + \ProjectionAnnotation[above left=-2pt and -4pt]{TTS}{TSno} + \ProjectionAnnotation[above right=-2pt and -4pt]{TTS}{TSSC} + + \ProjectionAnnotation[above left=-2pt and -4pt]{TSSC}{TSname} + \ProjectionAnnotation[right=-2pt]{TSSC}{TStatus} + \ProjectionAnnotation[above right=-2pt and -4pt]{TSSC}{TCity} + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\begin{frame}[fragile] + \frametitle{SIGs for relational schemas} + + \centering + \begin{tabular}{lll} + \toprule + \textbf{Relational} & \textbf{SIG} & \textbf{Notation} \\ + \midrule + attribute type & simple domain & \(\Type{A}\) \\ + tuple type & constructed domain (\(\times\)) & \(\TT{R}\) or \(\Type{A} \times \Type{B} \times \dotsc\) \\ + relation type & simple domain\footnote{Or possibly a complex constructed type involving union?} & \(\Type{R}\) \\ + \midrule + key\footnote{Implied by functional dependency.} & func., total, surj.\ edge & \(\Type{A} \KeyEdge \Type{B}\) \\ + foreign key\footnote{Inclusion dependency.} & — & — \\ + \midrule + restrict (\(\RelRestrict\)) & selection edge & \(A \SelectionEdge B\) or \(A \TrivialSelection B\)\footnote{Trivial case.} \\ + project (\(\RelProject\)) & projection edge & \(A \ProjectionEdge B\) or \(A \TrivialProjection B\) \\ + \bottomrule + \end{tabular} +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Comparing and transforming SIGs} + + \begin{itemize} + + \item Isomorphism between SIGs for \(\schema{1}\) and \(\schema{2}\) (both structure and semantics) indicates information equivalence: + \begin{itemize} + \item \(\Equivalent{\schema{1}}{\schema{2}}\) if we can make \(\schema{1}\) isomorphic to \(\schema{2}\) using equivalence preserving transformations {\tiny (or vice versa)} + \item \(\Dominates{\schema{2}}{\schema{1}}\) if we can make \(\schema{1}\) isomorphic to \(\schema{2}\) using information preserving transformations {\tiny (or vice versa)} + \item \(\schema{1}\) \& \(\schema{2}\) non-comparable if we can’t make them isomorphic + \end{itemize} + \medskip + + \item Transforming a SIG effectively transforms the schema. + \begin{itemize} + \item delete annotation, \(\RelRestrict\), \(\RelProject\) (\(\preceq\)) + \item move and/or copy edge (\(\preceq\)) + \item create/delete duplicate node: \(A \Rightarrow A \TrivialSelection A'\) (\(\equiv\)) + \item delete bijective (trivial) selection edge: \(A \TrivialSelection A' \Rightarrow A \quad A'\) (\(\preceq\)) + \item create recursive bijective selection edge: \(A \Rightarrow\)\smash{\tikz[baseline={(A.base)},every loop/.style={out=-25,in=25,bijection}]{\node (A) {\(A\)}; \path (A) edge [loop right] node {\scriptsize\(\RelRestrict\)} ();}}(\(\equiv\)) + \end{itemize} + + \end{itemize} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Gotta catch ’em all…} + \framesubtitle{(constraints, that is)} + + \begin{columns} + \begin{column}[T]{0.5\textwidth} + \structurebf{Consider {\tiny (disjoint restriction views, Date Ch. 4)}} + + \small + \begin{itemize} + \item \(S\{\Sno\text{,}\,\Sname\text{,}\,\Status\text{,}\,\City\}\) + \item view \(\LS = \RelRestrict_{\City = \text{`\emph{London}'}}S\) + \item view \(\NLS = \RelRestrict_{\City \ne \text{`\emph{London}'}}S\) + \item Base schema \(\schema{0} = \{S\text{,}\, \LS\text{,}\, \NLS\}\) + \item Sub-schemas \(\schema{1} = \{S\}\), \(\schema{2} = \{\LS\text{,}\, \NLS\}\), \(\schema{3} = \{LS\}\) + \item Date says \((\schema{1}\text{,}\, \schema{2})\) are informa- tion equivalent, \((\schema{1}\text{,}\, \schema{3})\) aren’t.\tinyskip + {\tiny (due to information hiding)} + \end{itemize} + + \alert{To construct truly comparable SIGs, we need to propagate all the constraints that we can from \(\schema{0}\) to \(\schema{1}\), \(\schema{2}\), and \(\schema{3}\).} + \end{column} + \begin{column}[T]{0.5\textwidth} + \begin{uncoverenv}<2-> + \structurebf{Constraints in \(\bm{\schema{0}}\)} + + \tiny + \begin{ConstraintList} + \item \(\{\Sno\} \rightarrow \{\Sname\text{,}\, \Status\text{,}\, \City\}\) holds in (a) \(S\); (b) \(\LS\); and (c) \(\NLS\)\quad [key] + + \item \(\RelProject_{\{\Sno\}}\LS \subseteq \RelProject_{\{\Sno\}}S\)\quad [FK \(\LS \rightarrow S\)] + + \item \(\RelProject_{\{\Sno\}}\NLS \subseteq \RelProject_{\{\Sno\}}S\)\quad [FK \(\NLS \rightarrow S\)] + + \item \(S = \LS \RelUnion \NLS\) + + \item \(\RelRestrict_{\City \ne \text{`\emph{London}'}}\LS = \emptyset\) + + \item \(\RelRestrict_{\City = \text{`\emph{London}'}}\NLS = \emptyset\) + + \item \(\LS \RelIntersect \NLS = \emptyset\) + + \item (a) \(\Type{S} = \Type{\LS} \RelUnion \Type{\NLS}\); (b) \(\TT{S} = \TT{\LS} \RelUnion \TT{\NLS}\) + + \item (a) \(\Type{\LS} \subset \Type{S}\); (b) \(\TT{\LS} \subset \TT{S}\) + + \item (a) \(\Type{\NLS} \subset \Type{S}\); (b) \(\TT{\NLS} \subset \TT{S}\) + + \item \(\CityLondon \subset \Type{\City}\) + + \item \((\TCityMinusLondon) \subset \Type{\City}\) + + \item \(\TSSL \subset \TSSC\) + + \item \(\TSSNL \subset \TSSC\) + \end{ConstraintList} + \end{uncoverenv} + \end{column} + \end{columns} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Propagating constraints to sub-schemas} + \framesubtitle{(ignoring \(\bm{\text{C}_{2}}\) and \(\bm{\text{C}_{3}}\) for now)} + + \small + + \structurebf{Directly propagate constraints that reference no relvars} + \begin{itemize} + \item[] \(\text{C}_{11}\), \(\text{C}_{12}\), \(\text{C}_{13}\), \(\text{C}_{14}\) + \end{itemize} + \medskip + + \structurebf{Directly propagate constraints that reference sub-schema relvars only} + \begin{itemize} + \item[\(\schema{1}\)] \(\text{C}_{1}\)(a) + \item[\(\schema{2}\)] \(\text{C}_{1}\)(b), \(\text{C}_{1}\)(c), \(\text{C}_{5}\), \(\text{C}_{6}\), \(\text{C}_{7}\) + \item[\(\schema{3}\)] \(\text{C}_{1}\)(b), \(\text{C}_{5}\) + \end{itemize} + \medskip + + \structurebf{Rewrite remaining constraints in terms of sub-schema relvars {\tiny (if possible)}} + + \begin{itemize} + \item[\(\schema{1}\)] Replace \(\LS\) with \(\RelRestrict_{\City = \text{`\emph{London}'}}\,S\) and \(\NLS\) with \(\RelRestrict_{\City \ne \text{`\emph{London}'}}\,S\) in \(\text{C}_{1}\)(b), \(\text{C}_{1}\)(c), \(\text{C}_{4}\), \(\text{C}_{5}\), \(\text{C}_{6}\), \(\text{C}_{7}\), \(\text{C}_{8}\), \(\text{C}_{9}\), \(\text{C}_{10}\). + + \item[\(\schema{2}\)] Replace \(S\) with \(\LS \RelUnion \NLS\) in \(\text{C}_{1}\)(a), \(\text{C}_{4}\), \(\text{C}_{8}\), \(\text{C}_{9}\), \(\text{C}_{10}\). + + \item[\(\schema{3}\)] Can’t rewrite any remaining constraints. + \end{itemize} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Propagating constraints to sub-schemas} + + \structurebf{Example} + \medskip + + \begin{tabular}{lll} + \textcolor{structure}{\(\schema{0}\)} & \(\text{C}_{4}\) & \(S = \LS \RelUnion \NLS\) \\[4pt] + & & \Large\quad\(\Downarrow\) \\[4pt] + \textcolor{structure}{\(\schema{1}\)} & \(\text{C}_{4}^{\schema{1}}\) & \(S = (\RelRestrict_{\City = \text{`\emph{London}'}}\,S) \RelUnion (\RelRestrict_{\City \ne \text{`\emph{London}'}}\,S)\) \\[8pt] + \textcolor{structure}{\(\schema{2}\)} & \(\text{C}_{4}^{\schema{2}}\) & \(\LS \RelUnion \NLS = \LS \RelUnion \NLS\) \\[8pt] + \textcolor{structure}{\(\schema{3}\)} & — & (can’t be propagated) \\ + \end{tabular} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame<1>[label=frame.SIG.Sone] +{ + \frametitle{The SIGs: \(\bm{\schema{1} = \{S\}}\)} + \framesubtitle{\alt<1>{\hyperlink{frame.SIG.example<3>}{\beamergotobutton{Compare}}}{\hyperlink{frame.SIG.transform<9>}{\beamerreturnbutton{Back}}}} + + \centering + \begin{tikzpicture}[ampersand replacement=\&,transform canvas={scale=0.8}] + \matrix[row sep=0.5cm] + { + \node (TLS) {\(\mathrlap{\,\Type{\LSsub}}\hphantom{\Type{\LS}}\)}; \&[7mm] \node (TTLS) {\(\mathrlap{\,\TT{\LSsub}}\hphantom{\TT{\LS}}\)}; \&[7mm] \&[4mm] \&[-4mm] \node (TSSL) {\(\StackTSSL\)}; \& \& \node (LSCity) {\(\CityLondon\)}; \\ + \& \& \& \node (TSname) {\(\Type{\Sname}\)}; \\ + \node (TLSPlusNLS) {\(\Type{S}\)}; \& \node (TTLSPlusNLS) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \& \node (TSSC) {\(\StackTSSC\)}; \& \& \node (TCity) {\(\Type{City}\)}; \\ + \& \& \& \& \& \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TNLS) {\(\mathrlap{\,\:\Type{\NLSsub}}\hphantom{\Type{\NLS}}\)}; \& \node (TTNLS) {\(\mathrlap{\,\:\TT{\NLSsub}}\hphantom{\TT{\NLS}}\)}; \& \& \& \node (TSSNL) {\(\StackTSSNL\)}; \& \& \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TLS), (TNLS), (TLSPlusNLS) } -- { (TTLS), (TTNLS), (TTLSPlusNLS) }, + }; + + % FDs + (TSno) -- [funcdep left,bend left] (TSSL); + (TSno) -- [funcdep right] (TSSNL); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTLSPlusNLS), (TTLS) } -- (TSno) + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTNLS) -- (TSno) + }; + + { [edges=projection left] + (TTLS) -- (TSSL), + (TSSL) -- { (TStatus), (LSCity) }, + }; + + { [edges=projection right] + (TTNLS) -- (TSSNL), + (TSSC) -- { (TSname), (TStatus) }, + (TSSL) -- (TSname), + (TSSNL) -- { (NLSCity), (TStatus) }, + (TSSNL) -- [bend left=10] (TSname), + }; + + % selection edges + { [edges=selection left] + { (TLSPlusNLS), (TTLSPlusNLS) } -- { (TLS), (TTLS) }, + (TSSC) -- { (TSSL), (TSSNL) }, + (TCity) -- (NLSCity), + }; + { [edges=selection right] + { (TLSPlusNLS), (TTLSPlusNLS) } -- { (TNLS), (TTNLS) }, + (TCity) -- (LSCity), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TSno) -- (TSSC), + (TSSC) -- (TCity), + (TTLSPlusNLS) -- [bend right] (TSSC), + }; + (TSno) -- [funcdep right] (TSSC); + (TSSC) -- [projection left] (TCity); + (TTLSPlusNLS) -- [projection right,bend right] (TSSC), + }; + + \node[below=5mm of NLSCity,alert] (caption) {\scriptsize\shortstack[r]{\textbf{Note:} \(\LSsub = \RelRestrict_{\City = \text{`\emph{London}'}}\,S\) \\ \(\NLSsub = \RelRestrict_{\City \ne \text{`\emph{London}'}}\,S\)}}; + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{The SIGs: \(\bm{\schema{2} = \{\LS\text{,}\, \NLS\}}\)} + \framesubtitle{\invisible{\beamergotobutton{Compare}}} + + \centering + \begin{tikzpicture}[ampersand replacement=\&,transform canvas={scale=0.8}] + \matrix[row sep=0.5cm] + { + \node (TLS) {\(\Type{\LS}\)}; \&[7mm] \node (TTLS) {\(\TT{\LS}\)}; \&[7mm] \&[4mm] \&[-4mm] \node (TSSL) {\(\StackTSSL\)}; \& \& \node (LSCity) {\(\CityLondon\)}; \\ + \& \& \& \node (TSname) {\(\Type{\Sname}\)}; \\ + \node (TLSPlusNLS) {\(\StackTLSPlusNLS\)}; \& \node (TTLSPlusNLS) {\(\StackTTLSPlusNLS\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \& \node (TSSC) {\(\StackTSSC\)}; \& \& \node (TCity) {\(\Type{City}\)}; \\ + \& \& \& \& \& \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TNLS) {\(\Type{\NLS}\)}; \& \node (TTNLS) {\(\TT{\NLS}\)}; \& \& \& \node (TSSNL) {\(\StackTSSNL\)}; \& \& \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TLS), (TNLS), (TLSPlusNLS) } -- { (TTLS), (TTNLS), (TTLSPlusNLS) }, + }; + + % FDs + (TSno) -- [funcdep left,bend left] (TSSL); + (TSno) -- [funcdep right] (TSSNL); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTLSPlusNLS), (TTLS) } -- (TSno) + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTNLS) -- (TSno) + }; + + { [edges=projection left] + (TTLS) -- (TSSL), + (TSSL) -- { (TStatus), (LSCity) }, + }; + + { [edges=projection right] + (TTNLS) -- (TSSNL), + (TSSC) -- { (TSname), (TStatus) }, + (TSSL) -- (TSname), + (TSSNL) -- { (NLSCity), (TStatus) }, + (TSSNL) -- [bend left=10] (TSname), + }; + + % selection edges + { [edges=selection left] + { (TLSPlusNLS), (TTLSPlusNLS) } -- { (TLS), (TTLS) }, + (TSSC) -- { (TSSL), (TSSNL) }, + (TCity) -- (NLSCity), + }; + { [edges=selection right] + { (TLSPlusNLS), (TTLSPlusNLS) } -- { (TNLS), (TTNLS) }, + (TCity) -- (LSCity), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TSno) -- (TSSC), + (TSSC) -- (TCity), + (TTLSPlusNLS) -- [bend right] (TSSC), + }; + (TSno) -- [funcdep right] (TSSC); + (TSSC) -- [projection left] (TCity); + (TTLSPlusNLS) -- [projection right,bend right] (TSSC), + }; + + \node[below=4cm of current page.south west,structure] (caption) {\Large This is already isomorphic to the SIG for \(\schema{1}\), so \(\Equivalent{\schema{1}}{\schema{2}}\).}; + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{The SIGs: \(\bm{\schema{3} = \{\LS\}}\)} + \framesubtitle{\invisible{\beamergotobutton{Compare}}} + + \centering + \begin{tikzpicture}[ampersand replacement=\&,transform canvas={scale=0.8}] + \matrix[row sep=0.5cm] + { + \node (TLS) {\(\Type{\LS}\)}; \&[7mm] \node (TTLS) {\(\TT{\LS}\)}; \&[7mm] \&[4mm] \&[-4mm] \node (TSSL) {\(\StackTSSL\)}; \& \& \node (LSCity) {\(\CityLondon\)}; \\ + \& \& \& \node (TSname) {\(\Type{\Sname}\)}; \\ + \node[invisible] (TLSPlusNLS) {\(\Type{S}\)}; \& \node[invisible] (TTLSPlusNLS) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \& \node (TSSC) {\(\StackTSSC\)}; \& \& \node (TCity) {\(\Type{City}\)}; \\ + \& \& \& \& \& \node (TStatus) {\(\Type{\Status}\)}; \\ + \node[invisible] (TNLS) {\(\Type{\NLS}\)}; \& \node[invisible] (TTNLS) {\(\TT{\NLS}\)}; \& \& \& \node (TSSNL) {\(\StackTSSNL\)}; \& \& \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TLS) -- (TTLS), + (TLSPlusNLS) --[invisible] (TTLSPlusNLS), + (TNLS) --[invisible] (TTNLS), + }; + + % FDs + (TSno) -- [funcdep left,bend left,invisible] (TSSL); + (TSno) -- [funcdep right,invisible] (TSSNL); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + (TTLS) -- (TSno) + }; + + { [edges=projection left] + (TTLS) -- (TSSL), + (TSSL) -- { (TStatus), (LSCity) }, + (TTLSPlusNLS) --[invisible] (TSno), + }; + + { [edges=projection right] + (TSSC) -- { (TSname), (TStatus) }, + (TSSL) -- (TSname), + (TSSNL) -- { (NLSCity), (TStatus) }, + (TSSNL) -- [bend left=10] (TSname), + (TTNLS) --[invisible] (TSno), + (TTNLS) -- [arrows={:->},invisible] (TSSNL), + }; + + % selection edges + { [edges=selection left] + (TSSC) -- { (TSSL), (TSSNL) }, + (TCity) -- (NLSCity), + }; + { [edges=selection right] + (TCity) -- (LSCity), + }; + + { [edges=bijection,edge label={\scriptsize\(\RelRestrict\)}] + { (TLS), (TTLS) } -- [invisible] { (TLSPlusNLS), (TTLSPlusNLS) }, + { (TLSPlusNLS), (TTLSPlusNLS) } -- [invisible] { (TNLS), (TTNLS) }, + }; + + { [edges=selection right] + { (TLSPlusNLS), (TTLSPlusNLS) } --[invisible] { (TLS), (TTLS) }, + }; + + { [edges=selection left] + { (TLSPlusNLS), (TTLSPlusNLS) } --[invisible] { (TNLS), (TTNLS) }, + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TSno) -- (TSSC), + (TSSC) -- (TCity), + (TTLSPlusNLS) -- [bend right,invisible] (TSSC), + }; + (TSno) -- [funcdep right] (TSSC); + (TSSC) -- [projection left] (TCity); + (TTLSPlusNLS) -- [projection right,arrows={:{crossbar}->},bend right,invisible] (TSSC); + }; + + \node[below=4cm of current page.south west,structure] (caption) {\Large Similarities with \(\schema{1}\) but not identical, so we need to transform…}; + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame[label=frame.SIG.transform] +{ + \frametitle{Transforming \(\bm{\schema{3} \Rightarrow \schema{1}}\)} + \framesubtitle{\alt<1-8>{\textcolor{structure}{blue} = input to transformation, \textcolor{alert}{red} = output\invisible{\beamergotobutton{Compare}}}{\hyperlink{frame.SIG.Sone<2>}{\beamergotobutton{Compare}}}} + + \centering + \begin{tikzpicture}[ampersand replacement=\&,transform canvas={scale=0.8}] + \matrix[row sep=0.5cm] + { + \node[input on=<2>] (TLS) {\(\Type{\LS}\)}; \&[7mm] \node[input on=<2>] (TTLS) {\(\TT{\LS}\)}; \&[7mm] \&[4mm] \&[-4mm] \node (TSSL) {\(\StackTSSL\)}; \& \& \node (LSCity) {\(\CityLondon\)}; \\ + \& \& \& \node (TSname) {\(\Type{\Sname}\)}; \\ + \node[visible on=<2->,output on=<2>,input on=<3>] (TLSPlusNLS) {\(\Type{S}\)}; \& \node[visible on=<2->,output on=<2>,input on=<3>] (TTLSPlusNLS) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \& \node (TSSC) {\(\StackTSSC\)}; \& \& \node (TCity) {\(\Type{City}\)}; \\ + \& \& \& \& \& \node (TStatus) {\(\Type{\Status}\)}; \\ + \node[visible on=<3->,output on=<3>] (TNLS) {\(\Type{\NLS}\)}; \& \node[visible on=<3->,output on=<3>] (TTNLS) {\(\TT{\NLS}\)}; \& \& \& \node (TSSNL) {\(\StackTSSNL\)}; \& \& \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TLS) --[input on=<4>] (TTLS), + (TLSPlusNLS) --[visible on=<4->,output on=<4>] (TTLSPlusNLS), + (TNLS) --[visible on=<4->,output on=<4>] (TTNLS), + }; + + % FDs + (TSno) -- [funcdep left,arrows={:-{crossbar}>},bend left,visible on=<7->,output on=<7>] (TSSL); + (TSno) -- [funcdep right,arrows={:-{crossbar}>},visible on=<7->,output on=<7>] (TSSNL); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + (TTLS) --[input on=<5>] (TSno), + (TTLSPlusNLS) --[visible on=<5->,output on=<5>] (TSno) + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTNLS) --[visible on=<5->,output on=<5>] (TSno) + }; + + { [edges=projection left] + (TTLS) --[input on=<6>] (TSSL), + (TSSL) -- { (TStatus), (LSCity) } + }; + + { [edges=projection right] + (TTNLS) -- [arrows={:->},visible on=<6->,output on=<6>] (TSSNL), + (TSSC) -- { (TSname), (TStatus) }, + (TSSL) -- (TSname), + (TSSNL) -- { (NLSCity), (TStatus) }, + (TSSNL) -- [bend left=10] (TSname), + }; + + % selection edges + { [edges=selection left] + (TSSC) -- { (TSSL), (TSSNL) }, + (TCity) -- (NLSCity), + }; + { [edges=selection right] + (TCity) -- (LSCity), + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelRestrict\)}] + { (TLS), (TTLS) } -- [visible on=<2-7>,output on=<2>] { (TLSPlusNLS), (TTLSPlusNLS) }, + { (TLSPlusNLS), (TTLSPlusNLS) } -- [visible on=<3-7>,output on=<3>] { (TNLS), (TTNLS) }, + }; + + { [edges=selection left] + { (TLSPlusNLS), (TTLSPlusNLS) } --[visible on=<8->] { (TLS), (TTLS) }, + }; + + { [edges=selection right] + { (TLSPlusNLS), (TTLSPlusNLS) } --[visible on=<8->] { (TNLS), (TTNLS) }, + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TSno) -- (TSSC), + (TSSC) -- (TCity), + (TTLSPlusNLS) -- [bend right,visible on=<6->] (TSSC), + }; + (TSno) -- [funcdep right,input on=<7>] (TSSC); + (TSSC) -- [projection left] (TCity); + (TTLSPlusNLS) -- [projection right,arrows={:{crossbar}->},bend right,visible on=<6->,output on=<6>] (TSSC); + }; + + \begin{scope}[circle,visible on=<8>,output on=<8>] + \node[draw] (c1) at (TLSPlusNLS) [above=11.5pt] {}; + \node[draw] (c2) at (TLSPlusNLS) [below=11.5pt] {}; + \node[draw] (c3) at (c1 -| TTLSPlusNLS) {}; + \node[draw] (c4) at (c2 -| TTLSPlusNLS) {}; + \end{scope} + + \node[below=4cm of current page.south west,structure] (caption) { + \Large + \only<1>{Initial state} + \only<2>{Duplicate \(\Type{\LS}\) and \(\TT{\LS}\) [\(\equiv\)]} + \only<3>{Duplicate \(\Type{S}\) and \(\TT{S}\) [\(\equiv\)]} + \only<4>{Copy and move \(\Type{\LS} \SurTotal \TT{\LS}\) edge (\(\times 2\)) [\(\preceq\)]} + \only<5>{Copy and move \(\TT{\LS} \ProjectionEdge \Type{\Sno}\) edge (\(\times 2\)) [\(\preceq\)]} + \only<6>{Copy and move \(\TT{\LS} \ProjectionEdge \TSSL\) edge (\(\times 2\)) [\(\preceq\)]} + \only<7>{Copy and move \(\Type{\Sno} \KeyEdge \TSSC\) edge (\(\times 2\)) [\(\preceq\)]} + \only<8>{Remove totality annotations [\(\preceq\)]} + \only<9>{Final state: \emph{not} isomorphic to SIG for \(\schema{1} \Rightarrow\) non-comparable.} + }; + \end{tikzpicture} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{So what does this mean?} + + \structurebf{\(\bm{\schema{1}}\) and \(\bm{\schema{2}}\) are information equivalent} + + \begin{itemize} + + \item[\(\Rightarrow\)] all view updates between them should be OK + + \end{itemize} + \bigskip + + \structurebf{\(\bm{\schema{1}}\) and \(\bm{\schema{3}}\) aren’t information equivalent} + + \begin{itemize} + + \item[\(\Rightarrow\)] some view updates between them will cause problems + + \end{itemize} + \bigskip + + \structurebf{This agrees with what Date found} {\tiny (yay!)} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{More examples} + \framesubtitle{(Nonloss projection views, Date Ch. 5)} + + \(S\{\Sno, \Status, \City\}\); views \(\ST = \RelProject_{\{\Sno, \Status\}}S\), \(\SC = \RelProject_{\{\Sno, \City\}}S\) + \medskip\bigskip + + \begin{columns} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\STsub}\)}; \&[7mm] \node (TTST) {\(\TT{\STsub}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TSTPlusSC) {\(\Type{S}\)}; \& \node (TTSTPlusSC) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \node (TSC) {\(\Type{\SCsub}\)}; \& \node (TTSC) {\(\TT{\SCsub}\)}; \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TST), (TSC), (TSTPlusSC) } -- { (TTST), (TTSC), (TTSTPlusSC) }, + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + (TSno) -- [funcdep right] (TCity); + (TSno) -- [funcdep right] (TSSC); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTSTPlusSC), (TTST) } -- (TSno), + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTSC) -- (TSno), + }; + + { [edges=projection left] + { (TSTPlusSC), (TTSTPlusSC) } -- { (TST), (TTST) }, + (TSSC) -- (TCity), + (TTST) -- (TStatus), + }; + + { [edges=projection right] + { (TSTPlusSC), (TTSTPlusSC) } -- { (TSC), (TTSC) }, + (TSSC) -- (TStatus), + (TTSC) -- (TCity), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TTSTPlusSC) -- [bend right] (TSSC), + }; + (TTSTPlusSC) -- [projection right, bend right] (TSSC), + }; + \end{tikzpicture}% + } \\ + \(\schema{1} = \{S\}\) + \end{column} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TSTPlusSC) {\(\Type{J}\)}; \& \node (TTSTPlusSC) {\(\TT{J}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \node (TSC) {\(\Type{\SC}\)}; \& \node (TTSC) {\(\TT{\SC}\)}; \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TST), (TSC), (TSTPlusSC) } -- { (TTST), (TTSC), (TTSTPlusSC) }, + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + (TSno) -- [funcdep right] (TCity); + (TSno) -- [funcdep right] (TSSC); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTSTPlusSC), (TTST) } -- (TSno), + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTSC) -- (TSno), + }; + + { [edges=projection left] + { (TSTPlusSC), (TTSTPlusSC) } -- { (TST), (TTST) }, + (TSSC) -- (TCity), + (TTST) -- (TStatus), + }; + + { [edges=projection right] + { (TSTPlusSC), (TTSTPlusSC) } -- { (TSC), (TTSC) }, + (TSSC) -- (TStatus), + (TTSC) -- (TCity), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TTSTPlusSC) -- [bend right] (TSSC), + }; + (TTSTPlusSC) -- [projection right, bend right] (TSSC), + }; + \end{tikzpicture}% + } \\ + \(\schema{2} = \{\ST, \SC\}\) + \end{column} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \& \& \node (TSno) {\(\Type{\Sno}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TST) -- (TTST), + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + (TTST) -- (TSno), + }; + + { [edges=projection left] + (TTST) -- (TStatus), + }; + }; + \end{tikzpicture}% + } \\ + \(\schema{3} = \{\ST\}\) + \end{column} + \end{columns} + \medskip\medskip + + \begin{tabbing} + \structurebf{Results:} \=\(\Equivalent{\schema{1}}{\schema{2}}\) {\tiny (as expected)} \\ + \>\(\schema{1}\) and \(\schema{3}\) incomparable {\tiny (as expected)} + \end{tabbing} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{More examples} + \framesubtitle{(Lossy projection views, Date Ch. 5)} + + \small + \(S\{\Sno, \Status, \City\}\); views \(\ST = \RelProject_{\{\Sno, \Status\}}S\), \(\TC = \RelProject_{\{\Status, \City\}}S\) + \medskip + + \begin{columns} + \begin{column}{0.5\textwidth} + \centering + \scalebox{0.4}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\STsub}\)}; \&[7mm] \node (TTST) {\(\TT{\STsub}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TSTPlusTC) {\(\Type{S}\)}; \& \node (TTSTPlusTC) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \node (TTC) {\(\Type{\TCsub}\)}; \& \node (TTTC) {\(\TT{\TCsub}\)}; \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TST), (TTC), (TSTPlusTC) } -- { (TTST), (TTTC), (TTSTPlusTC) }, + }; + + % FDs + { [edges=funcdep right] + (TSno) -- { (TCity), (TSSC) }, + (TSSC) -- [bend right] (TStatus), + }; + { [edges=funcdep left] + (TSno) -- (TStatus), + (TSSC) -- [bend left] (TCity), + }; + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTSTPlusTC), (TTST) } -- (TSno), + }; + + { [edges=projection left] + { (TSTPlusTC), (TTSTPlusTC) } -- { (TST), (TTST) }, + (TTST) -- (TStatus), + (TSSC) -- [bend right] (TCity), + }; + + { [edges=projection right] + { (TSTPlusTC), (TTSTPlusTC) } -- { (TTC), (TTTC) }, + (TSSC) -- [bend left] (TStatus), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TTSTPlusTC) -- [bend right] (TSSC), + (TTTC) -- [bend right=10] (TSSC), + }; + (TTSTPlusTC) -- [projection right, bend right] (TSSC), + (TTTC) -- [edges=bijection,edge label'={\scriptsize\(\RelProject\)}, bend right=10] (TSSC), + }; + \end{tikzpicture} + } \\ + \(\schema{1} = \{S\}\) \\[\baselineskip] + \scalebox{0.4}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \& \& \node (TSno) {\(\Type{\Sno}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TST) -- (TTST), + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + (TTST) -- (TSno), + }; + + { [edges=projection left] + (TTST) -- (TStatus), + }; + }; + \end{tikzpicture} + } \\ + \(\schema{3} = \{\ST\}\) + \end{column} + \begin{column}{0.5\textwidth} + \centering + \scalebox{0.4}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \& \& \node (TSno) {\(\Type{\Sno}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \node (TTC) {\(\Type{\TC}\)}; \& \node (TTTC) {\(\TT{\TC}\)}; \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TST), (TTC) } -- { (TTST), (TTTC) }, + }; + + % FDs + { [edges=funcdep right] + (TSSC) -- [bend right] (TStatus), + }; + { [edges=funcdep left] + (TSno) -- (TStatus), + (TSSC) -- [bend left] (TCity), + }; + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTST) } -- (TSno), + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTTC) -- (TSSC), + }; + + { [edges=projection left] + (TTST) -- (TStatus), + (TSSC) -- [bend right] (TCity), + }; + + { [edges=projection right] + (TSSC) -- [bend left] (TStatus), + }; + }; + \end{tikzpicture} + } \\ + \(\schema{2} = \{\ST, \TC\}\) \\[\baselineskip] + \scalebox{0.4}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \&[7mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TTC) {\(\Type{\TC}\)}; \& \node (TTTC) {\(\TT{\TC}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TTC) } -- { (TTTC) }, + }; + + % FDs + { [edges=funcdep right] + (TSSC) -- [bend right] (TStatus), + }; + { [edges=funcdep left] + (TSSC) -- [bend left] (TCity), + }; + + % projection edges + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTTC) -- (TSSC), + }; + + { [edges=projection left] + (TSSC) -- [bend right] (TCity), + }; + + { [edges=projection right] + (TSSC) -- [bend left] (TStatus), + }; + }; + \end{tikzpicture} + } \\ + \(\schema{4} = \{\TC\}\) + \end{column} + \end{columns} + \bigskip + + \structurebf{Results:} \(\schema{1}\) isn't comparable with any of \(\schema{2}\), \(\schema{3}\), or \(\schema{4}\) {\tiny (as expected)} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{More examples} + \framesubtitle{(Lossy one to one join views, Date Ch. 6)} + + \(\ST\{\Sno, \Status\}\), \(\SC\{\Sno, \City\}\); view \(S = \ST \RelNaturalJoin \SC\) + \medskip\bigskip + + \begin{columns} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \&[7mm] \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \node (TSTPlusSC) {\(\Type{S}\)}; \& \node (TTSTPlusSC) {\(\TT{S}\)}; \& \node (TSno) {\(\Type{\Sno}\)}; \& \node (TSSC) {\(\Type{\Status} \times \Type{\City}\)}; \\ + \& \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TSTPlusSC) -- (TTSTPlusSC), + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + (TSno) -- [funcdep right] (TCity); + (TSno) -- [funcdep right] (TSSC); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTSTPlusSC) } -- (TSno), + }; + + { [edges=projection left] + (TSSC) -- (TCity), + }; + + { [edges=projection right] + (TSSC) -- (TStatus), + }; + + % insert "gaps" into crossed edges + { [edges={white,line width=1.5mm}] + (TTSTPlusSC) -- [bend right] (TSSC), + }; + (TTSTPlusSC) -- [projection right, bend right] (TSSC), + }; + \end{tikzpicture} + } \\ + \(\schema{1} = \{S\}\) + \end{column} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \& \& \node (TSno) {\(\Type{\Sno}\)}; \& \\ + \node (TSC) {\(\Type{\SC}\)}; \& \node (TTSC) {\(\TT{\SC}\)}; \& \& \node (TCity) {\(\Type{\City}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + { (TST), (TSC) } -- { (TTST), (TTSC) }, + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + (TSno) -- [funcdep right] (TCity); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + { (TTST) } -- (TSno), + }; + + { [edges=bijection,edge label'={\scriptsize\(\RelProject\)}] + (TTSC) -- (TSno), + }; + + { [edges=projection left] + (TTST) -- (TStatus), + }; + + { [edges=projection right] + (TTSC) -- (TCity), + }; + }; + \end{tikzpicture} + } \\ + \(\schema{2} = \{\ST, \SC\}\) + \end{column} + \begin{column}{0.33\textwidth} + \centering + \scalebox{0.5}{% + \begin{tikzpicture} + \matrix[row sep=1.5cm,ampersand replacement=\&] + { + \node (TST) {\(\Type{\ST}\)}; \&[7mm] \node (TTST) {\(\TT{\ST}\)}; \&[10mm] \&[10mm] \node (TStatus) {\(\Type{\Status}\)}; \\ + \& \& \node (TSno) {\(\Type{\Sno}\)}; \\ + }; + + \graph{ + % relation types to tuple types + { [edges=surtotal] + (TST) -- (TTST), + }; + + % FDs + (TSno) -- [funcdep left] (TStatus); + + % projection edges + { [edges=bijection,edge label={\scriptsize\(\RelProject\)}] + (TTST) -- (TSno), + }; + + { [edges=projection left] + (TTST) -- (TStatus), + }; + }; + \end{tikzpicture}% + } \\ + \(\schema{3} = \{\ST\}\) + \end{column} + \end{columns} + \bigskip\medskip + + \structurebf{Results:} \(\schema{1}\) isn't comparable with either \(\schema{2}\) or \(\schema{3}\) {\tiny (as expected)} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \frametitle{Now what?} + + \begin{itemize} + + \item Is this a useful technique? {\tiny (working on analysing more complex examples)} + + \item Are inclusion dependencies important? \\ + If so, how to represent them? + + \item Do we need the whole transformation process? Determining whether or not all constraints can be propagated from the base schema may already be enough. + + \item Could it help provide a more formal basis for Date’s “pragma”? + + \item Might it reveal some interesting new insights about the view update problem? + + \end{itemize} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\frame +{ + \centering\Huge + \structurebf{Questions?} +} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\againframe<3>{frame.SIG.example} + +\againframe<2>{frame.SIG.Sone} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +\end{document}