Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Количество груп связей в many to many  [new]
andrei.ilin
Member

Откуда:
Сообщений: 31
Добрый день,

Есть таблица accounts clients,

create table test (clientid NUMBER(10), accountid NUMBER(10));

insert into test values (1, 10);
insert into test values (2, 20);
insert into test values (3, 30);
insert into test values (4, 40);
insert into test values (5, 50);
insert into test values (6, 60);

insert into test values (2, 10);
insert into test values (3, 10);
insert into test values (5, 60);

Надо вывести все групы связаных клиентов и счетов в виде

groupId, accountId, clientId, numberOfRows

То есть должно быть что то типа:

1 10 1 5
1 10 2 5
1 30 3 5
1 10 3 5
1 20 2 5

...

То есть вывести все группы и их состав которые независимы и не имеют других связей.
У клиентов может быть общий счет, на оборот. Идшники для клиентов и счетов не пересекаются.

Посмотрел примеры в гугле, но все примеры по parent child...
21 окт 13, 19:39    [15010524]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
grey_narn
Member

Откуда: Алма-Ата, Казахстан
Сообщений: 178
andrei.ilin,

Погуглите по connected components graph sql, наверное, можно как-то.
Если у вас небольшая таблица, то проще процедурно через PL/SQL.
21 окт 13, 22:35    [15011079]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
andrei.ilin
Member

Откуда:
Сообщений: 31
Ок, посмотрю в google.
Таблица 30 mil rows.
Не охота через Java делать, мне кажеться сиквелом можно как то сделать.
21 окт 13, 23:01    [15011180]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
andrei.ilin,

я не седжвик, поэтому за результат и скорость не ручаюсь
+
with t as (
    select * 
    from test
    model 
       dimension by (clientid,accountid)
       measures (to_number(null) root)
       rules sequential order
       (
         root[any,any] 
         order by clientid,accountid
                    =least( 
                             nvl(
                                 min(root)[cv(),any]
                                ,cv(clientid)
                                )
                            ,nvl(
                                 min(root)[any,cv()]
                                ,cv(clientid)
                                )
                            )
       )
)
select clientid
      ,accountid
      ,dense_rank()over(order by root)  group_number
      ,count(*) over(partition by root) connected
from t 
order by 3,1,2
22 окт 13, 00:06    [15011465]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Zeratulnn
Member

Откуда:
Сообщений: 85
andrei.ilin,

Возможно и не быстрый вариант
with a as(select distinct CONNECT_BY_ROOT(accountid) as ra, CONNECT_BY_ROOT(clientid) as rc,accountid, clientid from test
connect by NOCYCLE  accountid = prior accountid or clientid= prior clientid)

select dense_rank() over(order by gp) as dr,a.accountid, a.clientid,count(*) over(partition by gp) as ct from (
select a.*,listagg(accountid||','||clientid,';') within group(order by accountid,clientid) over(partition by ra,rc) gp from a)a
where gp like ra||','||rc||';%'

А также можете посмотреть математическую задачу на определение компонентов связности графов
22 окт 13, 09:42    [15012184]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Zeratulnn
Member

Откуда:
Сообщений: 85
Zeratulnn,

Немного поспешил
with a as(select distinct CONNECT_BY_ROOT(accountid) as ra, CONNECT_BY_ROOT(clientid) as rc,accountid, clientid from test
connect by NOCYCLE prior accountid = accountid or prior clientid= clientid)

select dense_rank() over(order by gp) as dr,a.accountid, a.clientid,count(*) over(partition by gp) as ct from (
select a.*,listagg(accountid||','||clientid||' ',';') within group(order by accountid,clientid) over(partition by ra,rc) gp from a)a
where gp like ra||','||rc||' '||'%'
22 окт 13, 09:46    [15012208]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
andrei.ilin,

create or replace function mincli(p$id in test.clientid%type) return test.clientid%type
deterministic
result_cache
is
v$id test.clientid%type;
begin
select min(t.clientid)
into v$id
from test t
where t.accountid in (select tt.accountid from test tt where tt.clientid = p$id);
if v$id < p$id then
   v$id := mincli(v$id);
end if;
return v$id;
end mincli;
/

select mincli(clientid) as groupid, clientid, accountid, count(*) over (partition by mincli(clientid)) as cnt
from test
/
22 окт 13, 11:52    [15013232]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
Павел Воронцов,

