~~DISCUSSION~~
======Adjacency Tree: Pfad pro id======
=====Aufgabenstellung=====
So. Nun widmen wir uns also einer weiteren interessanten Aufgabe. Das Ziel ist es, zu jedem Node den ganzen Pfad auf einer Zeile anzuzeigen. Zudem wollen wir ein Tree-String. Die Sortierung des Tree soll das sort-feld berücksichtigen


====SQL Statmenent====
<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, @det_grp := 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>

====Ausgabe====
^  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> |


=====Erklärbär=====
Acuh das sieht komplizierter aus als es ist. Ich gehe mal weiter von Innen nach Aussen zum erklären was da abgeht.

====Konzept====
Das Grundkonzept ist einfach. ich kombiniere

====Variablen setzen====
<code sql ;vars>-- [VARS]
(SELECT @last_id := 0, @pid := 0, @npid := NULL, @cnt:=0) AS var</code>
Auch hier kommen wir nicht ohne Variablen aus - Sorry. In diesem Schritt initialisiere ich mal alle Variablen.
  ***@lastid** Mein gedächnis welche ID auf der Zeile davor war
  ***@pid** ParentID. ID des aktuellen Parent
  ***@npid** Next Parent ID. Also der Parent des aktuellen Parents
  ***@cnt**Ein Counter, der wird für die richtige Reihenfolge verwednet. 1....n. 1 = tiefster Level, n oberster Level

====Gird erstellen====
<code sql grid>-- [GRID]
			(SELECT n3.id FROM nav n3) AS loop_rows,
			(SELECT n4.id, n4.title, n4.parentid	FROM nav n4) AS n	
</code>
Damit ich genügend Zeilen zur Verfügung habe, nehme ich einfach meine Tabelle und bringe sie ohne JOIN zusammen. Das gibt mit [Anzahl Zeilen von `nav`]<sup>2</sup> Zeilen.
\\ loop_ros interessiert nicht weiter. Bei n nehmen wir noch den Titel und den Parent-ID mit

====Den Baum durchiterieren====
<code sql prepared_data>-- [PREPARED_DATA]
		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	
</code>

=== ID-Reihenfolge der Tabellenkombination ===

Jetzt gehe ich alle Zeilen durch. Die Reihenfolde der Daten ist nun wichtig. Wenn ich das obige SQL 
mal kürze, dann sehen wir wie die ID-Reihenfolge ist. Wichtig, dass die 2te Spalte immer die gleichen iDs untereinander hat. Das macht MySQL selber schon richtig.
<code sql>SELECT 
	myloop.id AS loop_id,
	mylist.id AS list_id
FROM
	(SELECT id FROM nav) AS myloop,
	(SELECT id FROM nav) AS mylist
ORDER BY
	mylist.id,
	myloop.id</code>

Das ergibt das folgende
^ loop_id ^ list_id ^
| 1 | 1 |
| 2 | 1 |
| ... | 1 |
| 13 | 1 |
| 1 | 2 |
| 2 | 2 |
| ... | 2 |
| 13 | 2 |
| ... | ... |
| 13 | 13 |

=== Die Formeln ===
Dann nehme ich mir mal die Formalen zur Brust.
Das Verfahren ist jetzt, dass wir mit der ersten n.id beginnen und von dieser den Parent bestimmen. Im nächsten Eintrag der n.id-Gruppe (siehe Spalte 2 im Kapitel vorher) bestimmen wir den Parent vom Parent. Dies geht so weiter, bis der Parent NULL ist.
<code sql>
			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
</code>
	
== flag: Neue ID-Flag ==		
<code sql>@flag := (@last_id <> n.id)	AS flag</code>
\\ Wie wir weiter oben gesehen haben, ist die mylist nach der ID sortiert. Ich vergleiche nun, ob sich die ID 
noch die gleiche wie auf der letzten Zeile ist und speichere das Resultat in die Variable @flag

== cnt: Counter ==
<code sql>CASE 
	WHEN @flag
	THEN @cnt := 1
	ELSE @cnt := @cnt+1
