======[MySQL] Adjacency Tree======
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
=====Ausgangslage=====
>Dank slimox aus dem Tutorial-Forum habe ich jetzt auch eine Ahnung wie diese Variante des Baums heisst: **Adjacency Tree**---Nachzulesen bei [[http://dev.mysql.com/tech-resources/articles/hierarchical-data.html|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
^  Tabelle `nav`  ^^^^
^ id ^ parentId ^ title ^ sort ^
| 1 | _NULL_ | Node #001 | NULL |
| 2 | 1 | Node #002 | NULL |
| 3 | 2 | Node #003 | B |
| 4 | 1 | Node #004 | NULL |
| 5 | 4 | Node #005 | NULL |
| 6 | 5 | Node #006 | NULL |
| 7 | 6 | Node #007 | NULL |
| 8 | 2 | Node #008 | A |
| 9 | 10 | Node #009 | NULL |
| 10 | 8 | Node #010 | NULL |
| 11 | _NULL_ | Node #011 | NULL |
| 12 | 11 | Node #012 | 2 |
| 13 | 11 | Node #013 | 1 |

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'')
^  Baumdarstellung  ^^^^^^^
^ lvl1 ^ lvl2 ^ lvl3 ^  lvl4 ^  lvl5 ^  title ^ Bemerkung ^
| 01 |    |    |    |    | Node #001 | |
|    | 02 |    |    |    | Node #002 | Kein Sort definiert. Darum kommt Node 2 vor Node 4 |
|    |    | 08 |    |    | Node #008 | Dieser Node kommt vor dem Node 3, dank der sort=A |
|    |    |    | 10 |    | Node #010 | |
|    |    |    |    | 09 | Node #009 | |
|    |    | 03 |    |    | Node #003 | Siehe Node 8 |
|    | 04 |    |    |    | Node #004 | |
|    |    | 05 |    |    | Node #005 | |
|    |    |    | 06 |    | Node #006 | |
|    |    |    |    | 07 | Node #007 | |
| 11 |    |    |    |    | Node #011 | |
|    | 13 |    |    |    | Node #013 | Über das Feld sort kommt 13 vor 12 |
|    | 12 |    |    |    | Node #012 | Siehe Node 13 |

=====SQL Beispiele=====
====1) Einfache Pfad-Liste für eine id====

