First, can you write a SQL statement that gives the information you need from the current schema? Class::DBI can be inefficient when doing traversals across multiple objects because it does lots of individual queries instead of a single query with joins.

If you can write some SQL statements that do the job with the current schema, then you don't need to deal with trees or nested sets or anything like that.