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:

1. 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).
2. 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).
3. Az első egyedi azonosító egyetlen karakterből áll, mégpedig a szótár legelső eleméből.
4. 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..