hey brains

So I'm making this webapp, I can't reveal too many details but I hope I can explain this ok. It allows users to create a list of events on a calendar. But these events are grouped into time blocks, and there are various levels of these:

Whole Plan contains many Phases which contain many Sub Phases which contain many Blocks which contain many Weeks which contain many events.

The Whole Plan to Blocks all must be whole numbers of weeks in length.

So I went the simple way, each item gets its own table, containing:

ID, ParentID (FK to link to the appropriate parent table), Name, Length (in weeks), Order (this is the order within the direct parent, always starts at 1).

So I'm building the scripts that allow the users to start adding data. They create a new Plan and start adding Phases. They pick a Phase and add SubPhases to it, and so on down to the weeks where they can add the actual events on the 7 days.

That's ok - but it turns out that it's a real pig to read data out again.

For instance, when showing a list of Weeks for a given Block I need to number them on the screen according to their position in the whole plan, not just in their direct parent. So using that grid above, imagine I'm showing the weeks in Block 5, I'd list 23, 24, 25, 26, 27 and 28, not just 1, 2, 3, 4, 5, 6.

And I also need to show the start date for any given item, weeks, blocks, phases etc. The start date of the whole plan is stored there - and you can work it out from there by adding the weeks up of any preceding items.

I'm toying with the idea of recording this info in each table, and maintaining it when I do updates - since the users will be able to change the length of items, which will affect the start dates and week numbers of everything that comes after. But I hate that idea.

I dunno, I just wondered if maybe someone knows of some cunning way of setting up the tables so it's quick to get out the info I need, but also easy to maintain?

If you read this far, thanks for your time!

toying with the idea of linking the Weeks directly to the parent Plan. Guess I need to practice my database design analysis cos I find it really hard to see where problems might lie.

perhaps I could flatten it all so that all the tables: Week, Block, SubPhase and Phase all link directly to the Plan, instead of being hierarchic.

Even though there's no direct link from a Week to its parent Block any more, it should be easy to work out what the parent Block is by adding up the weeks of the preceding Blocks until I get to the Block that contains that week.

gonna go try out some SQL ...

RDBMSs just don't do very well at storing hierarchies. However, on a previous project we made a lot of use of Nested Set Trees (sometimes called Modified Preorder Tree Traversal) to store tree-like data. Once you get your head around the concept, certain otherwise complex types of analysis become really simple.

thanks Stickman, that's an interesting approach.

In your exp, is it easy enough to work out the next sibling on the same level using this method?

e.g.

I'm at "Yellow" - I want to know what the node to the right is. The correct answer is "Beef" - but how can you work that out?

IIRC you'd have to add a depth field to do this - just look for the row with the same depth and the next highest left value.

Originally posted by: DontBogartMe perhaps I could flatten it all so that all the tables: Week, Block, SubPhase and Phase all link directly to the Plan, instead of being hierarchic.

Even though there's no direct link from a Week to its parent Block any more, it should be easy to work out what the parent Block is by adding up the weeks of the preceding Blocks until I get to the Block that contains that week.

gonna go try out some SQL ...

well here's the SQL to find out the parent block for a given week number (here looking for 20):

SELECT blocks.id, blocks.week_to_find, blocks.length, blocks.order, weeks_before FROM (

SELECT b.id, 20 AS week_to_find, b.length, b.order, IFNULL( ( SELECT SUM( b1.length ) FROM block b1 WHERE b1.plan_id =1 AND b1.order < b.order ) , 0) AS weeks_before FROM block b WHERE plan_id =1 ORDER BY b.order DESC ) blocks WHERE ( weeks_before < week_to_find AND weeks_before + blocks.length >= week_to_find ) ORDER BY blocks.order DESC

Working on this table:

It's hard coded looking in the plan ID 1 here.

It comes back with either a single row or an empty set if the week is beyond the bounds of the existing blocks. This is the result of the above SQL:

We're looking for week 20 and since my blocks add up to 20 weeks defined, it comes back with Block 5 (starts on week 16 and is 5 weeks long).

Guess you couldn't really call that "easy" There's probably a neater way to do it, but this works ok, and could be used to find any ancestor of a week, by changing the table it works on. Getting siblings should be a doddle though, as is working out the week number and the start date (get the start date from the plan, then just add the number of weeks).

Inserting a new week (or deleting one) will involve changing the lengths of the ancestors, and then updating the orders for all subsequent siblings. That should be easy enough too.

I'll make up a list of operations I need to do.

// edit to show query results

Originally posted by: Stickman IIRC you'd have to add a depth field to do this - just look for the row with the same depth and the next highest left value.

hmm yeah I see that. Got some thinking to do then... thanks for the ideas Stick.

NST isn't a perfect solution (for one thing, you have to rebuild the tree every time you change it -- although using intervals can mitigate this somewhat) but it does make operations like finding ancestors and descendants very easy. So for example:

Find ancestors:

SELECT * FROM myTable where left < 5 and right > 6

where the the left and right values are those of the entry whose ancestors you want to find. That will get you a list of all ancestors, but combine it with depth and you can find a particular ancestor (e.g. parent would be this row's depth -1).

And similarly, find descendants:

SELECT * FROM myTable where left > 1 and right < 10

what did you mean by "using intervals"?

Since the depths are limited here to just Plan, Phase, SubPhase, Block and Week - just 5 levels - I think I'll just flatten the whole thing and have each item link both to its parent and also to the whole Plan. Each can also keep a record of its Start Date to avoid having to calculate that on reads. That can be updated during writes when speed isn't so important. That way it will be easy to fetch parents and children, and also siblings, plus know the order of each item both in terms of its direct parent, and also in terms of within all its siblings on the same level.

Speed isn't a vital consideration here, the trees won't be very complicated and there will be a very limited number of users.

Originally posted by: DontBogartMe what did you mean by "using intervals"?

In the above diagram, the left/right numbers increment by one. Make the increment larger -- e.g. 10 -- and you can insert new entries without (necessarily) having to re-index the entire structure. It's not ideal -- eventually you will reach a point where you have to re-index, but you could do this regularly offline to avoid delays during insertion.

Anyway, sounds like you have a plan. :thumbsup:

thanks - it's always good to talk things thru here

Originally posted by: DontBogartMe Since the depths are limited here to just Plan, Phase, SubPhase, Block and Week - just 5 levels - I think I'll just flatten the whole thing and have each item link both to its parent and also to the whole Plan. Each can also keep a record of its Start Date to avoid having to calculate that on reads. That can be updated during writes when speed isn't so important. That way it will be easy to fetch parents and children, and also siblings, plus know the order of each item both in terms of its direct parent, and also in terms of within all its siblings on the same level.

ha... it sounded so easy when I wrote that.

I haven't tried an NST... but I'm really thinking it must be easier than this nightmare.

Yeah, once the data's set up retrieval and traversal is pretty easy - but it's maintaining the data that's the real bugger.

I'm just moaning... nothing to share other than that warning to anyone that might stumble in here.