递归查询查找满足条件的循环
Recursive query find cycles that satisfy a condition
我必须解决给出的问题。 tableexchange包含多个汇率：
From
To
Rate
EUR
GBP
0.91
GBP
USD
1.24
USD
EUR
0.89
...
...
...
存在哪些货币，您可以将货币兑换成货币，但不能将货币兑换成任何其他货币。
为此，我想出了一个像这样的集合查询：
SELECT To FROM exchange EXCEPT ALL SELECT From FROM exchange
现在，对于我想回答的第二个问题，我想不出解决办法
是否有任何货币兑换周期，您可以通过周期交易来获利？确保您的查询终止。
我这里确实需要递归。所以这是我到目前为止的框架：
with recursive recursion (From, To, Rate, Depth) as (
select *, 1 from exchange
union
select exchange.*, Depth + 1
from exchange e, recursion r
where e.From = r.To and
Depth < k and
e.Rate * r.Rate > 1
)
select * from recursion;
对于那个速率条件，我很确定这是错误的，因为它只检查当前转换是否大于 1。但是如果我的转换小于 1 但在某些时候有一个转换再次使它无效怎么办？ k用于最终终止查询。
我该如何解决这个问题？我的第一个查询是否正确？
我的解决方案（尝试）：
在非递归部分，我保留了原样的名称，因为它们是按原样给出的。我不想更改它们（我知道命名不好）。
WITH RECURSIVE recursion (Start, From, To, Rate) AS (
SELECT From, From, To, Rate FROM exchange
UNION
SELECT r.Start, e.From, e.To, (r.Rate* e.Rate) exchange
FROM exchange e, recursion r
WHERE r.From = e.To AND
r.Start <> e.To --stop condition
)
SELECT *
FROM recursion
WHERE Rate > 1;
通过使用 from_curr 来放置一个锚点，正如我第二次命名该列一样，在名称 starting_curr 下，并沿着递归传播这一列，直到当前子项的to_curr 等于向下传播的 starting_curr.
并且，在子 UNION 分支中，不要 SELECT exchange.*，而是 SELECT recursion.starting_curr, exchange.from_curr,exchange.to_curr,recursion.rate * exchange.rate AS exchange。然后，查看迭代相乘的 exchange 是否超过或低于 1 的值。
这对我自己来说是一个很好的练习 - 因为我也需要在递归查询中擦亮我的锈迹 - 所以我会与你分享。
这是一个较长的答案；它包含一个完整的场景。
根据我从 FedEx 获得的 2021 年 1 月的汇率建立一个交易所 table - 在 WITH 条款中硬连线我找到的与美元相比的所有汇率：
DROP TABLE IF EXISTS exch;
CREATE TABLE IF NOT EXISTS exch
AS
WITH
one_dollar_is(curr,rate) AS (
SELECT 'AUD', 1.29433
UNION ALL SELECT 'BRL', 5.36730
UNION ALL SELECT 'CAD', 1.27250
UNION ALL SELECT 'CNY', 6.46720
UNION ALL SELECT 'DKK', 6.10820
UNION ALL SELECT 'HKD', 7.75330
UNION ALL SELECT 'INR', 73.11060
UNION ALL SELECT 'JPY', 103.78830
UNION ALL SELECT 'KRW', 1098.23670
UNION ALL SELECT 'MXN', 19.94120
UNION ALL SELECT 'MYR', 4.03570
UNION ALL SELECT 'NZD', 1.38889
UNION ALL SELECT 'NOK', 8.50960
UNION ALL SELECT 'ZAR', 15.13790
UNION ALL SELECT 'EUR', 0.82115
UNION ALL SELECT 'LKR', 190.76280
UNION ALL SELECT 'SEK', 8.28670
UNION ALL SELECT 'CHF', 0.88650
UNION ALL SELECT 'SGD', 1.32560
UNION ALL SELECT 'TWD', 28.00610
UNION ALL SELECT 'THB', 29.99720
UNION ALL SELECT 'GBP', 0.73308
UNION ALL SELECT 'VEB',1487241.13850
)
-- create an all-to-all conversion table, using the
-- rates to and from USD ...
SELECT
s.curr AS s_curr
, (t.rate / s.rate)::NUMERIC(18,10) AS rate
, t.curr AS t_curr
FROM one_dollar_is s
CROSS JOIN one_dollar_is t
-- dollar to other curr from original ..
UNION ALL
SELECT
'USD'
, rate
, curr
FROM one_dollar_is
UNION ALL
-- other curr to dollar from original.
SELECT
curr
, (1 / rate)::NUMERIC(18,10)
, 'USD'
FROM one_dollar_is
;
递归查询来了
WITH RECURSIVE
change_chain AS (
SELECT
1 AS dpth -- depth measurer
, s_curr AS start_curr -- anchor; starting currency
, t_curr AS end_curr
, rate
, s_curr||'->'||t_curr AS chain -- build the "currency used graph" used
, t_curr
FROM exch
UNION ALL
SELECT
par.dpth+1 AS dpth -- add 1 to parent
, par.start_curr -- keep starting currency
, chi.t_curr AS end_curr -- redundant end currency
, par.rate*chi.rate AS rate -- multiply parent rate by child rate
, par.chain||'->'||chi.t_curr AS chain -- keep building the change path
, chi.t_curr
FROM change_chain par
JOIN exch chi
ON par.t_curr=chi.s_curr
WHERE par.dpth > 1 OR par.start_curr=chi.t_curr
-- no point in keeping those ending in different currency, after more than 1 hops
)
SELECT
*
FROM change_chain
WHERE dpth <= 5 -- limit depth
AND t_curr=start_curr -- a bit redundant, but still ..
AND rate > 1.0001 -- limit to an exchange rate worth looking at.
dpth|start_curr|end_curr|rate |chain |t_curr
4|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->VEB |VEB
4|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->CHF |CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->AUD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->BRL->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CAD->VEB|VEB
5|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->CHF->CHF|CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CHF->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->VEB->CHF->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CNY->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->DKK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->EUR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->GBP->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->HKD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->INR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->JPY->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->KRW->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->LKR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->MXN->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->MYR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->NOK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->NZD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->SEK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->SGD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->THB->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->TWD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->USD->VEB|VEB
5|CHF |CHF |1.00010027|CHF->VEB->CHF->KRW->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->NZD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CHF->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->TWD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->THB->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->JPY->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->SGD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->LKR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CNY->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->DKK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->SEK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->MXN->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->BRL->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->EUR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->INR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->HKD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->NOK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->GBP->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CAD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->AUD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->MYR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->ZAR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->USD->VEB->CHF|CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->VEB->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->ZAR->VEB|VEB
请注意，PostgreSQL 中的查询有 5 个级别，在 30 分钟内从未在我的 Ubuntu 笔记本电脑上返回。我 运行 在同一台笔记本电脑上我的 Vertica 实例上也是如此，大约 3 分钟后它又回来了。
我必须解决给出的问题。 tableexchange包含多个汇率：
| From | To | Rate |
|---|---|---|
| EUR | GBP | 0.91 |
| GBP | USD | 1.24 |
| USD | EUR | 0.89 |
| ... | ... | ... |
存在哪些货币，您可以将货币兑换成货币，但不能将货币兑换成任何其他货币。
为此，我想出了一个像这样的集合查询：
SELECT To FROM exchange EXCEPT ALL SELECT From FROM exchange
现在，对于我想回答的第二个问题，我想不出解决办法
是否有任何货币兑换周期，您可以通过周期交易来获利？确保您的查询终止。
我这里确实需要递归。所以这是我到目前为止的框架：
with recursive recursion (From, To, Rate, Depth) as (
select *, 1 from exchange
union
select exchange.*, Depth + 1
from exchange e, recursion r
where e.From = r.To and
Depth < k and
e.Rate * r.Rate > 1
)
select * from recursion;
对于那个速率条件，我很确定这是错误的，因为它只检查当前转换是否大于 1。但是如果我的转换小于 1 但在某些时候有一个转换再次使它无效怎么办？ k用于最终终止查询。
我该如何解决这个问题？我的第一个查询是否正确？
我的解决方案（尝试）：
在非递归部分，我保留了原样的名称，因为它们是按原样给出的。我不想更改它们（我知道命名不好）。
WITH RECURSIVE recursion (Start, From, To, Rate) AS (
SELECT From, From, To, Rate FROM exchange
UNION
SELECT r.Start, e.From, e.To, (r.Rate* e.Rate) exchange
FROM exchange e, recursion r
WHERE r.From = e.To AND
r.Start <> e.To --stop condition
)
SELECT *
FROM recursion
WHERE Rate > 1;
通过使用 from_curr 来放置一个锚点，正如我第二次命名该列一样，在名称 starting_curr 下，并沿着递归传播这一列，直到当前子项的to_curr 等于向下传播的 starting_curr.
并且，在子 UNION 分支中，不要 SELECT exchange.*，而是 SELECT recursion.starting_curr, exchange.from_curr,exchange.to_curr,recursion.rate * exchange.rate AS exchange。然后，查看迭代相乘的 exchange 是否超过或低于 1 的值。
这对我自己来说是一个很好的练习 - 因为我也需要在递归查询中擦亮我的锈迹 - 所以我会与你分享。
这是一个较长的答案；它包含一个完整的场景。
根据我从 FedEx 获得的 2021 年 1 月的汇率建立一个交易所 table - 在 WITH 条款中硬连线我找到的与美元相比的所有汇率：
DROP TABLE IF EXISTS exch;
CREATE TABLE IF NOT EXISTS exch
AS
WITH
one_dollar_is(curr,rate) AS (
SELECT 'AUD', 1.29433
UNION ALL SELECT 'BRL', 5.36730
UNION ALL SELECT 'CAD', 1.27250
UNION ALL SELECT 'CNY', 6.46720
UNION ALL SELECT 'DKK', 6.10820
UNION ALL SELECT 'HKD', 7.75330
UNION ALL SELECT 'INR', 73.11060
UNION ALL SELECT 'JPY', 103.78830
UNION ALL SELECT 'KRW', 1098.23670
UNION ALL SELECT 'MXN', 19.94120
UNION ALL SELECT 'MYR', 4.03570
UNION ALL SELECT 'NZD', 1.38889
UNION ALL SELECT 'NOK', 8.50960
UNION ALL SELECT 'ZAR', 15.13790
UNION ALL SELECT 'EUR', 0.82115
UNION ALL SELECT 'LKR', 190.76280
UNION ALL SELECT 'SEK', 8.28670
UNION ALL SELECT 'CHF', 0.88650
UNION ALL SELECT 'SGD', 1.32560
UNION ALL SELECT 'TWD', 28.00610
UNION ALL SELECT 'THB', 29.99720
UNION ALL SELECT 'GBP', 0.73308
UNION ALL SELECT 'VEB',1487241.13850
)
-- create an all-to-all conversion table, using the
-- rates to and from USD ...
SELECT
s.curr AS s_curr
, (t.rate / s.rate)::NUMERIC(18,10) AS rate
, t.curr AS t_curr
FROM one_dollar_is s
CROSS JOIN one_dollar_is t
-- dollar to other curr from original ..
UNION ALL
SELECT
'USD'
, rate
, curr
FROM one_dollar_is
UNION ALL
-- other curr to dollar from original.
SELECT
curr
, (1 / rate)::NUMERIC(18,10)
, 'USD'
FROM one_dollar_is
;
递归查询来了
WITH RECURSIVE
change_chain AS (
SELECT
1 AS dpth -- depth measurer
, s_curr AS start_curr -- anchor; starting currency
, t_curr AS end_curr
, rate
, s_curr||'->'||t_curr AS chain -- build the "currency used graph" used
, t_curr
FROM exch
UNION ALL
SELECT
par.dpth+1 AS dpth -- add 1 to parent
, par.start_curr -- keep starting currency
, chi.t_curr AS end_curr -- redundant end currency
, par.rate*chi.rate AS rate -- multiply parent rate by child rate
, par.chain||'->'||chi.t_curr AS chain -- keep building the change path
, chi.t_curr
FROM change_chain par
JOIN exch chi
ON par.t_curr=chi.s_curr
WHERE par.dpth > 1 OR par.start_curr=chi.t_curr
-- no point in keeping those ending in different currency, after more than 1 hops
)
SELECT
*
FROM change_chain
WHERE dpth <= 5 -- limit depth
AND t_curr=start_curr -- a bit redundant, but still ..
AND rate > 1.0001 -- limit to an exchange rate worth looking at.
dpth|start_curr|end_curr|rate |chain |t_curr
4|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->VEB |VEB
4|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->CHF |CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->AUD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->BRL->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CAD->VEB|VEB
5|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->CHF->CHF|CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CHF->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->VEB->CHF->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->CNY->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->DKK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->EUR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->GBP->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->HKD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->INR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->JPY->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->KRW->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->LKR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->MXN->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->MYR->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->NOK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->NZD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->SEK->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->SGD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->THB->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->TWD->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->USD->VEB|VEB
5|CHF |CHF |1.00010027|CHF->VEB->CHF->KRW->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->NZD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CHF->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->TWD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->THB->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->JPY->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->SGD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->LKR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CNY->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->DKK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->SEK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->MXN->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->BRL->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->EUR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->INR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->HKD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->NOK->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->GBP->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->CAD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->AUD->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->MYR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->ZAR->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->VEB->VEB->CHF|CHF
5|CHF |CHF |1.00010027|CHF->VEB->CHF->USD->VEB->CHF|CHF
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->VEB->VEB|VEB
5|VEB |VEB |1.00010027|VEB->CHF->VEB->CHF->ZAR->VEB|VEB
请注意，PostgreSQL 中的查询有 5 个级别，在 30 分钟内从未在我的 Ubuntu 笔记本电脑上返回。我 运行 在同一台笔记本电脑上我的 Vertica 实例上也是如此，大约 3 分钟后它又回来了。