Index structure for supporting structural XML queries

Details Index structure for supporting structural XML queries Index structure for supporting structural XML queries

2007-10-23

2007-10-23

Vo, Tim (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

10723206

ABSTRACT:
The present invention provides a ViST (or “virtual suffix tree”), which is a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, it is shown that querying XML data is equivalent to finding (non-contiguous) subsequence matches. A variety of XML queries, including those with branches, or wild-cards (‘*’ and ‘//’), can be expressed by structure-encoded sequences. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on B+Trees without using any specialized data structures that are not well supported by common database management systems (hereinafter referred to as “DBMSs”).

REFERENCES:
patent: 2002/0059281 (2002-05-01), Watanabe et al.
patent: 2003/0204515 (2003-10-01), Shadmon et al.
patent: 2005/0234852 (2005-10-01), Coramutla
Haixun Wang, Sanghyun Park, Wei Fan, Philip s. Yu, ViST: a dynamic index method for querying XML data by tree structures, 2003, 110-121.

Affiliated with

Also associated with

Rating

Index structure for supporting structural XML queries does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Index structure for supporting structural XML queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Index structure for supporting structural XML queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3839392