Apparatus and method for skipping XML index scans with...

Details Apparatus and method for skipping XML index scans with... Apparatus and method for skipping XML index scans with...

2006-12-20

2009-06-23

LeRoux, Etienne P (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07552119

ABSTRACT:
An apparatus and method are disclosed for skipping XML index scans with common ancestors of a previously failed predicate. An XML index is scanned by an XML index scan to filter entries of the index matching at least one search value (predicate) of an XML query. When the XML index scan finds a matching entry, the entry is passed to an XPath evaluation component. The XPath evaluation component evaluates the entry against remaining predicates of the XML query for further qualification. When the XPath evaluation component disqualifies an entry, the XPath evaluation component provides feedback to the XML index scan to skip remaining entries comprising a common ancestor of the disqualified entry's path. The XML index scan can then efficiently skip index entries that will not qualify against the XML query.

REFERENCES:
patent: 6738755 (2004-05-01), Freytag et al.
patent: 6829606 (2004-12-01), Ripley
patent: 6947927 (2005-09-01), Chaudhuri et al.
patent: 7020651 (2006-03-01), Ripley
patent: 7086042 (2006-08-01), Abe et al.
patent: 7107282 (2006-09-01), Yalamanchi
patent: 7315852 (2008-01-01), Balmin et al.
patent: 7346609 (2008-03-01), Chen et al.
patent: 7451144 (2008-11-01), Koudas et al.
patent: 2003/0084025 (2003-05-01), Zuzarte
patent: 2003/0163285 (2003-08-01), Nakamura et al.
patent: 2003/0200502 (2003-10-01), Abe et al.
patent: 2003/0212662 (2003-11-01), Shin et al.
patent: 2003/0229617 (2003-12-01), Rjaibi et al.
patent: 2004/0111396 (2004-06-01), Musayev et al.
patent: 2004/0181521 (2004-09-01), Simmen
patent: 2004/0236722 (2004-11-01), Waas et al.
patent: 2004/0260675 (2004-12-01), Bruno et al.
patent: 2004/0261019 (2004-12-01), Imamura et al.
patent: 2005/0050016 (2005-03-01), Stanoi et al.
patent: 2005/0091188 (2005-04-01), Pal et al.
patent: 2005/0097078 (2005-05-01), Lohman et al.
patent: 2005/0097084 (2005-05-01), Balmin et al.
patent: 2005/0108209 (2005-05-01), Beyer et al.
patent: 2005/0131914 (2005-06-01), Abdo et al.
patent: 2005/0203957 (2005-09-01), Wang et al.
patent: 2005/0228779 (2005-10-01), Chaudhuri et al.
patent: 2005/0229158 (2005-10-01), Thusoo et al.
patent: 2005/0235356 (2005-10-01), Wang
patent: 2005/0257201 (2005-11-01), Rose et al.
patent: 2005/0267866 (2005-12-01), Markl et al.
patent: 2006/0064432 (2006-03-01), Pettovello
patent: 2006/0075000 (2006-04-01), Kleewein et al.
patent: 2006/0106758 (2006-05-01), Chen et al.
patent: 2006/0218194 (2006-09-01), Yalamanchi
patent: 2007/0208769 (2007-09-01), Boehm et al.
patent: 2007/0233645 (2007-10-01), Peterson et al.
patent: 2007/0245325 (2007-10-01), Lapounov et al.
patent: 2007/0250473 (2007-10-01), Larson et al.
patent: 2007/0299834 (2007-12-01), Liu et al.
patent: 2008/0120321 (2008-05-01), Liu et al.
“An Efficient Xpath Query Processor for XML Streams” Chen, Y.; Davidson, B.S.; Zheng, Y., IEEE 2006.
Balmin et al., “Grouping and Optimization of XPath Expressions in System RX”.
Freire et al., “A Flexible Infrastructure for Gathering XML Statistics and Estimating Query Cardinality,” Proceedings of the 20 st Int'l Conference on Data Engineering, 2004.
Ramanath et al., “IMAX: Incremental Maintenance of Schema-Based XML Statistics,” Proceedings of the 21st Int'l Conference on Data Engineering, 2005.
Beyer et al., “System RX: One Part Relational, One Part XML,” SIGMOD 2005, Jun. 14-16, 2005, Baltimore, MD, USA.
McHugh et al., “Query Optimization for XML,” Proc. of Very Large Data Bases, Edinburgh, U.K., 1999.
“Efficient Evaluation of Multiple Queries On Streaming XML Data” ACM Digital Library/INSPEC, Lee, M.L. et al.; 2002.
“WMS and GML based Interoperable Web Mapping System” ACM Digital Library/INSPEC, Shekhar et al.; 2001.
“XSQ: A Streaming Xpath Engine” ACM Digital Library, Peng, F. et al.; 2005.
“Multi-level Operator Combination in XML Query Processing” ACM Digital Library, Al-Khalifa, S. Et al.; 2002.
“An XML Query Engine for Network-Bound Data” ACM Digital Library, Ives, Z.G. et al.; 2002.
“Timber: A native XML database” Jagadish, H.V. et al., The VLDB Journal, 2002.
“Cost-based optimization in DB2 XML” Balmin, A. et al., IBM Systems Journal, vol. 45, No. 2, 2006.
“Cost-Sensitive Reordering of Navigational Primitives” Kanne, C.C. et al., ACM, 2005.
“Structural Join Order Selection for XML Query Optimization” Wu, Y. et al., IEEE 2003.
Dunren et al., “Query Optimization in XML Structured-Document Databases”, May 14, 2005.
Lukichev et al., “XML Query Algera for Cost-based Optimization”, University of Saint-Petersburg.
Kader et al., “XQuery Optimization in Relational Database Systems”.

Affiliated with

Also associated with

Rating

Apparatus and method for skipping XML index scans with... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for skipping XML index scans with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for skipping XML index scans with... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4085241