Method, apparatus, and computer-readable medium to extract a referentially intact subset from a database

An apparatus for extracting a referentially intact subset of data from a database while minimizing a quantity of parent-to-child join operations required to extract the referentially intact subset, the apparatus comprising:

• one or more processors;
• and
• one or more memories operatively coupled to at least one of the one or more processors and having instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:
• receive a request comprising at least one criterion indicating a criterion table in a plurality of tables of the database, wherein a schema of the database corresponds to an entity graph, the entity graph comprising a plurality of entities corresponding to the plurality of tables and a plurality of directed edges connecting the plurality of entities, each directed edge indicating a child-to-parent relationship between a child table in the plurality of tables and a parent table in the plurality of tables, such that each child table comprises a foreign key that references a primary key of a corresponding parent table;
• determine one or more directed edges in the plurality of directed edges that must be traversed in both directions in order to traverse all entities in the entity graph starting from a criterion entity corresponding to the criterion table by constructing a minimum spanning arborescence rooted at the criterion entity and encoding a differential weighting to parent-to-child directed edges than to child-to-parent directed edges;
• and
• generate the referentially intact subset of data from the plurality of tables based at least in part on a topological ordering of the entity graph and the one or more directed edges that must be traversed in both directions by executing a plurality join operations on the database, the plurality join operations comprising:
• an initial join operation corresponding to one or more records in the criterion table that fulfill the least one criterion, a plurality of child-to-parent join operations corresponding to the plurality of directed edges, and one or more parent-to-child join operations corresponding to the one or more directed edges that must be traversed in both directions.

At least one non-transitory computer-readable medium storing computer-readable instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

• receive a request comprising at least one criterion indicating a criterion table in a plurality of tables of the database, wherein a schema of the database corresponds to an entity graph, the entity graph comprising a plurality of entities corresponding to the plurality of tables and a plurality of directed edges connecting the plurality of entities, each directed edge indicating a child-to-parent relationship between a child table in the plurality of tables and a parent table in the plurality of tables, such that each child table comprises a foreign key that references a primary key of a corresponding parent table;
• determine one or more directed edges in the plurality of directed edges that must be traversed in both directions in order to traverse all entities in the entity graph starting from a criterion entity corresponding to the criterion table by constructing a minimum spanning arborescence rooted at the criterion entity and encoding a differential weighting to parent-to-child directed edges than to child-to-parent directed edges;
• and
• generate the referentially intact subset of data from the plurality of tables based at least in part on a topological ordering of the entity graph and the one or more directed edges that must be traversed in both directions by executing a plurality join operations on the database, the plurality join operations comprising:
• an initial join operation corresponding to one or more records in the criterion table that fulfill the least one criterion, a plurality of child-to-parent join operations corresponding to the plurality of directed edges, and one or more parent-to-child join operations corresponding to the one or more directed edges that must be traversed in both directions.