Method of compiling schema mapping

• US 6,874,141 B1
• Filed: 06/29/2000
• Issued: 03/29/2005
• Est. Priority Date: 06/29/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Taylor, William R., Swamy, Shekhar N.
• Primary Examiner(s): Zhen, Wei Y.
• Assistant Examiner(s): Kiss, Eric B.
• Application Number:
  US09/607,560
• Time in Patent Office: 1,734 Days
• Field of Search: 717/106, 717/109, 717/142, 717/143, 717/144, 709/102, 709/101, 715/513
• US Class Current: 717/144
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• 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/16 Automatic learning of transformation rules, e.g. from examples
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for compiling a mapping between a source schema and a target schema is provided. The method comprises multiple passes, including determining source node dependencies, matching hierarchy, and generating code. The method may further comprise initializing node dependency memory prior to determining source node dependencies, and freeing node dependency memory after code generation. The compiler algorithm provides for compiling user-defined functions in the mapping into the compiled representation. Another aspect of the invention provides for generating an XSL code representation of the mapping. An XSL style sheet representation may thus be generated from a visual mapping in accordance with the invention.

Claims

1. A method of generating code representing a mapping between a source schema, and a target schema, the source schema comprising a source tree having a source node and the target schema comprising a target tree having a target node, the method comprising:

initializing node dependencies memory comprising;

allocating memory for a compiler node;

associating the compiler node with the target node;

allocating memory for compiler variable classes; and

associating compiler variable classes with functoids;

determining source node dependencies for the target node by tracing from the target node through the mapping to the source schema, wherein the mapping comprises defined data transformations from the source schema to the target schema, and wherein determining source node dependencies comprises;

creating a target dependencies list for the target node;

creating a source dependencies list for the target node;

tracing back to the source tree through all possible paths recursively, adding source tree nodes to corresponding source dependencies lists;

setting a flag for the compiler nodes associated with the target node and an associated parent compiler node if there is a path from the target tree node to the source tree;

adding the target tree node to the target dependency list of an associated parent record node if the target node is a field node;

consolidating the target dependency list for target record nodes;

consolidating the source dependency list for target record nodes;

selecting a source loop path node for the target node according to the consolidated source dependency lists; and

storing the source loop path node in the compiler node associated with the target node;

matching hierarchy by generating a hierarchy match list for the target node; and

generating code according to the hierarchy match list.

2. The method of claim 1, wherein consolidating the target dependency list for target record nodes comprised adding child record nodes to the target dependency list if the target record node has a child field node with a flag set and the target record node has a child record node with a flag set, and wherein consolidating the source dependency list for target record nodes comprises adding source dependencies of each node in the target dependency list to the target dependency list.

3. The method of claim 2, wherein selecting a source loop path node for the target node according to the consolidated source dependency list comprises:

iterating through source nodes in the source dependency list;

finding the highest level loop point for which more than one occurrence of the source node is possible;

storing the current node in the source dependency list as the source loop path node if no loop point is found;

storing the current node in the source dependency list as the source loop path node if the current loop point is at a higher level than the previous loop point and if the paths to the previous and current loop points converge;

storing the previous node in the source dependency list as the source loop path node if the current loop point is at a lower level than the previous loop point and if the paths to the previous and current loop points converge;

storing the current node in the source dependency list as the source loop path node if the current loop point is at the same level as the previous loop point, and if the paths to the previous and current loop points converge;

generating a compiler error if the paths to the previous and current loop points do not converge.

4. The method of claim 3, wherein finding the highest level loop point for which more than one occurrence of the source node is possible comprises finding the highest level loop point for which maxoccurs =*.

5. The method of claim 3, wherein storing the source loop path node in the compiler node associated with the target node comprises:

storing the source loop path node as the source loop path node in the compiler node if the source loop path node is a record node; and

storing the parent record node of the source loop path bode as the source loop path node in the compiler node if the source loop path node is a field node.

6. The method of claim 5, wherein matching hierarchy by generating a hierarchy match list for the target node comprises:

creating a hierarchy match list for the target node if the target node has a source loop path node;

determining a consolidated compiler link option using links on target node dependencies; and

matching hierarchy according to the consolidated compiler link option.

7. The method of claim 6, wherein matching hierarchy according to the consolidated compiler link option comprises:

climbing up the source tree from the source loop path node, adding each source node to the hierarchy match list for the target node if the compiler link option is flattening;

traversing up the source tree until the source tree node level matches the target node level, adding source tree nodes to the hierarchy match list if the target node level is greater than the source loop path node level and if the compiler link option is top-down;

traversing up the target tree until the source tree node level matches the target node level, adding the source loop path node to the hierarchy match list of each target node traversed if the source loop path node level is greater than the target node level and if the compiler link option is top-down;

traversing up the source and target trees, adding source tree nodes to the hierarchy match lists of target nodes level by level if the compiler link option is top-down;

traversing up the source and target trees, adding source nodes to the hierarchy match lists of target nodes until level 1 of either the source or the target tree is reached if the compiler link option is bottom-up;

traversing up the source tree, adding the source tree node to the hierarchy match lists of the target tree nodes if the compiler link option is bottom-up and if level 1 of the target tree is reached; and

traversing up the source tree, adding the source tree nodes to the hierarchy match list of the target node.

8. The method of claim 7, wherein generating code according to the hierarchy match list comprises:

generating a code header for a root node;

generating a code trailer for the root node;

processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function; and

processing filed nodes in the executeleaf function.

9. The method of claim 8, wherein processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function comprises:

generating <

xsl;

for-each>

code in the preexecuteparent function using the hierarchy match list;

generating <

xsl;

if>

code in the preexecute parent function if there is an incoming link from a conditional functoid;

generating a start tag code for the target record node in the preexecuteparent function;

generating <

/xsl;

if>

code in the postexecuteparent function for record nodes if there is an incoming link from a conditional functoid;

generating <

xsl;

value-of>

code in the postexecuteparent function for record nodes if the incoming link is not from a conditional link by traversing a grid to source nodes; and

generating code for constant node values;

generating <

xsl;

for-each>

code in the postexecuteparent function for record nodes using the hierarchy match list;

generating <

xsl;

for-each>

code in the executeleaf function for leaf record nodes using the hierarchy match list;

generating <

xsl;

if>

code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating a start tag code in the executeleaf function for leaf records;

generating <

xsl;

if>

code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating <

xsl;

value-of>

code in the executeleaf function for leaf record nodes if the incoming link is not from a conditional link by traversing the grid to source nodes, and generating code for constant node values; and

generating <

xsl;

value-of>

code in the executeleaf function for field nodes by traversing grid to source nodes, and generating code for constant node values.

10. The method of claim 9, wherein generating <

xsl;

value-of>

code comprises;

using the value of a source tree node to generate code if the link is simple; and

tracing back to the source tree through all possible paths recursively and generating <

xsl;

variable name=. . . select=. . . />

code for each functoid if there is a functoid link.

11. The method of claim 10, wherein determining source node dependencies for the target node by tracing from the target node through the mapping to the source schema comprised depth-first tree traversal of the target tree, matching hierarchy by generating a hierarchy match list for the target node comprises depth-first tree traversal of the target tree, and wherein generating code according to the hierarchy match list comprises field-attribute tree traversal of the target tree.

12. The method of claim 8, wherein processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function comprises:

generating looping start code in the preexecuteparent function using the hierarchy match list;

generating conditional start code in the preexecuteparent function if there is an incoming link from a conditional functoid;

generating a start tag code for the target record node in the preexecuteparent function;

generating conditional end code in the postexecuteparent function for record nodes if there is an incoming link from a conditional functoid;

generating value code in the postexecuteparent function for record nodes if the incoming link is not from a conditional link by traversing a grid to a source nodes, and generating code for constant node values;

generating looping end code in the postexecuteparent function for record nodes using the hierarchy match list;

generating looping start code in the executeleaf function for leaf record nodes using the hierarchy match list;

generating conditional start code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating a start tag code in the executeleaf function for leaf records;

generating conditional end code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating value code in the executeleaf function for leaf record nodes if the incoming link is not from a conditional link by traversing the grid to source nodes, and generating code for constant node values; and

generating value code in the executeleaf functions for field nodes by traversing grid to source nodes, and generating code for constant node values.

13. The method of claim 1, wherein generating code according to the hierarchy match list comprises:

generating a code header for a root node;

generating a code trailer for the root node;

processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function; and

processing field nodes in the executeleaf function.

14. The method of claim 1, wherein generating code according to the hierarchy match list comprises creating an XSL style sheet representation of the mapping.

15. The method of claim 1, wherein the method is performed by computer-executable instructions that are stored on computer-readable media.

16. The method of claim 1, wherein the method is performed by computer-executable instructions that are transmitted by an electrical signal.

17. A method of generating code representing a mapping between a source schema and a target schema, the source schema comprising a source tree having a source node and the target schema comprising a target tree having a target node, the method comprising:

initializing node dependencies memory comprising;

allocating memory for a compiler node;

associating the compiler node with the target node;

allocating memory for compiler variable classes; and

associating compiler variable classes with functoids;

determining source node dependencies for the target node by tracing from the target node through the mapping to the source schema, wherein the mapping comprises defined data transformations from the source schema to the target schema;

matching hierarchy by generating a hierarchy match list for the target node, wherein matching hierarchy by generating a hierarchy match list for the target node comprises;

creating a hierarchy match list for the target node if the target node has a source loop path node;

determining a consolidated compiler link option using links on target node dependencies; and

matching hierarchy according to the consolidated compiler link option; and

generating code according to the hierarchy match list.

18. A method of generating code representing a mapping between a source schema and a target schema, the source schema comprising a source tree having a source node and the target schema comprising a target tree having a target node, the method comprising:

initializing node dependencies memory comprising;

allocating memory for a compiler node;

associating the compiler node with the target node;

allocating memory for compiler variable classes; and

associating compiler variable classes with functoids;

determining source node dependencies for the target node by tracing from the target node through the mapping to the source schema, wherein the mapping comprises defined data transformations from the source schema to the target schema;

matching hierarchy by generating a hierarchy match list for the target node; and

generating code according to the hierarchy match list, wherein generating code according to the hierarchy match list comprises;

generating a code header for a root node;

generating a code trailer for the root node;

processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function, wherein processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function comprises;

generating <

xsl;

for-each>

code in the preexecuteparent function using the hierarchy match list;

generating <

xsl;

if>

code in the preexecuteparent function if there is an incoming link from a conditional functoid;

generating a start tag code for the target record node in the preexecuteparent function;

generating <

/xsl;

if>

code in the postexecuteparent function for record nodes if there is an incoming link from a conditional functoid;

generating <

xsl;

value-of>

code in the postexecuteparent function for record nodes if the incoming link is not from a conditional link by traversing a grid to source nodes, and generating code for constant node values;

generating <

/xsl;

for-each>

code in the postexecuteparent function for record nodes using the hierarchy match list;

generating <

xsl;

for-each>

code in the executeleaf function for leaf record nodes using the hierarchy match list;

generating <

xsl;

if>

code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating a start tag code in the executeleaf function for leaf records;

generating <

xsl;

if>

code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating <

xsl;

value-of>

code in the executeleaf function for leaf record nodes if the incoming link is not from a conditional link by traversing the grid to source nodes, and generating code for constant node values; and

generating <

xsl;

value-of>

code in the executeleaf function for field nodes by traversing grid to source nodes, and generating code for constant node values; and

processing field nodes in the executeleaf function.

19. A method of generating code representing a mapping between a source schema and a target schema, the source schema comprising a source tree having a source node and the target schema comprising a target tree having a target node, the method comprising:

initializing node dependencies memory comprising;

allocating memory for a compiler node;

associating the compiler node with the target node;

allocating memory for compiler variable classes; and

associating compiler variable classes with functoids;

determining source node dependencies for the target node by tracing from the target node through the mapping to the source schema, wherein the mapping comprises defined data transformations from the source schema to the target schema;

matching hierarchy by generating a hierarchy match list for the target node;

generating code according to the hierarchy match list, wherein generating code according to the hierarchy match list comprises;

generating a code header for a root node;

generating a code trailer for the root node;

processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function, wherein processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function comprises;

generating looping start code in the preexecuteparent function using the hierarchy match list;

generating conditional start code in the preexecuteparent function if there is an incoming link from a conditional functoid;

generating a start tag code for the target record node in the preexecuteparent function;

generating conditional end code in the postexecuteparent function for record nodes if there is an incoming link from a conditional functoid;

generating value code in the postexecuteparent function for record nodes if the incoming link is not from a conditional link by traversing a grid to source nodes, and generating code for constant node values;

generating looping end code in the postexecuteparent function for record nodes using the hierarchy match list;

generating looping start code in the executeleaf function for leaf record nodes using the hierarchy match list;

generating conditional start code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating a start tag code in the executeleaf function for leaf records;

generating conditional end code in the executeleaf function for leaf record nodes if there is an incoming link from a conditional functoid;

generating value code in the executeleaf function for leaf record nodes if the incoming link is not from a conditional link by traversing the grid to source nodes, and generating code for constant node values; and

generating value code in the executeleaf function for field nodes by traversing grid to source nodes, and generating code for constant node values; and

processing field nodes in the executeleaf function.

20. A method for compiling a mapping between a source schema having source nodes associated therewith, and a target schema having target nodes associated therewith, comprising:

determining source node dependencies for at least one target node by tracing from the at least one target node through the mapping to the source schema, wherein determining source node dependencies comprises picking a source loop path for each target node, and detecting multiple source loop paths and wherein the mapping comprises defined data transformations from the source schema to the target schema;

matching hierarchy by generating a hierarchy match list for the at least one target node; and

generating code according to the hierarchy match list.

21. The method of claim 20, further comprising generating a compiler error if multiple source loop paths are detected.

22. The method of claim 21, wherein the method is performed by computer-executable instructions that are stored on computer-readable media.

23. The method of claim 21, wherein the method is performed by computer-executable instructions that are transmitted by an electrical signal.

24. The method of claim 20, wherein matching hierarchy comprises one of flattening, top-down, and bottom-up matching.

25. The method of claim 20, wherein the source schema and the target schema are XML schemas.

26. The method of claim 20, wherein generating code comprises creating an XSL style sheet representation of the mapping.

27. The method of claim 20, further comprising:

initializing node dependencies memory prior to determining source dependencies; and

freeing node dependencies memory after generating code.

28. The method of claim 20, further comprising:

initializing node dependencies memory comprising;

allocating memory for a compiler node;

associating the compiler node with the target node;

allocating memory for compiler variable classes; and

associating compiler variable classes with functoids.

29. The method of claim 20, wherein generating code according to the hierarchy match list comprises:

generating a code header for a root node;

generating a code trailer for the root node;

processing target record nodes in a preexecuteparent function, a postexecuteparent function, and an executeleaf function; and

processing filed nodes in the executeleaf function.

30. The method of claim 20, wherein matching hierarchy by generating a hierarchy match list for the at least one target node comprises:

creating a hierarchy match list for the at least one target node if the at least one target node has a source loop path node;

determining a consolidated compiler link option using links on target node dependencies; and

matching hierarchy according to the consolidated compiler link option.

31. The method of claim 20, wherein the method is performed by computer-executable instructions that are stored on computer-readable media.

32. The method of claim 20, wherein the method is performed by computer-executable instructions that are transmitted by an electrical signal.