TechBlog cikkei

Részfa lekérdezése

Van egy javaslatom UPi feladatára. A cél az volt, hogy olyan relációs adatbázist tervezzünk, ami egy fát reprezentál úgy, hogy egy részfa lekérése, egy új elem beillesztése, valamint az út meghatározása a gyökértől egy adott elemig a lehető leggyorsabb legyen.

Az implementációhoz két oszlopra van szükség. Az első oszlop (nevezzük IDnek) egy egyéni karaktersor, ami az adott elemet azonosítja. Az egyedi azonosító előállításához a következő algoritmust használjuk:

Tegyük fel, hogy az adatbázis N különböző karaktert képes megkülönböztetni (sajnos nem emlékszem, hogy egy "mezei" karaktermezőbe mind a 256 karakter szerepelhet-e, vagy sem, ezért inkább általánosan beszélek N karakterről, ami, ha az adatbázis képes char*ban gondolkodni, akkor N=256, ha meg nem, akkor valamivel kevesebb).
Ekkor az egyedi azonosítók előállításához N-1 karaktert használhatunk fel. Kinevezünk egy karaktert "érvénytelennek". A továbbiakban erre a speciális karakterre "szóköz" címen fogok hivatkozni, de nem feltétlen a valódi szóköz karakter (lehet a 0-ás karakter is, amennyiben N=256). Az érvényes karakterek gyűjtőhalmazát a továbbiakban "szótár"-nak hívom (vagyis a "szóköz" + "szótár" halmaz az összes érvényes karakter halmazát adja az adott adatbázis-implementációban).
Az első egyedi azonosító egyetlen karakterből áll, mégpedig a szótár legelső eleméből.
Minden további egyedi azonosító úgy képezendő, hogy (amennyiben a legutoljára képzett azonosító n karakterből áll) képezzük a szótár szerint a legnagyobb azonosítóra közvetlenül rákövetkező n karakteres karakterláncot. Amennyiben ilyen karakterlánc nem képezhető, úgy azt az azonosítót képezzük, ami n+1 karakterből áll, melyek mindegyike a szótár legelső karaktere.

A második oszlop (nevezzük PATHnak) az adott elem teljes elérési útvonalát tartalmazza a gyökértől, oly módon, hogy a szülők egymás után szerepelnek benne a gyökérig visszamenőleg, a "szóköz" karakterrel elválasztva.

Ha az adatokat a data tábla tartalmazza és a lekérendő részfa csúcsán levő elem PATH oszlopának a tartalma s, akkor

 SELECT *
 FROM data
 WHERE PATH LIKE s%

(Itt jegyzem meg, hogy évek óta nem írtam SQL kódot, szóval a szintaktika lehet, hogy nem stimmel.)

Út meghatározása a gyökértől

Triviális, a PATH oszlop tartalmazza

Új elem beillesztése

Tekintsük azt az elemet, amelynek ID mezőjének értéke parent és PATH mezőjének értéke parentPath. Ez esetben az ez alá beszúrandó elem ID mezője az általános ID-generáló algoritmussal áll elő, míg PATH mezőjének értéke parentPath+parent+szóköz lesz.

A módszer egyetlen hátránya, hogy amennyiben m helyiértéket engedünk meg az ID mezőnek, úgy maximum m^N-1 darab eleme lehet a fának. Ennél nagyobb korlát, hogy amennyiben a fa maximális mélysége k, úgy a PATH oszlopnak (m+1)*k szélesnek kell lennie (a +1 a szóközök miatt, bár némi spórolást el lehet követni, ha az ember a gyökér azonosítóját nem írja be a PATH mezőbe, mivel az triviálisan mindenhol szerepelni fog, bár akkor bizonyos lekérdezéseket külön kell szedni, így a program lesz valamivel bonyolultabb). 64 lehetséges karakterrel számolva a szótárban (lásd pl. base64) ez azt jelenti, hogy N=65, így m=3 esetén 262.144 sor tárolható. Ha egy szöveges oszlop maximum 65.535 karakterből állhat (nem tudom, milyen korlátok vannak az egyes SQL implementációkban, de még anno egy évtizeddel ezelőttről az rémlik, hogy ez valamilyen korlát volt), akkor tehát az ábrázolt fa maximális mélysége k=16.383 lehet. Mindenki döntse el, hogy ez megfelel-e, vagy sem..

Utoljára módosította SAdam 2011.V.15 19:23-n
Bejegyzés módosítása | PermaLink

Szavazás letiltva.

Hozzászólások

SAdam 2011.V.15 19:21

