tree problem - tj zaobilazenje rekurzije

[ Dejan Lozanovic @ 26.03.2004. 22:45 ] @

zna li neko "elegantno" resenje za drvo tj simulaciju direktorijuma ako vam je lakse da shavtite sta mi treba. Prosto resenje je rekurzivni upit :) medjutim ja koliko znam to cudo ima samo oracle i DB2 ostatak sveta je tu "supalj". Ima li nekoga sa laganim pristupm koji bi bio brz kasnije za pretragu tj ako navedem jedan element pa da u pretrazi budu ukljuceni i svi njegovi podelementi.

[ Deep|Blue @ 26.03.2004. 23:19 ] @

http://www.elitesecurity.org/tema/46435

[ _owl_ @ 27.03.2004. 14:17 ] @

Elegantnije resenje se zove nested tree model.

[ -zombie- @ 27.03.2004. 14:40 ] @

lozanović: (valjda sam sada pogodio prezime.. ;)

ako ti ova linkovana tema nije dovoljna, iznesi detaljnije uslove koji su ti važni, pa da smišljamo najbolje rešenje..

moje iskustvo je slično tamo predloženom, samo što sam ja imao i direktorijume i fajlove (oni koji ne mogu da imaju decu, a imaju više osobina od direktorijuma), tj i grane i listove.

rešenje koje se meni pokazalo najpraktičnije je bilo da imam dve tabele, jednu za direktorijume, drugu za fajlove. fajlovi su preko dir_id-a bili vezani za dirove (znači NE preko celog path-a, već su imali samo ime), a dirovi su imali kolonu parent_id i kompletan path, ali se ispostavilo da mi kolona parent_id nije zatrebala ni jedared, već sam sve radio upoređivanjem (delova) path-a.

naravno, tada pod obavezno ide index na polje dir.path. a ja ti predlažem da ipak održavaš i polje parent_id, možda ti nekad zatreba u budućnosti..

[ byTer @ 27.03.2004. 21:03 ] @

Ne znam kako je iko uspeo da odradi ovo. Ovaj drugi model je bas bez veze, jer gde ste videli root direktorijum sa samo deset foldera !!

Ovo je interesantno resenje recimo ako se krene sa dvocifrenim brojevima na pocetku, recimo, mada i to je opet malo... ali interesantno resenje.

Inace i sam sam radio malo na ovome, zato sto mi je trebalo, ali nisam uspeo nikako da dodjem do rekurzije, jer je algoritam ima oblik strele beskonacne duzine:

]]]]]]
]]]]]]]]]]
]]]]]]]]]]]]]
]]]]]]]]]]]]]]]
]]]]]]]]]]]]]]]]]]
sta ovde treba? (ja sam stao kod 5)
]]]]]]
]]]]]]]]]]
]]]]]]]]]]]]]
]]]]]]]]]]]]]]]
]]]]]]]]]]]]]]]]]]

Ovo resenje je slicno kao ono sa parentID i sa LevelID (ustvari struktura je ista). Ali je fora kada treba da prikazes sve foldere (ne mora foldere) odjednom.

Sve u svemu problem se svodi na pravljenje fajl sistema pa neko moze da zaviri u Linux Source posto interesuje i mene.

[ Dejan Lozanovic @ 28.03.2004. 00:27 ] @

Smislio sam model koji mi najvise odgovara :) , tj posto mi je mnogo vazno brzo citanje tj tabela nije mnogo velika pa mogu da si priustim luksuz da je tabela sa relacijom malo komplikovanija.

Primer stabla(direktorijuma)

tablea dir ima (ID, ime), i tabela relacija ima (roditelj,dete,dubina)

tablea relacija

Code:

idR | idD | dubina
------------------------
1    |  1     |   0
2    |   2    |  0
...
8    |   8     | 0
1    |   2     |  1
1     |   3    |  2
2     |   3    | 1
1     |   4    | 1
1     |  5     | 1
6     |  7     | 1
6     |  8     | 2
7     |  8     | 1

