create table relations (  
  p1 varchar2(1), p2 varchar2(1), 
  primary key ( p1, p2 ), 
  check ( p2 > p1 ) 
)

Table to store pre-computed subgraphs

create table complete_subgraphs  ( 
  subgraph        varchar2(4000) 
    unique,    
  dim             number(4),   
  subgraph_pretty varchar2(4000)   
)

API to Check Fully Connected Subgraphs when Adding/Removing an Edge

create or replace package graph_api    
  authid definer   
as   
     
  procedure addRelation(p1 in relations.p1%type,p2 in relations.p2%type);   
  procedure deleteRelation(p1 in relations.p1%type,p2 in relations.p2%type);   
   
  function isComplete(subgraph in complete_subgraphs.subgraph%type) return boolean;   
  procedure addSubgraph(subgraph in complete_subgraphs.subgraph%type);   
  procedure deleteSubgraph(subgraph in complete_subgraphs.subgraph%type);   
   
end graph_api;  

create or replace package body graph_api as  
  
  procedure addRelation(p1 in relations.p1%type,p2 in relations.p2%type) AS  
    v_graph complete_subgraphs.subgraph%type;  
    v_pos   pls_integer;  
  BEGIN  
    --dbms_output.put_line('addRelation ('||p1||','||p2||')');  
    -- the two node relation is always a complete subgraph  
    addSubgraph(p1||p2);  
      
    -- this logic assumes that the subgraphs are ordered and unique  
    -- find subgraphs where we can attach the beginning of the new relation somwhere  
    for g in (select s.subgraph, s.dim, instr(s.subgraph,p1) pos_p1  
              from complete_subgraphs s   
              where instr(s.subgraph,p1) > 0   
              and instr(s.subgraph,p2) = 0  
              ) loop  
      -- need to find where to add p2 into the string. Usually it would be at the end, but could also be somewhere in the middle          
      v_pos := g.dim + 1; -- add to last position if no greater node is found  
      for i in g.pos_p1+1 .. g.dim loop  
        if substr(g.subgraph, i, 1) > p2 then  
          v_pos := i;  
          exit; -- leave the loop  
        end if;  
      end loop;  
        
      v_graph := substr(g.subgraph, 1, v_pos-1) || p2 || substr(g.subgraph, v_pos);  
        
      -- is the new subgraph a complete subgraph?  
      if isComplete(v_graph) then           
        addSubgraph(v_graph);  
      end if;  
    end loop;  
    -- find subgraphs where we can attach the end of the new relation somwhere  
    -- abd + cd => abcd ?  
    for g in (select s.subgraph, s.dim, instr(s.subgraph,p2) pos_p2  
              from complete_subgraphs s   
              where instr(s.subgraph,p1) = 0   
              and instr(s.subgraph,p2) > 0  
              ) loop  
      --dbms_output.put_line('addRelation - consider '||g.subgraph||' + '||p1||p2);  
                
      -- need to find where to add p1 into the string. Usually it would be at the beginning, but could also be somewhere in the middle          
      v_pos := 1; -- add to first position if no lower node is found  
      for i in reverse 1 .. g.pos_p2-1 loop    
        --dbms_output.put_line('addRelation - inject p1 ? '||i);  
        if substr(g.subgraph, i, 1) < p1 then  
          v_pos := i+1;  
          --dbms_output.put_line('addRelation - inject p1 : '||v_pos);  
          exit; -- leave the loop  
        end if;  
      end loop;  
        
      v_graph := substr(g.subgraph, 1, v_pos-1) || p1 || substr(g.subgraph, v_pos);  
      --dbms_output.put_line('addRelation - '||v_graph);  
        
      -- is the new subgraph a complete subgraph?  
      if isComplete(v_graph) then           
        addSubgraph(v_graph);  
      end if;  
    end loop;  
      
  END addRelation;  
  
  procedure deleteRelation(p1 in relations.p1%type,p2 in relations.p2%type) AS  
  BEGIN  
    -- if a relation is deleted then all subgraphs that used this relation are not complete anymore  
    -- example: if "cd" is deleted then "acd", "abd", "abcd" and "cde" need to be deleted too  
    for g in (select *   
              from complete_subgraphs s   
              -- we remove(exchange with null) each node from the subgraph and compare the length to see if all nodes where there previously  
              --where length(translate(s.subgraph,'#'||deleteRelation.subgraph,'#')) = s.dim - length( deleteRelation.subgraph)   
              where instr(s.subgraph,p1) > 0   
              and instr(s.subgraph,p2) > 0  
             ) loop  
       deleteSubgraph(g.subgraph);  
    end loop;   
  END deleteRelation;  
  
  function isComplete(subgraph in complete_subgraphs.subgraph%type) return boolean as  
    v_check complete_subgraphs.subgraph%type;  
    v_dim   pls_integer;  
    v_ret   boolean := false;  
  BEGIN  
    --dbms_output.put_line('isComplete ? '||subgraph);   
    -- a subgraph is considered complete if   
    --   1. all subgraphs are constructed ordered (meaning each path is ordered from lowest to highest node)  
    --   2. the end node of the new relation is already connected with all previous end points. This is always a subgrpah of a lower dimension  
    -- for example "abce" is complete if "abe" is complete (e is connected to a and b) and "ce" exists  
    v_dim := length(subgraph);  
    if v_dim > 2 then  
      v_check := substr(subgraph,1,v_dim-2) || substr(subgraph,-1) ;  
      --dbms_output.put_line('search for '||v_check);   
      -- check if the lower dimension subgraph is complete  
      begin  
          select subgraph  
          into v_check  
          from complete_subgraphs  
          where subgraph = v_check;  
  
          -- check if there is a relation that matches the last two positions  
          --dbms_output.put_line('search for '||substr(isComplete.subgraph,-2));   
          select subgraph  
          into v_check  
          from complete_subgraphs  
          where subgraph = substr(isComplete.subgraph,-2)  
          and dim = 2;  
          -- The subgraph is complete  
          v_ret := true;  
  
      exception  
          when no_data_found then  
          -- The subgraph is not complete  
            v_ret := false;  
      end;  
        
    else  
      v_ret := true; -- Path of size 2 (2 nodes only) are always fully connected.  
    end if;  
    return v_ret;  
  END isComplete;  
  
  procedure addsubgraph(subgraph in complete_subgraphs.subgraph%type) as  
  begin  
    insert into complete_subgraphs(subgraph,dim,subgraph_pretty)  
    values (addsubgraph.subgraph,length(addsubgraph.subgraph),'('||rtrim(regexp_replace(addsubgraph.subgraph,'(.)','\1,'),',')||')');  
  exception  
    -- it could happen that we construct the same subgraph several times  
    -- then ignore it  
    when dup_val_on_index then null;  
  end addsubgraph;  
  
  procedure deleteSubgraph(subgraph in complete_subgraphs.subgraph%type) AS  
  begin  
    delete complete_subgraphs d  
    where d.subgraph = deletesubgraph.subgraph;  
  end deletesubgraph;  
  
