[mysql] boomstructuur

[Gaafy]

Hoi,

Ik ben bezig met een site waar een paar keen een boomstructuur in voor komt. Bijvoorbeeld bij het forum.
Nu staat bij bericht 2 in de kolom "parent" dat bericht 1 zijn ouder is.
Bij bericht 3 staat dan dat 2 zijn parent is.

Ik kom er niet uit, is het mogelijk deze structuur netjes weer tegeven. En hoe doe ik dit met zo min mogelijk query's?

Heeft er iemand toevallig nog een query liggen om dit netjes onder elkaar te krijgen. Dus als bericht 1 hebt je kan zien welke berichten er onder hangen, en als je bericht 3 kan zien welke berichten er boven hangen.

Alvast bedankt,

Gaafy

[Janoz]

Een boomstructuur is erg lastig in een relationele database. Vooral als er html pagina's gemaakt moeten worden..

Tenzij je met iets dynamischere omgeving bezig gaat (flash, applets) kun je beter geen boomstructuur gebruiken.

[Verwijderd]

[search=tree]

[Gaafy]

Op vrijdag 12 oktober 2001 12:06 schreef Janoz het volgende:
Een boomstructuur is erg lastig in een relationele database. Vooral als er html pagina's gemaakt moeten worden..

Tenzij je met iets dynamischere omgeving bezig gaat (flash, applets) kun je beter geen boomstructuur gebruiken.

Maar hoe maak ik dan een forum wat oneindig "diep" kan?

[chem]

[search=recursive] of [search=recursief] of [search=pyramide]

maar zwaar is het zeker

[tomato]

Op vrijdag 12 oktober 2001 12:15 schreef Gaafy het volgende:

[..]

Maar hoe maak ik dan een forum wat oneindig "diep" kan?

Er zijn wel truckjes voor, maar zonder die truckjes zal een goed relationeel model een enorm slechte performance krijgen bij veel lagen.
Ik heb hier ooit al eens iets uitgelegd over hoe je 'redelijk efficient' alle berichten per laag uit een goed relationeel model kunt krijgen. MrX had nog een veel mooier idee, al vond ik dat het wel voor wat database vervuiling zorgde. Je kon daarmee echter wel zeer efficient threads opbouwen. Ik weet niet zeker of dat topic weg is door BC3 ( ), anders moet het nog wel te vinden zijn.

[Verwijderd]

Ik gebruik iets in deze aard:

code:

function GetChildMsgs ($parent, $topic_id, $depth, $user) {

      $child_query = "SELECT * FROM $msgbrd_msgs WHERE TopicID=$topic_id AND ParentID='$parent' ORDER BY MsgID DESC";
      $child_result = mysql_query($child_query);

      while( $row = mysql_fetch_array($child_result) ) {

            $id = $row["MsgID"];
            $subject = $row["Subject"];
            $person = $row["Poster"];
            $date = $row["Date"];
            $date = date("j/m, G:i", strtotime($date));
            $sub = trimString($subject, 30);

            echo "\n\n<!-- CHILD $id, $parent -->\n";

            $i = 0;
            while ( $i < $depth ) {
                echo "&nbsp;&nbsp;";
                $i++;
            }

            ?>
            <a href="msg.php?topic_id=<? echo $topic_id; ?>&x=<? echo $id; ?>#
            <? echo $id; ?>" target="rightFrame" class="msglist" title="<? echo $subject; ?>"><font size="1">
            <? echo $sub; ?></font></a>
            <font size="1"> - </font><? echo $person; ?> - <font size="1">(<? echo $date; ?>)</font><br>
            <?

        // Recursive oproep met 1 level dieper
            GetChildMsgs($id, $topic_id, $depth+1, $user);
      }
}

Je oproep start je dan met:

code:

$msgs_query = "SELECT * FROM $gp_msgbrd_msgs WHERE TopicID=$topic_id AND ParentID=0 ORDER BY MsgID DESC LIMIT $start,$count";
$msgs_result = mysql_query($msgs_query);

