checking value in n-depth tree?

Question

I have two entities, post and category which is a 1:n relationship.

I have a reference table with two columns, post_id,category_id

The categories table has an id column, a status column and a parent_id column

If a category is a child of another category (n-depth) then it's parent_id is not null.

If a category is online it's status is 1, otherwise it is 0.

What I need to do is find out if a post is visible.

This requires:

Foreach category joined to the post trace up it's tree to the root node (till a category has parent_id == null), if any of those categories have status 0 then that path is considered offline.

If any path is online then the post is considered visible, otherwise it is hidden.

The only way I can think of doing this (as semi-pseudo code) is:

function visible(category_ids){
  categories = //select * from categories where id in(category_ids)
  online = false
  foreach(categories as category){
    if(category.status == 0)
      continue;

    children = //select id from categories where parent_id = category.id
    if(children)
      online = visible(children)
  }
  return online
}

categories = //select c.id from categories c join posts_categories pc on pc.category_id = c.id where pc.post_id = post.id

post.online = visible(categories)

But that could end up being a lot of sql queries, is there a better way?

the better way is called *nested set*. you can also have this pre-ordered which allows you to solve the output with one query. See [Getting nested set model into a
but hiding “closed” subtrees](http://stackoverflow.com/q/7729173/367456). — hakre, Oct 06 '12 at 10:20
Nested sets cannot be used here as the data will often be added to/removed from in the middle of trees — Hailwood, Oct 06 '12 at 10:22
are you adding and removing more often than displaying? and how large is that list? — hakre, Oct 06 '12 at 10:25
Well, it's a blog, so semi-regular updates. it's actually a generic module for a cms, so I can't give a clearer answer than that. — Hailwood, Oct 06 '12 at 10:32
well let's just say a nested set is not an option because you do not want to change the data-structure. actually I'd say the nested set model is very good for that and you might want to rethink this in the future. anyway, part of the optimization done in that linked answer works with a sorted data-set of your structure, too. But you still need to solve the sorting. I added this as an answer. — hakre, Oct 06 '12 at 10:36

score 0 · Answer 1 · answered Oct 06 '12 at 10:21

0

A classic database vs memory tradeoff. What you are doing is building a tree with leafs in it. To build the tree you need recursive loop the leafs. Coming from a database there are 2 scenarios:

Build the tree recursive with a query for each leaf. You hold 1 tree in memory. That is what you are doing.
Get a flat structure from the database, and build the tree recursive in memory. You hold a flat tree and the real tree in memory. That is your alternative way.

What is better depends on a lot of things: your hardware (disk access vs memory), the size of the tree to name two.

answered Oct 06 '12 at 10:21

JvdBerg

21,777
8
38
55

We are looking at an average of 5 categories per post, with each branch being about a depth of 5. with in total about 50 categories, but if we build a flat tree, wouldn't we have to walk the tree backwards? how would we do that? – Hailwood Oct 06 '12 at 10:28
@Hailwood: Depends. Is the order already sorted (children follow their parent) or not? – hakre Oct 06 '12 at 10:40
Not sorted, they are sorted by id, so in order of creation – Hailwood Oct 06 '12 at 11:05

score 0 · Accepted Answer · edited May 23 '17 at 12:04

If nested sets are not an option, I know about the following:

If the data is ordered so that children of a parent always follow after it's parent, you can solve this with one database-query over all data by skipping hidden nodes in the output.

This works equally with a sorted nested set, too, the principle has been outlined in this answer however the algorithms about getting the depth do not work and I would suggest a recursive iterator that is able to remove hidden items.

Also if the data is not ordered, you can create a tree structure from the (unsorted) query of all rows like outlined in the answer to Nested array. Third level is disappearing. No recursion needed and you get a structure you can easily output then, I should have covered that for <ul>/<li> html style output in another answer, too.

checking value in n-depth tree?

2 Answers2

Linked