Koji je dizajn baze najbolji, za kategorije koje su u parent-N-child vezi?

[misko_]

Cao,

Imam nešto ovako.
Postoji tablica lokacije, u kojoj su premljene informacije o lokacijama(naziv, adresa, kordinate itd).
Svaka lokacija može biti vezana sa 0 ili više kategorija(ovo je tipična NxN veza i to mi nije problem).
Problem mi je malo kod kategorija. Nazivi kategorija su npr. smještaj, hotel , kuća, 4zvjezdice, 3 zvjezdice, 2 zcjezdice, banke, bankomati, rent, skuter, auto.
Naravno postoji i logicka veza izmedu pojedinih kategorija.

Smještaj
Hotel
4 zvjezdce
3 zvjezdce
2 zvjezdce
Banke
Bankomati
Rent
Auto
Skuter
Brod


Imam oko 100 kategorija, ovo je samo pojednostavljeni primjer.

Znaci postoje root kategorije, što je u ovom primjeru, Smještaj Banke i Rent.
Samo su sa zadnjom kategorijom vezane lokacije, znači lokacija može biti vezana za 4 zvjezdce, 3 zvjezdce, 2 zvjezdce, Bankomati, Auto, Skuter, Brod.
A između root kategorije i zadnje kategorije, može biti N pod kategorija.

Meni trenutno kategorije u bazi funkcioniraju na sljedeci nacin. Postoji tablica Kategorije i ona ima 2 polja, Id i naziv.
Problem ovoga je sto u bazi nemam nikakvu vezu oko toga kako su povezane kategorije, ta logika mi je hard-codirana u preko 100 fajlova i skoro toliko isto direktorija, kako smo dosli do toga ne bi o tome:1089:

Ja imam par ideja kako da to pojednostavim, pa me zanimaju tuđa mišljena, po mogučnosti bih htio naci neki srebreni metak za ovakav problem.

IDEJA 1.
Da napravim konfiguraciski fajl, xml, u kojem bi mi bile veze između kategorije, nešto tipa

<root>
<kategorija>
<id>45<id> #ovo bi mi bio id iz baze
<naziv>Smještaj<naziv>
<pod_kategorija>
<kategorija>
<id>80<id>
<naziv>Hotel<naziv>
<kategorija>
<pod_kategorija>
<kategorija>
<id>42<id>
<naziv>4 zvjezdce<naziv>
<kategorija>
<kategorija>
<id>41<id>
<naziv>3 zvjezdce<naziv>
<kategorija>
<kategorija>
<id>43<id>
<naziv>2 zvjezdce<naziv>
<kategorija>
<pod_kategorija>
<pod_kategorija>
<kategorija>

Prednost:
Na ovaj nacin bi mi cijela logika bila u jednom fajlu.
Nedostatak:
Ako se doda nova kategorija, moralo bi se ručno prepraviti taj xml fajl.

IDEJA 2.
Prosiriti tablicu kategorije sa:
moze_imati_lokacije (DA/NE)
njegova_nad_kategorija(id on nad kategorije ili N/A)

Prednost:
U bazi bi mi bila logika, kako su kategorije vezane.
Nedostatak:
Nešto mi govori da ovo baš nije način na koji se baze trebaju koristi.
Morao bih napisati neku klasu koja bi prosla kroz cijelu tablicu kategorije i napravilia takvu strukturu u memoriji.

IDEJA 3.
na napravim više tablice tipa: root_kategorija, pod_kategorija1, pod_kategorija2, pod_kategorija3, do jedno 4 ili 5, ne mislim da ce više biti.
Prednost:
Ne vidim nikoju. Ova mi se ideja ne sviđa. možda samo osobno mišljenje.

Kada sada malo razmislim, možda je moje pitanje najbolje preformulirati i postaviti ga na način: Kako se struktura stabla(tree) sprema u bazu ?

Ako ste sve oko procitali, hvala vam na trudu, ako i niste svejedno hvala na pomoci...

[DejanVesic]

Pročitao sam post dva puta :) ali opet sam možda nešto propustio :)

Ovo je klasičan primer predstavljanja hijerarhije u relacionoj bazi.

Ako je zadovoljen uslov da jedna kategorija može imati samo jednog roditelja, rešava se sa:

kategorija: id, naziv, id_parent (id_parent = null -> root kategorija)

Ako jedna kategorija može da ima više roditelja (odnosno list možeš da prilepiš za više od jedne grane), onda se dodaje vezna tabela:

kat_relations ( id_parent, id_child)

U skladu sa izabranim rešenjem i napraviš rutine koje ti crtaju / dovlače podatke za stablo (rekurzivne ili iterativne, šta više voliš).

Šta misliš?

[Dejan Topalovic]

Ideja 3 ni u ludilu! Nemoj ni da pomisljas vise na takve stvari! :D

Ideja 1 bi mozda mogla proci, ukoliko ti je jako bitna brzina izvrsavanja i ukoliko ne mijenjas cesto kategorije. Znaci, parsujes XML fajl (vjerujem da je relativno brze, nego da izvrsavas hijerarhijske upite u bazi za svako ucitavanje stranice) i prikazujes kategorije i druge elemente iz XML fajla. Jos kad bi to mogao nekako cacheovati...

Ideja 2 je najcesce koristena i ima najvise logike za tu potrebu. U Oracleu vec odavno postoje naredbe za koristenje hijerarhijskih upita (CONNECT BY ...), a u MySQL-u se radi na tome.

[misko_]

kada covik ovako utroši uru vremena da napise pitanje i samomu mu postanu jasne neke stvari....

