Newsgroup: it.comp.www.php
Titolo: Struttura ad albero

scusatemi se lo posto anche qui (non è strettamente IT) ma ho un po'
di urgenza di risolvere questo problema.
Dovrei creare la classica struttura ad albero basata su un db.
Ho una tabella Strutture e una Sottostrutture. Ogni Struttura può
ramificarsi in diverse sottostrutture e così ogni sottostruttura (in
teoria senza vincoli di numero ma praticamente non credo si andrà
oltre i 5-6 nodi consecutivi). i record di Sottostrutture hanno un
campo id_padre_assoluto (la Struttura "root"), un campo
id_padre_relativo (la Sottostruttura immediatamente superiore) e un
campo livello che indica la profondità del nodo.
Dato che è la prima volta che mi trovo ad affrontare un problema di
questo tipo, ho fatto qualche ricerca con google e ho visto che la
tecnica più popolare sembra quella dei "nested sets" di Celko solo che
non ci ho capito un gran che e nell'immediato non ho neanche  molto
tempo per studiarlo.
Sapreste darmi un suggerimento per un campo "flag" calcolato o
derivato dagli altri con cui possa ordinare esattamente i record di
Sottostrutture? Al limite, dato che il db non dovrebbe risultare
enorme, sacrificando qualcosa sul piano prestazionale.
Grazie.
P.S. - in alternativa basterebbe anche di un link a qualcosa tipo
"Celko nested sets for dummies".

 "Celko nested sets for dummies".
Class: Joe Celko Nested Sets
http://www.phpclasses.net/browse/package/1374.html
-- 
I am what I am, I do what I can
Sei un newbie? Leggi questo 
http://url.repository.biz/go/1
Inviare email con allegati? 
http://url.repository.biz/go/1Z
Cerchi un programmatore PHP/MySQL? 
http://url.repository.biz/go/1Y
L'uomo, conscio di sbagliare, persevera.


http://www.phpclasses.net/browse/package/1374.html
Mi sfuggono parecchie cose (sono un dilettante, mai usato classi), ma
queste più di altre:
	$FieldLeft => Field name for table nasted set left field 
	$FieldRight => Field name for table nasted set right field
In che senso "left" e "right"?
    $FieldDiffer => Field name used to manage more than one type of
nasted set in the same table
	$FieldOrder => Field name for table nasted set order field   
	$FieldIgnore => Field name for tablr nested set ignore field 
	$TransactionTable => Name for table used to manage transactions
???

 	$TransactionTable => Name for table used to manage transactions
Nel senso di "sinistro" e "destro". La classe e' stata creata per poter
essere utilizzata au qualsiasi tabella che supporti la struttura base
dei Celko Nasted Sets. Questo tipo di tabella DEVE contenere come
minimo i seguenti campi:
IDNode: ID che identifica il singolo nodo 
IDParent: ID che identifica il nodo "genitore"
NSLeft: Campo Nasted Set sinistro (vedi descrizione funzionamento NS) 
NSRight: Campo Nasted Set sinistro (vedi descrizione funzionamento NS) 
NSLevel: Livello di profondità nella gerarchia (0 = nodo root)
NSOrder: Ordine dal SX a DX nel quale e' inserito il nodo, utilizzato
per inserire in una posizione specifica un nodo tra altri nodi dello
stesso livello e con lo stesso nodo "genitore"
NSDiffer: Campo utilizzato come discriminante per gestire gerarchie
multiple di nodi all'interno della stessa tabella
NSIgnore: Campo utilizzato in fase di spostamento, inserimento ed
eliminazione dei nodi
Tutti i nomi dei campi possono essere personalizzati per mezzo delle
mmbri della classa.
Poiche' le versioni piu' diffuse di MySQL non forniscono il supporto
per le transazioni viene poi utilizzata una tabella separata per
gestire le transazioni.
Un po' di link sui dati gerarchici nei DB relazionali:
http://www.sitepoint.com/print/1105
http://www.intelligententerprise.com/001020/celko1_1.shtml
http://www.dbmsmag.com/9603d06.html
http://www.sqlteam.com/item.asp?ItemID=8866


 campo livello che indica la profondità del nodo.
