Storing graph data representing workflow management

• US 10,437,804 B1
• Filed: 11/17/2015
• Issued: 10/08/2019
• Est. Priority Date: 09/21/2012
• Status: Active Grant

• Current Assignee: Comindware Limited
• Original Assignee: Comindware Limited
• Inventors: Tsypliaev, Maxim V., Volynskiy, Peter A.
• Primary Examiner(s): Kerzhner, Aleksandr
• Assistant Examiner(s): Cheung, Eddy
• Application Number:
  US14/943,088
• Time in Patent Office: 1,421 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method and system for storing complex graph data. The graph data is represented by triples, quadruples, quintuples, etc. In order to speed up storage and retrieval of graph data, the data is stored in a form of triples, quadruples, quintuples, etc. in a B-tree. The B-trees are data structures that allow operations on dynamic data sets. The operations can be search, search for minimum and maximum values, insert, delete, reference to parent or child directory. The tree can be used as a dictionary or as a prioritized chain. The speed of tree operations is proportional to the height. The data is read as blocks from the same location. If a tree node is moved to an operational memory, an allocated memory block is moved and the operation executes very fast.

Claims

1. A computer-implemented method for storing and displaying application data, the method comprising:

generating graphs that represent the application data, the graphs having a plurality of nodes that correspond to arguments of triples and connecting edges that represent predicates of the triples, wherein the triples describe business entities and processes operating with the business entities using subjects-predicates-objects, and represent the predicates and the arguments associated with the predicates, and

wherein the predicates express relationships or connections between the arguments, which are the subjects and the objects of the triples, with the subjects representing an identifier of the business entities, and the objects are values of properties of the business entities;

storing the predicates in a predicate key-value store;

storing the arguments in argument key-value stores; and

storing links to the argument key-value stores in the predicate key-value store for corresponding predicates stored in the predicate key-value store;

determining, in response to a request for the graph data from a requestor, a set of arguments stored in the argument key-value store, wherein the arguments are linked to the predicates via the predicate key-value store and the links stored therein, wherein the request is used to derive the arguments, and

wherein the request is also represented as a triple prior to submitting the request to the predicate key-value store; and

returning the graph data to the requestor and displaying the graph data to the requestor.

2. The method of claim 1, wherein values in the predicate key-value store are represented by a pair of links to argument key-value stores.

3. The method of claim 1, wherein the at least one key-value store is at least one B-tree.

4. The method of claim 1, wherein at least one of the key-value stores is representable by at least one table.

5. The method of claim 1, wherein the Subjects are stored in the key-value stores as keys, and the Objects are stored as values.

6. The method of claim 1, wherein the Objects are stored in the key-values stores as keys, and the Subjects are stored as values.

7. The method of claim 1, wherein at least some arguments are stored in key stores, and wherein the key-value stores store links to the key stores.

8. The method of claim 1, wherein the data in the key-values stores are sorted by keys.

9. A system for storing graph data, the system comprising:

a processor;

a memory connected to the processor;

a computer program logic stored in the memory and executed on the processor for implementing the steps of claim 1.

10. The method of claim 1, wherein the processes are business processes represented by a workflow, such that contents of the workflow is stored as the graphs.

11. A computer-implemented method for storing and displaying application data, the method comprising:

generating graphs that represent the application data, the graphs having a plurality of nodes that correspond to arguments of triples and connecting edges that represent predicates of the triples, wherein the triples describe business entities and processes operating with the business entities using subjects-predicates-objects, and represent the predicates and the arguments associated with the predicates, and

wherein the predicates express relationships or connections between the arguments, which are the subjects and the objects of the triples, with the subjects representing an identifier of the business entities, and the objects are values of properties of the business entities;

storing the predicates in a predicate key-value store;

storing arguments in argument key-value stores;

storing assigned unique identifiers to statements to the argument key-value stores;

storing links to the argument key-value stores in the predicate key-value store for corresponding predicates stored in the predicate key-value store;

determining, in response to a request for the graph data from a requestor, a set of arguments stored in the argument key-value store, wherein the arguments are linked to the predicates via the predicate key-value store and the links stored therein, wherein the request is used to derive the arguments, and

wherein the request is also represented as a triple prior to submitting the request to the predicate key-value store; and

returning the graph data for display to the requestor.

12. The method of claim 11, wherein the at least one key-value store is at least one B-tree.

13. The method of claim 11, wherein at least one of the key-value stores is representable by at least one table.

14. The method of claim 11, wherein the statements are any of:

triples;

triplets;

quadruples;

quintuples;

and n-tuples.

15. The method of claim 11, further comprising storing at least one terminator in at least one argument key-value store.

16. The method of claim 11, wherein the unique identifiers are stored in separate key stores, and wherein the key-value stores store links to the key stores.

17. The method of claim 11, wherein the data in the key stores and the key-values stores are sorted by keys.

18. The method of claim 11, wherein a search for predicates in the predicate key-value store includes identifying intersections of arguments based on the unique identifiers.