Holistic Boolean Twig Pattern Matching for Efficient XML Query Processing

Efficient twig pattern matching is essential to XML queries and other tree-based queries. Numerous so-called holistic algorithms have been proposed for efficiently processing the twig patterns in XML queries. However, a more general form of twig pattern, called Boolean-twig (or B-twig for short), which allows arbitrary combination of an arbitrary number of all the three logical connectives, AND, OR, and NOT, in a twig pattern, has not been adequately addressed. The theme of this study is on holistic (and efficient) B-twig pattern matching using region encoding and Dewey encoding schemes. We first adopt region encoding and propose a novel, direct approach called DBTwigMerge for holistic B-twig pattern matching, which although enjoys certain theoretical ``beauty'' and ``elegance'' but does not always outperform our prior approach, BTwigMerge. Based on the experience gained and in-depth investigation, we then come up with another new and more efficient approach, FBTwigMerge, which is proven to be the overall winner among all the holistic approaches using region encoding. In this study, we also studied the holistic B-twig pattern matching problem using Dewey encoding. The unique properties of Dewey encoding bring challenges and also benefits to this problem. By carefully addressing the challenges, this dissertation finally presents the first Dewey based holistic approach, called DeweyNOT, for efficiently solving the pattern matching problem with a subclass of B-twigs, i.e., twig queries involving arbitrary AND/NOT predicates. Extensive experimental studies have been conducted that demonstrate the viability and outstanding performance of the proposed approaches.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Campus Only Dissertation

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

2014

Author dc:creator

• Ding, Dabin

Contributors dc:contributor

• Che, Dunren

• B-twig
• holistic pattern matching
• twig query
• XML query processing

Repository record dc:identifier

https://opensiuc.lib.siu.edu/dissertations/811

OAI identifier oai:identifier

oai:opensiuc.lib.siu.edu:dissertations-1814