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