Efficient storage and retrieval of XML data

• US 10,565,178 B1
• Filed: 03/11/2015
• Issued: 02/18/2020
• Est. Priority Date: 03/11/2015
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Rajagopal, Hari Ohm Prasath
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Nafziger, David M
• Application Number:
  US14/644,763
• Time in Patent Office: 1,805 Days
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226

Abstract

A computing server can receive, from a computing device, an extensible markup language document and a location path pointing to an identifier uniquely identifying the extensible markup language document. The computing server can rearrange data within the extensible markup language document to generate a table including data arranged according to one or more location paths indicated by the extensible markup language document. Each location path of the one or more location paths can point to a storage location for data listed under the location path. The table can be specific to the identifier uniquely identifying the extensible markup language document. The computing server can store the table in a data store connected to the computing server. The computing server can retrieve, when required, the stored data from the data store within a time independent of a total number of XML documents in the data store.

Claims

1. A method comprising:

receiving, by a computing server comprising at least one programmable processor and from a computing device connected to the computing server, an extensible markup language document and a location path pointing to a unique path identifier uniquely identifying the extensible markup language document, the extensible markup language document and the location path being received separately, the extensible markup language document characterizing a tree having a root node and a plurality of child nodes;

generating, by the computing server, an in-memory first table that maps data within the extensible markup language document to one or more location paths, at least one location path of the one or more location paths being formed by combining the root node and a corresponding child node of the plurality of child nodes;

generating, by the computing server and by rearranging data within the in-memory first table, a second table comprising data arranged according to one or more location paths that are indicated by the extensible markup language document, the at least one location path of the one or more location paths pointing to a storage location for data listed under the location path in the table, the second table being specific to the unique path identifier, wherein generating the second table comprises;

retrieving the one or more location paths in the extensible markup language document and extensible markup language values associated with the possible location paths,

determining, by the computing server, the unique path identifier stored within the first table, and

serially processing, by the computing server, all entries in the first table, wherein the serially processing comprises;

receiving an entry from the first table, the entry comprising a location path and the unique path identifier,

determining that the entry does not exist in the second table,

creating, in response to the determining and from the first table, a location path and value pair for the unique path identifier, the location path and value pair comprising a location path and a corresponding value specific to the unique path identifier,

obtaining, in response to the determining indicating that the entry does exist in the second table, values associated with the location path and the unique path identifier,

determining, by the computer server, whether an entry exists in the first table having any location path of the one or more location paths and the unique path identifier,

creating, in response to determining the entry does not exist in the first table, a location path and value pair for the unique path identifier,

obtaining, in response to the determining indicating the entry does exist in the first table, a list of values associated with any location path of the one or more location paths and the unique path identifier,

determining, by the computer server, whether data stored in the in-memory data store exists in the obtained list of values,

adding, in response to the determining indicating the data does not exist in the obtained list of values, data indicated in a search query to the obtained list of values and

updating, in response to the adding, the obtained list of values associated with any location path of the one or more like location paths inside the second table, and

determining, by the computer server, whether all entries of the first table have been processed; and

storing, by the computing server and in response to determining that all entries of the first table have been processed, the second table in a data store connected to the computing server, the stored second table being searchable in a time that is independent of a total number of extensible markup language documents stored in the data store;

receiving, by the computing server and from the computing device, the search query, the search query including a specific location path of the one or more location paths and the unique path identifier;

searching, by the computing server, the second table in the data store for a data associated with the specific location path and the unique path identifier specified in the search query, the time taken to retrieve the searched data being independent of the total number of extensible markup language documents stored in the data store; and

sending, by the computing server, the searched data associated with the specific location path and the unique path identifier specified in the search query to the computing device.

2. The method of claim 1, wherein the table further comprises data arranged according to another location path that represents a combination of the one or more location paths that are generated using the extensible markup language document, the data arranged according to the another location path comprising data pointed to by each of the one or more location paths.

