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
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.
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
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
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
Any other assistance by another person constitutes a violation
of the honor code and will be treated as such.
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.
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
weak entity sets, if they are not appropriate for your application.
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.
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.
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.
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
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
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
Customers, including their name, address, and email.
Credit cards, including the company (e.g., Visa), number, and expiration
Each customer may have several credit cards on file, but each credit
card belongs to only one customer.
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
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.
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,
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.
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.