while( $row = mysql_fetch_array($msgs_result) ) {

      $id = $row["MsgID"];
      $subject = $row["Subject"];
      $person = $row["Poster"];
      $date = $row["Date"];
      $date = date("j/m, G:i", strtotime($date));
      $sub = trimString($subject, 30);

      GetChildMsgs($id, $topic_id, 1, $user);
}

Het is heel belangrijk dat je een index maakt op je news_id EN op je parent_id in je msgs tabel, anders gaan je queries een heel stuk langzamer gaan.

[Verwijderd]

Op vrijdag 12 oktober 2001 12:21 schreef tomato een heleboel, en onder andere het volgende:
MrX had nog een veel mooier idee, al vond ik dat het wel voor wat database vervuiling zorgde. Je kon daarmee echter wel zeer efficient threads opbouwen. Ik weet niet zeker of dat topic weg is door BC3 ( ), anders moet het nog wel te vinden zijn.

/me zucht
Jammer is dat, kan me nog wel herinneren dat we met een paar mensen een hele mooie oplossing hadden verzonnen, en die's inderdaad helaas verloren gegaan.

Ik zal nog eens kijken of ik het idee kan reproduceren en mooi omschrijven, maar ik schudt het ook niet zomaar uit mijn mouw.

[Nielsz]

NarfStyler >> Jij gebruikt dus per tak een query.
Niet optimaal denk ik zo.

[dusty]

Betere structuur gebruiken voor de database. Extra Kolom waarmee je kunt selecteren op de juiste volgorde waarmee je aan de hand van die data kan nagaan of het een nieuw bericht is of een "diepere" reply.

Voorbeeldje:

"47474.1.1"
"47474.1.2"
"47474.1.1.1"
"47474.1.1.2"

47474 is het bericht nummer de rest kan je zelf bedenken als je er goed over nadenk.

Hierdoor ga je het dus afvangen aan de programmeerkant ipv de database kant. Omdat anders de performance van de database te slecht wordt. (en dat vangt dit op.)

[chem]

Op vrijdag 12 oktober 2001 12:34 schreef MrX het volgende:

[..]

/me zucht
Jammer is dat, kan me nog wel herinneren dat we met een paar mensen een hele mooie oplossing hadden verzonnen, en die's inderdaad helaas verloren gegaan.

Ik zal nog eens kijken of ik het idee kan reproduceren en mooi omschrijven, maar ik schudt het ook niet zomaar uit mijn mouw.

http://gathering.tweakers.net/forum/list_messages/49380/1?limit=50 staat nog het eea.

[tomato]

Op vrijdag 12 oktober 2001 13:05 schreef chem het volgende:

[..]

http://gathering.tweakers.net/forum/list_messages/49380/1?limit=50 staat nog het eea.

Ja, maar dat is wel een erg oude thread en die 'mooie' methode komt daar niet in voor. Dacht trouwens dat die methode (ongeveer) op hetzelfde neerkwam als wat dusty hier zegt.

[drm]

* drm heeft het zo gedaan:

tabel struct

code:

nodeID    INT PK autoincr.
parentID  INT
type    enum ( "folder", "document", ... )

om een parent van een bepaalde node te krijgen:

code:

SELECT parentID
FROM   struct
WHERE  nodeID='$nodeID';

om de children van een bepaalde parent te krijgen:

code:

SELECT nodeID,type
FROM   struct
WHERE  parentID='$parentID';

dat is toch niet zo ingewikkeld
kwestie van recursie als je dieper dan 1 laag gaat.

_edit:
oh ja, als je een node meerdere parents wil laten hebben moet je van nodeID en parentID een samengestelde sleutel maken

[Verwijderd]

Op vrijdag 12 oktober 2001 13:39 schreef drm het volgende:
[...]
dat is toch niet zo ingewikkeld
kwestie van recursie als je dieper dan 1 laag gaat.

Niet ingewikkeld, maar veel te database intensief.

