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 mN-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..
Hozzászólások
9Apocalypse KÖZÖS
Az élet nem azt jelenti, hogy túléljük a viharokat, hanem hogy megtanulunk táncolni az esőben.
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:
Ezért az implementációm a következő:
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:
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'.
UPi 2011.V.30 13:37
Ön nem gondolkozik 4 dimenzióban.
Descant 2011.V.30 13:48
Beü beü beü