CS145 - Spring 2002
Introduction to Databases

Assignment #5 -- Due Wednesday May 15

The procedure for turning in this assignment, the late policy, and the grading is exactly the same as for Assignment #1. However, since there are no challenge problems on this assignment, your mark for written work will be either check or minus - no plus's available. As always, we strongly encourage you to do all of the exercises in order to make sure you understand the material and to prepare for the final exam.

Exercises

Using the translation method given in class and in the textbook, translate the E/R diagram in Figure 2.17 of the textbook (page 50) to a relational schema. Make sure to underline a key in each relation.
Does it make sense to combine any of the relations in your answer to Problem 1? If so, show the new schema, making sure to underline keys in the combined relations. Can you suggest a general principle for when relations can be combined and when they shouldn't be? What happens when you combine relations that you "shouldn't"?
Consider the E/R diagram in Figure 3.15 of the textbook (page 81). To this diagram, add an attribute date-born to each of the relationships ChildOf, FatherOf, and MotherOf, and add two attributes date and location to relationship Married. Translate the extended E/R diagram to a relational schema. You may use any of the various methods for translating subclasses that you prefer. Make sure to underline a key in each relation.
Based on the principles you came up with in Problem 2, combine relations in your answer to Problem 3 as appropriate. As always, make sure to underline keys in each relation of the schema.
Specify an ODL design for a database maintained by a library. The data should include information about books, employees, and customers. It should include a log of all books checked out by an employee to a customer, including if and when books were returned. This problem is deliberately free-form - you may include just the basic library information or you may go all-out. In either case, please state any assumptions you make about the real world in your design. In addition to class definitions with attributes and relationships, don't forget to include keys and inverse relationships as appropriate.
Translate your ODL design from Problem 5 into relations. You may use any of the methods discussed in class or in the textbook. Don't forget keys.
Specify an ODL class definition for any real-world domain of your choosing such that the class realistically includes a relationship that is its own inverse.
Translate your ODL design from Problem 7 into relations. You may use any of the methods discussed in class or in the textbook. Don't forget keys.
Consider a simple E/R diagram representing books and authors. It contains:
- Entity set Books with attributes ISBN and Title; ISBN is a key.
- Entity set Authors with attributes name, city, and state; name is a key.
- Relationship Wrote with attribute date.
For each of the following scenarios, design two or more possible XML document structures for the database design specified by the E/R diagram. You can specify your XML structures using a small sample document, a DTD, or (preferably) both.
(a) Wrote is one-one with referential integrity in both directions, i.e., every book has exactly one author and every author has written exactly one book. (Note: How do your XML structures extend to the case when some authors have written no books?)
(b) Wrote is one-many from books to authors with referential integrity, i.e., every book has zero or more authors and every author has written exactly one book. (Note: How do your XML structures extend to the case when some authors have written no books?)
(c) Wrote is many-many from books to authors with no referential integrity, i.e., every book has zero or more authors and every author has written zero or more books.

Challenge Problems

No challenge problems this week. Project Part C provides plenty of open-ended challenge.

Project Part 4

In this part of the project you will experiment with three features of Oracle: Indexes, PL/SQL, and Views. All of your work can be done through the sqlplus textual interface to Oracle, although you are welcome to build a Web front-end if you like. Two important notes:

For Oracle to do the best possible job executing queries over large amounts of data, it needs to gather statistics about the data. To force statistics-gathering, for each table in your database you need to run the command:
```
  analyze table [tablename] compute statistics;
```
where [tablename] is replaced by the name of the table. You must run this command after the data is loaded initially, and again if you make very significant changes to the contents of the table. We recommend you keep this habit up for the rest of the project.
You will need to read or review the following two Oracle help documents for this project part:
- Oracle 9i SQL (Indexes, Views, Timing SQL Commands, and PL/SQL vs. SQL/PSM)
- Using Oracle PL/SQL

Part A: Indexes

