Pertanyaan Oracle: dapatkan negara-negara yang dipisahkan oleh batas N


Saya ingin agar semua negara dipisahkan oleh N (1,2,3,4 ...) perbatasan dari negara tertentu.

N juga harus ditentukan.

Misalnya saya memiliki tabel "perbatasan" dan "negara":


perbatasan | tetangga
-----------------
  FR | DE
  FR | SAYA T
  IT | FR
  DE | FR
  DE | PL
  PL | DE
  DE | DK
  DK | DE


KODE COUNTRYNAME
---- ---------
FR Prancis
DE Jerman
RU Rusia
IT Italia
PL Polandia
DK Denmark
  1. N = 2 & negara = Prancis

Jika saya ingin membuat negara-negara dipisahkan oleh 2 perbatasan dari Perancis, itu harus mengembalikan Polandia (FR -> DE -> PL) dan Denmark (FR -> DE -> DK)

  1. N = 1 & negara = Prancis

Jika saya ingin membuat negara-negara dipisahkan oleh 1 perbatasan dari Perancis, itu harus mengembalikan Jerman (FR -> DE) dan Italia (FR -> IT)

Saya dapat memodifikasi batas jika diperlukan.

Saya mencoba beberapa kueri hierarkis tanpa berhasil.

Terima kasih BR


5
2018-05-20 12:46


asal


Jawaban:


Berikut ini adalah penghitungan lengkap dari semua jalur yang mungkin dan panjangnya, diberikan negara awal dan tidak ada batasan untuk jalur yang merupakan jalur terpendek antara dua negara (disclaimer, jangan jalankan ini di terlalu banyak negara):

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;

Hasilnya adalah:

| 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 di sini.

Simpan kueri dalam tampilan dan kemudian Anda dapat memfilternya, mis.

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

Catatan samping pada jalur terpendek:

Jika Anda memang membutuhkan jalur terpendek antara dua negara, cukup gunakan kembali Pandangan itu lagi memilih jalur yang sewenang-wenang ketika dua jalur terhubung (sekali lagi, ini bukan solusi yang paling efisien, jangan lakukan ini untuk terlalu banyak negara!):

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

Dan dapatkan:

| 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 |

Seperti yang bisa dilihat dalam Fiddle SQL ini, atau lagi, dengan sedikit lebih banyak data.


8
2018-05-20 15:47



Anda dapat menggabungkan tetangga dari setiap negara ke dalam kumpulan dan kemudian menggunakan kueri hierarkis sederhana untuk menemukan jalur (non-siklik):

SQL Fiddle

Setup Oracle 11g R2 Schema:

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);

Permintaan 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

Hasil:

|                 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 |

Jelaskan Rencana:

-----------------------------------------------------------------------------------------------
| 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')

Permintaan 2 Ini akan mendapatkan jalur terpendek (dengan ikatan) antara pasangan negara:

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

Hasil:

|                 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 |

Jelaskan Rencana:

---------------------------------------------------------------------------------------
| 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")

4
2018-05-20 20:28



Tabel BORDERS Anda berisi hubungan timbal balik (mis. FR->DE, DE->FR). Ini berarti Anda harus menangani siklus. Ini tidak mudah, karena Anda ingin menghindarinya FR->DE->PL->DE pada tiga derajat pemisahan.

Saya punya di sini klausa rekursif, (jadi Oracle 11gR2 atau yang lebih baru) yang melakukan ini.

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
;

Dibutuhkan lima parameter

  • path - rantai perbatasan sebelumnya
  • nghbr - Tetangga saat ini, menyatakan dengan negara root yaitu Prancis
  • prev_bdr - Perbatasan langsung sebelumnya untuk mencegah FR->DE->PL->DE
  • root_bdr - Perbatasan asal untuk mencegah FR->CH->IT->FR
  • lvl - untuk melacak derajat pemisahan

Contoh output untuk tiga derajat pemisahan:

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

Ada demo SQL Fiddle di sini. Saya menambahkan di beberapa negara lain: Swiss menambahkan beberapa kasus tepi yang buruk.

Jelas output di atas menunjukkan itu tidak menegakkan algoritma jalur terpendek, yang tersisa sebagai latihan untuk pembaca :) Jika Anda tertarik untuk menambahkan ini - dan Anda seharusnya, karena saya pikir itu kunci untuk solusi yang kuat - saya sarankan Anda nyata posting ini oleh Lucas Jellema.


3
2018-05-20 14:58



Anda bisa menggunakannya CONNECT_BY_ROOT untuk menemukan tetangga dan menyaring LEVEL untuk menemukan tetangga ke-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

Demo


0
2018-05-20 14:48