Graph-based techniques for detecting and storing data set dependencies
The disclosure describes a method for optimizing data flow graphs to represent relationships between data sets. In an example implementation, a processor receives an initial graph showing direct links between data sets and elements. The processor then expands this graph by replacing direct source-target links with new paths going through intermediate elements. Next, the processor simplifies the expanded graph by removing intermediary nodes and edges, replacing them with direct source-target links. If the graph shows an indirect path between two data sets through intermediate nodes, the path will be consolidated into a single direct link. Additionally, the optimized graph is persisted in a database and made accessible through queries. Overall, this improves lineage graph efficiency, allowing easier traversal and analysis, while also enabling incremental updates as data flows change.
1 . A method comprising:
receiving, by a processor, a first data flow graph that represents:
a first direct relationship between a first data set and a first data element of the first data set, and
a second direct relationship between the first data element and a second data set;
generating, by the processor, a second data flow graph by modifying the first data flow graph to replace the second direct relationship with:
a third direct relationship between the first data element and a second data element of the second data set that is determined based on the first data element, and
a fourth direct relationship between the second data element and the second data set;
determining, by the processor and based on determining that a set of intermediate direct relationships connect the first data set to the second data set, that the second data flow graph represents a first indirect relationship between the first data set and the second data set;
determining, by the processor and based on the second data flow graph, that the set of intermediate direct relationships comprises the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph;
generating, by the processor, and in response to determining that the second data flow graph represents the first indirect relationship between the first data set and the second data set, a third data flow graph by modifying the second data flow graph to replace the first direct relationship, the third direct relationship, and the fourth direct relationship with a fifth direct relationship between the first data set and the second data set, wherein generating the third data flow graph comprises:
removing, based on determining that the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph are in the set of intermediate direct relationships connecting the first data set to the second data set, the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph; and
storing, by the processor, the third data flow graph in a database, wherein the third data flow graph is accessible in the database via a database query.
2 . The method of claim 1 , further comprising:
determining, by the processor, that the first data flow graph represents a sixth direct relationship between a third data element of the first data set and a seventh direct relationship between the first data element and the second data set;
generating, by the processor, the second data flow graph by replacing the seventh direct relationship with: (i) an eighth direct relationship between the third data element and a fourth data element of the second data set that is determined based on the third data element, and (ii) a ninth direct relationship between the fourth data element and the second data set; and
determining, by the processor, the third data flow graph by removing the sixth direct relationship, the eighth direct relationship, and the ninth direct relationship.
3 . The method of claim 1 , wherein the database is a relational database.
4 . The method of claim 1 , wherein the first indirect relationship represents a shortest path between a first node of the second data flow graph that corresponds to the first data set and a second node of the second data flow graph that corresponds to the second data set.
5 . The method of claim 4 , wherein determining the shortest path comprises processing the second data flow graph using a dynamic programming routine.
6 . The method of claim 5 , wherein the dynamic programming routine uses a Floyd-Warshall traversal of the second data flow graph.
7 . The method of claim 1 , further comprising determining the first data flow graph, wherein determining the first data flow graph comprises:
monitoring a data processing application that transforms data between a plurality of data sets comprising the first data set and the second data set;
extracting metadata from the data processing application, wherein the metadata comprises information about source data sets, target data sets, data transformations, and relationships between data elements; and
generating the first data flow graph based on the metadata.
8 . The method of claim 7 , wherein the data processing application is an extract-transform-load application.
9 . The method of claim 7 , wherein the data processing application is executed by a database management system.
10 . The method of claim 1 , wherein determining the first indirect relationship comprises performing a breadth-first search traversal on the second data flow graph.
11 . The method of claim 1 , further comprising:
determining, by the processor, that the second data flow graph comprises a third data element that lacks an outgoing direct relationship and a fourth data element that lacks an incoming direct relationship;
determining, by the processor, that the fourth data element is determined based on the third data element, wherein determining that the fourth data element is determined based on the third data element is based on at least one of: (i) a first data type of the third data element and a second data type of the fourth data element, or (ii) a first extract, transform, and load (ETL) routine used to extract the third data element and a second ETL routine used to extract the fourth data element; and
generating, by the processor and based on determining the fourth data element is determined based on the third data element, a sixth direct relationship in the second data flow graph from the third data element to the fourth data element.
12 . The method of claim 1 , further comprising:
determining, by the processor, that the first data flow graph comprises a third data element that lacks an outgoing direct relationship and a fourth data element that lacks an incoming direct relationship;
determining, by the processor, that the fourth data element is determined based on the third data element, wherein determining that the fourth data element is determined based on the third data element is based on at least one of: (i) a first data type of the third data element and a second data type of the fourth data element, or (ii) a first extract, transform, and load (ETL) routine used to extract the third data element and a second ETL routine used to extract the fourth data element; and
generating, by the processor and based on determining the fourth data element is determined based on the third data element, a sixth direct relationship in the first data flow graph from the third data element to the fourth data element.
13 . The method of claim 1 , further comprising:
determining, by the processor, that the third data flow graph comprises a third data element that lacks an outgoing direct relationship and a fourth data element that lacks an incoming direct relationship;
determining, by the processor, that the fourth data element is determined based on the third data element, wherein determining that the fourth data element is determined based on the third data element is based on at least one of: (i) a first data type of the third data element and a second data type of the fourth data element, or (ii) a first extract, transform, and load (ETL) routine used to extract the third data element and a second ETL routine used to extract the fourth data element; and
generating, by the processor and based on determining the fourth data element is determined based on the third data element, a sixth direct relationship in the third data flow graph from the third data element to the fourth data element.
14 . The method of claim 1 , wherein:
the third direct relationship represents an extract, transform, and load (ETL) process; and
the fourth direct relationship represents that the first data element belongs to the second data set.
15 . A computing system comprising a processor and memory storing computer-executable instructions that, when executed by the processor, cause the computing system to perform operations comprising:
receiving, by the processor, a first data flow graph that represents:
a first direct relationship between a first data set and a first data element of the first data set, and
a second direct relationship between the first data element and a second data set;
generating, by the processor, a second data flow graph by modifying the first data flow graph to replace the second direct relationship with:
a third direct relationship between the first data element and a second data element of the second data set that is determined based on the first data element, and
a fourth direct relationship between the second data element and the second data set;
determining, by the processor and based on determining that a set of intermediate direct relationships connect the first data set to the second data set, that the second data flow graph represents a first indirect relationship between the first data set and the second data set;
determining, by the processor and based on the second data flow graph, that the set of intermediate direct relationships comprises the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph;
generating, by the processor, and in response to determining that the second data flow graph represents the first indirect relationship between the first data set and the second data set, a third data flow graph by modifying the second data flow graph to replace the first direct relationship, the third direct relationship, and the fourth direct relationship with a fifth direct relationship between the first data set and the second data set, wherein generating the third data flow graph comprises:
removing, based on determining that the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph are in the set of intermediate direct relationships connecting the first data set to the second data set, the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph; and
storing, by the processor, the third data flow graph in a database, wherein the third data flow graph is accessible in the database via a database query.
16 . The computing system of claim 15 , the operations further comprising:
determining, by the processor, that the first data flow graph represents a sixth direct relationship between a third data element of the first data set and a seventh direct relationship between the first data element and the second data set;
generating, by the processor, the second data flow graph by replacing the seventh direct relationship with: (i) an eighth direct relationship between the third data element and a fourth data element of the second data set that is determined based on the third data element, and (ii) a ninth direct relationship between the fourth data element and the second data set; and
determining, by the processor, the third data flow graph by removing the sixth direct relationship, the eighth direct relationship, and the ninth direct relationship.
17 . The computing system of claim 15 , wherein the first indirect relationship represents a shortest path between a first node of the second data flow graph that corresponds to the first data set and a second node of the second data flow graph that corresponds to the second data set.
18 . The computing system of claim 15 , the operations further comprising determining the first data flow graph, wherein determining the first data flow graph comprises:
monitoring a data processing application that transforms data between a plurality of data sets comprising the first data set and the second data set;
extracting metadata from the data processing application, wherein the metadata comprises information about source data sets, target data sets, data transformations, and relationships between data elements; and
generating the first data flow graph based on the metadata.
19 . One or more non-transitory computer-readable media storing computer-executable instructions that, when executed by a processor, cause the processor to perform operations, comprising:
receiving, by the processor, a first data flow graph that represents:
a first direct relationship between a first data set and a first data element of the first data set, and
a second direct relationship between the first data element and a second data set;
generating, by the processor, a second data flow graph by modifying the first data flow graph to replace the second direct relationship with:
a third direct relationship between the first data element and a second data element of the second data set that is determined based on the first data element, and
a fourth direct relationship between the second data element and the second data set;
determining, by the processor and based on determining that a set of intermediate direct relationships connect the first data set to the second data set, that the second data flow graph represents a first indirect relationship between the first data set and the second data set;
determining, by the processor and based on the second data flow graph, that the set of intermediate direct relationships comprises the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph;
generating, by the processor, and in response to determining that the second data flow graph represents the first indirect relationship between the first data set and the second data set, a third data flow graph by modifying the second data flow graph to replace the first direct relationship, the third direct relationship, and the fourth direct relationship with a fifth direct relationship between the first data set and the second data set, wherein generating the third data flow graph comprises:
removing, based on determining that the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph are in the set of intermediate direct relationships connecting the first data set to the second data set, the first direct relationship, the third direct relationship, and the fourth direct relationship from the second data flow graph; and
storing, by the processor, the third data flow graph in a database, wherein the third data flow graph is accessible in the database via a database query.
20 . The one or more non-transitory computer-readable media of claim 19 , the operations further comprising:
determining, by the processor, that the first data flow graph represents a sixth direct relationship between a third data element of the first data set and a seventh direct relationship between the first data element and the second data set;
determining, by the processor, the second data flow graph by replacing the seventh direct relationship with: (i) an eighth direct relationship between the third data element and a fourth data element of the second data set that is determined based on the third data element, and (ii) a ninth direct relationship between the fourth data element and the second data set; and
determining, by the processor, the third data flow graph by removing the sixth direct relationship, the eighth direct relationship, and the ninth direct relationship.