Back to search

Athens University Economics and Business (AUEB)

XML query processing: architecture and algorithms for optimization and execution

Abstract

dc:description

This 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/22675

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Georgiadis, Haris; Γεωργιάδης, Χαράλαμπος. XML query processing: architecture and algorithms for optimization and execution. Athens University Economics and Business (AUEB), 2010. http://hdl.handle.net/10442/hedi/22675