Athens University Economics and Business (AUEB)
XML query processing: architecture and algorithms for optimization and execution
Abstract
dc:descriptionThis thesis proposes a design for XPath processing on relational back-ends and a design for a generic and modular framework for cost-based execution of XPath queries. Based on these designs two complete systems have been developed, the PPFx system and the GeCOEX system, respectively. PPFx is an XML database system based on identifying, processing and combining Primitive Path Fragments (PPFs) on XPath expressions that runs on top of a relational back-end. A set of novel techniques is presented that significantly limit the number of SQL joins required, take advantage of the strengths of modern SQL query processors and exploit XML schema information to achieve big performance gains with low implementation complexity. The PPF-based XPath-to-SQL translation algorithm leads to SQL queries that involve only the absolutely necessary relations, with the minimum number of structural joins and the maximum exploitation of root-to-node path ids for the holistic evaluation of multi-step PPFs based on optimized regular expression filtering method. Moreover, the thesis presents a very efficient technique for backwards navigation that substitutes expensive backward structural joins with simple and cheap string manipulation, yielding performance improvement of up to 35% for reversible descendant-ancestor structural joins and of orders of magnitude for general descendant-ancestor structural joins. Furthermore, the thesis describes an optimization technique for accelerating, under specific and well-defined conditions, queries that have forward predicates, yielding - when applicable - performance improvements that range from 61% up to 99.6%. An extensive experimental study confirms the performance benefits of all these novel techniques and shows that PPFx running on top of a commercial RDBMS is competitive with respect to query performance with other native and relational-based state-of-the-art XPath processing systems, commercial as well as research prototypes. The thesis also presents in detail a Generic and Extensible Cost-based Optimization and Execution system for XPath, named GeCOEX. The cost-based optimizer of GeCOEX always picks the cheapest estimated plan, among a very large number of possible plans, for a wide range of XPath queries and different datasets in a very small fraction of the time required for efficient execution. The optimizer is based on XPAlgebra, a novel navigation based logical algebra and on a comprehensive set of rewritings. Experimental evaluation of the effectiveness of the overall GeCOEX system have shown that the execution time of the chosen plan is within 12% of the optimal execution time in all but one of the queries in the tested workloads. The GeCOEX system contains a framework for XPath execution that includes physical operator implementations along with cost models, as well as the necessary infrastructure for their easy deployment. The framework can be effectively used with a variety of different storage engines. The thesis describes two novel families of algorithms, namely Lookup and Sort-Merge-based, for all the major XPath “operations”, including forward and backward navigation, and demonstrate experimentally their performance advantages compared to existing techniques. The algorithms are implemented as physical operators for the XPAlgebra algebra which, along with physical operator implementations corresponding to existing XPath processing techniques, are all plugged in the GeCOEX system. Experimental results provide strong evidence of the performance benefits of the execution framework in general and the Lookup and Sort-Merge-based physical operator in particular. Cost models for all proposed physical operators have been defined whose accuracy have been evaluated experimentally.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Georgiadis, Haris
- Γεωργιάδης, Χαράλαμπος
Subjects
dc:subject × 25- Ημιδομημένα δεδομένα
- Επεξεργασία επερωτήσεων
- Βελτιστοποίηση επερωτήσεων βάσει κόστους
- Λογική άλγεβρα
- Σχεσιακά συστήματα βάσεων δεδομένων
- Λογικοί τελεστές
- Φυσικοί τελεστές
- Κανόνες μετασχηματισμού
- XML
- XPath
- XML-to-relational schema mapping
- Cost-based optimization
- Logical algebra
- Logical operators
- Physical operators
- Rewriting rules
- Access methods
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Πληροφοριακά συστήματα
- Επιστήμη ηλεκτρονικών υπολογιστών
- Computer and Information Sciences
- Natural Sciences
- Information Systems
- Computer Science
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/22675