List:General Discussion« Previous MessageNext Message »
From:Robert DiFalco Date:September 27 2006 4:17pm
Subject:RE: AW: Count of children
View as plain text  
For us the querying of trees is more important than the speed of writing them. So each
time we add a child or change a parent or whatever, we trigger a stored procedure that
updates a paths table. Then our query for children is pretty simple:
 
    SELECT Node.*
    FROM Node 
        JOIN Paths P ON Node.id = Paths.descendantID
    WHERE P.ancestorID = <pID>;

So to perform a count I can just do this part without the join:

    SELECT COUNT(*)
    FROM Paths
    WHERE Paths.ancestorID = <pID>;

Our system is structured using a sort of GoF composite parent so some nodes can be Groups
and others can only be leaves. If I want to return children nodes that are not leaves I
can do this:

    SELECT Node.*
    FROM Node 
        JOIN Paths P ON Node.id = Paths.childID
    WHERE P.ancestorID = <pID> AND Node.isLeaf = false;

The Paths table is pretty simple; just "descendantID" and "ancestorID" columns that make
up a composite primary key. Some people also add another column called "depth" as this
can make recalculating the tree easier.

R.

         

________________________________

From: Peter Brawley [mailto:peter.brawley@stripped] 
Sent: Wednesday, September 27, 2006 8:20 AM
To: André Hänsel
Cc: mysql@stripped
Subject: Re: AW: Count of children


André 

With an edge list, the solution entails recursion, so you need either an sproc or
application proc. With a nested sets model, the count is dead simple. If the id of the
target row is N, and the left & right node columns are named leftedge and rightedge,
the query is

SELECT COUNT(t2.id)
FROM tbl t1
JOIN tbl t2 ON t2.leftedge > t1.leftedge AND t2.leftedge < t1.rightedge
WHERE t1.id=N;

PB

-----

André Hänsel wrote: 

	I will use any model that is suitable. ;)
	
	I am somewhat familiar with both tree models but I can't come up with a
	method to get the count of all sub- and sub-sub-nodes in either of them.
	
	  

		-----Ursprüngliche Nachricht-----
		Von: Peter Brawley [mailto:peter.brawley@stripped] 
		Gesendet: Mittwoch, 27. September 2006 16:49
		An: André Hänsel
		Cc: mysql@stripped
		Betreff: Re: Count of children
		
		André,
		
		    

			I want the count of all sub-entries for a specific entry.
			      

		Depends on the model you are using--edge list or nested sets?
		
		PB
		
		-----
		
		André Hänsel wrote:
		    

			I have a table with id and parent_id.
			I want the count of all sub-entries for a specific entry.
			
			I found several documents about working with graphs/trees 
			      

		in MySQL but I
		    

			could not find a solution for my problem.
			
			I can imagine two possibilities, but one is memory 
			      

		intensive and the other
		    

			one creates load on updates.
			The first is, that I select all entries and then use a 
			      

		procedural language
		    

			to determine recursively whether an node is a sub-node of 
			      

		the specific node.
		    

			The second is, that I store the sub-node count with each 
			      

		node and when I do
		    

			an insert, I walk the tree upwards and increment the node-counts.
			
			Is there a smart solution/best practice for my problem?
			
			Now I can't think of another sentence starting with an i. ;-)
			
			Best regards,
			André
			
			
			  
			      

		-- 
		No virus found in this outgoing message.
		Checked by AVG Free Edition.
		Version: 7.1.407 / Virus Database: 268.12.9/457 - Release 
		Date: 9/26/2006
		
		    

	
	
	
	  


Thread
Count of childrenAndré Hänsel27 Sep
  • Re: Count of childrenjoao27 Sep
  • re: Count of childrenRob Desbois27 Sep
    • AW: Count of childrenAndré Hänsel27 Sep
    • Re: Count of childrenjoao27 Sep
      • Re: Count of childrenDouglas Sims27 Sep
  • Re: Count of childrenPeter Brawley27 Sep
    • AW: Count of childrenAndré Hänsel27 Sep
      • Re: AW: Count of childrenddevaudreuil27 Sep
      • Re: AW: Count of childrenPeter Brawley27 Sep
        • RE: AW: Count of childrenRobert DiFalco27 Sep