Mysql bináris fa ábrázolás

Adatbázis: SQL, XML DB

Üdv mindenkinek,

Egy hobby projekt keretén belül szeretnék többek között bináris fa ábrázolására megoldást keresni.

Mivel elég nagy fák is lehetnek és a fa nem szabályos (pár száz csomópont esetén is lehet nagyon magas a fa) ezért a mysql rekurzió
nem használható mert az maximum 255 ménységig működik. Így rekurzió helyett iteratív algoritmussal próbálkozok.

Ott tart a dolog, hogy iteratív inorder fa bejárással megkapom az X pozícióját a csomópontoknak de közben szeretném az Y pozíciót is
megállapítani ami a csomópont magassága a fában.

Elakadtam mert nem tudom, hogyan lehetne megállapítni az Y pozíciót (magasság a fában).
Ha esetleg van itt olyan aki érti a témát kérem mutasson utat mi lehet a megoldás.

A segítséget előre is köszönöm. 


/* 
FA 
CREATE TABLE `tree` (`id` BIGINT UNSIGNED, `lchild` BIGINT UBSIGNED, `rchild` BIGINT UNSIGNED);

EREDMENY FA
CREATE TEMPORARY TABLE `tmptree` (`node` BIGINT UNSIGNED, `xpos` INT UNSIGNED, `ypos` INT UNSIGNED);
*/


DROP PROCEDURE IF EXISTS `subtree`;
DELIMITER //
CREATE PROCEDURE `subtree` (
        IN `node` BIGINT UNSIGNED)
        BEGIN

                DECLARE `x` INT UNSIGNED DEFAULT 0;
                DECLARE `y` INT UNSIGNED DEFAULT 0;

                CREATE TEMPORARY TABLE `stack` (`i` INT UNSIGNED AUTO_INCREMENT, `n` INT UNSIGNED, PRIMARY KEY (`i`));

                WHILE ((SELECT COUNT(*) FROM `stack`) OR (`node` IS NOT NULL)) DO

                        IF `node` IS NOT NULL THEN
                                INSERT INTO `stack` (`n`) VALUES (`node`); /* verem - PUSH */
                                SELECT `lchild` FROM `tree` WHERE `id`=`node` INTO `node`; /* bal gyerek */
                        ELSE
                                SELECT `n` FROM `stack` ORDER BY `i` DESC LIMIT 1 INTO `node`; /* verem - POP */
                                DELETE FROM `stack` WHERE `n`=`node`; /* verem - POP */
                                SET `x`=`x`+1; /* következő x pozício */

                                INSERT INTO `tmptree` VALUES (`node`,`x`,`y`); /* csomópont kiírása */

                                SELECT `rchild` FROM `tree` WHERE `id`=`node` INTO `node`; /* jobb gyerek */
                        END IF;

                END WHILE;
                DROP TABLE `stack`;
        END //
DELIMITER ;
  • 7367 megtekintés

( Zsugabubus | 2013. 04. 08., h – 20:49 )

Bár nem tudom, mit ábrázolsz a fán, de BST, netán Red-Black tree nem lenne jobb?

De ezek szerint annak, hogy jobb, vagy bal "gyerek", nincs semmi jelentősége. Szóval lehetne ide valami hatékonyabb adatstruktúrát is találni. Pl., ha gyakran van szükség a mélység meghatározására, viszont kevés az insert vagy a delete, akkor akár a mélységet is el lehetne tárolni egy mezőben. Vagy mondjuk a szülőt is lehetne tárolni, nem csak a gyereket.
Szerintem végig kéne gondolni, hogy milyen műveleteket kell végezni az adatokon, és ez alapján keresni egy megfelelő adatstruktúrát, amihez vannak hatékony algoritmusok a szükséges műveletekhez.

Kicsit bővebben a feladat:

* Adott egy olyan adatszerkezet (bináris fa) ahol alá / fölérendelések vannak és minden csomópontnak legfeljebb 2 alárendeltje lehet.
* Van egy másik tábla ahol szám adatok keletkeznek, törlődnek a csomópontok szerint.
* Sokszor történik beszúrás a fába (előzőleg számított értékek befolyásolják a beszúrás helyét) és törlés a fából.
* Naponta egyszer történik a csomópontok adatainak kiértékelése. Egy csomópont értéke = saját érték + bal gyerek érték + jobb gyerek érték
* A kiértékelést "post order" bejárással gondoltam elvégezni. (alulról fölfelé egyszer bejárva a teljes fát)
* A kiértékelt fa tetszőleges részét (limitált magasságú részfával) kellene grafikusan ábrázolni a csomópont értékeit feltüntetve.

--
maszili

Ezt így sajnos nem tudom megbecsülni. A fába írás esetén is van olvasás mert az előzőleg számított érték alapján dől el, hogy hová kerül az új csomópont ha vannak elágazások (2 gyerek közül merre tovább). Illetve a grafikus megjelenítés esetén is olvasás történik.

