Query evaluation using ancestor information

Details Query evaluation using ancestor information Query evaluation using ancestor information

2011-07-12

2011-07-12

Trujillo, James (Department: 2159)

Data processing: database and file management or data structures

Database and file access

Query optimization

Reexamination Certificate

active

07979423

ABSTRACT:
Provided are techniques for processing a query. A query is received, wherein the query is formed by one or more paths, and wherein each path includes one or more steps. A hierarchical document including one or more document nodes is received. While processing the query and traversing the hierarchical document, one or more extraction entries are constructed, wherein each extraction entry includes a step instance match candidate identifying a document node and a step instance ancestor path for the document node, and one or more tuples are constructed using the one or more extraction entries by associating the step instance match candidate from one of the one or more extraction entries with the step instance match candidate from at least one of the one or more other extraction entries.

REFERENCES:
patent: 6920462 (2005-07-01), Kircher
patent: 2003/0088558 (2003-05-01), Zaharioudakis et al.
patent: 2003/0163285 (2003-08-01), Nakamura et al.
patent: 2003/0212662 (2003-11-01), Shin et al.
patent: 2003/0233618 (2003-12-01), Wan
patent: 2004/0034830 (2004-02-01), Fuchs et al.
patent: 2004/0060007 (2004-03-01), Gottlob et al.
patent: 2004/0068487 (2004-04-01), Barton et al.
patent: 2004/0073541 (2004-04-01), Lindblad et al.
patent: 2004/0083209 (2004-04-01), Shin
patent: 2004/0122795 (2004-06-01), Lin et al.
patent: 2004/0167864 (2004-08-01), Wang et al.
patent: 2004/0193607 (2004-09-01), Kudo et al.
patent: 2004/0205082 (2004-10-01), Fontoura et al.
patent: 2004/0260691 (2004-12-01), Desai et al.
patent: 2005/0021548 (2005-01-01), Bohannon et al.
patent: 2005/0028091 (2005-02-01), Bordawekar et al.
patent: 2005/0050016 (2005-03-01), Stanoi et al.
patent: 2005/0055336 (2005-03-01), Hui et al.
patent: 2005/0097084 (2005-05-01), Balmin et al.
patent: 2005/0257201 (2005-11-01), Rose et al.
patent: 2006/0106758 (2006-05-01), Chen et al.
patent: 2007/0174241 (2007-07-01), Beyer et al.
Jinhui Jian, Efficient XML Stream Processing with Automata and Query Algebra, Thesis, published Aug. 2003, pp. 1-90.
Erhard Rahm et al., Matching Large XML Schemas, SIGMOD vol. 33, No. 4, published Dec. 2004, pp. 1-6.
Bar-Yossef, Z., M. Fontoura, and V. Josifovski, “Buffering in Query Evaluation Over XML Streams,” Proceedings of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun. 2005, pp. 216-227.
Chen, Q., A. Lim, and K.W. Ong, “D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data”, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, Jun. 2003, pp. 134-144.
Diao, Y., D. Florescu, D. Kossmann, M.J. Carey, and M.J. Franklin, “Implementing Memoization in a Streaming XQuery Processor,” Proceedings of the 2nd International XML Database Symposium, 2004, pp. 35-50.
Florescu, D., C. Hillery, D. Kossmann, P. Lucas, F. Riccardi, T. Westmann, M.J. Carey, and A. Sundararajan, “The BEA Streaming XQUERY Processor,” VLDB Journal, 2004, pp. 294-315.
Florescu, D., C. Hillery, D. Kossmann, P. Lucas, F. Riccardi, T. Westmann, M.J. Carey, A. Sundararajan, and G. Agrawal, “The BEA/XQRL Streaming XQuery Processor”, Proceedings of the 29th VLDB Conference, 2003, 12 pp.
Garshol, L.M., “BNF and EBNF: What are they and how do they work?”, [online], [Retrieved on Dec. 21, 2007]. Retrieved from the Internet at <URL: http://www.garshol.priv.no/download/text/bnf.html>, last updated Jul. 21, 2003, 16 pp.
Josifovski, M. Fontoura, and A. Barta, “Querying XML Streams”, The VLDB Journal, 2004, pp. 294-315.
Kreowski, H., “A Pumping Lemma for Context-Free Graph Languages”, Proceedings of the International Workshop on Graph-Grammars and Their Application to Computer Science and Biology, 1978, pp. 270-283.
Little, S., “Tree::Simple—1.14”, [online], [Retrieved on Dec. 25, 2007]. Retrieved from the Internet at <http://search.cpan.org/˜stevan/Tree-Simple-1.14/lib/Tree/Simple.pm>, © 2004 Infinity Interactive, Inc., 12 pp.
PCT Invitation to Pay Additional Fees and International Search Report, May 2, 2007, for International Application No. PCT/EP2007/050292.
Wikipedia, “Pumping Lemma for Context-Free Languages”, [online], modified Apr. 25, 2008, [retrieved on Jun. 23, 2008], retrieved from the Internet at <URL: http://en.wikipedia.org/wiki/Pumping—lemma—for—Context.Free—Languages>, 5 pp.
Wikipedia, “Surjective Function”, [online], modified Jun. 17, 2008, [retrieved on Jun. 23, 2008], retrieved from the Internet at <URL: http://en.wikipedia.org/wiki/Surjection>, 5 pp.

Affiliated with

Also associated with

Rating

Query evaluation using ancestor information does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Query evaluation using ancestor information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query evaluation using ancestor information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2702367