Re: Efficient XPath 2.0 expression to return each <row

On Thu, Dec 13, 2018 at 06:07:35PM -0000, Costello, Roger L. costello@xxxxxxxxx scripsit:
> I have a large XML document containing data about airports around the world:
[...]
> I want an XPath 2.0 expression to return each <row> element for which there are other <row> elements having the same navaid. For the above example, I want the XPath expression to return the first and third <row> elements.
> 
> Here is one way to do it:
> 
> //row[navaid = (preceding-sibling::row/navaid, following-sibling::row/navaid)]
> 
> Eek! That is horribly inefficient. I ran that XPath expression on my XML document and it took a long time to finish.
> 
> Is there an efficient XPath 2.0 expression to solve this problem?

Probably not.

What you want to answer is "who are the others like me?" and this
compels you to either create some kind of mapping (XQuery maps are just
the thing; so are XSLT keys (or maps!)) so you can just ask the mapping,
or it compels you to stand on each node in turn and check all the
previous and following nodes for similarity, which is going to be
n^yikes in efficiency terms.

But the essential point is that you can't efficiently answer the
question relative to any single context node; if you try to answer it
from the document element, you suddenly need data structures XPath
hasn't got, and if you try to answer it from each row, you have to
re-commpute things.

-- Graydon