[Lazy Vulpes]

Hi, I've been trying for some time now to display a nested set in a particular way, but I haven't been able to achieve my goals so far. I'd greatly appreciate if someone could lend a hand with my code.

This is my database

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

The result I would like to achieve should look like this

ELECTRONICS
 TELEVISIONS
  TUBE
  TUBE
  LCD
  LCD
  PLASMA
  PLASMA
 TELEVISIONS
 PORTABLE ELECTRONICS
  MP3 PLAYERS
   FLASH
   FLASH
  MP3 PLAYERS
  CD PLAYERS
  CD PLAYERS
  2 WAY RADIOS
  2 WAY RADIOS
 PORTABLE ELECTRONICS
ELECTRONICS

(the indent is only for readability in this post)

This is the code I have so far

$sql_result = mysql_query("SELECT node.lft, node.rgt, node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;");

while($row = mysql_fetch_array($sql_result))
  {
	$tag[] = $row['name'];
	$depth[] = $row['depth'];
  }
echo($tag[0]."</br>");
$child_count=0;
for ($i=1; $i<=count($tag)-1; $i++)
{
	echo($tag[$i] . "</br>");
	if($depth[$i+1]<=$depth[$i])
	{
		$child_count+=1;
		echo($tag[$i]. "</br>");
	}
	else
	{
		$child_count=0;
	}

	if($depth[$i+1]<$depth[$i])
	{
		echo($tag[$i-$child_count]. "</br>");
                          // ^This is where things start to go wrong I think..
	}
}
echo($tag[0]."</br>");

With this approach, I believe it is how I handle child_count that is flawed, and that it is because I don't account for the child within the child of the parent. (FLASH)

A thousand thanks to anyone who can help me with this!

[e_i_pi]

I haven't got a solution per se, but have you looked into using something other than MySQL? I moved from MySQL to PostgreSQL, with one of the strong reasons being that MySQL doesn't support CTE's (Common Table Expressions). With CTE's, you can create proper hierarchical data without having to resort to the (arguably) esoteric workaround of "left / right" for sorting. You also get the benefit of being able to reparent easily, not being forced to recalculate the left/right values across the entire tree, and with a couple of views you can query the structure extremely easily and efficiently.

I wrote a tutorial on hierarchical data storage, view creation and querying, located here if you're interested.

[Lazy Vulpes]

Yes, I have been looking for something other than MySQL, but with only a superficial knowledge of databases I chose MySQL for all the reason you've probably heard a thousand times before, from small time developers like myself. I chose the nested set model 'cause it suited my needs the best, when using MySQL, not because I thought it was a good solution, as it (as you pointed out) have it's drawbacks.

PostgreSQL looks very promising and since it says you're a expert in databases I will trust your decision in moving from MySQL to PostgreSQL and do the same. (or at least do the effort of trying)

Thanks for your input e_i_pi, I appreciate it.

So for now, to any other who might reads this, please refer from spending time on finding a solution, I will post back whether or not I think a MySQL solution to my problem is the right thing.

This post has been edited by Lazy Vulpes: 03 July 2012 - 05:57 PM

[Dormilich]

I’m with e_i_pi here. AFAIK, MySQL does not support hierarchical output data.

[Lazy Vulpes]

Okay, I've played a little around with postgres, but I still don't get why this have brought me any closer to my goal.

I've followed i_e_pi's example and created a table like this.

+----+-----+----------------------+
| ID | pID | name                 |
+----+-----+----------------------+
| 1  | NULL| ELECTRONICS          |
| 2  |  1  | TELEVISIONS          |
| 3  |  2  | TUBE                 |
| 4  |  2  | LCD                  |
| 5  |  2  | PLASMA               |
| 6  |  1  | PORTABLE ELECTRONICS |
| 7  |  6  | MP3 PLAYERS          |
| 8  |  7  | FLASH                |
| 9  |  6  | CD PLAYERS           |
| 10 |  6  | 2 WAY RADIOS         |
+----+-----+----------------------+

(This is btw how I originally wanted my table to be like, but read that it was better with the nested sets model when doing a lot of retrieving.)