--
maszili

Aha...hát most amit még hozzá tudok tenni, az az, hogy ha jól néztem, amikor push-olsz a stackbe, az y++, amikor pop-olsz, az y--
A select count(*)-ot meg valahogy kiirtanám minden egyes iterációból.
Meg ha mindenképp tárolt eljárásban csinálod, a stack tárolása adatbázis táblában helyett nincs valami in-memory izé a MySQL-ben?

Sajnos az Y értéke nem olyan egyszerű mint elsőre látszik. Én is arra gondoltam, hogy a stack-ben lévő elemek száma adja az aktuális elem fa beli magasságát. De sajnos az nem jó mert jobb gyerek bejárása esetén minden alkalommal egyel elcsúszik és a végén teljesen hibás értékek keletkeznek.

Közben az lett a megoldás hogy a stack-ban tárolom az aktuális elem Y értékét ami a gyereke esetén egyel több. Tehát a következő modosításokkal jól működik a program: 


CREATE TEMPORARY TABLE `stack` (`i` INT UNSIGNED AUTO_INCREMENT, `n` INT UNSIGNED, `d` INT UNSIGNED DEFAULT 0, PRIMARY KEY (`i`));

/* STACK PUSH esetén*/
SELECT `d` FROM `stack` WHERE `n`=FLOOR(`node`/2) INTO `y`;
INSERT INTO `stack` (`n`,`d`) VALUES (`node`,`y`+1);

/* STACK POP esetén*/
SELECT `d` FROM `stack` ORDER BY `i` DESC LIMIT 1 INTO `y`;

Keresetm kultúrált verem megoldást mysql esetére de sajnos ennél jobbat nem találtam.

Milyen gyorsabb / egyszerűbb módszerrel lenne érdemesebb megvizsgálni, hogy van-e elem a veremben?

--
maszili

( petya | 2013. 04. 08., h – 21:05 )

Ez igy borzasztoan lassu lesz. Nezz utana a nested setnek vagy a closure tablenek. En alkalmazaslogikara nem hasznalnek tarolt eljarast.

A nested sets -el kapcsolatban ezt írják:

Nested sets are very slow for inserts because it requires updating lft and rgt for all records in the table after the insert.

Ha esetleg több százezer vagy milliós nagyságrendű adat lesz a fában akkor ez lehet, hogy nem lesz jó.

--
maszili

( lx | 2013. 04. 08., h – 21:19 )

Esetleg? 


create table tree (
node varchar(1024) not null,
value $adatod_tipusa
);

create unique index ix_tree_0 on tree (node);

insert into tree values ('0', $gyokeradat);
insert into tree values ('0.0', $gyoker_bal);
insert into tree values ('0.1', $gyoker_jobb);
insert into tree values ('0.0.0', $gyoker_bal_bal);

level = length( node) % 2 (level_of_root = 0)

( hory v | 2013. 04. 08., h – 23:08 )

Pont hasonlo feladat van nalunk is. A problema igazabol a hierarchikus szerkezet sql-ben torteno tarolasa es lekerdezese.

Baromi sok ido el***asa utan allithatom, hogy felesleges SQL alapokra epiteni a lekerdezest. Sose fogod gyorsra kihozni, szoval ha a teljesitmeny barminemu szempont, akkor a megoldas az adat benyalasa memoriaba es ott cache epitese. Nem kell komolyra gondolni, node-onkent egy bal+jobb pointer (8 byte) es egy rekord azonosito (tipikusan 4 byte). Ez alignment-tel egyutt is 16 mega millio node-onkent. Ennel sokkal tobbet zabalna le barmelyik SQL adatbazis cache cimen, es akarmilyen nyelven csinalod, baromi gyors.

Architekturalisan tekinthetsz erre ugy, mint egyfajta SQL extensionre: mivel az SQL elegge agyhalott szulemeny (a stored procedure-krol ne is beszeljunk), kenytelen vagy a DAO reteget kicsit kiboviteni az application-od alatt.

Mielőtt teljesen meggyőzzük egymást arról, hogy halva született ötlet az egész, említsük meg, hogy manapság komplett XML struktúrákat tárolunk RDB-ben, kb. úgy, ahogy lejjebb vázoltam: az xpath a kulcs.
Ahhoz képest a bináris fa lehetséges node-címei pehelysúlyú problémát jelentenek.

Az, hogy sql tárolt eljárás helyett más program valósítja meg a bináris fa inorder bejárását miért jobb mint a tárolt eljárás? Én úgy gondolom, hogy ha megspórolom az adatok olvasását az SQL szerverről majd azok visszatöltését az SQL szerverre akkor előbbre vagyok. Vagy rosszul gondolom?

