Phase III: (Due: Nov 30, 2009 - Sunday)

Complete the project by implementing evaluateDRC() method. Once the DRC query is determined to be safe and free of any semantic errors it should be executed to produce the result. Here are some notes:

• Uniquely number the nodes.
• Comparison Node: No work need be done at this node.
• Predicate Node: P(arg1,...,argn). The following steps should be executed to obtain the Relation for this node (assuming the relation for predicate P is denoted by variable Rel:

  1. Rename columns of Rel to C1,...,Cn
      Rel = rename[C1m...,Cn](Rel)
  2. Determine "selection conditions": 
     For each constant argument a condition of the form Ci=argi
     For each repeating variable (in arguments i and j) a condition of the 
     form Ci=Cj
     Let C1,...,Ck be the conditions generated.
  3. Apply each of the selection conditions to Rel:
     Rel = select[Ck](select[Ck-1](...(select[C1](Rel))))   
  4. Project unique columns corresponding to free variables
  5. Rename columns to free variables for the node.
  6. Set relation name to tempN, where N is the unique node number
     for this node.
  
  As an example, let the predicate term be P(X,Y,20,X,'tom',X,Y,Z)
  Then the relation for the node is evaluated as follows:
  
  Rel = get relation for P;
  Rel = rename[C1,C2,C3,C4,C5,C6,C7,C8](Rel);
  Rel = select[C3=20](Rel);
  Rel = select[C5='tom'](Rel);
  Rel = select[C1=C4](Rel);
  Rel = select[C1=C6](Rel);
  Rel = select[C2=C7](Rel);
  Rel = project[C1,C2,C8](Rel);
  Rel == rename[X,Y,Z](Rel);
  

• Query Node: The relation at the query node is simply the relation at the child node.
• Exists Node: The relation at the exists node is obtained by projecting the columns that correspond to the "Free Variables" at the node from the relation at the child node.
• Not Node: No work need be done at this node.
• or Node: The relation at the "or" node is the "union" of all the relations at the child nodes.
• and Node: The relation for the "and" node is computed as follows:
  • First, process "exists", "or" and "predicate" children. Compute the joins of relations at these children nodes.
  • Next process "comparison" children. Apply "selection" conditions (based on comparison node) on the resulting relation
  • Finally, process the "not" children as follows: Compute relation corresponding to child node of "not" node (call it Rel1); Prepare the complement relation (cartesian product of columns from relation that correspond to the free variables of the "not" node) - call it Rel2; Compute relation at "not" node as Rel2-Rel1; and join to relation of previous step.

  Example: Consider the "and" expression:
  p(x,y) and q(y,z) and not(r(x,z)) and not(s(x)) and x>y and x>z
  
  1. Rel = P join Q
  2. Rel = select[x>y](Rel)
  3. Rel = select[x>z](Rel)
  4. Rel2 = project[x](P) times project[z](Q);
     Rel = Rel join (Rel2 - R)
  5. Rel2 = project[x](P);
     Rel = Rel join (Rel2 - S)
  

[raj@tinman phase3]$ java DRC modb
DRC> {x,y | zipcodes(x,y) }
ANSWER(X:INTEGER,Y:VARCHAR)

Number of tuples = 6
67226:Wichita:
60606:Fort Dodge:
50302:Kansas City:
54444:Columbia:
66002:Liberal:
61111:Fort Hays:

DRC> {x | (exists y)(zipcodes(x,y)) }
ANSWER(X:INTEGER)

Number of tuples = 6
67226:
60606:
50302:
54444:
66002:
61111:

DRC> {y | (exists x)(zipcodes(x,y) and x < 60000) }
ANSWER(Y:VARCHAR)

Number of tuples = 2
Kansas City:
Columbia:

DRC> exit
[raj@tinman phase3]$