Als je check op een parent-child relatie 1 select query moet draaien draai je voor een stevige discussie al snel 50 queries, en dat is dan alleen nog voor het ophalen van de data van de discussie, niet voor andere eventueel dynamische elementen.

Met mijn hiervoor genoemde oplossing kun je in ieder geval het aantal queries beperken tot het aantal nivo's dat je wil afbeelden. Maar mijn 'mooie' & 'missing in action' oplossing liet het toe een hele boom in 1 query op te halen. Hoewel het wel een zware query zou zijn en er nogal wat overhead by kwam door een 'slim' databasemodel is dat mischien toch wel de moeite waard.

[drm]

-oops-

<sub>---->O------ snip ---->O------

En nu een echt reply:</sub>

MrX:
Niet ingewikkeld, maar veel te database intensief.

mwahhh:

code:

SELECT   t2.nodeID
FROM     struct as t1,
       struct as t2
WHERE    t1.parentID = t2.nodeID
    AND  t1.nodeID = '$nodeID';

Doe maar van genererenstein met PHP.

[Verwijderd]

drm, dat betekent dat je per node 1 query moet draaien, plus voor iedere uiteinde-node (dus een node zonder child) nog een query. Dat zou voor een beetje boomstruur al snel aardig wat queries zijn.

Nou is de query op zich wel een eenvoudige query, maar 30 maal 1 simpele query is nog steeds een behoorlijke databasebelasting.

[Verwijderd]

Op vrijdag 12 oktober 2001 13:55 schreef MrX het volgende:

[..]

Niet ingewikkeld, maar veel te database intensief.

Als je check op een parent-child relatie 1 select query moet draaien draai je voor een stevige discussie al snel 50 queries, en dat is dan alleen nog voor het ophalen van de data van de discussie, niet voor andere eventueel dynamische elementen.

Met mijn hiervoor genoemde oplossing kun je in ieder geval het aantal queries beperken tot het aantal nivo's dat je wil afbeelden. Maar mijn 'mooie' & 'missing in action' oplossing liet het toe een hele boom in 1 query op te halen. Hoewel het wel een zware query zou zijn en er nogal wat overhead by kwam door een 'slim' databasemodel is dat mischien toch wel de moeite waard.

Het nivo's kun je toch gewoon meecoden met een $maxdepth en als die bereikt is niet meer doorgaan ? En een hele boom in 1 query ophalen lijkt me echt wel heel straf.
Als je dat diepte probleem in de database zelf gaat steken kun je het natuurlijk via een query doen, maar ik vind het persoonlijk overbodige informatie opslaan.
Maar het is natuurlijk altijd een afweging tussen mooi design en traag dan overbodig zijn en sneller.

Als je voor het dislaying van een tree met alleen de nummers van msgs en hun subject een index maakt op die 2 velden, gaat dat displayen ook al een stuk sneller dan zonder index.

[dusty]

Op vrijdag 12 oktober 2001 14:09 schreef TheNarfstyler het volgende:

[..]

Het nivo's kun je toch gewoon meecoden met een $maxdepth en als die bereikt is niet meer doorgaan ? En een hele boom in 1 query ophalen lijkt me echt wel heel straf.
Als je dat diepte probleem in de database zelf gaat steken kun je het natuurlijk via een query doen, maar ik vind het persoonlijk overbodige informatie opslaan.
Maar het is natuurlijk altijd een afweging tussen mooi design en traag dan overbodig zijn en sneller.

Als je voor het dislaying van een tree met alleen de nummers van msgs en hun subject een index maakt op die 2 velden, gaat dat displayen ook al een stuk sneller dan zonder index.

Je zou de diepte mee kunnen coden. Echter ga je 3 lagen diep ga je in iedergeval voor elke reactie op de eerste 2 lagen kijken of er reacties op geweest zijn. Dit is erg database intensief (allemaal losse queries..) Dus dat wil je waarschijnlijk niet, vooral niet als een database druk bezocht wordt.

