Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Index Structures for Matching XML Twigs Using Relational Query
    Processors

Index Structures for Matching XML Twigs Using Relational Query Processors

File(s)
TR2004-1961.pdf (222.91 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5661
Collections
Computing and Information Science Technical Reports
Author
Chen, Zhiyuan
Gehrke, Johannes
Korn, Flip
Koudas, Nick
Shanmugasundaram, Jayavel
Srivastava, Divesh
Abstract

Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices suffer from at least one of three limitations: they focus only on indexing the structure (relying on a separate index for node content), or they are useful only for simple path expressions such as root-to-leaf paths, or they cannot be tightly integrated with a relational query processor. Moreover, there is no unified framework to compare these index structures. In this paper, we present a framework defining a family of index structures, including most existing XML path indices. We also propose two novel index structures in this family, with different space-time tradeoffs, that are effective for the evaluation of XML branching path expressions (i.e., twigs) with value conditions. We also show how this family of index structures can be realized using the access methods of the underlying database system. Finally, we present an experimental evaluation to understand the performance tradeoff between index space and twig matching time. The experimental results show that our novel indices achieve orders of magnitude improvement in performance for evaluating twig queries, albeit at a higher space cost, over the use of previously proposed XML path indices that can be tightly integrated with a relational query processor.

Date Issued
2004-08-04
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2004-1961
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance