xml – 如何在XQuery中处理递归？

发布时间：2020-12-16 23:07:43 所属栏目：百科来源：网络整理

导读：我试图通过使用mondial.sql数据库通过陆地边界从一个国家到另一个国家来寻找可以通过陆地到达的所有国家.它必须以递归方式完成,我发现一些在线功能,我认为这对于连接序列很有用,并且能够排除已经找到的国家. 问题是,即使被排除的国家似乎得到妥善处理,我最终

我试图通过使用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)

解决方法

您使用$reachCountries进行的检查仅保证国家/地区不会在同一路径上出现两次,但您仍然会沿着每条可能的路径访问每个国家/地区,这需要很长时间.没有循环,只有很多冗余.

这是一个简单的深度优先搜索,可以满足您的需求：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!