Homework #1 FAQ

PDA Project

Question: Can you suggest some possible topics for my PDA?
Answer: Feel free to visit any of the course staff during office hours. We'll probably ask you what you are most interested in and try to get you to do a project based on that. You can also look at Sample Projects to get some idea about the scope we expect.

Question: I tried to log on to Oracle following the directions in the or-intro document, but I got a weird response. What did I do wrong?
Answer: Patience, Patience! We'll get you all accounts on Oracle at the appropriate time. That's what the on-line regstration is for, so don't forget to sign up soon, if you haven't done so already. You'll also get an email to the cs145-all list when the accounts are ready.

Question 2

Question: How about S1 = {(0,1,2), (3,4,5)} and S2 = {(3,4,5), (0,1,2)}?
Answer: Nope! While their projections onto AB, BC, and AC are identical (e.g., both yield {(0,1), (3,4)} when projected onto AB), they are really the same relationship set. Note that in a set, order doesn't matter.

Question: A can't think of a real-world example that matches the requirements of the problem.
Answer: Actually, it's better to think of it as an abstract problem, with no interpretation on the entity sets A, B, and C, and no meaning for the entities used in your example.

Question 3

Question: Are there really only n subsets of entity sets arranged in a binary tree of n levels?
Answer: No; sorry. That number is 2^n - 1.

Question: What does representative mean?
Answer: It means the same thing as component in lecture notes 2, when talking about "Different Subclass Viewpoints".

Question: Can I have a hint for this question?
Answer: Yes you may. It is pretty near to impossible to count the number of possible subsets of the entity sets that form a tree at the root for n > 2. Notice that these sets are any that (a) include the root, and (b) if they include a node also include its parent. However, if you think about it, you can write a simple recurrence that gives f(n) (the number of subsets for n) in terms of f(n-1). This recurrence cannot easily be expressed in closed form (at least I couldn't do it), but it enables you to answer the question up to 5.