如何处理 XQuery 中的递归?
How to handle recursion in XQuery?
我正在尝试使用 mondial.sql 数据库通过陆路边界从一个国家/地区穿越到另一个国家/地区,从而找到所有可通过陆路到达的国家/地区。它必须递归地完成,我在网上找到了一些我认为对连接序列有用的函数,并且能够排除已经找到的国家。
问题是我最终陷入了一个循环,即使要排除的国家似乎处理得当。所以我的想法是,我可能必须以某种方式定义一个基本案例,以便在找到所有可能的国家/地区后停止递归。如何使用 XQuery 实现这一点?
(:functx.value-union and is-value-in-sequence were found at http://www.xqueryfunctions.com/xq/:)
declare namespace functx = "http://www.functx.com";
declare function functx:value-union
( $arg1 as xs:anyAtomicType* ,
$arg2 as xs:anyAtomicType* ) as xs:anyAtomicType* {
distinct-values(($arg1, $arg2))
};
declare function functx:is-value-in-sequence
( $value as xs:anyAtomicType? ,
$seq as xs:anyAtomicType* ) as xs:boolean {
$value = $seq
} ;
(:Recursive function for finding reachable countries:)
declare function local:findReachable($countries, $country, $reachedCountries) {
let $reachableCountries := $countries[@car_code = $country/border/@country]
for $c in $reachableCountries
where not(functx:is-value-in-sequence($c, $reachedCountries))
return functx:value-union($c, local:findReachable($countries, $c, functx:value-union($reachableCountries,
$reachedCountries)))
};
let $countries := //country
let $startingCountry := //country[@car_code = 'S']
return local:findReachable($countries, $startingCountry, $startingCountry)
你对 $reachedCountries
的检查只能保证国家不会出现两次 在同一条路径上 ,但你仍然会沿着每条可能的路径访问每个国家,这需要一个很久。没有循环,只有很多冗余。
这是一个简单的深度优先搜索,它可以满足您的需求:
declare function local:dfs($stack, $seen) {
if(empty($stack)) then $seen
else (
let $country := $stack[1]
let $neighbors :=
for $code in $country/border/@country[not(. = $seen/@car_code)]
return $country/../country[@car_code = $code]
return local:dfs(($neighbors, $stack[position() > 1]), ($seen, $neighbors))
)
};
local:dfs(doc('mondial.xml')//country[@car_code = 'S'], ())/name
我正在尝试使用 mondial.sql 数据库通过陆路边界从一个国家/地区穿越到另一个国家/地区,从而找到所有可通过陆路到达的国家/地区。它必须递归地完成,我在网上找到了一些我认为对连接序列有用的函数,并且能够排除已经找到的国家。
问题是我最终陷入了一个循环,即使要排除的国家似乎处理得当。所以我的想法是,我可能必须以某种方式定义一个基本案例,以便在找到所有可能的国家/地区后停止递归。如何使用 XQuery 实现这一点?
(:functx.value-union and is-value-in-sequence were found at http://www.xqueryfunctions.com/xq/:)
declare namespace functx = "http://www.functx.com";
declare function functx:value-union
( $arg1 as xs:anyAtomicType* ,
$arg2 as xs:anyAtomicType* ) as xs:anyAtomicType* {
distinct-values(($arg1, $arg2))
};
declare function functx:is-value-in-sequence
( $value as xs:anyAtomicType? ,
$seq as xs:anyAtomicType* ) as xs:boolean {
$value = $seq
} ;
(:Recursive function for finding reachable countries:)
declare function local:findReachable($countries, $country, $reachedCountries) {
let $reachableCountries := $countries[@car_code = $country/border/@country]
for $c in $reachableCountries
where not(functx:is-value-in-sequence($c, $reachedCountries))
return functx:value-union($c, local:findReachable($countries, $c, functx:value-union($reachableCountries,
$reachedCountries)))
};
let $countries := //country
let $startingCountry := //country[@car_code = 'S']
return local:findReachable($countries, $startingCountry, $startingCountry)
你对 $reachedCountries
的检查只能保证国家不会出现两次 在同一条路径上 ,但你仍然会沿着每条可能的路径访问每个国家,这需要一个很久。没有循环,只有很多冗余。
这是一个简单的深度优先搜索,它可以满足您的需求:
declare function local:dfs($stack, $seen) {
if(empty($stack)) then $seen
else (
let $country := $stack[1]
let $neighbors :=
for $code in $country/border/@country[not(. = $seen/@car_code)]
return $country/../country[@car_code = $code]
return local:dfs(($neighbors, $stack[position() > 1]), ($seen, $neighbors))
)
};
local:dfs(doc('mondial.xml')//country[@car_code = 'S'], ())/name