\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{enumerate}
\item[A.1]
(5 pts.)
We wish to design a database to represent train schedules.
Each station on the line has a unique name.
Each train
has a unique number, an origin station, a departure time, a destination
station, an arrival time, and a set of zero or more other
stations at which it stops, along with the time at which it makes the
stop. Draw an E/R diagram that represents this database structure as
faithfully as you can. Indicate keys of entity sets by underlines.
\item[A.2]
(5 pts.)
Give a DTD (XML schema) for the information described in (A.1).
Indicate the intent of your elements and attributes, if they are not
completely obvious from their names.
\item[A.3]
(5 pts.)
Relation R(A,B,C,D,E) has functional dependencies $A\fd B$, $B\fd C$,
and $C\fd D$. Find a Boyce-Codd Normal Form decomposition of R. Show
your work for partial credit.
\item[A.4]
(5 pts.)
Below is a Datalog program:
\begin{verbatim}
P(x) <- A(x) AND NOT B(x)
Q(x) <- B(x) AND NOT P(x)
R(x) <- P(x) AND NOT Q(x)
\end{verbatim}
Here, $P$, $Q$, and $R$ are IDB predicates, and $A$ and $B$ are EDB
predicates. Suppose the relation for $A$ is $\{1,2\}$ and the
relation for $B$ is $\{2,3\}$.
Give two different minimal fixedpoints for this program.
Note: a ``fixedpoint,''~--- sets of tuples
for each of the IDB predicates, such that no assignment of values for the
variables of any rule causes the rule to become false~--- is
a ``model'' in the terminology of logic. ``Minimal'' means that
deletion of one or more tuples makes the sets of tuples no longer be a
fixedpoint.
\end{enumerate}
\end{document}