• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursive taxonomy  RSS feed

 
Hawken
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey, I'm writing an algorithm that reads from a single table of "Categories", which has a recursive relationship to identify sub-categories, and need to print out the results, showing a more readable format, or a "flattened" view, kind of like in java editors where you can flatten your package view.

Table:
Category
--------
id
name
parent_id

Sample data:
1, industry, null
2, business, 1
3, software, 2
4, realestate, 3
5, marketing, 3
6, finance, 3

Desired output:
industry
industry.business
industry.business.software
industry.business.software.realestate
industry.business.software.marketing
industry.business.software.finance

Was wondering what might be the fastest approach to accomplish this, or if anyone has already done something like this, what you used? Any code appreciated.

Thanks!
[ February 02, 2006: Message edited by: Hawken ]
 
fred rosenberger
lowercase baba
Bartender
Posts: 12529
48
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hawken,

I'm sure somebody will be along shortly to help you, but in the meanwhile, i have to inform you your name does not meet our naming policy. Please read it, then follow the link to edit your profile.

thanks!!!
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My suspicion is that, if the number of entries is sufficiently small that you can produce a readable print-out, then you don't need the fastest algorithm. You need a reasonably-fast, simple, maintainable algorithm.

Perhaps make a SortedMap where the keys are the integer line numbers. The values would be of a class you'd define, containing the String name and the integer parent number.

To make your print-out, get the values() of the SortedMap. Each entry would be printed out by recursively looking up and printing the parents, then printing the name.

I'm sure that's not the fastest approach, but it's not bad and should be maintainable.
 
Jeff Albertson
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here, "fastest" probably translates to fewest database calls. I'm not a database guy (we employ database guys to be database guys ) but you should check the details of your particulat DBMS. I remember that Oracle, for example, has specific extensions to SQL to just this sort of thing. Our database guy showed me this once, but I immediately killed those brain cells with beer.

Of course, before you go performance crazy, see if the simplest thing is good enough
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I could imagine for a few records (less than 10 000*), which are accessed often and updated seldom, it could be fast to fetch all records, store them in a tree, and query the tree in memory.
If the rows aren't updated, but only new values inserted, you could update the tree with ".... WHERE rownum > lastMaximum " to be allways up to date.

*) a more serious value would depend on a lot of concrete information, like machine running the program, available memory, database connection and performance and vendor, ...
[ February 03, 2006: Message edited by: Stefan Wagner ]
 
Paul Clapham
Sheriff
Posts: 22378
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And if the children always appear after their parents in the input, as in the example, then it's very easy to build that tree. But if they don't, then it is rather difficult to build the tree. I couldn't figure out any SQL that guaranteed that records with parent_id = n would always appear after the record with id = n, so I had to write an algorithm that stored entries in a holding area until their parents showed up. (In my case the algorithm was complicated by the fact that not all leaf nodes were actually put into the tree, but if one was put into the tree then all of its parents had to be put into it as well, and you couldn't end up with leafless parent nodes.) So the performance would depend on the order of the input data.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!