Efficient Processing of XML Twig Queries with All Predicates

Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Some researches have proposed part solutions to process XML twig queries with AND,OR, or NOT predicates. However, very Little work has handled a twig query with three predica...

Full description

Saved in:
Bibliographic Details
Main Authors: Xiaoshuang Xu, Yucai Feng, Feng Wang
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Costs
Encoding
encoding scheme
Information science
Logic
Pattern matching
predicates
Query processing
twig query
XML
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. Some researches have proposed part solutions to process XML twig queries with AND,OR, or NOT predicates. However, very Little work has handled a twig query with three predicates comprehensively. In this paper, we propose a novel path-partitioned encoding scheme, and present a powerful XPattern extended from tree pattern with logic predicates. We also develop a holistic twig join algorithm, called MPTwig, which is designed for efficient matching an XML twig pattern with compound and nested predicates. We show that MPTwig based on path-partitioned encoding scheme guarantee the I/O and CPU optimality. Finally, experimental results on a representative data set indicate that the proposed algorithm performs significantly.
DOI:10.1109/ICIS.2009.74