Oracle: разделите страны на N границ

Question

Я хотел бы получить все страны, разделенные N (1,2,3,4 ...) границами от указанной страны.

N также следует указывать.

Например, у меня есть таблица "border" и "country":

border | neighbor
-----------------
  FR   |   DE
  FR   |   IT
  IT   |   FR
  DE   |   FR
  DE   |   PL
  PL   |   DE
  DE   |   DK
  DK   |   DE


CODE COUNTRYNAME  
---- ---------
FR   France   
DE   Germany
RU   Russia   
IT   Italy
PL   Poland      
DK   Denmark

1. N = 2 & country =Франция

Если я хочу отделить страны, разделенные двумя границами от Франции, следует вернуть Польшу (FR -> DE -> PL) и Данию (FR -> DE -> DK)

N = 1 & страна = Франция

Если я хочу разделить страны на одну границу от Франции, следует вернуть Германию (FR -> DE) и Италию (FR -> IT).

Я могу изменить границы при необходимости.

Я попытался выполнить несколько иерархических запросов безуспешно.

Спасибо BR

Answer 1

Вы можете объединить соседей каждой страны в коллекцию, а затем использовать простой иерархический запрос для поиска (нециклических) путей:

SQL Fiddle

Настройка схемы Oracle 11g R2 :

create table borders (border char(2), neighbor char(2));

insert into borders values ('FR','DE');
insert into borders values ('FR','IT');
insert into borders values ('IT','FR');
insert into borders values ('DE','FR');
insert into borders values ('DE','PL');
insert into borders values ('PL','DE');
insert into borders values ('DE','DK');
insert into borders values ('DK','DE');
insert into borders values ('RU','PL');
insert into borders values ('PL','RU');
insert into borders values ('IT','CH');
insert into borders values ('FR','CH');
insert into borders values ('DE','CH');
insert into borders values ('CH','IT');
insert into borders values ('CH','FR');
insert into borders values ('CH','DE');

CREATE TYPE countrylist AS TABLE OF CHAR(2);

Запрос 1 :

WITH neighbors ( country, neighbors ) AS (
  SELECT border,
         CAST( COLLECT( neighbor ) AS COUNTRYLIST )
  FROM   borders
  GROUP BY border
)
SELECT SYS_CONNECT_BY_PATH( country, '->' ) AS path,
       CONNECT_BY_ROOT( country ) AS origin,
       country AS destination,
       LEVEL - 1 AS path_length
FROM   neighbors
WHERE  LEVEL - 1 = 4      -- Remove this to find paths of any length
START WITH country = 'FR' -- Remove this to start from any country
CONNECT BY NOCYCLE
       country MEMBER OF PRIOR neighbors

Результаты :

|                 PATH | ORIGIN | DESTINATION | PATH_LENGTH |
|----------------------|--------|-------------|-------------|
| ->FR->CH->DE->PL->RU |     FR |          RU |           4 |
| ->FR->IT->CH->DE->DK |     FR |          DK |           4 |
| ->FR->IT->CH->DE->PL |     FR |          PL |           4 |

Объяснить план :

-----------------------------------------------------------------------------------------------
| Id  | Operation                                  | Name    | Rows | Bytes | Cost | Time     |
-----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                           |         |   16 |   608 |    5 | 00:00:01 |
| * 1 |   FILTER                                   |         |      |       |      |          |
| * 2 |    CONNECT BY NO FILTERING WITH START-WITH |         |      |       |      |          |
|   3 |     VIEW                                   |         |   16 |   608 |    4 | 00:00:01 |
|   4 |      SORT GROUP BY                         |         |   16 |   128 |    4 | 00:00:01 |
|   5 |       TABLE ACCESS FULL                    | BORDERS |   16 |   128 |    3 | 00:00:01 |
-----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
------------------------------------------
* 1 - filter(LEVEL-1=4)
* 2 - filter("COUNTRY"MEMBER OFPRIOR "NEIGHBORS" AND "COUNTRY"='FR')

Запрос 2 Это позволит получить кратчайший путь (со связями) междупары стран:

WITH neighbors ( country, neighbors ) AS (
  SELECT border,
         CAST( COLLECT( neighbor ) AS COUNTRYLIST )
  FROM   borders
  GROUP BY border
)
SELECT path,
       origin,
       destination,
       path_length
