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 = Paths.descendantID
    WHERE P.ancestorID = <pID>;

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

    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 = 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.




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


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

FROM tbl t1
JOIN tbl t2 ON t2.leftedge > t1.leftedge AND t2.leftedge < t1.rightedge



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

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

		Depends on the model you are using--edge list or nested sets?
		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,

		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


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