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

如果我想让国家与法国分开2个边界,它应该返回波兰(FR - > DE - > PL)和丹麦(FR - > DE - > DK)

2. N = 1&country = France

如果我想让国家与法国分开1个边界,它应该返回德国(FR - > DE)和意大利(FR - > IT)

如果需要,我可以修改边框.

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

谢谢BR

Answer 1

以下是所有可能路径及其长度的完整列举,给出了一个起始国家,并且没有限制路径是两个国家之间最短的路径(免责声明,不要在太多国家/地区运行):

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中可以看到的那样,或者再次提供更多的数据.