[mssql] zoeken in nested categorieen

[Pelle]

Ik ben hier bezig met een webshop-achtig project in ASP en MSSQL. De situatie is als volgt:

* er is een tabel products, en elk product is gelinked aan een categorie (dmv een catid veld in de tabel zelf)
* er is een tabel categories, en die heeft een FK naar zichzelf, oftewel: een categorie heeft een parent-cat-id.

De categorie-structuur krijgen we aangeleverd, en het vervelende is dat in een hoofdcategorie (met als parent-cat-id 1) soms direct de eind-categorieen zitten (de categorieen waar producten naar verwijzen), maar in de andere gevallen zitten er nog 1 of meer categorieen tussen, voor een eindcategorie is bereikt.

Even schematisch:

code:

1 Root
    2 Digitale camera's
        * Canon Digital Ixus
        * Nikon 4300
    3 Monitoren
        4 CRT
            * Dell 21'' bla
            * Viewsonic 19'' melp
        5 TFT
            * acer 17'' woei
            * hp 15'' knel
    6 Software
        7 Besturingssystemen
            8 Workstation OS
                * Windows XP
            9 Network OS
                * Novell 6.5
            10 Server OS
                * Windows server 2003
        11 Grafische software
            * Adobe Photoshop

Nu is de wens, dat er vanuit elk niveau gezocht kan worden in alle producten uit alle categorieen die daaronder hangen. Dus stel, ik zit in de categorie 'software', dan moet ik dus zoeken naar producten met cat-id 8, 9, 10 of 11.
Dit zou geen probleem moeten zijn als je te maken hebt met een vast aantal niveau's, maar het probleem is nu dus dat je niet weet hoeveel categorieen diep je moet zoeken.

Nu is mijn vraag hoe ik dit aan zou moeten pakken: ontkom je niet aan recursiviteit (zo ja, hoe?), of heeft MSSQL hier een oplossing voor? Ik meen me te herinneren dat Oracle een dergelijke mogelijkheid had om nested records te kunnen doorzoeken namelijk; wellicht dat MSSQL dat ook heeft? Ik ben al stug aan het zoeken geweest op MSDN, maar ik zie zo 1-2-3 niet iets wat van toepassing zou kunnen zijn.

[ Voor 3% gewijzigd door Pelle op 19-03-2004 09:40 ]

[P_de_B]

In Yukon kan dit standaard hebben ze gezegd, helaas nu nog niet.

Een redelijke oplossing kun je vinden als je in BOL zoek op 'expanding hierarchies'.

edit: hmm, had je vraag niet helemaal goed gelezen, maar ik denk toch dat je met het BOL onderwerp wel wat kunt. Laat het anders even weten.

[ Voor 35% gewijzigd door P_de_B op 17-03-2004 12:38 ]

[ACM]

Oracle en DB2 bieden idd Connect by als query-uitbreiding om een vorm van recursiviteit in te bouwen.

Je zou zelf een stored procedure in elkaar kunnen draaien die alle child id's ophaalt, bijvoorbeeld met zoiets in gewone (php)programmacode (ik weet niets van de syntax van MSSQL's SP-code af):

PHP:

function returnChildren($parentid)
{
   $outputset = array();
   $children = SELECT id FROM category WHERE parentid = $parentid;
   foreach($children as $child)
   {
       $outputset[] = $child;
       $outputset[] = returnChildren($child);
   }
}

't Klinkt als iets dat je met een paar handige UNION's wel moet kunnen oplossen, maar ik weet niet of T-SQL handigere dingen biedt.
De output van bovenstaande functie kan je vervolgens in een IN() gebruiken en dan heb je ineens alle childids.

Met jouw ondiepe boom is dat allemaal niet zo erg lijkt me, eventueel kan je die SP ook gewoon in programmacode wikkelen.

Voor diepe bomen moet je dat uiteraard niet doen, dan loop je een groot risico dat je recursie te veel performance kost.
Helaas is SQL totaal ongeschikt voor bomen en zijn systemen als ODBMS-en daar vele malen handiger mee (daar heb je ook wel recursieve structuren enzo, maar je kan het dan iig ook recursief opslaan als je zou willen). Zolang je aan SQL gebonden bent helpt dit regeltje je natuurlijk niks, gelukkig zijn er voor diepere bomen toch een paar handige oplossingen.

