[mySql] boomstructuur

[kvdveer]

Ik heb de volgende tabel:

Tabel (id,parentId,titel,SortOrder,...)

Deze tabel vormt een soort van boomstructuur. voor de Root is parentId 0, voor de leaves is de parentId de id van de parent, die uit dezelfde tabel komt.

Nu moet ik een aantal query's bouwen. Een query om de bomstructuur in HTML weer te geven (hiervoor heb ik o.a. het niveau van de child nodig) en een query waarmee ik het pad naar de root kan tonen.

Is dit überhaupt mogelijk in SQL? (ik weet dat oracle het kan, maar ja, ik moet het met MySql doen)
Zijn er eventueel alternatieve boomstructuren?

[Goodielover]

Het alternatief dat ik eens heb gebruikt gaat uit van redundantie in de opslag van de boomstructuur.

Tabel: Category
Cat_id
Cat_naam

Tabel: Cat_boom
Cat_id
Valt_onder_cat_id
Level_onder

Voeg je een nieuwe categorie toe, dan voeg je in de cat_boom tabel ook alle linken naar hogere niveau's toe door de hogere niveau's van je directe parent te kopiëren.

boompje met 4 enties (even tussen [c o d e] gezet)

code:

         cat1
        /   \
     cat2   cat3
    /   \
    cat4  cat5

de inhoud van de tabel cat_boom wordt dan:

code:

cat1  cat1    0
cat2  cat2    0
cat2  cat1    1
cat3  cat3    0
cat3  cat1    1
cat4  cat4    0
cat4  cat2    1
cat4  cat1    2
cat5  cat5    0
cat5  cat2    1
cat5  cat1    2

Als je alleen niveau 1 neemt heb je de normale boomstructuur.
Als je alles in een bepaalde sub-boom wilt hebben, selecteer je dus op val_onder_cat_id en join je naar category (en eventueel naar item die dan in de category zit)

[kvdveer]

Klinkt interresant, maar is (voor zo ver ik het nu begrijp) niet helemaal de oplossing voor mijn probleem.

Ik wil (altijd startend vanaf root) de volgende boom eenvoudig uit willen kunnen draaien:

code:

Cat1 (p=)
  Cat2 (p=Cat1)
    Cat4 (p=Cat2)
    Cat5 (p=Cat2)
  Cat3 (p=Cat1)

Maar het onderstaande mag ook...

code:

Cat1 (p=)
  Cat2 (p=Cat1)
  Cat3 (p=Cat1)
    Cat4 (p=Cat2)
    Cat5 (p=Cat2)

Die volgorde is belangrijk, dus daarom zit in mijn ontwerp de sortorder er nog bij.


Momenteel zit ik te denken aan het volgende ontwerp:
tabel(id,parent,titel,sortorder,niveau,...) Waarbij niveau redundant is.

Dan kun je die boom weergeven met de volgende query:
SELECT * FROM tabel ORDER BY niveau,sortorder


maar dan kan ik nog niet makkelijk dat pad uitdraaien.

edit:

Daar is dat ontwerp van jou nou net goed voor!...

[Goodielover]

Maar het onderstaande mag ook...

code:

Cat1 (p=)
  Cat2 (p=Cat1)
  Cat3 (p=Cat1)
    Cat4 (p=Cat2)
    Cat5 (p=Cat2)

Dit kan toch heel eenvoudig met mijn structuur

pak de cat_boom tabel met valt_onder_cat_id = cat1 en level_onder is je diepte voor de sortering met daarbinnen nog je eigen sortering

[Grum]

hier hebben ze betere dingen voor bedacht .. ik zoek even een link op

^[edit]
http://www.dbmsmag.com/9603d06.html
http://www.intelligententerprise.com/001020/celko1_1.shtml

zoek op sql trees & celko .. en je zal nog wel meer info kunnen opduiken

[Verwijderd]

Ik had hetzelfde probleem en heb het (ongeveer) zo opgelost :

PHP:

<?
$sql = "SELECT id, name, parent, order FROM table"; // haal alles uit de db.

