[MySQL + PHP] Optimalny vypis strukturovaneho menu

[reach]

Riesim jeden problem a niezeby som nevedel ako to riesit, ale chcel by som sa opytat na najoptimalnejsie riesenie.
Mam strukturovane menu typu:

Kód: Vybrat vše

1. hlavna kategoria
  1.1 podkategoria
  1.2 podkategoria
  1.3 podkategoria
2. hlavna kategoria
  2.1 podkategoria
  2.2 podkategoria
  2.3 podkategoria
    2.3.1 podpodkategoria
    2.3.2 podpodkategoria
  2.4 podkategoria
3. hlavna kategoria
...

zatial je to iba hlavna kategoria a podkategoria, neskor mozno bude aj pod-podkategoria. ale nepredpokladam ze ich bude viacej
Potom mam nejaku polozku, ktora moze patrit do lubovolnej kategorie, pripadne pod-kategorie, pripadne pod-podkategorie a moze naraz patrit aj viacerym kategoriam pripadne podktagoriam. cize:

Kód: Vybrat vše

polozka 1 - 1
polozka 2 - 1.1, 1.3
polozka 3 - 2.2, 2.3.1
...

Ide o to, ako si to mam ukladat do databazy tak, aby som nasledne mohol vyhladavat podla lubovolnej kategorie/podkategorie. To jest, aby ked zadam ze hladaj vsetko v "kategorii 1" najde mi "polozku 1" aj "polozku 2". Ak zadam, ze zobraz vsetko z "kategorie 1.1" tak tiez zobrazi "polozku 1" aj "polozku 2". Ale ak zadam vsetko z kategorie 1.2 tak najde len "polozka 1" pretoze ta patri vsetkym podkategoriam "kategorie 1".
Zatial su vsetky kategorie v 1 tabulke a podkategorie sa viazu cez "parent_id". Samozrejme, je mozne tuto tabulku zmenit, ak je to potrebne.
Verim, ze som sa vyjadril zrozumitelne. Ak nie, rad upresnim detaily. Dakujem, za kazdy hodnotny prispevok.

//edit: opraveny nazov thread-u
// mbing : Téma přesunuto ● z Programování do Tvorba webových stránek a aplikací.

[herbi2]

uplna klasika, trocha hledani a mas i algoritmus na prochazeni takovych struktur (napriklad na interval.cz sem to tusim kdysi videl)

pseudo kod:

Kód: Vybrat vše

table kategorie:
parent_id integer, //odkaz na "nadkategorii"
id integer primary key,
nazev varchar // nazev kategorie


table vazba:
  kategore_id integer,
  polozka_id integer

table polozka:
  polozka_id integer;
  nazev varchar,
  popis varchar,
  ...pripadne dalsi atributy


je dobry pridat i cizi klice a dalsi integritni omezeni(na coz mysql neni uplne nejvhodnejsi). Navic vkladani do takovyhle struktury samozrejme znamena celou sadu dotazu(insertu) do databaze...coz se ti muze zdat zbytecne slozity, ale ver ze jinak to nejde.

[reach]

No, toto riesenie je zjavne najjednoduchsie, ovsem neviem ci aj najoptimalnejsie. pri vyhladavani je potrebne bud robit rekurzivny dotaz alebo niekolko left join-ov, co tiez nie je najrychlejsie.
mna napadlo riesenie:

Kód: Vybrat vše

tabulka vazba:
  kategorie_id integer,
  podkategorie_id integer,
  podpodkategorie_id integer,
  polozka_id integer

to by sice pomohlo pri vyhladavani "smerom dole" ale nie "smerom nahor".

[logout]

Ahoj,

Příslušnost do více kategorií rozhodně řeš speciální tabulkou
<polozka> - <kategorie>. Tím se problém redukuje jak efektivně dostat strom do relační databáze.
Jsou rúzné techniky. Teď jsem si vzpoměl na dvě:

1) poměrně blbá, ale někde stačí: indexování pomocí řetězce, kdy strid = <stridrodiče>.<idmě>.
Příslušnost do skupiny se řeší pomocí kategorie like "<strid skupiny>%"
No a příslušnost do nadkategorie opačně
Příslušnost do skupiny se řeší pomocí <strid skupiny> like
"<kategorie>%"
Nevýhoda je, že je to pomalé
Výhodou je jednoduché přidávání
Místo oddělovače tečkou můžeš určit pevnou délku identifikátoru úrovně (budeš omezen max. počtem podkategorií v jedné kategorii,
ale bude to o něco málo rychlejší).