But now I'm really just more stuck than before.. Do I need to create a view that displayed the data as indicated in my original thread and then simply use SELECT * on it?

This post has been edited by Lazy Vulpes: 04 July 2012 - 03:21 PM

[e_i_pi]

I'm at work at the moment, so I haven't got my PHP/Postgres kit in front of me, but I imagine you would need this query to create the view:

CREATE VIEW "LocationTreeView"
AS
WITH "LocationTree"(
	"pID",
	"ID",
	"Depth",
	"name",
	"SortKey",
	"Indent"
) AS (
	-- Start with all the root node Locations
	SELECT
		"pID",
		"ID",
		0 AS "Depth",
		"name",
		"name" AS "SortKey",
		'' AS "Indent"
	FROM "Locations"
	WHERE "pID" IS NULL
	UNION ALL
	-- then recursively add the children
	SELECT
		"Children"."pID",
		"Children"."ID",
		"Parents"."Depth" + 1,
		"Children"."name",
		trim(both ' ' from "Parents"."SortKey") + '|' + "Children"."name") AS "SortKey", 
		"Parents"."Indent" + '  ' AS "Indent"
	FROM "Locations" AS "Children"
	INNER JOIN "LocationTree" AS "Parents" ON "Children"."pID" = "Parents"."ID"
)

SELECT
	"pID",
	"ID",
	"Depth",
	"name",
	"Indent" + "name" AS "IndentedName",
	"SortKey"
FROM "LocationTree"
ORDER BY "SortKey"

Mind you, the syntax could be off (I have nothing to test it against). I'll give it a go when I get home, as I have some nexus data at home waiting for a view to be created on it. It's 9am now, I get home around 6pm.

Once that view is created, to get the data in a format you described in your original post, you need to make a pseudo-sort-key for the "closing" elements, UNION the queries, then order by the sort key, like this:

SELECT
	"IndentedName",
	"SortKey"
FROM "LocationTreeView"


UNION

SELECT
	"IndentedName",
	"SortKey" + '~' AS "SortKey"
FROM "LocationTreeView"

ORDER BY "SortKey"

This post has been edited by e_i_pi: 04 July 2012 - 03:52 PM

[Lazy Vulpes]

Thanks e_i_pi, don't sweat it. Unfortunately I don't understand any of it, SQL is definitely not one of my strong sides..

[Lazy Vulpes]

I was hoping that, you (or someone else for that matter) would walk me through the logical process you're doing, in English. I have a strong logic, I just don't have the required skill set to visualize your code and put it into perspective.

In the mean time, I will do what I can do improve my SQL skills..

This post has been edited by Lazy Vulpes: 05 July 2012 - 09:44 AM

[e_i_pi]

Oh right, sure I think I've explained a lot in the tutorial, but I'll step you through the CTE query that creates the view. I also have the syntax correct now (have tried it on my system), so here is the complete query that should work with your data:

WITH RECURSIVE "CategoryTree"(
	"pID",
	"ID",
	"Depth",
	"Name",
	"SortKey",
	"Indent"
) AS (
	-- Start with all the root node Locations
	SELECT
		"pID",
		"ID",
		0 AS "Depth",
		"name" AS "Name",
		trim(both ' ' from "name") AS "SortKey",
		'' AS "Indent"
	FROM "Categories"
	WHERE "pID" IS NULL
	UNION ALL
	-- then recursively add the children
	SELECT
		"Children"."pID",
		"Children"."ID",
		"Parents"."Depth" + 1,
		trim(both ' ' from "Parents"."SortKey") || '|' || trim(both ' ' from "Children"."name") AS "SortKey", 
		"Parents"."Indent" || '  ' AS "Indent"
	FROM "Categories" AS "Children"
	INNER JOIN "CategoryTree" AS "Parents" ON "Children"."pID" = "Parents"."ID"
)

SELECT
	"pID",
	"ID",
	"Depth",
	"Name",
	"Indent" || "Name" AS "IndentedName",
	"SortKey"
FROM "CategoryTree"
ORDER BY "SortKey"

