METHOD AND SYSTEM FOR EFFECTIVE SCHEMA GENERATION VIA PROGRAMMATIC ANALYSIS

• US 20080282145A1
• Filed: 05/07/2007
• Published: 11/13/2008
• Est. Priority Date: 05/07/2007
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Heifets, Abraham, Perkins, Eric David, Kesselman, Joseph J.
• Granted Patent: US 8,276,064 B2
• Time in Patent Office: Days
• 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 all required portions of the electronic document;

generating an optimized document model; and

specializing a document processing program against the optimized document model.

2. The method of claim 1, further comprising generating a 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 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; and

determining all portions of the document required to compute an expression.

11. The method of claim 10, wherein determining all 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 all portions of the document necessary to evaluate a select expression of the xs1;

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

for-each expression;

identifying an xs1;

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

identifying an xs1;

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

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.

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

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

a programmatic analyzer to determine all required portions of the electronic document;

a parser to build up an indexed document tree including a plurality of nodes corresponding 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.

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

15. The system of claim 13, 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; and

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

16. The system of claim 15, further comprising:

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 all portions of the document necessary to evaluate a select expression of the xs1;

for-each expression as well as an xsl;

for-each body;

means for identifying an xs1;

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

means for identifying an xs1;

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

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; and

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

17. 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 all required portions of the electronic document;

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

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

18. The computer program product of claim 17, 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.

19. The computer program product of claim 17, 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

20. The computer program product of claim 17, 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.