甲骨文：获取由 N 个边界分隔的国家

Question

我想让所有国家与指定国家相隔 N (1,2,3,4 ...) 个边界。

还应指定 N。

例如我有 table "borders" 和 "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

N = 2 & 国家 = 法国

如果我想让国家与法国相隔 2 个边界，它应该 return 波兰（FR -> DE -> PL）和丹麦（FR -> DE -> DK）

N = 1 & 国家 = 法国

如果我想让国家与法国相隔 1 个边界，应该 return 德国（FR -> DE）和意大利（FR -> IT）

如果需要，我可以修改边框。

我尝试了一些分层查询但没有成功。

谢谢 BR

Answer 1

您可以使用 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

Demo

Answer 2

您的 BORDERS table 包含相互关系（例如 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

有a SQL Fiddle demo here。我添加了几个国家：瑞士添加了一些令人讨厌的边缘案例。

显然上面的输出显示它没有强制执行 shortest path algorithm, that is left as an exercise for the reader :) If you're interested in adding this - and you should be, because I think it's key to a robust solution - I suggest you real this post by Lucas Jellema。

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

将查询存储在视图中，然后您可以对其进行过滤，例如

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 |

As can be seen in this SQL Fiddle, or again, with a bit more data.

Answer 4

您可以将每个国家/地区的邻居聚合到一个集合中，然后使用简单的分层查询来查找（非循环）路径：

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

Results:

|                 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

Results:

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

甲骨文：获取由 N 个边界分隔的国家

Oracle: get countries separated by N borders

sql

oracle

connect-by

recursive-query

oracle11g

关于最短路径的旁注：