in reply to Storing Complex Structures in a database
I dont know how database-independent you want to be, but it seems that you are fixed on Relational DBMSes when tree structures are easier mapped to Object databases. The free one with excellent Perl interface written by Lincon Stein is called Acedb. visit http://STEIN.CSHL.ORG for more details
Lincoln Stein has also written Boulder which allows for creation of storage of nested Perl structures.
Depending on where your data is coming from, you may want to take a look at DBIx::Tree which creates tree structures out of self-referential database tables.