Ze zijn overigens allemaal zeer bewerkelijk op het moment dat je verschuivingen in je boom wilt en een van de oplossingen is zelfs bij een simpele insert al bewerkelijk.
parentids bijhouden: Dit is de standaard aanpak die recursie vereist, maar alle directe children selecteren en wijzigingen zijn zeer eenvoudig te doen.

Nested set: een door Joe Celko bedachte boomoplossing die gebruik maakt van het feit dat een hogere categorie de categorieen erin "omspant". Dus als je de diepste categorieen een bereik van x, x+1 (15, 16 ofzo) geeft en de gene die "daaromheen zit" x-1, x+2 (14, 17) en dat verder uitbouwt per niveau, dan kan je daar zeer handige selects mee uitvoeren zonder recursie.
Voor de children van een categorie is het tenslotte altijd zo dat ze een grotere "left" en een kleinere "right" hebben. Dat wat bij het opslaan van het parentid makkelijk gaat is hier juist bewerkelijk; inserts vereisen bijvoorbeeld verschuivingen van gemiddeld de helft van je complete categorieboom!

Een "variant" op de nested set is de nested interval:
Ene Thropasky oid heeft dat bedacht, het idee is dat je elk mogelijk "punt" van categorieen vastlegt en een childcategorie op zo'n plek dan vastpint. Welke plek ie dan precies terechtkomt hangt van de plek van de parent en een zwik rekenwerk af. Maar een insert is alleen een insert met wat rekenwerk, geen geklooi met verschuiven van de andere categorieen. 't Grote nadeel is echter dat op het moment dat je gaat proberen een oneindig aantal getallen vast te leggen, je ergens een geheugenlimiet bereikt. Maxint is tenslotte maar 2miljard en maxbigint 't kwadraat, maar er werd gebruik gemaakt van binair-exponentiele sprongen, dus alles wat een niveau dieper dan de parent lag had al minimaal het kwadraat van de parent's waarden... Alleen de meest linkse tak kon dan bijv 64 diep worden, die ernaast al niet meer en de meest rechtse kwam maar tot 1 diep. Beetje onhandig en nog lastige berekeningen ook.

Thropasky heeft zelf een (nog moeilijker te berekenen geloof ik) variant kortgeleden getoond van de nested interval die niet zo snel tegen de limiet van de integer aanliep, hoe deze precies werkt weet ik eigenlijk niet. 't Was iig iets dat de exponentiele groei eruit sloopte met de naam "Farey Fractions"


Een heel andere variant is het opslaan van het "materialized path", oftewel, sla niet cat6 heeft als parent cat2 heeft als parent cat1 op, maar het hele pad naar cat6 op 1.2.6
Je moet dan ineens wel weten "het hoeveeste record" je categorie is, overigens moest je datzelfde bij de nested intervals weten.
Selects kan je eenvoudig met LIKE's doen, die gelukkig van indices gebruik kan maken, als je bijv alle children van een parent zoekt (child.path like parent.path || '%').
Een nadeel is de bewerkelijke verschuivingen en een andere het feit dat je strings nogal lang kunnen worden, waarbij dan vermeld moet worden dat veel db's maar maximaal een bepaalde lengte van de string indexeren en/of soms de string compleet weigeren als er een index op zit. Binair coderen en in een blob stoppen (mits daar indices op kunnen) of een of andere bitstring/binary string scheelt je aardig wat ruimte, maar is minder leesbaar voor de mens

Meer informatie kan je met de gegeven namen vinden en bijvoorbeeld op deze site is een aardige uitleg geplaatst van de varianten: http://www.scenic-route.com/program/db/lists.htm Deze geeft voorbeeldcode in T-SQL dus je hebt mazzel (hmm, toch niet in T-SQL, maar in VB?)

edit:

Deze doet het in SQL Server: http://www.yafla.com/pape...rchies/sqlhierarchies.htm

Als je boom niet te diep is, zou je het best denk ik de recursie voor lief kunnen nemen en in je client-app implementeren of in stored procedures. Als je perse de performance wilt verbeteren voor je selects, dan is de nested set het eenvoudigst als je met getallen wilt werken, maar de nested interval wellicht wat sneller (hoewel mij niet helemaal duidelijk werd hoe het gebruik van indices kon maken, misschien functionele?)
De materialized path heeft als nadeel dat je ineens string-operaties doet, maar het zijn wel heel simpel te begrijpen operaties, wat dus weer een voordeel is.


