Извлечение семейств строк из связанных строк

У меня есть таблица связанных транзакций, похожая на следующую таблицу

+----+----+----+
| #  | A  | B  |
+----+----+----+
| 1  | 1  | 4  |
| 2  | 3  | 5  |
| 3  | 4  | 6  |
| 4  | 5  | 8  |
| 5  | 6  | 1  |
| 6  | 7  | 7  |
| 7  | 8  | 3  |
| 8  | 9  | 3  |
| 9  | 10 | 4  |
| 10 | 11 | 14 |
| 11 | 2  | 2  |
| 12 | 12 | 4  |
| 13 | 13 | 14 |
| 14 | 14 | 9  |
| 15 | 15 | 1  |
+----+----+----+

Числа в столбцах A и B представляют идентификаторы транзакций. Так, например, транзакция 1 связана с транзакцией 4 по некоторым критериям, транзакция 3 с транзакцией 5, транзакция 4 с транзакцией 6 и так далее.

Транзакции 2 и 7 не связаны ни с какой другой транзакцией, поэтому они являются самосвязанными.

То, что я хочу извлечь, - это семейства транзакций из этой таблицы. Поскольку tran 1 и 4 связаны, tran 4 и 6 связаны, tran 10 и 4 связаны и т. д., они входят в одно семейство транзакций - (1,4,6,10, 12,15).

Я хочу создать семейства транзакций с самым низким идентификатором транзакции, являющимся основной транзакцией. Так что в идеале вывод будет выглядеть так

+----+------+--------------+
| #  | Tran | Master_tran  |
+----+------+--------------+
| 1  | 1    | 1  |
| 2  | 3    | 3  |         
| 3  | 4    | 1  |
| 4  | 5    | 3  |
| 5  | 6    | 1  |
| 6  | 7    | 7  |
| 7  | 8    | 3  |
| 8  | 9    | 3  |
| 9  | 10   | 1  |
| 10 | 11   | 3  |
| 11 | 2    | 2  |
| 12 | 12   | 1  |
| 13 | 13   | 3  |
| 14 | 14   | 3  |
| 15 | 15   | 1  |
+----+------+----+

Я играл с самостоятельными соединениями.

SELECT     t1.a as x, 
           least (min(t1.b), min(t2.a)) as y  
FROM       test   t1 
LEFT JOIN  test   t2 on t2.b = t1.a  
GROUP BY   t1.a 
ORDER BY   t1.a asc

Этот код дает следующий вывод

+------+----+---+
| Col1 | X  | Y |
+------+----+---+
|    1 |  1 | 4 |
|    2 |  2 | 2 |
|    3 |  3 | 5 |
|    4 |  4 | 1 |
|    5 |  5 | 3 |
|    6 |  6 | 1 |
|    7 |  7 | 7 |
|    8 |  8 | 3 |
|    9 |  9 | 3 |
|   10 | 10 |   |
|   11 | 11 |   |
|   12 | 12 |   |
|   13 | 13 |   |
|   14 | 14 | 9 |
|   15 | 15 |   |
+------+----+---+

Я не уверен, что не так в моем коде. Может ли кто-нибудь указать мне в правильном направлении? Спасибо!


sql plsql listagg self-join
person Nicole    schedule 03.12.2015    source источник
comment
Поскольку вы никогда не знаете, какой длины будет цепочка, вы не можете использовать только одно самосоединение. Вам нужно столько самосоединений, сколько звеньев в цепочке. Это, очевидно, проблематично, потому что вы не знаете, сколько это времени. Одним из решений этого является использование рекурсивного запроса для постоянного самосоединения до тех пор, пока цепочка не закончится. Проблема в том, что у вас есть циклические ссылки, которые приведут к бесконечному циклу. Вам нужно будет решить эту проблему, исправив данные, чтобы они не зацикливались.   -  person Rabbit    schedule 04.12.2015
comment
Каково максимальное значение транса? Если он не такой большой, вы можете использовать рекурсивный запрос с битовой маской. Тогда вам не нужно беспокоиться о циклических ссылках. Под малым я подразумеваю ‹64 или около того.   -  person Rabbit    schedule 04.12.2015
comment
Благодарю за ваш ответ. Существует ~ 100 тыс. отдельных транзакций, поэтому значение tran превысит 64. Как я могу исправить данные, чтобы они не зацикливались?   -  person Nicole    schedule 04.12.2015
comment
Ну, может быть, ничего не исправить. Сначала я подумал, что это иерархические данные, но, возможно, это не так. Если это не иерархические данные, то ссылки, создающие петлю, сами по себе не являются неверными данными. Скорее, вам просто нужно найти способ убедиться, что вы не зацикливаетесь в своем рекурсивном запросе, возможно, сохраняя текущую строку пройденных значений.   -  person Rabbit    schedule 04.12.2015

Ответы (2)


arrow_upward
0
arrow_downward

в принципе, вам нужен оператор CONNECT BY для решения таких иерархических проблем. Хотя у вас есть циклические циклы, вам также понадобится предложение NOCYCLE, это устранит последнюю ссылку в цикле, и это нормально, поскольку эта ссылка никогда не будет частью ответа. У вас также есть ссылки в обоих направлениях (например, (13, 14) и (14, 9)), поэтому вы должны быть осторожны, включая это в свой запрос (дважды!).

WITH t_order
     AS (SELECT qt.qt_id, qt.qt_a, qt.qt_b, LEAST( qt.qt_a, qt.qt_b ) AS t_parent, GREATEST( qt.qt_a, qt.qt_b ) AS t_child
       FROM query_test qt
     UNION
     SELECT qb.qt_id, qb.qt_a, qb.qt_b, GREATEST( qb.qt_a, qb.qt_b ) AS t_parent, LEAST( qb.qt_a, qb.qt_b ) AS t_child
       FROM query_test qb)
, hier
  AS (SELECT     ps.qt_id
              , ps.qt_a
              , ps.qt_b
              , t_parent
              , t_child
              , LEVEL
              , CONNECT_BY_ROOT t_parent AS prev_tran
           FROM t_order ps
     CONNECT BY NOCYCLE PRIOR t_child = t_parent)
SELECT   hr.qt_id, hr.qt_a, MIN( hr.prev_tran ) AS master_tran
  FROM hier hr
GROUP BY hr.qt_id, hr.qt_a
ORDER BY hr.qt_id, hr.qt_a;

Это решит вашу проблему, но может работать очень медленно, если необходимо обработать эти 100 000 записей. Оператор SQL также становится трудным для понимания, если вам нужно объединить этот метод с множеством других столбцов. Для этого вы должны выделить все столбцы qt.qt и объединить их в последнем выборе.

WITH t_order
     AS (SELECT DISTINCT tran, root_tran
           FROM (SELECT LEAST( qt.qt_a, qt.qt_b ) AS tran, GREATEST( qt.qt_a, qt.qt_b ) AS root_tran
                   FROM query_test qt
                 UNION
                 SELECT GREATEST( qb.qt_a, qb.qt_b ) AS tran, LEAST( qb.qt_a, qb.qt_b ) AS root_tran
                   FROM query_test qb))
   , hier
     AS (SELECT DISTINCT tran, root_tran
           FROM (SELECT     tran, CONNECT_BY_ROOT root_tran AS root_tran
                       FROM t_order
                 CONNECT BY NOCYCLE PRIOR tran = root_tran)
          WHERE tran >= root_tran)
SELECT   qt.qt_id
       , qt.qt_a
       , MIN( LEAST( h1.root_tran, h2.root_tran ) ) AS master_tran
    FROM query_test qt
         INNER JOIN hier h1 ON qt.qt_a = h1.tran
         INNER JOIN hier h2 ON qt.qt_b = h2.tran
GROUP BY qt.qt_id, qt.qt_a
ORDER BY qt.qt_id, qt.qt_a;

Я не мог проверить это последнее утверждение.

person hendrik_at_geislersoftware    schedule 07.12.2015
comment
Эй, большое спасибо за ответ, он отлично работает с тестовым кодом. Однако, как вы упомянули, даже второй фрагмент кода требует много времени для реализации. Я запускал его в течение ~ 100 минут, прежде чем убить процесс. Есть ли способ сделать это быстрее? - person Nicole; 09.12.2015
comment
Да, но только столбцы A и B можно переставить с высокого на низкий. - person hendrik_at_geislersoftware; 11.12.2015
comment
Когда A гарантированно больше или равно B, наивысшее внутреннее соединение (h1) и функция LEAST не нужны. Это должно сократить примерно вдвое необходимое время. У меня есть идея для менее точного решения, я постараюсь опубликовать это позже. - person hendrik_at_geislersoftware; 11.12.2015

arrow_upward
0
arrow_downward

Возможно, я придумал другое решение.
Вместо использования оператора CONNECT BY вы также можете удвоить свои ссылки и удвоить их в любое время, когда это необходимо. Запрос на получение всех ссылок остается прежним, но за ним следует простой запрос на замену исходных ссылок всеми различными комбинациями двух ссылок.
Включая ссылку, образованную tran_a и tran_b, у вас есть 2 + 1 + 2 ссылки, поэтому вы можете найти пути длиной до 5 ссылок. Если это слишком коротко, вы вставляете идентичный подзапрос под предыдущим подзапросом, и теперь это 4 + 1 + 4, что составляет 9 ссылок. Как видите, максимальная длина пути удваивается для каждого добавленного подзапроса, что лишь незначительно увеличивает затраты на производительность.

Сначала запрос для проверки ваших демо-данных:

WITH double_0
     AS (SELECT DISTINCT root_tran, tran
           FROM ( SELECT LEAST( td_0.tran_a, td_0.tran_b ) AS root_tran
                       , GREATEST( td_0.tran_a, td_0.tran_b ) AS tran
                    FROM tran_demo td_0
                  UNION
                  SELECT GREATEST( qb.tran_a, qb.tran_b ) AS root_tran
                       , LEAST( qb.tran_a, qb.tran_b ) AS tran
                    FROM tran_demo qb ))
   , double_1
     AS (SELECT DISTINCT oa.root_tran, ob.tran
           FROM double_0 oa INNER JOIN double_0 ob ON oa.tran = ob.root_tran)
SELECT   td_1.td_id
       , td_1.tran_a
       , MIN( LEAST( d1.root_tran, d2.root_tran ) ) AS master_tran
    FROM tran_demo td_1
         INNER JOIN double_1 d1 ON td_1.tran_a = d1.tran
         INNER JOIN double_1 d2 ON td_1.tran_b = d2.tran
GROUP BY td_1.td_id, td_1.tran_a
ORDER BY td_1.td_id, td_1.tran_a;

Затем, как вы это измените:
Обратите внимание, что теперь вы запрашиваете double_2 в финальном запросе.

WITH double_0
     AS (SELECT DISTINCT root_tran, tran
           FROM ( SELECT LEAST( td_0.tran_a, td_0.tran_b ) AS root_tran
                       , GREATEST( td_0.tran_a, td_0.tran_b ) AS tran
                    FROM tran_demo td_0
                  UNION
                  SELECT GREATEST( qb.tran_a, qb.tran_b ) AS root_tran
                       , LEAST( qb.tran_a, qb.tran_b ) AS tran
                    FROM tran_demo qb ))
   , double_1
     AS (SELECT DISTINCT oa.root_tran, ob.tran
           FROM double_0 oa INNER JOIN double_0 ob ON oa.tran = ob.root_tran)
   , double_2
     AS (SELECT DISTINCT oa.root_tran, ob.tran
           FROM double_1 oa INNER JOIN double_0 ob ON oa.tran = ob.root_tran)
SELECT   td_1.td_id
       , td_1.tran_a
       , MIN( LEAST( d1.root_tran, d2.root_tran ) ) AS master_tran
    FROM tran_demo td_1
         INNER JOIN double_2 d1 ON td_1.tran_a = d1.tran
         INNER JOIN double_2 d2 ON td_1.tran_b = d2.tran
GROUP BY td_1.td_id, td_1.tran_a
ORDER BY td_1.td_id, td_1.tran_a;

Наконец, запрос, чтобы проверить, достаточно ли длины используемого вами пути: вы уже добавили следующий уровень и вычли текущий уровень.
Пока этот запрос не возвращает никаких строк, текущий запрос верен.

WITH double_0
     AS (SELECT DISTINCT root_tran, tran
           FROM ( SELECT LEAST( td_0.tran_a, td_0.tran_b ) AS root_tran
                       , GREATEST( td_0.tran_a, td_0.tran_b ) AS tran
                    FROM tran_demo td_0
                  UNION
                  SELECT GREATEST( qb.tran_a, qb.tran_b ) AS root_tran
                       , LEAST( qb.tran_a, qb.tran_b ) AS tran
                    FROM tran_demo qb ))
   , double_1
     AS (SELECT DISTINCT oa.root_tran, ob.tran
           FROM double_0 oa INNER JOIN double_0 ob ON oa.tran = ob.root_tran)
   , double_2
     AS (SELECT DISTINCT oa.root_tran, ob.tran
           FROM double_1 oa INNER JOIN double_0 ob ON oa.tran = ob.root_tran)
SELECT   td_1.tran_a
       , MIN( LEAST( d1.root_tran, d2.root_tran ) ) AS master_tran
    FROM tran_demo td_1
         INNER JOIN double_2 d1 ON td_1.tran_a = d1.tran
         INNER JOIN double_2 d2 ON td_1.tran_b = d2.tran
GROUP BY td_1.tran_a
MINUS
SELECT   td_2.tran_a
       , MIN( LEAST( d1.root_tran, d2.root_tran ) ) AS master_tran
    FROM tran_demo td_2
         INNER JOIN double_1 d1 ON td_2.tran_a = d1.tran
         INNER JOIN double_1 d2 ON td_2.tran_b = d2.tran
GROUP BY td_2.tran_a
ORDER BY tran_a;

Тестирование производительности вам придется провести самостоятельно. Я настроен оптимистично, пока подзапрос дешев и каждый раз эффективная длина пути удваивается. Рано или поздно это должно стать быстрее, чем предыдущее решение.
Кстати, здесь тоже работает замечание о сортировке исходных ссылок!
Пожалуйста, отметьте мой ответ, если он работает.

person hendrik_at_geislersoftware    schedule 11.12.2015