[Mysql] Ordinamento di un albero in forma non ricorsiva

notorious

[Mysql] Ordinamento di un albero in forma non ricorsiva

Salve a tutti, vi spiego subito il mio problema. Ho interfacciato la board MyBB al mio sito, e vorrei visualizzare l'albero dei forum e sottoforum. Fino adesso utilizzavo una funzione in php ricorsiva, che ad ogni chiamata fa una query al db: considerando che il mio hoster limita le query all'ora, la sola stampa dell'albero genera decisamente troppe interrogazioni.

Velocemente, questa è la struttura della tabella riguardante i forum:
la chiave è un intero, fid;
c'è un altro intero, disporder, che regola l'ordine di visualizzazione dei forum (ma solo per i forum figli - non nipoti, non so' se mi spiego - dello stesso padre);
c'è una stringa, parentlist: è formata da dei fid separati da virgole contenente tutti gli "antenati" (anche il padre diretto; l'ultimo elemento è se' stesso) del forum corrente (per esempio, utile per stampare direttamente "1. Categoria principale / 1.2 Forum musica / 1.2.5 Forum

Questi sono tutti i campi che credo siano necessari (poi vabeh, c'è nome, descrizione, ...) per la stampa dell'albero. Nella forma ricorsiva riesco sia a preservare la struttura dell'albero (padri->figli), sia l'ordinamento.
Per la forma non ricorsiva uso la seguente query (stampo tutti i forum che contengano nella parentlist il fid del forum radice - fid = 6):

SELECT *
        FROM mybb_forums
        WHERE parentlist LIKE "%,6,%"
        ORDER BY parentlist ASC
``` Ordinandolo per parentlist riesco a preservare la struttura dell'albero, ma non l'ordinamento, come vedete nel seguente esempio:
* [Concerti - Order: 30 - PlistSize: 3](http://127.0.0.1/test.php?id=10)
* [Concerti passati - Order: 1 - PlistSize: 4](http://127.0.0.1/test.php?id=18)
* [Concerti futuri - Order: 1 - PlistSize: 4](http://127.0.0.1/test.php?id=19)            
* [Home - Order: 10 - PlistSize: 3](http://127.0.0.1/test.php?id=8)
* [Multimedia - Order: 20 - PlistSize: 4](http://127.0.0.1/test.php?id=13)
* [Galleria Immagini - Order: 10 - PlistSize: 4](http://127.0.0.1/test.php?id=14)
* [Mappa del sito - Order: 30 - PlistSize: 4](http://127.0.0.1/test.php?id=15)
* [Test - Order: 1 - PlistSize: 5](http://127.0.0.1/test.php?id=27)                                
* [News - Order: 20 - PlistSize: 3](http://127.0.0.1/test.php?id=9)
* [News - Korona - Order: 1 - PlistSize: 4](http://127.0.0.1/test.php?id=16)
* [News - Queen - Order: 1 - PlistSize: 4](http://127.0.0.1/test.php?id=17)
* [Test news - Order: 1 - PlistSize: 5](http://127.0.0.1/test.php?id=28)
* [blabla - Order: 1 - PlistSize: 6](http://127.0.0.1/test.php?id=29)
* [bleble - Order: 1 - PlistSize: 7](http://127.0.0.1/test.php?id=30)                                                                                                Plist size è la dimensione della parentlist (l'ho trasformata in un'array tramite php, credo che possa essere utile per un eventuale algoritmo di ordinamento in php). Io vorrei che al primo livello l'ordine sia: Home, News, Concerti; al secondo livello (per quanto riguarda Home) Galleria immagini, Multimedia, Mappa, e così per tutti i livelli.
E' possibile implementare un tale ordinamento direttamente col Mysql senza ricorrere al php?

EDIT: scusate il post chilometrico che va contro le policy del forum, ma altrimenti non sarei stato abbastanza chiaro (forse non lo sono stato neanche così  :D)

notorious

Metto un altro post per non allungare troppo il primo. Inserisco una parte del risultato della query postata nel primo post per facilitare la comprensione del problema:

FID    PARENTLIST    NAME        DISPORDER
10    3,6,10        Concerti        30
18    3,6,10,18    Concerti Passati    1
19    3,6,10,19    Concerti futuri        1
8    3,6,8        Home            10
13    3,6,8,13    Multimedia        20
14    3,6,8,14    Gall. immag.        10
15    3,6,8,15    Mappa del sito        30
27    3,6,8,15,27    Test            1

...

Come vedete, l'ordinamento per parentlist mantiene la struttura dell'albero perché i figli hanno l'inizio della parentlist uguale alla parentlist dei genitori (è un ordinamento per stringhe). Il problema è che ovviamente, una volta ordinato per parentlist, non si riesce ad ordinare per nient'altro. Da profano non mi viene in mente niente per ordinare anche per disporder, preservando la struttura dell'albero, senza ricorrere al php

notorious

Scusate il terzo messaggio consecutivo, ma ho risolto in un altro modo (magari a qualcuno interessa ;)).
Ho risolto con l'Adjacency List Model, utilizzando i campi fid e pid (parent id):

SELECT t1.name AS lev1, t1.disporder AS order1,
       t2.name as lev2, t2.disporder AS order2,
       t3.name as lev3, t3.disporder AS order3,
       t4.name as lev4, t4.disporder AS order4,
       t5.name as lev5, t5.disporder AS order5,
       t6.name as lev6, t6.disporder AS order6
FROM   mybb_forums AS t1
       LEFT JOIN mybb_forums AS t2 ON t2.pid = t1.fid
       LEFT JOIN mybb_forums AS t3 ON t3.pid = t2.fid
       LEFT JOIN mybb_forums AS t4 ON t4.pid = t3.fid
       LEFT JOIN mybb_forums AS t5 ON t5.pid = t4.fid
       LEFT JOIN mybb_forums AS t6 ON t6.pid = t5.fid
WHERE t1.fid = 6 AND t2.fid != 7
ORDER BY order2,order3,order4,order5,order6
``` ```
CONFIGURAZIONE DEL SITO    1    Home    10    Galleria Immagini    10    NULL    NULL    NULL    NULL    NULL    NULL
CONFIGURAZIONE DEL SITO    1    Home    10    Multimedia    20    NULL    NULL    NULL    NULL    NULL    NULL
CONFIGURAZIONE DEL SITO    1    Home    10    Mappa del sito    30    Test    1    NULL    NULL    NULL    NULL
CONFIGURAZIONE DEL SITO    1    News    20    News - Korona    1    NULL    NULL    NULL    NULL    NULL    NULL
CONFIGURAZIONE DEL SITO    1    News    20    News - Queen    1    Test news    1    blabla    1    bleble    1
CONFIGURAZIONE DEL SITO    1    Concerti    30    Concerti passati    1    NULL    NULL    NULL    NULL    NULL    NULL
CONFIGURAZIONE DEL SITO    1    Concerti    30    Concerti futuri    1    NULL    NULL    NULL    NULL    NULL    NULL

Come vedete ogni riga ha dei "blocchi" (lev_i - order_i ), che, tranne per quanto riguarda il primo blocco di ogni riga, corrispondono ai rami dell'albero. Ci sono tanti blocchi quanto la profondità massima dell'albero.
Scorro tutte le righe, e per ogni riga scorro tutti i blocchi (tranne quelli impostati a NULL), e ogni blocco lo aggiungo in coda ad un array (se non è stato già aggiunto), ottenendo così il risultato cercato (che riesco a tradurre in una lista annidata):
home / gall img / multimedia / mappa / test / news etc...

Lo svantaggio è che con questa tecnica devo usare tanti left join quanto è la profondità massima dell'albero; per questo mi serve fare prima un'altra query e generare la query principale col php. La profondità massima dell'albero la prendo da:

SELECT *
        FROM mybb_forums
        WHERE parentlist LIKE "%,6,%"
        ORDER BY parentlist ASC

Per ogni riga conto il numero di elementi della parentlist, e prendo il massimo e il minimo di tutto il risultato. Profondità massima = max - min +1 (calcolata tramite php). Il risultato finale è questo: