1. A method of generating test data for a database, comprising: receiving, by a processor, a request to fabricate, for a database comprising multiple tables, a respective target number of data records for each of the tables; receiving one or more intra-database rules for the multiple tables; identifying one or more referential integrity constraints for the multiple tables; and fabricating, in response to the request, the respective target number of data records for each of the multiple tables, the fabricated data records complying with the one or more referential integrity constraints and the one or more intra-database rules, wherein fabricating the data records comprises repeatedly performing: determining a current count of data records in each of the tables, calculating, for each of the data tables, a completeness factor based on their respective current and target counts, and upon the completeness factor of at least one of the tables indicating the multiple data tables not comprising their respective target number of data records: selecting a given data table having the lowest completion factor, identifying parent tables from the multiple tables, that are connected in a path of foreign key to primary key paths to the selected given data table; tagging the given data table with a first tag value; tagging each of the identified parent tables with either the first tag value or a second tag value, responsive to a relation between the completeness factors of the parent tables and of corresponding child tables; creating a constraint satisfaction problem for the tagged tables; solving the constraint satisfaction problem in a manner which generates a new record for the tables tagged with the first tag value and uses existing records of tables tagged with the second tag value; and writing the generated new records into the corresponding tables.