No? No comment? :-(

UPi 2011.V.17 10:24

Sorry, még meg kell emésszem, elsőre úgy tűnik, hogy egész hasonló, amit én implementáltam!

BNC 2011.V.19 16:20

Az n értéke konkrét szervertől és használt adattípusoktól függ.

MSSql2008 esetén nvarchar(max)-ot használva 2^30-3 karakter hosszú lehet a mező, és Unicode értékeket vehet fel.

UPi 2011.V.30 11:55

Na, mostanra sikerült megemésztenem mindezt. Amit javasolsz az nagyon hasonló ahhoz, amit én találtam ki, pár különbséggel. A különbségek a következő megfigyelésekből erednek:

Én csak a [0-9 A-Y] karaktereket használom. Ennek oka az, hogy ugyan tudja az adatbázis a többit is tárolni, azonban a szortírozásuk locale függő (tud lenni). Ezt ki lehet ugyan kapcsolni a legtöbb adatbázis kezelőnél, ám ennek módja DB specifikus. (A Z karakterről még kicsit később). (Pl abc vagy később sortol mint ABC, vagy nem!)
Sajnos hasonlóképpen a szóköz kezelése is implementáció függő, ezért nem célszerű a használata. (Vagyis ABC DEF vagy előbb sortol mint az ABCDEF, vagy nem.)
Abból indulok ki, hogy a fa gyökerében nagyságrendekkel több elem lesz, mint lejjebb.

Ezért az implementációm a következő:

Az ID mező egyszerű 32 bites INT (többmilliárd a maximum értéke).
A PATH (én hierarchy-nak neveztem) szerkezete olyan, hogy a gyökérelemeket 6 karakteren tárolom, a továbbiakat pedig három karakteren: az első gyökér 000000, a második 000001, stb. Az első gyökér első levele 000000000, második levele 0000000001. A 36-ig gyökér első levele 0000120000. Stb.

A beszúrás, és egyéb műveletek hasonlóak, mint nálad.

Egy érdekesség: ha fordítva kell sortolni, akkor arra az
:ORDER BY hierarcy || 'Z' DESC
SQL mágiával van lehetőség... Ezen tűnődjetek, hogy miért :)

SAdam 2011.V.30 13:23

Pár megjegyzés:

Az első két pont, amit írtál, nem különbség. Én is azt mondtam, hogy vedd azt a legnagyobb karakterhalmazt, amit az adatbázis-szerver meg tud különböztetni (vagyis működik rajtuk a sort, stb), és ebből nevezz ki egyet "érvénytelennek", vagyis szóköznek. Nálad ezek szerint a használt karakterhalmaz a [0..9 A..Z], a szóköz pedig a Z.
Nem világos az utolsó példa. A 0000120000-nak tíz jegye van, még nem állt össze, hogy ez hogy jön ki.
A fordított sort-hoz annyi segítséget kérnék, hogy a "||" operátor az mi? Én eddig SQLben ilyennel nem találkoztam és a gugli sem volt a barátom, amikre tippelnék, hogy az 'OR' operátort (bár ORDER BY-ban olyat még nem ettem), a '+' operátort (string concat operator) vagy a ',' operátort váltja ki.

UPi 2011.V.30 13:26

0000120000 helyett 000012000 akar lenni. A kutya épp stresszben volt.

A || operátor SQL-ben a string összefűzés. Ezt általában +-szal jelölünk olyan nyelveken, amikben van operator overloading. Az SQL-ben szerencsére nincs.

SAdam 2011.V.30 13:35

(Válaszképp erre)

<blockquote> 0000120000 helyett 000012000 akar lenni. A kutya épp stresszben volt.

A || operátor SQL-ben a string összefűzés. Ezt általában +-szal jelölünk olyan nyelveken, amikben van operator overloading. Az SQL-ben szerencsére nincs. </blockquote>

Hm. Eddig minden SQL szerver, amivel dolgoztam, a '+'-t használta string összefűzésre. Igaz, eddig összesen Sybase SQL és Microsoft SQL szerverekkel volt dolgom, ami azért valljuk be, nem sok.

Ez esetben a megoldás: legyen az éppen összehasonlított két karakterlánc hossza m és n (m≤n). Ha a hosszabbik karakterlánc első m jegye különbözik a rövidebb karakterlánctól, akkor a 'Z'-nek nincs szerepe. Ha viszont megegyeznek, akkor a sortolásnál a rövidebb karakterlánc biztos, hogy előbbre kerül, mint a hosszabb, ugyanis a hosszabb karakterláncban bármi is áll az m+1-edik mezőn, az biztos, hogy DESC módban későbbre rendeződik, mint 'Z'.