3. The method of claim 1, wherein the computing device is configured to display the searched data on a graphical user interface.

4. The method of claim 1, wherein:

the receiving of the extensible markup language document and the location path, the generating of the table, and the storing of the table occur in design-time; and

the receiving of the search query, the searching of the table, and the sending of the searched data occur in real-time.

5. The method of claim 1, further comprising:

receiving, by the computing server and from the computing device, a search query including data stored in the table in the data store;

searching, by the computing server, the table in the data store for the identifier associated with the data stored in the table in the data store; and

sending, by the computing server, the identifier to the computing device.

6. The method of claim 5, wherein the computing device is configured to display the searched identifier on a graphical user interface.

7. The method of claim 5, wherein:

the receiving of the extensible markup language document and the location path, the generating of the table, and the storing of the table occur in design-time; and

the receiving of the search query, the searching of the table, and the sending of the searched data occur in real-time.

8. The method of claim 1, wherein the computing device is connected to the computing server via a communication network.

9. The method of claim 1, wherein:

the data store is connected to the computing server via a communication network; and

the data store is a key value data store comprising one or more keys and one or more values associated with the one or more keys, the one or more keys being the one or more location paths, the one or more values being the data listed under the one or more location paths.

10. A system comprising:

a computing device having an extensible markup language document and a location path pointing to a unique path identifier uniquely identifying the extensible markup language document;

a computing server operatively coupled to the computing device, the computing server comprising at least one programmable processor configured to;

separately receive the extensible markup language document and the location path from the computing device,

generate, by rearranging data within the extensible markup language document, a second table comprising data arranged according to one or more location paths that are indicated by the extensible markup language document, each location path of the one or more location paths pointing to a storage location for data listed under the location path, the second table being specific to the unique path identifier, wherein generating the second table comprises;

retrieving the one or more location paths in the extensible markup language document and all extensible markup language values associated with the possible location paths,

determining, by the computing server, the unique path identifier stored within the first table, and

serially processing, by the computing server, all entries in the first table, wherein the serially processing comprises;

receiving an entry from the first table, the entry comprising a location path and the unique path identifier,

creating, in response to the receiving and from the first table, a location path and value pair for the unique path identifier, the location path and value pair comprising a location path and a corresponding value specific to the unique path identifier,

obtaining, in response to the creating, values associated with the location path and the unique path identifier,

creating, in response to determining the entry does not exist in the first table, a location path and value pair for the unique path identifier,

obtaining, in response to an indication the entry does exist in the first table, a list of values associated with any location path of the one or more location paths and the unique path identifier,

adding, in response to an indication the entry does not exist in the obtained list of values, data indicated in a search query to the obtained list of values and

updating, in response to the adding, the obtained list of values associated with any location path of the one or more like location paths inside the second table, and

determining, by the computer server, whether all entries of the first table have been processed; and

store, by the computing server and in response to determining that all entries of the first table have been processed, the second table in a data store connected to the computing server, the stored second table being searchable in a time that is independent of a total number of extensible markup language documents stored in the data store;

receiving, by the computing server and from the computing device, the search query, the search query including a specific location path of the one or more location paths and the unique path identifier;

searching, by the computing server, the second table in the data store for a data associated with the specific location path and the unique path identifier specified in the search query, the time taken to retrieve the searched data being independent of the total number of extensible markup language documents stored in the data store; and

sending, by the computing server, the searched data associated with the specific location path and the unique path identifier specified in the search query to the computing device.

11. The system of claim 10, wherein the computing device executes a graphical user interface configured to display the searched data.

12. The system of claim 10, wherein:

the receiving of the extensible markup language document and the location path, the generating of the table, and the storing of the table occur in design-time; and

the receiving of the search query, the searching of the table, and the sending of the searched data occur in real-time.

13. The system of claim 10, wherein the computing server is further configured to:

receive, from the computing device, a search query including data stored in the table in the key value data store;

