Mechanism for efficiently evaluating operator trees

Details Mechanism for efficiently evaluating operator trees Mechanism for efficiently evaluating operator trees

2004-09-16

2009-10-13

Wong, Leslie (Department: 2164)

Data processing: database and file management or data structures

Database design

Data structure types

C707SE17127, C707SE17125, C715S234000

Reexamination Certificate

active

07603347

ABSTRACT:
An XPath expression is converted into a tree-based representation where each node represents an operation to be performed and the links between nodes in the tree represent the flow of data between operations. The conversion may involve creating a parse tree for the XPath expression, and then converting the parse tree into an operator tree. The operator tree is constructed in such a way that execution of the XPath expression begins at the leaf nodes of the operator tree, and the results are then passed up the tree. After each node is executed, the results are either (1) passed to a filter that filters the results with a predicate statement or (2) passed to another node to be operated upon. This occurs until no nodes remain to be executed.

REFERENCES:
patent: 4439837 (1984-03-01), Aiena et al.
patent: 4536873 (1985-08-01), Leete
patent: 5088032 (1992-02-01), Bosack
patent: 5590324 (1996-12-01), Leung et al.
patent: 5643633 (1997-07-01), Telford et al.
patent: 5870590 (1999-02-01), Kita et al.
patent: 5878410 (1999-03-01), Zbikowski et al.
patent: 5905982 (1999-05-01), Carey et al.
patent: 6026390 (2000-02-01), Ross et al.
patent: 6516327 (2003-02-01), Zondervan et al.
patent: 6519597 (2003-02-01), Cheng et al.
patent: 6584459 (2003-06-01), Chang et al.
patent: 6604100 (2003-08-01), Fernandez et al.
patent: 6636845 (2003-10-01), Chau et al.
patent: 6643633 (2003-11-01), Chau et al.
patent: 6654734 (2003-11-01), Mani et al.
patent: 6782380 (2004-08-01), Thede
patent: 7028028 (2006-04-01), Balmin et al.
patent: 7031956 (2006-04-01), Lee et al.
patent: 7062507 (2006-06-01), Wang et al.
patent: 7096224 (2006-08-01), Murthy et al.
patent: 7124137 (2006-10-01), Lin et al.
patent: 7139746 (2006-11-01), Shin et al.
patent: 7171404 (2007-01-01), Lindblad et al.
patent: 7171407 (2007-01-01), Barton et al.
patent: 7181438 (2007-02-01), Szabo
patent: 7216127 (2007-05-01), Auerbach
patent: 2001/0049675 (2001-12-01), Mandler et al.
patent: 2002/0073019 (2002-06-01), Deaton
patent: 2002/0078068 (2002-06-01), Krishnaprasad et al.
patent: 2002/0100027 (2002-07-01), Binding et al.
patent: 2002/0116457 (2002-08-01), Eshleman et al.
patent: 2002/0152267 (2002-10-01), Lennon
patent: 2002/0184401 (2002-12-01), Kadel Jr. et al.
patent: 2003/0028563 (2003-02-01), Stutz et al.
patent: 2003/0167456 (2003-09-01), Sabharwal
patent: 2003/0177341 (2003-09-01), Devillers
patent: 2003/0200214 (2003-10-01), Doole et al.
patent: 2003/0212662 (2003-11-01), Shin et al.
patent: 2003/0233618 (2003-12-01), Wan
patent: 2004/0015783 (2004-01-01), Lennon et al.
patent: 2004/0044659 (2004-03-01), Judd et al.
patent: 2004/0064466 (2004-04-01), Manikutty et al.
patent: 2004/0088320 (2004-05-01), Perry
patent: 2004/0103105 (2004-05-01), Lindblad et al.
patent: 2004/0143581 (2004-07-01), Bohannon et al.
patent: 2004/0148278 (2004-07-01), Milo et al.
patent: 2004/0167864 (2004-08-01), Wang et al.
patent: 2004/0167904 (2004-08-01), Wen et al.
patent: 2004/0193575 (2004-09-01), Chen et al.
patent: 2004/0199524 (2004-10-01), Rys et al.
patent: 2004/0205082 (2004-10-01), Fontoura et al.
patent: 2004/0215600 (2004-10-01), Aridor et al.
patent: 2004/0221226 (2004-11-01), Lin et al.
patent: 2004/0260691 (2004-12-01), Desai et al.
patent: 2004/0267719 (2004-12-01), Doherty et al.
patent: 2004/0267760 (2004-12-01), Brundage et al.
patent: 2005/0004892 (2005-01-01), Brundage et al.
patent: 2005/0022115 (2005-01-01), Baumgartner et al.
patent: 2005/0038688 (2005-02-01), Collins et al.
patent: 2005/0050016 (2005-03-01), Stanoi et al.
patent: 2005/0091188 (2005-04-01), Pal et al.
patent: 2005/0097084 (2005-05-01), Balmin et al.
patent: 2005/0102256 (2005-05-01), Bordawekar et al.
patent: 2005/0108630 (2005-05-01), Wasson et al.
patent: 2005/0114314 (2005-05-01), Fan et al.
patent: 2005/0120031 (2005-06-01), Ishii
patent: 2005/0160076 (2005-07-01), Kanemasa
patent: 2005/0160108 (2005-07-01), Charlet et al.
patent: 2005/0228792 (2005-10-01), Chandrasekaran et al.
patent: 2005/0228818 (2005-10-01), Murthy et al.
patent: 2005/0229158 (2005-10-01), Thusoo et al.
patent: 2005/0257201 (2005-11-01), Rose et al.
patent: 2005/0289125 (2005-12-01), Liu et al.
patent: 2005/0289138 (2005-12-01), Cheng et al.
patent: 2006/0195476 (2006-08-01), Nori et al.
patent: 2409078 (2005-06-01), None
patent: WO 03/027908 (2003-04-01), None
Krishnaprasad et al., Query Rewrite for XML in Oracle XML DB, 2004, Proceedings of the 30th VLDB Conference, 12 pages.
Khan et al., A performance Evaluation of Storing XML Data i Relational Database Management Systems, 2001, ACM, 8 pages.
Chen et al., From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery, 2003, Proceedings of the 29thVLDB Conference, pp. 1-12.
Daniele Braga et al., “A Graphical Environment to Query XML Data with Query,” Proceedings of the Fourth International Conference on Web Information Systems Engineering (WISE '03), 2003, IEEE, 10 pages.
McHugh, Jason et al., “Query Optimization for XML”, XP-002333353,Proceedings of the 25thVLDB Conference(1999) pp. 315-326.
Yoshikawa, Masatoshi et al., “XRel: A Path-Based Approach to Storage and Retrieval of XML Document Using Relational Databases”, XP-001143686,ACM Transactions on Internet Technology(2001), pp. 110-141.
Notification of Transmittal of the International Search Report and the Written Opinion of the International Search Authority, or the Declaration received from International application No. PCT/US2005/011762.
Pending claims from International application No. PCT/US2005/011762.
International Searching Authority, “Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration,” PCT/US2005/011763, dated Aug. 6, 2005, 12 pages.
Current Claims, PCT/US2005/011763, 4 pages.
Cooper, Brian F. et al., “A Fast Index for Semistructured Data,” Proceeding of the International Conference on Very Large Databases, 2001, XP-002303292, pp. 341-350.
McHugh, Jason, et al. “Indexing Semistructured Data,” Stanford Science Department, 1998, XP-002248313, pp. 1-21.
International Preliminary Examining Authority, “Notification of Transmittal of the International Preliminary Report of Patentability,” PCT/US2005/020795, dated Aug. 7, 2006, 10 pages.
International Preliminary Examining Authority, “Written Opinion of the International Preliminary Examining Authority,” PCT/US2005/020795, received May 31, 2006, 5 pages.
Claims, PCT/US2005/020795, 3 pages.
W3C, “XML Fragment Interchange,” W3C Working Draft, Jun, 30, 1999, XP-002167090, 17 pages.
Kudrass, Thomas, “Management of XML Documents without Schema in Relational Database Systems,” XP004347776, 10 pages.
MacKenzie, David et al., “Finding Files”, GNU Findutils Version 4.1.2, Nov. 1994, 38 pages.
Claims, Foreign Application No. 200580018627.9 (50277-3171), 3 pages.
State Intellectual Property Office of P.R.C., “Notification of the First Office Action”, Foreign Application No. 200580018627.9 (50277-3171), mailed Oct. 12, 2007, 9 pages.
Mackenzie et al., “Finding Files” Finding Utils, Version 4.1.2, Source Code, GNU.org, Nov. 31, 1994, source files, code.c; 3 pages.
Cormen et al., “Introduction to Algorithms”, MIT Press, 2ndEdition, 2001, 4 pages.
Shankar Pal et al., “Indexing XML Data Stored in a Relational Database”, Proceedings of the 30thVLDB Conference, 2004, 12 pages.
Mackenzie et al., “Finding Files”, FindUtils, Version 4.1.2, Source Code, GNU.org, Nov. 1997, source files, code. C, 22 pages.
European Patent Office, “Communication pursuant to Article 94 (3) EPC”, European patent application 05732473.3-1225, dated Feb. 4, 2008, 7 pages.
State Intellectual Property Office of P.R.C., “Notification of the First Office Action”, European patent application 2005800186273.9, dated Oct. 12, 2007, 9 pages.
Claims, European patent application 2005800186273.9, 3 pages.
Claims, European

Affiliated with

Also associated with

Rating

Mechanism for efficiently evaluating operator trees does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mechanism for efficiently evaluating operator trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for efficiently evaluating operator trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4072667