у нас одинаковые ошибки :)
22 окт 13, 13:16    [15014120]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
правильно будет как-то так:
+
declare
   i    int:=0;
   v    sys.ku$_objnumpairlist:=sys.ku$_objnumpairlist();
   
   type t_root is table of pls_integer index by pls_integer;
   root   t_root;
   
   function get_root(n int) return pls_integer is
   begin
      if root.exists(n) then 
         return root(n);
      else 
         return null;
      end if;
   end;
   
   procedure update_root(old_root pls_integer,new_root pls_integer) is
      i pls_integer;
   begin
      i := root.FIRST;
      while i is not null
      loop
         if root(i) = old_root then 
            root(i):=new_root;
         end if;
        
         i := root.NEXT(i);
      end loop;
   end;
   
   procedure add_link(clientid pls_integer,accountid pls_integer) is
      r1       pls_integer;
      r2       pls_integer;
      new_root pls_integer;
   begin
      r1:=get_root(clientid);
      r2:=get_root(accountid);
      if r1 is null or r2 is null then
         new_root :=coalesce(r1,r2,clientid);
      elsif r1 is not null then
         new_root := least(r1,r2);
         update_root(greatest(r1,r2),new_root);
      end if;
      root(clientid) :=new_root;
      root(accountid):=new_root;

   end;
   
   function str_format(clientid pls_integer,accountid pls_integer) return varchar2 is
   begin
      return utl_lms.format_message('(%d, %d) = group #%d'
                                   ,clientid
                                   ,accountid
                                   ,get_root(clientid)
                                   );
   end;
begin
   for r in (select * from test) loop
      add_link(r.clientid,r.accountid);
      v.extend;
      i:=i+1;
      v(i):=sys.ku$_objnumpair(r.clientid,r.accountid);
   end loop;
---
   for r in 1..i loop
      dbms_output.put_line(str_format(v(r).num1,v(r).num2));
   end loop;
end;
22 окт 13, 13:18    [15014130]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
+ тестовые данные
truncate table test;
begin
   insert into test values (1, 10);
   insert into test values (2, 20);
   insert into test values (3, 30);
   insert into test values (4, 40);
   insert into test values (5, 50);
   insert into test values (6, 60);

   insert into test values (3, 20);
   insert into test values (4, 10);
   insert into test values (4, 20);
   commit;
end;
/
22 окт 13, 13:18    [15014142]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
xtender,

Прости, а какие? Не въезжаю.
22 окт 13, 13:22    [15014191]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
Павел Воронцов,

тестовые данные выше погляди
22 окт 13, 13:25    [15014222]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
xtender,

Точно. Сперва держал это в голове, потом оно выпало.
22 окт 13, 13:35    [15014357]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Elic
Member

Откуда: 1984. Следующие на оккупацию финно-угром
Сообщений: 23857
Группировка типа "или" - не могу придумать как реализовать
22 окт 13, 14:17    [15014822]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
xtender,

Работа над ошибками:

+
create or replace function mincli(p$id in test.clientid%type
) return test.clientid%type
deterministic
result_cache
is
type tab$num is table of test.clientid%type index by pls_integer;
v$cid test.clientid%type;
v_tab$num tab$num;
function mcli(p$id in test.clientid%type
, p_tab$num in out tab$num) return test.clientid%type
is
v_tab$num2 tab$num;
v$id test.clientid%type := p$id;
begin
select t.clientid
bulk collect into v_tab$num2
from test t
where t.accountid in (select tt.accountid from test tt where tt.clientid = p$id);
<<idx2>>
for i$idx in v_tab$num2.first..v_tab$num2.last loop
if not p_tab$num.exists(v_tab$num2(i$idx)) and v_tab$num2(i$idx) <> p$id then
p_tab$num(v_tab$num2(i$idx)) := v_tab$num2(i$idx);
v$id := least(mcli(v_tab$num2(i$idx), p_tab$num),v$id);
end if;
end loop idx2;
return v$id;
end mcli;
begin
   v$cid := mcli(p$id,v_tab$num);
return v$cid;
end mincli;
/



Elic,

Тут нет идентификатора, за который можно зацепиться. Что-то я туплю как этот подход тут применить.
22 окт 13, 14:53    [15015085]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Elic
Member

Откуда: 1984. Следующие на оккупацию финно-угром
Сообщений: 23857
Павел Воронцов
Тут нет идентификатора, за который можно зацепиться. Что-то я туплю как этот подход тут применить.
Тут целых два идентификатора, выбирай любой. На худой конец - rownum.
+
select max(group_member_id) as group_max_id, accountid, clientid
  from
         , connect_by_root accountid as accountid
         , connect_by_root clientid  as clientid
      from test
      connect by nocycle decode(accountid, prior accountid, 1, 0)
                       + decode(clientid,  prior clientid,  1, 0)
                       = 1
  )
  group by accountid, clientid
  order by group_max_id, accountid
