Solved

category--unlimited sub category levels--self join problem...

Posted on 2002-05-10
8
1,017 Views
Last Modified: 2008-02-26
I have a problem which I think can be solved by SELF
JOIN but I can't figure out how to do it

here is table definition

CREATE TABLE first (
  firstcolumn int(11) default NULL,
  secondcolumn int(11) default NULL
) TYPE=MyISAM;


INSERT INTO first VALUES (0,1);
INSERT INTO first VALUES (0,2);
INSERT INTO first VALUES (0,3);
INSERT INTO first VALUES (2,4);
INSERT INTO first VALUES (2,5);
INSERT INTO first VALUES (2,6);
INSERT INTO first VALUES (5,7);
INSERT INTO first VALUES (5,8);
INSERT INTO first VALUES (5,9);

Now I use this as a table to track unlimited sub
category branches

like taking the above as example 1 , 2 , 3 are MAIN
categories

and the category subcategory tree will be

2-->4, 5, 6

5->7 , 8 , 9

Now I want to delete the following rows using one or
two sql statements

0,2

2,4
2,5
2,6
5,7
5,8
5,9

is it possible ?

I can delete upto the second level using the statement

DELETE from  first where firstcolumn=2 OR
secondcolumn=2

so only the rows

0,2

2,4
2,5
2,6


gets deleted but NOT

5,7
5,8
5,9

 

can you please help me formulate a SQL query which
does that ?

also if the table has a next level of data like

8 , 10

8, 11

8,12

those also must be deleted...

since 10 , 11, 12 are subcategories of 8 , which in
turn is a subcategory of 5 which in turn is a
subcategory of 2 ..and 2 is the main category

so if 2 is deleted all the below TREE must be deleted
too

ok that's it for a DELETE statement

now I want to write a SELECT statement which retrieves
all sub categories , sub sub categories , sub sub sub
categories and so on ...GIVEN a main category ID

so for example based on the above table  I want to
retrieve 4 ,5 ,6 , 7 ,8 ,9 IF GIVEN 2 as the main cat
id

also last but NOT the least ..for managing unlimited
sub category branches is the above database design the
best method ?


Thanks to all


chris

0
Comment
Question by:christopher sagayam
8 Comments
 
LVL 5

Expert Comment

by:kelfink
ID: 7002094
While some databases have special extensions for hierarchical data, such as Oracle, with its CONNECT BY clause, you won't find that here on mySQL.

I recommend you change the table structure a bit, and implement a different design, known as the NESTED SET HIERARCHY.  This is a design discussed by Joe Celko in several usenet postings, and in his SQL FOR SMARTIES book.

If you look at the following thread at Google, (http://groups.google.com/groups?q=celko+nested+set+atomic&hl=en&rnum=1&selm=Oy21PVU6AHA.1380%40tkmsftngp05)
you'll get a good idea of what the design needs.  In really-simple terms, though, the NSH pattern involves tracking child records within the boundary values of parents.  Each record stores one LEFT and one RIGHT boundary integer value, and all records which are children of that record will have LEFT and RIGHT boundary values which fall between those of the parent.

This pattern has slightly higher overhead for maintenance, but querying the tree is easier, and very flexible, plus it works on ANY SQL database, which is a great bonus.

0
 
LVL 2

Expert Comment

by:vasan_sr
ID: 7003109
Hi,
  the same thing we got it in our project and there is no alternative than recursive query.

 Good Luck
  vasanS
0
 
LVL 5

Expert Comment

by:kelfink
ID: 7007176
I disagree.  We have implemented the strategy I outlined above, and it's working great.   Our pure-SQL solution works in Oracle, mySQL, SqlServer, DB2, you name it.
As long as you can perform a self join on a table, Celko's solution works fine.  The only overhead associated it that you'll have two columns to help sort out the hierarchy, and you have to update more records when the hierarchy is modified.
0
 
LVL 6

Author Comment

by:christopher sagayam
ID: 7007384
celko's solution does not work in my case since the TOTAL number of records will NOT be known beforehand ...

and in celko's solution ..the right column of ROOT record will be 1 + 2*number of records..

any suggestions ?


also in a particular situation like this


Name left right
Fred  1    12
Cambel 2 , 3
John   4 , 11
smith   5,7


How do I add another member peter directly below Fred ?


chris




0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 5

Expert Comment

by:kelfink
ID: 7007410
To anser the second part of youe last post,
here's your existing tree (watch me build it)

1:  Add fred.
    Fred
   (1,2)

2: Add John under Fred...
    Fred
    (1,4)
        John



            Fred
           (1, 8)
      Cambel        John
       (2,3)        (4,7)
                     Smith
                     (5,6)
   
here's how you add Peter to the
Cambel and John
0
 
LVL 5

Expert Comment

by:kelfink
ID: 7007411
hold on....  that was too hard to type, and I ended up hitting enter.  I'll get back to this in a few minutes.
0
 
LVL 5

Accepted Solution

by:
kelfink earned 250 total points
ID: 7007454
Ok, here's a rundown of creating the tree you gave.  The numbers I arrive at are different from yours, but I believe they are correct.

1)     Add Fred
Insert Fred with left/right of (1,2).  All root nodes start this way.
Result:
             Fred(1,2)
