A computer-implemented method is provided for constructing a minimum superset of data that complies with referential completeness as well as other specified data relationships. Given extraction criteria for the data, an iterative process analyzes the database for records to be included in the minimal superset. The iterative process includes: selecting a given table from a listing of tables implicated by the extraction criteria; identifying tables in the relational database having either a parent or a child relationship with the given table; evaluating concurrently and asynchronously each of the identified tables; and repeating these steps for each of the tables in the listing of tables.