Data processing: database and file management or data structures – Database and file access – Preparing data for information retrieval
Reexamination Certificate
2007-09-05
2010-12-28
Vo, Tim T. (Department: 2168)
Data processing: database and file management or data structures
Database and file access
Preparing data for information retrieval
C707S999100, C717S144000, C717S132000
Reexamination Certificate
active
07860863
ABSTRACT:
Provided are techniques for optimizing the processing of hierarchical data. A linear processing graph is received, wherein the linear processing graph includes a plurality of operators, wherein each operator in the plurality is connected to at least one other operator by an arc, wherein hierarchical data flows on arcs, wherein the operators read and replace identified subregions within the hierarchical data flowing into the operators on the arcs, and wherein the operators do not modify the hierarchical data outside of these identified subregions. For each operator in the linear processing graph, a minimal set of dependent upstream operators on which that operator depends is found by examining how the identified subregions are created in the linear processing graph through obtaining a set of operators on which that operator depends, by analyzing dependencies carried by a set of vector nodes of the hierarchical data in an input schema of the operator, and, for each of the vector nodes, by analyzing an associated set of scalar nodes, wherein finding the minimum set of operators includes taking into consideration data preservation characteristics of the plurality of operators and taking into consideration structural-order preservation characteristics of the plurality of operators. The linear processing graph is rewritten to create a new graph that expresses dependencies based on the minimal set of dependent upstream operators for each operator.
REFERENCES:
patent: 4145733 (1979-03-01), Misunas et al.
patent: 5021947 (1991-06-01), Campbell et al.
patent: 5465372 (1995-11-01), Gottlieb et al.
patent: 5555201 (1996-09-01), Dangelo et al.
patent: 5603018 (1997-02-01), Terada et al.
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5801958 (1998-09-01), Dangelo et al.
patent: 5806062 (1998-09-01), Chen et al.
patent: 5822593 (1998-10-01), Lamping et al.
patent: 6192504 (2001-02-01), Pflüger et al.
patent: 6311265 (2001-10-01), Beckerle et al.
patent: 6601058 (2003-07-01), Forster et al.
patent: 6654952 (2003-11-01), Nair et al.
patent: 6772398 (2004-08-01), Saluja et al.
patent: 6801938 (2004-10-01), Bookman et al.
patent: 6832357 (2004-12-01), Saluja et al.
patent: 6918111 (2005-07-01), Damron et al.
patent: 6954749 (2005-10-01), Greenblatt et al.
patent: 7080088 (2006-07-01), Lau
patent: 7254590 (2007-08-01), Mudunuri et al.
patent: 7299458 (2007-11-01), Hammes
patent: 7392514 (2008-06-01), Edwards
patent: 7467371 (2008-12-01), Meredith et al.
patent: 2002/0080181 (2002-06-01), Razdow et al.
patent: 2003/0014379 (2003-01-01), Saias et al.
patent: 2003/0191765 (2003-10-01), Bargh et al.
patent: 2003/0200538 (2003-10-01), Ebeling et al.
patent: 2004/0117772 (2004-06-01), Brand et al.
patent: 2004/0123072 (2004-06-01), Kailas et al.
patent: 2004/0205058 (2004-10-01), Kiji
patent: 2004/0207665 (2004-10-01), Mathur et al.
patent: 2004/0225999 (2004-11-01), Nuss
patent: 2005/0071359 (2005-03-01), Elandassery et al.
patent: 2005/0097561 (2005-05-01), Schumacher et al.
patent: 2005/0251527 (2005-11-01), Phillips et al.
patent: 2005/0257194 (2005-11-01), Morrow et al.
patent: 2005/0257195 (2005-11-01), Morrow et al.
patent: 2006/0005173 (2006-01-01), Eng
patent: 2006/0048113 (2006-03-01), Ozone et al.
patent: 2006/0277392 (2006-12-01), Bittner, Jr.
patent: 2008/0052687 (2008-02-01), Gonzales-Tuchmann et al.
patent: 2008/0082984 (2008-04-01), McDaniel
patent: 2008/0134158 (2008-06-01), Salz et al.
patent: 2009/0064157 (2009-03-01), Bar-Or et al.
Dennis, J.B. and David P.M., “A Preliminary Architecture for a Basic Data-Flow Processor”, vol. 3, No. 4, Dec. 1974, pp. 126-132.
Miyazaki, T., and Edward A.L., “Code Generation by Using Integer-Controlled Dataflow Graph”Proceedings of the 1997 IEEE Internatinoal Conference on Acoustics, Speech, and Signal Processing, vol. 1, 1997, 4 pp.
Neubauer, F., A. Hoheisel, and J. Geiler, “Workflow-based Grid Applications”, © 2005 Elsevier, pp. 1-15.
Weimer, W. and G.C. Necula, “Finding and Preventing Run-Time Error Handling Mistakes”, © 2004 ACM, vol. 39, No. 10, pp. 419-431.
Arvind and R.S. Nikhil, “Executing a Program on the MIT Tagged-Token Dataflow Architecture”, © 1990 IEEE, pp. 300-318.
Bowers, S., B. Ludascher, A.H.H. Ngu, and T. Critchlow, “Enabling Scientific Workflow Reuse through Structured Composition of Dataflow and Control-Flow”, Proceedings of the 22nd International Conference on Data Engineering Workshops, © 2006 IEEE, 10 pp.
Cardelli, L., and P. Wegner, “On Understanding Types, Data Abstraction, and Polymorphism”, Computing Surveys, vol. 17, No. 4, Dec. 1985, pp. 471-522.
Kelly, P.M., P.D. Coddington, and A.L. Wendelborn, “Compilation of XSLT into Dataflow Graphs for Web Service Composition”, Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid, © 2006 IEEE, 9 pp.
Leymann, F., and D. Roller, “Production Workflow: Concepts and Techniques”, Sep. 1999, Prentice Hall PTR, 5 pp.
Morgenthal, J.P., “Enterprise Information Integration: A Pragmatic Approach”, May 30, 2005, Lulu.com, 4 pp.
Morrison, J.P., “Data Responsive Modular Interleaved Task Programming System”, IBM Technical Disclosure Bulletin, Jan. 1971, pp. 2425-2426.
Morrison, J.P., “Data Stream Linkage Mechanism”, IBM System Journal, vol. 17, No. 4, 1978, pp. 383-408.
W3C, “XSL Transformations (XSLT) Version 2.0”, [online], Jan. 23, 2007, [retrieved on Jun. 20, 2008], retrieved from the Internet at <URL: http://www.w3.org/TR/xslt20>, 50 pp.
Wikipedia, “Flow-based Programming”, [online], modified Jun. 12, 2008, [retrieved on Jun. 26, 2008], retrieved from the Internet at <URL: http://en.wikipedia.org/wiki/Flow-based—programming>, 7 pp.
Wikipedia, “XML Pipeline”, [online], modified Apr. 1, 2008, [retrieved on Apr. 19, 2008], retrieved from the Internet at <URL: http://en.wikipedia.org/wiki/XML—pipeline>, 4 pp.
U.S. Appl. No. 12/147,408, filed Jun. 26, 2008, entitled “Pipeline Optimization Based on Polymorphic Schema Knowledge”, invented by A. Bar-Or and M.J. Beckerle, 26 pp.
Yu, D. and H. Wang, “A New Approach for the Forward and Backward Substitutions of Parallel Solution of Sparse Linear Equations—Based on Dataflow Architecture”, © 1990 IEEE, pp. 621-627.
Florescu, D., C. Hillery, D. Kossmann, P. Lucas, F. Riccardi, T. Westmann, M.J. Carey, A. Sundarajan, and G. Agrawal, “The BEA/XQRL Streaming XQuery Processor”, Proceedings of the 29th VLDB Conference, 2003, 12 pp.
Koch, C., S. Sherzinger, N. Schweikardt, and B. Stegmaier, “FluXQuery: An Optimizing XQuery Processor for Streaming XML Data”, Proceedings of the 30th VLDB Conference, 2004, pp. 1309-1312.
LDODDS.COM, “XML Pipeline”, [online], updated on Aug. 21, 2002, [retrieved on Apr. 9, 2007], retrieved from the Internet at <URL: http://www.Idodds.com/wordtin/wiki.jsp?page=XMLPipeline>, 2 pp.
Morrison, J.P., “Flow-Based Programming: A New Approach to Application Development”, Van Nostrand Reinhold, New York, 1994, Chapter 10, 13 pp.
Pal, S., I. Cseri, O. Seeliger, M. Rhys, G. Schaller, W. Yu, D. Tomic, A. Baras, B. Berg, D. Churin, and E. Kogan, “XQuery Implementation in a Relational Database System”, Proceedings of the 31st VLDB Conference, 2005, pp. 1175-1186.
U.S. Appl. No. 11/566,193, filed Dec. 1, 2006, entitled “System and Method for Implementing a Unified Model for Integration Systems”, invented by A. Bar-Or and M.J. Beckerle.
US Patent Application, filed on Sep. 5, 2007, entitled “Compilation Model For Processing Hierarchical Data in Stream Systems”, invented by A. Bar-Or and M.J. Beckerle.
Bar-Or Amir
Beckerle Michael James
Davda Janaki K.
Fan Shiow-Jy
International Business Machines - Corporation
Konrad Raynes & Victor LLP
Vo Tim T.
LandOfFree
Optimization model for processing hierarchical data in... 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 model for processing hierarchical data in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization model for processing hierarchical data in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4230855