Nested Set - Bestimmung eines Elementes über den Pfad

[Basti93]

Einen guten Tag euch sachkundigen Programmierern dort draußen! :)

Ich habe ein Problem, mit dem ich mich jetzt schon seit längerem beschäftige und zu dem ich auch keine Lösung per Google & CO. gefunden habe. Vielleicht hat ja einer von euch eine Idee, ich bedanke mich schon mal im voraus bei allen, die sich mein Problem anschauen!

Folgendes Szenario:

Ein Dateisystem ist in Form eines Nested-Sets in einer Tabelle gespeichert:

• Eigene Dateien
  • Fotos
    • Urlaub 2012
    • Veranstaltung ABC
  • Rezepte
    • Kuchen
    • Kekse
    • Suppe
• Programme
  • Messenger
    • Fotos
    • Chat
    • Programme
  • Kuchen
  • ImportantEnterpriseStuff

[TABLE="class: grid, width: 500"]
[TR]
[TD]id (PrimaryKey)[/TD]
[TD]alias[/TD]
[TD]left (Index)[/TD]
[TD]right (Index)[/TD]
[TD]level[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]Eigene Dateien[/TD]
[TD]1[/TD]
[TD]16[/TD]
[TD]1[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]Fotos[/TD]
[TD]2[/TD]
[TD]7[/TD]
[TD]2[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]Urlaub 2012[/TD]
[TD]3[/TD]
[TD]4[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]Veranstaltung ABC[/TD]
[TD]5[/TD]
[TD]6[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]Rezepte 2012[/TD]
[TD]8[/TD]
[TD]15[/TD]
[TD]2[/TD]
[/TR]
[TR]
[TD]6[/TD]
[TD]Kuchen[/TD]
[TD]9[/TD]
[TD]10[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]7[/TD]
[TD]Kekse[/TD]
[TD]11[/TD]
[TD]12[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]8[/TD]
[TD]Suppe[/TD]
[TD]13[/TD]
[TD]14[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]9[/TD]
[TD]Programme[/TD]
[TD]17[/TD]
[TD]30[/TD]
[TD]1[/TD]
[/TR]
[TR]
[TD]10[/TD]
[TD]Messenger[/TD]
[TD]18[/TD]
[TD]25[/TD]
[TD]2[/TD]
[/TR]
[TR]
[TD]11[/TD]
[TD]Fotos[/TD]
[TD]19[/TD]
[TD]20[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]12[/TD]
[TD]Chat[/TD]
[TD]21[/TD]
[TD]22[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]13[/TD]
[TD]Programme[/TD]
[TD]23[/TD]
[TD]24[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]14[/TD]
[TD]Kuchen[/TD]
[TD]26[/TD]
[TD]27[/TD]
[TD]2[/TD]
[/TR]
[TR]
[TD]15[/TD]
[TD]ImportantEnterpriseStuff[/TD]
[TD]28[/TD]
[TD]29[/TD]
[TD]2[/TD]
[/TR]
[/TABLE]

Wie ihr sehen könnt, kann ein Alias mehrmals vorkommen. In einem Dateisystem kann ein Ordnername schließlich auch mehrmals vorkommen, z.B.:
C:/Eigene Dateien/Fotos/
C:/Programme/Messenger/Fotos/

Wenn ihr das ganze in einer MySQL-Datenbank testen wollt, könnt ihr einfach diesen Code hier benutzen:

