使用XQuery进行递归示例

Question

我有一个看起来像这样的数据库(访问它$database):

<country car_code="F" area="547030" capital="cty-france-paris">
  <name>France</name>
  <border country="AND" length="60"/>
  <border country="E" length="623"/>
  <border country="D" length="451"/>
  <border country="I" length="488"/>
  <border country="CH" length="573"/>
  <border country="B" length="620"/>
  <border country="L" length="73"/>
  <border country="MC" length="4.4"/>
</country>

.....
other countries

我想写一个函数,通过陆地边界提供从法国(或任何其他国家)可以到达的所有国家的名称.第一次尝试(可能有很多语法错误和其他错误,但程序的语义应该"更清楚"):

declare function local:reachable($country as element())
  as (return value should be a sequence of countries  )
{
  if $country == ()   (:if empty, it doesn't border to any other country:)
    then ()

  else(
    $country/name  UNION (for $bord in $country/border/@country  return
    local:reachable ($database/country/car_code = @bord ))
  )
}

对该功能的调用:

local:reachable($database/country[@car_code = "F"])

与法国接壤的国家应该是:

  <border country="AND" length="60"/>
  <border country="E" length="623"/>
  <border country="D" length="451"/>
  <border country="I" length="488"/>
  <border country="CH" length="573"/>
  <border country="B" length="620"/>
  <border country="L" length="73"/>
  <border country="MC" length="4.4"/>

但我们也需要找到这些国家的边境国家.最终输出应为"F","AND","E","D","I","CH","B","L","MC"......,X,Y,Z, (以及与这些国家接壤的其他国家).

• 我知道UNION没有定义,但还有什么我可以使用的吗？我只是想让它更清楚我想做什么

• 除了语法错误之外,一个大问题是如果"F"与"L"接壤,那么"L"将与"F"接壤,因此我的"函数"将永远不会终止 - 我该如何处理？

• 我能从语法上得到一些帮助吗？

• 如果问题不明确,请告诉我,以便我可以进一步澄清

Answer 1

在我们开始之前

以下是对您的代码的一些评论:

• $country as element()定义一个必须只包含一个元素的变量,所以它永远不能为空; 使用element()?如果元素是可选的,element()*如果存在可以是其中任意数量,或者element()+如果必须有一个或多个

• 序列操作,可以用于构建其它序列的序列:(1,2) , (3,4)构建体2组的序列:(1,2)和 (3,4),然后构造包含在其它所有项目另一个,从而导致:(1,2,3,4)

数据

让我稍微改变一下这个countries元素,所以我去掉了噪音,让这个演示更加简单.另外,我创建了一个简单但完整的地图.假设我们有两个相邻的国家U和K,另外4个国家形成一个正方形(每个国家与另外两个国家相邻):N,G,B和F.与现有地理或政治的任何相似之处仅在您眼中: - )

<!--
Map:   U K | N G
             B F
-->
<countries>
   <country id="U">
      <name>Over the top</name>
      <border idref="K"/>
   </country>
   <country id="K">
      <name>Beyond the see</name>
      <border idref="U"/>
   </country>
   <country id="N">
      <name>Flatland</name>
      <border idref="B"/>
      <border idref="G"/>
   </country>
   <country id="G">
      <name>Marxhome</name>
      <border idref="N"/>
      <border idref="F"/>
   </country>
   <country id="B">
      <name>Beerium</name>
      <border idref="N"/>
      <border idref="F"/>
   </country>
   <country id="F">
      <name>Grapeandcheese</name>
      <border idref="B"/>
      <border idref="G"/>
   </country>
</countries>

解

该解决方案包括一个递归函数,它消耗一个国家队列来处理.同时,它一次累积一个国家的结果列表.它占用队列中的第一个国家,将其添加到结果中,然后递归到尚未在队列中的所有相邻国家或当前结果.增强的结果也会传递下来.

xquery version "3.0";

declare variable $countries :=
<countries>
   <!-- as above, just copy and paste it -->
</countries>;

declare function local:reachable(
   $queue  as element(country)*,
   $result as element(country)*   
) as element(country)*
{
   if ( empty($queue) ) then (
      (: we do not consider one country reachable from itself :)
      tail($result)
   )
   else (
      let $this := head($queue)
      let $rest := tail($queue)
      let $more := $this/border/@idref[not(. = ($queue, $result)/@id)]
      return
         local:reachable(
            ( $rest, $countries/country[@id = $more] ),
            ( $result, $this ))
   )
};

(: for each countries, display its reachable countries
 :)
for $c in $countries/country
order by $c/@id
let $r := local:reachable($c, ())
return
   $c/name || ': ' || string-join($r/@id, ', ')

结果

Beerium: N, G, F
Grapeandcheese: N, G, B
Marxhome: N, B, F
Beyond the see: U
Flatland: G, B, F
Over the top: K