Conference rusure::math

     I don't want to give the impression that I know how to
     approach this problem :-) ... but it seems a bit
     underspecified to me.
     
     Can we assume that the +, *, -, / refer to operations over a
     field, so that, for example, + and * are commutative and
     associative, + and - are inverses, etc.?
     
     Can the identifiers have numerical coefficients?  If so,
     are they limited to integral or rational or real or complex
     coefficients?
     
     If a field, is it of characteristic zero (i.e., 1 + 1 + ...
     + 1 is never 0)?
     
     How do you want to handle a predicate of the form a1 * b1 = 0?
     (if it is allowed, that is)
     
     What would you do with this algorithm if you had it? :-)
     
     Dan

    Hi,
    
    I think this should answer all the questions in .1
    
    All the identifiers can assume real values. They are real variables.
    Each of the expressions can also have real numerical constants.
    Actually, these constants can belong to the third class (c)
    whose values are c1, c2, etc. Thus the constant 0 may be replaced
    by ci (I dont want to worry about a1 * b1 = 0, unless there
    is an elegant way of handling it).
    All commutative and associative laws that apply to real arithmetic
    may be assumed. 
    
    You may ignore concerns about overflow and underflow.
    
    Hope this helps.
    
    Murali.
           

     I have no real ideas for approaching this problem.
     
     You could change the initial trees so they are not binary,
     for example, changing
     
                       +
                      / \
                     a1  +
                        / \
                       a2  b1
     
     into
     
          (+ a1 a2 b1)
     
     Then the top level looks like
     
          (= (? ...) (? ...))
     
     If the "..." terms are all variables then depending on the
     operation you can try moving terms to the other side.  But
     if there are nested operations, like
     
          (= (+ ... (* a1 b1) ...) (? ...))
     
     then I don't see how to proceed automatically.  This seems
     like one of those things that are easier to do by hand than
     to program.
     
     What would you do with such a program if you had it?
     
     Dan

re .0:
> For example, a1 = b1 + b2*a2 cannot be split up that way.

Prove it.

    Reply to .3:
    
    Assume there are two (database) relations A and B.
    The attributes of A are a1, a2, ..., am and the attributes of B
    are b1, b2, ..., bn. A join predicate is of the form 
    expr1 = expr2, where each expression contains references to a's and
    b's. If I manage to bring all the a's to one side and all the b's to the
    other, then I can perform a simple join (reducing the processing
    costs). Otherwise, I have to perform a cartesian product of A and
    B (very expensive) and filter out those tuples that satisfy the
    predicate.
    
    If you are not familiar with database terminology, please see any
    book on introductory databases.
    
    Reply to 0.4
    
    Don't know of any good proof (other than an exhausting all
    possibilities). If you can come up with one, great.
    
    Murali.

Suppose a1 = b1 + a2*b2 can be split up as F(a1,a2) = G(b1,b2).
That is, assume there exist functions F and G such that:

	  x1 = y1 + x2*y2    implies   F(x1,x2) = G(y1,y2),	(1)
and	F(x1,x2) = G(y1,y2)  implies     x1 = y1 + x2*y2.	(2)

for any x1,x2,y1,y2.

By (1),
	F(a,b) = G( b*c - a, c )				(3)
	F(d,e) = G( e*f - d, f )				(4)

for any a, b, c, d, e, and f.

We wish to equate the parameters to G in (3) and (4).  If b<>e, replace the
free variables f and c with (a-d)/(b-e).  Then

	F(a,b) = G( b*(a-d)/(b-e) - a, (a-d)/(b-e) )
	       = G( (a*e - b*d)/(b-e), (a-d)/(b-e) )
	       = G( e*(a-d)/(b-e) - d, (a-d)/(b-e) )
	       = F(d,e)						(5)

for any a, b, d, and e, with b <> e.

But F(a,b) = F(x,1+b) = F(d,b); so (5) holds for any a, b, d, and e.

Thus, F(a,b) is independent of the values of a and b, and so it must be a
constant function.  Similarly, G is also a constant function, and since
F(0,0) = G(0,0), F and G must be the same constant function.

But by (2), F(1,0) = G(2,0) implies 1 = 2.  Thus, the assumption is wrong;
there are no such functions F and G.

					- Gilbert

P.S.  I hope this proof helps illuminate the original problem.

>By (1),
>	F(a,b) = G( b*c - a, c )				(3)
>	F(d,e) = G( e*f - d, f )				(4)

I think the sign of G's first arg is reversed, it should be:

	F(a,b) = G( a - b*c, c )				(3)
	F(d,e) = G( d - e*f, f )				(4)

(but the negation cancels in the following expansion, so the proof
is still valid, and still very pretty!)

The proof below is merely a restatement and of Peter Gilbert's proof in .6,
but it may point the way to a method for determining whether the variables
can be partitioned.

Rewriting the equation, f(a1,a2,b1,b2) = a1 - b1 - a2*b2 = 0.
The equation can be partitioned into the form g(a1,a2) = h(b1,b2) iff there
are functions g and h such that f(a1,a2,b1,b2) = g(a1,a2) - h(b1,b2) for all
a1, a2, b1, b2.

In that case,
g(a1,a2) - h(b1,b2) = f(a1,a2,b1,b2) = a1 - b1 - a2*b2   for all a1, a2, b1, b2
g(c1,c2) - h(b1,b2) = f(c1,c2,b1,b2) = c1 - b1 - c2*b2   for all c1, c2, b1, b2

Subtracting,
g(a1,a2) - g(c1,c2) = f(a1,a2,b1,b2) - f(c1,c2,b1,b2)
		    = a1 - c1 - a2*b2 + c2*b2    for all a1, a2, b1, b2, c1, c2

But this is clearly impossible, because b2 is "unbound" on the RHS. The
difference can be made arbitrary; Peter's proof picks b2 such that it is 0.

The only times the decomposition of f into g and h is possible is when all the
b's vanish from the difference above. The difference is easy to construct; an
algebraic demonstration that the b's vanish is less easy, but the techniques
that programs like MACSYMA use to simplify equations should apply.