Transform table to tree
Thursday, 20 January 2011 · 6 messages · last reply 21 Jan 2011
EK
Erdal Karaca20 Jan 2011 22:19 #
I have a table that is to be transformed to a tree:
<entry id="entry1" parentId="parentOfThisEntry" />
<entry id="entry2" parentId="parentOfThisEntry" />
<entry id="entry3" parentId="parentOfThisEntry" />
<entry id="entry4" parentId="parentOfThisEntry" />The tree structure can be constructed by the id/parentId relation. I failed to achieve this... :-(
I am using basex 6.5.
CG
Christian Grün20 Jan 2011 22:21 #
Quoted text · Erdal Karaca · 7 lines
> I have a table that is to be transformed to a tree: > > <entry id="entry1" parentId="parentOfThisEntry" /> > <entry id="entry2" parentId="parentOfThisEntry" /> > <entry id="entry3" parentId="parentOfThisEntry" /> > <entry id="entry4" parentId="parentOfThisEntry" /> > The tree structure can be constructed by the id/parentId relation.
How's the resulting tree gonna look like?
Christian
JC
Hi Erdal
I would think of this approach
- write a function, which takes as an argument value of attribute parentId
- returns tree of all elements, referring to this id (and all nested trees)
- inside call this function recursively for each element again returning next nested level
- in your base XQuery call this function with selecting ids of elements, which are in the root of the document (they will probably have some empty value of @parentId or their parentId will not be found in your document)
It would be nice exercise, but I cannot afford it today.
Jan
2011/1/20 Erdal Karaca <erdal.karaca.de at googlemail.com>
Quoted text · Erdal Karaca · 17 lines
> I have a table that is to be transformed to a tree: > > <entry id="entry1" parentId="parentOfThisEntry" /> > <entry id="entry2" parentId="parentOfThisEntry" /> > <entry id="entry3" parentId="parentOfThisEntry" /> > <entry id="entry4" parentId="parentOfThisEntry" /> > > The tree structure can be constructed by the id/parentId relation. > I failed to achieve this... :-( > I am using basex 6.5. > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk > >
--
*Ing. Jan Vlčinský*
CAD programy
Slunečnicová 338/3, 734 01 Karviná Ráj, Czech Republic
tel: +420-597 602 024; mob: +420-608 979 040
skype: janvlcinsky; GoogleTalk: jan.vlcinsky at gmail.com
http://cz.linkedin.com/in/vlcinsky
LW
Leonard Wörteler21 Jan 2011 14:26 #
Hi Erdal,
try this one (closely following Jan's idea):
Quoted text · Jan Vlčinský (CAD) · 19 lines
> declare function local:link($entries as node()*, $id as xs:string) { > let $children := $entries[@parentId eq $id] > return <entry id='{$id}'>{ > for $child in $children > return local:link($entries, $child/@id) > }</entry> > }; > > let $entries := > <entries> > <entry id="entry1" /> > <entry id="entry2" parentId="entry1" /> > <entry id="entry3" parentId="entry1" /> > <entry id="entry4" parentId="entry2" /> > <entry id="entry5" parentId="entry2" /> > <entry id="entry6" parentId="entry3" /> > <entry id="entry7" parentId="entry3" /> > </entries> > return local:link($entries/entry, 'entry1')
It should be noted that circular references would lead to
non-termination. To detect and prevent that, you could pass a sequence of already linked IDs in another argument.
Hope that helps,
cheers Leo :-)
Quoted text · Jan Vlčinský (CAD) · 57 lines
Am 21.01.2011 12:30, schrieb Jan Vlčinský (CAD): > Hi Erdal > I would think of this approach > > * write a function, which takes as an argument value of attribute > parentId > o returns tree of all elements, referring to this id (and all > nested trees) > o inside call this function recursively for each element again > returning next nested level > * in your base XQuery call this function with selecting ids of > elements, which are in the root of the document (they will > probably have some empty value of @parentId or their parentId will > not be found in your document) > > It would be nice exercise, but I cannot afford it today. > > Jan > > 2011/1/20 Erdal Karaca <erdal.karaca.de > <http://erdal.karaca.de> at googlemail.com <http://googlemail.com>> > > I have a table that is to be transformed to a tree: > > <entry id="entry1" parentId="parentOfThisEntry" /> > <entry id="entry2" parentId="parentOfThisEntry" /> > <entry id="entry3" parentId="parentOfThisEntry" /> > <entry id="entry4" parentId="parentOfThisEntry" /> > > The tree structure can be constructed by the id/parentId relation. > I failed to achieve this... :-( > I am using basex 6.5. > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > <mailto:BaseX-Talk at mailman.uni-konstanz.de> > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk > > > > > -- > *Ing. Jan Vlčinský* > CAD programy > Slunečnicová 338/3, 734 01 Karviná Ráj, Czech Republic > tel: +420-597 602 024; mob: +420-608 979 040 > skype: janvlcinsky; GoogleTalk: jan.vlcinsky at gmail.com > <mailto:jan.vlcinsky at gmail.com> > http://cz.linkedin.com/in/vlcinsky > > > > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
LW
Leonard Wörteler21 Jan 2011 14:31 #
This version preserves the original attributes:
Quoted text · Leonard Wörteler · 9 lines
> declare function local:link($entries as node()*, $id as xs:string) { > let $entry := $entries[@id eq $id], > $children := $entries[@parentId eq $id] > return element entry { > $entry/@*, > for $child in $children > return local:link($entries, $child/@id) > } > };
Leo
Quoted text · Leonard Wörteler · 31 lines
Am 21.01.2011 14:26, schrieb Leonard Wörteler: > Hi Erdal, > > try this one (closely following Jan's idea): > >> declare function local:link($entries as node()*, $id as xs:string) { >> let $children := $entries[@parentId eq $id] >> return <entry id='{$id}'>{ >> for $child in $children >> return local:link($entries, $child/@id) >> }</entry> >> }; >> >> let $entries := >> <entries> >> <entry id="entry1" /> >> <entry id="entry2" parentId="entry1" /> >> <entry id="entry3" parentId="entry1" /> >> <entry id="entry4" parentId="entry2" /> >> <entry id="entry5" parentId="entry2" /> >> <entry id="entry6" parentId="entry3" /> >> <entry id="entry7" parentId="entry3" /> >> </entries> >> return local:link($entries/entry, 'entry1') > > It should be noted that circular references would lead to > non-termination. To detect and prevent that, you could pass a sequence > of already linked IDs in another argument. > > Hope that helps, > cheers Leo :-)
HV
Leonard, you beat me to it!
I just made this:
declare function local:makeTree($root, $table) {
let $children := $table[@parentId eq $root/@id]
return if ($children)
then <entry id="{$root/@id}">{ for $c in $children return local:makeTree($c, $table) }</entry>
else $root
};
let $table :=
(<entry id="entry1" parentId="entry2" />,
<entry id="entry2" parentId="entry3" />,
<entry id="entry3" parentId="" />,
<entry id="entry4" parentId="entry3" />,
<entry id="entry5" parentId="entry2" />,
<entry id="entry6" parentId="entry1" />)
let $root := $table[@parentId eq '']return ($table, local:makeTree($root, $table))
Works very well, but indeed, be aware of circular references. One could remove the children from the table in the recursive call for example.
However, as Christian so efficiently pointed out, I also cannot see how the example Erdal gave can sensibly be made into a tree. So it doesn't really surprise me that Erdal couldn't make the table into a tree.
Kind regards,
Huib.
Op 21 jan 2011, om 14:26 heeft Leonard Wörteler het volgende geschreven:
Quoted text · Leonard Wörteler · 92 lines
> Hi Erdal, > > try this one (closely following Jan's idea): > >> declare function local:link($entries as node()*, $id as xs:string) { >> let $children := $entries[@parentId eq $id] >> return <entry id='{$id}'>{ >> for $child in $children >> return local:link($entries, $child/@id) >> }</entry> >> }; >> >> let $entries := >> <entries> >> <entry id="entry1" /> >> <entry id="entry2" parentId="entry1" /> >> <entry id="entry3" parentId="entry1" /> >> <entry id="entry4" parentId="entry2" /> >> <entry id="entry5" parentId="entry2" /> >> <entry id="entry6" parentId="entry3" /> >> <entry id="entry7" parentId="entry3" /> >> </entries> >> return local:link($entries/entry, 'entry1') > > It should be noted that circular references would lead to > non-termination. To detect and prevent that, you could pass a sequence > of already linked IDs in another argument. > > Hope that helps, > cheers Leo :-) > > Am 21.01.2011 12:30, schrieb Jan Vlčinský (CAD): >> Hi Erdal >> I would think of this approach >> >> * write a function, which takes as an argument value of attribute >> parentId >> o returns tree of all elements, referring to this id (and all >> nested trees) >> o inside call this function recursively for each element again >> returning next nested level >> * in your base XQuery call this function with selecting ids of >> elements, which are in the root of the document (they will >> probably have some empty value of @parentId or their parentId will >> not be found in your document) >> >> It would be nice exercise, but I cannot afford it today. >> >> Jan >> >> 2011/1/20 Erdal Karaca <erdal.karaca.de >> <http://erdal.karaca.de> at googlemail.com <http://googlemail.com>> >> >> I have a table that is to be transformed to a tree: >> >> <entry id="entry1" parentId="parentOfThisEntry" /> >> <entry id="entry2" parentId="parentOfThisEntry" /> >> <entry id="entry3" parentId="parentOfThisEntry" /> >> <entry id="entry4" parentId="parentOfThisEntry" /> >> >> The tree structure can be constructed by the id/parentId relation. >> I failed to achieve this... :-( >> I am using basex 6.5. >> >> _______________________________________________ >> BaseX-Talk mailing list >> BaseX-Talk at mailman.uni-konstanz.de >> <mailto:BaseX-Talk at mailman.uni-konstanz.de> >> https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk >> >> >> >> >> -- >> *Ing. Jan Vlčinský* >> CAD programy >> Slunečnicová 338/3, 734 01 Karviná Ráj, Czech Republic >> tel: +420-597 602 024; mob: +420-608 979 040 >> skype: janvlcinsky; GoogleTalk: jan.vlcinsky at gmail.com >> <mailto:jan.vlcinsky at gmail.com> >> http://cz.linkedin.com/in/vlcinsky >> >> >> >> _______________________________________________ >> BaseX-Talk mailing list >> BaseX-Talk at mailman.uni-konstanz.de >> https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk > _______________________________________________ > BaseX-Talk mailing list > BaseX-Talk at mailman.uni-konstanz.de > https://mailman.uni-konstanz.de/mailman/listinfo/basex-talk
Written for BaseX 6. BaseX may have changed since: please check the current documentation.
⚡Generated with XQuery