Array
(
    [1] => Array
        (
            [name] => root
            [id] => 1
            [parent] => 0
            [order] => 1
        )

    [2] => Array
        (
            [name] => Groep 1
            [id] => 2
            [parent] => 1
            [order] => 1
        )
    [3] => Array
        (
            [name] => Groep 2 (Subgroep van groep 1)
            [id] => 3
            [parent] => 2
            [order] => 1
        )
    [4] => Array
        (
            [name] => Groep 3 (Subgroep van groep 1)
            [id] => 4
            [parent] => 2
            [order] => 2
        )
)
foreach($treeArr as $key => $val) {
          echo $key." ".$val[name]." ".$val[id]." ".$val[parent];
        echo $treeArr[ $val[parent] ][name]; // Bevat de naam van de parent van het getoonde object
      }
?>

Met een recursieve functie kan je dan de parent of child van elk object in je array opzoeken en op basis daarvan een nieuw array opbouwen.
Beetje extra werk, maar ik kon zo snel ook niet een efficiënte oplossing vinden met MySQL.

[kvdveer]

Die celco is idd een mooi alternatief!
Eenvoudig op te bouwen, en toch hanteerbaar.
Mocht iemand er interresse in hebben, kan ik hier het principe nog wel even uitleggen. (gewoon vragen in deze thread)

[Grum]

het leuke is dat der maar weinig over bekend is ...
ECHT weinig mensen weten het ...
maar het is de meest efficient manier om een tree op te slaan in een db

[kvdveer]

Wat ik alleen niet helemaal snap... Waarom doen ze zo moeilijk om er een item aan toe te voegen?

Je kan toch met 3 queries dat voor elkaar krijgen?

edit:
code verplaatst naar de post hieronder om het overzichtelijk te houden

...

Ze hebben daar kilometers code staan om dat te doen...
Het is natuurlijk wel netter om het bovenstaande in een transaction te doen...

[kvdveer]

Ik heb een paar minutjes vrij gevonden.

Van iedere node hou jee een variabele rechts en links aan.
Rechts is altijd minimaal 1 groter dan links. De var links van braches is altijd minimaal 1 groter dan de branch van hun parent, en de var rechts is altijd minimaal 1 kleiner dan die van hun parent.
Het volgende verband ontstaat:
Voor iedere node:
node.links < node.rechts
(node.rechts - node.links) / 2 = aantal kinderen.

Voor alle niet root nodes
node.links > parent.links
node.rechts < parent.rechts

