Adjacency Tree ist eine Hirarchische Baumstruktur.

Das übliche Problem. Wir haben eine Baumstruktur mit beliebig tiefer Verästelung. Nun brauchen wir für eine ID alle ID's des Astes bis hin zur Haubt-ID (Hauptkategorie oder was auch immer)

12.03.2014: Dank Dirks Kommentar habe ich erkannt, dass die bisherige Lösung Fehlerbehaftet ist.
Hier jetzt die neue Version, inkl. Sortierung

Dank slimox aus dem Tutorial-Forum habe ich jetzt auch eine Ahnung wie diese Variante des Baums heisst: Adjacency Tree—Nachzulesen bei mysql.com
Auf eine Anfrage hin, habe ich das ganze noch um die Spalte title ergänzt.

Folgende Tabelle habe ich mal für die Testdaten

Das ergibt dann einen Baum der so aussieht. Die innerhalb eines Level geht nach sort und anschliessen nach title (für die Einträge
sort IS NULL)

Hier habe ich eine zusammenfassung. Das ganze ausführlich und mit Erklärung: Adjacency Tree: Einfache Pfad-Liste für eine id oder als Beispiel zu Spielen bei SQLFiddle

Mit dem folgenden SQL kann man den ganzen Ast auslesen. Ich nehme mal die ID 9 als Startpunkt Der Ast müsste dann so aussehen:
9 → 10 → 8 → 2 → 1

SELECT
	nav.id,
	nav.title
FROM
	(
		SELECT  
			@cnt := @cnt + 1 AS cnt,
			-- Die letzte ParentID als ID ausgeben
			@id AS id,
			-- Die nächste ParentID ermitteln
			@id := IF(@id IS NOT NULL, (SELECT parentID FROM nav WHERE id = @id), NULL) AS parentID
		FROM
			nav,
			-- Die Variablen initialisieren
			-- TODO: Hier anstelle der 9 deine Start-ID setzen
			(SELECT @id := 9, @cnt:= 0) AS vars
		WHERE
			@id IS NOT NULL
	) AS dat
	-- Das ganze mit der Navigationstabelle verlinken on den Titel 
	-- und ggf. weitere Informationen auszulesen
	 INNER JOIN nav
		ON dat.id = nav.id
ORDER BY
	cnt;

Die Ausgabe sieht dann so aus

Oder wenn man den Pfad jedes Eintrages haben will

Hier habe ich eine zusammenfassung. Das ganze ausführlich und mit Erklärung: Adjacency Tree: Pfad pro id oder bei SQL Fiddle

SELECT
	l.grpid AS id,
	MAX(l.cnt) AS lvl,
	CONCAT(REPEAT('+ ', MAX(l.cnt) -1), l.grptitle) AS tree_title,
	GROUP_CONCAT(p.title ORDER BY cnt DESC SEPARATOR ' -> ') AS lst_title,
	CAST(GROUP_CONCAT(l.pid ORDER BY cnt DESC SEPARATOR '>') AS CHAR) AS lst_id,	
	GROUP_CONCAT(p.srt ORDER BY cnt DESC SEPARATOR '.') AS lst_sort
FROM
	(
		SELECT
			n.id AS grpid,
			n.title AS grptitle,
			-- FLag, ob eine neue ID beginnt
			@flag := (@last_id <> n.id)	AS flag,
			-- Counter pro ID setzen. Wird für die Sortierreihenfolge im GROUP_CONCAT() verwendet
			CASE 
				WHEN @flag
				THEN @cnt := 1
				ELSE @cnt := @cnt+1
			END AS cnt,
			-- Parent ID ermitteln
			CAST(CASE 
				WHEN @flag
				THEN @pid := n.id
				ELSE @pid := @npid
			END AS SIGNED) AS pid,
			-- Nächste Parent ID Ermitteln
			(
				SELECT @npid := n2.parentid
				FROM nav n2  
				WHERE n2.id = @pid
			)					AS npid,			
			@last_id := n.id AS nid
		FROM
			(SELECT @last_id := 0, @pid := 0, @npid := NULL, @cnt:=0) AS vars,
			(SELECT n3.id FROM nav n3) AS loop_rows,
			(SELECT n4.id, n4.title, n4.parentid	FROM nav n4) AS n	
	) AS l
	INNER JOIN (
		-- Details zum Parent
		SELECT id, title,
			-- Sortieurng definieren
			CAST(CASE
				WHEN sort IS NULL
				THEN CONCAT('C_', title)
				ELSE CONCAT('B_', sort)
			END AS CHAR) AS srt
		FROM nav
	) AS p
		ON l.pid = p.id
GROUP BY
	grpid,
	grptitle
ORDER BY
	lst_sort

Natürlich kann es auch interessant sein, den Baum von oben nach unten zu durchsuchen. Die Aufgabenstellung könnte etwa so aussehen: Gib mir alle Unterordner einer bestimmten id. Wenn wir da die Gruppierung weglassen, haben wir eine Auflistung aller ids mit den dazugehörigen parentids. In diesen parentids kann man nun den Ordner suchen und - tada - alle ids die zu diesem Ordner gehören werden ausgegeben.

SELECT
	nav.id,
	nav.title
FROM
	(
		SELECT
			-- id die für den Pfad verwendet wird
			IF(@lastid <> mylist.id, @id := mylist.id, @id) AS pathid,
			-- Die Start-Id.
			@lastid := mylist.id AS id,
			-- bestimmen der nächsten id im Path
			@id := (SELECT parentID FROM nav  WHERE id = @id) AS parentID
		FROM
			-- Variablen initialisieren
			(SELECT @id := 0, @lastid := 0, @rownum := 0) AS vars,
			-- Die Tabelle mit sich selber multiplizieren umd genügend
			-- Zeilen zur Verfügung zu haben
			(SELECT id FROM nav) AS myloop,
			(SELECT id FROM nav) AS mylist
	) AS t
	INNER JOIN nav
		ON t.id = nav.id
WHERE
	-- Wir suchen alle Unterordner der id 2
	pathid = 2

Ergibt mit id=2 das Resultat

Und hier die SQLs um die Beispieldaten in eine eigene DB zu importeiren und die Beispiele nachzuspielen

CREATE TABLE nav
	(`id` INT, `parentId` INT, `title` VARCHAR(9), `sort` INT)
;
 
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (1, NULL, 'Node #001', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (2, 1, 'Node #002', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (3, 2, 'Node #003', 2);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (4, 1, 'Node #004', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (5, 4, 'Node #005', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (6, 5, 'Node #006', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (7, 6, 'Node #007', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (8, 2, 'Node #008', 1);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (9, 10, 'Node #009', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (10, 8, 'Node #010', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (11, NULL, 'Node #011', NULL);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (12, 11, 'Node #012', 2);
INSERT INTO `nav` (`id`, `parentId`, `title`, `sort`) VALUES (13, 11, 'Node #013', 1);

• Beispiel 1 bei sqlfiddle.com
• Beispiel 2 bei sqlfiddle.com
• Beispiel 3 bei sqlfiddle.com