Группировать все связанные записи во многих отношениях, компоненты, связанные с графиком SQL

Ответ 1

Я думал об использовании рекурсивного CTE, но, насколько мне известно, в SQL Server невозможно использовать UNION для подключения элемента привязки и рекурсивного член рекурсивного CTE (я думаю, что это можно сделать в PostgreSQL), поэтому невозможно исключить дубликаты.

declare @i int

with cte as (
     select
         GroupID,
         row_number() over(order by Company) as rn
     from Table1
)
update cte set GroupID = rn

select @i = @@rowcount

-- while some rows updated
while @i > 0
begin
    update T1 set
        GroupID = T2.GroupID
    from Table1 as T1
        inner join (
            select T2.Company, min(T2.GroupID) as GroupID
            from Table1 as T2
            group by T2.Company
        ) as T2 on T2.Company = T1.Company
    where T1.GroupID > T2.GroupID

    select @i = @@rowcount

    update T1 set
        GroupID = T2.GroupID
    from Table1 as T1
        inner join (
            select T2.Publisher, min(T2.GroupID) as GroupID
            from Table1 as T2
            group by T2.Publisher
        ) as T2 on T2.Publisher = T1.Publisher
    where T1.GroupID > T2.GroupID

    -- will be > 0 if any rows updated
    select @i = @i + @@rowcount
end

;with cte as (
     select
         GroupID,
         dense_rank() over(order by GroupID) as rn
     from Table1
)
update cte set GroupID = rn

демонстрационная версия sql

Я также пробовал алгоритм поиска первого порядка. Я думал, что это может быть быстрее (это лучше с точки зрения сложности), поэтому я буду предлагать решение здесь. Я обнаружил, что это не быстрее, чем SQL-подход:

declare @Company nvarchar(2), @Publisher nvarchar(2), @GroupID int

declare @Queue table (
    Company nvarchar(2), Publisher nvarchar(2), ID int identity(1, 1),
    primary key(Company, Publisher)
)

select @GroupID = 0

while 1 = 1
begin
    select top 1 @Company = Company, @Publisher = Publisher
    from Table1
    where GroupID is null

    if @@rowcount = 0 break

    select @GroupID = @GroupID + 1

    insert into @Queue(Company, Publisher)
    select @Company, @Publisher

    while 1 = 1
    begin
        select top 1 @Company = Company, @Publisher = Publisher
        from @Queue
        order by ID asc

        if @@rowcount = 0 break

        update Table1 set
            GroupID = @GroupID
        where Company = @Company and Publisher = @Publisher

        delete from @Queue where Company = @Company and Publisher = @Publisher

        ;with cte as (
            select Company, Publisher from Table1 where Company = @Company and GroupID is null
            union all
            select Company, Publisher from Table1 where Publisher = @Publisher and GroupID is null
        )
        insert into @Queue(Company, Publisher)
        select distinct c.Company, c.Publisher
        from cte as c
        where not exists (select * from @Queue as q where q.Company = c.Company and q.Publisher = c.Publisher)
   end
end

демонстрационная версия sql

Я тестировал свою версию и Гордон Линофф, чтобы проверить, как она работает. Похоже, что CTE намного хуже, я не мог дождаться, когда он завершится более чем на 1000 строк.

Здесь демонстрация скриптов sql со случайными данными. Мои результаты:
128 строк:
мое решение RBAR: 190 мс Решение моего SQL: 27 мс
Решение Гордона Линоффа: 958 мс
256 строк:
мое решение RBAR: 560 мс Решение для моего SQL: 1226ms
Решение Гордона Линоффа: 45371мс

Это случайные данные, поэтому результаты могут быть не очень последовательными. Я думаю, что время может быть изменено индексами, но не думайте, что это может изменить целую картину.

старой версии - используя временную таблицу, просто вычисляя GroupID, не касаясь исходной таблицы:

declare @i int

-- creating table to gather all possible GroupID for each row
create table #Temp
(
    Company varchar(1), Publisher varchar(1), GroupID varchar(1),
    primary key (Company, Publisher, GroupID)
)

-- initializing it with data
insert into #Temp (Company, Publisher, GroupID)
select Company, Publisher, Company
from Table1

select @i = @@rowcount