Problem je samo sto se za svaki direktorijum unosi n slogova gde je n njegova dubina. Ali lako dobijate primera radi direktorijume koji su podirektorijumi ili koji su nad direktorijumi datog direktorijuma itd... Vrednosti sa dubinom 0 i nisu morali da se unose ali ovako ubrzavaju stvari jos malo, ne morate sami explicitno da dodajete i taj direktorijum koji trazite ako vam treba.

[ Dejan Lozanovic @ 28.03.2004. 00:36 ] @

Citat:

byTer:
Ne znam kako je iko uspeo da odradi ovo. Ovaj drugi model je bas bez veze, jer gde ste videli root direktorijum sa samo deset foldera !!

U sustini moze to da se resi uvodjenjem separatora npr "."

[ byTer @ 28.03.2004. 03:35 ] @

Citat:

Dejan Lozanovic:

Citat:

byTer:
Ne znam kako je iko uspeo da odradi ovo. Ovaj drugi model je bas bez veze, jer gde ste videli root direktorijum sa samo deset foldera !!

U sustini moze to da se resi uvodjenjem separatora npr "."

Shvatam. Hvala, bas mi je ovo trebalo.

[ Dejan Lozanovic @ 28.03.2004. 11:36 ] @

pa malo je komplikovanije da dobijes rezultate ako nemas rekurziju, nazalost ja koliko sam upcen samo oracle i db2 imaju mogucnost rekurzivnog upita. Kod ostalih moras da se snalazis kako znas i umes ;)) ukoliko imas potrebu da radis mnogo unosa u samu tabelu onda ces primeniti jedan od gore navedenih primera, a ako pak trebas da radis brzo citanje onda je ovaj moj primer ipak pogodniji(upisujes relaciju svako sa svakim gde god su povezani elementi) to opet jeste malo komplikovano za unos i update ali ces dobiti brze rezultate za pretragu.

[ byTer @ 28.03.2004. 14:49 ] @

Ja sam ucitavao po nivoima u jedan niz recordseta pa sam iteracijom svaki sa svakim pokusavao da ih povezem po CihldID vezi. A na ovakav nacin nisam mogao da dodjem do rekurzije (ili ne znam).

[ Deep|Blue @ 30.03.2004. 23:35 ] @

pitanje koje mi je palo na pamet kad sam resavao ovo jeste: Da li mi zbilja treba da korisnici posle jednog iscitavanja vide celo stablo???
resenje sa tablom za direktorijume i tabele za fajlove mi se cini veoma jednostavno i efikasno

[ byTer @ 30.03.2004. 23:46 ] @

Na sta ciljas?

Citat:

Da li mi zbilja treba da korisnici posle jednog iscitavanja vide celo stablo???

[ Dejan Lozanovic @ 31.03.2004. 14:01 ] @

Citat:

byTer:
Ja sam ucitavao po nivoima u jedan niz recordseta pa sam iteracijom svaki sa svakim pokusavao da ih povezem po CihldID vezi. A na ovakav nacin nisam mogao da dodjem do rekurzije (ili ne znam).

Pa rekurzija i iteracija su ekvivalentne u teoriskom smislu sada dali ces ti to staviti u neku for petlju ili ces tu petlju zameniti pozivom iste funkcije identicna je stvar. Meni je "skupo" da pozivam 10-15 puta select da bi dobio koji su mi sve pod direktorijumi u igri. Pa sam smislio onu foru da napravim relaciju svako sa svakim i na taj nacin rasteretim pozive ka bazi podataka. tj da jednim elegantnim select pozivom dobijem sve sto mi treba jer imacu mnogo vise citanja tih tabela a vrlo retko unos ili izmenu istih.

[ _owl_ @ 31.03.2004. 14:23 ] @

Citat:

Pa rekurzija i iteracija su ekvivalentne u teoriskom smislu sada dali ces ti to staviti u neku for petlju ili ces tu petlju zameniti pozivom iste funkcije identicna je stvar.

Samo su njihovi rezultati ekvivalentni, sve ostalo je bitno drugacije.

[ Deep|Blue @ 31.03.2004. 20:50 ] @

Citat:

byTer:
Na sta ciljas?

Citat:

Da li mi zbilja treba da korisnici posle jednog iscitavanja vide celo stablo???