2)     Add John under Fred
John should have LEFT = (right of john), and always, RIGHT = LEFT + 1.  So the new values are 2,3.  
Make room for this node by updating all values in the existing tree which are 2 or greater, by adding two…
Result:  
Fred(1,4)
     John(2,3)

3)     Add Cambel under Fred:
a.     Cambel should have value 2,3 to be under fred and (supposing it matters) to the left of John.
b.     Update all values 2 or greater,
c.     insert Cambel with 2,3.
Result:
     Fred(1,6)
Cambel(2,3)     John(4,5).

4)     Add Smith under John:
a.     Smith needs to be between John’s 4 and 5.  So update all greater than or equal to 5, by two.
b.     Add new Smith record with values 5,6.
Result:
              Fred(1,8)
    Cambel(2,3)        John(4,7).
                         Smith (5,6)

So, I didn’t need to know the ultimate number of records I’d have in the tree.  It’s dynamic.  It required two sql statements to add a new node…An update (moving nodes out of the way) and the insert to create the new node.

Want to add the new node for Peter, directly below Fred?
Ok.
You didn’t say whether Peter would be on the left of Fred, middle, or right, so I’ll do the most efficient, which is to add him on the right.

5)     Add Peter under Fred (on the right):
a.  The right-hand-most value for Fred is 8 (looking above) so this is the new LEFT value for Peter.  Add 2 to all those values >= 8.
b.  Update all nodes with RGT >= 8 (in this case, just the root node.)

You’ll now have:
         Fred(1,10)
Cambel(2,3)   John(4,7).
                  Smith (5,6)
c.     There’s now room to add the node Peter (8,9) which fits nicely to the right of John.
Result:
              Fred(1,10)
Cambel(2,3)   John(4,7)     Peter(8,9)
             Smith (5,6)

The worst-case scenario adding a record is to add a left child of the left-most node on the tree, which required updating all nodes.  But, this is still accomplished with one SQL UPDATE statement, so it’s not any more complex, just a bigger update.

As for the comment you made about the rootnode having RIGHT = 2*number of nodes, well, that’s just a cool feature, answering the question “how big is my tree?”  To get the answer, divide the RIGHT value of the rootnode by two.  Generally, how many children are under any node (including the node itself)?  == (RGT – LFT + 1)/ 2.  

It’s a good system.  Celko's book and his other articles online explain how to display a tree in one query, how to delete nodes, and other statistics.
0
 
LVL 17

Expert Comment

by:Squeebee
ID: 9803406
chris18,
No comment has been added lately (558 days), so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area for this question:

RECOMMENDATION: Award points to chris18 http:#0

Please leave any comments here within 7 days.

-- Please DO NOT accept this comment as an answer ! --

Thanks,

Squeebee
EE Cleanup Volunteer
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

More Fun with XML and MySQL – Parsing Delimited String with a Single SQL Statement Are you ready for another of my SQL tidbits?  Hopefully so, as in this adventure, I will be covering a topic that comes up a lot which is parsing a comma (or other…
All XML, All the Time; More Fun MySQL Tidbits – Dynamically Generate XML via Stored Procedure in MySQL Extensible Markup Language (XML) and database systems, a marriage we are seeing more and more of.  So the topics of parsing and manipulating XM…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
Access reports are powerful and flexible. Learn how to create a query and then a grouped report using the wizard. Modify the report design after the wizard is done to make it look better. There will be another video to explain how to put the final p…

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now