Ik geloof dat ik zo een aardig overzicht van de mogelijke nesting heb gegeven, weet iemand nog aanvullingen?
Voor mensen die er meer over willen lezen, Joe Celko is bezig met het uitbrengen van een boek (zegt ie al een jaar, maar 't schijnt nu "in print" te zijn) over het werken met hierarchien (niet alleen bomen, ook andere graven) in SQL.

[ Voor 6% gewijzigd door ACM op 17-03-2004 13:21 ]

[Pelle]

Interessant verhaal, thanks
Ik denk dat ik niet onder recursie uit ga komen dan; ik zal eens kijken of ik daar een SP voor kan schrijven. Zo niet, dan kan het alsnog wel in ASP, maar het blijft wel een beetje ranzige oplossing.

[Macros]

Ik denk dat ik ook nog een oplossing weet. Je houdt 1 tabel bij waarin met parentid's alle relaties zijn gelegt tussen je takken in je boom.
Die lees je 1 keer helemaal in je applicatie in. Dan in elke node hou je dan een lijst bij van alle nodes die eronder liggen. Als een gebruiker dan wil zoeken in die subtree, haal je die lijst op uit die node, en kan je daarop selecten.
Nadeel is dat als je stateless werkt, zoals met php ofzo, dat je dan altijd die hele 'index' moet inlezen en daarna aanmaken. In php zou ik dat oplossen door die boom met print_r ofzo naar een file te schrijven, dan kan je hem met exec() in 1 keer weer inlezen, of anders zet je hem als text in de database. Als je boom dan veranderd, dan lees je hem weer in en schrijf je hem opnieuw naar een file of db veld.

[ACM]

Nadeel is dat je dan alle voordelen van referentiele integriteit en efficientere record-level-locking echt compleet overboord zet
Maar het is idd een oplossing die ik in een of andere pattern boek (van Fowler?) tegenkwam, xml van maken en dat in een blob in je database mikken...

[P_de_B]

Pelle schreef op 17 maart 2004 @ 13:47:
Interessant verhaal, thanks
Ik denk dat ik niet onder recursie uit ga komen dan; ik zal eens kijken of ik daar een SP voor kan schrijven. Zo niet, dan kan het alsnog wel in ASP, maar het blijft wel een beetje ranzige oplossing.

dan zou ik toch even de methode uit Books Online bekijken

[Verwijderd]

de oplossing is parent id maken hé ( anders eens naar de SQL structuur kijken an apb bookmarks ) !!! staat mooi wat je nodig hebt

[ACM]

'de oplossing' die jij noemt heb ik ook genoemd en gebruikt ie al...
En heeft een paar nadelen, o.a. dat je verplicht bent recursie toe te passen, danwel in je SQL-statements, danwel in je clientapplicatie

[d00d]

Kun je de SQL code even generen en plakken?
Ik heb zoiets als die al eens eerder opgelost maar ben nogal lui en wil dus niet teveel tijd besteden aan het aanmaken van de database.

Ik zie recursie trouwens helemaal niet als een nadeel. Het zorgt er vaak voor dat de code klein blijft en dus goed leesbaar.

[ Voor 1% gewijzigd door d00d op 18-03-2004 16:13 . Reden: typo ]

[Pelle]

Zal morgen op de zaak even kijken, ben er nog niet aan toegekomen

Verwijderd schreef op 17 maart 2004 @ 22:14:
de oplossing is parent id maken hé

Euh..

Pelle schreef op 17 maart 2004 @ 12:36:
* er is een tabel categories, en die heeft een FK naar zichzelf, oftewel: een categorie heeft een parent-cat-id.

Dus

[ACM]

d00d schreef op 18 maart 2004 @ 16:12:
Ik zie recursie trouwens helemaal niet als een nadeel. Het zorgt er vaak voor dat de code klein blijft en dus goed leesbaar.

Uiteraard, maar zodra je recursief queries gaat aanroepen ben je performance-wise niet handig bezig als je daar wel behoefte aan hebt.

Trouwens, recursief sql-queries uitvoeren is wel wat anders dan recursief een functie-call doen. Imho is het eerste niet perse duidelijker dan een goed geformuleerde enkelvoudige query, wat de andere oplossingen allemaal toelaten.