2) Pravolevé očíslování.
Když máš strom očísluješ ho tak, že ho prohledáváš do hloubky a každému uzlu přiřadíš jedno číslo při vstupu a druhé při odchodu ze stromu.
Např

Kód: Vybrat vše

      1,12
     /    \
    2,7  8,11
   /   \    \
  3,4  5,6 9,10


Výhoda je rychlé vyhledávání, pokjud čísla nazvu left a right, tak když hledáš a v kategorii <a,b>, tak uděláš dotaz
left BETWEEN a AND b.
Když všechno co náleží do "nadkategorií" kategorie <a,b>, tak
left < a AND right > b.

Nevýhoda je, že při přidávání musíš přečíslovat tabulku
UPDATE kategorie SET right = right + 2 WHERE right > PridanyRight
UPDATE kategorie SET left = left + 2 WHERE left > PridanyLeft
Šlo by to řešit i tak, že si mezi číslama ponecháš "mezery" a tabulku přečísluješ teprve až Ti někde mezera dojde.
Pokud však nejsou inserty příliš časté, nebo jsou v dávkách, je to ideální řešení.

MAtyáš

[logout]

je dobry pridat i cizi klice a dalsi integritni omezeni(na coz mysql neni uplne nejvhodnejsi). Navic vkladani do takovyhle struktury samozrejme znamena celou sadu dotazu(insertu) do databaze...coz se ti muze zdat zbytecne slozity, ale ver ze jinak to nejde.

Ne dobrý, ale neudělat to je prasečina . Navíc v mysql to jde, akorát musíš použít InnoDb tabulky.

Ještě doplník tomu pravo-levému očíslování: Sám to užívám a řeším to tak, že struktura je stejná jako navrhoval herbi2 s tím, že
kategorie má ještě pole pravy,levy: integer a pak mám funkci, která strom projde a pravolevě očísluju (pokud bys měl zájem, můžu jí sem dát).


Matyáš

[Z@chi]

Preti si tento clanek:
http://interval.cz/clanky/metody-uklada ... atabazich/
moznosti jak to udelat je hodne. Nejlepsi je obsem ten posledni zpusob, ktery je oznacen jako traverzovani kolem stromu. Byla tady o nem uz rec.
Mam pro nej udelanou celou tridu. Je zde sice slozita editace, ale vypis stromu je potom velice jednoduchy a hlavne nezatezuje databazi.

[reach]

to logout:
ak by Ti to nevadilo, budem rad, ak tu zverejnis svoju funkciu na pravo-lave ocislovanie.

este ma napadla jedna otazka: ako to riesite ak potomok moze mat 2 a viac rodicov?

[logout]

Ahoj,
v týdle metodě nemůže mít potomek víc rodičů. Pokud chceš, aby jen listy (položky kategorií) mohli mít víc rodičů, tak udělej speciální tabulku kategorie s tím číslováním, pak tabulku s položka kategorií a tabulku tato položka patří do této kategorie.
Pokud chceš, aby i kategorie mohly patřit do více nadkategorií, tak mě nenapadá teď nic jiného než udělat tabulku kategorií (plochou, bez nějaké stromové struktury) a pak strom (tabulku s pravolevým číslováním), jehož položky budou odkazovat na kategorie: tzn. každá kategorie se může vyskytnout ve stromu vícekrát.

Ta funkce

Kód: Vybrat vše

<?
require_once('../lib/conf.php');
require_once('../lib/database/sql.connect.php');

function MakeTree($table)
{
echo "<pre>";
MakeTreeWork($table);
echo "</pre>";
echo "<b>Hotovo</b>\n"; 
}

function MakeTreeWork($table,$id=0,$root=0,$count=0,$level=0)
  {
  if($level++>40)
    die("Prekrocena hloubka $level, koncim");
  global $SQL;
  $id=(int) $id; 
  $res=$SQL->Query("SELECT nazev,id FROM $table WHERE rodic ". ($id==0? "IS NULL" : " = $id") );
  if($root!=0)
   $myroot=$root;
  while($row=$res->Row())
      {
      if($root==0)
       $myroot=$row['id'];
      $levy=++$count;
      if($level<=2)
         {
         for($r=1;$r<$level;$r++)
             echo " - ";
         echo $row['nazev']."\n";   
             }
      $count=MakeTreeWork($table,$row['id'],$myroot,$count,$level);
      $SQL->Update($table,Array("levy","pravy","koren"),Array($levy,++$count,$myroot),"id = ".(int)$row['id']);
      }
  $res->Close();
  $SQL->Commit();
  return $count;
  }


