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

Posted on by lukaseder
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) {
    tables.addAll(table.referencedTables);
    tables.addAll(table.referencingTables);
  }
}
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()) {
          result.add(fk.getKey().getTable());
        }

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

    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!

Published by lukaseder

I made jOOQ

Leave a Reply