Továbbá az, hogy máshová helyezem az algoritmust attól még a probléma fenn áll mert akkor is szükség van az inorder bejárásra és kellene az aktuális elem fa beli magassága is.

--
maszili

Amennyiben a 0.[01].[01]... alakú sztringek a node-azonosítók, a bejárás adott node-tól kb. ennyi:

select node, value from tree
where node like '$adottnode%'
order by node
;

A szint meghatározása pedig mint lent.
Adott szint összes elemének kiírása ebből kifejezhető.
Adott node szülőjének meghatározása pedig egy substr és length segítségével összevágható.

Biztosan lassabb, mint egy konkrétan a célra hardkódolt pointerfa, de biztosan rugalmasabban kezelhető.

Ez XML-re tök jó: egyszer leparsolod a doksit, betöltöd, és utána már csak lekérdezések vannak.
Viszont mondjuk egy komplett részfa mozgatása itt a hozzátartozó összes sor update-elésével jár, míg az eredeti koncepcióban egy mezőt kell csak módosítani. Szóval nem mindegy, hogy milyen műveleteket akarunk tudni egyszerűen elvégezni.

Én úgy gondolom, hogy ha megspórolom az adatok olvasását az SQL szerverről majd azok visszatöltését az SQL szerverre akkor előbbre vagyok. Vagy rosszul gondolom?

Kérdés, hogy mit veszítesz a vámon cserébe. Ha áthoztad az adatokat, akkor az általad választott memóriastruktúrában tudod tárolni - te érted az adatstruktúrádat, az sql szerver meg nem. Továbbá te tudod struktúráltan cache-elni, az sql szerver meg csak sql struktúrában tudja, tehát a kettő közti konverziót minden egyes lekérdezésnél el kell végezni.
És akkor arról nem is beszéltünk, hogy az sql scriptnyelvéhez képest mennyivel hatékonyabb nyelvet tudsz választani.

Nyilván létezhet olyan eset, amikor a tárolt eljárás nem, vagy nem igazán rosszabb hatásfokú.

Majdnem mondtam, hogy nem muszaj SQL-ben irni a tarolt eljarast, de aztan rajottem, hogy de, mivel MySQL. (Postgresben 4 nyelv van gyarilag (pl perl), meg egy kupac kulso modulkent (java, stb.): http://www.postgresql.org/docs/9.2/static/external-pl.html )
Vagy van valakinek ujabb infoja? MariaDB?

( DieHappy | 2013. 04. 09., k – 14:01 )

Nem sokat ertek az SQL-hez, szoval csak felmegoldast tudok. Amikor csaladfat kellett rajzoltatnom, akkor egy kvazi globalis x[y] tombot hasznaltam. Rekurzivan vegig kell menni a fan, lerajzolni az elso elemet aminek nincs gyereke, es az x[szint] -be berakni a koordinatat. Ha lesz valamikor egy kovetkezo elem ezen a szinten, akkor x[szint] + akarmi-re kell rakni, es frissiteni x[szintet]. Ha szebben akarod, akkor azt is mondhatod, hogy az x[szint] is befolyasolja x[szint-1] -et, stb. Van egy graf-rajzolo program unix alatt, a dot. Azt is hasznalhatod vizualizaciora, az kicsit szofisztikaltabb: megcsinalja a fat, azutan globalisan optimalizal rajta, hogy szebb legyen.

( asch v | 2013. 04. 10., sze – 12:36 )

Az ilyenkor szokásos kérdésem: hány csomópontra tervezed a programodat összesen (worst case)? Mennyi adat egy csomópont?
Az adatbázisokat RAM-ba el nem férő adatmennyiség kezelésére találták ki blokk-rendszerű random access eszközökön (diszk). Ha befér az adatmennyiség a RAM-ba, akkor nem érdemes adatbázist használni.

Ha egymillió csomópont esetén (annyi nem nagyon lesz) elfogadható sebességgel működik a program akkor az számomra kielégítő. Majd készítek teszt adatokat és kiderül.

A fa csomópontjai csak a relációkat (node,left,right) és a csomópontonkénti értékeket (num) tárolják, tehát 4 adat összesen. A többi adatok külön táblákban vannak.

Lehet, hogy elfér a memóriában de nem szeretnék egy komplett mysql-t készíteni a szükséges funkcionalitásokkal. Én úgy gondolom, hogy a mysql készítői nem voltak ostobák és a rendelkezésre álló memóriát optimálisan használva nem a merevlemezt fogja zörgetni ha nem muszály. Ha adatmódosítás történik akkor úgy is ki kell írni a merevlemezre és úgy gondolom a mysql ezt jobban csinálja mint ahogy én meg tudnám írni. Ebből a megfontolásból kész adatbázis kezelő programot (mysql) használok saját program helyett.

--
maszili