Een boom zou er dan als volgt uit kunnen zien: (genoteerd als NODE(links,rechts)

code:

    A(1,10)
     /   \
   B(2,7)   C(8,9)
    /  \ 
D(3,4) E(5,6)

een recursieve pseudocode functie:

code:

function BuildCelco(root,left) returns integer ; aantal
{
  root.left = left;
  a = left;
  for each root.children as child {
    a = BuildCelco(child,++a);
  }
  root.right=++a; // bugfix... ;)
  return ++a;
}

Om de boom in preorder uit te lezen:
preorder betekent parent eerst, dan kinderen.

code:

SELECT * 
FROM tabel
ORDER BY lft;

Om de boom in preorder uit te lezen:
Zie boven, maar dan inclusief niveau

code:

SELECT t1.*, count(t2.id) as niveau
FROM tabel as t1 
  LEFT JOIN tabel as t2
  ON ( t1.lft > t2.lft AND t1.rgt < t2.rgt)
ORDER BY lft
GROUP BY t1.id;

Om de boom in postorder uit te lezen:
postorder betekent kinderen eerst, dan parent.

code:

SELECT * 
FROM tabel
ORDER BY rgt DESC;

Om alle parents te krijgen van een object C:
De objecten zijn gesorteerd van Root naar C

code:

SELECT *
FROM tabel
WHERE lft < $Cleft AND rgt > $Cright
ORDER BY left;

om een item toe te voegen tussen B en C (onder A)

code:

UPDATE tabel
SET lft = lft+1
WHERE lft > $Bright

UPDATE tabel
SET rgt = rgt+1
WHERE rgt > $Bright

INSERT INTO tabel (id,lft,right
VALUES ('X',$Bright+1,$Bright+2)

om een item toe te voegen onder C:

code:

UPDATE tabel
SET lft = lft+1
WHERE lft > $Cleft

UPDATE tabel
SET rgt = rgt+1
WHERE rgt > $Cleft

INSERT INTO tabel (id,lft,right
VALUES ('X',$Cleft+1,$Cleft+2)

[Verwijderd]

om een item toe te voegen onder C:

code:

...
INSERT INTO tabel (id,lft,right
VALUES ('X',$Cleft+1,$Cleft+2)

is er hier niet vergeten dat als je een element toevoegd (in dit voorbeeld aan C) dat lft van het root element er 2 bij moet krijgen i.p.v. 1 zoals hier gedaan wordt?

[Verwijderd]

Ik ben zelf bezig met een script waar ik de celco theorie gebruik. Omdat ik mysql gebruik heb ik de hierboven update querys gebruikt om elements toe te voegen. De query's kloppen niet helemaal, ik ben nu bezig met het bekijken van de queries en ze aan te passen.

Ik zal ze posten zodra ik hiermee klaar ben (kan 2 dagen duren, heb ook nog andere dingen te doen )

[kvdveer]

Ik zie nu dat er nog een bug zit in mijn code:

Op donderdag 03 januari 2002 15:03 schreef kvdveer het volgende:

om een item toe te voegen tussen B en C (onder A)

code:

UPDATE tabel
SET lft = lft+2 ; bugfix
WHERE lft > $Bright

UPDATE tabel
SET rgt = rgt+2 ; bugfix
WHERE rgt > $Bright

INSERT INTO tabel (id,lft,right
VALUES ('X',$Bright+1,$Bright+2)

om een item toe te voegen onder C:

code:

UPDATE tabel
SET lft = lft+2 ; bugfix
WHERE lft > $Cleft

UPDATE tabel
SET rgt = rgt+2 ; bugfix
WHERE rgt > $Cleft

INSERT INTO tabel (id,lft,right
VALUES ('X',$Cleft+1,$Cleft+2)

[Verwijderd]

Op donderdag 03 januari 2002 14:07 schreef Grum_ het volgende:
het leuke is dat der maar weinig over bekend is ...
ECHT weinig mensen weten het ...
maar het is de meest efficient manier om een tree op te slaan in een db

Kan iemand dit bevestigen? Ik heb ooit gehoord dat RDBMS juist niet geschikt zijn om trees in op te slaan

[kvdveer]

Op dinsdag 05 februari 2002 13:51 schreef Zef het volgende:

[..]

Kan iemand dit bevestigen? Ik heb ooit gehoord dat RDBMS juist niet geschikt zijn om trees in op te slaan

Inderdaad. Een RDBMS* is niet geschikt om trees in op te slaan. vandaar dat je de tree eerst naar iets lineairs moet vertalen... Dat is waar dit topic over gaat.

In oracle zijn er trouwens wel manieren om een tree op te slaan.

* relational database management system.

[Soultaker]

Op donderdag 03 januari 2002 14:07 schreef Grum_ het volgende:
het leuke is dat der maar weinig over bekend is ...
ECHT weinig mensen weten het ...
maar het is de meest efficient manier om een tree op te slaan in een db

Het is inderdaad een leuke datastructuur (niet alleen voor databases trouwens), maar natuurlijk niet voor elk doel. Het invoegen, verwijderen en verplaatsen van knopen in de boom kost hier O(N) bewerkingen (waarbij N het aantal knopen in de boom is), terwijl dat in de klassieke representatie slechts O(1) is. In een grote boomstructuur kan dit soms niet wenselijk zijn. Bovendien heeft de klassieke methode een referentiekolom minder nodig.

Het hangt er dus (zoals altijd) vanaf wat precies de toepassing van de database is. Voor een relatief diepe boom, waarin weinig gegevens gewijzigd worden, is dit een mooie datastructuur. In een brede boom die vaker bijgewerkt wordt dan uitgelezen, is de klassieke structuur aan te raden.

[Verwijderd]

Op dinsdag 05 februari 2002 15:03 schreef kvdveer het volgende:
[..]
Inderdaad. Een RDBMS* is niet geschikt om trees in op te slaan. vandaar dat je de tree eerst naar iets lineairs moet vertalen... Dat is waar dit topic over gaat.

Eh, ja begrijp ik Ik bedoelde qua performance.

[creative8500]

Kan dat niet zo?

code:

CREATE TABLE test (
  id int(10) NOT NULL auto_increment,
  root_id int(10) NOT NULL default '0',
  inhoud text NOT NULL,
  PRIMARY KEY  (id),
  UNIQUE KEY id (id)
)

en dan als query

code:

SELECT * FROM 'test' ORDER BY root_id ASC, id ASC

Of bedoellu dat niet?

[Verwijderd]

Op donderdag 03 januari 2002 15:03 schreef kvdveer het volgende:
[knip]

Mijn dank is groot! Dit kan ik wel gebruiken. Heb je toch niet het id dat je het voor lul hier neer zet .