CREATE TABLE IF NOT EXISTS `test_filesystem` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `alias` varchar(255) NOT NULL,
  `left` int(11) NOT NULL,
  `right` int(11) NOT NULL,
  `level` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `left` (`left`,`right`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 AUTO_INCREMENT=16 ;

INSERT INTO `test_filesystem` (`id`, `alias`, `left`, `right`, `level`) VALUES
(1, 'Eigene Dateien', 1, 16, 1),
(2, 'Fotos', 2, 7, 2),
(3, 'Urlaub 2012', 3, 4, 3),
(4, 'Veranstaltung ABC', 5, 6, 3),
(5, 'Rezepte 2012', 8, 15, 2),
(6, 'Kuchen', 9, 10, 3),
(7, 'Kekse', 11, 12, 3),
(8, 'Suppe', 13, 14, 3),
(9, 'Programme', 17, 30, 1),
(10, 'Messenger', 18, 25, 2),
(11, 'Fotos', 19, 20, 3),
(12, 'Chat', 21, 22, 3),
(13, 'Programme', 23, 24, 3),
(14, 'Kuchen', 26, 27, 2),
(15, 'ImportantEnterpriseStuff', 28, 29, 2);

Mein Problem ist nun folgendes:

Angenommen, ich bekomme folgenden Pfad übergeben: Programme/Messenger/Fotos/
Nun würde ich gerne mit Hilfe eines SQL-Befehls die ID des Ordners "Fotos" bekommen.
Ich will also NICHT den Pfad zu dem Element mit der ID 11 haben, sondern anhand dieses Pfades die ID ermitteln.

Mein bisheriger Lösungsansatz ist sehr unschön: (Beispiel: Programme/Messenger/)

SELECT b.id
FROM test_filesystem AS b

WHERE

b.alias = "Messenger" AND


b.left BETWEEN
(
SELECT c.left
FROM test_filesystem AS c
WHERE c.level = 1 AND c.alias = "Programme"
)


AND


(
SELECT c.right
FROM test_filesystem AS c
WHERE c.level = 1 AND c.alias = "Programme"
)

Ihr seht das Problem sicher schon: Bei längeren Pfaden wird diese Version sehr langsam, da sich die Anzahl der Unterabfragen stark erhöht, da ich für jede BETWEEN-Bedingung zwei SELECT-Anweisungen benötige:

Beispiel: Programme/Messenger/Fotos/

SELECT a.id
FROM test_filesystem AS a
WHERE


a.alias = "Fotos" AND


a.left BETWEEN
(
    SELECT b.left
    FROM test_filesystem AS b
    WHERE


    b.alias = "Messenger" AND


    b.left BETWEEN
    (
        SELECT c.left
        FROM test_filesystem AS c
        WHERE c.level = 1 AND c.alias = "Programme"
    )


    AND


    (
        SELECT c.right
        FROM test_filesystem AS c
        WHERE c.level = 1 AND c.alias = "Programme"
    )
)


AND


(
    SELECT b.right
    FROM test_filesystem AS b
    WHERE


    b.alias = "Messenger" AND


    b.left BETWEEN
    (
        SELECT c.left
        FROM test_filesystem AS c
        WHERE c.level = 1 AND c.alias = "Programme"
    )


    AND


    (
        SELECT c.right
        FROM test_filesystem AS c
        WHERE c.level = 1 AND c.alias = "Programme"
    )
)

Könnt ihr mir helfen, einen performanteren SQL-Befehl zu finden, der mein Problem löst?
Vielleicht gibt es ja einen Kniff in der SQL-Syntax, der mir helfen kann oder einer von euch hat eine gute Idee!

Ich würde mich über Hilfe sehr freuen! :)

Ergänzung: Das ganze sollte wenn möglich nur über SQL-Befehle laufen, ohne Zwischenschritte in PHP.

 

[Basti93]

Guten Abend :)
Da hier in diesem Forum wohl keiner eine Idee hat, verweise ich auf die Beiträge in einem anderen Forum, für den Fall, dass auch andere hier sich mit Nested Sets beschäftigen: php.de

 

[mermshaus]

Es ist nett, dass du das machst, aber noch besser wäre es gewesen, die Threads nicht fünf Tage lang parallel laufen zu lassen, sondern sofort Querverweise in beiden Foren zu setzen.

Das als Bitte für die Zukunft. Es ist gerade bei komplizierten Themen einfach super ärgerlich, sich reinzudenken, obwohl schon lange Lösungen existieren.