Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Транзитивное замыкание через T-SQL  [new]
Kew1
Member

Откуда:
Сообщений: 33
Всем здравствуйте.

Задача:
Есть таблица с парами значений. Необходимо дополнить её значениями, исходя из транзитивности оных. То есть, если x=y, а y=z, то x=z. Пары в таблице могут быть рефлективны, а могут и нет – тогда нужно дополнить набор, чтобы все пары были рефлективны. То есть, если есть x=y, то должна быть и y=x.

Я понимаю, что это можно сделать процедурно.
Но интересно, можно ли это сделать через T-SQL?

Попытался, но вижу, что неверно - не все варианты в результате...

WITH
t AS
  (SELECT 'x' AS a, 'y' AS b
   UNION ALL
   SELECT 'y' AS a, 'x' AS b
   UNION ALL 
   SELECT 'y' AS a, 'z' AS b
   UNION ALL 
   SELECT 'z' AS a, 'y' AS b
   UNION ALL 
   SELECT 'm' AS a, 'n' AS b
   UNION ALL 
   SELECT 'm' AS a, 'z' AS b),
 
coupled_reflective AS

  (SELECT t2.a, t2.b
   FROM t t1
   JOIN t t2 ON t1.a=t2.b
   AND t1.b!=t2.a),

reversive_coupled_reflective AS

  (SELECT t2.b, t2.a
   FROM t t1
   JOIN t t2 ON t1.a=t2.b
   AND t1.b!=t2.a),

rs AS

  (SELECT *
   FROM coupled_reflective
   UNION
   SELECT *
   FROM t
   EXCEPT
   SELECT *
   FROM reversive_coupled_reflective),

 cte AS

  (SELECT a, b
   FROM rs
   UNION ALL
   SELECT rs.b, cte.b
   FROM rs
   JOIN cte ON rs.a=cte.a
   AND rs.b!=cte.b),

 cte2 AS

  (SELECT a, b
   FROM rs
   UNION ALL
   SELECT rs.a, cte.a
   FROM rs
   JOIN cte ON rs.b=cte.b
   AND rs.a!=cte.a)



SELECT a, b FROM cte2
UNION
SELECT b, a FROM cte2
UNION
SELECT a, b FROM cte
UNION
SELECT b, a FROM cte
UNION
SELECT a, b FROM t
UNION
SELECT b, a FROM t
1 мар 17, 01:49    [20252787]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21249
Вот, для MySQL нарисовал, работает... разбирайся. Специально не стал в один запрос собирать.
+ MySQL Console Output
mysql> create table test(a char(1), b char(1));
Query OK, 0 rows affected (0.27 sec)

mysql>
mysql> insert into test (a, b)
    -> select 'x', 'y' union all
    -> select 'x', 'z' union all
    -> select 'y', 'z' union all
    -> select 'z', 'y' union all
    -> select 'a', 'b' union all
    -> select 'a', 'c' union all
    -> select 'q', 'w' ;
Query OK, 7 rows affected (0.08 sec)
Records: 7  Duplicates: 0  Warnings: 0

mysql>
mysql> create view chars
    -> as
    -> select a from test
    -> union
    -> select b from test ;
Query OK, 0 rows affected (0.07 sec)

mysql>
mysql> create view nchars
    -> as
    -> select t1.a, count(t2.a) num
    -> from chars t1, chars t2
    -> where t1.a >= t2.a
    -> group by t1.a ;
Query OK, 0 rows affected (0.04 sec)

mysql>
mysql> create view mnchars
    -> as
    -> select q1.a, min(q1.num) num
    -> from (
    -> select t1.a, least(t1.num, t2.num) num
    -> from test t0, nchars t1, nchars t2
    -> where t0.a = t1.a
    ->   and t0.b = t2.a
    -> group by t1.a
    -> union
    -> select t2.a, least(t1.num, t2.num) num
    -> from test t0, nchars t1, nchars t2
    -> where t0.a = t1.a
    ->   and t0.b = t2.a
    -> group by t2.a
    -> ) q1
    -> group by q1.a
    -> ;
Query OK, 0 rows affected (0.04 sec)

mysql>
mysql> select t1.a,t2.a
    -> from mnchars t1, mnchars t2
    -> where t1.num=t2.num
    ->   and t1.a != t2.a ;
+------+------+
| a    | a    |
+------+------+
| a    | b    |
| a    | c    |
| b    | a    |
| b    | c    |
| c    | a    |
| c    | b    |
| q    | w    |
| w    | q    |
| x    | y    |
| x    | z    |
| y    | x    |
| y    | z    |
| z    | x    |
| z    | y    |
+------+------+
14 rows in set (0.03 sec)
1 мар 17, 09:18    [20253090]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21249
PS. Функция LEAST возвращает наименьший из аргументов. Для MS SQL можно заменить на
CASE WHEN a<b THEN a ELSE b END
1 мар 17, 09:22    [20253109]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21249
PPS. Операцию, выполняемую в mnchars, надо зарекурсить для получения глобально минимального индекса. Сейчас она будет правильно работать только для веток длиной не более 3.
1 мар 17, 09:40    [20253169]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Kew1
Member

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

Во-первых, спасибо за ваше время.

Изначально я упросил вводную, в реальной задаче вместо литер - GUID. Хотя, сравнение GUID тоже работает. Хотя, вероятно, и медленней.
Спал мало - пока не могу понять, где нужно воткнуть рекурсию. Нужно время, чтобы понять, что тут происходит в принципе :)
1 мар 17, 10:17    [20253285]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Kew1
Member

Откуда:
Сообщений: 33
LEAST - это же не агрегатная функция, зачем там GROUP BY?

Переписал, чтобы работало на MS SQL, пока без предложенной рекурсии.

--create table #test (a char(1), b char(1))
--insert into #test
--   SELECT 'x' AS a, 'y' AS b
--   UNION ALL
--   SELECT 'y' AS a, 'x' AS b
--   UNION ALL 
--   SELECT 'y' AS a, 'z' AS b
--   UNION ALL 
--   SELECT 'z' AS a, 'y' AS b
--   --UNION ALL 
--   --SELECT 'm' AS a, 'n' AS b
--   UNION ALL 
--   SELECT 'm' AS a, 'z' AS b

with chars as
(
select a from #test
union
select b from #test
),

nchars as
(
select t1.a, count(t2.a) num
  from chars t1, chars t2
 where t1.a >= t2.a
 group by t1.a
),

mnchars  as
(
select q1.a, min(q1.num) num
from (
select t1.a, CASE WHEN t1.num<=t2.num THEN t1.num ELSE t2.num END num
from #test t0, nchars t1, nchars t2
where t0.a = t1.a
and t0.b = t2.a
--group by t1.a
union
select t2.a, CASE WHEN t1.num<=t2.num THEN t1.num ELSE t2.num END num
from #test t0, nchars t1, nchars t2
where t0.a = t1.a
and t0.b = t2.a
--group by t2.a
) q1
group by q1.a
)

select t1.a,t2.a
  from mnchars t1, mnchars t2
 where t1.num=t2.num
   and t1.a != t2.a


Результат озадачил (на моём наборе пар)... Где y-z, z-y, m-n -- пары из ещё заданного набора?

a	a
---------
z m
y x
x y
m z
1 мар 17, 10:42    [20253339]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21249
Kew1
Нужно время, чтобы понять, что тут происходит в принципе

Первая вьюшка просто собирает список всех возможных итемов.
Вторая их нумерует.
Tретья для каждого итема каждой пары берёт минимальный номер. Теоретически после неё все итемы одной группы (связанные парностью прямо или через итемы-посредники) должны получить одинаковый номер, равный минимальному из всех номеров итемов группы. И именно на этой стадии нужна рекурсия - потому как без неё каждый итем получит минимальный из номеров для себя, соседа и соседа соседа, но не дальше, а в реальности у тебя длина цепи соседей ничем не ограничена.
Ну и конечный запрос просто составляет все возможные пары из итемов одной группы.

Kew1
LEAST - это же не агрегатная функция, зачем там GROUP BY?
Да на автомате воткнул - сперва написал под MIN(LEAST), потом понял, что оно нафиг не надо из-за внешнего запроса (обёртывал позже), но убрал только MAX.

Kew1
Результат озадачил

Выведи для просмотра наборы записей, выдаваемые промежуточными CTE. Возможно, даже третью вьюшку для отладки подели на отдельные CTE-шки без вложенности.
1 мар 17, 11:20    [20253462]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Kew1
Member

Откуда:
Сообщений: 33
По-моему, не выйдет. Проблема в рекурсии, именно в ней нужно определить связность, насколько я понимаю.
2 мар 17, 12:30    [20257039]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 21249
Да выйдет, выйдет... пишут же на чистом SQL запросы для, скажем, поиска кратчайшего пути в графах... там тоже без рекурсии никуда. См. например тут.
2 мар 17, 13:34    [20257417]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Из соседнего форума
Guest
Kew1
Попытался, но вижу, что неверно - не все варианты в результате...

как-то все должно быть проще, видимо вы где-то запутались. Направление мысли вроде верно.

+ для оракла


Не нашел сходу в документации - как отрабатывает MS рекурсивные зацикливания. Если MS не умеет их обрабатывать, вполне возможно в вашем примере столько кажущихся мне не нужными операций - попытки избежать зацикливаний.

Kew1
То есть, если x=y, а y=z, то x=z. Пары в таблице могут быть рефлективны, а могут и нет – тогда нужно дополнить набор, чтобы все пары были рефлективны. То есть, если есть x=y, то должна быть и y=x.


Connected to Oracle Database 12c Enterprise Edition Release 12.1.0.2.0 

SQL> with
  2      t as
  3      (
  4          select 'x' as a, 'y' as b from dual   union all
  5          select 'y' as a, 'z' as b from dual union all
  6          select 'z' as a, 'a' as b from dual union all
  7          select 'x1' as a, 'y1' as b from dual
  8      ),
  9      rflx AS
 10      (
 11          select a, b from t
 12          union
 13          select b, a from t
 14      ),
 15      rec (a, b, lvl) as
 16      (
 17          select a, b, 1 from rflx
 18          union all
 19          select
 20              rec.a, rflx.b, lvl+1
 21          from
 22              rflx, rec
 23          where
 24              rec.b = rflx.a and
 25              rec.a != rflx.b
 26     )
 27     cycle a, b set cycled to 1 default 0
 28  select distinct
 29      a, b
 30  from rec
 31  /
A  B
-- --
z  a
y  a
a  x
a  z
x1 y1
y  x
y1 x1
z  y
x  z
z  x
x  a
x  y
y  z
a  y
14 rows selected

2 мар 17, 14:57    [20257721]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Из соседнего форума
Guest
Похоже MS не умеет останавливать рекурсию на зацикливаниях.
Можно ограничить глубину рекусрии.
Полагаю самый глубокий уровень рекурсии не должен превосходить количества уникальных узлов.
Конечно, в этом случае, у нас может добавится много оверхеда
+ для оракла

Connected to Oracle Database 12c Enterprise Edition Release 12.1.0.2.0 

SQL> with
  2      t as
  3      (
  4          select 'x' as a, 'y' as b from dual union all
  5          select 'y' as a, 'z' as b from dual union all
  6          select 'z' as a, 'a' as b from dual union all
  7          select 'a' as a, 'x' as b from dual union all
  8          select 'x1' as a, 'y1' as b from dual
  9      ),
 10      rflx AS
 11      (
 12          select a, b from t
 13          union
 14          select b, a from t
 15      ),
 16      rec (a, b, lvl) as
 17      (
 18          select a, b, 1 from rflx
 19          union all
 20          select
 21              rec.a, rflx.b, lvl+1
 22          from
 23              rflx, rec
 24          where
 25              rec.b = rflx.a and
 26              rec.a != rflx.b and
 27              rec.lvl <= (select count(distinct a) from rflx)
 28     )
 29     --cycle a, b set cycled to 1 default 0
 30  select distinct a, b from rec;
A  B
-- --
z  a
y  a
a  x
a  z
x1 y1
y  x
y1 x1
z  y
x  z
z  x
x  a
x  y
y  z
a  y
14 rows selected

2 мар 17, 15:53    [20257913]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
iap
Member

Откуда: Москва
Сообщений: 47144
Из соседнего форума
Похоже MS не умеет останавливать рекурсию на зацикливаниях.
Можно ограничить глубину рекусрии.
Кто же мешает накапливать пройденные узлы в строке с разделителями, например,
и по ходу дела проверять, был уже узел или ещё нет?
2 мар 17, 16:17    [20258054]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Dmitry V. Liseev
Member [заблокирован]

Откуда: Санкт-Петербург
Сообщений: 5489
Что-то я не уверен, что можно рекурсивно одним запросом. Там количество операций сильно растёт при увеличении количества рёбер в исходном графе. Можно быстро налететь на ограничение глубины рекурсии. Я делал циклом. Если есть ребро из A в B и из B в C, то смотрел, есть ли ребро из A в C. Если нет, добавлял. Так по всем рёбрам. В конце смотрю: удалось добавить хоть одно новое ребро? Если да, повторяем. И так до тех пор, пока очередной проход не показывает, что возможные варианты уже ранее были добавлены и ничего нового добавить не удалось.
2 мар 17, 16:34    [20258132]     Ответить | Цитировать Сообщить модератору
 Re: Транзитивное замыкание через T-SQL  [new]
Kew1
Member

Откуда:
Сообщений: 33
Не могу сейчас писать.
Спасибо за комментарии.
Вот реализация озвученного выше предложения.

http://stackoverflow.com/questions/42555799/find-all-possible-pairs-based-on-transitivity-via-t-sql
2 мар 17, 17:07    [20258304]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить