在xml中存储具有共索引节点的树的最有效方法

我在接一个老项目,效率和效益是关键。我分析了100 GB的XML数据。对于每个xml树(数以百万计),使用一些xml属性从中推断模式。不过,对于这个问题,我会把事情大大简化,但重要的是要记住 很多 对数据进行快速处理,并将结果整齐地存储在xml中是很重要的。此外,还需要遍历生成的xml树。实际上,它将用作 BaseX 但我以后再谈。

从每棵树(及其子树,但现在这并不重要)创建一个基于根节点的直接子节点的模式。作为一个基本示例,请使用以下XML树:

<node letter="X">
  <node letter="A"/>
  <node letter="B"/>
  <node letter="C"/>
  <node letter="D"/>
</node>

该模式是通过获取所有子字母属性并对其进行排序和连接来创建的。在这种情况下,模式是 ABCD .

对于每个树,还生成所有可能的子树(顺序不重要,最小组合2),即所有可能的子树组合,并生成它们的模式。我不包括组合树的xml,但是除了 ABCD ,因此将是:

AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD

在层次结构中,它们看起来像这样(注意终端节点中的重复)。

此外,在生成的xml中应该以某种方式指示我们开始的完整模式,以指示它是树中的“main”模式。最后,我希望恢复从给定模式(参见后面的内容)派生的所有模式,并将这些模式过滤为只有“主”模式。

从查询的角度来看,您可以 argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found because 抗体 is part of ABCD。所以如果我要找模式 AB 根据上面的数据,我想找到

ABCD
ABC
ABD

很明显这里有两个步骤。首先,概括一个层次: AB -> ABC,ABD 然后 ABC->ABCD (又一次) ABD->ABDC 当然,每个结果只能找到一次)。中间步骤 ABC 和 ABD 对我也很重要,不仅仅是决赛 ABCD 结果。

我所面临的问题是,如何有效地存储一棵树,如图像中显示的树,使其为1。以我所讨论的方式易于查询;尽可能稀疏而不丢失任何节点;建造效率高。后一点对于这个问题不太重要,因为我将自己实现构建脚本——这将在Python3.6中完成。

到目前为止,我的想法是要有一个相当扁平的结构,通过对直接父节点进行“共索引”来工作。看起来是这样的:

<tree>
  <node pattern="AB" index="1">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="8"/> <!-- ABD -->
  </node>
  <node pattern="AC" index="2">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="9"/> <!-- ACD-->
  </node>
  <node pattern="AD" index="3">
    <parentnode coindex="8"/> <!-- ABD -->
    <parentnode coindex="9"/> <!-- ACD -->
  </node>
  <node pattern="BC" index="4">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="BD" index="5">    
      <parentnode coindex="8"/> <!-- ABD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="CD" index="6">    
      <parentnode coindex="9"/> <!-- ACD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="ABC" index="7">    
    <parentnode coindex="11"/> <!-- ABCD -->
  </node>
  <node pattern="ABD" index="8">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ACD" index="9">   
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="BCD" index="10">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ABCD" index="11" isMain="true"/>
</tree>

通过这样做,我想一个人可以得到所有连接在一起的模式。例如,如果我现在要找AB,我希望找到那个节点的子节点( parentnode )取下这些索引并用它们来寻找直系父母。然后重复该过程,直到没有元素留下coindex(例如 ABCD 在这种情况下)。

假设有成千上万个这样的xml元素,并且主要的元素用 isMain . 注意 伊斯曼 不一定是没有父节点子节点的模式!其结果是 全部的 原始XML树。意思是在某些情况下,一个模式可能是主要的,而在其他情况下,它可能是组合的一部分。在这种情况下 node 是 用表示 伊斯曼 因为在原始的XML中有“一些树将此模式作为其主模式”。

到目前为止,这只是我的想法,但我不确定是否有更好的方法,或者更重要的是,是否可以在basex中很容易地查询到。基本上是给定的输入 抗体 我想找回所有相关的 pattern s(abc、abd、abcd)使用索引,然后通过仅检索 isMain="true" . 我期待看到更好的想法,以及在Basex中查询它们的方法。如果我的想法是好的,那么我希望看到一种在单个xquery表达式中捕获查询的好方法。