Newsgroup: it.comp.www.php
Titolo: Funzione ricorsiva gestione utenti

Ho la necessità di fare una cosa abbastanza comune, ovvero identificare
se un dato ID è figlio di un altro ID, per una gestione utenti su più
livelli.
Ad esempio:
+------+----------+--------------+
| id   | parentid | nome         |
+------+----------+--------------+
| 1    | 0        | paperino     |
| 2    | 1        | qui          |
| 3    | 1        | quo          |
| 4    | 1        | qua          |
| 5    | 0        | paperina     |
| 6    | 4        | figlio di qua|
+------+----------+--------------+
dovrebbe essere abbastanza comprensibile.
ci sono due utenti 'base' ovvero paperino e paperina che
hanno infatti parentid = 0
paperino ha 3 figli (parentid = 1 che corrisponde a paperino)
e sono qui, quo, qua.
qua ha un figlio, di nome figlio di qua.
Ho bisogno di tirar fuori un array del tipo:
1
|--- 2
|--- 3
|--- 4
|    |-- 6
|
|--- 5
in questo modo, paperino può gestire tutto, compreso "figlio di qua"
perchè è sotto di lui, mentre non può accedere a paperina.
non è difficile, ma nel caso ci fosse una libreria già fatta sarebbe
meglio, altrimenti me la faccio io.
posso anche cambiare il database, eventualmente, anche se una struttura
del genere mi pare buona e son già abituato a lavorarci.

 del genere mi pare buona e son già abituato a lavorarci.
Mi correggo, il problema non è avere una libreria già fatta, anche
perchè ho già scritto il codice (15 righe) e funziona, l'albero
vien creato, il problema però è gestire la query facendola partire
da un utente ben preciso.
adesso come adesso, faccio una query unica, che prende tutti gli utenti,
crea l'albero e filtro l'array partendo da l'id che mi interessa, ma non
è molto saggia come cosa, se avessi 457000 utenti dovrei ogni volta
prendere tutti gli utenti, creare l'albero per intero e poi filtrarlo.
ma non posso nemmeno filtrare a livello di query, visto che facendo una
cosa simile a:
select * from users where id = 14 or parentid = 14;
prenderei solo l'utente 14 ed i suoi figli diretti, e mai i figli dei
figli (che per forza di cose non avranno mai 14 come parentid)
any idea?

 perchè è sotto di lui, mentre non può accedere a paperina.
Il disegno che hai tracciato ha Paperino come radice e Paperina come 
figlio.
Quanto spesso devi generare l'albero? Per una volta al giorno non ti 
conviene cambiare struttura.

 conviene cambiare struttura.
Si spera più e più volte ogni ora. Più cambia, meglio è, perchè
il sistema vuol dire che funziona e la gente lo usa.

 LOL, e chi sarebbe la sorella? Non la conosco.
Della Duck, la gemella.
Non ti sei mai chiesto perché lo chiamassero 'zio'? :-)
Comunque per un problema simile al tuo (generazione di
un albero di sezioni ad infiniti livelli) faccio una select al
contrario di tutta la tabella, la ciclo in memoria in uno
stack e poi tiro fuori solo il livello che mi serve.
Non ho trovato di meglio e, poiché nel mio caso si tratta
di un numero comunque ragionevole di record, non ho
mai avuto problemi.
Se i tuoi record sono molti, non hai modo di utilizzare
caching, su disco, in memoria, in sessione?
-- 
ValeRyo
XT600 "Katoki Pajama" - 
http://www.slimmit.com/go.asp?7Y9
GamerTag: 
http://card.mygamercard.net/IT/nxe/ValeRyo76.png
 

 mai avuto problemi.