end graph_api; 

Trigger to call API and add/remove entries in the subgraphs table

create or replace trigger relations_complete_subgraphs_ct  
  for insert or update or delete on relations   
  compound trigger  
  
  -- temp list of p1 and p2 and dml type (I=Insert, D=delete)  
  type rel_row_t is record (p1 relations.p1%type, p2 relations.p1%type, dml_type varchar2(1));   
  type rels_t is table of rel_row_t index by binary_integer;   
  g_rels rels_t;  
  g_rels_empty rels_t;  
  
  before statement is  
  begin  
    -- serialize access to the subgraphs table  
    execute immediate('lock table complete_subgraphs in exclusive mode');  
    g_rels := g_rels_empty;  -- initialization not really needed in a compound trigger  
  end before statement;  
  
  after each row is  
  begin  
    -- act depending on dml type  
    case  
      when inserting then  
        -- add to list  
        g_rels(g_rels.count+1) := rel_row_t(:new.p1,:new.p2,'I');  
      when updating then  
        -- do a delete with the old version and an insert   
        g_rels(g_rels.count+1) := rel_row_t(:old.p1,:old.p2,'D');  
        g_rels(g_rels.count+1) := rel_row_t(:new.p1,:new.p2,'I');  
      when deleting then  
        -- remember what to remove  
        g_rels(g_rels.count+1) := rel_row_t(:old.p1,:old.p2,'D');  
    end case;  
  end after each row;  
  
  after statement is  
  begin  
    -- handle all the changes  
    for r in 1..g_rels.count loop  
      case g_rels(r).dml_type   
      when 'I' then   
        graph_api.addRelation(g_rels(r).p1, g_rels(r).p2);  
      when 'D' then   
        graph_api.deleteRelation(g_rels(r).p1, g_rels(r).p2);  
      end case;    
    end loop;    
  
  end after statement;  
