CS145 Assignment #6

Due Wednesday Nov. 22, 2000

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, but it is up to you how many new relations you choose to create. 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.

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.
   • Explicit derefrencing (using the DEREF operator).

Problem Set

1. (15 pts.) A database system, containing of two objects A and B (these could be components of two tuples, for example) executes three transactions: T1, T2 and T3. Initially A has a value of 10, and B a value of 20.
   • T1 first writes a value of 30 for A; then changes B to 40. Finally, T1 commits. T1 runs with isolation level SERIALIZABLE.

   • T2 starts by changing A to 50, then modifies B to 60. At this point T2 does a rollback, and all changes are undone. T2 runs with isolation level SERIALIZABLE.

   • T3 is a read-only transaction that first reads A and then reads B. The isolation level of T3 is discussed below.

   We do not know in what order these three transactions execute.

   a)

   Assume that T3 runs with isolation level SERIALIZABLE. What are all the possible A, B values that T3 can read? Give each answer as a pair [a,b], where a is the A value read, and b is the B value read by T3.

   b)

   Assume that T3 runs with isolation level READ COMMITTED. What additional A, B values can T3 read? [Do not list pairs given in part (a).]

   c)

   Assume that T3 runs with isolation level READ UNCOMMITTED. What additional A, B values can T3 read? [Do not list pairs given in parts (a) or (b).]

2. (10 pts.) Consider the following sequence of steps in which A, the owner of privilege p allows the privilege p to be propagated elsewhere:

   Step	By	Action
   1	A	GRANT p to B WITH GRANT OPTION
   2	A	GRANT p to C WITH GRANT OPTION
   3	B	GRANT p to D
   4	C	GRANT p to D WITH GRANT OPTION
   5	D	GRANT p to E WITH GRANT OPTION
   6	E	GRANT p to F

   a)

   Show the grant diagram after these steps.

   b)

   If A then issues the revocation:

        REVOKE p FROM C CASCADE
   

   what will be the resulting grant diagram?

3. (15 pts.) Here are the running example relations about books, authors, reviewers, and such:
   • BookAuthor(book, year, author, earnings)
   • BookReference(book, year, referencedBook, referencedYear, times)
   • BookReview(book, year, reviewer, score)
   • BookPublish(book, year, publisher, price, num)

   Write the following queries in Datalog:

   a)

   Find the books referenced by books that were reviewed by their own authors. Produce only the name of the book as an answer, but remember that book and year together are needed to identify books.

   b)

   Find the authors who never reviewed a book published by Prentice-Hall.

   c)

   Find the second-highest review score of the book First Course in Database Systems, which was published in 1997. Your program need not work correctly if there are two or more reviews tied for highest, but explain what your program produces in this case.