CS145 Assignment #1

Due Wednesday, October 6, 1999

Some Mechanics for Homeworks

For All Students

For On-Campus Students

For SITN students

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.

Step 1 of Your PDA (Personal Database Application)

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 need not necessarily require advanced features such as subclassing or weak entity sets.

(a)

(25 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)

(25 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.

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

1. (25 pts.) We would like to design a database that can be used to store information about the structure of C programs. To make life simple, we shall consider only a few statement types: assignments, if-statements (with optional else), and blocks (groups of statements surrounded by {...}). For example, the following code:

        if(x == y) {
            a = b;
            c = d;
        }
   

   shows an if-statement, whose body is a block, and within that block are two assignment statements. The if-statement has a condition (x == y), as well as a body. This if-statement has no ``else part,'' however.

   Design an E/R diagram in which Statement, Condition, and Identifier (a variable, such as x or a above) are important entity sets. Different kinds of statements have different constitutents. For example, if-statements (without else) have a condition and a statement that is the body of the if-statement.

   Blocks have zero or more statements in a list. Your E/R diagram should represent the different kinds of statements and provide enough structure so that the data (entities and relationship sets that form the actual database) would allow us to determine the constituents of each statement of a program (e.g., that the particular if-statement shown above has the block {a=b;c=d;} as its body and the expression x==y as its condition). It is appropriate to invent a key attribute used to identify each statement. Your diagram should also allow us to tell which identifiers appear in which assignment statements and in which conditions.

   If the above specifications are not completely clear, you may resolve ambiguities in any reasonable way; just tell us what you assume.

2. (15 pts.) Consider an E/R diagram such as the one below, with a ternary relationship and arrows entering two of the related entity sets, A and B.

                                       / \
                   |---|              /   \              |---|
                   | A |<-------------     ------------->| B |
                   |---|              \   /              |---|
                                       \ /
                                        |
                                        |
                                      |---|
                                      | C |
                                      |---|
   

   There is a correct interpretation, which is that, given A and C entities, there is at most one related B entity, and, given B and C entities, there is at most one related A entity. There is also an incorrect interpretation ``given a C entity, there is at most one related A entity and at most one related B entity.''

   (a)

   Give an example of a relationship set that meets the correct interpretation of the diagram but does not meet the incorrect interpretation. You may use abstract entities, like a1, a2, b1, and so on, or you may give the entity sets a real interpretation (e.g., movies), and use actual values in the triples of your relationship set.

   (b)

   Does every relationship set that satisfies the incorrect interpretation also satisfy the correct interpretation? Justify your answer.

   (c)

   On the other hand, if the incorrect interpretation is what we want to say, there is another E/R diagram that says it. Draw this diagram.

3. (10 pts.) Worldwide phone numbers consist of a country code, an area code, an exchange, and a (four-digit) number. For example, Ullman's office phone is 001 (country code for the US), 650 (US area code), 725 (exchange within its area code), and number 4802. Treating country codes, area codes, exchanges, and ``numbers'' as separate entity sets, draw an appropriate E/R diagram. Indicate on the diagram what the keys are for each of the entity sets, using the ``weak entity set'' notation that was developed for this purpose.