Assignment #6
Due Wednesday November 20

This assignment will be graded out of 24 points.

(6 points, 2 per part)
Consider the following familiar relational schema:
```
             lives (name, street, city)      // name is a key
             works (name, company, salary)   // name is a key
             located (company, city)         // company is a key
```
(a)
Give an example of two client transactions T1 and T2 operating on this database. Assume that transaction T1 has isolation level serializable. For transaction T2, consider isolation levels read uncommitted and read committed. Design your transactions so that there is some result allowed when T2 uses read uncommitted that is not allowed when T2 uses read committed. Assume that transactions T1 and T2 both commit. More specifically, give:

(i)
The two transactionsT1 and T2, each specified as a sequence of one or more SQL statements followed by commit. Your transactions need not involve all of the relations in the schema.

(ii)
A simple initial set of data for the relations used by your transactions (the initial state).

(iii)
The state of the data after T1 and T2 have both executed such that this final state could result when T2 uses read uncommitted, but could not result when T2 uses read committed. Also show the interleaving (ordering) of the statements in the two transactions that produced this final state.

(b)
Do part (a) again, except this time for transaction T2 consider isolation levels read committed and repeatable read, where the final state could result when T2 uses read committed, but could not result when T2 uses repeatable read.

(c)
Do part (a) again, except this time for transaction T2 consider isolation levels repeatable read and serializable, where the final state could result when T2 uses repeatable read, but could not result when T2 uses serializable.
(3 points)
Consider a set of users U, V, W, X, and Y. Suppose that user U creates a relation R(A) and is thus the owner of relation R. Now suppose the following set of statements is executed in order:
```
  1. User U: grant select on R to V,W with grant option
  2. User V: grant select on R to W
  3. User W: grant select on R to X,Y
  4. User U: grant select on R to Y
  5. User U: revoke select on R from V restrict
  6. User U: revoke select on R from W cascade
```
Show the grant diagram after steps 4, 5, and 6. Since all of the nodes in the diagrams will be for privilege ``select on R'', you may omit writing it in each node.
(3 points, 1 per part) Use any simple relational schema for this problem you like, such as R(A).

(a)
Give the simplest example you can think of where a series of one or more grant statements results in a cycle in the grant diagram. Show the grant statements and the resulting diagram.

(b)
Give an example of a grant diagram that includes a cycle, along with a single revoke statement with the cascade option, such that the revoke statement deletes all privilege nodes on the cycle. Show the grant diagram before the revoke statement, specify the revoke statement, then show the grant diagram after the revoke statement.

(c)
Give an example of a grant diagram that includes a cycle, along with a single revoke statement with the cascade option, such that the revoke statement deletes some privilege nodes on the cycle but not all of them. Show the grant diagram before the revoke statement, specify the revoke statement, then show the grant diagram after the revoke statement.
(4 points)
There's a type of database security that was not covered in class or in the course notes called statistical authorization. With statistical authorization, some users may be permitted to retrieve only aggregate information from the database, e.g., average salaries but not individual salaries. Furthermore, to prevent users from applying aggregates to very small numbers of tuples (such as the average of one salary!), the system requires that a certain minimum number of tuples contribute to each aggregate result. Finally, to prevent the user from using intersection properties to deduce a single value (e.g., the user could ask for X = sum(A1,A2,A3,A4,A5), then ask for Y = sum(A2,A3,A4,A5), then compute X-Y to deduce the value of A1), the system may require that the tuples participating in multiple queries issued by the same user have a small intersection. In this problem you will explore how, even with such security measures, specific information can still be deduced from the database.
Here's the problem. Consider the simple relation student(ID,GPA). Suppose that, for security reasons, the following restrictions are made on user U's set of queries against this relation:
- The result of every query must be a single aggregate value--an SQL aggregate function applied to one of the attributes of the relation.
- At least 4 different tuples must be used in the aggregate to produce each query's result.
- For any two queries issued by user U, the sets of tuples used to produce the two query results must have an intersection no larger than 2.
Assume that student IDs are in the range 1 to 50, and that attribute GPA is of type float. Give a set of queries that satisfies the above restrictions, and from whose answers you can determine the GPA of the student with ID = 1. Write the queries in SQL, then show the computation that produces the GPA for the student with ID = 1 from the query results. Use as few queries as you can. Warning: This problem does take some thinking!
PDA: Programming
(2 points, 1 per part)
In this problem you will experiment with transactions in Sybase. Since it would be difficult for you to simulate multiple users operating on your database, you will simply experiment with the properties of transaction commit versus rollback.

(a)
Create a sqsh input file that initiates a transaction on your PDA database using ``begin transaction'', performs one or more data modification commands, then commits the transaction using ``commit''. Issue queries before and after executing the transaction to demonstrate that the modification has been made on the database. Use your small database. Turn in a listing demonstrating that you have done the required work.

(b)
Create a sqsh input file that initiates a transaction on your PDA database using ``begin transaction'', performs one or more data modification commands, then aborts the transaction using ``rollback''. Issue queries before and after executing the transaction to demonstrate that the modification has not been made on the database. Use your small database. Turn in a listing demonstrating that you have done the required work.
PDA: Written work
(6 points, 2 each for parts (b), (c), and (d))

(a)
Remind us of the schema for your PDA (the schema you implemented in Sybase).

(b)
Suppose multiple clients are operating on your PDA database. Give an example where problems with concurrent access can arise if transactions are not used. Please specify:

(i)
An initial set of data in one or more relations of your PDA (the initial state).

(ii)
SQL statements issued by two clients concurrently (one or more statements per client).

(iii)
A final state of the relations in which the statements have been executed in an interleaved fashion so the resulting state is intuitively incorrect.

Your example will be graded on simplicity as well as correctness. Note that you do not have to run your SQL statements; this is a written problem only.

(b)
Now suppose that your multiple clients use transactions with isolation level serializable in order to alleviate the problems with concurrent access. Give an example where the final state of your PDA database depends on the order in which the transactions are executed. Please specify:

(i)
An initial state for one or more relations.

(ii)
SQL transactions issued by two clients concurrently (one transaction per client, one or more statements per transaction).

(iii)
Two different valid final states of the relations, depending on which transaction executed first.

Your example need not correspond to your example from part (b). Again, you will be graded on simplicity as well as correctness, and you do not have to run your SQL statements.

(d)
Using your PDA, specify a simple scenario in which an application program (e.g., a C program running on your PDA using embedded SQL and transaction commands) might decide to abort a transaction based on user input. You may specify the scenario using prose or simple pseudocode, whichever you prefer. Once again, no actual programming is required.

The TAs of CS145, cs145ta@cs.stanford.edu, last modified: 11/13/96

Assignment #6 Due Wednesday November 20

Assignment #6
Due Wednesday November 20