Granted Patent B2

US 12,405,949 · App. 18/345,706 · Granted Sep 2, 2025

Inventors: David Clemens (Cambridge, MA); Dusan Radivojevic (North Andover, MA); Neil Galarneau (West Roxbury, MA)

Assignee: Ab Initio Technology LLC

G06F16/245G06F16/22G06F16/248G06F16/83G06F40/117

Abstract

Claims (65)

1. A method performed by a data processing system for updating data structures with lineage from a database, wherein updating provides for increased efficiency in determining lineage, including:

storing, in memory of a data processing system, a first data structure representing a first item of data or a first transform;

wherein the first data structure specifies lineage of a given item of data or a given transform, wherein the lineage specifies an item of data or a transform that affects or is affected by the given item of data or the given transform; and

updating, by a data processing system, the lineage specified by the first data structure, by:

from time to time, receiving, from a database and by a data processing system, data representing lineage of the given item of data or the given transform;

based on the received data representing the lineage, identifying, by a data processing system, a second data structure, stored in memory, representing a second item of data or a second transform that affects or is affected by the given item of data or the given transform; and

updating, by a data processing system, the first data structure stored in memory with a reference to the second data structure, stored in memory, representing the second item of data or the second transform that affects or is affected by the given data item or the given transform;

wherein the second data structure specifies lineage of the second item of data or the second transform.

2. The method of claim 1 , wherein updating the first data structure comprises updating a pointer of the first data structure to reference a memory location of the second data structure representing the second item of data or the second transform.

3. The method of claim 1 , further comprising

generating a third data structure specifying lineage of the second item of data or the second transform; and

storing, in the memory of the data processing system, the third data structure.

4. The method of claim 1 , further comprising receiving, from the database, the data representing lineage of the given item of data or the given transform at regular intervals or scheduled intervals.

5. The method of claim 1 , wherein the data representing lineage of the given item of data or the given transform is received in response to a request transmitted to the database.

6. The method of claim 1 , further comprising:

receiving a query including a request for lineage;

based on the query, accessing the first data structure and a third data structure to determine the requested lineage; and

generating a response to the query, the response including data representing the requested lineage.

7. The method of claim 6 , further comprising:

accessing a walk plan that includes instructions for determining the requested lineage; and

collecting data from the first data structure and third data structure according to the walk plan to determine the requested lineage.

8. The method of claim 1 , wherein the given item of data or the given transform is the first item of data or the first transform.

9. A system for updating data structures with lineage from a database, wherein updating provides for increased efficiency in determining lineage, the system comprising:

at least one processor; and

at least one computer-readable medium storing instructions executable by the at least one processor to perform operations comprising:

storing, in memory, a first data structure representing a first item of data or a first transform;

wherein the first data structure specifies lineage of a given item of data or a given transform, wherein the lineage specifies an item of data or a transform that affects or is affected by the given item of data or the given transform; and

updating the lineage specified by the first data structure, by:

from time to time, receiving, from a database, data representing lineage of the given item of data or the given transform;

based on the received data representing the lineage, identifying a second data structure, stored in memory, representing a second item of data or a second transform that affects or is affected by the given item of data or the given transform; and

updating the first data structure stored in memory with a reference to the second data structure, stored in memory, representing the second item of data or the second transform that affects or is affected by the given data item or the given transform;

wherein the second data structure specifies lineage of the second item of data or the second transform.

10. The system of claim 9 , wherein updating the first data structure comprises updating a pointer of the first data structure to reference a memory location of the second data structure representing the second item of data or the second transform.

11. The system of claim 9 , wherein the at least one computer readable medium stores instructions executable by the at least one processor to perform operations further comprising:

generating a third data structure specifying lineage of the second item of data or the second transform; and

storing, in the memory, the third data structure.

12. The system of claim 9 , wherein the at least one computer readable medium stores instructions executable by the at least one processor to perform operations further comprising:

receiving, from the database, the data representing lineage of the given item of data or the given transform at regular intervals or scheduled intervals.

13. The system of claim 9 , wherein the data representing lineage of the given item of data or the given transform is received in response to a request transmitted to the database.

14. The system of claim 9 , wherein the at least one computer readable medium stores instructions executable by the at least one processor to perform operations further comprising:

receiving a query including a request for lineage;

based on the query, accessing the first data structure and a third data structure to determine the requested lineage; and

generating a response to the query, the response including data representing the requested lineage.

15. The system of claim 14 , wherein the at least one computer readable medium stores instructions executable by the at least one processor to perform operations further comprising:

accessing a walk plan that includes instructions for determining the requested lineage; and

collecting data from the first data structure and the third data structure according to the walk plan to determine the requested lineage.

16. At least one non-transitory computer readable medium storing instructions executable by at least one processor to perform operations comprising:

storing, in memory, a first data structure representing a first item of data or a first transform;

wherein the first data structure specifies lineage of a given item of data or a given transform, wherein the lineage specifies an item of data or a transform that affects or is affected by the given item of data or the given transform; and

updating the lineage specified by the first data structure, by:

from time to time, receiving, from a database, data representing lineage of the given item of data or the given transform;

based on the received data representing the lineage, identifying a second data structure, stored in memory, representing a second item of data or a second transform that affects or is affected by the given item of data or the given transform; and

updating the first data structure stored in memory with a reference to the second data structure, stored in memory, representing the second item of data or the second transform that affects or is affected by the given data item or the given transform;

wherein the second data structure specifies lineage of the second item of data or the second transform.

17. The at least one non-transitory computer readable medium of claim 16 , wherein updating the first data structure comprises updating a pointer of the first data structure to reference a memory location of the second data structure representing the second item of data or the second transform.

18. The at least one non-transitory computer readable medium of claim 16 storing instructions executable by the at least one processor to perform operations further comprising:

generating a third data structure specifying lineage of the second item of data or the second transform; and

storing, in the memory, the third data structure.

19. The at least one non-transitory computer readable medium of claim 16 storing instructions executable by the at least one processor to perform operations further comprising:

receiving, from the database, the data representing lineage of the given item of data or the given transform at regular intervals or scheduled intervals.

20. The at least one non-transitory computer readable medium of claim 16 , wherein the data representing lineage of the given item of data or the given transform is received in response to a request transmitted to the database.

21. The at least one non-transitory computer readable medium of claim 16 storing instructions executable by the at least one processor to perform operations further comprising:

receiving a query including a request for lineage;

based on the query, accessing the first data structure and a third data structure to determine the requested lineage; and

generating a response to the query, the response including data representing the requested lineage.

Assignments (3)

Continuity (3)

References Cited (144)