ja sam pokusavao nesto slicno, sa malo vecim stablom. na kraju mi je ispalo da je najjednostavnije i najbrze da dam korisniku deo po deo stabla kad zatrazi to. naime kad klikne na neki cvor, ja mu dajem sadrzaj stavki unutar tog cvora. (fazon windows explorera)

[ broker @ 01.04.2004. 23:47 ] @

Hm. Ja nameravam da napavim nesto kao on line knjigu gde mi je sadrzaj naravno u obliku stabla i jedan od zahteva je da se vidi ceo sadrzaj ili njegov deo ali kao stablo (izabrana stavka i sve stavke po dubini).

Nisma jos poceo da se konkretno bavim ovim poblemom nego ga premecem po glavi, ali sa radoznaloscu pratim diskusiju.

[ byTer @ 02.04.2004. 01:27 ] @

Citat:

Dejan Lozanovic:

Citat:

Pa da ali sa jednim prolazenjem desava se da se ponavljaju nizi nivoi vise puta, evo mog algoritma u VBu, mada jos nisam probao ovaj sa separatorom, za koji mislim da ce biti ono krajnje.

Code:

    Set MaxLevel = conn.execute("SELECT Max(Levl) AS MaxL, Min(Levl) AS MinL FROM Categories WHERE Class="&Categ("CatID"))
    MaxLvl = MaxLevel("MaxL")
    If MaxLvl > 0 Then
      Redim Child(MaxLvl)
    End If
    i = 1
    While i <= MaxLvl
      Set Child(i) = server.CreateObject("ADODB.RecordSet")
      Child(i).LockType = 1
      Child(i).CursorType = 3
      Child(i).ActiveConnection = conn
      Child(i).Source = "SELECT * FROM categories WHERE class = "&Categ("CatID")&" AND Levl = " &i& " ORDER BY class, levl, childID"
      Child(i).Open
      i = i + 1
    Wend


        Do Until Child(1).EOF
           WriteChild(1)
              If MaxLvl >= 2 Then
              Do Until Child(2).EOF
                 If Child(2)("ChildID") = Child(1)("CatID") Then
                    WriteChild(2)
                       If maxLvl >= 3 Then
                       Do Until Child(3).EOF
                       If Child(3)("ChildID") = Child(2)("CatId") Then
                          WriteChild(3)
                          If maxLvl >= 4 Then
                          Do Until Child(4).EOF
                             If Child(4)("ChildID") = Child(3)("CatId") Then
                                WriteChild(4)
                                If maxLvl >= 5 Then
                                   Do Until Child(5).EOF
                                      If Child(5)("ChildID") = Child(4)("CatId") Then
                                         WriteChild(5)
                                      End If
                                   Child(5).MoveNext
                                   Loop
                                End If
                             End If
                          Child(4).MoveNext
                          Loop
                          End If
                       End If
                       Child(3).MoveNext
                       Loop
                       Child(3).MoveFirst
                       End If
                 End If
              Child(2).MoveNext
              Loop
              Child(2).MoveFirst
              End If
        Child(1).MoveNext
        Loop
'''''''''''''''''''''''''''''''
    Categ.MoveNext
    Loop

[ mbabuskov @ 02.04.2004. 16:04 ] @

Citat:

Dejan Lozanovic:
pa malo je komplikovanije da dobijes rezultate ako nemas rekurziju, nazalost ja koliko sam upcen samo oracle i db2 imaju mogucnost rekurzivnog upita. Kod ostalih moras da se snalazis kako znas i umes ;)).

MSSQL, Interbase i Firebird imaju rekurzivne stored procedure koje mogu da obave istu stvar.

[ Dejan Lozanovic @ 02.04.2004. 18:39 ] @

pa DB2 i oracle imaju rekurziju unutar samog select poziva bez ugnjezdjenih procedura. Primer DB2 select-a

Code:

with
D(DEO,sadrzi,kol) AS(
VALUES(1,2,7),(1,5,13),(1,4,25),(2,5,14),(2,6,18),(3,6,26),(4,7,21),(6,8,7)
),
potomak(sadrzi,kol) as (
select sadrzi,kol from d where deo=1
union all
select d.sadrzi,d.kol*p.kol from potomak p,d
where p.sadrzi=d.deo
)

select sadrzi,sum(kol) as kol
from potomak
group by sadrzi;