[PHP] Recursie door onbekend aantal dochters in database

[Verwijderd]

Hoi,

Ik heb een tabel, met daarin folders, die ieder gelinkt zijn aan een parent. Table layout:

folder_id (INT(10))
folder_name (VARCHAR(50))
folder_parent (INT(10))

Dus iedere folder met een uniek id heeft een aangewezen parent, waarbij folder_parent 0 'Home' is.
Du bijvoorbeeld de volgende folders:

folder_id	folder_name	folder_parent
1	Folder A	0
2	Folder B	0
3	Folder AA	1
4	Folder AB	1
5	Folder AAA	3

Dit zijn dus twee folders onder de Home, met twee dochter-folders in folder A, waarvan en één weer een dochter heeft.

Nu is van te voren niet te berekenen hoeveel mappen er in de (MySQL) database onder de andere mappen liggen (de structuur is voor de gebruikers vrij uitbreidbaar), maar als ik een map wil deleten moet ik ook uitvogelen hoe ik alle onderliggende mappen delete...is hier een handige manier voor?

Ik zoek dus iets om (theoretisch oneindig) uit te zoeken welke structuur er onder een bepaalde map ligt, om dan de hele structuur te kunnen deleten als een hogere moedermap wordt verwijderd.

Ik hoop dat dit enigszins duidelijk is, ik staar me er al even op dood.....Help?!

EDIT: ik heb al een aantal queries genest, en dat werkt, maar ik kan er wel 100 nesten, en wat als de gebruiker 101 niveaus heeft gemaakt? dan krijg ik 'orphaned folders' in de tabel. Ik hoop dus dat er een methode is om oneindig te nesten tot op het diepste niveau, en dan 'van beneden af' alles weg te gooien, tot aan de moederfolder die wordt verwijderd. Am I making sense here?

Thx,
Mark.

[ Voor 14% gewijzigd door Verwijderd op 01-03-2005 01:31 ]

[Lukse]

Mij lijkt de makkelijkste manier een recursieve functie in php.

[Blorgg]

Opvragen welke subfolders er bij de parent horen die je wilt verwijderen. Daarna voor elke sub- en sub- en sub- enz. folder de subfolders opvragen en alles netjes in een array laten zetten. Vervolgens kan je aan het einde netjes alle waarden uit je array halen en de hele zwik met een query verwijderen.

Met een beetje pseudo code krijg je dan iets als:

PHP:

function get_subfolders($foldernaam)
    {
    global $subfolderarray;

    $query =    "select de subfolders van $foldernaam,
                of anders gezegd: elke map die als parent $foldernaam heeft";
    $result = mysql_query($query) 
        or die(mysql_error());

    while($data = mysql_fetch_array($result)) 
        {
        // je array verder vullen $subfolderarray[] = $data['iets'];
        // voor elke waarde get_subfolders($data['iets']);
        }
    }

Let wel, dit is niet erg netjes aangezien je voor elke subfolder een query gaat krijgen.

[ Voor 12% gewijzigd door Blorgg op 01-03-2005 01:59 ]

[Gwaihir]

Blorgg schreef op dinsdag 01 maart 2005 @ 01:53:
Let wel, dit is niet erg netjes aangezien je voor elke subfolder een query gaat krijgen.

Hoe zou je dat willen vermijden dan? Het enige alternatief wat ik kan verzinnen is alle data in je PHP script laden en dan analyseren, maar dat lijkt me veel langzamer / moeizamer / minder elegant.

Hmm.. misschien kun je wel alle vragen van één trede de diepte in clusteren tot één query. Dus: ik delete folder A -> 1) zoek daar de subfolders van op, 2) zoek alle subfolders van die subfolders op, en zo verder.

[prototype]

