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