Detecting duplicate derivations

• Unique ID scheme using hash table
• Base case: Give unique ids to relations. r=1, s=2 ...
• One level up: r x s
  • Compute h ( x, id(r), id(s))
  • Look up hash table to find (x, 1, 2)
  • If not found give new id to r x s
• At higher levels: same idea, using ids of inputs (must compute them first if not available)
• If excatly same expression exists, will be found fast.
• Note:
  • Transformation of E= E : put under same equivalence node
  • Equivalence node represents set of logically equivalent expressions which implies can choose any one of them.
  • Operation nodes need all inputs
  • AND-OR DAG
    OR: Equivalence node
    AND: Operation node
  • Algorithm/Enforcer node have:
    cost = local cost + sum of cost of inputs
  • Equivalence nodes have
    Cost = min (cost of inputs)
  • Must also deal with physical properties