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

Пример

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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