Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. A number of algorithms have been proposed to process a twig query based on region encoding. In this paper, based on a novel labeling scheme: extended Dewey, we propose a novel and efficient holistic twig join algorithm, namely TJFast. Compared to previous work, our algorithm only needs to access the labels of leaf query nodes. We report our experimental results to show that our algorithms are superior to previous approaches in terms of the number of elements scanned and query performance.

REFERENCES

• 1: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 2: Jiaheng Lu , Ting Chen , Tok Wang Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031272]
• 3: J. Lu, T. Chen, and T. W. Ling. TJFast: Efficient processing of XML twig pattern matching. Technical report, National university of Singapore, 2004.
• 4: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
holistic twig join, labeling scheme