CS145 Assignment #1

Due Wednesday, October 11, 2000

Some Mechanics for Homeworks

For All Students

Assignments are due in class on Wednesday. You are allowed one lateness of up to 48 hours; use that privilege carefully.

For On-Campus Students

Assignments should be turned in during class or at the course secretary's office: Gates Building room 419. If you want a receipt for your work, Ms. Bharwada can give you one.

For SITN students

Assignments due on Wednesday must be timestamped by the Thursday morning courier to be considered on-time. Like all students, you have one free 48-hour exception. You should not have to worry about receipts for work, because SITN logs everything it receives.

Remember: the due time/day of 11AM Wednesday applies to you too, although we often cannot verify the exact time you delivered your work to your local pickup point. However, please do not imagine, say, that it is OK to hand-deliver the work Thursday morning.

Special Directions for Assignment 1 Only

In general, we shall expect your work to be handed in as one set of pages, fastened together. However, because we want to look that your proposed projects quickly, we ask that for this assignment only, you hand in three separate sets of pages, each with your name at the front. These three sections can be clipped together if you wish. They are:

The signed statement about rules for sharing ideas in CS145.
Step 1 of your Personal Database Application.
The three written problems at the end of this assignment.

Certification Regarding Honor-Code Policy

I feel bad that I have to take this step, but I have noticed an increasing number of students who, when confronted in an obvious case of plagiarism, tell me that they had never read the course policy on the subject. Therefore, I request that everyone download or copy (i.e., with real scissors, not an icon of a scissor) the statement from The Course Introduction reproduced below, and sign it.

The basic presumption is that the work you do is your own. Occasionally, especially when working problem sets or writing programs (but never on exams!), it may be necessary to ask someone for help. You are permitted to do so, provided you meet the following two conditions.

You acknowledge the help on the work you hand in.

You understand the work that you hand in, so that you could explain the reasoning behind the parts of the work done for you by another.

Any other assistance by another person constitutes a violation of the honor code and will be treated as such.

If you have any questions about what this policy means, please discuss the matter with the instructor now.

Step 1 of Your PDA (Personal Database Application)

As the course progresses you will be building a substantial database application for a real-world scenario of your choosing. You will design a relational schema for the database, and you will create an actual database using a relational database management system. You will populate the database with sample data, write interactive queries and modifications on the database, and develop user-friendly tools for manipulating the database.

Your first step is to identify the domain you would like to manage with your database, and to construct an entity-relationship diagram for the data. We suggest that you pick an application that you will enjoy working with, since you'll be stuck with it for the whole quarter! In previous years, students who built a database about something they were interested in--a hobby, material from another course, a research project, etc.--got the most out of this part of CS145.

Try to pick an application that is relatively substantial, but not too enormous. For example, when expressed in the entity-relationship model, you might want your design to have in the range of five or so entity sets, and a similar number of relationships. Note that this is a ballpark figure only! You should certainly include different kinds of relationships (e.g., many-one, many-many) and different kinds of data (strings, integers, etc.), but your application is not required to use advanced features, such as subclassing, multiway relationsships, or weak entity sets, if they are not appropriate for your application.

(a): (30 pts.) Describe the database application you propose to work with throughout the course. Your description should be brief and relatively informal. If there are any unique or particularly difficult aspects of your proposed application, please point them out. Your description will be graded only on suitability and conciseness.
(b): (30 pts.) Specify an entity-relationship diagram for your proposed database. As always, don't forget to underline key attributes and include arrowheads indicating the multiplicity of relationships. If there are weak entity sets, indicate them by double lines, as described in class.

Reminders

We shall try to catch major problems in your proposed designs within three days of your submitting it, so your Step 2 of the PDA will not be adversely affected. To make sure we can tell you of a problem with your design, please include your email address on this part of the assignment.

Also, don't forget to save a copy of your PDA for reference as you do Step 2 of the PDA.

If you are having trouble thinking of an application, or if you are unsure whether your proposed application is appropriate, please feel free to consult with one of the course staff.

Problem Set

(20 pts.) In this exercise, you will model the database of an ``eTailer,'' such as Amazon. Here are the kinds of information that the eTailer wishes to maintain:
- Their suppliers, including supplier names, addresses, and a logo to display.
- The items made by each supplier (e.g., HP), including the type of item (e.g., printer), the model number (e.g., 693C), and the retail price. Note that different suppliers may use the same model number for different items, even if those items are of the same type and price. However, one supplier will not use the same model number for two different items.
- Customers, including their name, address, and email.
- Credit cards, including the company (e.g., Visa), number, and expiration date. Each customer may have several credit cards on file, but each credit card belongs to only one customer.
- Orders. Each order has a unique ID, has a single customer who placed the order. One of the customer's credit cards was used to pay for the order, and the order must tell which. A customer can place several orders and use different credit cards for each. An order is for some set of items, and their is an associated quantity for each. There are several ways to represent orders, but try to use a design that does not allow an order to be placed for a customer who does not own the credit card used to pay for the order.
Give an E/R design for this database. Briefly explain your reasoning, including the intuitive meaning of any relationships you use and any entity sets you use other than suppliers, items, customers, and orders. Do not forget to indicate keys, many-one relationships, and weak entity sets in the appropriate ways.
(10 pts.) It is not always possible to replace a three-way relationship by two (or even three) two-way (binary) relationships. Suppose there is a three-way relationship among entity sets A, B, and C. Suppose also that there is some relationship set S representing the ``current value'' of this relationship. If we replace this relationship by relationships A-B, A-C, and B-C, we form the relationship sets for these new relationships by ``projecting'' each triple (a,b,c) in S onto its A and B components for A-B, and similarly for the other two binary relationships. Give an example of two relationship sets S1 and S2 (for the three-way relationship) that are different, and yet their projections onto the three binary relationship sets are each the same. Note that this situation demonstrates that the three-way relationship contains more information than the three two-way relationships. If you cannot solve this problem, then for partial credit try showing the same result, but assume that we use only two of the three binary relationships, e.g., S1 and S2 have the same projections for A-B and B-C only.
(10 pts.) Suppose we have a collection of entity sets related by isa, such that their hierarchy forms a balanced binary tree with n levels. If we follow the rule outlined in the book that any entity can have representatives in the root and any subtree extending from the root, how many different subsets of these 2^n - 1 entity sets can hold exactly the set of representatives for some entity? Give the counts of different subsets for n = 1, 2, 3, 4, and 5. Note, for example, that n = 1 is the case where there is a single entity set --- the root --- and n = 2 is the case of a root and two children.