END AS cnt,</code>
Dies ist ein Counter, der bei jeder neuen ID wieder mit 1 beginnt.

== pid: Parent-ID==
<code sql>CAST(CASE 
	WHEN @flag
	THEN @pid := n.id
	ELSE @pid := @npid
END AS SIGNED) AS pid,</code>
Dies ist die ID des Parents des aktuellen Eintrages. Bei einer neuen ID-Gruppe wird die ID selber übernommen. Ansonsten ists der Parent, der in der Zeile davor als npid ermittelt wurde

== npid: Nächste Parent-ID ==
<code sql>(
	SELECT @npid := n2.parentid
	FROM nav n2  
	WHERE n2.id = @pid
)	AS npid,</code>
Hier wird der Parent des aktuelen Parents ermittelt.

== nid: Nächste Last-ID ==
<code mysql>@last_id := n.id AS nid</code>


Das Resultat sieht gekürzt dann etwa so aus. Die Spalte grpid ist die ID des nodes, pid die ID der Parents
^ grpid ^ grptitle ^ flag ^ cnt ^ <wrap em>pid</wrap> ^ npid ^ nid ^
| 1 | Node #001 | 1 |1 | <wrap em>1</wrap> | NULL | 1 |
| 1 | Node #001 | 0 |2 | NULL | NULL | 1 |
| ... |||||||
| 11 | Node #011 | 1 | 1 | <wrap em>11</wrap> | NULL | 11 |
| 11 | Node #011 | 0 | 2 | NULL | NULL | 11 |
| ... |||||||
| 6 | Node #006 | 1 | 1 | <wrap em>6</wrap> | 5 | 6 |
| 6 | Node #006 | 0 | 2 | <wrap em>5</wrap> | 4 | 6 |
| 6 | Node #006 | 0 | 3 | <wrap em>4</wrap> | 1 | 6 |
| 6 | Node #006 | 0 | 4 | <wrap em>1</wrap> | NULL | 6 |
| 6 | Node #006 | 0 | 5 | NULL | NULL | 6 |
| ... |||||||
| 3 | Node #003 | 1 | 1 | <wrap em>3</wrap> | 2 | 3 |
| 3 | Node #003 | 0 | 2 | <wrap em>2</wrap> | 1 | 3 |
| 3 | Node #003 | 0 | 3 | <wrap em>1</wrap> | NULL | 3 |
| 3 | Node #003 | 0 | 4 | NULL | NULL | 3 |
| ... |||||||

=====Infos Ergänzen, Gruppieren und Pfad bilden=====
So, jetzt nur noch alles zusammenpacken, die Infos der Nodes ergänzen und fertig.
Ich glaube, dieser Code-teil ist selbstsprechend
<code mysql>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
	[PREPARED_DATA] 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>

===== Sortierung =====
Nur noch soviel zur Sortierung.
Die Sortierung im Beispiel ist die folgende. Nodes mit einem sort-Eintrag haben vor den anderen Vorrang. Darim wird für die Sortierung ein B als Prefix verwendet. Bei den restlichen Feldern wird nach title sortiert. Mit dem Prefix C kommen sie definitiv nach den B-Nodes. Diese Sortierung kann beliebig im folgenden Code-Schnippsel angepasst werden.
<code mysql>CAST(CASE
	WHEN sort IS NULL
	THEN CONCAT('C_', title)
	ELSE CONCAT('B_', sort)
	END AS CHAR) AS srt</code>

Der nachteil, Zaheln werden ebenfalls als Text sortiert. Ergo kommt 11 (''B_11'') vor 2 (''B_2'')
Als weiteres Beispiel eine Lösung, damit nach Zahlen und nach Text sortiert werden kann. Die Zahl sollte mehr als 10 Ziffern sein. Ansonsten muss der LPAD() angepasst werden
<code mysql>    CASE
        WHEN sort REGEXP '^[[:digit:]]+$'
        THEN CONCAT('B_', LPAD(sort, 10, '0'))
        WHEN NOT sort IS NULL
        THEN CONCAT('B_', sort)
        ELSE CONCAT('C_', title)
    END AS srt_2</code>


{{tag>MySQL Tree}}