-- while some rows inserted into #Temp
while @i > 0
begin
    -- expand #Temp in both directions
    ;with cte as (
        select
            T2.Company, T1.Publisher,
            T1.GroupID as GroupID1, T2.GroupID as GroupID2
        from #Temp as T1
            inner join #Temp as T2 on T2.Company = T1.Company
        union
        select
            T1.Company, T2.Publisher,
            T1.GroupID as GroupID1, T2.GroupID as GroupID2
        from #Temp as T1
            inner join #Temp as T2 on T2.Publisher = T1.Publisher        
    ), cte2 as (
        select
            Company, Publisher,
            case when GroupID1 < GroupID2 then GroupID1 else GroupID2 end as GroupID
        from cte
    )
    insert into #Temp
    select Company, Publisher, GroupID
    from cte2
    -- don't insert duplicates
    except
    select Company, Publisher, GroupID
    from #Temp

    -- will be > 0 if any row inserted
    select @i = @@rowcount
end

select
    Company, Publisher,
    dense_rank() over(order by min(GroupID)) as GroupID
from #Temp
group by Company, Publisher

= > Пример скрипта sql

Ответ 2

Ваша проблема - проблема с нахождением граф-подстановок. Это немного сложнее, потому что ваша структура данных имеет два типа узлов ( "компании" и "публичные объявления" ), а не один тип.

Вы можете решить это с помощью одного рекурсивного CTE. Логика следующая.

Сначала преобразуем задачу в граф только с одним типом node. Я делаю это, заставляя узлы компаний и края связывать между компаниями, используя информацию издателя. Это просто соединение:

      select t1.company as node1, t2.company as node2
      from table1 t1 join
           table1 t2
           on t1.publisher = t2.publisher
     )

(Для эффективности вы также можете добавить t1.company <> t2.company, но это не является строго необходимым.)

Теперь, это "простая" проблема перемещения графа, где рекурсивный CTE используется для создания всех соединений между двумя узлами. Рекурсивный CTE просматривает график с помощью join. По пути он ведет список всех посещенных узлов. В SQL Server это необходимо сохранить в строке.

Код должен убедиться, что он не посещает node дважды для данного пути, потому что это может привести к бесконечной рекурсии (и ошибке). Если вышесказанное называется edges, CTE, который генерирует все пары подключенных узлов, выглядит так:

     cte as (
      select e.node1, e.node2, cast('|'+e.node1+'|'+e.node2+'|' as varchar(max)) as nodes,
             1 as level
      from edges e
      union all
      select c.node1, e.node2, c.nodes+e.node2+'|', 1+c.level
      from cte c join
           edges e
           on c.node2 = e.node1 and
              c.nodes not like '|%'+e.node2+'%|'
     )

Теперь, используя этот список подключенных узлов, присвойте каждому node минимум всех узлов, к которым он подключен, включая себя. Это служит идентификатором связанных подграфов. То есть все компании, подключенные друг к другу через издателей, будут иметь одинаковый минимум.

Последние два шага - перечислить этот минимум (как GroupId) и присоединить GroupId к исходным данным.

Полный (и я могу добавить проверенный) запрос выглядит так:

with edges as (
      select t1.company as node1, t2.company as node2
      from table1 t1 join
           table1 t2
           on t1.publisher = t2.publisher
     ),
     cte as (
      select e.node1, e.node2,
             cast('|'+e.node1+'|'+e.node2+'|' as varchar(max)) as nodes,
             1 as level
      from edges e
      union all
      select c.node1, e.node2,
             c.nodes+e.node2+'|',
             1+c.level
      from cte c join
           edges e
           on c.node2 = e.node1 and
              c.nodes not like '|%'+e.node2+'%|'
     ),
     nodes as (
       select node1,
              (case when min(node2) < node1 then min(node2) else node1 end
              ) as grp
       from cte
       group by node1
      )
select t.company, t.publisher, grp.GroupId
from table1 t join
     (select n.node1, dense_rank() over (order by grp) as GroupId
      from nodes n
     ) grp
     on t.company = grp.node1;

Обратите внимание, что это работает при поиске любых связанных подграфов. Он не предполагает, что любое определенное количество уровней.

EDIT:

Вопрос о производительности для этого досадно. Как минимум, указанный выше запрос будет работать лучше с индексом на Publisher. Еще лучше взять предложение @MikaelEriksson и поместить ребра в отдельную таблицу.

Еще один вопрос: ищете ли вы классы эквивалентности среди компаний или издателей. Я взял подход к использованию компаний, потому что я думаю, что это лучше "объяснимость" (моя склонность отвечать была основана на многочисленных комментариях, что это не может быть сделано с CTE).

Я предполагаю, что вы можете получить разумную производительность, хотя это требует большего знания ваших данных и системы, чем предусмотрено в OP. Однако вполне вероятно, что лучшая производительность будет получена из подхода с несколькими запросами.

Ответ 3

Вот мое решение SQL Fiddle

В природе отношений требуется цикл, как я полагаю.

Вот SQL:

--drop TABLE Table1

CREATE TABLE Table1
    ([row] int identity (1,1),GroupID INT NULL,[Company] varchar(2), [Publisher] varchar(2))
;

INSERT INTO Table1
    (Company, Publisher)
select
    left(newid(), 2), left(newid(), 2)

declare @i int = 1

while @i < 8
begin
    ;with cte(Company, Publisher) as (
        select
            left(newid(), 2), left(newid(), 2)
        from Table1
    )
    insert into Table1(Company, Publisher)
    select distinct c.Company, c.Publisher
    from cte as c
    where not exists (select * from Table1 as t where t.Company = c.Company and t.Publisher = c.Publisher)

    set @i = @i + 1
end;


CREATE NONCLUSTERED INDEX IX_Temp1 on Table1 (Company)
CREATE NONCLUSTERED INDEX IX_Temp2 on Table1 (Publisher)

declare @counter int=0
declare @row int=0
declare @lastnullcount int=0
declare @currentnullcount int=0

WHILE EXISTS (
  SELECT *
  FROM Table1
  where GroupID is null
  )
BEGIN
    SET @[email protected]+1
    SET @lastnullcount =0

    SELECT TOP 1
        @row=[row]
    FROM Table1
    where GroupID is null
    order by [row] asc

    SELECT @currentnullcount=count(*) from table1 where groupid is null
    WHILE @lastnullcount <> @currentnullcount
    BEGIN
        SELECT @lastnullcount=count(*)
        from table1
        where groupid is null 

        UPDATE Table1
        SET [email protected]
        WHERE [row][email protected]

        UPDATE t2
        SET [email protected]
        FROM Table1 t1
        INNER JOIN Table1 t2 on t1.Company=t2.Company
        WHERE [email protected]
        AND t2.GroupID IS NULL

        UPDATE t2
        SET [email protected]
        FROM Table1 t1
        INNER JOIN Table1 t2 on t1.publisher=t2.publisher
        WHERE [email protected]
        AND t2.GroupID IS NULL

        SELECT @currentnullcount=count(*)
        from table1
        where groupid is null
    END
END

SELECT * FROM Table1

Изменить: Добавлены индексы, как я ожидал бы на реальной таблице, и больше согласуются с другими наборами данных, которые использует Roman.

Ответ 4

Вы пытаетесь найти все связанные компоненты вашего графика, которые могут выполняться только итеративно. Если вы знаете максимальную ширину любого подключенного компонента (т.е. Максимальное количество ссылок, которые вы должны будете брать от одной компании/издателя к другому), вы могли бы в принципе сделать это примерно так:

SELECT
    MIN(x2.groupID) AS groupID,
    x1.Company,
    x1.Publisher
FROM Table1 AS x1
    INNER JOIN (
        SELECT
            MIN(x2.Company) AS groupID,
            x1.Company,
            x1.Publisher
        FROM Table1 AS x1
            INNER JOIN Table1 AS x2
            ON x1.Publisher = x2.Publisher
        GROUP BY
            x1.Publisher,
            x1.Company
    ) AS x2
    ON x1.Company = x2.Company
GROUP BY
    x1.Publisher,
    x1.Company;

Вы должны сохранить вложенный подзапрос (чередующиеся соединения в компании и издателе и с самым глубоким подзапросом, в котором указана MIN (компания), а не MIN (groupID)) до максимальной глубины итерации.

Я действительно не рекомендую это; было бы проще сделать это за пределами SQL.

Отказ от ответственности: я ничего не знаю о SQL Server 2012 (или любой другой версии); у него может быть какая-то дополнительная возможность создания скриптов, позволяющая динамически выполнять эту итерацию.

Ответ 5

Это рекурсивное решение, использующее XML:

with a as ( -- recursive result, containing shorter subsets and duplicates
    select cast('<c>' + company + '</c>' as xml) as companies
          ,cast('<p>' + publisher + '</p>' as xml) as publishers
      from Table1

    union all

    select a.companies.query('for $c in distinct-values((for $i in /c return string($i),
                                                        sql:column("t.company")))
                          order by $c
                          return <c>{$c}</c>')
          ,a.publishers.query('for $p in distinct-values((for $i in /p return string($i),
                                                         sql:column("t.publisher")))
                          order by $p
                          return <p>{$p}</p>')
    from a join Table1 t
      on (   a.companies.exist('/c[text() = sql:column("t.company")]') = 0 
          or a.publishers.exist('/p[text() = sql:column("t.publisher")]') = 0)
     and (   a.companies.exist('/c[text() = sql:column("t.company")]') = 1
          or a.publishers.exist('/p[text() = sql:column("t.publisher")]') = 1)
), b as ( -- remove the shorter versions from earlier steps of the recursion and the duplicates
    select distinct -- distinct cannot work on xml types, hence cast to nvarchar
           cast(companies as nvarchar) as companies
          ,cast(publishers as nvarchar) as publishers
          ,DENSE_RANK() over(order by cast(companies as nvarchar), cast(publishers as nvarchar)) as groupid
     from a
    where not exists (select 1 from a as s -- s is a proper subset of a
                       where (cast('<s>' + cast(s.companies as varchar)
                                 + '</s><a>' + cast(a.companies as varchar) + '</a>' as xml)
                             ).value('if((count(/s/c) > count(/a/c))
                                         and (some $s in /s/c/text() satisfies
                                             (some $a in /a/c/text() satisfies $s = $a))
                                      ) then 1 else 0', 'int') = 1
                     )
      and not exists (select 1 from a as s -- s is a proper subset of a
                       where (cast('<s>' + cast(s.publishers as nvarchar)
                                 + '</s><a>' + cast(a.publishers as nvarchar) + '</a>' as xml)
                             ).value('if((count(/s/p) > count(/a/p))
                                         and (some $s in /s/p/text() satisfies
                                             (some $a in /a/p/text() satisfies $s = $a))
                                      ) then 1 else 0', 'int') = 1
                     )
), c as (  -- cast back to xml
    select cast(companies as xml) as companies
          ,cast(publishers as xml) as publishers
          ,groupid
      from b
)
select Co.company.value('(./text())[1]', 'varchar') as company
      ,Pu.publisher.value('(./text())[1]', 'varchar') as publisher
      ,c.groupid
  from c
       cross apply companies.nodes('/c') as Co(company)
       cross apply publishers.nodes('/p') as Pu(publisher)
 where exists(select 1 from Table1 t -- restrict to only the combinations that exist in the source
               where t.company = Co.company.value('(./text())[1]', 'varchar')
                 and t.publisher = Pu.publisher.value('(./text())[1]', 'varchar')
             )

Набор компаний и набор издателей хранятся в XML-полях на промежуточных этапах, и существует некоторое литье между xml и nvarchar, необходимое из-за некоторых ограничений SQL Server (например, неспособность группировать или использовать distinct на столбцах XML.

Ответ 6

Бит поздно для вызова, и поскольку SQLFiddle, похоже, работает с банкоматом, мне придется угадать ваши структуры данных. Тем не менее, это казалось забавным вызовом (и это было =), поэтому вот что я сделал из него:

Настройка:

IF OBJECT_ID('t_link') IS NOT NULL DROP TABLE t_link
IF OBJECT_ID('t_company') IS NOT NULL DROP TABLE t_company
IF OBJECT_ID('t_publisher') IS NOT NULL DROP TABLE t_publisher
IF OBJECT_ID('tempdb..#link_A') IS NOT NULL DROP TABLE #link_A
IF OBJECT_ID('tempdb..#link_B') IS NOT NULL DROP TABLE #link_B
GO

CREATE TABLE t_company ( company_id     int IDENTITY(1, 1) NOT NULL PRIMARY KEY,
                         company_name   varchar(100) NOT NULL)

GO 

CREATE TABLE t_publisher (publisher_id     int IDENTITY(1, 1) NOT NULL PRIMARY KEY,
                          publisher_name   varchar(100) NOT NULL)

CREATE TABLE t_link (company_id int NOT NULL FOREIGN KEY (company_id) REFERENCES t_company (company_id),
                     publisher_id int NOT NULL FOREIGN KEY (publisher_id) REFERENCES t_publisher (publisher_id),
                                PRIMARY KEY (company_id, publisher_id),
                     group_id int NULL
                             )
GO

-- example content


-- ROW   GROUPID     Company     Publisher
--1     1           A           Y
--2     1           A           X
--3     1           B           Y
--4     1           B           Z
--5     2           C           W
--6     2           C           P
--7     2           D           W


INSERT t_company (company_name) VALUES ('A'), ('B'), ('C'), ('D')
INSERT t_publisher (publisher_name) VALUES ('X'), ('Y'), ('Z'), ('W'), ('P')

INSERT t_link (company_id, publisher_id)
SELECT company_id, publisher_id
  FROM t_company, t_publisher
 WHERE (company_name = 'A' AND publisher_name = 'Y')
    OR (company_name = 'A' AND publisher_name = 'X')
    OR (company_name = 'B' AND publisher_name = 'Y')
    OR (company_name = 'B' AND publisher_name = 'Z')
    OR (company_name = 'C' AND publisher_name = 'W')
    OR (company_name = 'C' AND publisher_name = 'P')
    OR (company_name = 'D' AND publisher_name = 'W')




GO

/*
-- volume testing

TRUNCATE TABLE t_link
DELETE t_company
DELETE t_publisher


DECLARE @company_count   int = 1000,
        @publisher_count int = 450,
        @links_count     int = 800


INSERT t_company (company_name)
SELECT company_name    = Convert(varchar(100), NewID())
  FROM master.dbo.fn_int_list(1, @company_count) 

UPDATE STATISTICS t_company

INSERT t_publisher (publisher_name)
SELECT publisher_name  = Convert(varchar(100), NewID())
  FROM master.dbo.fn_int_list(1, @publisher_count) 

UPDATE STATISTICS t_publisher

-- Random links between the companies & publishers

DECLARE @count int
SELECT @count = 0

WHILE @count < @links_count
    BEGIN

        SELECT TOP 30 PERCENT row_id = IDENTITY(int, 1, 1), company_id = company_id + 0
          INTO #link_A
          FROM t_company
         ORDER BY NewID()

        SELECT TOP 30 PERCENT row_id = IDENTITY(int, 1, 1), publisher_id = publisher_id + 0
          INTO #link_B
          FROM t_publisher
         ORDER BY NewID()

        INSERT TOP (@links_count - @count) t_link (company_id, publisher_id)
        SELECT A.company_id,
               B.publisher_id
          FROM #link_A A
          JOIN #link_B B
            ON A.row_id = B.row_id
         WHERE NOT EXISTS ( SELECT *
                              FROM t_link old
                             WHERE old.company_id   = A.company_id
                               AND old.publisher_id = B.publisher_id)

        SELECT @count = @count + @@ROWCOUNT

        DROP TABLE #link_A
        DROP TABLE #link_B    
    END

*/

Фактическая группировка:

IF OBJECT_ID('tempdb..#links') IS NOT NULL DROP TABLE #links
GO

-- apply grouping

-- init
SELECT row_id = IDENTITY(int, 1, 1), 
       company_id,
       publisher_id,
       group_id = 0
  INTO #links
  FROM t_link

-- don't see an index that would be actually helpful here right-away, using row_id to avoid HEAP
CREATE CLUSTERED INDEX idx0 ON #links (row_id)
--CREATE INDEX idx1 ON #links (company_id)   
--CREATE INDEX idx2 ON #links (publisher_id)

UPDATE #links
   SET group_id = row_id


-- start grouping
WHILE @@ROWCOUNT > 0
    BEGIN  
        UPDATE #links
           SET group_id = new_group_id
          FROM #links upd
          CROSS APPLY (SELECT new_group_id = Min(group_id)
                         FROM #links new
                        WHERE new.company_id   = upd.company_id
                           OR new.publisher_id = upd.publisher_id 
                                     ) x
        WHERE upd.group_id > new_group_id

        -- select * from #links
    END


-- remove 'holes'
UPDATE #links
   SET group_id = (SELECT COUNT(DISTINCT o.group_id) 
                          FROM #links o
                         WHERE o.group_id <= upd.group_id)
  FROM #links upd

GO

UPDATE t_link
   SET group_id = new.group_id
  FROM t_link upd
  LEFT OUTER JOIN #links new
               ON new.company_id = upd.company_id
              AND new.publisher_id = upd.publisher_id

GO    
SELECT row = ROW_NUMBER() OVER (ORDER BY group_id, company_name, publisher_name),
       l.group_id,
       c.company_name, -- c.company_id,
       p.publisher_name -- , p.publisher_id
 from t_link l
 JOIN t_company c
   ON l.company_id = c.company_id
 JOIN t_publisher p 
   ON p.publisher_id = l.publisher_id
 ORDER BY 1

На первый взгляд этот подход еще не был опробован кем-либо еще, интересно посмотреть, как это можно сделать разными способами... (предпочитают не читать их заранее, так как это испортит головоломку =)

Результаты выглядят так, как ожидалось (насколько я понимаю требования и пример), и производительность не слишком убогая, хотя нет реального указания на количество записей, над которыми это должно работать; не уверен, как он будет масштабироваться, но не ожидайте слишком много проблем...