;
А Zeratulnn, вроде как, перемудрил.
22 окт 13, 15:53    [15015588]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
Elic,

Да, красиво. Осталось спросить у ТС что на его данных шустрей работать будет.
22 окт 13, 16:34    [15016008]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
Павел Воронцов
Member

Откуда: Новосибирск
Сообщений: 2123
Блог
Elic,

На всякий случай твое решение, но рабочее:
+
select min(group_member_id) as group_max_id, accountid, clientid
  from  (select clientid as group_member_id
         , connect_by_root accountid as accountid
         , connect_by_root clientid  as clientid
      from test
      connect by nocycle decode(accountid, prior accountid, 1, 0)
                       + decode(clientid,  prior clientid,  1, 0)
                       = 1
  ) a
  group by accountid, clientid
  order by group_max_id, accountid
/
22 окт 13, 16:35    [15016019]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
Павел Воронцов
Осталось спросить у ТС что на его данных шустрей работать будет.
если группы небольшие, то можно и connect by(там по экспоненте сложность увеличивается), а если большие, то лучше так:
+
declare
   type int_array    is table of pls_integer index by pls_integer;
   type arr_elems    is table of sys.ku$_objnumset index by pls_integer;
   root              int_array;
   root_elems        arr_elems;

   n        int;
   clients  int_array;
   accounts int_array;

    l integer:=dbms_utility.get_time();

    procedure print(v in varchar2) is
    begin
      dbms_output.put_line(to_char((dbms_utility.get_time-l)/100,'0999.99')||' '||v);
      l:=dbms_utility.get_time();
    end;

   
   function get_root(n int) return pls_integer is
   begin
      if root.exists(n) then 
         return root(n);
      else 
         return null;
      end if;
   end;
   
   procedure update_root(old_root pls_integer,new_root pls_integer) is
      i pls_integer;
   begin
      if old_root!=new_root then 
         root_elems(new_root):=root_elems(new_root) multiset union all root_elems(old_root);
         for i in 1..root_elems(old_root).count
         loop
            root(root_elems(old_root)(i)):=new_root;
         end loop;
         root_elems(old_root).delete;
       end if;
   end;
   
   procedure add_elem(p_root pls_integer, p_elem pls_integer) is
   begin
      if not root_elems.exists(p_root) then
         root_elems(p_root):=sys.ku$_objnumset(p_elem);
      else
         root_elems(p_root).extend();
         root_elems(p_root)(root_elems(p_root).count):=p_elem;
      end if;
   end;
   
   procedure add_link(clientid pls_integer,accountid pls_integer) is
      r1       pls_integer;
      r2       pls_integer;
      new_root pls_integer;
   begin
      r1:=get_root(clientid);
      r2:=get_root(accountid);
      
      if r1 is null or r2 is null then
         new_root := coalesce(r1,r2,clientid);
         if r1 is null then add_elem(new_root,clientid ); root(clientid) :=new_root; end if;
         if r2 is null then add_elem(new_root,accountid); root(accountid):=new_root; end if;
      else
         new_root := least(r1,r2);
         root(clientid) :=new_root;
         root(accountid):=new_root;
         update_root(greatest(r1,r2),new_root);
      end if;
      
   end;
   
   function str_format(p int) return varchar2 is
   begin
      return utl_lms.format_message('(%d, %d) = group #%d'
                                   ,clients(p)
                                   ,accounts(p)
                                   ,get_root(clients(p))
                                   );
   end;
begin
   print('start');
   select clientid,accountid 
          bulk collect into clients,accounts
   from test 
--   where rownum<=1000
   ;
   print('fetched');
   n:=clients.count;
   dbms_output.put_line('count='||n);
   for i in 1..n loop
      add_link(clients(i),accounts(i));
   end loop;
   print('processed');
