A modified multidimensional XML dataguide for efficient holistic processing of XML queries with value predicates

Abstract

Recent years have witnessed a dramatic growth of the amount of data that is represented by XML. That creates the need for efficient indexing and query processing algorithms in order to extract the relevant information contained in these data sets. As a result, researcher proposed several structural join algorithms. Most of them, however, require a set of expensive join operations to answer both path and twig queries. As a result of aforementioned limitation a variety of holistic join techniques were proposed. The principal shortcoming of these techniques is that they operates in two phase producing intermediate result. They also fail to support XML queries with value predicates efficiently which is however highly desired. In this thesis, we are proposing a multidimensional index structure called MXD (Multidimensional XML DataGuide), which supports processing XML Queries with value predicates efficiently. Also we are proposing two new XML query processing algorithms, namely MXD-Path (Multidimensional XML DataGuide Path Query Processing) and MXD-Twig (Multidimensional XML DataGuide Twig Query Processin) to evaluate path and twig queries respectively. MXD-Path efficiently processes path queries without performing any join operation while MXD-Twig allows holistic processing of twig queries. TMXD-Twig operates on leaf nodes’ lists representing the individual path’s solutions and is capable of skipping nodes not contributing to the final answer of the query, thereby reducing disk access, number of join operations and consequently reducing the time required to evaluate queries. Our experiments show that both MXD-Path and MXD-Twig are efficient for processing both single-path and branching queries with various value predicates respectively.