On Monday May 13 we posted to cs145-announce@lists an important note regarding this part of the assignment. Please read it if you haven't already.

As discussed in class and the textbook, an important technique for improving the performance of queries is to create indexes. An index on an attribute A of relation R allows the DBMS to quickly find all tuples in R matching a given value or range of values for attribute A (useful when evaluating selection or join conditions involving attribute A). An index can be created on any attribute of any relation, or on several attributes combined. The syntax for creating indexes in Oracle is given in the document Oracle 9i SQL. Please pay careful attention to the information about Stanford/Oracle-specific syntax.

Create at least one useful index on each table in your large AuctionBase schema. Run several queries over your large AuctionBase database with the indexes and without the indexes. Try to write queries that are realistic, that are complex enough to take a while to execute, and that can exploit the indexes you chose so you can best experiment with the performance differences. Turn in a transcript showing your commands to create indexes, and showing the relative times of query execution with and without indexes. Please truncate all large query results. A few tuples in the result suffice to show us that your query works.

Please note:

As mentioned in the document Oracle 9i SQL, Oracle automatically creates indexes for attributes declared as keys. Thus, when you created a table in Project Part 3 and declared a PRIMARY KEY, an index was created, and you need not attempt to create another index on your key attributes. Most tables have at least one attribute (or group of attributes) other than the primary key that can benefit from an index, but if you feel there are no other attributes that are useful to index in one or more of your tables then please tell us.
As described in the document Oracle 9i SQL, in order to set the system to show query execution times you must issue the command "set timing on;" at the sqlplus prompt.
Make sure that your indexes are created on the separate tablespace "indx" by adding "tablespace indx" at the end of your create index command.
As mentioned above, for Oracle to take full advantage of indexes it may need to have gathered statistics for the relevant tables. Make sure to run "analyze table [tablename] compute statistics;" for each table in your AuctionBase schema.
Your timings will be affected by external factors such as system load. However, it should not be hard to construct queries for which you see a consistent dramatic difference between the execution times with indexes and the times without. If you are having difficulty, please see a member of the course staff.
If you're getting "space quota exceeded" errors, use the following commands to check your existing indexes and tables, and drop those that you do not need for now (you can always reload them later):
```
   select index_name from user_indexes;
   select table_name from user_tables;
```

Part B: PL/SQL

As you learned from the textbook material, the Programming with SQL help session, and the midterm exam, it is not possible using a single SQL DELETE statement to delete an arbitrary number of tuples in the presence of duplicates. You are to write a PL/SQL program to perform this function. Specifically, create a table R(A,B) in Oracle. The types and values of the attributes don't matter, except you should populate R with many duplicate tuples. You are to write a PL/SQL program that takes three arguments: a, b, and n. The program should delete exactly n copies of tuple (a,b) from table R. If R contains fewer than n (a,b) tuples then all of them should be deleted. Turn in your PL/SQL code, along with a transcript demonstrating convincingly that your program works under the various relevant conditions (n > 0; n = 0; no tuples matching (a,b); fewer than n matches; exactly n matches; more than n matches, etc.).

Part C: Views

You are to do some sleuth work: Your task is to determine what criteria 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 instead 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 AuctionBase schema and data for this problem if you like, or you may use a separate, simpler database.

You should turn in a writeup specifying clearly the view update criteria you believe Oracle uses, along with a series of view creation and modification statements that support your findings.

What to submit

Your submission directory should contain the following 6 files:

`p4a.script`		Transcript for Part A
`p4b.sql`		PL/SQL program for Part B
`p4b.script`		Transcript for Part B
`p4c.txt`		Writeup with conclusions from your experiments for Part C
`p4c.script`		Transcript that supports your conclusions for Part C
`README`		Any additional information that you wish to include

Once your submission directory is created, submission instructions are exactly the same as for previous project parts. Remember that points may be deducted if you do not follow the submission procedures exactly as specified, including file naming and contents, and if you submit more than once, all submissions except your last will be ignored.