Reorganizace vícerozměrného B-stromu

• Název práce v češtině: Reorganizace vícerozměrného B-stromu
• Název v anglickém jazyce: Reorganization of multidimensional B-tree
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Ústav: Katedra softwarového inženýrství (32-KSI)
• Vedoucí / školitel: RNDr. Matúš Ondreička, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 12.11.2008
• Datum zadání: 12.11.2008

Zásady pro vypracování

Viacrozmerný B-strom (VB-stom) [1] je dynamická stromová štruktúra, v ktorej je možné indexovať objekty podľa viacerých atribútov. Základom VB-stromu je B-strom, ktorého uzly sú tvorené ďalšími B-strommi. VB-strom má viacero úrovní, v každej jednotlivej úrovni sa nachádzajú B-stromy, v ktorých sú indexované hodnoty jedného z atribútov.
Úlohou bude implementovať efektívny VB-strom v jazyku Java, spolu s metódami na jeho obsluhu. Implementovať klasické aktualizačné operácie (add, delete, member, atd.) pre rôzne dátové typy (napr. ineger, string, date, atd.) a ich hodnoty (napr. prípustnosť hodnoty NUL), ďalej metódy na vykonávanie rozsahových dotazov [2] (preskakovanie úrovní VB-stromu), postavenie stromu od listovej úrovne z predom známych dát a ďalšie, viz. [3].
Hlavnou úlohou bude analýza a následná implementácia rôznych reorganizácií VB-stromu vzhľadom na dáta v ňom uložené (veľkosti domén atribútov, dátové typy atribútov, distribúcia hodnôt atribútov) a vzhľadom na jeho praktické použitie v MD-algoritme [4]. Množinu objektov s M atribútmi je možné indexovať v N! rôznych VB-stromoch (všetky permutácie poradia úrovní VB-stromu). Jednou z takýchto reorganizácií je napr. prevod VB-stromu z jedným poradím úrovní na VB-strom s iným poradím úrovní.
Pre potreby tejto bakalárskej práce postačí, ak bude VB-strom implementovaný ako trieda (obsah VB-stromu je v operačnej pamäti).

Seznam odborné literatury

[1] Pokorný, J., Žemlička, M.: Základy implementace souborů a databází. Skripta UK, Vydavatelství Karolinum, 2004.
[2] Scheuerman, P., Ouksel, M.: Multidimensional B-trees for associative searching in database systems. Information systems, Vol. 34, No. 2, 1982.
[3] Leslie, H., Jain, R., Birdsall, D., and Yaghmai, H. 1995. Efficient Search of Multi-Dimensional B-Trees. In Proceedings of the 21th international Conference on Very Large Data Bases (September 11 - 15, 1995). U. Dayal, P. M. Gray, and S. Nishio, Eds. Very Large Data Bases. Morgan Kaufmann Publishers, San Francisco, CA, 710-719.
[4] Ondreička, M., Pokorný J.: Extending Fagin's algorithm for more users based on multidimensional B-tree. In: Proc. of ADBIS 2008, P. Atzeni, A. Caplinskas, and H. Jaakkola (Eds.), LNCS 5207, Springer-Verlag Berlin Heidelberg, 2008, pp. 199?214.

Předběžná náplň práce

Hlavnou úlohou bude analýza a následná implementácia viacrozmerného B-stromu v jazyku Java spolu s metódami na jeho obsluhu. Implementovať klasické aktualizačné operácie, metódy rozsahové dotazy, vytvorenie VB-stromu od listovej úrovne a rôzne reorganizácie VB-stromu.

Předběžná náplň práce v anglickém jazyce

The main focus of this work is analyze and implementation of multidimensional B-tree in Java. Implementation of actualization operations, methods for range queries and various methods for reorganization of multidimensional B-tree.