Hi Team ,
with data ( 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 data ;
my data is like above .
Assume those columns data is nothing but persons info .relation between these two columns is knows each other ( a knows b and b knows a i.e) bi-directional ).
with this data i want to find out the groups based on below conditions .
1) each group must contain more than 2 persons.
2) one person should know , remaining persons in the same group.
expected o/p is :
-----------------
(a,b,c)
(a,b,c,d)
(b,c,d)
(c,d,e)
i missed to add below o/p in previous post
(c,e,f)
(a,c,d)
(a,b,d)
An interesting problem!
I reached out on Twitter for solutions to this. You can find the community answers in the following Live SQL script:
https://livesql.oracle.com/apex/livesql/file/content_IOHVI2K4AYK6GOMOAVG93YBF6.html For brevity here, I'll just discuss Stew Ashton's optimized solution.
This works by:
- Using recursive with to traverse the graph
- For each new vertex, it:
- Adds it to a nested table array of vertices
- Builds a table with an edge from the new vertex to all the existing vertices in the subgraph
- For these edges, checks there are NO edges which are NOT in the existing edge set. i.e. every generated edge is in the original graph.
So this is saying, for each new vertex:
Does this have an edge to all the existing vertices in the subgraph?
If no, this does NOT form a fully connected subgraph. If yes, it does!
In SQL, this looks something like:
create table relations (
p1 varchar2(1), p2 varchar2(1),
primary key ( p1, p2 ),
check ( p2 > p1 )
);
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;
create or replace type ntt as table of varchar2(1);
/
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)
);
PS
(a,b,c)
(a,b,d)
(a,c,d)
(b,c,d)
(c,d,e)
(c,e,f)
(a,b,c,d) Note: for this problem, the worst-case number of subgraphs is 2^number of vertices. So for a trivial, 100 vertex graph the number of possible subgraphs is a number with
thirty digits!
This could be exceptionally slow!To resolve this, you may want to calculate the subgraphs on write. See the package & trigger in the Live SQL script for this method. Note this moves the calculation to insert/delete time. Which brings its own issues...
Or, it's worth asking: do you
really need
all the fully connected subgraphs?
I'm guessing no. In which case you may be looking for strongly connected components (or similar). This is more feasible to run on large graphs :)
You can use our graph technologies to do this. Hans Viehmann covered these in our SQL Office Hours session on 16th July, where we discussed this problem.
The recording for this will be available soon. When it's live you can access it at:
https://asktom.oracle.com/pls/apex/f?p=100:551:::NO:551:P551_CLASS_ID,P551_STUDENT_ID:6204&cs=11921B2B179A7F0F930F234DE1BF1DCFC