Methods and systems for multidimensional analysis of interconnected data sets stored in a graph database

Patent metadata

Field	Value
Publication number	US-10909178-B2
Application number	US-201615062110-A
Country	US
Kind code	B2
Filing date	Mar 5, 2016
Priority date	Mar 5, 2015
Publication date	Feb 2, 2021
Grant date	Feb 2, 2021

Abstract

Multidimensional databases are well-suited for viewing data at different levels of detail. Graph databases are well-suited for modeling data sets with complex relationships. A novel platform for analysis and planning is enabled by linking multidimensional and graph databases. Graphs are data structures stored in graph databases. Graphs use nodes and edges to model data elements, some of which are derived. A graph is traversed to derive new data elements. To perform analysis on the graph data elements, graph traversal paths are stored as tuples in a fact table. This fact table is in turn loaded into the multidimensional database by mapping the fact table's attribute columns to dimensions of the multidimensional database.

First claim

We claim:

1. A method, comprising:
providing a hypercube linked to a graph, wherein the graph includes a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein the hypercube include a subset of nodes of the plurality of nodes, and wherein the providing of the hypercube comprises:
transforming the graph into a logical fact table, wherein the logical fact table includes two columns, the two columns includes a fact column and a key column, comprising:
imposing a topological ordering to the graph;
traversing, based on the topological ordering, the graph starting at one node of the plurality of nodes; and
for the one node:
determining whether the one node is to be included in the logical fact table, comprising:
determining whether the one node is a foreign key to a dimension table; and
in response to a determination that the one node is a foreign key to a dimension table, determining that the one node is to be included in the logical fact table; and
in response to a determination that the one node is to be included in the logical fact table:
adding the one node to the key column;
applying an edge measure function to an edge metric between the one node and a parent node of the one node to obtain a resulting value; and
writing the resulting value for the edge metric in the fact column of the logical fact table;
obtaining hierarchical data, comprising:
compiling nodes, edges, and measure formulae into an executable program for traversing the graph, comprising:
evaluating all upstream nodes of a given node before the given node based on the topological ordering;
evaluating all downstream nodes of the given node after the given node based on the topological ordering;
determining whether the given node is a cube-eligible node, wherein the cube-eligible node is to be imported into the hypercube; and
in response to a determination that the given node is a cube-eligible node:
preparing a tuple by linking the given node to a cube-eligible node upstream of the given node;
computing cube-eligible measure data along the tuple; and
storing the cube-eligible measure data against the tuple;
preparing an output set of tuples and corresponding cube-measures as a time vector;
combining the hierarchical data and the logical fact table to obtain an instantiation of the hypercube, comprising:
mapping a member of a dimension of the hypercube to a corresponding cube-eligible node of the graph, dimensions of the hypercube including nodes of the output set of tuples and time; and
loading a set of values from the logical fact table into cube cells of the hypercube;
providing a dependency analysis across the graph and the hypercube;
preparing a base plan that provides a set of all graph and hypercube data at a certain point in time;
receiving a scenario including a user change in the base plan;
receiving an inquiry for a measure value at a cube cell of the hypercube or at a graph node of the graph;
retrieving a base value for the measure value;
applying a sequential list of changes resulting from the user change in dependency order based on the dependency analysis after filtering the sequential list of changes to identify a subset of changes that are upstream of the measure value;
computing an incremental value for the measure value by applying the subset of changes to propagate the user change to the measure value;
combining the base value and the incremental value to find a final value for the measure value; and
returning the final value in response to the inquiry.

2. The method of claim 1 , wherein the mapping provides a many-to-one relationship between the graph nodes and a corresponding hypercube member.

3. The method of claim 1 , further comprising:
receiving a plurality of scenarios each including a user change of a plurality of user changes; and
finding a plurality of final values for the measure value, each final value of the plurality of final values resulting from a scenario of the plurality of scenarios.

4. The method of claim 1 , wherein the scenario is private to a user.

5. The method of claim 1 , wherein the scenario is shared among a plurality of users.

6. The method of claim 1 , wherein the scenario is branched from the base plan.

7. The method of claim 1 , wherein the scenario is branched from a previous scenario.

8. The method of claim 1 , wherein the scenario is based on a plurality of user changes stored in order of entry.

9. A computer program product being embodied in a tangible non-transitory computer readable storage medium and comprising computer instructions for:
providing a hypercube linked to a graph, wherein the graph includes a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein the hypercube include a subset of nodes of the plurality of nodes, and wherein the providing of the hypercube comprises:
transforming the graph into a logical fact table, wherein the logical fact table includes two columns, the two columns includes a fact column and a key column, comprising:
imposing a topological ordering to the graph;
traversing, based on the topological ordering, the graph starting at one node of the plurality of nodes; and
for the one node:
determining whether the one node is to be included in the logical fact table, comprising:
determining whether the one node is a foreign key to a dimension table; and
in response to a determination that the one node is a foreign key to a dimension table, determining that the one node is to be included in the logical fact table; and
in response to a determination that the one node is to be included in the logical fact table:
adding the one node to the key column;
applying an edge measure function to an edge metric between the one node and a parent node of the one node to obtain a resulting value; and
writing the resulting value for the edge metric in the fact column of the logical fact table;
obtaining hierarchical data, comprising:
compiling nodes, edges, and measure formulae into an executable program for traversing the graph, comprising:
evaluating all upstream nodes of a given node before the given node based on the topological ordering;
evaluating all downstream nodes of the given node after the given node based on the topological ordering;
determining whether the given node is a cube-eligible node, wherein the cube-eligible node is to be imported into the hypercube; and
in response to a determination that the given node is a cube-eligible node:
preparing a tuple by linking the given node to a cube-eligible node upstream of the given node;
computing cube-eligible measure data along the tuple; and
storing the cube-eligible measure data against the tuple;
preparing an output set of tuples and corresponding cube-measures as a time vector;
combining the hierarchical data and the logical fact table to obtain an instantiation of the hypercube, comprising:
mapping a member of a dimension of the hypercube to a corresponding cube-eligible node of the graph, dimensions of the hypercube including nodes of the output set of tuples and time; and
loading a set of values from the logical fact table into cube cells of the hypercube;
providing a dependency analysis across the graph and the hypercube;
preparing a base plan that provides a set of all graph and hypercube data at a certain point in time based on a scenario that contains user changes;
receiving a scenario including a user change in the base plan;
receiving an inquiry for a measure value at a cube cell of the hypercube or at a graph node of the graph;
retrieving a base value for the measure value;
applying a sequential list of changes resulting from the user change in dependency order based on th

Assignees

• Workday Inc

Inventors

• Shore Matthew
• Botee Huned
• Kuo Joe
• Balasubramhanya Suresh

Classifications

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title