Hier habe ich eine zusammenfassung. Das ganze ausführlich und mit Erklärung:
[[mysql:adjacencytree:pathlistperid]] oder als Beispiel zu Spielen [[http://sqlfiddle.com/#!8/252a2/1|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''
<code sql>
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;
</code>

Die Ausgabe sieht dann so aus

^  Ausgabe Beispiel 1  ^^
^ id ^ title ^
| 9 | Node #009 |
| 10 | Node #010 |
| 8 | Node #008 |
| 2 | Node #002 |
| 1 | Node #001 |


----
====2) Pfad pro id====
Oder wenn man den Pfad jedes Eintrages haben will

Hier habe ich eine zusammenfassung. Das ganze ausführlich und mit Erklärung: [[:mysql:adjacencytree:pathperid]] oder bei [[http://sqlfiddle.com/#!8/9bfeb/12|SQL Fiddle]]

<code sql>
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
</code>

^  Asugabe von Beispiel 2: Pfad pro id  ^^^^^^
^ id ^ lvl ^ tree_title ^ lst_title ^ lst_id ^ lst_sort ^</typo>
| <typo fs:80%;>1</typo> | <typo fs:80%;>1</typo> | <typo fs:80%;>Node #001</typo> | <typo fs:80%;>Node #001</typo> | <typo fs:80%;>1</typo> | <typo fs:80%;>C_Node #001</typo> |
| <typo fs:80%;>2</typo> | <typo fs:80%;>2</typo> | <typo fs:80%;>+ Node #002</typo> | <typo fs:80%;>Node #001 -> Node #002</typo> | <typo fs:80%;>1>2</typo> | <typo fs:80%;>C_Node #001.C_Node #002</typo> |
| <typo fs:80%;>8</typo> | <typo fs:80%;>3</typo> | <typo fs:80%;>+ + Node #008</typo> | <typo fs:80%;>Node #001 -> Node #002 -> Node #008</typo> | <typo fs:80%;>1>2>8</typo> | <typo fs:80%;>C_Node #001.C_Node #002.B_1</typo> |
| <typo fs:80%;>10</typo> | <typo fs:80%;>4</typo> | <typo fs:80%;>+ + + Node #010</typo> | <typo fs:80%;>Node #001 -> Node #002 -> Node #008 -> Node #010</typo> | <typo fs:80%;>1>2>8>10</typo> | <typo fs:80%;>C_Node #001.C_Node #002.B_1.C_Node #010</typo> |
| <typo fs:80%;>9</typo> | <typo fs:80%;>5</typo> | <typo fs:80%;>+ + + + Node #009</typo> | <typo fs:80%;>Node #001 -> Node #002 -> Node #008 -> Node #010 -> Node #009</typo> | <typo fs:80%;>1>2>8>10>9</typo> | <typo fs:80%;>C_Node #001.C_Node #002.B_1.C_Node #010.C_Node #009</typo> |
| <typo fs:80%;>3</typo> | <typo fs:80%;>3</typo> | <typo fs:80%;>+ + Node #003</typo> | <typo fs:80%;>Node #001 -> Node #002 -> Node #003</typo> | <typo fs:80%;>1>2>3</typo> | <typo fs:80%;>C_Node #001.C_Node #002.B_2</typo> |
| <typo fs:80%;>4</typo> | <typo fs:80%;>2</typo> | <typo fs:80%;>+ Node #004</typo> | <typo fs:80%;>Node #001 -> Node #004</typo> | <typo fs:80%;>1>4</typo> | <typo fs:80%;>C_Node #001.C_Node #004</typo> |
| <typo fs:80%;>5</typo> | <typo fs:80%;>3</typo> | <typo fs:80%;>+ + Node #005</typo> | <typo fs:80%;>Node #001 -> Node #004 -> Node #005</typo> | <typo fs:80%;>1>4>5</typo> | <typo fs:80%;>C_Node #001.C_Node #004.C_Node #005</typo> |
| <typo fs:80%;>6</typo> | <typo fs:80%;>4</typo> | <typo fs:80%;>+ + + Node #006</typo> | <typo fs:80%;>Node #001 -> Node #004 -> Node #005 -> Node #006</typo> | <typo fs:80%;>1>4>5>6</typo> | <typo fs:80%;>C_Node #001.C_Node #004.C_Node #005.C_Node #006</typo> |
| <typo fs:80%;>7</typo> | <typo fs:80%;>5</typo> | <typo fs:80%;>+ + + + Node #007</typo> | <typo fs:80%;>Node #001 -> Node #004 -> Node #005 -> Node #006 -> Node #007</typo> | <typo fs:80%;>1>4>5>6>7</typo> | <typo fs:80%;>C_Node #001.C_Node #004.C_Node #005.C_Node #006.C_Node #007</typo> |
| <typo fs:80%;>11</typo> | <typo fs:80%;>1</typo> | <typo fs:80%;>Node #011</typo> | <typo fs:80%;>Node #011</typo> | <typo fs:80%;>11</typo> | <typo fs:80%;>C_Node #011</typo> |
| <typo fs:80%;>13</typo> | <typo fs:80%;>2</typo> | <typo fs:80%;>+ Node #013</typo> | <typo fs:80%;>Node #011 -> Node #013</typo> | <typo fs:80%;>11>13</typo> | <typo fs:80%;>C_Node #011.B_1</typo> |
| <typo fs:80%;>12</typo> | <typo fs:80%;>2</typo> | <typo fs:80%;>+ Node #012</typo> | <typo fs:80%;>Node #011 -> Node #012</typo> | <typo fs:80%;>11>12</typo> | <typo fs:80%;>C_Node #011.B_2</typo> |




====3) Alle Unterordner einer id====
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.
<code sql>
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
</code>

Ergibt mit id=2 das Resultat
^  Ausgabe von Beispiel 3: Alle Unterordner einer id  ^^
^ id ^ title ^
| 2 | Node #002 |
| 3 | Node #003 |
| 8 | Node #008 |
| 9 | Node #009 |
| 10 | Node #010 |


=====Beispiel-Script=====
Und hier die SQLs um die Beispieldaten in eine eigene DB zu importeiren und die Beispiele nachzuspielen
<code sql>
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);
</code>

===== Spielwiese =====
  *[[http://sqlfiddle.com/#!2/e1702/1|Beispiel 1 bei sqlfiddle.com]]
  *[[http://sqlfiddle.com/#!2/e1702/2|Beispiel 2 bei sqlfiddle.com]]
  *[[http://sqlfiddle.com/#!2/e1702/3|Beispiel 3 bei sqlfiddle.com]]
{{tag>MySQL Tree}}