Optimization of extensible markup language path language...

Details Optimization of extensible markup language path language... Optimization of extensible markup language path language...

2011-01-04

2011-01-04

Vy, Hung T (Department: 2163)

Data processing: database and file management or data structures

Database and file access

Query optimization

C707S714000

Reexamination Certificate

active

07865502

ABSTRACT:
An apparatus, system, and method are disclosed for optimization of XPath expressions in a database management system configured to accept XML queries. Operations of the method include receiving an XQuery representation and partitioning XPath expressions within the XQuery representation into a plurality of XPath expression clusters. The XPath expression clusters may comprise one or more XPath expressions and those in each cluster may operate on a common document. Furthermore, the XPath expressions in each cluster are hierarchically related to each other such that branch nodes of the cluster are executable independent of nodes in other XPath expression clusters. The method also defines merging the one or more XPath expressions into one or more expression trees for each XPath expression cluster. The method generates one or more query execution plans from the one or more XPath expression blocks. The method includes, for each query execution plan, splitting each of the XPath expression blocks into one or more ordered fragments. The method determines a cardinality according to database statistics and an execution cost for each XPath expression block within each query execution plan. Finally, the method determines an aggregate cardinality for each query execution plan and an aggregate execution cost for each query execution plan. Therefore, an XQuery may be optimized at both the global XQuery and local XPath expression block level, improving performance and reducing overhead.

REFERENCES:
patent: 6738755 (2004-05-01), Freytag et al.
patent: 6757677 (2004-06-01), Pham et al.
patent: 6829606 (2004-12-01), Ripley
patent: 6947927 (2005-09-01), Chaudhuri et al.
patent: 7020651 (2006-03-01), Ripley
patent: 7062481 (2006-06-01), Pham et al.
patent: 7086042 (2006-08-01), Abe et al.
patent: 7107282 (2006-09-01), Yalamanchi
patent: 7315852 (2008-01-01), Balmin et al.
patent: 2003/0078909 (2003-04-01), Pham et al.
patent: 2003/0078922 (2003-04-01), Pham et al.
patent: 2003/0084025 (2003-05-01), Zuzarte
patent: 2003/0163285 (2003-08-01), Nakamura et al.
patent: 2003/0212662 (2003-11-01), Shin et al.
patent: 2003/0225768 (2003-12-01), Chaudhuri 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/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/0240624 (2005-10-01), Ge et al.
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/0162426 (2007-07-01), Brown et al.
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/0222087 (2008-09-01), Balmin et al.
Balmin et al., “Grouping and Optimization of XPath Expressions in System RX”.
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”.
Tao et al., “An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces”, IEEE Transactions on Knowledge and Data Engineering, v. 16, n. 10, p. 1169-1184, Oct. 2004.
Pendersen et al., “Cost Modeling and Estimation for OLAP-XML Federations”, Technical Report 02-5003, Aalborg University Dept. of CS, Dec. 2002.
“An Efficient Xpath Query Processor for XML Streams” Chen, Y.; Davidson, B.S.; Zheng, Y., IEEE 2006.
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 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.
Balmin et al., “Grouping and Optimization of XPath Expressions in DB2 pureXML”.
Re et al., “A Complete and Efficient Algebraic Compiler for XQuery”.
Shanmugasundaram et al., “A General Technique for Querying XML Documents Using a Relational Database System”.
Fiebig et al., “Anatomy of a Native XML Base Management System”, VLDB Journal vol. 11, No. 4, Dec. 13, 2002.
Beyer et al., “DB2 Goes Hybrid: Integrating Native XML and XQuery With Relational Data and SQL”, IBM Systems Journal, vol. 45, No. 2, 2006.
Pirahesh et al., “Extensible/Rule Based Query Rewrite Optimization in Starburst”, IBM Almaden Research Center.
Koch et al., “FluXQuery: An Optimizing XQuery Processor for Streaming XML Data”, Proceedings of the 30th VLDB Conference,Toronto, Canada, 2004.
Chen et al., “From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery”, Proceedings of the 29th VLDB Conference, Berlin, Germany 2003.
Brantner et al., “Full-fledged Algebraic XPath Processing in Natix”.
Bruno et al., “Holistic Twig Joins: Optimal XML Pattern Matching”, ACM SIGMOD 'Jun. 4-6, 2002
Balmin et al., “Cost-based optimization in DB2/XML”, IBM Systems Journal, Feb. 16, 2006.
McHugh et al., “Lore: A Database Management System for Semistructured Data”.
Halverson et al., “Mixed Mode XML Query Processing”, Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
Boncz et al., “MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine”, SIGMOD 2006, Jun. 27-29, 2006.
Al-Khalifa et al., “Multilevel Operator Combination in XML Query Processing”, CIKM'02, Nov. 4-9, 2002.
Liu et al., “Native XQuery Processing in Oracle XMLDB”.
Diao et al., “Query Processing for High-Volume XML Message Brokering”, Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
Krishnaprasad et al., “Query Rewrite for XML in Oracle XML DB”, Proceedings of the 30th V

Affiliated with

Also associated with

Rating

Optimization of extensible markup language path language... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization of extensible markup language path language..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of extensible markup language path language... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2723534