[SQL] Recursief mogelijk?

[xces]

Ik heb een tabel met de volgende definitie:
* taakid
* parenttaakid
* actief
* naam
* omschrijving

Het idee is dat je een taak kunt hebben, en een taak kan aan/onder een andere taak hangen. Je kunt hier dus heel diep en heel ver mee gaan. Op dit moment heb ik het 4 levels diep. Mijn vraag is, of het mogelijk is om een query los te laten op deze tabel, die dit doet:

Selecteer alle taken met bijbehorende subtaken (en daarbijbehorende taken, etc. etc.), ieder level gesorteerd op namen van taken op dat level..

p.s. hoofdtaken hebben als parenttaakid "-1"

Volgens mij is zoiets niet mogelijk, toch? Het zou me een hoop query's schelen namelijk

p.p.s. Als het wel mogelijk is, kan iemand me dan een schop in de goede richting geven? Ik heb het werkend met een hoop queries, maar wil het graag wat optimaliseren door het wat technischer te doen, en er tegelijkertijd wat van te leren...

[ Voor 27% gewijzigd door xces op 05-01-2007 10:11 . Reden: onderste disclaimer toegevoegd :[ ]

[Verwijderd]

Is wel mogelijk, gewoon de tabel op zichzelf joinen.... maar ben nooit zo goed geweest in join's dus hoe het precies zit weet ik zo niet
Alhoewel, ik denk dat je dan wel een view nodig hebt.... waar hebben we het hierover, MySql ondersteunt volgens mij (nog) geen views

[ Voor 32% gewijzigd door Verwijderd op 05-01-2007 10:10 ]

[Creepy]

Totaal afhankelijk van welke database je gebruikt. Zo heeft Oracle een "connect by" functie om zo parent / child relaties te kunnen gebruiken. Welke database gebruikt je? Ik gok op een MySQL. Ik geloof niet dat MySQL hier standaard zaken voor heeft.

Edit: een tabel met zichzelf joinen kan ook, maar dan krijg je een join conditie per diepte.

[ Voor 16% gewijzigd door Creepy op 05-01-2007 10:12 ]

[xces]

Het is inderdaad MySQL (5 overigens)

[Verwijderd]

In SQL is het niet mogelijk (a.f.a.i.k.) met deze structuur maar er zijn wel mogelijkheden als je de structuur aan past. Meer hierover kun je lezen in dit topic waar een mogelijke oplossing wordt gegeven (met zijn voor- en nadelen).

[MBV]

Voor performance zou je dus het meest-voorkomende aantal niveau's diep kunnen joinen, en daarna verder als dat nodig is. Scheelt je een hele berg queries

[Verwijderd]

Creepy schreef op vrijdag 05 januari 2007 @ 10:11:
...
Edit: een tabel met zichzelf joinen kan ook, maar dan krijg je een join conditie per diepte.

Niet als je selecteerd uit een view, die zichzelf dus joint.

[apa]

Hoe zou je willen dat het resultaat eruit ziet?
Kan je een voorbeeld geven van de inhoud van de tabel en hoe de uiteindelijke recordset eruit moet zien?

[xces]

@djingelz; ik zal dit eens op mijn gemak gaan bekijken. Aangezien ik niet weet of dit mijn probleem gaat oplossen doe ik toch een poging om ook in dit topic tot een oplossing te komen, vandaar antwoord op de vraag van "Apa".

Gedeelte van huidige structuur:
klant
klant/add
klant/edit
klant/delete
klant/bestelling
klant/bestelling/add
klant/bestelling/edit
klant/bestelling/delete
manager/bedrijf
manager/bedrijf/add
manager/bedrijf/edit
manager/bedrijf/delete
manager/bedrijf/contactpersoon
manager/bedrijf/contactpersoon/add
manager/bedrijf/contactpersoon/edit
manager/bedrijf/contactpersoon/delete

Dit zijn dus taken, de slashes staan erbij om de indeling wat duidelijker te maken, maar het komt erop neer dat ik het via Rollen mogelijk wil maken dat een klant bijvoorbeeld wel toegevoegd en bewerkt kan worden, maar niet verwijderd kan worden als men die taak niet heeft. Zoals je ziet kan het best diep gaan.

[ Voor 16% gewijzigd door xces op 05-01-2007 11:36 ]

[Scarfish]

Is in dit geval bij jou een manager, bedrijf en contactpersoon ook een taak?

Dus het volgende:

Taak1: manager
Taak2: bedrijf
Taak3: contactpersoon
Taak4: edit

Taak1 --- Taak2 --- Taak3 --- Taak4

[MisterData]

Je zou het Celko-model kunnen gebruiken (er was ook een mooie naam voor, ben 'em even kwijt). Iets complexer, maar daarmee kun je met één simpele query alles netjes ophalen en sorteren

[MTWZZ]

Je kunt ook een function maken die de childs van een taak opzoekt en dan de functie recursief aanroepen

Ik heb even wat getest (op MSSQL welliswaar) met een tijdelijke tabel en een WHILE loopje.
Men neme de tabel test:

code:

iTestID     vCode iParentTestID 
----------- ----- ------------- 
1           A     NULL
2           B     1
3           C     2
4           D     3
5           E     4
6           CC    2

en dit script:

SQL:

-- Maak een tijdelijke tabel met alleen het ID
CREATE TABLE #tmp (
    iTestID int NOT NULL
)

-- Countertje
DECLARE @iCounter AS int

-- Voeg de rijen toe die als parent ID 3 hebben
INSERT INTO #tmp
SELECT  iTestID
FROM    Test
WHERE   iParentTestID = 3

-- Rowcount opslaan
SELECT @iCounter = @@ROWCOUNT

WHILE @iCounter > 0
BEGIN
        -- Voeg de rijen toe die een parent ID hebben die al in #tmp staat
        -- maar waarvan de rij zelf nog niet in #tmp voorkomt (NOT EXISTS)
    INSERT INTO #tmp
    SELECT T.iTestID
    FROM #tmp TMP
    INNER JOIN Test T ON (T.iParentTestID = TMP.iTestID
        AND
        NOT EXISTS(SELECT iTestID FROM #tmp WHERE
                #tmp.iTestID = T.iTestID)
        )
    
        -- rowcount weer opslaan voor de loop
    SELECT @iCounter = @@ROWCOUNT
END

-- #tmp bevat nu alle iTestID's die aan elkaar gerelateerd zijn, door Test met #tmp te joinen
-- krijg je alle betreffende records.
SELECT  *
FROM    #tmp

Als resultaat (tabel #tmp) krijg je dan:

code:

iTestID     
----------- 
4
5

[ Voor 89% gewijzigd door MTWZZ op 05-01-2007 12:29 ]

[xces]

@Scarfish; inderdaad. Indien je de taak "Manager" hebt, mag je een overzicht zien van alle bedrijven die onder jou vallen.

@MTWZZ, in die thread die djingelz noemde, stellen ze dat ook voor, en hetzelfde doen ze in de conclusie van het Celko model.

De conclusie is eigenlijk; "Haal alle taken in 1x op, en doe dmv associative arrays er een tree van maken." Dit schijnt minder performance hit te geven dan alles puur in SQL te doen.. p.s. voor zover de recursieve functies in alle artikelen eruit zagen, zo had ik het ook al. Ik denk dat ik het hele zaakje maar met 1 query binnenhaal, om het vervolgens in PHP op te splitsen/te bouwen.

[ Voor 18% gewijzigd door xces op 05-01-2007 12:30 ]

[gorgi_19]

@MTWZZ : Je kan ipb een temptable ook een tablevar gebruiken, scheelt weer een stuk performance

[MBV]

Ik zie trouwens 1 ding over het hoofd: stel, je doet een select * from tabel, en gaat dat zelf in PHP 'joinen'. Ben je dan niet al veel sneller?

PHP:

//pseudo-php
$results = execute("SELECT parentid, id, name FROM tasks ORDER BY parentid");
$return = $parents = array();
foreach($results as $row)
{
  $parents[$row['parent']][$row['id'] = $row['name'];
}
//$parents[-1] bevat nu een array met alles uit de eerste laag

parse_tree($parents, -1)

function parse_tree($parents, $nodeid)
{
  $children = array();
  foreach ($parents[$nodeid] as $childid => $name)
  {
    $children[$childid] = parse_tree($parents, $childid);
  }
  return array($nodeid => $children);
}

Niet getest natuurlijk, en je moet nog iets met die naam doen, maar dit zou je basis kunnen zijn

[edit]* MBV moet vaker op F5 drukken, en niet die hele k*t-functie denken te verzinnen [/ME]

[ Voor 12% gewijzigd door MBV op 05-01-2007 12:44 ]

[MTWZZ]

@gorgi_19
I know, ik heb het ook maar even snel in elkaar gehackt hoor

@MBV
Tsja dat is denk ik iets om te testen maar ik denk dat je aan de SQL kant wel wat winst boekt aangezien je niet alle data heen en weer hoeft te slepen

[apa]

Ik ben zelf niet zo goed thuis in MySQL, dus zal ik hier een voorbeeld geven die je zou kunnen gebruiken om dit te doen op SQL Server. Ik vermoed dat het vrij makkelijk moet zijn om dit om te zetten naar MySQL-code?!

Neem aan dat de structuur op de DB staat opgeslagen in een tabel "Structure":

code:

taakid  parenttaakid    naam
------- --------------- ---------------
1       NULL            klant
2       1               add
3       1               edit
4       1               delete
5       1               bestelling
6       5               add
7       5               edit
8       5               delete
9       NULL            manager
10      9               bedrijf
11      10              add
12      10              edit
13      10              delete
14      10              contactpersoon
15      14              add
16      14              edit
17      14              delete

Deze inhoud is voldoende om de hiërarchie voor te stellen die je aangehaald hebt.

De query in SQL Server zou er dan zo kunnen uitzien:

SQL:

DECLARE @intLevel       int
DECLARE @intRowsAdded   int

CREATE TABLE #tmpStructure      (
                                intLevel        int,
                                intTaakID       int,
                                strPath         varchar(255)
                                )

SET @intLevel = 0

INSERT INTO #tmpStructure       (
                                intLevel,
                                intTaakID,
                                strPath
                                )
        SELECT  intLevel        = @intLevel,
                intTaakID       = taakid,
                strPath         = naam
        FROM    Structure
        WHERE   parenttaakid IS NULL

SET @intRowsAdded = @@ROWCOUNT

WHILE @intRowsAdded > 0
BEGIN
        SET @intLevel = @intLevel + 1

        INSERT INTO #tmpStructure       (
                                        intLevel,
                                        intTaakID,
                                        strPath
                                        )
                SELECT  intLevel        = @intLevel,
                        intTaakID       = Structure.taakid,
                        strPath         = #tmpStructure.strPath + '/' + Structure.naam
                FROM    #tmpStructure
                        INNER JOIN Structure ON Structure.parenttaakid = #tmpStructure.intTaakID
                WHERE   #tmpStructure.intLevel = @intLevel - 1

        SET @intRowsAdded = @@ROWCOUNT
END

SELECT  strPath
FROM    #tmpStructure WITH (NOLOCK)

DROP TABLE #tmpStructure

Het resultaat van deze query is exact hetgeen je hierboven hebt getoond...

Dit is vrij performant omdat je slechts 1 maal door de WHILE loopt per niveau in je hïerarchie (min 1 voor het eerste niveau wat buiten de WHILE staat). In jouw voorbeeld loop je er dus 3 keer doorheen.

Een voordeel van deze manier van werken is bovendien dat je de hele query makkelijk in een stored procedure kan proppen waardoor je met 1 enkele call naar je database alle nodige data terugkrijgt.

Hopelijk heb je hier wat aan...

[ Voor 4% gewijzigd door apa op 05-01-2007 13:45 ]

[MBV]

een While in een SELECT wordt niet ondersteund door MySQL volgens mij: http://dev.mysql.com/doc/refman/5.1/en/select.html

Misschien in een stored procedure, maar ik gok van niet.

[ Voor 19% gewijzigd door MBV op 05-01-2007 14:23 ]

[apa]

MBV schreef op vrijdag 05 januari 2007 @ 14:22:
een While in een SELECT wordt niet ondersteund door MySQL volgens mij: http://dev.mysql.com/doc/refman/5.1/en/select.html

Misschien in een stored procedure, maar ik gok van niet.

De WHILE staat niet in de SELECT hoor

MySQL lijkt me WHILE-statements trouwens wel te ondersteunen. Maar zoals ik al zei: ik heb helemaal geen ervaring met MySQL dus weet ik ook niet sinds welke versie en of je het noodzakelijk in een stored procedure moet gebruiken (dat laatste lijkt me trouwens wel aannemelijk).

[MTWZZ]

@ape
Ik ga vanmiddag wel even een poging wagen om dit op MySQL te laten werken. Snel testje wilde niet lukken aangezien MySQL me geen variabele laat declareren

[xces]

MTWZZ, is het al gelukt

[The Eagle]

Ik zie dat je met iets van beveiliging bezig bent
Vraag je eens af of je (blijf je ook een beetje DB-generiek) dan niet gewoon wat meer tabellen wilt gebruiken. Denk bijv aan:
USER
ROLE
PERMISSIONS

Waarbij PERMISSIONS de diverse rechten tot schermen bevat.
ROLE bevat permissions (juist, verwijzing naar), USER bevat de gebruikersnamen. Tot slot heb je dan ook nog een tabel ROLEUSER waarbij je users en rollen koppelt. Zo ben je een stuk flexibeler

[xces]

ehmz, niet om het een of anders, maar zo doe ik het al;
1 contactpersoon kan 1 of meerdere rollen hebben, en 1 rol kan 1 of meerdere "permissions" hebben. Dit is alleen niet het probleem waar het hier om gaat, dus ik ga er even niet verder op in.

[MTWZZ]

xces schreef op maandag 08 januari 2007 @ 11:14:
MTWZZ, is het al gelukt

Nee helaas nog geen tijd gehad, ik zal een poging doen vannavond wat in elkaar te hacken

[xces]

Oke, thanx. Zoals ik het nu heb is het misschien al een stuk in de richting. Ik heb er nu even voor gekozen om de array (lees: tree) in PHP op te bouwen en wel als volgt.

Even de structuur van de tabel (vereenvoudigd)
taakid
parenttaakid
naam

Er zijn ook nog 2 velden; omschrijving en actief, maar deze hebben voor de uitleg even geen functie, vandaar achterwege gelaten.

Stap 1:
Allereerst haal ik alle records op, gesorteerd op parenttaakid. Ik kan ook wel iedere keer een nieuwe query op de database uitvoeren, maar om de SQL server te ontlasten doe ik het dus opbouwen in PHP. Ik weet niet of dit performance gezien trager/sneller is, maar het lijkt me beter voor de SQL server.

Stap 2:
Vervolgens loop ik door de gevonden items heen; met deze functie:

PHP:

        /**
         * Bouwt een recursieve array op van alle taken voor dit bedrijf.
         */
        public function bouwTree($arrTaken, $intParentID) {
            $arrFound = array();
            foreach ($arrTaken as $intTaakID => $objTaak) {
                //
                // Enkel verwerken, indien het parentID klopt.
                if ($objTaak->getParentTaakID() == $intParentID) {
                    //
                    // Kindjes opzoeken
                    $arrTemp = array();
                    $arrTemp['parent'] = $objTaak->getNaam();
                    $arrTemp['childs'] = $this->bouwTree($arrTaken, $objTaak->getTaakID());

                    //
                    // Toevoegen
                    $arrFound[] = $arrTemp;
                }
            }
            return $arrFound;
        }

Zoals je ziet een vrij standaard recursieve PHP functie. Doordat er bij het ophalen van de taken gesorteerd is op "parenttaakid ASC" kan deze functie goedgaan. $objTaak is een klasse. Een array die er ongeveer zo uitziet is het resultaat.

code:

Array(
    [0] => Array(
            [parent] => overzichtFactuur
            [childs] => Array(
                    [0] => Array(
                            [parent] => overzichtFactuurBetalen
                            [childs] => Array()
                        )
                    [1] => Array(
                            [parent] => overzichtFactuurDownload
                            [childs] => Array()
                        )
                    [2] => Array(
                            [parent] => overzichtFactuurView
                            [childs] => Array()
                        )
                )
        )
    [1] => Array(
            [parent] => overzichtBestelling
            [childs] => Array(
                    [0] => Array(
                            [parent] => overzichtBestellingCancel
                            [childs] => Array()
                        )
                )
        )
)

etc.

Waarschijnlijk moet ik het nog wel kunnen versimpelen, door niet iedere keer de hele array met gevonden taken door te lopen, maar hiervoor zou ik graag wat tips krijgen.

[MBV]

ehm, gewoon je array ergens opslaan? Sessie ofzo? Zo doe ik dat vaak met dure operaties

[MTWZZ]

^^ Dat sowiezo.
Het voordeel om dit in de database server te doen is dat je niet de data hoeft over te pompen naar de clientside (PHP). Je hebt namelijk een hoeveelheid data waar je wel doorheen loopt (en dus ophaalt) maar waar je niets mee doet.

[xces]

Ik doe het momenteel wel allemaal gebruiken, maar ik sla het inderdaad ook op.

[markg85]

ik probeer op dit moment iets vergelijkbaars..

Ik probeer het zo te doen:

1. fetch van cat_id, cat_parent en cat_name alle resultaten en prop het in een array.
2. filter de array en gooi er 4 arrays uit:
- - array 1 = alle categorieen in 1 array (dus waar cat_parent gelijk is aan 0)
- - array 2 = zelfde als 1 alleen dan waar cat_parent ongelijk is aan 0
- - array 3 = een kleine array waar eigenlijk alleen alle cetegory id`s in zitten can de hoofd categorieen (waar cat_parent gelijk is aan 0)
- - array 4 = zelfde als 3 alleen dan waar cat_patent ongelijk is aan 0

Ik heb er allen 1 probleem mee... ik krijg het nog maar niet goed aan elkaar gekoppeld
dus iemand een idee wat ook handig zou zijn als je via mysql een array terug kan krijgen die al eigenlijk helemaal klaar is en waar je alleen nog maar met een foreach doorheen hoeft te lopen.. maarja dan heb je dus weer een recursive query en dat is nou niet echt mysql`s sterke kant. en niet handig voor de performance.

dus code samples zijn welkom

[MBV]

ik heb hierboven een helemaal uitgewerkt code-sample staan, daar moet je toch wel wat mee kunnen Op jouw manier ga je 'met de hand' de recursie doen, en kom je klem te zitten bij elke laag die je uitbreid. Bomen maken en doorlopen moet nou eenmaal recursief _{(behalve als je 1 element eruit wilt opvragen )}

[markg85]

MBV schreef op dinsdag 09 januari 2007 @ 15:58:
ik heb hierboven een helemaal uitgewerkt code-sample staan, daar moet je toch wel wat mee kunnen Op jouw manier ga je 'met de hand' de recursie doen, en kom je klem te zitten bij elke laag die je uitbreid. Bomen maken en doorlopen moet nou eenmaal recursief _{(behalve als je 1 element eruit wilt opvragen )}

ach ja recursion is ook net nieuw voor mij
ennuh.. blijkbaar heb ik over jouw voorbeeld heengekeken..

Thanx!

edit:://
hmm.. er zitten wat foutjes in je parse_tree function....
ik probeer ze eruit te helen, maar zou het ook wel leuk vinden als jij m misschien nog zou kunnen verbeteren. als ik m goed heb post ik m hier.

[ Voor 16% gewijzigd door markg85 op 09-01-2007 20:05 ]

[MBV]

Wat voor foutjes? Hij was nog niet helemaal af, zoals je eronder kon zien. Het lijkt me wel een goede basis. En misschien is bouwTree van xces wel iets, die is al wel af

[xces]

Zit ik meteen met mijn volgende idee/probleem. Een passport achtige website bouwen. D.w.z. 1 subdomein die alle authorisaties voor mijn websites kunnen afhandelen.

[D-Raven]

Geen idee of dit de meest veilige oplossing is. Maar je zou een authenticatie database kunnen gebruiken waarin de logins worden bijgehouden. En dat alle sites in het subdomein daar gebruik van maken.
Dan heb je dus een centrale authenticatie punt in je gehele domein.

[MTWZZ]

xces schreef op woensdag 10 januari 2007 @ 09:16:
Zit ik meteen met mijn volgende idee/probleem. Een passport achtige website bouwen. D.w.z. 1 subdomein die alle authorisaties voor mijn websites kunnen afhandelen.

Ik zou zeggen UTFS
Dit is al een flink aantal keren voorbij gekomen met verschillende oplossingen

[xces]

Ja dat dacht ik al, vandaar dat ik er zelf ook eerst onderzoek naar ga doen.

p.s. sleutelwoorden voor me waarop ik moet zoeken?

[ Voor 26% gewijzigd door xces op 10-01-2007 11:26 ]

[MTWZZ]

In ieder geval hier (wikipedia) even lezen over SSO en zoeken op: Single sign-on OR sso

[markg85]

hier nog mijn parse_tree() versie

PHP:

        function parse_tree($parents, $nodeid=0, $level=0)
        {
            foreach ($parents[$nodeid] as $parent_id => $parent_name)
            {
                $this->drop_down_array[] = array('cat_id' => $parent_id, 'stripes' => $level, 'cat_name' => $parent_name);
                if (@is_array($parents[$parent_id]))
                {
                    $this->parse_tree($parents, $parent_id, $level + 1);
                }
            }
        }