end relations_complete_subgraphs_ct; 

insert into relations   
  with rws ( p1 , p2 ) as (   
    select 'a' ,'b' from dual union all  
    select 'a' ,'c' from dual union all  
    select 'a' ,'d' from dual union all  
    
    select 'b' ,'c' from dual union all  
    select 'b' ,'d' from dual union all  
    
    select 'c' ,'d' from dual union all  
    select 'c' ,'e' from dual union all  
    select 'c' ,'f' from dual union all  
    
    select 'd' ,'e' from dual union all  
    
    select 'e' ,'f' from dual   
  )  
    select * from rws

select *   
/* Find all the fully connected subgraphs in this graph  
  
  (a,b,c)       
  (a,b,d)       
  (a,b,c,d)     
  (a,c,d)       
  (b,c,d)       
  (c,d,e)       
  (c,e,f)    
  
 */  
from relations

create or replace type ntt as table of varchar2(1); 

Naive - find all the possible subgraphs

with nodes as (  
  select distinct node from relations   
  unpivot (  
    node for px in ( p1, p2 )  
  )  
), graphs as (  
  select column_value graph,   
         cardinality ( column_value ) ns  
  from   powermultiset (   
    (  
      select cast ( collect ( node order by node ) as ntt )  
      from   nodes  
    )   
  )  
)  
  select * from graphs  
  where  ns >= 3  
  and    (  
    select count(*) from relations  
    where  p1 member graph  
    and    p2 member graph  
  ) = ns * ( ns - 1 ) / 2

Search Within Possible Subgraphs

with candidates as (  
  select connect_by_root ( p1 ) || sys_connect_by_path ( p2, ',' ) pth,   
         level lvl   
  from   relations  
  where  level > 1  
  connect by p1 = prior p2  
), pairs as (   
  select '%' || r.p1 || ',%' || r.p2 || '%' pair  
  from   relations r  
)  
  select g.pth, lvl, count(*), max ( pair )   
  from   candidates g  
  join   pairs r  
  on     g.pth like pair  
  group  by g.pth, lvl  
  having count(*) = lvl * ( lvl + 1 ) / 2  
  order  by pth

Refining - only add nodes with an edge back to the start

with graphs (   
  node, rt, pth, lvl  
) as (   
  select p2, p1, p1 || ',' || p2, 1 lvl   
  from   relations  
  union  all  
  select n.p2, g.rt, g.pth || ',' || n.p2, lvl + 1 lvl  
  from   graphs g  
  join   relations n  
  on     g.node = n.p1  
  where  exists (  
    select * from relations r  
    where  r.p1 = g.rt  
    and    r.p2 = n.p1  
  )  
)  
  select g.pth, lvl, count(*)  
  from   graphs g  
  join relations r  
  on     g.pth like '%' || r.p1 || ',%' || r.p2 || '%'  
  group  by g.pth, lvl  
  having count(*) > 1  
  and    count(*) = lvl * ( lvl + 1 ) / 2  
  order  by pth

Verify Each Edge is Fully Connected When Adding

with data(p, p1, p2, coll) as (   
  select a.p1, b.p1, b.p2, ntt(a.p1, a.p2, b.p2)   
  from   relations a    
  join   relations b   
  on     a.p2 = b.p1   
  and    (a.p1, b.p2) in (select * from relations)   
  union all   
  select a.p1, b.p1, b.p2, a.coll multiset union ntt(b.p2)   
  from   data a    
  join   relations b   
  on     a.p2 = b.p1   
  and (   
    select count(*)   
    from   table ( a.coll )   
    where  ( column_value, b.p2 ) not in (   
      select * from relations   
    )   
  ) = 0   
) cycle p, p1, p2 set is_cycle to '1' default '0'   
  select ps   
  from   data, lateral(   
    select '(' || listagg ( column_value, ',' )   
             within group ( order by column_value ) || ')' ps   
    from   table(coll)   
 )

Query the Pre-computed Subgraphs

select subgraph_pretty  
from   complete_subgraphs  
where  dim > 2