% APCCM2017_Stanger.tex
% Author: Nigel Stanger
%
% Built using Tex Live 2016 distribution.
% All packages except perhaps PGF should be in the standard TeX Live packages.
% REQUIRES PGF v3.0 or later for diagrams (custom arrow tips).
% REQUIRES TeX Gyre fonts (newtxmath package).
% NOTE: the last two figures use a small amount of colour.
%
% Revisions: 22 Aug 2016 Initial submission.
% 07 Nov 2016 Camera-ready version.
%%
%% MAX 10 PAGES (all material)
%%
\documentclass{article}
\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{bm}
\usepackage{subfig}
\usepackage{booktabs}
\usepackage[margin=1in]{geometry}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usetikzlibrary{graphs}
\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{calc}
\usetikzlibrary{arrows}
% Relational algebra operators
\newcommand{\RelRestrict}{\ensuremath{\sigma}}
\newcommand{\RelProject}{\ensuremath{\pi}}
\newcommand{\RelUnion}{\ensuremath{\cup}}
\newcommand{\RelIntersect}{\ensuremath{\cap}}
\newcommand{\RelJoin}{\ensuremath{\Join}}
% "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 SIG diagrams in 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={blue,thick},
input delete/.style={blue!40,thick,dashed},
output/.style={red,thick},
output temp/.style={red,thick,dashed},
path 1/.style={green!60!black,thick},
path 2/.style={orange,thick},
}
% 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}}
\newcommand{\eqnnumber}{\refstepcounter{equation}(\theequation)}
\hyphenation{co-pied sche-ma}
\pagestyle{empty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
% OUTLINE (20 mins max)
% Quick overview of view update problem and Date's effort
% - problem: Date's approach appears little different from earlier metadata-heavy approaches
% - problem: effectively punts on the hardest and most interesting cases
% - problem: operational definition of information equivalence
% - not focusing on view update problem, but rather how it can be characterised
% Quick overview of information capacity
% - relative measure, not quantitative
% - designed for relational schemas, so ideal
% - basic concepts of SIG transformation and isomorphism
% - my notation extensions
% Examples:
% - quickly go through restriction view example in more detail
% - other examples (summary): projection views, join views?
% Future work?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Disjoint restriction views (Date, Chapter 4)}
\label{sec-disjoint-restriction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relvars}
\begin{itemize}
\item base relvar \(S\{\Sno, \Sname, \Status, \City\}\)
\item view \(\LS = \RelRestrict_{\City = \mathit{'London'}}S\) [London suppliers] \eqnnumber\label{eqn-ls}
\item view \(\NLS = \RelRestrict_{\City \ne \mathit{'London'}}S\) [non-London suppliers] \eqnnumber\label{eqn-nls}
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tuple types}
\begin{align}
\TT{S} &= \Type{\Sno} \times \Type{\Sname} \times \Type{\Status} \times \Type{\City} \nonumber \\
\TT{\LS} &= \Type{\Sno} \times \Type{\Sname} \times \Type{\Status} \times \CityLondon \nonumber \\
\TT{\NLS} &= \Type{\Sno} \times \Type{\Sname} \times \Type{\Status} \times (\TCityMinusLondon) \nonumber
\end{align}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Base schema \(\bm{\schema{0} = \{S, \LS, \NLS\}}\)}
\begin{ConstraintList}
\item\label{constraint-restrict-key} \Sno\ is a key for each of \(S\), \(\LS\), and \(\NLS\), so the functional dependency \(\{\Sno\} \rightarrow \{\Sname, \Status, \City\}\) also holds in each of (a) \(S\); (b) \(\LS\); and (c) \(\NLS\).
% not sure how relevant the FK constraints are?
% how to represent? FK is a subset of the original key, so selection edge between S.Sno and each of LS.Sno and NLS.Sno
% or perhaps a selection edge from Sno to itself? (labelled FK)
% Notation: \Type{\Sno}, \Type{\LS.\Sno}, \Type{\NLS.\Sno}?
\item\label{constraint-restrict-lsfk} \(\RelProject_{\{\Sno\}}\LS \subseteq \RelProject_{\{\Sno\}}S\) [foreign key from \(\LS\) to \(S\)]
\item\label{constraint-restrict-nlsfk} \(\RelProject_{\{\Sno\}}\NLS \subseteq \RelProject_{\{\Sno\}}S\) [foreign key from \(\NLS\) to \(S\)]
\item\label{constraint-restrict-union} \(S = \LS \RelUnion \NLS\) [from (\ref{eqn-ls}) and (\ref{eqn-nls}) above]
\item\label{constraint-restrict-notlondon} \(\RelRestrict_{\City \ne \mathit{'London'}}\LS = \emptyset\) [from (\ref{eqn-ls}) above]
\item\label{constraint-restrict-london} \(\RelRestrict_{\City = \mathit{'London'}}\NLS = \emptyset\) [from (\ref{eqn-nls}) above]
\item\label{constraint-restrict-disjoint} \(\LS \RelIntersect \NLS = \emptyset\) [from \Constraint{\ref{constraint-restrict-notlondon}} and \Constraint{\ref{constraint-restrict-london}}]
\item\label{constraint-restrict-relation-type-union} (a) \(\Type{S} = \Type{\LS} \RelUnion \Type{\NLS}\); (b) \(\TT{S} = \TT{\LS} \RelUnion \TT{\NLS}\) [from \Constraint{\ref{constraint-restrict-union}}]
\item\label{constraint-restrict-relation-types} (a) \(\Type{\LS} \subset \Type{S}\); (b) \(\TT{\LS} \subset \TT{S}\) [from (\ref{eqn-ls}) above]
\item\label{constraint-restrict-tuple-types} (a) \(\Type{\NLS} \subset \Type{S}\); (b) \(\TT{\NLS} \subset \TT{S}\) [from (\ref{eqn-nls}) above]
\item\label{constraint-restrict-implied-types-london} \(\CityLondon \subset \Type{\City}\)
\item\label{constraint-restrict-implied-types-nonlondon} \((\TCityMinusLondon) \subset \Type{\City}\)
\item\label{constraint-restrict-implied-types-TSSL} \(\TSSL \subset \TSSC\)
\item\label{constraint-restrict-implied-types-TSSNL} \(\TSSNL \subset \TSSC\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{1} = \{S\}}\)}
\noindent A user granted access only to \(\schema{1}\) can see only relvar \(S\). Constraint \Constraint{\ref{constraint-restrict-key}}(a) can be propagated directly from \(\schema{0}\) into \(\schema{1}\) as it is already expressed in terms of \(S\) only. Constraints \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}} do not include any named relvars in \(\schema{0}\), and thus can also be propagated directly from \(\schema{0}\) into \(\schema{1}\). Constraints \Constraint{\ref{constraint-restrict-key}}(b), \Constraint{\ref{constraint-restrict-key}}(c), and \Constraint{\ref{constraint-restrict-union}}--\Constraint{\ref{constraint-restrict-tuple-types}} cannot be propagated directly from \(\schema{0}\) into \(\schema{1}\), but can all be rewritten in terms of \(S\) only, by substituting the definitions of \(\LS\) (equation~\ref{eqn-ls}) and \(\NLS\) (equation~\ref{eqn-nls}). To simplify expressions, we shall use \(\LSsub\) to denote \(\RelRestrict_{\City = \mathit{'London'}}S\) (\ref{eqn-ls}) and \(\NLSsub\) to denote \(\RelRestrict_{\City \ne \mathit{'London'}}S\) (\ref{eqn-nls}). (This also clearly distinguishes the substitutions from the \(\LS\) and \(\NLS\) relvars in \(\schema{0}\), \(\schema{2}\), and \(\schema{3}\).)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-i-restrict}
\begin{ConstraintList}[\schema{1}]
\item \Sno\ is a key for each of \(\LSsub\) and \(\NLSsub\), therefore the functional dependency \(\{\Sno\} \rightarrow \{\Sname, \Status, \City\}\) also holds in each of (b) \(\LSsub\); and (c) \(\NLSsub\). [The fact that we are dealing with two disjoint subsets of \(\City\) does not change this.]
\setcounter{constraint}{3}
\item \(S = \LSsub \RelUnion \NLSsub\) [or even just \(S = S\)]
\item \(\RelRestrict_{\City \ne \mathit{'London'}}\LSsub = \emptyset\)
\item \(\RelRestrict_{\City = \mathit{'London'}}\NLSsub = \emptyset\)
\item \(\LSsub \RelIntersect \NLSsub = \emptyset\)
\item (a) \(\Type{S} = \Type{\LSsub} \RelUnion \Type{\NLSsub}\); (b) \(\TT{S} = \TT{\LSsub} \RelUnion \TT{\NLSsub}\) \newline
{[or even just \(\Type{S} = \Type{S}\) and \(\TT{S} = \TT{S}\)]}
\item (a) \(\Type{\LSsub} \subset \Type{S}\); (b) \(\TT{\LSsub} \subset \TT{S}\)
\item (a) \(\Type{\NLSsub} \subset \Type{S}\); (b) \(\TT{\NLSsub} \subset \TT{S}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-i-restrict}
\noindent The constraints appearing in \(\schema{1}\) are \Constraint{\ref{constraint-restrict-key}}(a), \Constraint[\schema{1}]{\ref{constraint-restrict-key}}(b), \Constraint[\schema{1}]{\ref{constraint-restrict-key}}(c), \Constraint[\schema{1}]{\ref{constraint-restrict-union}}--\Constraint[\schema{1}]{\ref{constraint-restrict-tuple-types}}, and \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}}. The constraints within the schema also imply the existence of several subtype nodes (e.g., the two subtypes of \(\Type{City}\) implied by \Constraint{\ref{constraint-restrict-implied-types-london}} and \Constraint{\ref{constraint-restrict-implied-types-nonlondon}}), along with corresponding selection and projection edges. \Constraint[\schema{1}]{\ref{constraint-restrict-union}}, \Constraint[\schema{1}]{\ref{constraint-restrict-relation-type-union}}(a), and \Constraint[\schema{1}]{\ref{constraint-restrict-relation-type-union}}(b) are effectively tautologies that add no new information, and can thus be safely ignored. The completed SIG for \(\schema{1}\) is shown in Figure~\ref{fig-sig-s-i-restrict}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=0.5cm]
{
\node (TLS) {\(\Type{\LSsub}\)}; &[7mm] \node (TTLS) {\(\TT{\LSsub}\)}; &[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) {\(\Type{\NLSsub}\)}; & \node (TTNLS) {\(\TT{\NLSsub}\)}; & & & \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),
};
\end{tikzpicture}
\caption{SIG for schema \(\schema{1} = \{S\}\).}
\label{fig-sig-s-i-restrict}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{2} = \{\LS, \NLS\}}\)}
\noindent A user granted access only to \(\schema{2}\) can see only relvars \(\LS\) and \(\NLS\). Constraints \Constraint{\ref{constraint-restrict-key}}(b), \Constraint{\ref{constraint-restrict-key}}(c), and \Constraint{\ref{constraint-restrict-notlondon}}--\Constraint{\ref{constraint-restrict-disjoint}} can be propagated directly from \(\schema{0}\) into \(\schema{2}\) as they are defined only in terms of \(\LS\) and \(\NLS\). \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}} can be propagated directly into \(\schema{2}\) as they are not expressed in terms of any named relvars in \(\schema{0}\). \Constraint{\ref{constraint-restrict-key}}(a), \Constraint{\ref{constraint-restrict-union}}, \Constraint{\ref{constraint-restrict-relation-type-union}}, \Constraint{\ref{constraint-restrict-relation-types}}, and \Constraint{\ref{constraint-restrict-tuple-types}} can be rewritten in terms of \(\LS\) and \(\NLS\) only.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-ii-restrict}
\begin{ConstraintList}[\schema{2}]
\item \Sno\ is a key for \(\LS \RelUnion \NLS\), therefore the functional dependency \(\{\Sno\} \rightarrow \{\Sname, \Status, \City\}\) also holds in (a) \(\LS \RelUnion \NLS\).
\setcounter{constraint}{3}
\item \(\LS \RelUnion \NLS = \LS \RelUnion \NLS\)
\setcounter{constraint}{7}
\item (a) \(\Type{\LS} \RelUnion \Type{\NLS} = \Type{\LS} \RelUnion \Type{\NLS}\); \newline
(b) \(\TT{\LS} \RelUnion \TT{\NLS} = \TT{\LS} \RelUnion \TT{\NLS}\)
\item (a) \(\Type{\LS} \subset \Type{\LS} \RelUnion \Type{\NLS}\); (b) \(\TT{\LS} \subset \TT{\LS} \RelUnion \TT{\NLS}\)
\item (a) \(\Type{\NLS} \subset \Type{\LS} \RelUnion \Type{\NLS}\); (b) \(\TT{\NLS} \subset \TT{\LS} \RelUnion \TT{\NLS}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-ii-restrict}
\noindent The constraints appearing in \(\schema{2}\) are \Constraint[\schema{2}]{\ref{constraint-restrict-key}}(a), \Constraint{\ref{constraint-restrict-key}}(b), \Constraint{\ref{constraint-restrict-key}}(c), \Constraint[\schema{2}]{\ref{constraint-restrict-union}}, \Constraint{\ref{constraint-restrict-notlondon}}--\Constraint{\ref{constraint-restrict-disjoint}}, \Constraint[\schema{2}]{\ref{constraint-restrict-relation-type-union}}--\Constraint[\schema{2}]{\ref{constraint-restrict-tuple-types}}, and \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}}. This is essentially the same set of constraints as \(\schema{1}\), but with different rewritings. This means that the SIG for \(\schema{2}\) can be built in the same manner as for \(\schema{1}\), with some nodes named differently. In particular, \Constraint[\schema{2}]{\ref{constraint-restrict-relation-type-union}} implies that there will be nodes \(\TLSPlusNLS\) and \(\TTLSPlusNLS\) instead of \(\Type{S}\) and \(\TT{S}\), respectively. There will also be \(\Type{\LS}\) instead of \(\Type{\LSsub}\), etc. The complete SIG for \(\schema{2}\) is shown in Figure~\ref{fig-sig-s-ii-restrict}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\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),
};
\end{tikzpicture}
\caption{SIG for schema \(\schema{2} = \{\LS, \NLS\}\).}
\label{fig-sig-s-ii-restrict}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-chema \(\bm{\schema{3} = \{LS\}}\)}
\noindent A user granted access only to \(\schema{3}\) can see only relvar \(\LS\). Constraints \Constraint{\ref{constraint-restrict-key}}(b) and \Constraint{\ref{constraint-restrict-notlondon}} can be propagated directly into \(\schema{3}\), as they are defined in terms of \(\LS\) only. \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}} can also be propagated directly into \(\schema{3}\) as previously discussed. The remaining constraints cannot be rewritten in terms of \(\LS\) only, and so cannot be propagated into \(\schema{3}\). As we were able to propagate all constraints into \(\schema{1}\), this indicates a qualitative difference between \(\schema{1}\) and \(\schema{3}\). It therefore seems likely that the relative information capacities of \(\schema{1}\) and \(\schema{3}\) will also differ.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-iii-restrict}
\noindent N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-iii-restrict}
\noindent The constraints appearing in \(\schema{3}\) are \Constraint{\ref{constraint-restrict-key}}(b), \Constraint{\ref{constraint-restrict-notlondon}}, and \Constraint{\ref{constraint-restrict-implied-types-london}}--\Constraint{\ref{constraint-restrict-implied-types-TSSNL}}. The SIG will only include edges and nodes that relate either directly to \(\LS\) or are independent of any relvar, such as the subtype node \(\TSSNL\). The complete SIG for \(\schema{3}\) is shown in Figure~\ref{fig-sig-s-iii-restrict} on the previous page.
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}
\centering
\begin{tikzpicture}
\matrix[row sep=0.5cm]
{
\node (TLS) {\(\Type{\LS}\)}; &[7.5mm] \node (TTLS) {\(\TT{\LS}\)}; &[7mm] &[4mm] &[-4mm] \node (TSSL) {\(\StackTSSL\)}; & & \node (LSCity) {\(\CityLondon\)}; \\
& & & \node (TSname) {\(\Type{\Sname}\)}; \\
& & \node (TSno) {\(\Type{\Sno}\)}; & & \node (TSSC) {\(\StackTSSC\)}; & & \node (TCity) {\(\Type{City}\)}; \\
& & & & & \node (TStatus) {\(\Type{\Status}\)}; \\
& & & & \node (TSSNL) {\(\StackTSSNL\)}; & & \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\
};
\graph{
% relation types to tuple types
{ [edges=surtotal]
(TLS) -- (TTLS),
};
% projection edges
{ [edges=bijection,edge label={\scriptsize\(\RelProject\)}]
(TTLS) -- (TSno)
};
{ [edges=projection left]
(TTLS) -- (TSSL),
(TSSL) -- { (TStatus), (LSCity) },
};
{ [edges=projection right]
(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),
};
% insert "gaps" into crossed edges
{ [edges={white,line width=1.5mm}]
(TSno) -- (TSSC),
(TSSC) -- (TCity),
};
(TSno) -- [funcdep right] (TSSC);
(TSSC) -- [projection left] (TCity);
};
\end{tikzpicture}
\caption{SIG for schema \(\schema{3} = \{\LS\}\).}
\label{fig-sig-s-iii-restrict}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Transformations}
\label{sec-transforming-restrict}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{2}}\)}
\noindent Looking at the SIGs for \(\schema{1}\) and \(\schema{2}\), we can see almost immediately that both SIGs have the same node and edge structure; indeed the only difference is in the names of some of the nodes. However, we already know from the discussion in Sections~\ref{sec-constraints-s-i-restrict} and~\ref{sec-constraints-s-ii-restrict} that these differently named nodes are just rewritings that represent the same domains. We therefore have an immediate isomorphism between the two SIGs and can conclude that the information capacities of \(\schema{1}\) and \(\schema{2}\) are equivalent, i.e., \(\Equivalent{\schema{1}}{\schema{2}}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{3}}\)}
There are some shared structures, but the two SIGs are clearly different. Since SIG transformations only ever preserve or enhance information capacity, intuitively we should attempt to transform the ``smaller'' SIG for \(\schema{3}\) into the ``larger'' SIG for \(\schema{1}\).
First, duplicate node \(\Type{\LS}\) to \(\Type{S}\) and node \(\TT{\LS}\) to \(\TT{S}\). To obtain a node structure similar to that of \(\schema{1}\), we also need to further duplicate \(\Type{S}\) to \(\Type{\NLS}\) and \(\TT{S}\) to \(\TT{\NLS}\). The result of these duplications is shown in Figure~\ref{fig-transform-all-duplicates}. The transformed SIG now has the same node structure as that for \(\schema{1}\).
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[t]
\centering
\begin{tikzpicture}
\matrix[row sep=0.5cm]
{
\node [input keep] (TLS) {\(\Type{\LS}\)}; &[7mm] \node [input keep] (TTLS) {\(\TT{\LS}\)}; &[7mm] &[4mm] &[-4mm] \node (TSSL) {\(\StackTSSL\)}; & & \node (LSCity) {\(\CityLondon\)}; \\
& & & \node (TSname) {\(\Type{\Sname}\)}; \\
\node [output] (TLSPlusNLS) {\(\Type{S}\)}; & \node [output] (TTLSPlusNLS) {\(\TT{S}\)}; & \node (TSno) {\(\Type{\Sno}\)}; & & \node (TSSC) {\(\StackTSSC\)}; & & \node (TCity) {\(\Type{City}\)}; \\
& & & & & \node (TStatus) {\(\Type{\Status}\)}; \\
\node [output] (TNLS) {\(\Type{\NLS}\)}; & \node [output] (TTNLS) {\(\TT{\NLS}\)}; & & & \node (TSSNL) {\(\StackTSSNL\)}; & & \node (NLSCity) {\(\StackTCityMinusLondon\)}; \\
};
\graph{
% relation types to tuple types
{ [edges=surtotal]
(TLS) -- (TTLS),
};
% projection edges
{ [edges=bijection,edge label={\scriptsize\(\RelProject\)}]
(TTLS) -- (TSno)
};
{ [edges=projection left]
(TTLS) -- (TSSL),
(TSSL) -- { (TStatus), (LSCity) },
};
{ [edges=projection right]
(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,output},edge label'={\scriptsize\(\RelRestrict\)}]
{ (TLS), (TTLS) } -- { (TLSPlusNLS), (TTLSPlusNLS) },
{ (TLSPlusNLS), (TTLSPlusNLS) } -- { (TNLS), (TTNLS) },
};
% insert "gaps" into crossed edges
{ [edges={white,line width=1.5mm}]
(TSno) -- (TSSC),
(TSSC) -- (TCity),
};
(TSno) -- [funcdep right] (TSSC);
(TSSC) -- [projection left] (TCity);
% transformation indicators
{ [edges={->,gray,dashed,bend left=45}]
(TLS) -- [edge node={node[sloped,above]{\small\emph{copy}}}] (TLSPlusNLS),
(TLSPlusNLS) -- [edge node={node[sloped,above,rotate=180]{\small\emph{copy}}}] (TNLS)
};
};
\end{tikzpicture}
\caption{SIG for transformed schema \(\schema{3}'\) after duplicating \Type{\LS} and \TT{\LS} to produce analogues of the additional nodes in \(\schema{1}\). Inputs to the transformations are coloured \textcolor{blue}{blue}, outputs are coloured \textcolor{red}{red}. [\(\equiv\)]}
\label{fig-transform-all-duplicates}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
The next phase is to copy and move edges. To produce the edge \(\Type{S} \SurTotal \TT{S}\), we can first \emph{copy} \(\Type{\LS} \SurTotal \TT{\LS}\) across the path \(\TT{S} \TrivialSelection \TT{\LS}\) (giving \(\Type{\LS} \SurTotal \TT{S}\)), then \emph{move} it across \(\Type{S} \TrivialSelection \Type{\LS}\). We can carry out a similar series of transformations to copy and move \(\Type{S} \SurTotal \TT{S}\) to \(\Type{\NLS} \SurTotal \TT{\NLS}\) (see Figure~\ref{fig-transform-edge-moves}).
We next copy and move the unique projection edge \(\TT{\LS} \TrivialProjection \Type{\Sno}\) to produce the edges \(\TT{S} \TrivialProjection \Type{\Sno}\) and \(\TT{\NLS} \TrivialProjection \Type{\Sno}\). Similarly, we copy and move \(\TT{\LS} \ProjectionEdge \TSSL\) to produce \(\TT{S} \LabelledEdge{\sigedge{12}}{\RelProject} \TSSC\) and \(\TT{\NLS} \LabelledEdge{\sigedge{02}}{\RelProject} \TSSNL\). Note that the first edge in the latter pair of transformations loses its totality annotation, and the second edge its surjectivity annotation, as a result of composition with the pre-existing non-bijective selection edges between the constructed tuple types running vertically down the centre of the SIG.
Finally, we carry out similar copy and move transformations to copy the key edge \(\Type{\Sno} \KeyEdge \TSSC\) to \(\Type{\Sno} \LabelledEdge{\sigedge{03}}{\mathit{key}} \TSSL\), and \(\Type{\Sno} \LabelledEdge{\sigedge{03}}{\mathit{key}} \TSSNL\). Both new edges lose their totality annotations for the same reason as the projection edges above. The final result of all these edge transformations is shown in Figure~\ref{fig-transform-edge-moves}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[t]
\centering
\begin{tikzpicture}
\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) {\(\Type{S}\)}; & \node (TTLSPlusNLS) {\(\TT{S}\)}; & \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) -- [input keep,edge node={node (c1a) {}}] (TTLS),
(TLSPlusNLS) -- [output,edge node={node (c1b) {}}] (TTLSPlusNLS),
(TNLS) -- [output,edge node={node (c1c) {}}] (TTNLS),
};
% FDs
(TSno) -- [funcdep left,arrows={-{crossbar}>},bend left,output] (TSSL);
(TSno) -- [funcdep right,arrows={-{crossbar}>},output] (TSSNL);
% projection edges
{ [edges=bijection,edge label={\scriptsize\(\RelProject\)}]
(TTLS) -- [input keep] (TSno),
(TTLSPlusNLS) -- [output] (TSno),
};
{ [edges=bijection,edge label'={\scriptsize\(\RelProject\)}]
(TTNLS) -- [output] (TSno),
};
{ [edges=projection left]
(TTLS) -- [input keep,edge node={node (c2a) {}}] (TSSL),
(TSSL) -- { (TStatus), (LSCity) },
};
{ [edges=projection right]
(TSSC) -- { (TSname), (TStatus) },
(TSSL) -- (TSname),
(TSSNL) -- { (NLSCity), (TStatus) },
(TSSNL) -- [bend left=10] (TSname),
(TTNLS) -- [arrows={:->},output,edge node={node (c2c) {}}] (TSSNL),
};
% selection edges
{ [edges=selection left]
(TSSC) -- { (TSSL), (TSSNL) },
(TCity) -- (NLSCity),
};
{ [edges=selection right]
(TCity) -- (LSCity),
};
{ [edges=bijection,edge label'={\scriptsize\(\RelRestrict\)}]
{ (TLS), (TTLS) } -- { (TLSPlusNLS), (TTLSPlusNLS) },
{ (TLSPlusNLS), (TTLSPlusNLS) } -- { (TNLS), (TTNLS) },
};
% insert "gaps" into crossed edges
{ [edges={white,line width=1.5mm}]
(TSno) -- (TSSC),
(TSSC) -- (TCity),
(TTLSPlusNLS) -- [bend right] (TSSC),
};
(TSno) -- [funcdep right,input keep] (TSSC);
(TSSC) -- [projection left] (TCity);
(TTLSPlusNLS) -- [projection right,arrows={:{crossbar}->},bend right,output,edge node={node (c2b) {}}] (TSSC),
% transformation indicators
{ [edges={->,gray,dashed}]
(c1a) -- (c1b),
(c1a) -- [bend right=12,edge node={node[above,sloped,pos=0.175]{\small\emph{copy \& move}}}] (c1c),
(c2a) -- [bend right=12] (c2b),
(c2a) -- [bend right=12,edge node={node[above,sloped,pos=0.175]{\small\emph{copy \& move}}}] (c2c)
};
};
\end{tikzpicture}
\caption{SIG for transformed schema \(\schema{3}'\) after copying and moving various edges. [\(\preceq\)]}
\label{fig-transform-edge-moves}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
If we compare Figure~\ref{fig-sig-s-i-restrict} with Figure~\ref{fig-transform-edge-moves}, we can see that the transformed SIG for \(\schema{3}'\) now has the same topology as the SIG for \(\schema{1}\). We still need to remove the totality annotations from the newly created trivial selection edges between the relation and tuple types on the left, but even when this is done, we do not achieve the desired isomorphism, as the edges \(\TT{S} \LabelledEdge{\sigedge{12}}{\RelProject} \TSSC\), \(\TT{\NLS} \LabelledEdge{\sigedge{02}}{\RelProject} \TSSNL\), \(\Type{\Sno} \LabelledEdge{\sigedge{03}}{\mathit{key}} \TSSL\), and \(\Type{\Sno} \LabelledEdge{\sigedge{03}}{\mathit{key}} \TSSNL\) all have different annotations from the corresponding edges in the SIG for \(\schema{1}\). This clearly shows that the information capacities of \(\schema{1}\) and \(\schema{3}\) are incomparable, and that view updates based on this pair of schemas will be problematic.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Additional notes}
If we were to create a fourth sub-schema \(\schema{4} = \{\NLS\}\) and compare this with \(\schema{1}\), the result would be similar to that for \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Nonloss projection views (Date, Chapter 5)}
\label{sec-nonloss-projection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relvars}
\begin{itemize}
\item base relvar \(S\{\Sno, \Status, \City\}\)
\item view \(\ST = \RelProject_{\{\Sno, \Status\}}S\) [supplier status] \eqnnumber\label{eqn-st}
\item view \(\SC = \RelProject_{\{\Sno, \City\}}S\) [supplier city] \eqnnumber\label{eqn-sc}
\end{itemize}
(Incidentally, the views form a 6NF nonloss decomposition of \(S\).)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tuple types}
\begin{align}
\TT{S} &= \Type{\Sno} \times \Type{\Status} \times \Type{\City} \nonumber \\
\TT{\ST} &= \Type{\Sno} \times \Type{\Status} \nonumber \\
\TT{\SC} &= \Type{\Sno} \times \Type{\City} \nonumber
\end{align}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Base schema \(\bm{\schema{0} = \{S, \ST, \SC\}}\)}
\begin{ConstraintList}
\item\label{constraint-project-key} \(\Sno\) is a key for each of \(S\), \(\ST\), and \(\SC\), so the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in each of (a) \(S\) and (b) \(\ST\); and the functional dependency \(\{\Sno\} \rightarrow \{\City\}\) holds in each of (c) \(S\) and (d) \(\SC\). [(a) and (c) could in principle be merged into a single functional dependency \(\{\Sno\} \rightarrow \{\Status, \City\}\) in \(S\).]
% not sure how relevant the FK constraints are?
% how to represent? FK is a subset of the original key, so selection edge between S.Sno and each of LS.Sno and NLS.Sno
% or perhaps a selection edge from Sno to itself? (labelled FK)
% Notation: \Type{\Sno}, \Type{\LS.\Sno}, \Type{\NLS.\Sno}?
\item\label{constraint-project-stfk} \(\RelProject_{\{\Sno\}}\ST \subseteq \RelProject_{\{\Sno\}}S\) [foreign key from \(\ST\) to \(S\)]
\item\label{constraint-project-scfk} \(\RelProject_{\{\Sno\}}\SC \subseteq \RelProject_{\{\Sno\}}S\) [foreign key from \(\SC\) to \(S\)]
\item\label{constraint-project-join} \(S = \SC \RelJoin \ST\) [from (\ref{eqn-st}), (\ref{eqn-sc})]
\item\label{constraint-project-s-st-identical} \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\ST\) [from \Constraint{\ref{constraint-project-join}}, (\ref{eqn-st})]
\item\label{constraint-project-s-sc-identical} \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\SC\) [from \Constraint{\ref{constraint-project-join}}, (\ref{eqn-sc})]
\item\label{constraint-project-st-sc-identical} \(\RelProject_{\{\Sno\}}\ST = \RelProject_{\{\Sno\}}\SC\) [from \Constraint{\ref{constraint-project-join}}, (\ref{eqn-st}), (\ref{eqn-sc})]
\item\label{constraint-project-relation-type-join} (a) \(\Type{S} = \Type{\ST} \RelJoin \Type{\SC}\); (b) \(\TT{S} = \TT{\ST} \RelJoin \TT{\SC}\) [from \Constraint{\ref{constraint-project-join}}]
\item\label{constraint-project-types-st} (a) \(\Type{\ST} = \RelProject_{\{\Sno, \Status\}}\Type{S}\); (b) \(\TT{\ST} = \RelProject_{\{\Sno, \Status\}}\TT{S}\) [from (\ref{eqn-st})]
\item\label{constraint-project-types-sc} (a) \(\Type{\SC} = \RelProject_{\{\Sno, \City\}}\Type{S}\); (b) \(\TT{\SC} = \RelProject_{\{\Sno, \City\}}\TT{S}\) [from (\ref{eqn-sc})]
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{1} = \{S\}}\)}
\noindent A user granted access only to \(\schema{1}\) can see only relvar \(S\). Constraints \Constraint{\ref{constraint-project-key}}(a) and \Constraint{\ref{constraint-project-key}}(c) can be propagated directly from \(\schema{0}\) into \(\schema{1}\) as they are already expressed in terms of \(S\) only. Constraints \Constraint{\ref{constraint-project-join}}--\Constraint{\ref{constraint-restrict-tuple-types}} cannot be propagated directly from \(\schema{0}\) into \(\schema{1}\), but can all be rewritten in terms of \(S\) only, by substituting the definitions of \(\ST\) (equation~\ref{eqn-st}) and \(\SC\) (equation~\ref{eqn-sc}), i.e., \(\STsub = \RelProject_{\{\Sno, \Status\}}S\) and \(\SCsub = \RelProject_{\{\Sno, \City\}}S\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-i-project}
\begin{ConstraintList}[\schema{1}]
\item \Sno\ is a key for each of \(\STsub\) and \(\SCsub\), therefore the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in (b) \(\STsub\), and the functional dependency \(\{\Sno\} \rightarrow \{\City\}\) holds in (d) \(\SCsub\).
\setcounter{constraint}{3}
\item \(S = \STsub \RelJoin \SCsub\) [or even just \(S = S\)]
\item \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\STsub\)
\item \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\SCsub\)
\item \(\RelProject_{\{\Sno\}}\STsub = \RelProject_{\{\Sno\}}\SCsub\)
\item (a) \(\Type{S} = \Type{\STsub} \RelJoin \Type{\SCsub}\); (b) \(\TT{S} = \TT{\STsub} \RelJoin \TT{\SCsub}\) \newline
{[or even just \(\Type{S} = \Type{S}\) and \(\TT{S} = \TT{S}\)]}
\item (a) \(\Type{\STsub} = \RelProject_{\{\Sno, \Status\}}\Type{S}\); (b) \(\TT{\STsub} = \RelProject_{\{\Sno, \Status\}}\TT{S}\)
\item (a) \(\Type{\SCsub} = \RelProject_{\{\Sno, \City\}}\Type{S}\); (b) \(\TT{\SCsub} = \RelProject_{\{\Sno, \City\}}\TT{S}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-i-project}
\noindent The constraints appearing in \(\schema{1}\) are \Constraint{\ref{constraint-project-key}}(a), \Constraint[\schema{1}]{\ref{constraint-project-key}}(b), \Constraint{\ref{constraint-project-key}}(c), \Constraint[\schema{1}]{\ref{constraint-project-key}}(d), and \Constraint[\schema{1}]{\ref{constraint-project-join}}--\Constraint[\schema{1}]{\ref{constraint-project-types-sc}}. \Constraint[\schema{1}]{\ref{constraint-project-join}}, \Constraint[\schema{1}]{\ref{constraint-project-relation-type-join}}(a), and \Constraint[\schema{1}]{\ref{constraint-project-relation-type-join}}(b) are effectively tautologies that add no new information, and can thus be safely ignored. The completed SIG for \(\schema{1}\) is shown in Figure~\ref{fig-sig-s-i-project}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{1} = \{S\}\).}
\label{fig-sig-s-i-project}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{2} = \{\ST, \SC\}}\)}
\noindent A user granted access only to \(\schema{2}\) can see only relvars \(\ST\) and \(\SC\). Constraints \Constraint{\ref{constraint-project-key}}(b), \Constraint{\ref{constraint-project-key}}(d), and \Constraint{\ref{constraint-project-st-sc-identical}} can be propagated directly from \(\schema{0}\) into \(\schema{2}\) as they are already expressed in terms of \(\ST\) and \(\SC\) only. The remaining constraints cannot be propagated directly from \(\schema{0}\) into \(\schema{2}\), but can all be rewritten in terms of \(\ST\) and \(\SC\) only, by substituting \(J = \ST \RelJoin \SC\) for \(S\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-ii-project}
\begin{ConstraintList}[\schema{2}]
\item \Sno\ is a key for \(J\), therefore (a) the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in \(J\), and (c) the functional dependency \(\{\Sno\} \rightarrow \{\City\}\) holds in \(J\).
\setcounter{constraint}{3}
\item \(J = \ST \RelJoin \SC\) [or even just \(\ST \RelJoin \SC = \ST \RelJoin \SC\)]
\item \(\RelProject_{\{\Sno\}}J = \RelProject_{\{\Sno\}}\ST\)
\item \(\RelProject_{\{\Sno\}}J = \RelProject_{\{\Sno\}}\SC\)
\setcounter{constraint}{7}
\item (a) \(\Type{J} = \Type{\ST} \RelJoin \Type{\SC}\); (b) \(\TT{J} = \TT{\ST} \RelJoin \TT{\SC}\)
\item (a) \(\Type{\ST} = \RelProject_{\{\Sno, \Status\}}\Type{J}\); (b) \(\TT{\ST} = \RelProject_{\{\Sno, \Status\}}\TT{J}\)
\item (a) \(\Type{\SC} = \RelProject_{\{\Sno, \City\}}\Type{J}\); (b) \(\TT{\SC} = \RelProject_{\{\Sno, \City\}}\TT{J}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-ii-project}
\noindent The constraints appearing in \(\schema{2}\) are \Constraint[\schema{2}]{\ref{constraint-project-key}}(a), \Constraint{\ref{constraint-project-key}}(b), \Constraint[\schema{2}]{\ref{constraint-project-key}}(c), \Constraint{\ref{constraint-project-key}}(d), \Constraint[\schema{2}]{\ref{constraint-project-join}}--\Constraint[\schema{2}]{\ref{constraint-project-s-sc-identical}}, \Constraint{\ref{constraint-project-st-sc-identical}}, and \Constraint[\schema{2}]{\ref{constraint-project-relation-type-join}}--\Constraint[\schema{2}]{\ref{constraint-project-types-sc}}. \Constraint[\schema{2}]{\ref{constraint-project-join}} is effectively a tautology that adds no new information, and can be ignored. The completed SIG for \(\schema{2}\) is shown in Figure~\ref{fig-sig-s-ii-project}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{2} = \{\ST, \SC\}\).}
\label{fig-sig-s-ii-project}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{3} = \{\ST\}}\)}
\noindent A user granted access only to \(\schema{3}\) can see only relvar \(\ST\). Only constraint \Constraint{\ref{constraint-project-key}}(b) can be propagated directly from \(\schema{0}\) into \(\schema{3}\) as it is the only one expressed in terms of \(\ST\) only. None of the remaining constraints can be rewritten in terms of \(\ST\) only, and so cannot be propagated into \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-iii-project}
N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-iii-project}
\noindent The only constraint appearing in \(\schema{3}\) is \Constraint{\ref{constraint-project-key}}(b). The SIG will only include edges and nodes that relate either directly to \(\ST\) or are independent of any relvar. The completed SIG for \(\schema{3}\) is shown in Figure~\ref{fig-sig-s-iii-project}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{3} = \{\ST\}\).}
\label{fig-sig-s-iii-project}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Transformations}
\label{sec-transforming-project}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{2}}\)}
\noindent The SIGs for \(\schema{1}\) and \(\schema{2}\) are immediately isomorphic, so \(\Equivalent{\schema{1}}{\schema{2}}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{3}}\)}
Despite their differences, it's clear that the comparison between \(\schema{1}\) and \(\schema{3}\) for projection views will be similar to that for disjoint restriction views (Section~\ref{sec-transforming-restrict}), as the SIG structures are topologically similar. It's therefore reasonable to conclude that the information capacities of \(\schema{1}\) and \(\schema{3}\) are incomparable, and that view updates based on this pair of schemas will be problematic.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Additional notes}
If we were to create a fourth sub-schema \(\schema{4} = \{\SC\}\) and compare this with \(\schema{1}\), the result would be similar to that for \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Lossy projection views (Date, Chapter 5)}
\label{sec-lossy-projection}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relvars}
\begin{itemize}
\item base relvar \(S\{\Sno, \Status, \City\}\)
\item view \(\ST = \RelProject_{\{\Sno, \Status\}}S\) [supplier status] \eqnnumber\label{eqn-st-lossy}
\item view \(\TC = \RelProject_{\{\Status, \City\}}S\) [status \& city] \eqnnumber\label{eqn-tc-lossy}
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tuple types}
\begin{align}
\TT{S} &= \Type{\Sno} \times \Type{\Status} \times \Type{\City} \nonumber \\
\TT{\ST} &= \Type{\Sno} \times \Type{\Status} \nonumber \\
\TT{\TC} &= \Type{\Status} \times \Type{\City} \nonumber
\end{align}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Base schema \(\bm{\schema{0} = \{S, \ST, \TC\}}\)}
\begin{ConstraintList}
\item\label{constraint-project-lossy-key} \(\Sno\) is a key for each of \(S\) and \(\ST\), so the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in each of (a) \(S\) and (b) \(\ST\); and the functional dependency \(\{\Sno\} \rightarrow \{\City\}\) holds in (c) \(S\). [(a) and (c) could in principle be merged into a single functional dependency \(\{\Sno\} \rightarrow \{\Status, \City\}\) in \(S\).]
\item\label{constraint-project-lossy-key-ii} \(\{\Status, \City\}\) is a key for \(\TC\), so the functional dependencies (a) \(\{\Status, \City\} \rightarrow \{\Status\}\) and (b) \(\{\Status, \City\} \rightarrow \{\City\}\) hold in \(\TC\).
% not sure how relevant the FK constraints are?
% how to represent? FK is a subset of the original key, so selection edge between S.Sno and each of LS.Sno and NLS.Sno
% or perhaps a selection edge from Sno to itself? (labelled FK)
% Notation: \Type{\Sno}, \Type{\LS.\Sno}, \Type{\NLS.\Sno}?
\item\label{constraint-project-lossy-stfk} \(\RelProject_{\{\Sno\}}\ST \subseteq \RelProject_{\{\Sno\}}S\) [foreign key from \(\ST\) to \(S\)]
\item\label{constraint-project-lossy-s-st-identical} \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\ST\) [from (\ref{eqn-st-lossy})]
\item\label{constraint-project-lossy-st-tc-status} \(\RelProject_{\{\Status\}}\ST = \RelProject_{\{\Status\}}\TC\) [from (\ref{eqn-tc-lossy})]
\item\label{constraint-project-lossy-types-st} (a) \(\Type{\ST} = \RelProject_{\{\Sno, \Status\}}\Type{S}\); (b) \(\TT{\ST} = \RelProject_{\{\Sno, \Status\}}\TT{S}\) [from (\ref{eqn-st-lossy})]
\item\label{constraint-project-lossy-types-tc} (a) \(\Type{\TC} = \RelProject_{\{\Status, \City\}}\Type{S}\); (b) \(\TT{\TC} = \RelProject_{\{\Status, \City\}}\TT{S}\) [from (\ref{eqn-tc-lossy})]
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{1} = \{S\}}\)}
\noindent A user granted access only to \(\schema{1}\) can see only relvar \(S\). Constraints \Constraint{\ref{constraint-project-lossy-key}}(a) and \Constraint{\ref{constraint-project-lossy-key}}(c) can be propagated directly from \(\schema{0}\) into \(\schema{1}\) as they are already expressed in terms of \(S\) only. Constraints \Constraint{\ref{constraint-project-lossy-key-ii}} and \Constraint{\ref{constraint-project-lossy-s-st-identical}}--\Constraint{\ref{constraint-project-lossy-types-tc}} cannot be propagated directly from \(\schema{0}\) into \(\schema{1}\), but can all be rewritten in terms of \(S\) only, by substituting the definitions of \(\ST\) (equation~\ref{eqn-st-lossy}) and \(\TC\) (equation~\ref{eqn-tc-lossy}), i.e., \(\STsub = \RelProject_{\{\Sno, \Status\}}S\) and \(\TCsub = \RelProject_{\{\Status, \City\}}S\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-i-project-lossy}
\begin{ConstraintList}[\schema{1}]
\item \(\Sno\) is a key for \(\STsub\), therefore the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in (b) \(\STsub\).
\item \(\{\Status, \City\}\) is a key for \(\TCsub\), so the functional dependencies (a) \(\{\Status, \City\} \rightarrow \{\Status\}\) and (b) \(\{\Status, \City\} \rightarrow \{\City\}\) hold in \(\TCsub\). [Ignoring the trivial case of \(\{\Status, \City\} \rightarrow \{\Status, \City\}\).]
\setcounter{constraint}{3}
\item \(\RelProject_{\{\Sno\}}S = \RelProject_{\{\Sno\}}\STsub\)
\item \(\RelProject_{\{\Sno\}}\STsub = \RelProject_{\{\Sno\}}\TCsub\)
\item (a) \(\Type{\STsub} = \RelProject_{\{\Sno, \Status\}}\Type{S}\); (b) \(\TT{\STsub} = \RelProject_{\{\Sno, \Status\}}\TT{S}\)
\item (a) \(\Type{\TCsub} = \RelProject_{\{\Status, \City\}}\Type{S}\); (b) \(\TT{\TCsub} = \RelProject_{\{\Status, \City\}}\TT{S}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-i-project-lossy}
\noindent The constraints appearing in \(\schema{1}\) are \Constraint{\ref{constraint-project-lossy-key}}(a), \Constraint[\schema{1}]{\ref{constraint-project-lossy-key}}(b), \Constraint{\ref{constraint-project-lossy-key}}(c), \Constraint[\schema{1}]{\ref{constraint-project-lossy-key-ii}}, and \Constraint[\schema{1}]{\ref{constraint-project-lossy-s-st-identical}}--\Constraint[\schema{1}]{\ref{constraint-project-lossy-types-tc}}. The completed SIG for \(\schema{1}\) is shown in Figure~\ref{fig-sig-s-i-project-lossy}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{1} = \{S\}\).}
\label{fig-sig-s-i-project-lossy}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{2} = \{\ST, \TC\}}\)}
\noindent A user granted access only to \(\schema{2}\) can see only relvars \(\ST\) and \(\TC\). Constraints \Constraint{\ref{constraint-project-lossy-key}}(b), \Constraint{\ref{constraint-project-lossy-key-ii}}, and \Constraint{\ref{constraint-project-lossy-st-tc-status}} can be propagated directly from \(\schema{0}\) into \(\schema{2}\) as they are already expressed in terms of \(\ST\) and \(\TC\) only. The remaining constraints cannot be propagated from \(\schema{0}\) into \(\schema{2}\) at all, as none of them can be rewritten in terms of \(\ST\) and \(\TC\) only (due to the lossy decomposition of \(S\) into \(\ST\) and \(\TC\)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-ii-project-lossy}
N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-ii-project-lossy}
\noindent The constraints appearing in \(\schema{2}\) are \Constraint[\schema{2}]{\ref{constraint-project-lossy-key}}(b), \Constraint[\schema{2}]{\ref{constraint-project-lossy-key-ii}}, and \Constraint[\schema{2}]{\ref{constraint-project-lossy-st-tc-status}}. The completed SIG for \(\schema{2}\) is shown in Figure~\ref{fig-sig-s-ii-project-lossy}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{2} = \{\ST, \TC\}\).}
\label{fig-sig-s-ii-project-lossy}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{3} = \{\ST\}}\)}
\noindent A user granted access only to \(\schema{3}\) can see only relvar \(\ST\). Only constraint \Constraint{\ref{constraint-project-lossy-key}}(b) can be propagated directly from \(\schema{0}\) into \(\schema{3}\) as it is the only one expressed in terms of \(\ST\) only. None of the remaining constraints can be rewritten in terms of \(\ST\) only, and so cannot be propagated into \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-iii-project-lossy}
N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-iii-project-lossy}
\noindent The only constraint appearing in \(\schema{3}\) is \Constraint{\ref{constraint-project-key}}(b). The SIG will only include edges and nodes that relate either directly to \(\ST\) or are independent of any relvar. The completed SIG for \(\schema{3}\) is shown in Figure~\ref{fig-sig-s-iii-project-lossy}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{3} = \{\ST\}\).}
\label{fig-sig-s-iii-project-lossy}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{4} = \{\TC\}}\)}
\noindent A user granted access only to \(\schema{4}\) can see only relvar \(\TC\). Only constraint \Constraint{\ref{constraint-project-lossy-key-ii}} can be propagated directly from \(\schema{0}\) into \(\schema{4}\) as it the only one expressed in terms of \(\TC\) only. None of the remaining constraints can be rewritten in terms of \(\TC\) only, and so cannot be propagated into \(\schema{4}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-iv-project-lossy}
N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-iv-project-lossy}
\noindent The only constraint appearing in \(\schema{4}\) is \Constraint[\schema{4}]{\ref{constraint-project-lossy-key-ii}}. The completed SIG for \(\schema{4}\) is shown in Figure~\ref{fig-sig-s-iv-project-lossy}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
&[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}
\caption{SIG for schema \(\schema{4} = \{\TC\}\).}
\label{fig-sig-s-iv-project-lossy}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Transformations}
\label{sec-transforming-project-lossy}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{2}}\)}
\noindent The SIGs for \(\schema{1}\) and \(\schema{2}\) can't be made isomorphic. We can duplicate nodes \(\Type{\ST}\) and \(\TT{\ST}\), but there is no way to link these to the existing nodes \(\Type{\TC}\) and \(\TT{\TC}\) (and vice versa if we duplicate \(\Type{\TC}\) and \(\TT{\TC}\) instead). There are insufficient bijective edges across which to copy other edges. \(\schema{1}\) and \(\schema{2}\) are therefore incomparable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{3}}\)}
Essentially identical to the nonloss projection case (compare Figure~\ref{fig-sig-s-iv-project-lossy} with Figure~\ref{fig-sig-s-iii-project}), so \(\schema{1}\) and \(\schema{3}\) are incomparable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{4}}\)}
The SIG for \(\schema{4}\) is a subset of that for \(\schema{2}\), so \(\schema{1}\) and \(\schema{4}\) must also be incomparable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Lossy one to one join views (Date, Chapter 6)}
\label{sec-one-to-one-join}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relvars}
\begin{itemize}
\item base relvar \(\ST\{\Sno, \Status\}\) [supplier status]
\item base relvar \(\SC\{\Sno, \City\}\) [supplier city]
\item view \(S = \ST \RelJoin \SC\) \eqnnumber\label{eqn-s-join-one}
\end{itemize}
There are two possible interpretations consistent with these relvars:
\begin{description}
\item[nonloss join:] All suppliers must have a value for both \(\Status\) and \(\City\). This is essentially just the inverse of the nonloss projection view case (see Section~\ref{sec-nonloss-projection}), and thus has the same constraints and characteristics. We therefore don't need to consider this interpretation any further.
\item[lossy join:] Suppliers must have a value for at least one of \(\Status\) or \(\City\). This implies that there may be tuples in \(\ST\) that don't have a corresponding tuple in \(\SC\) (and vice versa), and thus also don't appear in \(S\). In other words, \(S\) is the join of \(\ST\) and \(\SC\), but \(\ST\) and \(\SC\) aren't necessarily projections of \(S\). This interpretation also implies that \(\Sno\) in \(\ST\) and \(\SC\) is not a foreign key to \(S\). This is the interpretation that we will focus on.
\end{description}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tuple types}
\begin{align}
\TT{S} &= \Type{\Sno} \times \Type{\Status} \times \Type{\City} \nonumber \\
\TT{\ST} &= \Type{\Sno} \times \Type{\Status} \nonumber \\
\TT{\SC} &= \Type{\Sno} \times \Type{\City} \nonumber
\end{align}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Base schema \(\bm{\schema{0} = \{S, \ST, \SC\}}\)}
\begin{ConstraintList}
\item\label{constraint-join-one-key} \(\Sno\) is a key for each of \(S\), \(\ST\), and \(\SC\), so the functional dependency \(\{\Sno\} \rightarrow \{\Status\}\) holds in each of (a) \(S\) and (b) \(\ST\); and the functional dependency \(\{\Sno\} \rightarrow \{\City\}\) holds in each of (c) \(S\) and (d) \(\SC\). [(a) and (c) could in principle be merged into a single functional dependency \(\{\Sno\} \rightarrow \{\Status, \City\}\) in \(S\).]
\item\label{constraint-join-one-join} \(S = \SC \RelJoin \ST\) [from (\ref{eqn-s-join-one})]
\item\label{constraint-join-one-relation-type-join} (a) \(\Type{S} = \Type{\ST} \RelJoin \Type{\SC}\); (b) \(\TT{S} = \TT{\ST} \RelJoin \TT{\SC}\) [from \Constraint{\ref{constraint-join-one-join}}]
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{1} = \{S\}}\)}
\noindent A user granted access only to \(\schema{1}\) can see only relvar \(S\). Constraints \Constraint{\ref{constraint-project-key}}(a) and \Constraint{\ref{constraint-project-key}}(c) can be propagated directly from \(\schema{0}\) into \(\schema{1}\) as they are already expressed in terms of \(S\) only. Constraints \Constraint{\ref{constraint-join-one-join}} and \Constraint{\ref{constraint-join-one-relation-type-join}} cannot be propagated directly from \(\schema{0}\) into \(\schema{1}\), but can be rewritten in terms of \(S\) only, by substituting \(S\) for the expression \(\ST \RelJoin \SC\) (equation~\ref{eqn-s-join-one}). Constraints \Constraint{\ref{constraint-project-key}}(b) and \Constraint{\ref{constraint-project-key}}(d) cannot be propagated into \(\schema{1}\), as they cannot be rewritten in terms of \(S\) only.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-i-join-one}
\begin{ConstraintList}[\schema{1}]
\setcounter{constraint}{1}
\item \(S = S\)
\item (a) \(\Type{S} = \Type{S}\); (b) \(\TT{S} = \TT{S}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-i-join-one}
\noindent The constraints appearing in \(\schema{1}\) are \Constraint{\ref{constraint-join-one-key}}(a), \Constraint{\ref{constraint-join-one-key}}(c), \Constraint[\schema{1}]{\ref{constraint-join-one-join}}, and \Constraint[\schema{1}]{\ref{constraint-join-one-relation-type-join}}. \Constraint[\schema{1}]{\ref{constraint-join-one-join}} and \Constraint[\schema{1}]{\ref{constraint-join-one-relation-type-join}} are effectively tautologies that add no new information, and can thus be safely ignored. The completed SIG for \(\schema{1}\) is shown in Figure~\ref{fig-sig-s-i-join-one}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
&[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}
\caption{SIG for schema \(\schema{1} = \{S\}\).}
\label{fig-sig-s-i-join-one}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{2} = \{\ST, \SC\}}\)}
\noindent A user granted access only to \(\schema{2}\) can see only relvars \(\ST\) and \(\SC\). Constraints \Constraint{\ref{constraint-join-one-key}}(b) and \Constraint{\ref{constraint-join-one-key}}(d) can be propagated directly from \(\schema{0}\) into \(\schema{2}\) as they are already expressed in terms of \(\ST\) and \(\SC\) only. Constraints \Constraint{\ref{constraint-join-one-join}} and \Constraint{\ref{constraint-join-one-relation-type-join}} cannot be propagated directly from \(\schema{0}\) into \(\schema{2}\), but can be rewritten in terms of \(\ST\) and \(\SC\) only, by substituting \(\ST \RelJoin \SC\) for the expression \(S\) (equation~\ref{eqn-s-join-one}). Constraints \Constraint{\ref{constraint-project-key}}(a) and \Constraint{\ref{constraint-project-key}}(c) cannot be propagated into \(\schema{1}\), as they cannot be rewritten in terms of \(\ST\) and \(\SC\) only.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-ii-join-one}
\begin{ConstraintList}[\schema{2}]
\setcounter{constraint}{1}
\item \(\ST \RelJoin \SC = \ST \RelJoin \SC\)
\item (a) \(\Type{\ST} \RelJoin \Type{\SC} = \Type{\ST} \RelJoin \Type{\SC}\); (b) \(\TT{\ST} \RelJoin \TT{\SC} = \TT{\ST} \RelJoin \TT{\SC}\)
\end{ConstraintList}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-ii-join-one}
\noindent The constraints appearing in \(\schema{2}\) are \Constraint{\ref{constraint-join-one-key}}(b), \Constraint{\ref{constraint-join-one-key}}(d), \Constraint[\schema{1}]{\ref{constraint-join-one-join}}, and \Constraint[\schema{1}]{\ref{constraint-join-one-relation-type-join}}. \Constraint[\schema{1}]{\ref{constraint-join-one-join}} and \Constraint[\schema{1}]{\ref{constraint-join-one-relation-type-join}} are effectively tautologies that add no new information, and can thus be safely ignored. The completed SIG for \(\schema{2}\) is shown in Figure~\ref{fig-sig-s-ii-join-one}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{2} = \{\ST, \SC\}\).}
\label{fig-sig-s-ii-join-one}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sub-schema \(\bm{\schema{3} = \{\ST\}}\)}
\noindent A user granted access only to \(\schema{3}\) can see only relvar \(\ST\). Only constraint \Constraint{\ref{constraint-join-one-key}}(b) can be propagated directly from \(\schema{0}\) into \(\schema{3}\) as it is the only one expressed in terms of \(\ST\) only. None of the remaining constraints can be rewritten in terms of \(\ST\) only, and so cannot be propagated into \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Rewritten constraints}
\label{sec-constraints-s-iii-join-one}
N/A
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{SIG}
\label{sec-sigs-s-iii-join-one}
\noindent The only constraint appearing in \(\schema{3}\) is \Constraint{\ref{constraint-join-one-key}}(b). The SIG will only include edges and nodes that relate either directly to \(\ST\) or are independent of any relvar. The completed SIG for \(\schema{3}\) is shown in Figure~\ref{fig-sig-s-iii-join-one}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\centering
\begin{tikzpicture}
\matrix[row sep=1.5cm]
{
\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}
\caption{SIG for schema \(\schema{3} = \{\ST\}\).}
\label{fig-sig-s-iii-join-one}
\end{figure}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Transformations}
\label{sec-transforming-join-one}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{2}}\)}
\noindent The SIGs for \(\schema{1}\) and \(\schema{2}\) can't be made isomorphic, as there's no way using SIG transformations to create in \(\schema{3}\) a node equivalent to \(\Type{\Status} \times \Type{\City}\) in \(\schema{1}\). \(\schema{1}\) and \(\schema{2}\) are therefore incomparable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{\(\bm{\schema{1}, \schema{3}}\)}
This is essentially identical to the lossy projection views example (see Section~\ref{sec-sigs-s-iii-project-lossy}). \(\schema{1}\) and \(\schema{3}\) are therefore incomparable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Additional notes}
If we were to create a fourth sub-schema \(\schema{4} = \{\SC\}\) and compare this with \(\schema{1}\), the result would be similar to that for \(\schema{3}\).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