Sono utenti, su almeno 3 livelli, ovvero amministratore, rivenditore,
cliente, e ciascuno deve poter creare illimitati sottolivelli.
l'admin deve poter creare illimitati reseller, il reseller illimitati
utenti e l'utente illimitati sotto-account.
Ci sarebbero i nested tree, ma son decisamente overkill.
Io devo fare una cosa relativamente semplice:
sapere se l'ID 56 è figlio (anche di 937esimo grado) dell'utente
loggato in quel preciso momento. Fine.
Questo perchè una volta fatto l'elenco degli id figli posso filtrare
tutte le query mettendo un bel user_id IN (lista_figli) anzichè 
user_id = utenteid
Potrei fare, come sto facendo ora, una mega select prendendo tutti
i record di tutta la tabella, creare un array ad albero e ciclarlo
finchè non trovo un elemento avente id = al cliente loggato.
Una volta trovato, prendo tutti i suoi figli (che son già li dentro
l'array, in un elemento child) e mi creo una lista di id 
(2,3,56,98, ...)
ma non è il massimo per le performance.

 utenti e l'utente illimitati sotto-account.
Io ho usato una tecnica un po' bastarda, che va bene quando hai un numero 
(previsto) limitato di sottolivelli. Richiede un po' di spazio in piu` 
nel DB e un po' di lavoro in insert/update, ma permette di fare una sola 
query in select.
La tabella diventa qualcosa tipo
id serial,
parent int, (facoltativo)
parents text,
nome text,
...
Per esempio:
id=1, parents='-', nome='Paperino';
id=2, parents='-1-', nome='Qui';
id=2, parents='-1-', nome='Quo';
id=3, parents='-1-', nome='Qua';
id=4, parents='-1-3-', nome='Figlio di Qua';
id=5, parents='-', nome='Paperina';
id=6, parents='-1-3-4-', nome='Figlio del figlio di Qua';
In pratica quando inserisci un nuovo elemento fai (sintassi Zend 
Framework, ma credo sia abbastanza chiara)
$list = new ListaUtenti();
$parent = $list->find($_POST['parentid'])->current();
$new = $list->createRow();
$new->parents = $parent->parents . $parent->id. '-';
$new->nome = $_POST['nome'];
$new->save();
Quando fai una modifica all'albero devi ricordarti di modificare in 
cascata anche tutti i figli.
In lettura, per avere solo i rootnode:
select * from tabella where parents='-';
Per i figli (diretti) di Paperino:
select * from tabella where parents='-1-';
Per tutto l'albero genealogico che parte da Paperino:
select * from tabella where parents='-1-%';
Per i figli diretti di Qua:
select * from tabella where parents='%-3-';
Per l'abero genealogico di Qua:
select * from tabella where parents='%-3-%';
Ecc. ecc. Penso di aver reso l'idea.
I trattini iniziale e finale servono appunto ad avere maggiore controllo 
sulle query.
indicizzando quella colonna hai prestazioni ottime, ma appunto devi stare 
attento alle dimensioni. Mediamente mi pare che i DB indicizzino bene il 
primo KB di un campo di testo, quindi oltre i 2-300 livelli (o meno se 
hai tanti utenti da avere id di 4 o 5 cifre o oltre) cadono un po' le 
prestazioni, ma per le situazioni classiche (fino a 10-15 livelli) 
dovresti andare tranquillo.
Bye.

 any idea?
Sì, cambi la struttura del db inserendo la relazione figlio_di_grado_n 
in cui metti un genitore, un discendente e il grado di parentela. 
In questo modo l'inserimento di un elemento nell'albero al livello 
n-esimo comporta n-1 record in questa nuova tabella ma la select è 
immediata.

 user_id = utenteid
Credo che la soluzione più semplice sia quella che ha proposto
Alessandro oppure una via di mezzo: in un campo salvi l'id
del parente di grado più alto.
Se hai bisogno di sapere la genealogia di un determinato nodo
puoi fare una select where avo=X e poi crearti l'array come fai
già ora.


 query in select.
[cut]
Be, ma in tal caso, mi conviene usare i nested tree, alla fine
il procedimento è simile, una volta trovata una classe che
li gestisca in autonomo si è a cavallo.
Per lo spazio non è un problema, è una semplice tabella di
relazione, i dettagli degli utenti stanno in una tabella
differente, quindi anche se avessi milioni di utenti, la
tabella non sarà mai 'grossa', dopotutto son solo id.
Forse però mi conviene limitare a due livelli, ovvero
rivenditore+cliente, così facendo, mi basta fare una
query tipo:
select * from utenti where id = $loggatoid or parent_id = $loggatoid
per prendere tutti, sia clienti che rivenditore.
se l'utente loggato è un rivenditore, avrà corrispondenza sia in
id che in parentid, ricavando quindi tutti i figli.
se l'utente loggato è un utente, avrà corrispondenza solo in $id
perchè non ci sarà mai un parentid impostato a se stesso (non avendo
sottolivelli)

 immediata.
Credo di non aver capito.
Se ho il figlio di grado 20, portandomi dietro il genitore diretto
posso ricavare solo il genitore diretto.
dovrei portarmi dietro tutta la lista di genitori, quindi 20 livelli.

 gi ora.
Non va bene, perchè io devo poter generare l'albero da qualunque
punto, non solo dal primo livello.
se ho 10 livelli, devo poter generare l'albero a partire dal
settimo e quindi vedere i 3 figli.
se mi salvo l'avo, posso generare l'albero a partire sempre e solo
dal super genitore, ovvero l'avo.
e poi, per salvarmi l'avo, devo comunque ciclare a ritroso tutti gli
utenti eseguendo una query ogni volta oppure prendere tutti gli utenti,
generare l'array (di cui sto parlando da inizio thread) e ciclarlo.
io vorrei evitare di fare sia una query per ogni utente, sia dover
leggere tutti gli utenti, creare un array ed elaborare quello.
oltre che per performance, anche per bug, se si dovesse verificare
un problema, in memoria avrei tutti i dati di tutti gli utenti, non
mi piace molto come soluzione.

 posso ricavare solo il genitore diretto.
Direi di sì perché parli di genitore diretto. Io ti ho suggerito di 
tenere una tabella con tutte le relazioni verticali _e il loro grado_. 
In questo modo hai qualche inserimento in più per ogni nuovo nodo ma hai 
sempre tutta la struttura verticale immediatamente accessibile. Per 
determinare tutta l'ascendenza di un nodo ti basta una SELECT usando il 
nodo in questione come campo 'discendente' e una clausola ORDER BY 
'grado'.

 tenere una tabella con tutte le relazioni verticali _e il loro grado
Mi puoi fare un esempio?

 Mi puoi fare un esempio?
La tabella è parentela(avo, discendente, grado), considera la situazione:
A
|—B
|—C
(A,B,1) (A,C,1) 
Ora aggiungiamo un figlio a B:
A
|—B
| |—D
|
|—C
(A,B,1) (A,C,1) (B,D,1) (A,D,2)
L'inserimento di un nodo a livello 3 ti costa 2 inserimenti.

 ciclarlo.
Perché? Quando generi il figlio conosci suo padre e di
conseguenza l'avo.


 L'inserimento di un nodo a livello 3 ti costa 2 inserimenti.
Ok, ma così facendo non potrei comunque interrogare per B ed
ottenere tutti i suoi figli con una singola query. Ottieni solo
il suo diretto discendente, come un normale id/parentid

 conseguenza l'avo.
Non so, se devo compilare il database o aumentare le query di
inserimento, tanto vale complicarlo con un nested tree, 
che è stato pensato per fare esattamente questa cosa, non trovi?
avrei preferito un qualche sistemino più semplice, mi sa che opterò
per un monolivello senza subclienti di clienti.

 che è stato pensato per fare esattamente questa cosa, non trovi?
Sei tu che hai chiesto come fare *senza* :-)


 Sei tu che hai chiesto come fare *senza* :-)
E si, ma pensavo ci fosse un modo per evitare di dover mettere mano
al db, perchè in tal caso, avendo visto i nested tree, se devo
modificare il db uso i nested tree.
Solo che mi sembra decisamente overkill per una gestione utenti.

 Solo che mi sembra decisamente overkill per una gestione utenti.
Se vuoi un modello ad albero usa una struttura ad albero, altrimenti ne 
scegli un'altra dato che nella discussione sei passato da 20 a 2 
livelli. Secondo me più che l'implementazione devi chiarire le 
specifiche.

 db.
No, mi sarò spiegato male io.
Vedi questa tabella:
Id  Nome            Padre   Avo
1   Nonna papera    NULL    NULL
2   Quackmore       1       1
3   Paperino        2       1
4   Della           2       1
5   Qui             4       1
6   Quo             4       1
7   Qua             4       1
8   P. di Topolino  NULL    NULL
9   Topolino        8       8
10  Topolonia       8       8
11  Tip             10      8
12  Tap             10      8
Se Quo fa login, selezioni Quo e tutti quelli che hanno lo stesso
avo, poi sul subset ti fai l'array e lo cicli come fai già ora per
estrarne solo il sottoramo che ti interessa.
Se Quo genera un figlio hai già in sessione l'id di quo e il suo
avo, quindi ti sarà semplice inserire
13  Figlio di Quo   6       1
Io sto ragionando sui dati che hai postato, se invece ogni record
è di 10k e devi averlo tutto in memoria per lavorare allora è ovvio
che non puoi fare select * from tabella.


 specifiche.