Recursie is vrij eenvoudig, als je een vaste stappenplan volgt. Bij ons op school is het zo uitgelegd dat men je aanraadt om vanaf de laatste iteratie terug te berenderen; je zult dus vanaf de diepste folder terug moeten zien te redeneren naar de hoogste folder. Als je dit eenmaal goed verwoord hebt dan kun je het omzetten naar code. Ik verveelde me zojuist en heb daarom even snel een recursie scriptje gemaakt, adhv een id en een parentid; het maakt gebruik van een paar onderdelen van m'n eigen classenlibrary, als je deze eventueel ook wilt moet je maar even gillen. Ze zijn niet noodzakelijk iig voor het begrijpen van de code.
Mogelijkerwijs zal het niet helemaal werken maar voor zover ik het snel heb getest schijnt het te werken. Bovendien heb 'k er geen zin meer in Ik hoop iig dat het je helpt. ALs je nog vragen hebt mbt het algoritme, vuur maar raak, maar de code spreekt vrijwel voor zich dunkt me zo.
Even kort het algoritme.
Een methode A die een id vereist, selecteert alle folders met een bepaalde gemeenschappelijke parentID met de waarde id. Vervolgens wordt per folder gekeken of deze eventueel subfolders heeft(kinderen dus). Zo ja, dan wordt de procedure weer herhaald (methode A wordt weer aangeroepen dit keer met de id's van de huidige subfolders als parentId's), net zolang totdat een folder geen kinderen meer heeft. Als dat het geval is roept de methode niet langer zichzelf meer aan. Je kunt dit beschouwen dus als de guard van de recursie.

PHP:

<?php

    require_once('class.FactoryDatabase.php');

    /**
     * Boring folder recursion test.
     *
     * WARNING: Really louzy documentation and rancid code for your viewing pleasures ;)
     *
     * @author Ninh Bui <buixn at cs dot utwente dot nl>
     * @version 1337
     */
    class TestFolderRecursion
    {
        /** Has-a database */
        private $db;
        
        /**
         * Constructor for property initialization.
         */
        public function __construct()
        {
            $this->initializeDatabase();
            
        }
        
        /**
         * Initializes the database.
         */
        public function initializeDatabase()
        {
            $this->db = FactoryDatabase::create('MySql');
            $this->db->setHost('localhost');
            $this->db->setPort(3306);
            $this->db->setUsername('root');
            $this->db->setPassword('melp!');
            $this->db->setDbName('recursion');
            $this->db->pconnect();
        }
        
        
        /**
         * Returns a multidimensional array containing the specified parent and it's children,
         * it's children's children etc...
         *
         * @param int $id The parent id.
         * @require $id >= 0
         */
        public function getChildrenByParentId($id)
        {
            $data = $this->db->select('SELECT * FROM `folders` WHERE  pid=' . $id);

            if ($data)
            {
                $children = array();
                for ($i=0; $i < count($data); $i++)
                {
                    $pid = $data[$i]['id'];
                    if ($this->hasChildren($pid))
                    {
                        $children[$i] = $data[$i];
                        $children[$i][] = $this->getChildrenByParentId($pid);
                    }
                    else
                    {
                        $children[$i] = $data[$i];
                    }
                }
                return $children;
            }
        }
        
        /**
         * Returns a boolean value corresponding to the question if a given parent id
         * has children.
         */
        public function hasChildren($id)
        {
            $data = $this->db->select('SELECT * FROM `folders` WHERE pid='. $id);
            $result = false;
            if ($data)
            {
                $result = true;
            }
            return $result;
        }

    }
    
    
    //TESTTIME!! w00t ;)
    $tfr  = new TestFolderRecursion();
    $tree = $tfr->getChildrenByParentId(0);
    
    print_r($tree);
?>

[ Voor 23% gewijzigd door prototype op 01-03-2005 04:01 ]

[prototype]

Het resultaat:

code:

Array
(
    [0] => Array
        (
            [0] => 1
            [id] => 1
            [1] => 0
            [pid] => 0
            [2] => Folder A
            [name] => Folder A
            [3] => Array
                (
                    [0] => Array
                        (
                            [0] => 4
                            [id] => 4
                            [1] => 1
                            [pid] => 1
                            [2] => Folder AA
                            [name] => Folder AA
                            [3] => Array
                                (
                                    [0] => Array
                                        (
                                            [0] => 6
                                            [id] => 6
                                            [1] => 4
                                            [pid] => 4
                                            [2] => Folder AAA
                                            [name] => Folder AAA
                                        )

                                    [1] => Array
                                        (
                                            [0] => 7
                                            [id] => 7
                                            [1] => 4
                                            [pid] => 4
                                            [2] => AAA2
                                            [name] => AAA2
                                        )

                                    [2] => Array
                                        (
                                            [0] => 8
                                            [id] => 8
                                            [1] => 4
                                            [pid] => 4
                                            [2] => AAA3
                                            [name] => AAA3
                                        )

                                )

                        )

                    [1] => Array
                        (
                            [0] => 5
                            [id] => 5
                            [1] => 1
                            [pid] => 1
                            [2] => Folder AA2
                            [name] => Folder AA2
                        )

                )

        )

    [1] => Array
        (
            [0] => 2
            [id] => 2
            [1] => 0
            [pid] => 0
            [2] => Folder B
            [name] => Folder B
        )

    [2] => Array
        (
            [0] => 3
            [id] => 3
            [1] => 0
            [pid] => 0
            [2] => Folder C
            [name] => Folder C
        )

)

[prototype]

De tabledump die ik heb gebruikt voor het experimentje

code:

-- Database: `recursion`
-- 

-- --------------------------------------------------------

-- 
-- Table structure for table `folders`
-- 

CREATE TABLE `folders` (
  `id` int(5) unsigned NOT NULL auto_increment,
  `pid` int(5) unsigned NOT NULL default '0',
  `name` varchar(255) default NULL,
  PRIMARY KEY  (`id`),
  KEY `pid` (`pid`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=9 ;

-- 
-- Dumping data for table `folders`
-- 

INSERT INTO `folders` VALUES (1, 0, 'Folder A');
INSERT INTO `folders` VALUES (2, 0, 'Folder B');
INSERT INTO `folders` VALUES (3, 0, 'Folder C');
INSERT INTO `folders` VALUES (4, 1, 'Folder AA');
INSERT INTO `folders` VALUES (5, 1, 'Folder AA2');
INSERT INTO `folders` VALUES (6, 4, 'Folder AAA');
INSERT INTO `folders` VALUES (7, 4, 'AAA2');
INSERT INTO `folders` VALUES (8, 4, 'AAA3');

[Janoz]

imho zitten in dat scriptje wel heel veel queries. Welke folder bij een bepaalde parent hoort en hoeveel kinderen hij heeft kan heel makkelijk in 1 query ipv 2.Effectief ben je nu 2 queries per folder aan het doen. Daarnaast vind ik een SELECT * FROM erg 'smerig' waneer je alleen maar wilt weten of er elementen zijn. In dat geval kun je beter een count(*) gebruiken.

Gebruik je bij het opvragen van de kinderen:

code:

SELECT 
   folder.id       AS id, 
   COUNT(sub.id)   AS children 
FROM 
     folders folder 
   LEFT JOIN 
     folders sub 
   ON 
     folder.id=sub.pid 
WHERE 
   folder.pid= ____

dan heb je ten eerste alle kinderen van een bepaalde node en gelijk ook het aantal kleinkinderen per kind.

[ Voor 5% gewijzigd door Janoz op 01-03-2005 08:43 ]

[prototype]

Dat het een dure manier was was ik van op de hoogte Het kan heel makkelijk in minder queries, sterker nog je zou de hele table kunnen selecten, op kunnen vangen en vervolgens in elkaar kunnen draaien. Dat zou resulteren in 1 query ofzo, of dat echter efficienter en makkelijker te begrijpen is weet ik niet.
Hoe dan ook, mijn streven was ook nooit zozeer efficientie, meer simpliciteit; de werking is in 1 oogopslag te zien. Daar heeft de TS meer aan imho dan l33t code practice Wat betreft het SELECT * gebeuren verontschuldig ik me iig, 't was 4:00 AM ofzo

[ Voor 11% gewijzigd door prototype op 01-03-2005 09:29 ]

[raps]

prototype schreef op dinsdag 01 maart 2005 @ 09:26:
Hoe dan ook, mijn streven was ook nooit zozeer efficientie, meer simpliciteit; de werking is in 1 oogopslag te zien. Daar heeft de TS meer aan imho dan l33t code practice Wat betreft het SELECT * gebeuren verontschuldig ik me iig, 't was 4:00 AM ofzo

Als dat je streven was, heeft Borgg dat toch een stuk beter gedaan in dit draadje.


Aangezien de TS op zoek is naar een theoretische manier om bomen te kunnen aanspreken met enkele queries, zou hij eens kunnen kijken naar Joe Celko's benadering van boomstructuur. Deze staat, samen met de manier besproken in dit draadje, uitgelegd in een artikel op sitepoint.

[Paul]

Recursief kinderen verwijderen? Ik heb geen idee hoe je dat in SQL zou kunnen doen, maar in pseudocode:

code:

procedure DeleteSubtree(subtreeRoot: integeer);
begin
  select id where parent_id = subtreeRoot

  voor ieder gevonden_id
    DeleteSubtree(gevonden_id);

  delete from folders where id = subtreeRoot
end;

Dit kost je wel een select per node, en bij VEEL levels diep loop je kans op een stack overflow Maar goed, dat laatste heb je altijd bij een recursieve functie.


omdat ik toch bezig ben: het opbouwen van de grafische boom:

code:

procedure TekenTree(root, level: integeer);
begin
  select naam where id = root
  teken lijntjes voor niveau level en zet er de naam bij

  select id where parent_id = root
  voor ieder gevonden_id
    TekenTree(gevonden_id, level + 1);

end;

Dit is echter wel iets lastiger, want hoe weet je nu welke doorlopende vertikale lijntjes je moet trekken? Daar ben ik nog niet helemaal uit

[ Voor 38% gewijzigd door Paul op 01-03-2005 10:48 . Reden: debug :P ]

[Knutselsmurf]

Voor het verwijderen is er nog een andere methode.
Allereerst verwijder je de node die je wilt verwijderen.
Dan kan het dus voorkomen dat je een aantal wezen creeert. Vervolgens verwijder je alle wezen, dus alle nodes die verwijzen naar een niet-bestaande parent. Dit herhaal je net zolang tot er geen wezen meer zijn. Op deze wijze blijft het aantal queries voor het verwijderen van een deel van een boom beperkt tot het aantal niveaus. Als je in stap 1 3 kinderen verwijdert, kun je in stap 2 in 1 keer alle kleinkinderen verwijderen, terwijl je daar anders 3 queries voor nodig zou hebben.

[MSalters]

Als je bijvoorbeeld A wil deleten, waarom dan niet

SQL:

DELETE * WHERE foldername LIKE 'A/%'

Heb je niet eens een parent FK voor nodig.

Het helpt veel als je separators gebruikt tussen de delen van je foldenames

edit:
en een terminator

, anders is het niet duidelijk of foldername AB een toplevel is of B in A. A/B/ is altijd helder, maar dan mag je geen / in een deel gebruiken. De separators en terminator zijn nodig, omdat je dan op een nivo A en AA kunt hebben. Anders moet elke naam binnen de desbetreffende scope een unieke prefix zijn. Met een afsluitende / die niet verder niet voorkomt is dat gegarandeerd.

offtopic:
ben geen SQL guru, maar volgens mij verdient dit de kwalificatie smerige hack?

[ Voor 25% gewijzigd door MSalters op 01-03-2005 13:02 . Reden: toelichting over / gebruik ]

[Paul]

Ik denk dat de daar gekozen foldernamen eerder zijn om onze beeldvorming wat te vergemakkelijken dan dat het echt de namen zijn

Als ik in een menu met 100 items (brr gelukkig is het een boom ) iets op moet zoeken vind ik het wel leuk als de namen wat zinnigs zeggen over wat er achter zit

offtopic:
Yup

[ Voor 4% gewijzigd door Paul op 01-03-2005 12:48 ]

[MSalters]

Ach, als de namen wat langer zijn dan moet je misschien een
LIKE 'huis/garage/ferrari/%' doen.

[Verwijderd]

De namen waren idd. ter illustratie, maar dat terzijde.

Iedereen bedankt voor de hulp...eigenlijk best blond dat ik het niet gewoon zelf heb gezien, maar soms staar je je gewoon dood op je eigen code (vooral midden in de nacht ), en heb je even een zetje van buitenaf nodig.

De quick&dirty code (die nu nog een 'echo' doet i.p.v. een DELETE) :

PHP:

function deletefoldertree($id) {
  $query = "SELECT * FROM $tb_folders WHERE folder_parent = $id";
  $result = mysql_query($query);

  while ($row = mysql_fetch_array($result)) {
    $folder_id = $row["folder_id"];
    echo $folder_id . "<br>"; // Dit wordt een DELETE statement
    deletefoldertree($folder_id);
  }
}

Ik heb nog flink zitten stoeien met de array-oplossing van protoype, maar die multidimensional werd zo diep dat er op een gegeven moment geen eind meer aan kwam...wel mooie code trouwens.

Nogmaals mijn hartelijke dank voor het meedenken!

Mark.

[MSalters]

Overigens: een DB met referential integrity doet dit toch automatisch, als je de key relatie netjes aanmaakt, met een cascading delete? Schijnt zelfs in MYSQL te werken.

[ Voor 12% gewijzigd door MSalters op 01-03-2005 13:23 ]

[Paul]

Verwijderd schreef op dinsdag 01 maart 2005 @ 13:06:De quick&dirty code (die nu nog een 'echo' doet i.p.v. een DELETE) :

Die code heeft een bugje Hij verwijderd nu alles, behalve het allereerste record. Je delete nu je folder_id, maar nergens je originele id

Aangezien je voor iedere folder_id toch een keer deletefoldertree aanroept kun je het beste de delete-statement uit de loop halen

[Verwijderd]

Paul Nieuwkamp schreef op dinsdag 01 maart 2005 @ 10:32:
(...)
omdat ik toch bezig ben: het opbouwen van de grafische boom:
Dit is echter wel iets lastiger, want hoe weet je nu welke doorlopende vertikale lijntjes je moet trekken? Daar ben ik nog niet helemaal uit

De beschikbare info van de boom vat je in een compostite-structuur. Composite en zijn iterators kan je makkelijk geavanceerder maken dan het geval is bij een 1-dimensionale record set. Zo kan je voorzien in functies voor ChildCount, NextChild, IndentLevel, ExpandState etc. Hieruit kan je de knopjes voor +, -, elleboogjes en staafjes afleiden.

Ook kan je met composite de hele boom in fracties laden. Hiermee voorkom je lang wachten (bv Windows Explorer ). Verder kan de info in je boom ook verouderen. Dan is het belangrijk je boom handig aan te kunnen passen. Composite zit hier gemakkelijker dan een botte recursieve routine.

[Vuurvlieg]

Voor het verwijderen van child elements zou ik cascading deletes gebruiken. Deze zorgen ervoor dat als een primary key verwijderd word, eventuele foreign keys ook verwijderd worden (althans dit kan, er zijn meer mogelijkheden). Dit zorgt ervoor dat je database zichzelf in een consistente staat houdt. Dus het verwijderen van een parent element zou ervoor zorgen dat alle children ook verwijderd worden, aangezien dit parents kunnen zijn van anderen zullen deze ook verwijderd worden.. etc..

Linkje voor mysql:

http://dev.mysql.com/doc/...eign-key-constraints.html

[Verwijderd]

Paul Nieuwkamp schreef op dinsdag 01 maart 2005 @ 13:34:
[...]

Die code heeft een bugje Hij verwijderd nu alles, behalve het allereerste record. Je delete nu je folder_id, maar nergens je originele id

Aangezien je voor iedere folder_id toch een keer deletefoldertree aanroept kun je het beste de delete-statement uit de loop halen

You're right! Is verbeterd, thanks!

[Verwijderd]

Vuurvlieg schreef op dinsdag 01 maart 2005 @ 15:04:
Voor het verwijderen van child elements zou ik cascading deletes gebruiken. Deze zorgen ervoor dat als een primary key verwijderd word, eventuele foreign keys ook verwijderd worden (althans dit kan, er zijn meer mogelijkheden). Dit zorgt ervoor dat je database zichzelf in een consistente staat houdt. Dus het verwijderen van een parent element zou ervoor zorgen dat alle children ook verwijderd worden, aangezien dit parents kunnen zijn van anderen zullen deze ook verwijderd worden.. etc..

Linkje voor mysql:

http://dev.mysql.com/doc/...eign-key-constraints.html

Leuk....ga ik zeker eens naar kijken...maar werkt dit op alle soorten db-servers? Ik bouw de code nu modulair voor MySQL en MS-SQL, met meerdere merken databases in de pen.....

[Vuurvlieg]

Ja wij gebruiken het in PostgreSQL, volgens mij zit het in de SQL standaard. Alle databases die enigszins rijk aan features (en sql compliant) zijn zullen het wel ondersteunen. Tot voor kort gebruikten wij ook php om de database op orde te houden, onze ervaring wees echter uit dat dit veel beter in de database kan. Na een verdieping hoe dit mogelijk was zijn we onder andere met cascading deletes en updates gaan werken. succes ermee!

[MSalters]

Ik schrijf niet voor niets "zelfs in MYSQL"; MYSQL is ongeveer de definitie van "minimum feature set om nog een DB te mogen heten"