Als je de normaal vormen gaat bekijken zal je zien dat bij de 4e en 5e normaal vorm het erg gebruikelijk is om extra informatie erbij te slaan om de snelheid van de database te waarborgen. Immers is het soms sneller om iets aan de codeer kant af te vangen dan aan de database kant. Dit is vooral bij de wat meer ingewikkelde formules. Dit is een typisch geval van zo'n situatie. Dus JA het is extra informatie die je opslaat over de boom. Maar door die methode kan je wel de snelheid van de database waarborgen wat erg belangrijk is bij een druk bezochte forum of een forum met erg veel reacties en dieptes. Maar je moet je niet vergissen dat hierdoor de design juist slechter wordt, juist door deze methode toe te passen breng je je database model een stapje hoger in de normaal vorm en wordt alleen je design mooier en sneller.

[Verwijderd]

Overigens vraag ik me af of een Directory Service niet een mooie oplossing zou kunnen bieden voor het opzetten van een forum met een sterk hierargische structuur.

[Verwijderd]

4de en 5de normaalvorm ? Kun je die eens verduidelijken, staan namelijk niet in mijn databases boek

[drm]

Op vrijdag 12 oktober 2001 14:09 schreef MrX het volgende:
drm, dat betekent dat je per node 1 query moet draaien, plus voor iedere uiteinde-node (dus een node zonder child) nog een query. Dat zou voor een beetje boomstruur al snel aardig wat queries zijn.

Nou is de query op zich wel een eenvoudige query, maar 30 maal 1 simpele query is nog steeds een behoorlijke databasebelasting.

Ik bedoel maar aan te geven dat je de query kan genereren met een recursive functie.

Als de query dan gegenereert is kan je hem doen aan de database. Krijg je alleen een leipe bende aan result terug, maar die kan je vervolgens ook weer recursief afhandelen...

Desnoods zou je de query ook met een JOIN kunnnen doen...

* drm is benieuwd of MrX zijn idee een beetje begrijpt...

[dusty]

Op vrijdag 12 oktober 2001 16:19 schreef TheNarfstyler het volgende:
4de en 5de normaalvorm ? Kun je die eens verduidelijken, staan namelijk niet in mijn databases boek

Database boeken van tegenwoordig ook, duidelijk geen Date....

A Simple Guide to Five Normal Forms in Relational Database Theory

(Deze uitleg is niet geheel compleet..)

[Verwijderd]

Op vrijdag 12 oktober 2001 16:31 schreef drm het volgende:

[..]

Ik bedoel maar aan te geven dat je de query kan genereren met een recursive functie.

Als de query dan gegenereert is kan je hem doen aan de database. Krijg je alleen een leipe bende aan result terug, maar die kan je vervolgens ook weer recursief afhandelen...

Desnoods zou je de query ook met een JOIN kunnnen doen...

* drm is benieuwd of MrX zijn idee een beetje begrijpt...

Uhm .... nee helaas, volgens mij begrijp ik het niet.

Neem de volgende data:
NodeID ParentID Type
1 Null 1
2 1 1
3 1 1
4 2 1

Je wil de hele boom laten zien, dus:
1
|-2
| |-4
|
|-3

Dan doe je volgens mij de volgende query om de start node te vinden:
SELECT NodeID
FROM Struct
WHERE ParentID IS NULL;

Vervolgens het je de node met NodeID = 1 Dan doe je de query om de kinderen te vinden:
SELECT NodeID
FROM Struct
WHERE ParentID=1;

Je vindt de kinderen met NodeID 2 en 3.
Dan doe je de queries om de kinderen van die node te vinden:
SELECT NodeID
FROM Struct
WHERE ParentID=2;

en

SELECT NodeID
FROM Struct
WHERE ParentID=3;

Je vindt alleen bij NodeID 2 een kind, namelijk 4, dus je gaat hiervoor de kinderen vinden.
SELECT NodeID
FROM Struct
WHERE ParentID=4;

Hierbij vindt je ook niets.

Welgeteld heb je dus 5 queries gedaan voor 4 nodes . Meestal zal je de startnode weten te vinden, zodat je 1 query kan besparen (dus mijn eerdere schatting klopt niet), maar 1 query per node blijft veel.

