OTC Assignment #1 FAQ

Heirarchy problem:

This problem asks about the possible number of combinations in the tree 
that have the set A in it. For example, a simplified example is like so:

Suppose we have an entity set A with subclasses B and C. Also, B has 
subclasses W and X and C has subclasses Y and Z.
i.e., a diagram (with ISA removed) like:

        A
      /   \
    B      C
   / \    / \
  W  X   Y   Z

Then if e is in A, there are many sets of entity sets in which e could be:

{A}, {A,B}, {A,C}, {A,B,C}, {A, B, W}, {A, C, Y, Z} and so on...

Also note that there is nothing wrong with an entity being in several 
entity sets that are part of one ISA hierarchy.  More properly, the entity 
is represented in several of these entity sets.  The place to read is from 
the bottom of p. 33 to the box on p. 37, especially the paragraph in
the middle of p. 35.

----------------------------------------------------------------------

            A
           /\
          /  \
         B    C
        /\    /\
       D  E  F  G

If entity e is in G, what does it mean for a subset of entity sets to
"REPRESENT" e.

e can be in any subset of entity sets (be "represented" in them), the only 
constraint being that if e is in an entity set, it is also in its "parent" 
entity set. Thus, the subset {A,C,G} is legal, while the subset {D,E,F,G} 
is not (since it includes D but not its parent, for example); but the set 
{A,B,C,D,E,F,G} is legal.
 
--------------------------------------------------------------------------

Cardinality is defined as the number of elements in a given mathematical 
set. In our case, the number of entities in the entity set.

--------------------------------------------------------------------------

Ternary relation question:

Here, please realize that A is not a key for B and C. In a dual relation, 
if we have:

|---|          /\               |---|
| A |---------/R \------------->| B |
|---|         \  /              |---|
               \/

then A is indeed a key for B, but that is not the case for ternary 
relations. 

For the purposes of this question, AB->C and AC->B.

To help you understand the problem simplest is to work with a small 
example.

Suppose |A| = 5, |B| = 3, and |C| = 4.

Let A = {a1,...a5}, B={b1,b2,b3}, C={c1,c2,c3,c4}.

Note that there is a *range* of possible values for the total number of
combinations of values.

For example,

(a1,b1,c1), (a1,b2,c2), (a2,b2,c1) is a legal relationship set with 3 
triples (t=3). 

(a1,b1,c1) is a legal relationship set with just 1 triple (t=1).

There is thus not a unique value for t. Some combinations are not legal; 
for example:

(a1,b1,c1), (a1,b1,c2)

is not legal, because it violates AB->C (the two triples have the same A 
and B values but different C values). Because of this restriction, there 
is a maximum value for t, beyond which there is certainly some illegal
combination of tuples in the relationship set. The problem for you to 
solve is to figure out the maximum value of t.


If you still have questions, please email cs145-help@lists.stanford.edu