Preferirei poter gestire illimitati livelli, perchè una volta
implementata l'infrastruttura, essa va avanti da sola, sia che
sia prente un 1 livello, sia che siano presenti 456 livelli.
Fatto il giochino, lui è a posto.
Però questi 20 livelli non sono fondamentali, se devo impazzire
con strutture bizzarre/complesse/difficili da manutenere, allora
faccio fallback a 2 livelli.
In quest'ultimo caso, però, se per sfiga un giorno avessi la
necessità di aggiungere un livello dovrei riprogettare l'intera
sezione.
Sto cercando di fare una valutazione costi/benefici:
implemento solo 2 livelli e ci metto 10 secondi ma son limitato
oppure implemento infiniti livelli, ci metto 2 giorni ma sono
libero?
-- 
Non tocca a noi dominare tutte le maree del mondo,
il nostro compito è di fare il possibile per la
salvezza degli anni nei quali viviamo,
sradicando il male dai campi che conosciamo.

 che non puoi fare select * from tabella.
Ok, ora è chiaro.
Come sistema direi che possa andare.
In questo caso, uso la solita semplicità di una struttura id/parentid
con la mia funzione che genera l'albero, ma in più posso generare
un albero a partire da un solo avo e non di tutta la tabella.
in pratica la select * avrà in più un filtro su avo.
Così facendo, l'array da generera si baserà solo sul valore di avo
limitando il recordset ed evitando di dover leggere tutta la tabella
tutte le volte.
(se dovesse esseci un bug nel codice, poi, in memoria avrei solo
l'albero di tale avo, senza impattare su tutti gli altri clienti)


Anche se hai risolto, magari può esserti utile:
http://www.slideshare.net/billkarwin/models-for-hierarchical-data

oppure anche qui (la cosa mi interessa e stò googlando un pò):
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
..e scommetto che usi mysql, altrimenti con 1 query facevi tutto:
http://www.postgresql.org/docs/8.4/static/queries-with.html

 
http://www.slideshare.net/billkarwin/models-for-hierarchical-data
interessate. Grazie.


 
http://www.postgresql.org/docs/8.4/static/queries-with.html
Purtroppo uso mysql


> perchè ho già scritto il codice (15 righe) e funziona...
 
puoi postarle le 15 righe? io ci sto impazzendo!