search the table in the key value data store for the identifier associated with the data stored in the table in the key value data store; and

send the identifier to the computing device.

14. The system of claim 13, wherein the computing device includes a user interface device that is configured to display the searched identifier.

15. The system of claim 13, wherein:

the receiving of the extensible markup language document and the location path, the generating of the table, and the storing of the table occur in design-time; and

the receiving of the search query, the searching of the table, and the sending of the searched data occur in real-time.

16. The system of claim 10, wherein the computing device is operatively coupled to the computing server via a communication network.

17. The system of claim 10, wherein the key value data store is operatively coupled to the computing server via a communication network.

18. The system of claim 10, wherein generating the second table further comprises:

determining by the computer server, that the entry from the first table does not exist in the second table, determining, by the computer server, whether an entry exists in the first table having any location path of the one or more location paths and the unique path identifier, and

determining, by the computer server, whether data stored in the in-memory data store exists in the obtained list of values.

19. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

receiving an extensible markup language document and a location path pointing to a unique path identifier uniquely identifying the extensible markup language document, the location path being external to the extensible markup language document during the receiving of the extensible markup language document and the location path, the extensible markup language document characterizing a tree having a root node and a plurality of child nodes;

generating an in-memory first table that maps data within the extensible markup language document to one or more location paths, each location path of the one or more location paths being formed by combining the root node and a corresponding child node of the plurality of child nodes, each location path of the one or more location paths pointing to a storage location for data listed under the location path;

generating, by modifying at least one of order and position of data within the in-memory first table, a second table comprising data arranged according to one or more location paths that are indicated by the extensible markup language document, the second table being specific to the unique path identifier, wherein generating the second table comprises;

retrieving the one or more location paths in the extensible markup language document and all extensible markup language values associated with the possible location paths,

determining, by the computing server, the unique path identifier stored within the first table, and

serially processing, by the computing server, all entries in the first table, wherein the serially processing comprises;

receiving an entry from the first table, the entry comprising a location path and the unique path identifier,

determining that the entry does not exist in the second table,

creating, in response to the determining and from the first table, a location path and value pair for the unique path identifier, the location path and value pair comprising a location path and a corresponding value specific to the unique path identifier,

obtaining, in response to the determining indicating that the entry does exist in the second table, values associated with the location path and the unique path identifier,

determining, by the computer server, whether an entry exists in the first table having any location path of the one or more location paths and the unique path identifier,

creating, in response to determining the entry does not exist in the first table, a location path and value pair for the unique path identifier,

obtaining, in response to the determining indicating the entry does exist in the first table, a list of values associated with any location path of the one or more location paths and the unique path identifier,

determining, by the computer server, whether data stored in the in-memory data store exists in the obtained list of values,

adding, in response to the determining indicating the data does not exist in the obtained list of values, data indicated in a search query to the obtained list of values and

updating, in response to the adding, the obtained list of values associated with any location path of the one or more like location paths inside the second table, and

determining, by the computer server, whether all entries of the first table have been processed; and

storing, by the computing server and in response to determining that all entries of the first table have been processed, the second table in a data store connected to the computing server, the stored second table being searchable in a time that is independent of a total number of extensible markup language documents stored in the data store;

receiving, by the computing server and from the computing device, the search query, the search query including a specific location path of the one or more location paths and the unique path identifier;

searching, by the computing server, the second table in the data store for a data associated with the specific location path and the unique path identifier specified in the search query, the time taken to retrieve the searched data being independent of the total number of extensible markup language documents stored in the data store; and

sending, by the computing server, the searched data associated with the specific location path and the unique path identifier specified in the search query to the computing device.

20. The non-transitory computer program product of claim 19, wherein the operations further comprise:

receiving a second search query including data stored in the table in the key value data store;

searching the table in the key value data store for the identifier associated with the data stored in the table in the key value data store; and

sending the identifier.