...
mi sfugge qualcosa...
per ipotesi assumiamo che tutte le Strutture 'Si' facciano capo a una 
superstruttura, volendo fittizia, detta r.
la tua rappresentazione è ora un albero radicato non bilanciato in cui 
il primo livello sarà rappresentato da soli nodi Struttura, il secondo 
livello da nodi Sottostruttura, i livelli sottostanti saranno le 
"ramificazioni" dei componenti della sottostruttura.
Ammesso che le Sottostrutture siano entità disgiunte e che gli  elementi 
di una sottostruttura e le varie ramificazioni siano univocamente 
assegnati ad una e una sola sottostruttura hai un albero di nodi unici.
Per rappresentare questa struttura è sufficiente che ogni elemento sia 
rappresentato dalla coppia (IDNodo, IDPadre).
L'albero di partenza sarà rappresentabile con la lista di coppie:
(S0,r);(S1,r);....(Sn,r) dove n è il numero delle Strutture presenti.
una sottostruttura Ssk "figlia" di Sj si rappresenta con (Ssk,Sj) e così 
via.
A questo punto prima di andare avanti sarebbe bene capire che tipo di 
operazioni vengono effettuate con frequenza per capire che cosa potrebbe 
convenire fare, la gestione di un albero come lista di nodi è 
relativamente semplice per quello che riguarda l'aggiunta di nodi e di 
sottoalberi, leggermente più "costosa" la rimozione dei sottoalberi o 
una eventuale fusione di più sottoalberi.
Però alcune di queste cose dipendono fortemente dal problema che 
rappresenti: Se è un organigramma o una rappresentazione di categorie 
merceologiche o di 3d in un forum è un cosa...
Ciao Gianfranzo
-- 
ICQ#: 21258924 Nick Gianfranzo
Home page 
http://www.gianfranzo.it
Gianfranzo è contro la guerra
"dopo tutto, gli angeli non sono altro che dei volatili" D. Pennac


http://www.sqlteam.com/item.asp?ItemID=8866
Molte grazie.
Andrň a studiarmeli.

merceologiche o di 3d in un forum è un cosa...
Si tratta della rappresentazione di realtà "aziendali".
Diciamo che una root è "Cicciobello spa". Da questa si diramano due
sottostrutture: filiale di Roma e filiale di Milano.
La filiale di Roma ha due sottostrutture: ufficio acquisti e ufficio
vendite. E così via.
Il mio problema è mostrare il tutto in modo corretto in forma di
"albero".

 "albero".
nel caso che cercavo di spiegare potresti avere una sola tabella:
ID;ParentID;Descrizione;.....
per cui l'albero del tuo esempio sarebbe rappresentato da:
1 1 CiccioBelloSpa
2 1 Filiale Roma CiccioBello
3 1 Filiale Milano CiccioBello
L'albero è
    1
   / \
  2   3
ovvero (1,1);(2,1);(3,1).
ci sono due cose interessanti in questa rappresentazione: sono root 
tutti i record che hanno ID e ParentID coincidenti; Sono i figli del 
nodo x tutti quelli che hanno ParentID=x; Il nodo n ha un figlio se 
esiste un ParentiID=n;
Aggiungere un nodo è banale: è sufficiente inserire una coppia 
ID-ParentID; cambiare radice ad un sottoalbero anche è una operazione 
banale: è sufficiente modificare il ParentID della radice del 
sottoalbero che cambia con l'ID dell'elemento su cui il sottoalbero 
viene innestato:
supponi che CiccioBello Spa sia acquisita da ACME (5 5 ACME) che produce 
un albero: (5,5)(1,5)(2,1)(3,1) ora CiccioBello Spa passa da ACME a GGGG 
(6 6 GGGG) il nuovo albero si genera semplicemente modificando il nodo 
(1,5) in (1,6).
La cosa più complessa è la rimozione perché devi procedere eliminando 
prima le foglie e via via fino alla radice.
Spero ora di essere stato più chiaro.




