# 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.