That looks like a lot of SQL, but it can be broken into parts:
DEFINING THE RECURSIVE TABLE

WITH RECURSIVE "CategoryTree"(
	"pID",
	"ID",
	"Depth",
	"Name",
	"SortKey",
	"Indent"
) AS (

This part of the statement declares a common table expression (CTE) that we are naming "CategoryTree", and giving 6 columns - "pID", "ID", "Depth", "Name", "SortKey", "Indent". A common table expression is a method of writing sub-queries that can reference themselves. In other words, it is the means by which we achieve hierarchical querying. You can read about it here.

CREATING THE ROOT NODE(S)

-- Start with all the root node Locations
SELECT
	"pID",
	"ID",
	0 AS "Depth",
	"name" AS "Name",
	trim(both ' ' from "name") AS "SortKey",
	'' AS "Indent"
FROM "Categories"
WHERE "pID" IS NULL

This is where we select the "root" node(s) of the tree. In order to build a hierarchy, we need to start somewhere. In this case, we are defining the root nodes as those categories that have a pID of NULL. In your data above, that should mean the root node(s) is the set {"ELECTRONICS"}. Just one root node in other words. That's fine, we only need one.

BUILDING THE REMAINDER OF THE TREE

UNION ALL
-- then recursively add the children
SELECT
	"Children"."pID",
	"Children"."ID",
	"Parents"."Depth" + 1,
	trim(both ' ' from "Parents"."SortKey") || '|' || trim(both ' ' from "Children"."name") AS "SortKey", 
	"Parents"."Indent" || '  ' AS "Indent"
FROM "Categories" AS "Children"
INNER JOIN "CategoryTree" AS "Parents" ON "Children"."pID" = "Parents"."ID"

This is where it gets tricky, so I'll explain as best I can.

First up, we have a UNION ALL statement - that statement means that we are combining the results of the "root node" part of the query with whatever is to come. The difference between UNION ALL and UNION is that UNION ALL will distinctly combine the results. So, {1, 2} UNION {2, 3} = {1, 2, 2, 3}. But, {1, 2} UNION ALL {2, 3} = {1, 2, 3}. This comes in handy with the next part.

Next, we are selecting all of the immediate children of the current members of the set. BUT, because we have used WITH RECURSIVE up the top of the query, the immediate children of those children will be selected next, and then the immediate children of those children, and so on and so forth. Also, since we have used UNION ALL, that means that any children that were selected in any previous iterations will be combined with the result, therefore no duplicates will be created. So, let's look at this in a real world context using your data:
Step 1
The only member of the set is {"ELECTRONICS"}. So we need to add all of it's immediate children, in other words, the set {"TELEVISIONS", "PORTABLE ELECTRONICS"}.
Step 2
The set is now {"ELECTRONICS, "TELEVISIONS", "PORTABLE ELECTRONICS"}. Since we are using UNION ALL though, and we have already found the children of {"ELECTRONICS"}, the query only finds the children of {"TELEVISIONS", "PORTABLE ELECTRONICS"}. These children are {"TUBE", "LCD", "PLASMA", "MP3 PLAYERS", "CD PLAYERS", "2 WAY RADIOS"}.
Step 3
For the same reasoning as last step, we don't find the children of {"TELEVISIONS", "PORTABLE ELECTRONICS"}, we only find the children of {"TUBE", "LCD", "PLASMA", "MP3 PLAYERS", "CD PLAYERS", "2 WAY RADIOS"}, which is the miserly set of {"FLASH"}.
Step 4
Since the only additional child from last iteration was {"FLASH"}, and that has no children, the WITH RECURSIVE stops looking. The common table expression has been built.

Some pointers on the query string itself:

• We start with a depth of zero, and incremenet it each iteration by adding 1 to the parent's depth.
  
• We use trim on the sort key so that we can remove leading and trailing spaces from the name of the category. This will ensure all categories sort correctly.
  
• We name the CategoryTree as "Parents" and the Categories table as "Children" so as not to confuse the two. Because we have used an INNER JOIN, we can get to step 4, where there will be no more results, which will stop the recursion.

SELECTING YOUR RESULTS
Now that we have built the CTE, all we need to do is SELECT against it:

SELECT
	"IndentedName",
	"SortKey"
FROM "LocationTreeView"
UNION
SELECT
	"IndentedName",
	"SortKey" || '~' AS "SortKey"
FROM "LocationTreeView"

ORDER BY "SortKey"

What I'm doing here is selecting the indented names and sort keys of the results, then selecting them again, but this time with a tilde character (~) appended to the end. Why? Because the tilde character comes after all alpha-numeric characters in the ASCII table, so when it comes to sorting, the sort keys turn out like this:

A
A|B
A|B|F
A|B|F~
A|B~
A|C
A|C~
A|G
A|G~
A~
D
D|E
D|E~
D~

...which will result in an indented view like this:

A
  B
    F
    F
  B
  C
  C
  G
  G
A
D
  E
  E
D

Which is what you were after in the first place

This post has been edited by e_i_pi: 05 July 2012 - 02:16 PM
Reason for edit:: Fixing errors

[Lazy Vulpes]

Thank you e_i_pi! You're the best!

I get errors when I run it though..

ERROR:  each UNION query must have the same number of columns
LINE 22:   "Children"."pID",
           ^

********** Error **********

ERROR: each UNION query must have the same number of columns
SQL state: 42601
Character: 358

[Lazy Vulpes]

If I add "Children"."name", under "Parents"."Depth" + 1, it fixes the error..

But the complete code and the pieces doesn't matches up, which confuses me, also when I try to run it in my php file something goes wrong. (I cannot tell what 'cause no errors show up) And for some reason it seems that my sql is executed in lower case..

[Lazy Vulpes]

I'm really sorry for all the posting..

I think I'm getting the right result now. This is what I'm doing

WITH RECURSIVE "CategoryTree"(
	"pID",
	"ID",
	"Depth",
	"Name",
	"SortKey",
	"Indent"
) AS (
	-- Start with all the root node Locations
	SELECT
		"pID",
		"ID",
		0 AS "Depth",
		"name" AS "Name",
		trim(both ' ' from "name") AS "SortKey",
		'' AS "Indent"
	FROM "categories"
	WHERE "pID" IS NULL
	UNION ALL
	-- then recursively add the children
	SELECT
		"Children"."pID",
		"Children"."ID",
		"Parents"."Depth" + 1,
		"Children"."name",
		trim(both ' ' from "Parents"."SortKey") || '|' || trim(both ' ' from "Children"."name") AS "SortKey", 
		"Parents"."Indent" || '  ' AS "Indent"
	FROM "categories" AS "Children"
	INNER JOIN "CategoryTree" AS "Parents" ON "Children"."pID" = "Parents"."ID"
)

SELECT

	"Name",
	"SortKey"

FROM "CategoryTree"

UNION
SELECT

	"Name",
	"SortKey" || "z" AS "SortKey"
FROM "CategoryTree"
ORDER BY "SortKey"

As you can see I've used "z" as the character to get the right sorting. I would rather use a character that isn't a letter but I have no clue what is picked in what order. ~ didn't work..

Also, I still can't get this to work in my php file. I'm guessing it's 'cause the string is executed in lower case, which I have no idea why.

[Lazy Vulpes]

Okay, I'm a idiot.. I just needed to escape the ' signs..

Thanks for all you've done e_i_pi! I'm still not getting it 100% but I'll keep working with this, and again thanks a lot!

[e_i_pi]

Good to see you got it working. With the SELECT though, it would be better to do this:

SELECT

	"Name",
	"SortKey"

FROM "CategoryTree"

UNION
SELECT

	"Name",
	"SortKey" || 'z' AS "SortKey"
FROM "CategoryTree"
ORDER BY "SortKey"

Notice the single quotes around the z character? Single qoutes are for strings, double quotes are for table/column names. So you're trying to concatenate the column z, not the string z. That may be why the tilde character was not working for you.

[Lazy Vulpes]

I've actually already changed it, it didn't made any difference though..