CS145 Assignment #6

Due Wednesday Nov. 17, 1999

Step 6 of Your PDA

1. (20 pts.) Declare some data types that could be used with the data of your PDA. You need to choose types such that:
   • There are at least two methods included among these types; not every type must have methods, however.
   • At least one type is suitable as a column type (abstract data type).
   • At least one type is suitable as a row type (type of a relation).
   • At least one type is a table type, defined from one of the other types you declared.

   Show your declarations (don't forget type bodies when there are methods) and the successful compilation of the declarations. Remember that the slash is needed to cause compilation.

2. (20 pts.) Declare some relations that could hold data associated with your PDA. Choose relations so that:
   • At least one relation has a column type defined in (1) for one of its attributes.
   • At least one relation should be of a row type that you defined in (1).
   • At least one relation should have a table type defined in (1) for one of its columns.
   • At least one reference type (REF) must be involved, either in your relation declarations or in the types from (1) themselves.

   Note that it is possible for one relation to satisfy all these conditions. Write INSERT statements to populate your new relations from the data in the original relations of your PDA. Show the correct compilation of your declaration and correct execution of your insertion statements.

   Aside: The most recent release of the Oracle loader allows object-relations to be populated directly. However, this loader is not yet running at Stanford, so we have to populate object-relations in this kludgy way.

3. (20 pts.) Write 4 or more queries on your relations from (2). Among these queries, you should demonstrate the following features at least once:
   • Use of methods.
   • Access of data within a column type.
   • Access of data within a table type.
   • Use of a table type's value in a FROM clause.
   • Following REF's.
   • Derefrencing.

Problem Set

1. (25 pts.) Suppose we have the following attributes: C (course), T (teacher), H (hour), R (room), S (student), and G (grade), with the following functional dependencies: C->T, CS->G, HR->C, HT->R, HS->R, CH->R, HS->C, and HRS->T. Note that these FD's allow us to assume that a course may meet in different rooms at different hours. The interpretation of the first three are ``a course has only one teacher,'' ``a student gets only one grade in a course,'' and ``only one course can be in a room at any one time.'' The others have similar interpretations that follow from ``physics''; e.g., students and teachers cannot be in two places at once.

   (a)

   The first five FD's are one minimal set of FD's. Find another minimal set. Show your reduction steps.

   (b)

   Give a decomposition of the schema CSGHRT into 3NF schemas that have a lossless join and preserve FD's.

   (c)

   If we project the relation CSGHRT onto the set of attributes CHRT, and project the given FD's, what are the keys for CHRT?

   (d)

   Are there any BCNF violations for CHRT? Give an example, if so.

   (e)

   Are there any 3NF violations for CHRT? Give an example, if so.

2. (15 pts.) Suppose we have a relation schema ABCD and the dependencies A->->B and B->C (i.e., A multidetermines B, while B functionally determines C). Which of the following dependencies must hold? For each, either give a reason why, or give a counterexample relation instance for ABCD.

   (a)

   B->->AD

   (b)

   A->->C

   (c)

   B->->D