Zugang zum Dokument

Rode, Henning:

Methods and Cost Models for XPath Query Processing in Main Memory Databases

Datei(en):

Download PDF 742kB  




URL: http://kops.ub.uni-konstanz.de/volltexte/2004/1195/
Institut: Fachbereich Informatik und Informationswissenschaft
Dokumentart: Diplomarbeit, Magisterarbeit
Sprache: Englisch
Erstellungsjahr: 2003
Eingestellt in KOPS am: 04.03.2004
Kurze Inhaltszusammenfassung auf Englisch Recent work on XPath evaluation has produced e cient relational index structures for maintaining and querying XML through a DBMS. Built on top of an relational encoding, named the XPath Accelerator, this thesis takes a closer look at its utilization within the scope of query processing. Basic XPath operations, such as axis steps and simple node tests, remain in the focus of the study. Appropriate database operations for their evaluation are introduced in the context of the main memory DBMS Monet. In those cases where the existing database operators fail to exploit the tree properties of XML data, new algorithms have been developed, designed speci cally for evaluation of XPath axes. As an important step towards cost analysis for the proposed XPath operations, result size estimation is discussed in the trade o between accuracy and expense. Di erent methods show how statistical data as well as sampling techniques can be used for estimating result sizes of simple axis steps. The generation of cost functions mainly considers the time, that the XPath operations spend on data access. Even in main memory databases, CPU processing usually gets stalled for outstanding memory fetches. Therefore, our cost functions explicitly analyze the cache usage of the operations, adopting a hierarchical memory access model. Detailed tests demonstrate the accuracy and performance of the proposed result size and cost estimation techniques.
Kontrollierte Schlagwörter (Deutsch): XML , XPath , Modellierung , Relationale Datenbank , Sequentieller Algorithmus
Freie Schlagwörter (Englisch): XPath Result Size Estimation
DDC-Sachgruppe: Informatik
CCS - Klassifikation H.2.4 Syst
Urheberrecht: Hinweis zum Urheberrecht