recursion?

[Anon]

Hi guys, I'm having a spot of bother working out how to delete a 'folder' in a tree database.

Problem is that I need to delete all 'sub-folders' and their contents and I just can't see how to do it if I dan't know how many (if any) sub-folders a folder may have?

Here's how the database is set up

Bookmarks DB

urls
id|name|location|desc

catagories
cat_id|parent|name

cat_link
id|url_id|cat_id

Hope someone can point me in the right direction.

Nick

[Anon]

You aren't going to like the answer. :-( It's not messy or anything, but it does involve lots of queries--that is, unless your dbms supports real foreign keys, in which case ON DELETE CASCADE may take care of the problem with no further ado (not sure since it's a self-join here, or so it appears.)

To delete a subtree:
  Delete the parent node BUT REMEMBER THE ID!
  For each child node (i.e. having the deleted node as parent)
    Delete the subtree rooted at this child node

[Anon]

Yep, reckon that'w what I'm trying . Heres the code at the time of reply, let me know if you see any silly mistakes

function delete_catagory($cat_id) {

/* First get sub-folders */
$sub_cats_qry="SELECT cat_id FROM bookmarks_catagories ";
$sub_cats_qry.="WHERE  parent_cat_id = $cat_id";
if(!($con=$this->_db_connect())) {
    return FALSE;
}
if(!($result=mysql_query($sub_cats_qry))) {
    return FALSE;
}
while($subcats=mysql_fetch_row($result)) {
    $subs_cat_ids[]=$subcats[0]; // add id to subs array
}

/* Okay, lets see if there are sub-folders */
if($sub_cats_ids) {
    foreach($sub_cat_ids as $sub_catagory) {
        $this->delete_catagory($sub_catagory)    // Get recursive!
        $del_sub_qry="

Still on the case as you can see. Thaks Kirk.

Nick

[Anon]

Umm, I see a SELECT query but no DELETE query. Where is it you actually delete something?

In case I forgot to mention (yup, I did forget!) the order specified in my pseudocode is important. You want to delete from the top down, as this makes it less likely that someone will be able to add a child after you've deleted that level.

[Anon]

Thanks Kirk, there's no DELETE as I have'nt witten it yet. I just wanted you to see how far I'd got before I carried on.

I reckon i'ts probably not as hard as it seems. I think attention to detail is the key.

This tree is intended for one user but the reason that I'm writing a class to handle the the basic functions is that I'd like to re-use/adapt on other projects so your comment about order is of serious interest.

Could you expand/simplify that? I'm not sure of what you mean by 'top'. Is that the ultimate child or the ultimate parent?

Much thanks

Nick

[Anon]

'top' of the subtree means the parent of that subtree. Making it go away first means that there is a shorter time window where someone might find the parent and try to add a new child of it.

[Anon]

That makes sense. Cheers kirk, catch you later.'

Nick

[smarlowe]

I would really suggest you use a transactional database to ensure integrity here. This is one of those times that it gets important to have something that either all happens or none does to keep the data in a clean state.

If you have foreign keys setup across the three tables, then so much the better. That should stop the inserting a leaf on a parent that's about to be deleted since the parent being locked for write should result in no insertion?

Well, as long as the new leafs were inserted transactionally as well, that should work.

:-)

To understand recursion, one must first understand recursion.

[Anon]

What if I can't use transactions?
Just live with it I suppoce?

Nick

[smarlowe]

But I wouldn't.

Does your database have the ability to create constraints on it's data that would prevent the insertion of a leaf to a folder that is being deleted and is currently locked? It seems even simple row level locking should be able to do that. Just lock all the rows in the join table that have the id of the folder you're about to delete.

Or, maybe a foreign key / constraint could guarantee that you can't have a parent without a child (i.e. no NULLS allowed).

Does your dbms do either of those things? The first one seems a bit of work, and could get ugly if you've got recursive data and are deleting a huge giant structure. The locks could take quite a while to go on and come back off, and you might have to worry about someone who is currently adding something to a child sticking it right back in before the locks go in place, or it doesn't get noticed, and suddenly there are the few odd extra rows here and there.

So, I'd vote for the constraint.

[knickerlas]

I'm not sure actually Scott. I'll look into it.
I'm using MySQL for this task (indeed I've not ever used a different D😎

Cheers

Nick

[smarlowe]

I'm pretty sure MySQL supports unique key indexes across multiple tables.

[knickerlas]

Hmm, I'll check out.
Cheers Scott.