Volá se to MakeTree("názevTabulky");
Nechám Ti ji tak jak je, asi si ji budeš muset trochu upravit.
V tabulce to updatuje sloupce
levy, pravy, koren
levy, pravy nastaví na pravolevé číslování,
kořen nastaví na id kořenu stromu.
(Mám v tabulce víc stromů, takže se mi hodí i údaj, do kterého stromu patří daný údaj, Ty si to budeš moct odmáznout).
Předpokládá v tabulce sloupec rodic, ve kterým je (kupodivu) id rodiče.
Jo, a dotazy tam mam řešený pomocí svý třídy, tak Ty si budeš muset trošku přepsat (ten update zhruba takhle:
UPDATE $table SET "levy"=$levy, pravy = ++$count
WHERE id = ".(int)$row['id'])
Máš tam i proměnnou level, kdybys chtěl mít u prvku i informaci o tom, jak je "hluboko".
Matyáš

[reach]

to logout:
vrela vdaka, urcite to velmi pomoze...

[Vebloud]

Pokud má víc rodičů, už to nění strom, ale obecný graf. Jednoduše to lze udělat tak, že budeš mít tabulku s kategoriema a vazby budeš dělat přes externí tabulku, kde budeš mít ID rodiče a ID potomka a máš vyřešeno. Jednosduchá editace záznamů, poněkud méně efektivní výpis.

A tady už se rekurzivnímu výpisu nevyhneš a musíš si dávat majzla, aby jsi neskončil v kruhu.

P.S.: Opravdu výstižný název threadu

[logout]

Ahoj,
nebude to obecnej graf, nebudou tam cykly (to by kategorie a musela bejt v kategorii b a zároveň b v a, což neodpovídá realitě). Bude to "zdrcnutej strom", prostě strom, až na to, že k z vrcholu může být více cest k uzlu. A to jde elegantně vyřešit tak, že všechny vrcholy, do kterých vede více cest "rozštěpím" a odkážu na stejný prvek v jiný tabulce. Tzn. budu mít tabulku se stromem, kde prvky stromu budou idčka z kategorií v samostatné tabulce:
table strom
{
id,
rodic,
levy,
pravy,
idkategorie
}

table kategorie
{
id,
nazev,
...
}

Pro vyhledávání nemusím používat rekurzi: např. na všechny kategorie náležící do kategorie s id=q je

Kód: Vybrat vše

SELECT distinct k2.id FROM
     (kategorie k INNER JOIN strom m on (k.id = m.idkategorie))
   INNER JOIN
     (kategorie k2 INNER JOIN strom m2 on (k.id = strom.idkategorie))
   ON
      (k.levy <= k2.levy AND k.pravy >= k2.pravy)
WHERE
   k.id=q


Vypadá to složitě, ale pro DB je to rychlý, efektivní.

Matyáš

[reach]

to Velbloud:
doteraz som to riesil tak ako si napisal ty, ale nezdalo sa mi to velmi efektivne a tak som sa chcel opytat ako to riesia ostatni.
co sa tyka nazvu thread-u tak predtym tam bol nazov (nepamtam presne aky) ale niekto to premenoval len na '[MySQL + PHP]'

[logout]

Eeee, teď jak se na to koukám, tak jsem ten SQL dotaz napsal blbě,
trošku jsem tam poplet tabulky, správně je

Kód: Vybrat vše

SELECT distinct k2.id FROM
     (kategorie k INNER JOIN strom m on (k.id = m.idkategorie))
   INNER JOIN
     (kategorie k2 INNER JOIN strom m2 on (k.id = m2.idkategorie))
   ON
      (m.levy <= m2.levy AND m.pravy >= m2.pravy)
WHERE
   k.id=q


ale myšlenka je snad jasná : Vezmu kategorii, k ní všechny záznamy ve stromě, k nim všechny podřízené záznamy ve stromě a k nim Id-čka kategorií (a DISTINCT, aby se neopakovaly).
Matyáš

[esem]

(skoro) offTopic:
Optimalni znamena nejlepsi z moznych. Nejoptimalnejsi je nesmysl. Oprav si nadpis. Vyjadrujes se jak ti debilove politici. Doufam, ze mas na vic nez ti idioti vytrzeni z reality, kteri si musi vymyslet nesmyslne tvary podobneho razeni.

[Z@chi]

(skoro) offTopic:
Optimalni znamena nejlepsi z moznych. Nejoptimalnejsi je nesmysl. Oprav si nadpis. Vyjadrujes se jak ti debilove politici. Doufam, ze mas na vic nez ti idioti vytrzeni z reality, kteri si musi vymyslet nesmyslne tvary podobneho razeni.

ach jo. kdyby jsi radeji pomohl s resenim tohoto topicu. ty radeji kritizujes nadpis.