---
/*
   for i in 1..n loop
      dbms_output.put_line(str_format(i));
   end loop;
--   */
end;
22 окт 13, 17:29    [15016483]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
еще чуток оптимизнул:
+
declare
   type int_array    is table of pls_integer index by pls_integer;
   type arr_elems    is table of sys.ku$_objnumset index by pls_integer;
   root              int_array;
   root_elems        arr_elems;

   n        int;
   clients  int_array;
   accounts int_array;

    l integer:=dbms_utility.get_time();

    procedure print(v in varchar2) is
    begin
      dbms_output.put_line(to_char((dbms_utility.get_time-l)/100,'0999.99')||' '||v);
      l:=dbms_utility.get_time();
    end;

   
   function get_root(n int) return pls_integer is
   begin
      if root.exists(n) then 
         return root(n);
      else 
         return null;
      end if;
   end;
   
   procedure update_root(old_root pls_integer,new_root pls_integer) is
      i       pls_integer;
      elem    pls_integer;
      cnt_old pls_integer;
      cnt_new pls_integer;
   begin
      if old_root!=new_root then 
         --root_elems(new_root):=root_elems(new_root) multiset union all root_elems(old_root);
         cnt_old:=root_elems(old_root).count;
         cnt_new:=root_elems(new_root).count;
         root_elems(new_root).extend(cnt_old);
         for i in 1..cnt_old
         loop
            elem := root_elems(old_root)(i);
            root(elem):=new_root;
            root_elems(new_root)(cnt_new+i):=elem;
         end loop;
         root_elems(old_root).delete;
      end if;
   end;
   
   procedure add_elem(p_root pls_integer, p_elem pls_integer) is
   begin
      if not root_elems.exists(p_root) then
         root_elems(p_root):=sys.ku$_objnumset(p_elem);
      else
         root_elems(p_root).extend();
         root_elems(p_root)(root_elems(p_root).count):=p_elem;
      end if;
   end;
   
   procedure add_link(clientid pls_integer,accountid pls_integer) is
      r1       pls_integer;
      r2       pls_integer;
      new_root pls_integer;
   begin
      r1:=get_root(clientid);
      r2:=get_root(accountid);
      
      if r1 is null or r2 is null then
         new_root := coalesce(r1,r2,clientid);
         if r1 is null then add_elem(new_root,clientid ); root(clientid) :=new_root; end if;
         if r2 is null then add_elem(new_root,accountid); root(accountid):=new_root; end if;
      else
         new_root := least(r1,r2);
         root(clientid) :=new_root;
         root(accountid):=new_root;
         update_root(greatest(r1,r2),new_root);
      end if;
      
   end;
   
   function str_format(p int) return varchar2 is
   begin
      return utl_lms.format_message('(%d, %d) = group #%d'
                                   ,clients(p)
                                   ,accounts(p)
                                   ,get_root(clients(p))
                                   );
   end;
begin
   print('start');
   select clientid,accountid 
          bulk collect into clients,accounts
   from test 
--   where rownum<=1000
   ;
   print('fetched');
   n:=clients.count;
   dbms_output.put_line('count='||n);
   for i in 1..n loop
      add_link(clients(i),accounts(i));
   end loop;
   print('processed');
---
/*
   for i in 1..n loop
      dbms_output.put_line(str_format(i));
   end loop;
--   */
end;
22 окт 13, 17:50    [15016596]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
проверил дома на стареньком интеле на 3млн связанных - обработало за 14 секунд
22 окт 13, 21:39    [15017404]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
andrei.ilin
Member

Откуда:
Сообщений: 31
Павел Воронцов
Elic,

На всякий случай твое решение, но рабочее:
+
select min(group_member_id) as group_max_id, accountid, clientid
  from  (select clientid as group_member_id
         , connect_by_root accountid as accountid
         , connect_by_root clientid  as clientid
      from test
      connect by nocycle decode(accountid, prior accountid, 1, 0)
                       + decode(clientid,  prior clientid,  1, 0)
                       = 1
  ) a
  group by accountid, clientid
  order by group_max_id, accountid
/


Запустил на 60 mil в параллели 16, за 4 часа не отработало. Утром проверю - тут случайно не O((n^2)/2) сложность? А то что то очень долго.
22 окт 13, 23:05    [15017670]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
andrei.ilin
Утром проверю - тут случайно не O((n^2)/2) сложность?
а не O(n!)?
22 окт 13, 23:14    [15017692]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
xtender
а не O(n!)?
брр, т.е. O(n^n)
22 окт 13, 23:17    [15017699]     Ответить | Цитировать Сообщить модератору
 Re: Количество груп связей в many to many  [new]
xtender
Member

Откуда: Мск
Сообщений: 3241
трудно оценивать, т.к. тут зависит как от размера групп важен так и от общего кол-ва зависит
22 окт 13, 23:19    [15017701]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Oracle Ответить
 
Лучший учебный центр Microsoft!
Новейшие курсы Microsoft SQL Server 2014!
ОЧЕНЬ привлекательные цены на курсы Oracle — от 26 тыс.руб.!
Все курсы по базам данных: Microsoft SQL Server 2014, Oracle, IBM DB2, Access, MySql