FROM   (
  SELECT SYS_CONNECT_BY_PATH( country, '->' ) AS path,
         CONNECT_BY_ROOT( country ) AS origin,
         country AS destination,
         LEVEL - 1 AS path_length,
         RANK() OVER (
           PARTITION BY CONNECT_BY_ROOT( country ), country
           ORDER BY LEVEL ASC
         ) AS path_length_rank
  FROM   neighbors
  WHERE  LEVEL > 1
  CONNECT BY NOCYCLE
         country MEMBER OF PRIOR neighbors
  ORDER BY origin, destination
)
WHERE  path_length_rank = 1

Результаты :

|                 PATH | ORIGIN | DESTINATION | PATH_LENGTH |
|----------------------|--------|-------------|-------------|
|             ->CH->DE |     CH |          DE |           1 |
|         ->CH->DE->DK |     CH |          DK |           2 |
|             ->CH->FR |     CH |          FR |           1 |
|             ->CH->IT |     CH |          IT |           1 |
|         ->CH->DE->PL |     CH |          PL |           2 |
|     ->CH->DE->PL->RU |     CH |          RU |           3 |
|             ->DE->CH |     DE |          CH |           1 |
|             ->DE->DK |     DE |          DK |           1 |
|             ->DE->FR |     DE |          FR |           1 |
|         ->DE->FR->IT |     DE |          IT |           2 |
|         ->DE->CH->IT |     DE |          IT |           2 |
|             ->DE->PL |     DE |          PL |           1 |
|         ->DE->PL->RU |     DE |          RU |           2 |
|         ->DK->DE->CH |     DK |          CH |           2 |
|             ->DK->DE |     DK |          DE |           1 |
|         ->DK->DE->FR |     DK |          FR |           2 |
|     ->DK->DE->FR->IT |     DK |          IT |           3 |
|     ->DK->DE->CH->IT |     DK |          IT |           3 |
|         ->DK->DE->PL |     DK |          PL |           2 |
|     ->DK->DE->PL->RU |     DK |          RU |           3 |
|             ->FR->CH |     FR |          CH |           1 |
|             ->FR->DE |     FR |          DE |           1 |
|         ->FR->DE->DK |     FR |          DK |           2 |
|             ->FR->IT |     FR |          IT |           1 |
|         ->FR->DE->PL |     FR |          PL |           2 |
|     ->FR->DE->PL->RU |     FR |          RU |           3 |
|             ->IT->CH |     IT |          CH |           1 |
|         ->IT->FR->DE |     IT |          DE |           2 |
|         ->IT->CH->DE |     IT |          DE |           2 |
|     ->IT->CH->DE->DK |     IT |          DK |           3 |
|     ->IT->FR->DE->DK |     IT |          DK |           3 |
|             ->IT->FR |     IT |          FR |           1 |
|     ->IT->CH->DE->PL |     IT |          PL |           3 |
|     ->IT->FR->DE->PL |     IT |          PL |           3 |
| ->IT->FR->DE->PL->RU |     IT |          RU |           4 |
| ->IT->CH->DE->PL->RU |     IT |          RU |           4 |
|         ->PL->DE->CH |     PL |          CH |           2 |
|             ->PL->DE |     PL |          DE |           1 |
|         ->PL->DE->DK |     PL |          DK |           2 |
|         ->PL->DE->FR |     PL |          FR |           2 |
|     ->PL->DE->CH->IT |     PL |          IT |           3 |
|     ->PL->DE->FR->IT |     PL |          IT |           3 |
|             ->PL->RU |     PL |          RU |           1 |
|     ->RU->PL->DE->CH |     RU |          CH |           3 |
|         ->RU->PL->DE |     RU |          DE |           2 |
|     ->RU->PL->DE->DK |     RU |          DK |           3 |
|     ->RU->PL->DE->FR |     RU |          FR |           3 |
| ->RU->PL->DE->FR->IT |     RU |          IT |           4 |
| ->RU->PL->DE->CH->IT |     RU |          IT |           4 |
|             ->RU->PL |     RU |          PL |           1 |

Объяснить план :