otisao sma malo googlati (http://www.google.at/search?num=100&hl=en&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&hs=6KZ&q=tree+structure+in+db&btnG=Search&meta=)

i pronasao http://www.sitepoint.com/article/hierarchical-data-database/

opisana su 2 rijesenja toga problema



Ako jedna kategorija može da ima više roditelja (odnosno list možeš da prilepiš za više od jedne grane), onda se dodaje vezna tabela:

kat_relations ( id_parent, id_child)



Ok shvacam ali onda ovo nije vise struktura stabla, da li znaš kako se ovakva struktura zove ?

[jablan]

Graf.

Inače, drugo ili prvo rešenje, a verovatno drugo. Obično je zgodno i da se stablo kategorija kešira u memoriji, jer se relativno retko edituje.

[misko_]

Graf.

Inače, drugo ili prvo rešenje, a verovatno drugo. Obično je zgodno i da se stablo kategorija kešira u memoriji, jer se relativno retko edituje.

je mozes dati neki link u vezi toga, shvacam koncept, samo kao to u PHP-u...

[jablan]

Za keširanje pitaš? Nisam baš neki stručnjak za PHP, ali pretpostavljam da možeš da koristiš static promenljive za to, i da kategorije ponovo učitaš kadgod se promene.

Sad, neko sofisticiranije rešenje za invalidaciju keša bi verovatno podrazumevalo neki sistem observera (http://en.wikipedia.org/wiki/Observer_pattern), a verovatno neki PHP frejmvork obezbeđuje sve to (i keširanje i invalidaciju, a moguće i kompletan rad sa hijerarhijskim strukturama).

[DejanVesic]

Jablan je sve lepo odgovorio, da, graf.

Koje ćeš rešenje izabrati isključivo zavisi od biznis zahteva; ako nema šanse da se list kači na više od jednog drveta, onda prvo - jednostavnije je i za implementaciju i za održavanje.

Ako taj uslov nije ispunjen, onda drugo.

Keširanja ima milion; od najprostijeg "dohvati sve što treba iz baze, napravi php / xml fajl i od sada pa nadalje koristi njega" do najkomplikovanijih, koji sve čuvaju u memoriji i slušaju promene itd.

Za početak idi bez keširanja; kada sve funkcionalno proradi, onda razmišljaj o optimizacijama.

[jablan]

Ako taj uslov nije ispunjen, onda drugo.
Pa sad, i nije neophodno da koristi grafove ako mu treba višestruka pripadnost - dovoljni su tagovi. Mnogo se lakše implementiraju, a često hijerarhija i nije preterano bitna.

[bluesman]

Kesiranje je jako vazno ako ima puno kategorija. Imam jedan sajt gde je klijent napravio preko 1000 kategorija koje idu do 6. nivoa u dubinu. Ja generalno pokupim sve kategorije i onda ga promuljam, napravim stablo preko rekurzije i sacuvam u cache file kao obican php array.

Kase se regenerise samo kada on iz administracije promeni nesto u kategorijama, doda novu, izmeni postojecu ili obrise neku.

Ako ima malo kategorija, onda i nije kriticno, mada je lepo da se kesiraju te stavke koje se ne menjaju cesto. Opet, zavisi i od posete, ako ima 10 ljudi dnevno, nema ni neke potrebe za kesiranjem.

Ja sam inace isao "ne-skolski", pa sam u svakoj kategoriji napravio dodatna polja, pored parent_id koji je id "roditeljske" klategorije, imam i "parents" koji drzi sve "roditelje" te kategorije do glavne kategorije, pa tako ako imam kategoriju koja je u 4. nivou, u parents stoji "9,125,903".

Pa ako hoces da prikazes celu granu do vrha radis SELECT * FROM cat WHERE cat_id ON (parents), kao sto rekoh nije skolski ali ubrzava posao.

[ivanhoe]

imas ovde lepo objasnjenjo: http://www.sitepoint.com/article/hierarchical-data-database

Preorder numeracija kategorija je po meni daleko bolja, jer smanjuje broj upita prilikom selecta, na ustrb koplikovanijih izmena podataka, sto ti za kategorije odgovara jer se one retko menjaju

Inace ja imam svoju hack varijantu preordera, koja je super za pretty urls, a to je da sa svakom kategorijom u bazi cuvam i komplet njenu putanju, putanju kao niz ID-jeva, i md5 hash putanje. Kad mi neko na sajtu dodje na /foo/bar/tralala.php, smao treba da uradim jedan select WHERE md5_hash='md5($path)', i imam sve sto mi treba od podataka o celoj toj grani...

[LiquidBrain]

kada covik ovako utroši uru vremena da napise pitanje i samomu mu postanu jasne neke stvari....

otisao sma malo googlati (http://www.google.at/search?num=100&hl=en&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&hs=6KZ&q=tree+structure+in+db&btnG=Search&meta=)

i pronasao http://www.sitepoint.com/article/hierarchical-data-database/

opisana su 2 rijesenja toga problema



Ok shvacam ali onda ovo nije vise struktura stabla, da li znaš kako se ovakva struktura zove ?

Ne treba to smatrati strukturama vec relacijama izmedju tabela... Prvi slucaj je relacija jedan na prema vise, dok je drugi slucaj relacije vise na prema vise, sto automatski zahteva da imash dodatnu tabelu.

detaljnije na tu temu imash ovde: http://articles.techrepublic.com.com/5100-10878_11-5034792.html

[online]

Autor teksta nije nijednom u svom "Further Reading" pomenuo izvanrednu knjigu Joa Celcoa "Trees and hierarchies".

[ivanhoe]

da, to nije losa knjiga, ali nije bas neohpodna, vecinu stvari vec ili znas ili mozes da provalis, narocito ko je imao dodira sa nekim IT predmetom tipa Strukture podataka i slicno..