Allora...
Nel frattempo (e nella mia niubbaggine) mi sono inventato il sistema
qua sotto. Lo so che è brutto, goffo etc etc, però PARE che funzioni.
Se tu o altri poteste dargli una breve occhiata e segnalare eventuali
falle o carenze ve ne sarei estremamente grato.
Il tutto è preposto alla creazione di un campo "tree" (formato
1.1.2etc) che serve all'sql per ordinare esattamente i record. Non ci
dovrebbe essere la necessità di aggiunte o correzioni a posteriori
quindi potrebbe anche reggere.
Suppongo che il tutto funzioni solo grazie a mysql che, se c'è da
calcolare) trasforma automaticamente le stringhe in numeri.
Le diciture "_str" e "_substr" stanno per "struttura" e
"substruttura".
$dip_str = $_POST['dip_str'];
$dip_substr = $_POST['dip_substr'];
$id_substr = $_POST['id_substr'];
// non dipende da alcuna sottostr.
if($dip_substr == "(nessuna)")
	{ $dip_substr = 0;
	$livello_substr = 1;
	$sql = "select max(tree) from sottostrutture where dip_str =
'$dip_str'";
	$query = mysql_query($sql, $conn);
	$row = mysql_fetch_row($query);
	$first_point_pos = strpos($row[0], ".");
	$max_root = substr($row[0], 0, $first_point_pos);
	$tree = $max_root + 1; }
// dipende da una sottostr.
else
	{ // trasforma il nome in id
	$dip_substr = enc($dip_substr);
	$sql = "select id from sottostrutture where nome = '$dip_substr' and
dip_str = '$dip_str'";
	$query = mysql_query($sql, $conn);
	$row = mysql_fetch_row($query);
	$dip_substr = $row[0];
	// calcola il nuovo livello
	$sql = "select livello from sottostrutture where id =
'$dip_substr'";
	$query = mysql_query($sql, $conn);
	$row = mysql_fetch_row($query);
	$lev_substr = ($row[0] + 1);
	// controlla se allo stesso livello esistono sottostr. dipendenti
dalla dalla sottostr. superiore
	$sql = "select tree from sottostrutture where (dip_str = '$dip_str'
and dip_substr = '$dip_substr' and livello = '$lev_substr')";
	$query = mysql_query($sql, $conn);
	$num_rows = mysql_num_rows($query);
	// se ne trova
	if($num_rows > 0)
		{ // trova il tree più alto tra le sottostr. dello stesso livello
dipendenti dalla sottostr. superiore
		$sql = "select max(tree) from sottostrutture where (dip_str =
'$dip_str' and dip_substr = '$dip_substr' and livello =
'$lev_substr')";
		$query = mysql_query($sql, $conn);
		$row = mysql_fetch_row($query);
		$max_tree = $row[0];
		// trova l'ultimo punto della stringa per vedere dove inizia
l'ultima frazione (quella da incrementare), elimina il punto e la
separa
		$last_point = strrpos($max_tree, ".");
		$last_fract = substr($max_tree, ($last_point + 1));
		// incrementa l'ultima frazione e la salda nuovamente al resto
della stringa
		$new_last_fract = $last_fract + 1;
		$tree_rest = substr($max_tree, 0, ($last_point + 1));
		$tree = $tree_rest . $new_last_fract; }
	// se invece non ne trova
	else
		{ // trova il tree della sottostr. superiore e inizia una nuova
serie di frazioni
		$sql = "select tree from sottostrutture where (dip_str =
'$dip_str' and id = '$dip_substr')";
		$query = mysql_query($sql, $conn);
		$row = mysql_fetch_row($query);
		$tree_dip_substr = $row[0];
		$tree = $tree_dip_substr . ".1"; }
	 }

qua sotto. 
Questo non toglie che mi guarderò attentamente quello che avete
scritto tu e Setec, anche se non riesco a cogliere bene la differenza
tra i due tipi di "albero".
Purtroppo no ho alcuna formazione teorica sulle strutture logiche.