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