Op vrijdag 12 oktober 2001 16:19 schreef TheNarfstyler het volgende:
4de en 5de normaalvorm ? Kun je die eens verduidelijken, staan namelijk niet in mijn databases boek

http://www.swi.psy.uva.nl/gegevensbanken/gegevensbanken00-01/ppt-slides/h_6.pdf vanaf pagina 17.

Overigens worden er in NV4 en NV5 geen gegevens toegevoegd voor snelheid alleen verdere afhankelijkheden van gegevens geelimineerd.

Op zich is zijn punt wel terecht. Wat hij zegt is dat een volledig genormaliseerde database zonder redundantie, gegenereerde gegevens en afhankelijkheden theoretisch iets heel moois is, maar in de praktijk soms niet werkt.

In die situaties kan je weloverwogen redundantie, afhankelijkheden en gegenereerde gegevens toevoegen, zolang je ook maar zorgt dat de applicatie hier gebaat bij is en programmatisch zorgt dat de integeriteit van de data niet verloren gaat.

Ook hebben sommige afhankelijkheden geen impact op de applicatie en kun je ze soms beter laten zitten. Dekn aan Nederlandse NAW gegevens. Het volledige adres is funktioneel afhankelijk van de postcode en het huisnummer, maar toch worden deze gegevens normaal gesproken gewoon in 1 tabel opgenomen zonder uit te normaliseren.

HTH

[Verwijderd]

Op vrijdag 12 oktober 2001 13:55 schreef MrX het volgende:

[..]
Maar mijn 'mooie' & 'missing in action' oplossing liet het toe een hele boom in 1 query op te halen. Hoewel het wel een zware query zou zijn en er nogal wat overhead by kwam door een 'slim' databasemodel is dat mischien toch wel de moeite waard.

Ik heb nogeens flink door mijn hersenkamer gezocht, maar kon niet meer de hele oplossing verzinnen zoals die in een verloren gegaan topic stond.

Ik kom wel op de oorspronkelijke opzet, maar die heeft te veel beperkingen en is ook wel erg gekunsteld. Een ander had toen een verbetering voorgesteld die het al heel wat beter zou maken, maar die kan ik me niet meer herinneren helaas.

Dus maak je niet al te veel voorstellen ervan. De methode die hier staat uitgelegd is nogsteeds een redelijk efficiente in een recursieve situatie en waarschijnlijk 1 van de beter oplossingen.

Enjoy

[ACM]

* ACM vraagt zich af of zoiets niet op te lossen is met het iets als het 'path' type van postgresql ?

Kwa opslag bespaart je dat iig de overhead van varchars.
Maar met een taal als php zal het wel weinig uitmaken aan de programmeer-technische kant.

Ook heb ik zoiets wel es opgelost met een simpele boom-achtige structuur.
nodeID
parentID

waren de enige velden benodigd in die applicatie. En bij elke page-aanroep werd de "boom gecreerd" (tree=1|2|3|4|16) zodat je wel altijd "terug kon lopen".

Echte boomoverzichten zijn er niet mee mogelijk, niveau overzichten wel. En het gaat redelijk snel (niet gechecked of het met veeeel entries nog steeds snel is)

[Gaafy]

Hmm, langzaam maar zeker komen we bij de oplossing.

Het is overigens vrij frustrerend om te lezen dat er een goede oplossing is, maar niemand die meer weet. Is het niet toegepast in een website, waar we het weer uit kunnen knippen?

Over de oplossing <A HREF="http://gathering.tweakers.net/forum/list_messages/49380/1?limit=50">hier</A>, is er nog een uiteindelijke versie van dat script.

En wat vinden jullie van het script op <A HREF="http://www.phpfreakz.nl/artikelen.php?aid=17">php freakz</A>?

Edit: Hoe maak je links.
Edit2: Ik wil dit stukje script overigens niet gaan gebruiken voor een forum.

[Nielsz]

blaat
blaat.php

zo

[Gaafy]

He, bedankt!