0

На карте есть метки, при этом координаты не берем в расчет, будет объединение по имени. Между метками свои связи, т.е. сущность и в БД выглядит как метка1-метка2. Нужно присвоить одинаковую группу тем строкам в таблице, у которых совпадает метка с левой или правой стороны, т.е. это как объединить отрезки в одну группу. В исходных данных real_group проставлена руками, ее стремлюсь получить в расчетах. Исходные данные

id mark_A mark_B real_group
10 метка_1 метка_2 1
11 метка_3 метка_4 2
12 метка_3 метка_5 2
13 метка_4 метка_3 2
14 метка_5 метка_6 2
15 метка_7 метка_3 2
16 метка_7 метка_18 2
17 метка_7 метка_19 2
18 метка_8 метка_9 3
19 метка_10 метка_11 3
20 метка_10 метка_8 3
21 метка_12 метка_13 4
22 метка_14 метка_15 5
23 метка_16 метка_17 6

SQL-код:

drop table if exists #all_marks;
create table #all_marks (id int, mark_A varchar(20), mark_B varchar(30), real_group int);
insert into #all_marks (id, mark_A, mark_B, real_group) values 
(10, 'метка_1', 'метка_2', 1),
(11, 'метка_3', 'метка_4', 2),
(12, 'метка_3', 'метка_5', 2),
(13, 'метка_4', 'метка_3', 2),
(14, 'метка_5', 'метка_6', 2),
(15, 'метка_7', 'метка_3', 2),
(16, 'метка_8', 'метка_9', 3),
(17, 'метка_10', 'метка_11', 3),
(18, 'метка_10', 'метка_8', 3),
(19, 'метка_12', 'метка_13', 4),
(20, 'метка_14', 'метка_15', 5),
(21, 'метка_16', 'метка_17', 6);

with all_marks_with_rank as (
    select *, DENSE_RANK() over(order by mark_A) RankedGroup
    from #all_marks
)
, all_marks_with_group as (select distinct
    al.*, 
    case 
        when (a.mark_A is not null and a.RankedGroup < al.RankedGroup) then a.RankedGroup
        when (b.mark_B is not null and b.RankedGroup < al.RankedGroup) then b.RankedGroup
        else al.RankedGroup
    end grouped
from all_marks_with_rank al
left outer join all_marks_with_rank a on a.mark_A = al.mark_B
left outer join all_marks_with_rank b on b.mark_B = al.mark_A
)
select *,
    DENSE_RANK() over (order by grouped) group_result
from all_marks_with_group

group_result (именно по количеству одинаковых связей, сама цифра не важна) совпадает везде, кроме 16 и 17 ID (метки 7-18 и 18-19), хотя по логике они должны быть в группе 2. Почему не пойму, может есть какое-то другое решение?

Дополнение: вот такие данные получаются после выполнения скрипта, мне нужно, чтобы group_result у 16 и 17 id совпадал с group_result у ID c 11 по 15, т.к. метка_7 уже есть у ID 15, а метка_18 общая у 16 и 17 ID, ну т.е. есть связь. (извините за сумбур, вечереет)

id mark_A mark_B real_group RankedGroup grouped group_result
10 метка_1 метка_2 1 1 1 1
18 метка_8 метка_9 3 11 2 2
19 метка_10 метка_11 3 2 2 2
20 метка_10 метка_8 3 2 2 2
21 метка_12 метка_13 4 3 3 3
22 метка_14 метка_15 5 4 4 4
23 метка_16 метка_17 6 5 5 5
16 метка_7 метка_18 2 10 6 6
17 метка_18 метка_19 2 6 6 6
11 метка_3 метка_4 2 7 7 7
12 метка_3 метка_5 2 7 7 7
13 метка_4 метка_3 2 8 7 7
14 метка_5 метка_6 2 9 7 7
15 метка_7 метка_3 2 10 7 7
0

2 ответа 2

2

В общем виде, Ваш метод, думаю, не будет корректно работать если в real_group есть пути длиннее 3-х отрезков.
Пример решения через рекурсию. Мах глубина рекурсии - мах длина пути в данных.

with segments as ( --все отрезки являются началом построения неориентированного графа
    select id,mark_A,mark_B,real_group
        ,cast(concat('[',id,']') as varchar(max)) s1Path
    from #all_marks t1
)
,rGroup as (-- соберем графы, включающие начальные отрезки (для каждого id)
  select id id0  -- Ид, для которого собриаем граф
      , 1 n  --номер шага рекурсии, для инфо
      ,id, mark_A, mark_B, real_group -- в качестве первого шага - сам этот отрезок
      , cast(s1Path as varchar(max)) grPath -- пройденный путь по графу
  from segments
  union all -- все связанные отрезки, рекурсивно
  select r.id0
       ,n+1 n
       , a.id, a.mark_A, a.mark_B, a.real_group   -- следующий отрезок
      , concat(r.grPath,'>',a.s1Path) grPath  --список пройденных отрезков по пути
  from rGroup r inner join  segments a on  
      (a.mark_A=r.mark_A )  or (a.mark_A=r.mark_B ) 
   or (a.mark_B=r.mark_A )  or (a.mark_B=r.mark_B )  
  where  charindex(a.s1Path,r.grPath)<1 -- пока не наткнемся на пройденный отрезок
)
,t2 as( -- исключим дубли для каждого пути
select id0,id
from rGroup
group by id0,id
  )
,t3 as(
select id0,string_agg(id,',')within group(order by id) idPathOrdered -- весь граф
from t2 
group by id0
)
select *, dense_rank()over(order by idPathOrdered) calcGr
from t3 order by id0
option(maxrecursion 100)

Пример здесь

4
  • 1
    Большое спасибо! Все работает, немного подправил код под версию 2016: 1 ...,t3 as( select distinct id0, STUFF((SELECT ',' + cast(t22.id as varchar(max)) from t2 t22 where t2.id0 = t22.id0 order by t22.id FOR XML PATH(''),TYPE ).value('.','varchar(MAX)') ,1,1,'' ) idPathOrdered -- весь граф from t2 group by id0, id ) select *, dense_rank()over(order by idPathOrdered) calcGr from t3 order by id0 option(maxrecursion 100)
    – aford
    16 янв в 10:21
  • Единственный минус - на больших объемах данных очень долго работает, даже с индексами
    – aford
    16 янв в 12:50
  • Да, что с рекурсией что с множественными join, будет работать долго. XML_PATH по сравнению со STRING_AGG - также очень долго. Сможете попробовать на сопоставимом объеме данных сравнить XML PATH и STRING_AGG ? Было бы интересно.
    – ValNik
    16 янв в 14:00
  • К сожалению, не смогу сравнить, т.к. установлена студия 2016 и нет возможности обновить. Но стоит чуть прибавить данных - падает скорость (20 маркеров - 30 секунд, 30 и выше - не хватало терпения ждать). Скорее всего придется искать другие варианты решения задачи, но зато столкнулся с рекурсией в sql, не считаю зря потраченным время
    – aford
    16 янв в 14:43
0

Нашел решение с подробным описанием

@ValNik, спасибо за наводку на рекурсию и неориентированные графы!

drop table if exists #all_marks;
create table #all_marks (id int, mark_A varchar(20), mark_B varchar(20), real_group int);
insert into #all_marks (id, mark_A, mark_B, real_group) values 
(10, 'метка_1', 'метка_2', 1), (11, 'метка_3', 'метка_4', 2), (12, 'метка_3', 'метка_5', 2), (13, 'метка_4', 'метка_3', 2), (14, 'метка_5', 'метка_6', 2), (15, 'метка_7', 'метка_3', 2), (16, 'метка_7', 'метка_18', 2)
,(17, 'метка_18', 'метка_19', 2), (18, 'метка_8', 'метка_9', 3), (19, 'метка_10', 'метка_11', 3), (20, 'метка_10', 'метка_8', 3), (21, 'метка_12', 'метка_13', 4), (22, 'метка_14', 'метка_15', 5), (23, 'метка_16', 'метка_17', 6)
,(24, 'метка_1', 'метка_2', 1), (25, 'метка_3', 'метка_4', 2), (26, 'метка_3', 'метка_5', 2), (27, 'метка_4', 'метка_3', 2), (28, 'метка_5', 'метка_6', 2)
,(29, 'метка_1', 'метка_152', 1), (30, 'метка_152', 'метка_1', 1), (31, 'метка_152', 'метка_300', 1), (32, 'метка_200', 'метка_250', 1), (33, 'метка_250', 'метка_152', 1);

with marksOneLine as 
(
    select mark_A as mark from #all_marks
    union
    select mark_B as mark from #all_marks
)
, marksPairs as
(
    select mark_A, mark_B from #all_marks where mark_A <> mark_B
    union
    select mark_B as mark_A, mark_A as mark_B from #all_marks where mark_A <> mark_B
)
, marksRecursive as
(
    select
        cast(marksOneLine.mark as varchar(8000)) as anchorMark
        , mark_A
        , mark_B
        , cast(',' + mark_A + ',' + mark_B + ',' as varchar(8000)) as markPath
        , 1 as lvl
    from 
        marksPairs
        inner join marksOneLine on marksOneLine.mark = marksPairs.mark_A
    union all
    select
        marksRecursive.anchorMark
        , marksPairs.mark_A
        , marksPairs.mark_B
        , cast(marksRecursive.markPath + marksPairs.mark_B + ',' as varchar(8000)) as markPath
        , marksRecursive.lvl + 1 as lvl
    from marksPairs
    inner join marksRecursive on marksRecursive.mark_B = marksPairs.mark_A
    where marksRecursive.markPath not like cast ('%,' + marksPairs.mark_B + ',%' as varchar(8000))
)
, marksRecursionResult as
(
    select anchorMark, mark_A, mark_B
    from marksRecursive
)
, marksCleanResult as
(
    select anchorMark, mark_A as mark from marksRecursionResult
    union
    select anchorMark, mark_B as mark from marksRecursionResult
)
, marksResult as 
(
    select
        marksOneLine.mark
        , case when CA_Data.XML_Value is null then marksOneLine.mark else CA_Data.XML_Value end as groupMembers
        , DENSE_RANK() over(order by case when CA_Data.XML_Value is null then marksOneLine.mark else CA_Data.XML_Value end) as groupId
    from 
        marksOneLine
        cross apply
        (
            select marksCleanResult.mark + ','
            from marksCleanResult
            where marksCleanResult.anchorMark = marksOneLine.mark
            order by marksCleanResult.mark for XML PATH(''), type
        ) as CA_XML(XML_VALUE)
        cross apply
        (
            select CA_XML.XML_VALUE.value('.', 'NVARCHAR(MAX)')
        ) as CA_Data(XML_VALUE)
    where
        marksOneLine.mark is not null
)
select a.*, r.groupId
from #all_marks a
join marksResult r on r.mark = a.mark_A
order by real_group

Пример

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.