Mapping data structures

• US 8,626,799 B2
• Filed: 10/03/2011
• Issued: 01/07/2014
• Est. Priority Date: 10/03/2011
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Bahl, Rohit, Funk, Eric O., Yeung, Alan
• Primary Examiner(s): BROWN, SHEREE N
• Application Number:
  US13/251,858
• Publication Number:
  US 20130086124A1
• Time in Patent Office: 827 Days
• Field of Search: 707/802
• US Class Current: 707/802
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

A method for transforming data structures includes processing a portion of a source data structure (SDS) with a first processing resource by associating the first processing resource with a target data structure (TDS) key element located in a key position of a queue, determining whether the queue includes an SDS node element corresponding to the key position, processing the SDS node element responsive to determining that the queue includes the SDS node element corresponding to the key position, wherein the processing the SDS node element comprises retrieving the SDS node element from the queue, processing the retrieved SDS node element to generate a resultant TDS node element, outputting the resultant TDS node element to an empty key position in the queue, and mapping the resultant TDS node element to the TDS.

Claims

1. A computer implemented method for transforming data structures, the method comprising:

processing a portion of a source data structure (SDS) with a first processing resource by;

associating the first processing resource with a target data structure (TDS) key element located in a key position of a queue, the queue including tasks that transform the SDS to the TDS to perform the associating;

determining whether the queue includes an SDS node element corresponding to the key position based on whether the SDS node element exists in the key position;

processing the SDS node element responsive to determining that the queue includes the SDS node element corresponding to the key position, wherein the processing the SDS node element comprises;

retrieving the SDS node element from the queue;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue;

mapping the resultant TDS node element to the TDS;

determining whether the queue includes a second SDS node element corresponding to the key position; and

processing the second SDS node element responsive to determining that the queue includes the second SDS node element corresponding to the key position,

wherein the processing the retrieved SDS node element to generate a resultant TDS node element comprises;

identifying an SDS element identifier associated with the retrieved SDS node element;

outputting a request for a transform rule, the request including an identifier of the SDS element identifier associated with the retrieved SDS node element and an identifier of the requesting processing resource;

receiving a transform rule associated with the SDS element identifier; and

applying a transform rule corresponding to the identified SDS element identifier to generate the resultant TDS node element.

2. The method of claim 1, further comprising:

processing a second portion of the SDS with a second processing resource by;

determining whether the queue includes any populated key positions that are not being processed;

associating the second processing resource with a TDS key element located in an unprocessed populated key position of the queue;

determining whether the queue includes an SDS node element corresponding to the unprocessed populated key position;

processing the SDS node element responsive to determining that the queue includes the SDS node element corresponding to the unprocessed populated key position, wherein the processing the SDS node element comprises;

retrieving the SDS node element from the queue;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue;

mapping the resultant TDS node element to the TDS;

determining whether the queue includes a second SDS node element corresponding to the key position; and

processing the second SDS node element responsive to determining that the queue includes the second SDS node element corresponding to the key position.

3. The method of claim 1, further comprising:

determining with the first processing resource, whether the queue includes any populated key positions that are not being processed responsive to determining that the queue does not include an SDS node element corresponding to the key position;

associating the first processing resource with a TDS key element located in an unprocessed populated key position of the queue;

determining whether the queue includes an SDS node element corresponding to the key position;

retrieving the SDS node element from the queue responsive to determining that the queue includes the SDS node element corresponding to the key position;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue; and

mapping the resultant TDS node element to the TDS.

4. The method of claim 1, wherein the processing the retrieved SDS node element to generate a resultant TDS node element comprises:

identifying an SDS element identifier associated with the retrieved SDS node element; and

applying a transform rule corresponding to the identified SDS element identifier to generate the resultant TDS node element.

5. The method of claim 1, wherein the processing of the portion of the SDS with the first processing resource is performed in parallel with the processing of the second portion of the SDS with the second processing resource.

6. The method of claim 1, further comprising processing requests for transform rules, wherein the processing requests for transform rules includes:

receiving a request for a transform rule at a third processing resource and a fourth processing resource, the request including an identifier of the SDS element identifier associated with the retrieved SDS node element and an identifier of the requesting processing resource;

processing the request with the third processing resource and the fourth processing resource, the third processing resource is associated with a first list of transform rules and the fourth processing resource is associated with a second list of transform rules, wherein the processing includes;

the third processing resource determining whether the first list of transform rules includes an SDS element identifier matching the received SDS element identifier;

