проблема рекурсивного запроса - получение кластера направленных соединений

Question

Пытаясь не выбирать одно и то же соединение несколько раз, я пытался использовать условие charindex () = 0 следующим образом:

WITH Cluster(calling_party, called_party, link_strength, Path)
AS
(SELECT
    calling_party,
    called_party,
    link_strength,
    CONVERT(varchar(max), calling_party + '.' + called_party) AS Path
FROM
    monthly_connections_test
WHERE
    link_strength > 0.1 AND
    calling_party = 'b'
UNION ALL
SELECT
    mc.calling_party,
    mc.called_party,
    mc.link_strength,
    CONVERT(varchar(max), cl.Path + '.' + mc.calling_party + '.' + mc.called_party) AS Path
FROM
    monthly_connections_test mc
INNER JOIN Cluster cl ON
    (
        mc.called_party = cl.called_party OR
        mc.called_party = cl.calling_party
    ) AND
    (
        CHARINDEX(cl.called_party + '.' + mc.calling_party, Path) = 0 AND
        CHARINDEX(cl.called_party + '.' + mc.called_party, Path) = 0
    )
WHERE
    mc.link_strength > 0.1
)
SELECT
    calling_party,
    called_party,
    link_strength,
    Path
FROM
    Cluster OPTION (maxrecursion 30000)

Условие, однако, не выполняет свое назначение, поскольку несколько строк выбираются несколькораз.

Фактическая цель здесь - получить весь кластер соединений, к которому принадлежит выбранный пользователь (в примере пользователя b).

Edit1:

Я попытался изменить запрос следующим образом:

With combined_users AS
 (SELECT calling_party CALLING, called_party CALLED, link_strength FROM dbo.monthly_connections_test WHERE link_strength > 0.1),
 related_users1 AS
 (
 SELECT c.CALLING, c.CALLED, c.link_strength, CONVERT(varchar(max), '.' + c.CALLING + '.' + c.CALLED + '.') path from combined_users c where CALLING = 'a1'
 UNION ALL
 SELECT c.CALLING, c.CALLED, c.link_strength,
    convert(varchar(max),r.path  + c.CALLED + '.') path 
        from combined_users c 
        join related_users1 r 
        ON (c.CALLING = r.CALLED) and CHARINDEX(c.CALLING + '.' + c.CALLED + '.', r.path)= 0 

        ),
related_users2 AS
(
SELECT c.CALLING, c.CALLED, c.link_strength, CONVERT(varchar(max), '.' + c.CALLING + '.' + c.CALLED + '.') path from combined_users c where CALLED = 'a1'
UNION ALL
 SELECT c.CALLING, c.CALLED, c.link_strength,
    convert(varchar(max),r.path  + c.CALLING + '.') path 
        from combined_users c 
        join related_users2 r 
        ON c.CALLED = r.CALLING and CHARINDEX('.' + c.CALLING + '.' + c.CALLED, r.path)= 0
)
        SELECT CALLING, CALLED, link_strength, path FROM
        (SELECT CALLING, CALLED, link_strength, path FROM related_users1 UNION SELECT CALLING, CALLED, link_strength, path FROM related_users2) r OPTION (MAXRECURSION 30000)

Чтобы проверить запрос, я создал кластер ниже:

Запросвыше вернулась следующая таблица:

a1  a2  1.0000000   .a1.a2.
a11 a13 1.0000000   .a12.a1.a13.a11.
a12 a1  1.0000000   .a12.a1.
a13 a12 1.0000000   .a12.a1.a13.
a14 a13 1.0000000   .a12.a1.a13.a14.
a15 a14 1.0000000   .a12.a1.a13.a14.a15.
a2  a10 1.0000000   .a1.a2.a10.
a2  a3  1.0000000   .a1.a2.a3.
a3  a4  1.0000000   .a1.a2.a3.a4.
a3  a6  1.0000000   .a1.a2.a3.a6.
a4  a8  1.0000000   .a1.a2.a3.a4.a8.
a4  a9  1.0000000   .a1.a2.a3.a4.a9.

Запрос явно возвращает соединения с выбранным узлом и соединения в противоположном направлении.Проблема заключается в смене направления: например, соединения a7, a4 и a11, a10 не выбраны, поскольку направление изменяется (относительно начального узла).

Кто-нибудь знает, как изменить запрос в порядкевключить все соединения?

Спасибо

Answer 1

Хорошо, здесь нужно обсудить несколько вещей.

В общем, у меня есть PostgreSQL, так что все это сделано с этим;я пытаюсь использовать только стандартный SQL, поэтому с SQL Server это тоже должно работать.

Во-первых, если вас интересуют только вызовы с мощностью ссылки более 0,1, скажем:

-- like calls, but only strong enough to be interesting
create view strong_calls (calling_party, called_party, link_strength)
as (
  select calling_party, called_party, link_strength
  from monthly_connections_test
  where link_strength > 0.1
);

И теперь мы будем говорить в терминах этой таблицы.

Во-вторых, вы говорите:

Фактическая цель здесь - получить весь кластер.соединений, к которым принадлежит выбранный пользователь (в примере пользователя b).

Если это правда, почему вы вычисляете путь?Если вы просто хотите узнать набор соединений, вы можете сделать следующее:

with recursive cluster (calling_party, called_party, link_strength)
as (
  (
    select calling_party, called_party, link_strength
    from strong_calls
    where calling_party = 'b'
  )
  union
  (
    select c.calling_party, c.called_party, c.link_strength
    from cluster this, strong_calls c
    where c.calling_party = this.called_party
    or c.called_party = this.calling_party
  )
)
select *
from cluster;

В-третьих, возможно, вы действительно не хотите находить, какие соединения находятся в кластере, вы хотите узнать, какие люди находятся вкластер, и какой кратчайший путь к ним от цели.В этом случае вы можете сделать:

with recursive cluster (party, path)
as (
  select cast('b' as character varying), cast('b' as character varying)
  union
  (
    select (case
      when this.party = c.calling_party then c.called_party
      when this.party = c.called_party then c.calling_party
    end), (this.path || '.' || (case
      when this.party = c.calling_party then c.called_party
      when this.party = c.called_party then c.calling_party
    end))
    from cluster this, strong_calls c
    where (this.party = c.calling_party and position(c.called_party in this.path) = 0)
    or (this.party = c.called_party and position(c.calling_party in this.path) = 0)
  )
)
select party, path
from cluster
where not exists (
  select *
  from cluster c2
  where cluster.party = c2.party
  and (
    char_length(cluster.path) > char_length(c2.path)
    or (char_length(cluster.path) = char_length(c2.path)) and (cluster.path > c2.path)
  )
)
order by party, path;

Как видите, вы были на верном пути.

Если вы действительно хотите получить список всех вызовов вкластер, с путями, тогда я вернусь к вам!

РЕДАКТИРОВАТЬ: имейте в виду, что запросы, которые не создают пути, будут иметь характеристики производительности, очень отличающиеся от тех, которые делают.Грубо говоря, запросы без пути будут выполнять O (n) работу (вероятно, примерно за O (log n) шагов итерации), потому что они посещают каждый узел в кластере, но шаги построения пути сделают гораздо больше - O (н!) может быть?- потому что они должны посетить каждый путь через график.Вы будете в порядке, если кластеры будут такими же большими, как в ваших примерах, но если они будут намного больше, вы можете обнаружить, что время выполнения является чрезмерно большим.

Answer 2

Чтобы ответить на ваш отредактированный вопрос, если вы хотите игнорировать направленность ссылок, попробуйте:

create view symmetric_users (calling_party, called_party, link_strength)
as (
  select calling_party, called_party, link_strength from monthly_connections_test
  union
  select called_party , calling_party, link_strength from monthly_connections_test
)

Тогда укажите ваш запрос на это.

Если у вас есть пользователи, которые звонят друг другу, у вас будет две строки для каждой заказанной пары пользователей. Вы должны быть в состоянии отфильтровать их, выбрав более сильный.

Answer 3

charindex ('b.d', 'bcdb') = 0, потому что есть 'c.'между

Легче читать:

WITH cluster(calling_party, called_party, link_strength, PATH) 
     AS (SELECT calling_party, 
                called_party, 
                link_strength, 
                CONVERT(VARCHAR(MAX), calling_party + '.' + called_party) AS 
                PATH 
         FROM   monthly_connections_test 
         WHERE  link_strength > 0.1 
                AND calling_party = 'b' 
         UNION ALL 
         SELECT mc.calling_party, 
                mc.called_party, 
                mc.link_strength, 
                CONVERT(VARCHAR(MAX), cl.PATH + '.' + mc.calling_party + '.' + 
                mc.called_party) 
                AS PATH 
         FROM   monthly_connections_test mc 
                INNER JOIN cluster cl 
                  ON ( mc.called_party = cl.called_party 
                        OR mc.called_party = cl.calling_party ) 
                     AND ( Charindex(cl.called_party + '.' + mc.calling_party, 
                           PATH) 
                           = 0 
                           AND Charindex(cl.called_party + '.' + 
                               mc.called_party, 
                               PATH) 
                               = 
                               0 ) 
         WHERE  mc.link_strength > 0.1) 
SELECT calling_party, 
       called_party, 
       link_strength, 
       PATH 
FROM   cluster 
OPTION (MAXRECURSION 30000)