Method and system for effective schema generation via programmatic analysis

• US 8,276,064 B2
• Filed: 05/07/2007
• Issued: 09/25/2012
• Est. Priority Date: 05/07/2007
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Heifets, Abraham, Kesselman, Joseph J., Perkins, Eric David
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): ROBINSON, MARSHON L
• Application Number:
  US11/745,028
• Publication Number:
  US 20080282145A1
• Time in Patent Office: 1,968 Days
• Field of Search: 715/234, 715/237, 715/143, 715/243, 717/143
• US Class Current: 715/237
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

A method to generate an effective schema of an electronic document for optimizing the processing thereof may include performing a programmatic analysis to determine all required portions of the electronic document. The method may also include generating a parser or deserializer to build an optimized document model; and specializing a document processing program against the optimized document model.

Claims

1. A method to generate an effective schema of an electronic document for optimizing the processing thereof, comprising:

performing a programmatic analysis to determine required portions of the electronic document prior to generating a parser to generate an optimized document model, wherein the performing programmatic analysis comprises;

beginning at a document root path;

proceeding into a template matching a root corresponding to the document root path;

setting a current context as the root;

determining portions of the document required to compute an expression, wherein determining portions of the document required to compute an expression comprises;

identifying an xs1;

value-of expression as requiring a string-value of a first node in a node set selected by a specified path through the document;

identifying an xs1;

for-each expression as requiring portions of the document necessary to evaluate a select expression of the xs1;

for-each expression as well as a body of the xs1;

for-each expression;

identifying an xs1;

choose expression as requiring portions of the document necessary to evaluate any tests, handlers and default clause;

identifying an xs1;

call-template expression as requiring portions of the document necessary to evaluate any parameter and to evaluate a body of the called template determined by the xs1;

call-template expression, wherein template body uses are recomputed for each template call in response to multiple calls to a template in the document with different document portions being bound to parameters, and wherein document use of a definition will be recursive in response to the xs1;

call-template being one of recursive and mutually recursive; and

requiring a path into a document tree specified by a path expression;

generating the optimized document model; and

specializing a document processing program against the optimized document model.

2. The method of claim 1, further comprising generating the parser to produce the optimized document model using the required portions of the document.

3. The method of claim 1, further comprising determining if one of the required portions of the electronic document is being handled by tracking an encountered element against a set of required paths.

4. The method of claim 3, further comprising building up a plurality of nodes corresponding to each of the required portions of the document, each node being tagged to its corresponding required portions of the document.

5. The method of claim 4, further comprising:

building up an indexed document tree as the plurality of nodes returned up a parse stack; and

using the required portions of the document as determined by the programmatic analysis as an input to an input specialization transformation module for optimizing the document processing program.

6. The method of claim 1, further comprising rendering the documents with a shorter processing time and a reduced memory requirement than without optimization.

7. The method of claim 1, further comprising conditioning the document processing program to facilitate programmatic analysis.

8. The method of claim 7, wherein conditioning the document processing program to facilitate programmatic analysis comprises:

generating a complete stylesheet;

removing any reverse path use from the processing program;

desugaring alternative equivalent expressions to one canonical form;

converting implied actions to explicit actions; and

assigning a unique identification to each template.

9. The method of claim 8, wherein generating the complete stylesheet comprises:

evaluating all includes and imports; and

applying all modes, template priorities and import precedences.

10. The method of claim 1, wherein performing a programmatic analysis to determine required portions of the electronic document comprises determining used portions of the document via a whole-program data use analysis.

11. A system to generate an effective schema of an electronic document for optimizing the processing thereof, comprising:

a programmatic analyzer to determine required portions of the electronic document prior to parsing, wherein the programmatic analyzer comprises;

means for identifying a document root path to begin analysis;

means for proceeding into a template matching a root corresponding to the document root path;

means for setting a current context as the root;

means for determining portions of the document required to compute an expression;

means for identifying any xs1;

value-of expression as requiring a string-value of a first node in a node set selected by a specified path through the document;

means for identifying an xs1;

for-each expression as requiring portions of the document necessary to evaluate a select expression of the xs1;

for-each expression as well as an xs1;

for-each body;

means for identifying an xs1;

choose expression as requiring portions of the document necessary to evaluate any tests, handlers and default clause;

means for identifying an xs1;

call-template as requiring portions of the document necessary to determine any parameter and to evaluate a body of a called template determined by the xs1;

call-template expression, wherein template body uses are recomputed for each template call in response to multiple calls to a template in the document with different document portions being bound to the parameters, and wherein document use of a definition will be recursive in response to the xs1;

call-template being one of recursive and mutually recursive;

means for determining a path into a document tree specified by the specified path;

a parser to build up an indexed document tree including a plurality of nodes each corresponding to a required portion of the electronic document; and

an input specialization transform module to optimize a document processing program against an optimized document model from the parser.

12. The system of claim 11, further comprising a document conditioner to condition the document processing program to facilitate programmatic analysis.

13. A computer program product to generate an effective schema of an electronic document for optimizing the processing thereof, the computer program product comprising:

a computer usable medium having computer usable program code embodied therein, the computer usable medium comprising;

computer usable program code configured to perform a programmatic analysis to determine required portions of the electronic document prior to parsing to generate an optimized document model, wherein the computer useable program code configured to perform the programmatic analysis comprises;

computer useable program code configured to begin at a document root path;

computer useable program code configured to proceed into a template matching a root corresponding to the document root path;

computer useable program code configured to set a current context as the root;

computer useable program code configured to determine portions of the document required to compute an expression, wherein the computer useable program code configured to determine portions of the document required to compute an expression comprises;

computer useable program code configured to identify an xs1;

value-of expression as requiring a string-value of a first node in a node set selected by a specified path through the document;

computer useable program code configured to identify an xs1;

for-each expression as requiring portions of the document necessary to evaluate a select expression of the xs1;

for-each expression as well as a body of the xs1;

for-each expression;

computer useable program code configured to identify an xs1;

choose expression as requiring portions of the document necessary to evaluate any tests, handlers and default clause;

computer useable program code configured to identify an xs1;

call—

template expression as requiring portions of the document necessary to evaluate any parameter and to evaluate a body of the called template determined by the xs1;

call-template expression, wherein template body uses are recomputed for each template call in response to multiple calls to a template in the document with different document portions being bound to parameters, and wherein document use of a definition will be recursive in response to the xs1;

call-template being one of recursive and mutually recursive; and

computer useable program code configured to require a path into a document tree specified by a path expression;

computer usable program code configured to generate the optimized document model; and

computer usable program code configured to specialize a document processing program against the optimized document model.

14. The computer program product of claim 13, wherein the computer usable medium further comprises computer usable program code configured to generate a parser to produce the optimized document model using the required portions of the document.

15. The computer program product of claim 13, wherein the computer usable medium further comprises computer usable program code configured to build up a plurality of nodes corresponding to each of the required portions of the document to form an indexed document tree, each node being tagged to its corresponding one of the required portions of the document.

16. The computer program product of claim 13, wherein the computer usable medium further comprises computer usable program code configured to determine used portions of the document via a whole-program data use analysis.