W3C home > Mailing lists > Public > w3c-ietf-xmldsig@w3.org > January to March 2002

Alternative XPathFilter - a picture says more...

From: Christian Geuer-Pollmann <geuer-pollmann@nue.et-inf.uni-siegen.de>
Date: Wed, 20 Mar 2002 00:23:40 +0100
To: John Boyer <JBoyer@PureEdge.com>, reagle@w3.org
Cc: w3c-ietf-xmldsig@w3.org
Message-ID: <52945311.1016583820@pinkpanther>
Hi Joseph,
ho John,

maybe a picture says more than thousand words ;-)) (I renamed the include 
to include-but-search to indicate that it has to be traversed).

Given the tree in the picture. I arbitrarily selected some nodes (single 
nodes on the right side or contingous areas on the left) which are to be 
selected by this xpath transform. Black nodes are to be included in the 
output, white nodes are to be omitted.

The root node A is labeled "exclude-but-search". This means that it is not 
to be outputted, but some descendants (probably) are.

The black node B on the left side is labeled "include-but-search" because 
itself is to be outputted and it's descendants must be traversed to copy 
them to the result node set.

The unselected child C is labeled "exclude" because itself and _all_ it's 
descendants are omitted/not outputted. So we don't need the -but-search 
suffix because we won't find any selected nodes inside - this is an 
optimization.

The unselected subtree D is in an area where no nodes are selected, but if 
we label it 'exclude', the algorithm won't traverse it and we can save 
time. But without that label, it'd work, though.

The selected-subtree E in the middle is "include-but-search" because itself 
and all it's descendants are to be outputted.

On the right side, we have this annoying exclude-but-search, 
include-but-search, exclude-but-search alternation because here are no nice 
subtrees which are the main focus of this transform but a 'real' nodeset 
which could also be handled by our old XPath transform...

We have 7 contingous areas or nodes and NEED 7 labels (XPath evaluations) 
for this, while we can optimize the speed with 1 additional label (the 
"exclude" for node D).

Is my idea now a little bit clearer now?


Best regards,
Christian


xpath2filter_tree.gif
(image/gif attachment: xpath2filter_tree.gif)

Received on Tuesday, 19 March 2002 18:19:29 GMT

This archive was generated by hypermail 2.2.0 + w3c-0.29 : Thursday, 13 January 2005 12:10:15 GMT