Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

RFC: Tree-like applications

by rustic (Scribe)
on Jun 06, 2012 at 11:18 UTC ( #974696=perlmeditation: print w/ replies, xml ) Need Help??

Servus, fellow monks!
Perhaps, this is a computer science class question, I have to post it for my accomplishment. I have a web based application that I've wrote which allows the user to view an existing, initially empty tree and add nodes to it. The tree nodes are stored in a MySQL database. The program is reading them from the database, displays the tree, and add new nodes to it upon the user's request. Each node is identified by a unique node ID and have a parent P.

Now let's assume that this will be the start of a large scale application and it's intended to serve the basis for other tree-like implementations. What will be the approach for writing a re-usable code ? How the software architecture and design will be looking ?

I will provide below the UI and datbase sketches togheter with the source code with some explanations. Anyone can easily try it on a CGI enabled HTTPD and MySQL DB.

Tree Manager


Current Tree:
DepthTree Nodes
0[P: NONE ID: 1]
1[P: 1 ID: 2][P: 1 ID: 3]
2[P: 2 ID: 4] [P: 2 ID: 5][P: 3 ID: 6]
3[P: 5 ID: 7] [P: 5 ID: 8] [P: 5 ID: 9] [P: 5 ID: 10][P: 6 ID: 11]

Add Node To: PID box
Add button

Typing in parent node ID in “PID” box and clicking “Add” button should add a new node, to the node with that ID or produce an error message in case invalid node ID is entered.

The database contains a single table which for the above UI sketch looks like following:

NIDPNIDDEPTH
100
211
311
422
522
632
753
853
953
1053
1163
where NID is the node's ID, PNID is it's parent node ID and DEPTH is the node's level in the tree.

Then, I have two CGI scripts, first - very small for creating the initial DB table:

#!/usr/bin/perl use warnings; use strict; use DBI; use DBD::mysql; use CGI qw( :standard ); my $dbh = DBI->connect( "DBI:mysql:btree", "root", "", { RaiseError => + 1 } ); my $string = "CREATE TABLE Nodes ( NID INT NOT NULL AUTO_INCREMENT, PNID INT NOT NULL, DEPTH INT NOT NULL, PRIMARY KEY(NID) )"; $dbh->do( $string ); $dbh->do( q{ INSERT INTO Nodes ( PNID, DEPTH ) VALUES ( 0, 0 ) } ); $dbh->disconnect(); print header(), start_html( "Database Creation" ); print h4( "The btree Database Tables Has Been Created" );

Here, database btree, table Nodes.

and the Tree Manager itself:
#!/usr/bin/perl use warnings; use strict; use DBI; use DBD::mysql; use CGI qw( :standard ); my $dbh = DBI->connect( "DBI:mysql:btree", "root", "", { RaiseError => + 1 } ); my ( $sth, $results, $err ); if ( param("Add") ) { my $pnid = param("PNID"); $sth = $dbh->prepare( q{ SELECT DEPTH FROM Nodes WHERE NID = ? + } ); $sth->execute($pnid); $results = $sth->fetchrow_arrayref(); warn( $DBI::errstr ) if ( $DBI::err ); if ( $sth->rows == 0 ) { $err = 1; } else { my $query = "INSERT INTO Nodes ( PNID, DEPTH ) VALUES ( " +. $pnid . ", " . ( $results->[0] + 1 ) . " )"; $dbh->do( $query ); } $sth->finish(); } #$sth = $dbh->prepare( q{ SELECT * FROM Nodes ORDER BY DEPTH ASC, PNID + ASC, NID ASC } ); $sth = $dbh->prepare( q{ SELECT DISTINCT( PNID ), DEPTH FROM Nodes ORD +ER BY DEPTH ASC } ); $sth->execute(); $results = $sth->fetchall_arrayref(); warn( $DBI::errstr ) if ( $DBI::err ); $sth->finish(); print header(), start_html( "Tree Manager" ); print h3( { -align => "center" }, "Tree Manager" ), hr(), table( { -border => 0, -width => "100%" }, Tr( th( { -align => + "left", -colspan => "2" }, "Current Tree:" ) ), Tr +( th( { -width => "5%" }, "Depth" ), th( "Tree Nodes" ) ) ); my ( $pnid, $content, $td, $depth, $tman ); for ( @$results ) { if ( $depth != $_->[1] ) { # here we change the tree level $tman .= Tr( td( { -align => "center", -width => "5%" }, $ +depth ), $td ); $td = ""; } $depth = $_->[1]; $sth = $dbh->prepare( q{ SELECT * FROM Nodes WHERE PNID = ? } +); $sth->execute($_->[0]); $pnid = $sth->fetchall_arrayref(); warn( $DBI::errstr ) if ( $DBI::err ); for ( @$pnid ) { $content .= " [P: $_->[1] ID: $_->[0]] "; } $td .= td( { -align => "center" }, $content ); $content = ""; } $dbh->disconnect(); $sth->finish(); $tman .= Tr( td( { -align => "center", -width => "5%" }, $depth ), $td + ); print table( { -border => 1, -width => "100%" }, $tman ); print h5("Check you enetered correctly the parrent node!") if $err; print start_form(), table( { -border => 0, -width => "100%" }, Tr( th( { -align => "le +ft", -width => "10%" }, "Add Node To:" ), td( textfield( -name => "PNID", -size => 10 ) ) ), Tr( td( submit( "Add" ) ), td() ) ), end_form(); print end_html();
Please note, how can one improve the SQL query for tree traversal ?

And, back to my request for comments... what will be the imrovements one can make in terms of scalabilty and code re-usage ?

Comment on RFC: Tree-like applications
Select or Download Code
Re: RFC: Tree-like applications
by Corion (Pope) on Jun 06, 2012 at 11:30 UTC

    There are two or three more approaches to modelling trees in SQL, described by Joe Celko. There is Trees and Hierarchies in SQL. I didn't find the book worth its price due to the material being online in articles by Celko and also partially in his book SQL for Smarties (of which I only have the first or second edition).

    The data structures and algorithms for the other tree implementations follow different ideas than your "child / parent" approach. The child/parent approach is good for quick inserts into the tree and good for quick updates (moving a subtree).

    Another approach is to materialize the path to each node, for example in a varchar column. Then you get a column like:

    1 1.1 1.2 1.2.1 ...

    In such a structure, you can easily retrieve full subtrees with like comparisons or <= and > comparisons. Inserting is a bit slower and moving subtrees is mediocre.

    Yet another approach is to store per node the covered range of children, min(child_value) and max(child_value) as left / right boundary. This also allows for easy inserts and easy queries for subtrees. Moving subtrees is mediocre again.

      Materialize the path to each node - looks very interesting, one approach worth to know, ++1. As well for the link and nice explanation.
Re: RFC: Tree-like applications
by moritz (Cardinal) on Jun 06, 2012 at 11:44 UTC
      Definitely I had to go for a CPAN search. I agree, perhaps this will be the best approach for a re-usable and scalable code.
Re: RFC: Tree-like applications
by choroba (Abbot) on Jun 06, 2012 at 11:52 UTC
    When we did trees in SQL, we found this trick very valuable. It makes possible to implement $node->descendants quite efficiently. Node insertion, on the other hand, gets slower, because you have to recalulate the id's (but we only stored finished trees, so we did not care).
      A very explanatory article, with nice SQL queries examples.
      Thx!
Reaped: Re: RFC: Tree-like applications
by NodeReaper (Curate) on Jun 07, 2012 at 13:25 UTC
Reaped: Re: RFC: Tree-like applications
by NodeReaper (Curate) on Jun 10, 2012 at 13:02 UTC
Reaped: Re: RFC: Tree-like applications
by NodeReaper (Curate) on Jun 12, 2012 at 12:53 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://974696]
Approved by Corion
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2014-12-18 10:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (49 votes), past polls