Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

(OT?) Recursive sql queries?

by BUU (Prior)
on Feb 26, 2004 at 09:28 UTC ( [id://331946]=perlquestion: print w/replies, xml ) Need Help??

BUU has asked for the wisdom of the Perl Monks concerning the following question:

This is probably mostly off topic, but I was using perl to do it since I couldn't figure out a way to do it natively in sql. What I have is basically a tree structure stored in a relational database system. The tree is stored by each node storing the id of it's parent, then I simply fetched the parent node, then fetched all of it's child nodes and recursed on that. However that required a lot of perl glue and I wondered if there was any more elegant method to retrieve the tree from the database?

Replies are listed 'Best First'.
Re: (OT?) Recursive sql queries?
by matija (Priest) on Feb 26, 2004 at 10:12 UTC
    You will have to create a lot LESS perl code, if you use Class::DBI to define your tree structure. You could do something like this:
    package TreeNode; use base 'Class::DBI'; __PACKAGE__->table('forrest'); __PACKAGE__->has_a(parent=>TreeNode); __PACKAGE__->has_many(children=>TreeNode);
    Note that there are several ways of representing a tree structure inside a relational database:
    • You can have a separate table mapping children and parents.
    • You can have each node store the index of one child, and the leftmost (or the rightmost, I suppose) sibling.
    • You can have each node only remembering it's parent
    • If you know the maximum number of children per node, you can have indices for all the children in each node (ugh :-( )

    Each of those representations has it's advantages and it's disadvantages, depending on what you intend to do with the tree once you have it in the database.

    Whichever method you choose to implement, I am willing to bet the code will be much cleaner (more readable and easier to debug) if you use Class::DBI than if you use straight SQL in the code.

Re: (OT?) Recursive sql queries?
by castaway (Parson) on Feb 26, 2004 at 09:50 UTC
    That would depend quite a bit on which Database you are actually using, and if they allow recursive SQL. DB2 does, for example, you define a temporary view, which can select on itself. (Thus each iteration/recursion grabs the parent of the last node stored).

    Eg:

    Recursive SQL (DB2): (WITH X defines a temporary view) WITH trips(destination, route, totalcost) AS ((SELECT destination, destination, cost FROM flights WHERE origin = "SFO") UNION ALL (SELECT f.destination, t.route || ',' || f.destination, t.totalcost * f.cost FROM trips t, flights f WHERE t.destination = f.origin)) SELECT route, totalcost FROM trips WHERE destination = "JFK"; NB: There is no stop condition, so this will run indefinitely..
    (Which is currently sitting around on my scratchpad, together with an iterative solution, using an SQL procedure, which is probably faster than using perl, let the database do the work.)

    The recursion in DB2 works such that each recursion only 'sees' the results of the previous one.

    Anyway, this rambling doesnt help if you dont have DB2, or anything that does such temporary views.. So the other possibility is a stroed sql procedure, assuming you can do those.

    C.

Re: (OT?) Recursive sql queries?
by adrianh (Chancellor) on Feb 26, 2004 at 11:37 UTC
    However that required a lot of perl glue and I wondered if there was any more elegant method to retrieve the tree from the database?

    You might want to consider using an alternate nested set representation of trees, rather than storing a parent ID for each node. Using this representation you can get a subtree with a single SQL query, no recursion necessary.

      Interesting article. Do you have any others? It was a teaser, but didn't provide methods for maintaining said list.

      ------
      We are the carpenters and bricklayers of the Information Age.

      Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

        The second part of the article actually talks about maintaining the tables as far as deleting sub-trees. And the third part of the article gets into inserting sub-trees. It gets more involved and complex as it goes, but if you are reading more than you are writing, this method seems pretty cool.

        -stvn
      Hrm, that looks interesting, the sql is certainly nice and simple enough, but I have to wonder, how do you maintain it? What happens if, after you've got all your nice lft and rgt columns set up, you want to insert a new node someplace?

      After thinking about it for a bit, I think the biggest win is just to store 2 ids, an "ultimate parent" and a "sub parent", then I can just get all my nodes in one query and munge them in to a tree in perl.
        Hrm, that looks interesting, the sql is certainly nice and simple enough, but I have to wonder, how do you maintain it? What happens if, after you've got all your nice lft and rgt columns set up, you want to insert a new node someplace?

        It's not hard. There previously mentioned Intelligent Enterprise article covers one possible method. It's worth a read. You can do lots of useful things (aggregate reports, deleting subtrees, etc.) very quickly over in SQL land without having to bring stuff out of the database and munge it into a hierarchy on the Perl side.

        After thinking about it for a bit, I think the biggest win is just to store 2 ids, an "ultimate parent" and a "sub parent", then I can just get all my nodes in one query and munge them in to a tree in perl.

        This, of course, depends on your definition of "biggest win" ;-)

        This way you have to have an id for every level of subtree that you want to refer to which means a change to the DB schema if you change the hierarchy.

Re: (OT?) Recursive sql queries?
by dragonchild (Archbishop) on Feb 26, 2004 at 12:51 UTC
    Which database system? Oracle (and PostgreSQL, kinda) handle tree structures without a problem. For example, in Oracle you could do the following (all on the SQL*Plus commandline):
    CREATE TABLE FOO ( id NUMBER NOT NULL ,name VARCHAR2(20) ,parent NUMBER ); INSERT INTO FOO VALUES (1, 'First', NULL); INSERT INTO FOO VALUES (2, 'Second 1', 1); INSERT INTO FOO VALUES (3, 'Second 2', 1); INSERT INTO FOO VALUES (4, 'Third', 2); -- This is a formatting command COLUMN id a40; SELECT parent ,name ,LPAD(' ', 6*(Level - 1)) || id AS id FROM foo START WITH id = 1 CONNECT BY parent = PRIOR id;

    I've tested the above, so you can actually just cut'n'paste it. The PG syntax is similar, but not identical, and you have to patch the latest release. (I don't remember where the patch can be downloaded from - google for it.)

    Most other RDBMS do not have this kind of functionality built in. There are PL/SQL packages out there to handle this kind of structure, but they're very kludgy to use.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

Re: (OT?) Recursive sql queries?
by Taulmarill (Deacon) on Feb 26, 2004 at 09:53 UTC
    you may want to fetch all the data at once from the database and let Sort::Tree do the work for you.

      If it's going to be a quickie that will only be run a few times a week (at most), maybe. But doing it a lot negates many of the benefits of having a database management system.

      ----
      : () { :|:& };:

      Note: All code is untested, unless otherwise stated

Re: (OT?) Recursive sql queries?
by schweini (Friar) on Feb 27, 2004 at 01:45 UTC
    i asked something similar a while back, and (as usual) got some rather useful answers...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://331946]
Approved by Roger
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (5)
As of 2024-03-28 15:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found