---------------------------------------------------------------------------------------
| Id  | Operation                          | Name    | Rows | Bytes | Cost | Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                   |         |   16 | 32576 |    6 | 00:00:01 |
| * 1 |   VIEW                             |         |   16 | 32576 |    6 | 00:00:01 |
|   2 |    SORT ORDER BY                   |         |   16 |   608 |    6 | 00:00:01 |
| * 3 |     WINDOW SORT PUSHED RANK        |         |   16 |   608 |    6 | 00:00:01 |
| * 4 |      FILTER                        |         |      |       |      |          |
| * 5 |       CONNECT BY WITHOUT FILTERING |         |      |       |      |          |
|   6 |        VIEW                        |         |   16 |   608 |    4 | 00:00:01 |
|   7 |         SORT GROUP BY              |         |   16 |   128 |    4 | 00:00:01 |
|   8 |          TABLE ACCESS FULL         | BORDERS |   16 |   128 |    3 | 00:00:01 |
---------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
------------------------------------------
* 1 - filter("PATH_LENGTH_RANK"=1)
* 3 - filter(RANK() OVER ( PARTITION BY ANY,"COUNTRY" ORDER BY LEVEL)<=1)
* 4 - filter(LEVEL>1)
* 5 - filter("COUNTRY"MEMBER OFPRIOR "NEIGHBORS")

Answer 2

Ваша таблица BORDERS содержит взаимные отношения (например, FR->DE, DE->FR).Это означает, что вам нужно обрабатывать циклы.Это совсем не просто, потому что вы хотите избежать FR->DE->PL->DE при трех степенях разделения.

Здесь у меня есть рекурсивное предложение WITH (то есть Oracle 11gR2 или новее), которое делает это.

with hqry (path, nghbr, prev_bdr, root_bdr, lvl) as (
    select b.border
            , b.neighbor
            , b.border
            , b.border
            , 1 as lvl
    from borders b
    where b.border = 'FR'
    union all
    select hqry.path || '->' || b.border
           , b.neighbor
           , hqry.nghbr
           , hqry.root_bdr
           , hqry.lvl + 1
    from hqry
         join borders b on b.border = hqry.nghbr
    where b.neighbor != hqry.root_bdr
    and  b.neighbor != hqry.prev_bdr
    and hqry.lvl < 3  -- this is a nasty kludge, with more time I'd like to fix it
)
SEARCH DEPTH FIRST BY path SET order1
CYCLE path SET cycle TO 1 DEFAULT 0
select path || '->' ||  nghbr as end_path
from hqry
where hqry.lvl = 3
;

Требуется пять параметров

• path - предыдущая цепочка границ
• nghbr - текущий сосед с указанием корневой страныт.е. Франция
• prev_bdr - непосредственно предшествующая граница для предотвращения FR->DE->PL->DE
• root_bdr - исходная граница для предотвращения FR->CH->IT->FR
• lvl - доотслеживать степени разделения

Пример вывода для трех степеней разделения:

FR->CH->DE->DK
FR->CH->DE->PL
FR->DE->CH->IT
FR->DE->PL->RU
FR->IT->CH->DE

Здесь есть демонстрационная программа SQL Fiddle .Я добавил еще пару стран: Швейцария добавляет несколько неприятных краев.

Очевидно, что вышеприведенный вывод показывает, что он не применяет алгоритм кратчайшего пути , который оставлен в качестве упражнения длячитатель :) Если вы заинтересованы в добавлении этого - и вы должны это сделать, потому что я думаю, что это ключ к надежному решению - я предлагаю вам настоящий этот пост от Лукаса Джеллема .

Answer 3

Вот полное перечисление всех возможных путей и их длин с учетом стартовой страны и без ограничений в отношении путей, являющихся кратчайшими возможными путями между двумя странами (отказ от ответственности, не используйте это в слишком многих странах):

WITH 
  countries AS (SELECT DISTINCT border country FROM t),
  chains (country, path, destination, steps) AS (
    SELECT country, country, country, 0
    FROM countries
    UNION ALL
    SELECT chains.country, chains.path || '->' || t.neighbor, t.neighbor, chains.steps + 1
    FROM chains
    JOIN t ON chains.destination = t.border 
    AND chains.path NOT LIKE '%' || t.neighbor || '%' -- This prevents cycles
  )
