Hi Rob,

I think I see how your documents are structured. Depending on the use case, you could try collecting all refs first, throw away the duplicates and then process them. As in:

for $ref in distinct-values(collection('c')//ref/@link) return local:process(@ref)

Hartelijke groet,

Huib.

Verstuurd vanaf mijn iPad

Op 18 jul. 2012 om 08:48 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi Huib,

Thanx for the reply.

I’ve seen this kind of solution before on the internet but this does not work in my case. I don’t have a single @ref-attribute in $node-element. Instead I have several ref-child-elements within a $node-element. (that is what a meant with linear versus iterative) In that case I would have an iteration through the ref-child-elements within my function. So there will be an iteration of recursive calls. But every time I come back from a recursive call my ref-collection won’t be updated with the processed $nodes from this call but will be reset to its original value. This because of the declarative nature of the XML-tools.

So now I started programming in JAVA in eclipse and stored my XML-files in a BaseX-database. I can connect to the database but I was wondering what the best approach would be from there.

Any suggestions would be welcome. Van: Huib Verweij [mailto:hhv@home.nl] Verzonden: dinsdag 17 juli 2012 20:33 Aan: Rob CC: basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

I think XQuery and XSLT are very much capable of handling your example. If I understand it correctly, I do not know what linear or iterative recursion is.

In fact I programmed something similar to the algorithm you describe in XQuery recently. I was processing nodes from the BaseX database though, not XML files. Starting with the first node and an empty sequence as the two arguments to the function I process only references that are NOT in the sequence.

declare function local:refs($node, $refs) { if ($node/@ref) then if (empty(index-of($refs, $node/@ref)) then let $processedNode := <do something with $node> return local:refs($processedNode, (@ref, $refs)) else ... else <process all children of $node> }

Well, it looked something like that. You get the idea I hope. Just add every processed reference to $refs and check that the current @ref is not in $refs before you process it.

If storing your XML inside BaseX is not an option you might try out Nux (http://acs.lbl.gov/software/nux/), I have used it successfully to process XML files in the past, simply using the fire-xquery command line tool.

Regards,

Huib Verweij.

Verstuurd vanaf mijn iPad

Op 17 jul. 2012 om 15:01 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi,

Can you please help me solving a challenge I have with a specific type XML-query?

I’ve a bunch of XML-files that are referencing each other. So, a XML-file can reference to multiple XML-files and a XML-file can be referenced to by multiple XML-files. This whole reference-structure could be cyclic. Actually an m:n relationship between XML-files with possible cyclic structure.

The standard solution would be to build a recursive-routine for processing an XML-file that, before actually processing the XML-file, checks in some way, for example with some sort of “file-in-process”-buffer, if the XML-file isn’t already being processed. If not store the name in this buffer, processes the XML-file and initiate the recursive routine for the referenced XML-files.

A structure like this (not real code (at all)):

INSTANTIATE Guard FROM COLLECTION

PROCESS-RECURSIVELY( XML-fileName) { PROCESS( XML-fileName)

            ITERATE Called-XML-file THROUGH XML-file//call-ELEMENT {
                           IF NOT ( Guard.EXISTS( Called-XML-file.NAME) {
                                           Guard.ADD( Called-XML-file.NAME)

                                           PROCESS-RESURSIVELY(Called-XML-file.NAME)
                           }
            }

}

PROCESS-RESURSIVELY(“start-file”)

I found out that, but I could be mistaken, that the standard W3C-XML-tooling (XPATH, XQUERY, XLST) can’t handle this situation because of their declarative nature. Recursiveness is possible with these tools but only in a linear way not in an iterative way.

That is why I’m looking for alternatives. Hopefully BaseX can help me out here. I’ve BaseX and the JAVA-examples in eclipse running. I’m b.t.w. nor a JAVA- nor an eclipse-expert so it was a bit of a struggle, but I managed.

My question: What is the best way to approach this challenge? Can you give me some tips?

Kind regards,

Rob Stapper

Meine frage ist in English weil mein Deutsch nicht so gut is wie mein Englisch. Enschuldigung dafür. ;-)

I am using the Free version of SPAMfighter. SPAMfighter has removed 501 of my spam emails to date.

Do you have a slow PC? Try free scan! _______________________________________________ BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

Hi Dirk,

Thought about that one too.

But for some reason it doesn’t seem to be possible integrating two independent processors; an iterative recursive node-processor and a “sequence of already processed nodes”-processor, in one and the same query-session.

Anyway, I couldn’t make it happen, but then again I’m pretty fresh here.

I can’t help it, but I’m get more and more convinced that is simply isn’t possible because to the declarative nature of the XML-tooling.

Thnx for the reply.

Van: Dirk Kirsten [mailto:dk@basex.org] Verzonden: woensdag 18 juli 2012 10:35 Aan: Huib Verweij CC: Rob; basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

Another possibility would be to return the processed ref-child-elements from the recursive function and to update the sequence of already processed nodes. Therefore you could immediately update the sequence and take this into account for the next iterative step.

Cheers, Dirk

On Wed, Jul 18, 2012 at 9:16 AM, Huib Verweij hhv@home.nl wrote:

Hi Rob,

I think I see how your documents are structured. Depending on the use case, you could try collecting all refs first, throw away the duplicates and then process them. As in:

for $ref in distinct-values(collection('c')//ref/@link)

return local:process(@ref)

Hartelijke groet,

Huib.

Verstuurd vanaf mijn iPad

Op 18 jul. 2012 om 08:48 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi Huib,

Thanx for the reply.

I’ve seen this kind of solution before on the internet but this does not work in my case.

I don’t have a single @ref-attribute in $node-element. Instead I have several ref-child-elements within a $node-element. (that is what a meant with linear versus iterative)

In that case I would have an iteration through the ref-child-elements within my function. So there will be an iteration of recursive calls.

But every time I come back from a recursive call my ref-collection won’t be updated with the processed $nodes from this call but will be reset to its original value.

This because of the declarative nature of the XML-tools.

So now I started programming in JAVA in eclipse and stored my XML-files in a BaseX-database.

I can connect to the database but I was wondering what the best approach would be from there.

Any suggestions would be welcome.

Van: Huib Verweij [mailto:hhv@home.nl] Verzonden: dinsdag 17 juli 2012 20:33 Aan: Rob CC: basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

I think XQuery and XSLT are very much capable of handling your example. If I understand it correctly, I do not know what linear or iterative recursion is.

In fact I programmed something similar to the algorithm you describe in XQuery recently. I was processing nodes from the BaseX database though, not XML files. Starting with the first node and an empty sequence as the two arguments to the function I process only references that are NOT in the sequence.

declare function local:refs($node, $refs) {

if ($node/@ref)

then

if (empty(index-of($refs, $node/@ref))

then let $processedNode := <do something with $node>

return local:refs($processedNode, (@ref, $refs))

else ...

else <process all children of $node>

}

Well, it looked something like that. You get the idea I hope. Just add every processed reference to $refs and check that the current @ref is not in $refs before you process it.

If storing your XML inside BaseX is not an option you might try out Nux (http://acs.lbl.gov/software/nux/), I have used it successfully to process XML files in the past, simply using the fire-xquery command line tool.

Regards,

Huib Verweij.

Verstuurd vanaf mijn iPad

Op 17 jul. 2012 om 15:01 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi,

Can you please help me solving a challenge I have with a specific type XML-query?

I’ve a bunch of XML-files that are referencing each other.

So, a XML-file can reference to multiple XML-files and a XML-file can be referenced to by multiple XML-files. This whole reference-structure could be cyclic.

Actually an m:n relationship between XML-files with possible cyclic structure.

The standard solution would be to build a recursive-routine for processing an XML-file that, before actually processing the XML-file, checks in some way, for example with some sort of “file-in-process”-buffer, if the XML-file isn’t already being processed. If not store the name in this buffer, processes the XML-file and initiate the recursive routine for the referenced XML-files.

A structure like this (not real code (at all)):

==============================================================

INSTANTIATE Guard FROM COLLECTION

PROCESS-RECURSIVELY( XML-fileName) {

PROCESS( XML-fileName)

ITERATE Called-XML-file THROUGH XML-file//call-ELEMENT {

IF NOT ( Guard.EXISTS( Called-XML-file.NAME) {

Guard.ADD( Called-XML-file.NAME)

PROCESS-RESURSIVELY(Called-XML-file.NAME)

}

}

}

PROCESS-RESURSIVELY(“start-file”)

=============================================================

I found out that, but I could be mistaken, that the standard W3C-XML-tooling (XPATH, XQUERY, XLST) can’t handle this situation because of their declarative nature.

Recursiveness is possible with these tools but only in a linear way not in an iterative way.

That is why I’m looking for alternatives. Hopefully BaseX can help me out here.

I’ve BaseX and the JAVA-examples in eclipse running.

I’m b.t.w. nor a JAVA- nor an eclipse-expert so it was a bit of a struggle, but I managed.

My question: What is the best way to approach this challenge?

Can you give me some tips?

Kind regards,

Rob Stapper

Meine frage ist in English weil mein Deutsch nicht so gut is wie mein Englisch. Enschuldigung dafür. ;-)

_____

I am using the Free version of SPAMfighter http://www.spamfighter.com/len . SPAMfighter has removed 501 of my spam emails to date.

Do you have a slow PC? http://www.spamfighter.com/SLOW-PCfighter?cid=sigen Try free scan!

_______________________________________________ BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

_______________________________________________ BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

Hi Christian,

You're probably right. I hoped to find a working example somewhere. But, I still haven't found what I was looking for (this would make a good song title) and that worries me somehow. I'll have a look at the links and do some more digging.

Rob

-----Oorspronkelijk bericht----- Van: Christian Grün [mailto:christian.gruen@gmail.com] Verzonden: woensdag 18 juli 2012 13:50 Aan: Rob CC: Dirk Kirsten; Huib Verweij; basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

I can’t help it, but I’m get more and more convinced that is simply isn’t possible because to the declarative nature of the XML-tooling.

I'm frequently surprised that you can do nearly everything in a functional language (and in particular XQuery) what you can do in an imperative way, but I agree that it often takes a while to find out what's the most elegant approach. You could have a look at the higher order features of XQuery [1,2], or the map module [3], which can be used to create sets of sequences (something that cannot be done in pure XQuery 3.0). If you decide to spend some more time in getting to know the full range of language features, you may eventually prefer to write all your XML code in XQuery, as we do.

Christian

[1] http://docs.basex.org/wiki/Higher-Order_Functions [2] http://docs.basex.org/wiki/Higher-Order_Functions_Module [3] http://docs.basex.org/wiki/Map_Module

Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

Another possibility would be to return the processed ref-child-elements from the recursive function and to update the sequence of already processed nodes. Therefore you could immediately update the sequence and take this into account for the next iterative

step.

Cheers, Dirk

On Wed, Jul 18, 2012 at 9:16 AM, Huib Verweij hhv@home.nl wrote:

Hi Rob,

I think I see how your documents are structured. Depending on the use case, you could try collecting all refs first, throw away the duplicates and then process them. As in:

for $ref in distinct-values(collection('c')//ref/@link)

return local:process(@ref)

Hartelijke groet,

Huib.

Verstuurd vanaf mijn iPad

Op 18 jul. 2012 om 08:48 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi Huib,

Thanx for the reply.

I’ve seen this kind of solution before on the internet but this does not work in my case.

I don’t have a single @ref-attribute in $node-element. Instead I have several ref-child-elements within a $node-element. (that is what a meant with linear versus iterative)

In that case I would have an iteration through the ref-child-elements within my function. So there will be an iteration of recursive calls.

But every time I come back from a recursive call my ref-collection won’t be updated with the processed $nodes from this call but will be reset to its original value.

This because of the declarative nature of the XML-tools.

So now I started programming in JAVA in eclipse and stored my XML-files in a BaseX-database.

I can connect to the database but I was wondering what the best approach would be from there.

Any suggestions would be welcome.

Van: Huib Verweij [mailto:hhv@home.nl] Verzonden: dinsdag 17 juli 2012 20:33 Aan: Rob CC: basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

I think XQuery and XSLT are very much capable of handling your example. If I understand it correctly, I do not know what linear or iterative recursion is.

In fact I programmed something similar to the algorithm you describe in XQuery recently. I was processing nodes from the BaseX database though, not XML files. Starting with the first node and an empty sequence as the two arguments to the function I process only references that are NOT in the sequence.

declare function local:refs($node, $refs) {

if ($node/@ref)

then

 if (empty(index-of($refs, $node/@ref))

 then let $processedNode := <do something with $node>

         return  local:refs($processedNode, (@ref, $refs))

 else ...

else <process all children of $node>

}

Well, it looked something like that. You get the idea I hope. Just add every processed reference to $refs and check that the current @ref is not in $refs before you process it.

If storing your XML inside BaseX is not an option you might try out Nux (http://acs.lbl.gov/software/nux/), I have used it successfully to process XML files in the past, simply using the fire-xquery command line

tool.

Regards,

Huib Verweij.

Verstuurd vanaf mijn iPad

Op 17 jul. 2012 om 15:01 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi,

Can you please help me solving a challenge I have with a specific type XML-query?

I’ve a bunch of XML-files that are referencing each other.

So, a XML-file can reference to multiple XML-files and a XML-file can be referenced to by multiple XML-files. This whole reference-structure could be cyclic.

Actually an m:n relationship between XML-files with possible cyclic structure.

The standard solution would be to build a recursive-routine for processing an XML-file that, before actually processing the XML-file, checks in some way, for example with some sort of “file-in-process”-buffer, if the XML-file isn’t already being processed. If not store the name in this buffer, processes the XML-file and initiate the recursive routine for the referenced XML-files.

A structure like this (not real code (at all)):

==============================================================

INSTANTIATE Guard FROM COLLECTION

PROCESS-RECURSIVELY( XML-fileName) {

            PROCESS( XML-fileName)



            ITERATE Called-XML-file THROUGH XML-file//call-ELEMENT 

{

                           IF NOT ( Guard.EXISTS( 

Called-XML-file.NAME) {

                                           Guard.ADD(

Called-XML-file.NAME)

PROCESS-RESURSIVELY(Called-XML-file.NAME)

                           }

            }

}

PROCESS-RESURSIVELY(“start-file”)

=============================================================

I found out that, but I could be mistaken, that the standard W3C-XML-tooling (XPATH, XQUERY, XLST) can’t handle this situation because of their declarative nature.

Recursiveness is possible with these tools but only in a linear way not in an iterative way.

That is why I’m looking for alternatives. Hopefully BaseX can help me out here.

I’ve BaseX and the JAVA-examples in eclipse running.

I’m b.t.w. nor a JAVA- nor an eclipse-expert so it was a bit of a struggle, but I managed.

My question: What is the best way to approach this challenge?

Can you give me some tips?

Kind regards,

Rob Stapper

Meine frage ist in English weil mein Deutsch nicht so gut is wie mein Englisch. Enschuldigung dafür. ;-)

---

I am using the Free version of SPAMfighter. SPAMfighter has removed 501 of my spam emails to date.

Do you have a slow PC? Try free scan!

---

BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

---

BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

---

BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

Leo,

;-) Ausgezeichnet (briljant)

Exactly what I was looking for. I don't know if I had been able to figure this out on my own, not within reasonable time. Not even with Christian's tips. For me it's a whole new concept.

Danke,

Rob

-----Oorspronkelijk bericht----- Van: Leonard Wörteler [mailto:leo@woerteler.de] Verzonden: donderdag 19 juli 2012 17:28 Aan: Rob CC: basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Dear Rob,

Am 19.07.2012 07:24, schrieb Rob:

You're probably right. I hoped to find a working example somewhere. But, I still haven't found what I was looking for (this would make a good song title) and that worries me somehow. I'll have a look at the links and do some more digging.

it sounds to as if you want to implement a depth-first search over your documents. That's actually pretty easy in XQuery. The trick is to simulate the mutable state (in your case the global variable `Guard`) by threading it through all resursive function calls.

In the attached example I used an example graph from Wikipedia [1]. It is encoded as a list of nodes and references to their children:

<graph> <node name='Frankfurt' id='1'> <child idref='2' /> <child idref='3' /> <child idref='4' /> </node> ... </graph

The graph obviously has many cycles. the function `local:depth-first($graph, $start)` traverses it in depth-first order, visiting every node only once and collecting the node names in order.

I used the Map Module [2] to encapsulate the state and the XQuery 3.0 higher-order function `fold-left(..)` [3], but you could use your own recursive function instead of the latter to iterate over the child nodes and pass the state along.

Hope this helps, cheers, Leo __________

[1] http://en.wikipedia.org/wiki/File:MapGermanyGraph.svg [2] http://docs.basex.org/wiki/Map_Module [3] http://docs.basex.org/wiki/Higher-Order_Functions#Folds

Hi Rob,

as Dirk said, returning the list of processed references is probably what you're after I think. You could implement two functions then, one for recursive processing and one for iterative processing as you say, calling each other as necessary. The last function would require passing the number of refs that still need to be processed to the function, counting down to zero.

function process-node($node, $refs, $refPos){ $currentRef := $node/ref[position() eq $refPos]

if ($refPos gt 0) process-node($node, ($currentRef, $refs), $refPos - 1)

I guess it's the recursive way of iterating :-).

XQuery is a functional programming language, which sometimes requires to think differently about algorithms, perhaps that's what tripping you up? It's certainly not less powerful than imperative programming languages!

Hope this helps.

Huib.

Verstuurd vanaf mijn iPad

Op 18 jul. 2012 om 09:16 heeft Huib Verweij hhv@home.nl het volgende geschreven:

Hi Rob,

I think I see how your documents are structured. Depending on the use case, you could try collecting all refs first, throw away the duplicates and then process them. As in:

for $ref in distinct-values(collection('c')//ref/@link) return local:process(@ref)

Hartelijke groet,

Huib.

Verstuurd vanaf mijn iPad

Op 18 jul. 2012 om 08:48 heeft Rob r.stapper@home.nl het volgende geschreven:

...

Hi Huib,

Thanx for the reply.

I’ve seen this kind of solution before on the internet but this does not work in my case. I don’t have a single @ref-attribute in $node-element. Instead I have several ref-child-elements within a $node-element. (that is what a meant with linear versus iterative) In that case I would have an iteration through the ref-child-elements within my function. So there will be an iteration of recursive calls. But every time I come back from a recursive call my ref-collection won’t be updated with the processed $nodes from this call but will be reset to its original value. This because of the declarative nature of the XML-tools.

So now I started programming in JAVA in eclipse and stored my XML-files in a BaseX-database. I can connect to the database but I was wondering what the best approach would be from there.

Any suggestions would be welcome. Van: Huib Verweij [mailto:hhv@home.nl] Verzonden: dinsdag 17 juli 2012 20:33 Aan: Rob CC: basex-talk@mailman.uni-konstanz.de Onderwerp: Re: [basex-talk] Question concerning querying cyclic network xml-structure.

Hi Rob,

I think XQuery and XSLT are very much capable of handling your example. If I understand it correctly, I do not know what linear or iterative recursion is.

In fact I programmed something similar to the algorithm you describe in XQuery recently. I was processing nodes from the BaseX database though, not XML files. Starting with the first node and an empty sequence as the two arguments to the function I process only references that are NOT in the sequence.

declare function local:refs($node, $refs) { if ($node/@ref) then if (empty(index-of($refs, $node/@ref)) then let $processedNode := <do something with $node> return local:refs($processedNode, (@ref, $refs)) else ... else <process all children of $node> }

Well, it looked something like that. You get the idea I hope. Just add every processed reference to $refs and check that the current @ref is not in $refs before you process it.

If storing your XML inside BaseX is not an option you might try out Nux (http://acs.lbl.gov/software/nux/), I have used it successfully to process XML files in the past, simply using the fire-xquery command line tool.

Regards,

Huib Verweij.

Verstuurd vanaf mijn iPad

Op 17 jul. 2012 om 15:01 heeft Rob r.stapper@home.nl het volgende geschreven:

Hi,

Can you please help me solving a challenge I have with a specific type XML-query?

I’ve a bunch of XML-files that are referencing each other. So, a XML-file can reference to multiple XML-files and a XML-file can be referenced to by multiple XML-files. This whole reference-structure could be cyclic. Actually an m:n relationship between XML-files with possible cyclic structure.

The standard solution would be to build a recursive-routine for processing an XML-file that, before actually processing the XML-file, checks in some way, for example with some sort of “file-in-process”-buffer, if the XML-file isn’t already being processed. If not store the name in this buffer, processes the XML-file and initiate the recursive routine for the referenced XML-files.

A structure like this (not real code (at all)):

INSTANTIATE Guard FROM COLLECTION

PROCESS-RECURSIVELY( XML-fileName) { PROCESS( XML-fileName)

            ITERATE Called-XML-file THROUGH XML-file//call-ELEMENT {
                           IF NOT ( Guard.EXISTS( Called-XML-file.NAME) {
                                           Guard.ADD( Called-XML-file.NAME)

                                           PROCESS-RESURSIVELY(Called-XML-file.NAME)
                           }
            }

}

PROCESS-RESURSIVELY(“start-file”)

I found out that, but I could be mistaken, that the standard W3C-XML-tooling (XPATH, XQUERY, XLST) can’t handle this situation because of their declarative nature. Recursiveness is possible with these tools but only in a linear way not in an iterative way.

That is why I’m looking for alternatives. Hopefully BaseX can help me out here. I’ve BaseX and the JAVA-examples in eclipse running. I’m b.t.w. nor a JAVA- nor an eclipse-expert so it was a bit of a struggle, but I managed.

My question: What is the best way to approach this challenge? Can you give me some tips?

Kind regards,

Rob Stapper

Meine frage ist in English weil mein Deutsch nicht so gut is wie mein Englisch. Enschuldigung dafür. ;-)

I am using the Free version of SPAMfighter. SPAMfighter has removed 501 of my spam emails to date.

Do you have a slow PC? Try free scan! _______________________________________________ BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk

---

BaseX-Talk mailing list BaseX-Talk@mailman.uni-konstanz.de https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk