Re: [xml-dev] I have implemented SAX based XPath Engine
MK> OK. So let's change the query to
//book[author = editor]/price
Which of course is true if any of the book's authors has the same name as
one of its editors. You don't know the order or cardinality of the children
author, editor, and price, so I assume you are "remembering" all the author,
editor, and price children until you hit the end tag of a book; you're then
evaluating the predicate, and if it's true, you output all the price
children?
ST>
Yes. you are correct;
MK>
How much do you "remember" about the price children?
SK>
only the location of price element. because that is what user is interested.
here location mean, the unique xpath to that price element say
/library[1]/book[5]/price[1]
MK>
There's a question mark
here because you don't really know what information the user wants about the
price elements: they might want the string value, or the attributes, or
perhaps the children,...
SK>
wrong. I know what much information user wants from price elements in
xpath compilation stage only. so I simply remember the location of price element
if user would have given xpath:
//book[author = editor]/price/@type
Then during compilation stage, I know that he is interested in type attribute.
MK>
For author and editor, I guess the minimum that needs to be remembered is
the string-value of each author and editor child, and you can claim to be
"pure streaming" if the only memory you allocate is enough to hold these
values?
SK>
Yes. during compilation stage, it is seen that he is comparing nodesets.
nodesets are compared by comparing string value of each nodeitem. so only
the string value is remembered.
for more details:
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/model/expr/bool/Comparison.java
from its constructor, you can see that it requires each its member to be of type Datatype.STRINGS
and its member will be:
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/model/expr/nodeset/list/Strings.java
which will remember only stringized nodeitems of nodeset.
------------------------------------------------------------------------
ST>XMLDog do supports absolute paths in predicate also. for example:
/*/fibonacci[ count(/*/fibonacci) - 1 ]
Does that involve more than one scan/parse of the input file? If not, how is
it done?
ST>
No. it requires only one parse over input. XMLDog does xpath evaluation in single parse.
during compilation stage, each expression knows when its evaluation starts and finishes.
an expression adjusts its evaluation period depending on its members evaluation span.
here count(/*/fibonacci) is evaluation starts when document started and ends when document ended.
it parent NodeSet expression will remember its cached result until its member gets evaluated. i.e
till the document end.
---------------------------------------------------------------------------
MK> You've got an example that does *[last()]. Do you allow *[last() - 1]?
Is this done with a pure streaming approach?
ST> Yes. it supports [last()-1] also;
MK> How do you do this? With multiple passes over the data? Or with a
lookahead buffer?
ST> in single pass over data, it is evaluated; same as before the results are cached
until its predicates are evaluated;
----------------------------------------------------------------------------
I understand that it is difficult to digest how my implemenation works, in simple words.
The engine is rewritten lots of times to accomodate all xpath evaluation. i.e
the algo is refined/modifed N number of times.
I added the xpath you have mentioned: //book[author = editor]/price to my testsuite.
the input xmlfile is
http://code.google.com/p/jlibs/source/browse/trunk/xmlFiles/library.xml
to confirm that XMLDog handles all cases, i added multple <book> elements in sample xml
with different order of author, editor, price.
To make it more complicated, i added nested <book> elements between author, editor, price elements.
and the testcase has passed.
The XMLDog supports debug mode. in this mode it prints lot of information about what context information
it is cached, when it is discarded.
To enable debug mode, you need to edit following file and change value static variable called debug to true,
and recompile jlibs.
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/Debuggable.java
For your reference, i am attaching the output of XMLDog for //book[author = editor]/price.
in the beginning of this file, you will see the compiled tree for given xpath.
rest of the file shows, details of what is happening in engine for each sax event.
- Santhosh
//book[author = editor]/price
Which of course is true if any of the book's authors has the same name as
one of its editors. You don't know the order or cardinality of the children
author, editor, and price, so I assume you are "remembering" all the author,
editor, and price children until you hit the end tag of a book; you're then
evaluating the predicate, and if it's true, you output all the price
children?
ST>
Yes. you are correct;
MK>
How much do you "remember" about the price children?
SK>
only the location of price element. because that is what user is interested.
here location mean, the unique xpath to that price element say
/library[1]/book[5]/price[1]
MK>
There's a question mark
here because you don't really know what information the user wants about the
price elements: they might want the string value, or the attributes, or
perhaps the children,...
SK>
wrong. I know what much information user wants from price elements in
xpath compilation stage only. so I simply remember the location of price element
if user would have given xpath:
//book[author = editor]/price/@type
Then during compilation stage, I know that he is interested in type attribute.
MK>
For author and editor, I guess the minimum that needs to be remembered is
the string-value of each author and editor child, and you can claim to be
"pure streaming" if the only memory you allocate is enough to hold these
values?
SK>
Yes. during compilation stage, it is seen that he is comparing nodesets.
nodesets are compared by comparing string value of each nodeitem. so only
the string value is remembered.
for more details:
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/model/expr/bool/Comparison.java
from its constructor, you can see that it requires each its member to be of type Datatype.STRINGS
and its member will be:
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/model/expr/nodeset/list/Strings.java
which will remember only stringized nodeitems of nodeset.
------------------------------------------------------------------------
ST>XMLDog do supports absolute paths in predicate also. for example:
/*/fibonacci[ count(/*/fibonacci) - 1 ]
Does that involve more than one scan/parse of the input file? If not, how is
it done?
ST>
No. it requires only one parse over input. XMLDog does xpath evaluation in single parse.
during compilation stage, each expression knows when its evaluation starts and finishes.
an expression adjusts its evaluation period depending on its members evaluation span.
here count(/*/fibonacci) is evaluation starts when document started and ends when document ended.
it parent NodeSet expression will remember its cached result until its member gets evaluated. i.e
till the document end.
---------------------------------------------------------------------------
MK> You've got an example that does *[last()]. Do you allow *[last() - 1]?
Is this done with a pure streaming approach?
ST> Yes. it supports [last()-1] also;
MK> How do you do this? With multiple passes over the data? Or with a
lookahead buffer?
ST> in single pass over data, it is evaluated; same as before the results are cached
until its predicates are evaluated;
----------------------------------------------------------------------------
I understand that it is difficult to digest how my implemenation works, in simple words.
The engine is rewritten lots of times to accomodate all xpath evaluation. i.e
the algo is refined/modifed N number of times.
I added the xpath you have mentioned: //book[author = editor]/price to my testsuite.
the input xmlfile is
http://code.google.com/p/jlibs/source/browse/trunk/xmlFiles/library.xml
to confirm that XMLDog handles all cases, i added multple <book> elements in sample xml
with different order of author, editor, price.
To make it more complicated, i added nested <book> elements between author, editor, price elements.
and the testcase has passed.
The XMLDog supports debug mode. in this mode it prints lot of information about what context information
it is cached, when it is discarded.
To enable debug mode, you need to edit following file and change value static variable called debug to true,
and recompile jlibs.
http://code.google.com/p/jlibs/source/browse/trunk/xml/src/jlibs/xml/sax/sniff/Debuggable.java
For your reference, i am attaching the output of XMLDog for //book[author = editor]/price.
in the beginning of this file, you will see the compiled tree for given xpath.
rest of the file shows, details of what is happening in engine for each sax event.
- Santhosh