SELECT *
FROM chains
ORDER BY country, steps;

Результат:

| COUNTRY |           PATH | DESTINATION | STEPS |
|---------|----------------|-------------|-------|
|      DE |             DE |          DE |     0 |
|      DE |         DE->PL |          PL |     1 |
|      DE |         DE->FR |          FR |     1 |
|      DE |         DE->DK |          DK |     1 |
|      DE |     DE->FR->IT |          IT |     2 |
|      DK |             DK |          DK |     0 |
|      DK |         DK->DE |          DE |     1 |
|      DK |     DK->DE->FR |          FR |     2 |
|      DK |     DK->DE->PL |          PL |     2 |
|      DK | DK->DE->FR->IT |          IT |     3 |
|      FR |             FR |          FR |     0 |
|      FR |         FR->IT |          IT |     1 |
|      FR |         FR->DE |          DE |     1 |
|      FR |     FR->DE->DK |          DK |     2 |
|      FR |     FR->DE->PL |          PL |     2 |
|      IT |             IT |          IT |     0 |
|      IT |         IT->FR |          FR |     1 |
|      IT |     IT->FR->DE |          DE |     2 |
|      IT | IT->FR->DE->PL |          PL |     3 |
|      IT | IT->FR->DE->DK |          DK |     3 |
|      PL |             PL |          PL |     0 |
|      PL |         PL->DE |          DE |     1 |
|      PL |     PL->DE->FR |          FR |     2 |
|      PL |     PL->DE->DK |          DK |     2 |
|      PL | PL->DE->FR->IT |          IT |     3 |

SQLFiddle здесь.

Сохраните запрос в представлении, а затем отфильтруйте его, например

SELECT * FROM my_view WHERE country = 'FR' AND steps = 2

Примечание по кратчайшим путям:

Если вам действительно нужны кратчайшие пути между двумя странами, просто повторно используйте это представление, снова выбирая произвольный путь, когда два пути связываются (опять же, этоне самое эффективное решение, не делайте этого для слишком многих стран!):

SELECT 
  country,
  destination,
  MIN(steps) KEEP (DENSE_RANK FIRST ORDER BY steps) AS steps,
  MIN(path)  KEEP (DENSE_RANK FIRST ORDER BY steps) AS path
FROM paths
WHERE country != destination
GROUP BY country, destination
ORDER BY country, destination

И получите:

| COUNTRY | DESTINATION | STEPS |           PATH |
|---------|-------------|-------|----------------|
|      DE |          DK |     1 |         DE->DK |
|      DE |          FR |     1 |         DE->FR |
|      DE |          IT |     2 |     DE->FR->IT |
|      DE |          PL |     1 |         DE->PL |
|      DK |          DE |     1 |         DK->DE |
|      DK |          FR |     2 |     DK->DE->FR |
|      DK |          IT |     3 | DK->DE->FR->IT |
|      DK |          PL |     2 |     DK->DE->PL |
|      FR |          DE |     1 |         FR->DE |
|      FR |          DK |     2 |     FR->DE->DK |
|      FR |          IT |     1 |         FR->IT |
|      FR |          PL |     2 |     FR->DE->PL |
|      IT |          DE |     2 |     IT->FR->DE |
|      IT |          DK |     3 | IT->FR->DE->DK |
|      IT |          FR |     1 |         IT->FR |
|      IT |          PL |     3 | IT->FR->DE->PL |
|      PL |          DE |     1 |         PL->DE |
|      PL |          DK |     2 |     PL->DE->DK |
|      PL |          FR |     2 |     PL->DE->FR |
|      PL |          IT |     3 | PL->DE->FR->IT |

Как видно из этогоSQL Fiddle или снова с немного большим количеством данных .

Answer 4

Вы можете использовать CONNECT_BY_ROOT, чтобы найти соседей, и отфильтровать по LEVEL, чтобы найти n-го соседа.

SELECT *
FROM (
    SELECT border
        ,connect_by_root(neighbor) AS neighbor
    FROM borders
    WHERE border = :ctry
        AND LEVEL = :n
  CONNECT BY NOCYCLE 
  PRIOR border = neighbor
    ) WHERE neighbor != :ctry

Демо