Storing graph data representing workflow management

• US 9,189,509 B1
• Filed: 09/21/2012
• Issued: 11/17/2015
• Est. Priority Date: 09/21/2012
• Status: Active Grant

• Current Assignee: Comindware Limited
• Original Assignee: Comindware Limited
• Inventors: Tsypliaev, Maxim V., Volynskiy, Peter E.
• Primary Examiner(s): Young, Kevin L
• Application Number:
  US13/624,078
• Time in Patent Office: 1,152 Days
• US Class Current: 1/1
• 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 graph data representing a workflow of a business process, the method comprising:

generating the workflow of the business process;

generating a graph having a plurality of nodes and connecting edges, wherein contents of the workflow is stored in the form of graphs;

generating a graph data having a predicate and arguments corresponding to the nodes;

implementing a B-tree as a set of tables including a predicate table and arguments tables;

storing the predicate in the predicate table of the B-tree;

storing the arguments in arguments tables of the B-tree;

storing relations between the arguments in a relations table of the B-tree;

generating a link to the relations table of the B-tree;

generating links to the arguments table of the B-tree;

storing the link to the relations table of the B-tree and the links to the arguments tables of the B-tree in the predicate table of the B-tree so as to indicate a connection between the relations B-tree and the arguments B-trees,

wherein relations between the predicate and the arguments are determined by the edges of the graph;

determining, in response to a request for a graph item from a requestor, a set of arguments and a relation connected by the predicate table of the B-tree; and

returning the graph item to the requestor.

2. The method of claim 1, wherein the graph data is represented by any of:

a triple;

a quadruple; and

a quintuple.

3. The method of claim 1, wherein the predicate has an arbitrary number of corresponding arguments.

4. The method of claim 1, further comprising assigning a unique identifier to the predicate and corresponding arguments.

5. The method of claim 4, further comprising sorting the predicates in the predicate table of the B-tree based on the identifier.

6. The method of claim 1, further comprising generating a terminator value and storing it in a terminator table of the B-tree.

7. The method of claim 6, wherein the terminator value indicates an end of the arguments corresponding to the predicate.

8. The method of claim 1, wherein the relations tables of the B-tree referenced by the links stored in the predicate table of the B-tree contain links to other tables of the B-tree containing arguments and terminators.

9. The method of claim 1, wherein the predicates are hashed prior to storing in the predicate table of the B-tree.

10. The method of claim 9, wherein the predicates are sorted by sorting corresponding hash values.

11. The method of claim 1, wherein the arguments are hashed prior to storing in the argument tables of the B-tree.

12. The method of claim 11, wherein the arguments are sorted by sorting corresponding hash values.

13. The method of claim 1, wherein the search for predicates in the predicate table of the B-tree includes identifying intersections of attributes of identifiers of the predicates.

14. The method of claim 13, wherein the identifiers are sorted based on order of writing of sets of identifiers into the predicate table of the B-tree.

15. The method of claim 1, wherein the B-tree is a binary search trees that has a plurality of nodes.

16. The method of claim 1, wherein the arguments are subjects and objects.

17. A system for storing graph data representing data representing a workflow of a business process, 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.