[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Why not reinvent the wheel?

• From: Joe English <jenglish@f...>
• To: Vasileios Papadimos <vpapad@c...>, xml-dev@l...
• Date: Fri, 02 Mar 2001 13:02:48 -0800

Jonathan Robie wrote:

> Vasileios Papadimos wrote:
>
> >An unordered join would also be associative (right?), and that would turn
> >XML query optimization back into the exponential problem we know and love :-
> )
>
> Your first sentence is something I really want to think about before
> answering. As for your second...well, good query optimization is going to
> be important.


Ordered and unordered joins are both associative, in the sense that:

    [(x1,x2,x3) | x1 <- e1, (x2,x3) <- [(x2,x3) | x2 <- e2, x3 <- e3]]
==
    [(x1,x2,x3) | (x1,x2) <- [(x1,x2) | x1 <- e1, x2 <- e2], x3 <- e3]


Unordered joins however are commutative:

    FOR x1 in e1, x2 in e2 RETURN ...
==
    FOR x2 in e2, x1 in e1 RETURN ...

This is what opens up more possibilities for optimizations;
it holds for unordered joins, but not for ordered ones.

The exponential-time problem Vasileios refers to is in the size
of the query, but since it can give you a polynomially-sized
time reduction in the size of the _input_, it's usually worth
doing.

It seems to me that unordered sequences ought to be the default
in XQuery, not ordered ones.  As long as there is an option to
sort the result by document position, nothing is lost, but there
is much to be gained.


--Joe English

  jenglish@f...

• References:
  • Re: Why not reinvent the wheel?
    • From: Jonathan Robie <Jonathan.Robie@S...>

• Prev by Date: RE: To Buy, or to Build? That is the q...
• Next by Date: RE: is that a fork in the road?
• Previous by thread: Re: Why not reinvent the wheel?
• Next by thread: Re: Why not reinvent the wheel?
• Index(es):
  • Date
  • Thread