the third processing resource sending a transform rule associated with the SDS element identifier to the requesting processing resource, and [[a]]an indicator to the fourth processing resource indicating that the request has been satisfied responsive to determining that the first list of transform rules includes the SDS element identifier matching the received SDS element identifier;

the fourth processing resource determining whether the second list of transform rules includes an SDS element identifier matching the received SDS element identifier; and

the fourth processing resource sending a transform rule associated with the SDS element identifier to the requesting processing resource, and an indicator to the third processing resource indicating that the request has been satisfied responsive to determining that the second list of transform rules includes the SDS element identifier matching the received SDS element identifier.

7. The method of claim 6, further comprising:

the fourth processing resource ceasing the determination of whether the second list of transform rules includes an SDS element identifier matching the received SDS element identifier responsive to receiving the indicator from the third processing resource indicating that the request has been satisfied.

8. The method of claim 6, wherein the first list of transform rules and the second list of transform rules are dissimilar.

9. The method of claim 6, further comprising:

retrieving a user definable function that defines an allocation of a plurality of processing resources, the plurality of processing resources includes at least the first, second, third, and fourth processing resources; and

allocating the each of the processing resources of the plurality of resources for either processing requests for transform rules or processing portions of the SDS according the user definable function.

10. A system for transforming data structures comprising:

a microprocessor including a queue including target data structure (TDS) key positions and source data structure (SDS) element positions associated with the TDS key positions;

a first processing resource executable by the microprocessor, the first processing resource operative to process a portion of a source data structure (SDS) with a first processing resource by;

associating the first processing resource with a target data structure (TDS) key element located in a key position of a queue, the queue including tasks that transform the SDS to the TDS to perform the associating;

determining via the microprocessor whether the queue includes an SDS node element corresponding to the key position based on whether the SDS node element exists in the key position;

processing the SDS node element via the microprocessor in response to determining that the queue includes the SDS node element corresponding to the key position, wherein the processing the SDS node element comprises;

retrieving the SDS node element from the queue;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue;

mapping the resultant TDS node element to the TDS;

determining whether the queue includes a second SDS node element corresponding to the key position; and

processing the second SDS node element responsive to determining that the queue includes the second SDS node element corresponding to the key position,

wherein the processing the retrieved SDS node element to generate a resultant TDS node element comprises;

identifying an SDS element identifier associated with the retrieved SDS node element; and

applying a transform rule corresponding to the identified SDS element identifier to generate the resultant TDS node element.

11. The system of claim 10, further comprising a second processing resource operative to process a second portion of the SDS by:

determining whether the queue includes any populated key positions that are not being processed;

associating the second processing resource with a TDS key element located in an unprocessed populated key position of the queue;

determining whether the queue includes an SDS node element corresponding to the unprocessed populated key position;

processing the SDS node element responsive to determining that the queue includes the SDS node element corresponding to the unprocessed populated key position, wherein the processing the SDS node element comprises;

retrieving the SDS node element from the queue;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue;

mapping the resultant TDS node element to the TDS;

determining whether the queue includes a second SDS node element corresponding to the key position; and

processing the second SDS node element responsive to determining that the queue includes the second SDS node element corresponding to the key position.

12. The system of claim 10, wherein the first processing resource is further operative to determine whether the queue includes any populated key positions that are not being processed responsive to determining that the queue does not include an SDS node element corresponding to the key position, associate with a TDS key element located in an unprocessed populated key position of the queue, determine whether the queue includes an SDS node element corresponding to the key position, retrieve the SDS node element from the queue responsive to determining that the queue includes the SDS node element corresponding to the key position, process the retrieved SDS node element to generate a resultant TDS node element, output the resultant TDS node element to an empty key position in the queue, and map the resultant TDS node element to the TDS.

13. The system of claim 10, wherein the processing the retrieved SDS node element to generate a resultant TDS node element comprises:

identifying an SDS element identifier associated with the retrieved SDS node element;

outputting a request for a transform rule, the request including an identifier of the SDS element identifier associated with the retrieved SDS node element and an identifier of the requesting processing resource;

receiving a transform rule associated with the SDS element identifier; and

applying a transform rule corresponding to the identified SDS element identifier to generate the resultant TDS node element.

14. The system of claim 10, wherein the processing of the portion of the SDS with the first processing resource is performed in parallel with the processing of the second portion of the SDS with the second processing resource.

15. The system of claim 10, wherein the system is further operative to process requests for transform rules, wherein the processing requests for transform rules includes:

receiving a request for a transform rule at a third processing resource and a fourth processing resource, the request including an identifier of the SDS element identifier associated with the retrieved SDS node element and an identifier of the requesting processing resource;

processing the request with the third processing resource and the fourth processing resource, the third processing resource is associated with a first list of transform rules and the fourth processing resource is associated with a second list of transform rules, wherein the processing includes;

the third processing resource determining whether the first list of transform rules includes an SDS element identifier matching the received SDS element identifier;

the third processing resource sending a transform rule associated with the SDS element identifier to the requesting processing resource, an indicator to the fourth processing resource indicating that the request has been satisfied responsive to determining that the first list of transform rules includes the SDS element identifier matching the received SDS element identifier;

the fourth processing resource determining whether the second list of transform rules includes an SDS element identifier matching the received SDS element identifier; and

the fourth processing resource sending a transform rule associated with the SDS element identifier to the requesting processing resource, and an indicator to the third processing resource indicating that the request has been satisfied responsive to determining that the second list of transform rules includes the SDS element identifier matching the received SDS element identifier.

16. The system of claim 15, wherein the fourth processing resource is operative to cease the determination of whether the second list of transform rules includes an SDS element identifier matching the received SDS element identifier responsive to receiving the indicator from the third processing resource indicating that the request has been satisfied.

17. The system of claim 15, wherein the first list of transform rules and the second list of transform rules are dissimilar.

18. The system of claim 15, wherein the system is operative to retrieve a user definable function that defines an allocation of a plurality of processing resources, the plurality of processing resources includes at least the first, second, third, and fourth processing resources, and allocate the each of the processing resources of the plurality of resources for either processing requests for transform rules or processing portions of the SDS according the user definable function.

19. A computer implemented method for processing a request for a transform rule, the method comprising:

processing a portion of a source data structure (SDS) with a first processing resource by;

associating the first processing resource with a target data structure TDS key element located in a key position of a queue, the queue including tasks that transform the SDS to the TDS to perform the associating;

determining whether the queue includes an SDS node element corresponding to the key position based on whether the SDS node element exists in the key position;

processing the SDS node element responsive to determining that the queue includes the SDS node element corresponding to the key position, wherein the processing the SDS node element comprises;

retrieving the SDS node element from the queue;

processing the retrieved SDS node element to generate a resultant TDS node element;

outputting the resultant TDS node element to an empty key position in the queue;

mapping the resultant TDS node element to the TDS;

determining whether the queue includes a second SDS node element corresponding to the key position; and

processing the second SDS node element responsive to determining that the queue includes the second SDS node element corresponding to the key position,

wherein the processing the retrieved SDS node element to generate a resultant TDS node element comprises;

identifying an SDS element identifier associated with the retrieved SDS node element;

outputting a request for a transform rule, the request including an identifier of the SDS element identifier associated with the retrieved SDS node element and an identifier of the requesting processing resource

receiving said request from a first processing resource,

processing the request with a second processing resource and a third processing resource, the second processing resource is associated with a first list of transform rules and the third processing resource is associated with a second list of transform rules, wherein the processing includes;

the second processing resource determining whether the first list of transform rules includes an SDS element type matching the received SDS element type;

the second processing resource sending a transform rule associated with the SDS element type to the requesting processing resource, and an indicator to the third processing resource indicating that the request has been satisfied responsive to determining that the first list of transform rules includes the SDS element type matching the received SDS element type;

the third processing resource determining whether the second list of transform rules includes an SDS element type matching the received SDS element type; and

the third processing resource sending a transform rule associated with the SDS element type to the requesting processing resource, and an indicator to the second processing resource indicating that the request has been satisfied responsive to determining that the second list of transform rules includes the SDS element type matching the received SDS element type;

receiving a transform rule associated with the SDS element identifier; and

applying a transform rule corresponding to the identified SDS element identifier to generate the resultant TDS node element.

20. The method of claim 19, further comprising the third processing resource ceasing the determination of whether the second list of transform rules includes an SDS element type matching the received SDS element type responsive to receiving the indicator from the second processing resource indicating that the request has been satisfied.

21. The method of claim 19, further comprising the second processing resource ceasing the determination of whether the first list of transform rules includes an SDS element type matching the received SDS element type responsive to receiving the indicator from the third processing resource indicating that the request has been satisfied.

22. The method of claim 19, wherein the first list of transform rules and the second list of transform rules are dissimilar.