## Serious SQL: A “convex hull” of “correlated tables”

Now THIS is an interesting, and challenging question on the jOOQ user group: https://groups.google.com/d/topic/jooq-user/6TBBLYt9eR8/discussion Say you have a big database with lots of tables and foreign key references. Now you would like to know all tables that are somehow inter-connected by their respective foreign key relationship “paths”. You could call this a “convex hull” around all of your “correlated tables”. Here’s a pseudo-algorithm to achieve this:
```
// Initialise the hull with an "origin" table
Set tables = {"any table"};
int size = 0;

// Grow the "tables" result until no new tables are added
while (size < tables.size) {
size = tables.size;

for (table in tables) {
}
}

```
At the end of this algorithm, you would have all tables in the “tables” set, that are somehow connected with the original “any table”.

### Calculate this with jOOQ

With jOOQ’s generated classes, you can easily implement the above algorithm in Java. This would be an example implementation
```
public class Hull {
public static Set<Table<?>> hull(Table<?>... tables) {
Set<Table<?>> result =
new HashSet<Table<?>>(Arrays.asList(tables));

// Loop as long as there are no new result tables
int size = 0;
while (result.size() > size) {
size = result.size();

for (Table<?> table : new ArrayList<Table<?>>(result)) {

// Follow all outbound foreign keys
for (ForeignKey<?, ?> fk : table.getReferences()) {
}

// Follow all inbound foreign keys from tables
// within the same schema
for (Table<?> other : table.getSchema().getTables()) {
if (other.getReferencesTo(table).size() > 0) {
}
}
}
}

return result;
}

public static void main(String[] args) {
// Calculate the "convex hull" for the T_AUTHOR table
System.out.println(hull(T_AUTHOR));
}
}

```

### Do it with SQL

Now this still looks straightforward. But we’re SQL pro’s and we love weird queries, so let’s give Oracle SQL a shot at resolving this problem in a single SQL statement. Here goes (warning, some serious SQL ahead)!
```
-- "graph" denotes an undirected foreign key reference graph
-- for schema "TEST"
with graph as (
select c1.table_name t1, c2.table_name t2
from all_constraints c1
join all_constraints c2
on c1.owner = c2.r_owner
and c1.constraint_name = c2.r_constraint_name
where c1.owner = 'TEST'
union all
select c2.table_name t1, c1.table_name t2
from all_constraints c1
join all_constraints c2
on c1.owner = c2.r_owner
and c1.constraint_name = c2.r_constraint_name
where c1.owner = 'TEST'
),
-- "paths" are all directed paths within that schema
-- as a #-delimited string
paths as (
select sys_connect_by_path(t1, '#') || '#' path
from graph
connect by nocycle prior t1 = t2
),
-- "subgraph" are all those directed paths that go trough
-- a given table T_AUTHOR
subgraph as (
select distinct t.table_name,
regexp_replace(p.path, '^#(.*)#\$', '\1') path
from paths p
cross join all_tables t
where t.owner = 'TEST'
and p.path like '%#' || t.table_name || '#%'
),
-- This XML-trick splits paths and generates rows for every distinct
-- table name
split_paths as (
select distinct table_name origin,
cast(t.column_value.extract('//text()') as varchar2(4000)) table_names
from
subgraph,
table(xmlsequence(xmltype(
'<x><x>' || replace(path, '#', '</x><x>') ||
'</x></x>').extract('//x/*'))) t
),
-- "table_graphs" lists every table and its associated graph
table_graphs as (
select
origin,
count(*) graph_size,
listagg(table_names, ', ') within group (order by 1) table_names
from split_paths
group by origin
)
select
origin,
graph_size "SIZE",
dense_rank() over (order by table_names) id,
table_names
from table_graphs
order by origin

```
When run against the jOOQ integration test database, this beautiful query will return:
```+----------------------+------+----+-----------------------------------------+
| ORIGIN               | SIZE | ID | TABLE_NAMES                             |
+----------------------+------+----+-----------------------------------------+
| T_658_11             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_12             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_21             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_22             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_31             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_32             |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_658_REF            |    7 |  3 | T_658_11, T_658_12, T_658_21, T_658_22, |
|                      |      |    | T_658_31, T_658_32, T_658_REF           |
| T_AUTHOR             |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| T_BOOK               |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| T_BOOK_DETAILS       |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| T_BOOK_STORE         |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| T_BOOK_TO_BOOK_STORE |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| T_DIRECTORY          |    1 |  2 | T_DIRECTORY                             |
| T_LANGUAGE           |    7 |  1 | T_AUTHOR, T_BOOK, T_BOOK_DETAILS,       |
|                      |      |    | T_BOOK_SALE, T_BOOK_STORE,              |
|                      |      |    | T_BOOK_TO_BOOK_STORE, T_LANGUAGE        |
| X_TEST_CASE_64_69    |    4 |  4 | X_TEST_CASE_64_69, X_TEST_CASE_71,      |
|                      |      |    | X_TEST_CASE_85, X_UNUSED                |
| X_TEST_CASE_71       |    4 |  4 | X_TEST_CASE_64_69, X_TEST_CASE_71,      |
|                      |      |    | X_TEST_CASE_85, X_UNUSED                |
| X_TEST_CASE_85       |    4 |  4 | X_TEST_CASE_64_69, X_TEST_CASE_71,      |
|                      |      |    | X_TEST_CASE_85, X_UNUSED                |
| X_UNUSED             |    4 |  4 | X_TEST_CASE_64_69, X_TEST_CASE_71,      |
|                      |      |    | X_TEST_CASE_85, X_UNUSED                |
+----------------------+------+----+-----------------------------------------+```

### Can you beat this? :-)

I challenge you to write a shorter query and to achieve the same result! Here’s the integration test database: https://github.com/jOOQ/jOOQ/blob/master/jOOQ-test/src/org/jooq/test/oracle/create.sql Note that the above query is horribly inefficient. There’s a lot of potential in beating that, too!