Starting from seed rows in one table, find all related rows across all tables needed for referential integrity. Walk the FK graph in both directions:
Forward (parent→child): seed is parent, find children that reference it.
Backward (child→parent): seed is child, find parents it references.
Track visited to avoid loops. This is the core of Synthesized.io's subsetting feature — extracting a self-consistent slice of production data for dev/staging.
Setup (folded above the editor — click + to view): data class FK(child, childCol, parent, parentCol); an in-memory fakeDb standing in for a real database; fetchRelated(table, returnCol, filterCol, filterIds): Set<Long> as your only data accessor; a pre-built schema: List<FK> for the test scenario.
data class FK(val child: String, val childCol: String, val parent: String, val parentCol: String)
val fakeDb = mapOf(
"departments" to listOf(mapOf("id" to 1L), mapOf("id" to 2L)),
"users" to listOf(
mapOf("id" to 1L, "dept_id" to 1L), mapOf("id" to 2L, "dept_id" to 1L),
mapOf("id" to 3L, "dept_id" to 2L)
),
"orders" to listOf(
mapOf("id" to 10L, "user_id" to 1L), mapOf("id" to 11L, "user_id" to 1L),
mapOf("id" to 12L, "user_id" to 2L), mapOf("id" to 13L, "user_id" to 3L)
),
"products" to listOf(mapOf("id" to 100L), mapOf("id" to 101L), mapOf("id" to 102L)),
"order_items" to listOf(
mapOf("id" to 1000L, "order_id" to 10L, "product_id" to 100L),
mapOf("id" to 1001L, "order_id" to 10L, "product_id" to 101L),
mapOf("id" to 1002L, "order_id" to 12L, "product_id" to 100L),
mapOf("id" to 1003L, "order_id" to 13L, "product_id" to 102L)
)
)
fun fetchRelated(table: String, returnCol: String, filterCol: String, filterIds: Set<Long>): Set<Long> {
return fakeDb[table]?.filter { row -> (row[filterCol] as? Long) in filterIds }
?.mapNotNull { row -> row[returnCol] as? Long }?.toSet() ?: emptySet()
}
val schema = listOf(
FK("users", "dept_id", "departments", "id"),
FK("orders", "user_id", "users", "id"),
FK("order_items", "order_id", "orders", "id"),
FK("order_items", "product_id", "products", "id")
)
//sampleStart
fun collectSubset(
seedTable: String,
seedIds: Set<Long>,
fks: List<FK>
): Map<String, Set<Long>> {
// BFS through FK graph starting from seed.
// Follow FKs BOTH directions:
// Forward (parent→child): seed is parent, find children
// Backward (child→parent): seed is child, find parents
// Track visited to avoid infinite loops.
// Return: map of table → collected IDs
TODO()
}
//sampleEnd
fun main() {
// Test 1: Seed users {1, 2} — find everything related
val result = collectSubset("users", setOf(1L, 2L), schema)
check(result["users"] == setOf(1L, 2L)) { "FAIL: seed users" }
println("✅ Users: ${result["users"]}")
check(result["orders"]?.containsAll(setOf(10L, 11L, 12L)) == true) { "FAIL: orders for users 1,2" }
check(result["orders"]?.contains(13L) != true) { "FAIL: order 13 is for user 3, not included" }
println("✅ Orders: ${result["orders"]}")
check(result["departments"]?.contains(1L) == true) { "FAIL: department 1 referenced by users" }
println("✅ Departments: ${result["departments"]}")
check(result["order_items"]?.containsAll(setOf(1000L, 1001L, 1002L)) == true) { "FAIL: order_items" }
println("✅ Order items: ${result["order_items"]}")
check(result["products"]?.containsAll(setOf(100L, 101L)) == true) { "FAIL: products" }
println("✅ Products: ${result["products"]}")
// Test 2: Seed with no FKs — just returns seed
val r2 = collectSubset("products", setOf(100L), emptyList())
check(r2["products"] == setOf(100L)) { "FAIL: isolated seed" }
check(r2.size == 1) { "FAIL: no other tables" }
println("✅ Isolated seed: only products")
println("\n🎉 ALL TESTS PASSED!")
}
Solution
fun collectSubset(
seedTable: String,
seedIds: Set<Long>,
fks: List<FK>
): Map<String, Set<Long>> {
val collected = mutableMapOf<String, MutableSet<Long>>()
collected[seedTable] = seedIds.toMutableSet()
val queue = ArrayDeque<Pair<String, Set<Long>>>()
queue.add(seedTable to seedIds)
while (queue.isNotEmpty()) {
val (table, ids) = queue.removeFirst()
if (ids.isEmpty()) continue
for (fk in fks) {
if (fk.parent == table) {
// Forward: children referencing these parent ids
val childIds = fetchRelated(fk.child, "id", fk.childCol, ids)
val seen = collected.getOrPut(fk.child) { mutableSetOf() }
val delta = childIds - seen
if (delta.isNotEmpty()) {
seen.addAll(delta)
queue.add(fk.child to delta)
}
}
if (fk.child == table) {
// Backward: parent ids referenced by these child rows
val parentIds = fetchRelated(fk.child, fk.childCol, "id", ids)
val seen = collected.getOrPut(fk.parent) { mutableSetOf() }
val delta = parentIds - seen
if (delta.isNotEmpty()) {
seen.addAll(delta)
queue.add(fk.parent to delta)
}
}
}
}
return collected
}