Mapstructuur in tabelvorm, alle mappen onder bepaalde map?

[CyberSnooP]

Ik gebruik hiervoor op dit moment PHP en MySQL, maar ben eigenlijk een beetje opzoek naar een standaard oplossings methode voor het volgende:

Ik heb een database tabel folders met de velden: id en parent (en natuurlijk nog meer zoals name). Als voorbeeld even de volgende inhoud:

code:

id | parent 
1   NULL
2   1
3   2
4   2
5   4
6   1

In boom vorm:
1
|-2
| |-3
| |-4
|   |-5
|-6

Nu wil ik graag met een query bijvoorbeeld alle mapen onder map 2 verzamelen. Ik hoop dan dus de rijen behoorende bij de IDs 3, 4 en 5 te krijgen.

Echter, het testen van de parent vereist een soort van recursie. Is het toch mogelijk om met een query alle kinderen (direct en indirect)van map 2 te verkrijgen? En zo niet: wat is hier dan de meest praktische oplossing voor?

[xtra]

Helaas, je zit toch aan recursie vast. Alleen van Oracle weet ik dat je met CONNECT BY in een keer een boomstructuur kunt krijgen.
Alternatief is een andere structuur van je tabel. Met het Nested Set model krijg je wel eenvoudig alle onderliggende rijen. Zie http://www.webgoeroe.net/item/277
(Ziet er wel boeiend uit, maar ik heb het zelf nooit toegepast.

[bigtree]

Het kan ook zonder recursie. Zie mijn post in [Php/mysql] recursief tree weergeven *.
Je moet dan wel van 2 tabellen gebruik maken in plaats van één.

[Lister]

bigtree schreef op 27 april 2003 @ 02:27:
Het kan ook zonder recursie. Zie mijn post in [Php/mysql] recursief tree weergeven *.
Je moet dan wel van 2 tabellen gebruik maken in plaats van één.

Ik heb ff gekeken naar je voorbeeld en op zich is het leuk bedacht en je kan dan wel snel alle childs van een parent vinden, maar volgens mij wordt het een stuk lastiger om de positie van die childs onder een parent te vinden.

Als je 4 hebt toegevoegd zoals in jouw voorbeeld dan wordt de Children tabel als ik het goed heb
1,2
1,3
1,4
3,4

Als je dan de tree weer wilt opbouwen moet je voor elke child kijken of er nog een andere parent is want dan zit hij op een sublevel. En daarna moet je nog eens voor alle niet-sublevel childs kijken welke childs daar onder hangen.
Voor Parent 1:
Child 2 -> geen andere parents dus hangt direct onder 1
Child 3 -> geen andere parents dus hangt direct onder 1
Child 4 -> wel een andere parent dus overslaan

Dan weer voor alle niet-sublevel childs
Parent 2: -> geen andere childs, dus klaar
Parent 3: -> Child 4 -> geen andere parents dus hangt direct onder 3

Dan weer voor alle niet-sublevel childs
Parent 4: -> geen andere childs, dus klaar

Ik weet niet of ik het een beetje duidelijk verwoordt, maar ik denk dus dat het niet echt simpeler wordt, tenzij je niet geinteresseerd bent in de daadwerkelijke boomstructuur.

[Genoil]

Er is ook een compleet andere manier om trees op te slaan, waarbij er slechts 1 simpele query nodig is om de tree er netjes gesorteerd uit te halen:

hele lap halfgare nested set achtige oplossing weggehaad...rubbish...

hier wordt het allemaal nog wat ingewikkelder uitgelegd:

http://groups.google.com/...posting.google.com&rnum=3

[ Voor 103% gewijzigd door Genoil op 28-04-2003 09:47 ]

[Knutselsmurf]

Zoiets heb ik ook ooit gebouwd en ik zat ook met hetzelfde probleem. Uiteindelijk heb ik het opgelost met de volgende query(s):

code:

  select ID,alle_ander_informatie from folders where parent in (gevonden_resultaten);

In eerste instantie is gevonden_resultaten in dit geval 2. In het voorbeeld komen hier 2 resultaten uit, 3 en 4. Deze worden in PHP aan een lijstje toegevoegd en de query wordt opnieuw uitgevoerd, waarna 5 als resultaat komt. Deze opnieuw toevoegen enz, enz. net zolang tot de query geen resultaten meer geeft. Deze manier kost je 1 query per 'diepte'. Let er wel op, dat de volgorde waarin de resultaten uiteindelijk beschikbaar komen wat apart is. Eerst alle resultaten van niveau 1, dan niveau 2 enz. In dit voorbeeld is dat toevallig gelijk. Maar stel dat node 5 onder node 3 zou hangen. Dan krijg je met deze methode als volorde 3,4,5 terwijl met andere methoden 3,5,4 als resultaat verkregen wordt. Vraag is dus nog of de volgorde uitmaakt......

[MrBrown]

Wat ook een wel simpele methode is, is behalve je id en je parent ook het pad naar een node op te slaan.
Dus bijvoorbeeld bij jou voorbeeld het item 3:
ID = 3
Parent = 2
Path = 1.2.3

Om dan bijvoorbeeld de kinderen van item 2 te verkrijgen kan je een query bouwen als:
SELECT * FROM Table WHERE Path LIKE '1.2.%'

[Genoil]

MrBrown schreef op 27 April 2003 @ 16:25:
Wat ook een wel simpele methode is, is behalve je id en je parent ook het pad naar een node op te slaan.
Dus bijvoorbeeld bij jou voorbeeld het item 3:
ID = 3
Parent = 2
Path = 1.2.3

Om dan bijvoorbeeld de kinderen van item 2 te verkrijgen kan je een query bouwen als:
SELECT * FROM Table WHERE Path LIKE '1.2.%'

Het nadeel van het pad opslaan is wanneer je een node met daaronder een hele subtree aan nodes verplaatst, moet je van de gehele subtree de paden aan gaan passen, terwijl je anders slechts het parent_id van de verplaatste node hoeft aan te passen. Daarnaast heb je bij bovenstaande query totaal geen grip op de structuur van een onderliggende subtree. Ik bedoel, nodes 1.2.24, 1.2.3.67.87, 1.2.25, 1.2.678.122.3452 enz. enz komen semi-willekeurig als resulaat uit die query, zonder enige structurering. kun je in PHP alsnog alles gaan lopen sorteren, alsof dat geen tijd kost

[MrBrown]

Genoil schreef op 27 april 2003 @ 18:08:
[...]


Het nadeel van het pad opslaan is wanneer je een node met daaronder een hele subtree aan nodes verplaatst, moet je van de gehele subtree de paden aan gaan passen, terwijl je anders slechts het parent_id van de verplaatste node hoeft aan te passen. Daarnaast heb je bij bovenstaande query totaal geen grip op de structuur van een onderliggende subtree. Ik bedoel, nodes 1.2.24, 1.2.3.67.87, 1.2.25, 1.2.678.122.3452 enz. enz komen semi-willekeurig als resulaat uit die query, zonder enige structurering. kun je in PHP alsnog alles gaan lopen sorteren, alsof dat geen tijd kost

Probleem 1: Ja, dat klopt, je moet dan inderdaad een afweging maken. Als het aantal updates hoog is in verhouding met het aantal selects, dan is deze manier idd niet echt aan te raden.
Probleem 2: ORDER BY Path

[Soultaker]

Genoil schreef op 27 April 2003 @ 18:08:
Het nadeel van het pad opslaan is wanneer je een node met daaronder een hele subtree aan nodes verplaatst, moet je van de gehele subtree de paden aan gaan passen, terwijl je anders slechts het parent_id van de verplaatste node hoeft aan te passen. Daarnaast heb je bij bovenstaande query totaal geen grip op de structuur van een onderliggende subtree. Ik bedoel, nodes 1.2.24, 1.2.3.67.87, 1.2.25, 1.2.678.122.3452 enz. enz komen semi-willekeurig als resulaat uit die query, zonder enige structurering. kun je in PHP alsnog alles gaan lopen sorteren, alsof dat geen tijd kost

Beide problemen worden opgelost door de manier te gebruiken waar xtra op wees (http://www.webgoeroe.net/item/277). Deelbomen verplaatsen kost dan slechts een vast aantal lineaire queries en als je je SQL queries sorteert op id, krijg je er een handige uitvoer uit (die je meestal direct kunt gebruiken).

[martinvw]

Genoil schreef op 27 April 2003 @ 13:11:
Er is ook een compleet andere manier om trees op te slaan, waarbij er slechts 1 simpele query nodig is om de tree er netjes gesorteerd uit te halen:

code:

De tree:

A
|
+-AA
|  |
|  +-AAA
|  +-AAB
|
+-AB
   |
   +-ABA
   +-ABB


De tree in een "x,y" coordinatenstelsel: 

        -X-
   
-------------------
|        A        |
---------+---------   |
|  AA    |   AB   |   Y
----+----+----+----   |
|AAA| AAB| ABA|ABB|   
-------------------


De databasetabel:

id |name| y | x |
---+----+---+---|
 1 |   A| 0 | 0 |
 2 |  AA| 1 | 0 |
 3 |  AB| 1 | 2 |
 4 | AAA| 2 | 0 |
 5 | AAB| 2 | 1 |
 6 | ABA| 2 | 2 |
 7 | ABB| 2 | 3 |

Het eerste figuur laat de tree zien zoals we hem willen hebben. Het tweede figuur laat de tree in een andere voorstelling zien, elke node krijgt een x en een y coordinaat, waarbij de linker- resp. bovenkant van het blok de waarde van het coordinaat bepaalt (x positief naar rechts, y positief naar beneden). De derde figuur is de bijhorende databasetabel. Met een eenvoudige query:

code:

SELECT * FROM tree ORDER BY x,y

krijg je de nodes eruit in exact dezelfde volgorde van boven naar beneden als in de bovenste figuur. Met de waarden voor x en y kun je bij het renderen zo bepalen hoever je moet inspringen.

Nadeel van deze methode is het bewerken van de tree, dit is bewerkelijk en daarom is deze methode met name geschikt voor tree die weinig worden bewerkt en veel worden gelezen. Daar heb ik ook nog geen code voor, ik kan ook helaas het artikel waarin me dit werd uitgelegd niet meer vinden...

[edit]

oww, ik zat er nog ff over na te denken, en waneer je een gedeelte van de tree wilt weergeven, moet je x eigenlijk opsplitsen in x_left en x_right, voor de linker en rechtercoordinaat van de node. Alle children van AA (x_left=0, x_right=2, y=1)

code:

SELECT * FROM tree WHERE x_left > 0 AND x_right < 2 AND y > 1  ORDER BY x_left,y

[nogeenedit]

oooh het kan nog mooier, heb je die y ook niet meer nodig. je hebt dus alleen nog x_left en x_right. query voor de gehele tree wordt dan:

code:

SELECT * FROM tree ORDER BY x_left, x_right DESC

hier wordt het allemaal nog wat ingewikkelder uitgelegd:

http://groups.google.com/...posting.google.com&rnum=3

Deze methode staat ook op de eerder gegeven link, is eigenlijk wel interessant

Ben nog ff aan t lezen.
Klaar, ik vind t kewl, ik denk dat ik er zo nog ff mee ga spelen.

[ Voor 3% gewijzigd door martinvw op 27-04-2003 19:18 ]

[Genoil]

MrBrown schreef op 27 April 2003 @ 18:43:
[...]

Probleem 2: ORDER BY Path

oja, maar gaat dat dan wel goed met int(10) > int(9) vs. string("10") < string("9") qua orderen?

verder weer behoorlijk van me dat ik over dat artikel op webgoeroe heengelezen heb....

[EfBe]

De methodiek van Joe Celko, aangehaald in die google groups link is het materiaal wat je moet doornemen. Celko was een van de mensen uit de Sql standaardisatie commissie, hij weet waar hij over praat

[CyberSnooP]

xtra schreef op 26 april 2003 @ 22:19:
Alternatief is een andere structuur van je tabel. Met het Nested Set model krijg je wel eenvoudig alle onderliggende rijen. Zie http://www.webgoeroe.net/item/277

Wat ik zo apart vind aan deze methode (die ook wordt beschreven in de google newsgroup link hierboven) is dat een item toevoegen zo onwijs veel row updates vereist als het een beetje links in de boom komt (een lage right waarde van het element waarnaast je wil invoegen). Is dat niet ook redelijk inefficient?

Ik ben wel van plan om de Nested Set methode een keer te gaan proberen, maar het process van invoegen (kiezen van nieuwe left-right waarden) is me nog niet helemaal duidelijk.

[Soultaker]

CyberSnooP schreef op 27 April 2003 @ 20:33:
Wat ik zo apart vind aan deze methode (die ook wordt beschreven in de google newsgroup link hierboven) is dat een item toevoegen zo onwijs veel row updates vereist als het een beetje links in de boom komt (een lage right waarde van het element waarnaast je wil invoegen). Is dat niet ook redelijk inefficient?

In principe wel, maar het hangt er een beetje vanaf hoe groot je boom is en waar je 'm voor gebruikt. Als je een relatief grote boomstructuur zoals bijvoorbeeld de Google Directory (http://directory.google.nl/) hebt, dan is die nog niet zo groot dat het updaten van alle indices echt heel ingewikkeld is (enkele tientallen tot honderden rijen updaten is peanuts). Belangrijker is echter dat een dergelijke boomstructuur heel vaak doorlopen wordt (misschien wel tientallen malen per seconde!) en slechts zelden bijgewerkt (hooguit een keer per week, of iets dergelijks).

In zo'n situatie is het aantrekkelijk om (zoals ook in het webgoeroe-artikel stond) de moeizame updates te accepteren in ruil voor een datastructuur die wel efficient uit te lezen is.

[bigtree]

Lister schreef op 27 April 2003 @ 11:29:
[...]
Als je dan de tree weer wilt opbouwen moet je voor elke child kijken of er nog een andere parent is want dan zit hij op een sublevel. En daarna moet je nog eens voor alle niet-sublevel childs kijken welke childs daar onder hangen.

Je hebt helemaal gelijk. Het doel van mijn methode was echter dat je alle children met één query kon ophalen, dat lukt prima.

Als je daarna de tree wilt opbouwen zul je ofwel een recursieve functie uit moeten dokteren die de children onder de goede parent zet (volgens jouw methode), ofwel de foreign key van de *directe* parent van een node gewoon in je Items tabel op moeten nemen. Da's trouwens een stuk sneller! Weliswaar redundant, maar dat is de hele children tabel ook al.

[Verwijderd]

Niet PHP, maar misschien wel een leuk stukje;
http://msdn.microsoft.com...ld/html/storagedbdsgn.asp

Zie de paragraaf Designing a Hierarchical Directory. Hier wordt verteld wat voor verschillende truukjes er zijn om dit optelossen.