\documentstyle[psfig, fullpage, 11pt]{article}
\def\fd{\mathrel{\rightarrow}}
\def\mvd{\hbox{$\rightarrow$\hskip-5pt$\rightarrow$}}
\def\ans{\par\smallskip\noindent{\bf Answer:~}}
\def\tjoin#1{\mathrel{\hbox{$\hbox{$\bowtie$}\atop#1$}}}
\def\join{\mathrel{\bowtie}}
\def\sjoin{\mathrel{\raise1pt\hbox{\vrule
height5pt depth0pt\hskip-1.5pt$>$\hskip
-3pt$<$}}}
\begin{document}
\begin{center}
{\large\bf PART A}
\end{center}
\begin{itemize}
\item[A.1]
(10 pts.)
We may represent an undirected graph by relations (or predicates)
$Node(x)$, meaning ``$x$ is a node of the graph,'' and $Edge(x,y)$,
meaning ``there is an edge between nodes $x$ and $y$.'' Note that
although the graph is undirected, we do not assume that $Edge$ is
symmetric. That is, there might be a tuple $Edge(2,3)$ or $Edge(3,2)$
to indicate that there is an edge between nodes 2 and 3 (nodes 2 and 3
are {\em adjacent}), but it is
possible that only one of these tuples is present, not both.
Write a Datalog
program for the predicate $P$ defined by: $P(x)$ is true if and only if
node $x$ is not adjacent to any node of degree 1 (a node is {\em of
degree 1} if it is adjacent to exactly one other node). You may use Datalog
with negation and with the six comparison operators (less-than,
not-equals, etc.). However, make sure each of your rules is safe.
Be sure to explain what each of your predicates is
intended to mean, if it is not obvious from the name.
\item[A.2]
(10 pts.)
The relation $R(A,B,C,D)$ has functional dependency $A\fd C$ and
multivalued dependency $B\mvd CD$.
\begin{itemize}
\item[a)] (6 pts.) Give two {\bf nontrivial} multivalued dependencies, each with
{\bf one} attribute on the left and {\bf one} attribute on the right,
that follow logically from the given dependencies.
Explain your reasoning, or give the names of the rules by which these
MVD's follow.
\item[b)] (4 pts.) Give one {\bf other nontrivial} functional dependency with
{\bf one} attribute on the left and {\bf one} attribute on the right,
that follows logically from the given dependencies.
Explain your reasoning.
\end{itemize}
\end{itemize}
\end{document}