LOGISTICS

• Turning in written exercises: The procedure for turning in the written exercises on this assignment is the same as for the previous assignments, with the same deadline and late policy.

• Turning in PDA: Your PDA work will again be submitted electronically. The overall procedure is the same as for the previous electronic submissions (see http://www.stanford.edu/class/cs145/submit-README.txt), and the same deadline and late policy applies. Please be sure to follow the explicitly specified file naming scheme and additional submission instructions at the end of Problem 5.

THE ASSIGNMENT

Problem 1

(a) Consider our favorite relational schema from class:

  Student(ID, name, address, GPA, SAT)
  Campus(location, enrollment, rank)
  Apply(ID, location, date, major, decision)

Give an example of two transactions T1 and T2 operating on this database. Assume that transaction T1 has isolation level SERIALIZABLE. (But note that true serializability is guaranteed only when all transactions have this isolation level.) 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:

1. The two transactions T1 and T2, each specified as a sequence of one or more SQL statements followed by commit. Your transactions should be as simple as possible; e.g., they probably do not need to involve all three relations, and you can drop attributes as well if you find it convenient.
2. A simple initial set of data for the relations used by your transactions (the initial state).
3. 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 specify the interleaving (ordering) of the statements between 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.

   (d) Now suppose multiple clients are operating on the database, and all of their transactions use isolation level SERIALIZABLE. Give a realistic example where the final state of the database depends on the order in which concurrent transactions are serialized. Please specify:

   1. An initial state for one or more relations.
   2. Transactions issued by two clients concurrently (one transaction per client, one or more SQL statements per transaction).
   3. Two different valid final states of the relations, depending on which transaction executed first.

   Problem 2

   Many database systems offer the option of deferred referential integrity checking, where an entire statement or transaction's worth of database modifications can be made before a referential integrity constraint is checked. For this problem consider a scenario where only immediate checking is supported: referential integrity is checked immediately after each tuple insertion, deletion, or update that might affect the constraint.

   Specify one or more table declarations in SQL such that no tuples can ever be inserted into any of the tables without violating a referential integrity constraint.

   Problem 3

   Consider the following SQL declarations:

     create table Employee(ID integer unique, salary integer, dept# integer)
     create table Department(number integer unique, salaryCap integer)
   
     create assertion Policy check (
       not exists (select *
                   from Employee, Department
                   where Employee.dept# = Department.number
                   and Employee.salary > Department.salaryCap) )
   

   (a) State in English the policy enforced by assertion Policy.

   (b) Rewrite the above table declarations to use attribute-based and/or tuple-based check constraints to enforce the policy, instead of the general assertion. Your constraints should be defined so that under no circumstances can the policy be violated, no matter what database modifications occur.

   (c) Using the same schema, write a general assertion A that cannot be translated to attribute-based and/or tuple-based check constraints while still guaranteeing that under no circumstances can the policy be violated. That is, your assertion A should be such that any attempt to encode A as a set of attribute-based or tuple-based check constraints will leave open the possibility of certain database modifications causing assertion A to become violated. Please give as simple an example as you can find.

   Problem 4

   Consider a relation TA(name,class,salary) and assume that name is a key. Consider the following trigger, specified using the "for each row" option:

     create trigger 145Hardship
     after update of class on TA
     referencing old as O new as N
     when (N.class = 'CS145' and O.class <> 'CS145')
     update TA
       set salary = 1.1 * salary
       where name = N.name
     for each row
   

   (a) Describe in English what this trigger does.

   (b) Write an equivalent trigger that does not use the "for each row" option.

   (c) Specify another trigger on the TA relation that uses the "for each row" option such that an equivalent trigger cannot be written without the "for each row" option. (Assume that the equivalent trigger is not allowed to introduce temporary variables or tables.) In addition to specifying the trigger in SQL, describe in English what your trigger does. As usual, the simpler and more intuitive your answer is, the better.

   Problem 5 (Personal Database Application, Part 6)

   This week you will experiment with Oracle's proprietary programming language PL/SQL, as well as Oracle's facilities for views, constraints, and triggers. Some of this week's programming work will be independent of your PDA.

   PL/SQL and triggers are discussed in the document Using Oracle PL/SQL. (Currently, the version of this document in your course reader and from the book Web site - linked from the course home page under Oracle Information - is the most current version.) View definitions and constraint declarations largely follow the SQL2 standard although there are some restrictions; see the document Oracle 8i SQL, for discussion. (Recall that the latest version of this document, which you also used for project part 4, is modified from the course reader and is linked to the course home page.) A few frequently-asked questions regarding constraints and triggers appear in the Oracle 8i: Frequently Asked Questions page on the book Web site, linked from the course home page under Oracle Information.

   (a) Although the "EXCEPT ALL" (or "MINUS ALL") operator to perform bag difference is part of the SQL standard, it is not supported by Oracle. Your job is to implement this operator using PL/SQL. Specifically:

   1. Create two tables R1(A,B) and R2(A,B) in Oracle with identical schemas. The types and values of the attributes don't matter. However, both tables should contain duplicate tuples, and they should contain enough different duplicate situations (e.g., four copies in R1 and two in R2; one copy in R1 and three in R2; two copies in R1 and zero in R2, etc.) to fully test your bag deletion algorithm. Also create an empty table Diff(A,B) with the same schema, to hold the result.

   2. Write a PL/SQL program to compute the bag difference of R1 and R2, putting the result in Diff.

   3. Submit a file bags.sql containing your PL/SQL code, along with a script file 6a.script showing the initial contents of R1 and R2, the successful execution of your program, and the bag difference result in Diff.

   Please make your program as general-purpose as possible. You may hard-wire the table and attribute names for R1, R2, and Diff, but nothing else. (In particular, do not use or assume any additional database tables for your computation.) During grading we may test your program for correctness on our own instances of R1 and R2.

   (b) Create two useful views on top of your PDA database schema. Submit a file views.sql containing the CREATE VIEW statements. Also submit a script file 6b.script showing the response of the system to the view definitions, and for each view, showing a query involving the view and the system response. (As usual you should truncate the response if more than a few tuples are produced.)

   (c) You are to recreate your PDA schema, adding specifications for additional keys, referential integrity, and other constraints.

   1. Modify your PDA CREATE TABLE statements as follows.

      • For each relation in your schema, if the relation has any keys in addition to the PRIMARY KEY that you already declared, specify the additional keys as UNIQUE. If there are no additional keys, add a comment to that effect.

      • For each referential integrity constraint that should hold in your schema, specify the constraint using a REFERENCING clause within the appropriate CREATE TABLE statement. You may use the default option for handling referential integrity violations (violations will generate an error). We expect that everyone's PDA should include at least one referential integrity constraint. If your PDA has no natural referential integrity constraints, then it probably is either far simpler than we asked for, or a poor design - please contact one of the course staff.

      • Add at least two attribute-based and two tuple-based CHECK constraints to relations of your database schema. Remember that these constraints are more limited in Oracle than in the SQL2 standard; see the document Oracle 8i SQL for discussion.

      Submit a file cons.sql containing all your CREATE TABLE statements, along with a script file 6c1.script showing their successful execution in Oracle.

   2. Reload your small PDA database. Did you get any key, referential integrity, or CHECK constraint violations? Please turn in the .log file generated by the Oracle bulk-loader, renamed as small.log.

   3. Reload your large PDA database. Did you get any key, referential integrity, or CHECK constraint violations? Please turn in the .log file generated by the Oracle bulk-loader, renamed as large.log.

   4. You don't necessarily need to modify your program for generating data if it creates violations. However, for this part of the problem you should start with a database (small or large) that does not create violations. Write data modification commands to illustrate the following seven scenarios:

      • An INSERT command creating a key violation
      • An UPDATE command creating a key violation
      • An INSERT command creating a referential integrity violation
      • A DELETE command creating a referential integrity violation
      • An UPDATE command creating a referential integrity violation
      • An INSERT command creating a CHECK constraint violation
      • An UPDATE command creating a CHECK constraint violation

      Submit a file viols.sql containing all seven commands, along with a script file 6c2.script showing their unsuccessful execution in Oracle. (d) Create at least two "interesting" triggers for your PDA. Submit a file trigs.sql containing the CREATE TRIGGER statements. Also submit a script file 6d.script showing the response of the system to the trigger definitions, and the execution of database modifications that illustrate the firing of each trigger and cases where neither trigger fires. Show in your script the results of queries demonstrating that the triggers had an effect when they fired and no effect when they didn't.

      (e) Extra credit problem: If you do a good job on this problem you are eligible for up to an extra 20% of the total points for this programming assignment.

      You are to do some sleuth work: Your task is to determine what criteria exactly Oracle uses in deciding whether a view is updatable, i.e., whether it is possible to perform INSERT, DELETE, and/or UPDATE statements on the view. While your sleuth work could involve sifting through HELP pages or Oracle books, we prefer that you do it experimentally. Write a series of views along with modification commands on the views to determine when Oracle allows views to be updated and when it does not. As discussed in class and in the textbook, some SQL views are obviously updatable, some are obviously not updatable (due to ambiguities), and some are theoretically updatable but it is difficult for a system to determine the correct update translations. In your solution to this problem you should attempt to provide a concise characterization of those views that Oracle allows to be updated, and you should support your claim by demonstrating:

      • views meeting the criteria that can be updated, and
      • views not meeting the criteria that cannot be updated.

      If separate criteria apply for INSERT, DELETE, and UPDATE commands then these should be included in your solution. You may use your PDA schema and data for this problem if you like, or you may use a separate, simpler database.

      If you attempt this problem, please submit a text file extra.txt specifying the view update criteria you believe Oracle uses, and specifying clearly the contents of submitted .sql and/or .script files that support your findings.

   Submission

   To avoid confusion, we have specified precisely the files that should be submitted for this programming part. For parts (a)-(d) you should submit the following 12 files, and only these files:

     bags.sql
     6a.script
     views.sql
     6b.script
     cons.sql
     6c1.script
     small.log
     large.log
     viols.sql
     6c2.script
     trigs.sql
     6d.script
   

   If you attempt the extra credit problem (part (e)), then you must also submit extra.txt and some clearly specified additional files. If for some reason you feel you must submit files beyond those discussed here, please justify the files in a submitted file called README. Submissions that do not conform to these guidelines will not be graded.

   Unless otherwise specified, the scripts you turn in for this assignment may show operations running over your small or your large database (or in the case of Parts (a) and (e), another database altogether).

   • If you use your small database, be sure to test your work on your large database as well to make sure it is correct and reasonably efficient.
   • If you use your large database, please do not submit listings showing hundreds of lines of query results.
   As always, you should include comments for any program code, database queries, or other operations that are not crystal clear, and it is an Honor Code violation to edit scripts before turning them in (other than simple formatting, comments, or truncation).