LINKED DATA PROCESSOR FOR DATABASE STORAGE

• US 20160321376A1
• Filed: 04/28/2015
• Published: 11/03/2016
• Est. Priority Date: 04/28/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: TAYLOR, JOHN ANTHONY
• Granted Patent: US 10,095,807 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems and methods are provided for storing and retrieving data using a linked data model having a tree format. Instead of using a traditional relational database, a linked data model can be used with links between data items that reflect the underlying business logic. To facilitate retrieval of data, the data items stored using the linked data model can be individually addressable.

Claims

1. A method for storing data in a distributed storage environment, the method comprising:

receiving input data comprising one or more received data items and a corresponding graph representation, the graph representation including a representation of the one or more data items, the graph representation having a tree format, the graph representation including a representation of at least one link between a first data item from the one or more received data items and second data item from a resource saved in durable storage;

applying a plurality of resource determination rules to the graph representation to identify at least one missing resource, the at least one missing resource comprising a plurality of stored data items, the plurality of stored data items including the second data item;

loading the at least one missing resource;

updating the graph representation to include a representation of the plurality of stored data items of the at least one missing resource;

modifying at least one data item of the plurality of stored data items based on the input data, the first data item and second data item being linked after the modifying of the at least one data item;

applying one or more resource creation rules to the updated graph representation to determine a plurality of resources, each resource of the plurality of resources comprising at least one data item; and

saving the determined plurality of resources to durable storage, the determined plurality of resources comprising the one or more received data items and the modified at least one data item.

2. The method of claim 1, wherein the modified at least one data item is modified to include a link to a received data item.

3. The method of claim 1, wherein modifying the at least one data item of the plurality of stored data items comprises replacing the at least one data item of the plurality of stored data items with at least one received data item.

4. The method of claim 1, wherein two or more resources of the at least one missing resource comprise a third data item.

5. The method of claim 1, wherein two or more resources of the plurality of determined resources comprise at least one data item from the received one or more data items.

6. The method of claim 1, wherein the link between the first data item and the second data item comprises a two way link.

7. The method of claim 1, wherein applying the resource determination rules comprises adding data items from the identified missing resources to a missing resource list;

and adding data items from the missing resource list to a resource list, the updating of the graph representation being based on the resource list after the adding of the data items from the missing resource list.

8. The method of claim 1, wherein the saved plurality of determined resources comprise an append-only database.

9. The method of claim 1, wherein the input data comprises data in an RDF format.

10. The method of claim 1, wherein the save plurality of determined resources comprise a plurality of data item trees, each data item tree having a root data item.

11. A method for retrieving data in a distributed storage environment, the method comprising:

receiving a request for a data item;

identifying a data item tree corresponding to the received request, the data item tree comprising a plurality of data items stored according to a linked data model, the data items in the identified data item tree being linked together so that each data item in the identified data item tree can be accessed from any other data item in the identified data item tree by traversing links between data items;

traversing the identified data item tree by following one or more links between a root data item and at least one data item matching the received request;

providing, responsive to the received request, the matched at least one data item.

12. The method of claim 11, further comprising:

caching the matched at least one data item;

receiving a second request, the cached at least one data item matching the received second request; and

providing, responsive to the received second request, the cached at least one data item.

13. The method of claim 11, wherein each of the plurality of stored data items further comprises a distinct address.

14. The method of claim 11, wherein providing the matched at least one data item comprises extracting data from the matched at least one data item and providing the extracted data.

15. A system for storing and retrieving data in a distributed storage environment, the system comprising:

durable storage comprising a plurality of physical storage devices;

one or more processors having associated memory, the associated memory including computer-executable instructions executed by the one or more processors to provide;

a plurality of resource determination rules;

a plurality of resource creation rules;

a Linked Data Processor for reading stored data items into memory based on the plurality of resource determination rules and for storing data items to the durable storage based on the plurality of resource creation rules; and

a plurality of data item trees comprising data items linked by two-way links, each data item tree comprising a root data item and one or more data items linked to at least one other data item, each data item comprising a data item address.

16. The system of claim 15, wherein at least two data item trees comprise a first data item.

17. The system of claim 15, the system further comprising a graph store component.

18. The system of claim 15, further comprising resource list, a deduced resource list, and a missing resource list.

19. The system of claim 15, further comprising a content delivery network for caching data items from the durable storage and for matching requests for data items with cached data items, data items from durable storage, or a combination thereof.

20. The system of claim 15, wherein the data item trees comprise an append-only database.