近似XML查询处理技术解析

# 近似 XML 查询处理技术解析 ## 1. 导航条件匹配与得分机制 在处理 XML 文档查询时，导航条件的匹配至关重要。当文档中的元素满足所有结构约束（即元素的出边）时，导航条件才算完全匹配。对于任何匹配的导航条件（元素到叶子节点的路径），会分配一个结构得分 c。这个得分 c 是可调整的，目的是在结构得分和内容得分之间实现最佳平衡。不过，在某些评分模型中，得分 c 的设置相对粗糙，未来可以探索让 c 依赖于近似结构匹配的优劣程度。 ## 2. 近似查询处理概述 近似查询处理技术多种多样，且深受近似程度的影响。例如，一些早期方法在查询时会对数据应用所有允许的转换，但这种方法仅在可能的转换数量相当有限时才可行。还有些方法会评估原始查询的所有可能松弛情况，但这也只有在仅基于查询就能获得这些松弛情况时才有可能实现。 需要注意的是，XML 数据的近似查询通常是阈值查询或 top - k 查询。在这种情况下，能够提前修剪那些不太可能产生高分结果的候选答案，对于高效处理查询至关重要。 ### 2.1 Twig - Path 评分与 Whirpool 架构 - **Twig - Path 评分**：采用典型的 top - k 算法，通过 DAG 维护预计算的 idf 分数，用于所有部分匹配可能满足的松弛查询。使用矩阵表示查询、其松弛情况和部分匹配，以便在 top - k 查询处理过程中快速确定部分匹配最能满足的松弛查询，并修剪无关的部分查询匹配。 - **Whirpool 架构**：这是一种灵活的架构，用于自适应处理 XML 文档的 top - k 查询。它允许对同一查询的部分匹配遵循不同的执行计划，并利用 top - k 查询模型在查询处理期间做出动态选择。其处理方法的关键特征如下： - 极有可能进入 top - k 集合的部分匹配会被优先处理。 - 不太可能进入 top - k 集合的部分匹配会遵循最便宜的计划，以便尽早修剪。 其自适应查询评估依赖于服务器，每个 twig 模式中的节点对应一个服务器。其中一个服务器比较特殊，它会生成与查询根节点的候选匹配，从而初始化一组部分匹配，这些部分匹配会在系统中自适应路由。其他服务器为元素 e 维护一个部分匹配的优先队列（之前都未经过该服务器）。对于优先队列头部的每个部分匹配，服务器会执行以下操作： 1. 计算一组扩展（部分或完整）匹配，每个扩展匹配都会用一个与查询结构一致的 e 节点（如果有）扩展部分匹配。 2. 为每个扩展匹配计算分数。 3. 确定扩展匹配是否会影响 top - k 集合或受其影响。 系统会维护一个 top - k（部分或完整）匹配的候选集及其分数，以此来确定新计算的部分匹配是更新集合中现有匹配的分数、替换集合中的现有匹配，还是被修剪掉。完整的匹配不再进一步处理，而未被修剪的部分匹配会被发送到路由器。路由器会根据部分匹配的最大可能最终分数维护一个队列，对于队列头部的部分匹配，路由器会确定下一个需要处理该部分匹配的服务器，并将其发送到该服务器的队列中。 下面是 Whirpool 架构处理流程的 mermaid 流程图： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(生成候选匹配):::process B --> C{是否完整匹配}:::decision C -->|是| D(不再处理):::process C -->|否| E(计算扩展匹配):::process E --> F(计算分数):::process F --> G{是否影响 top - k 集合}:::decision G -->|是| H(更新或替换):::process G -->|否| I(修剪或发送到路由器):::process I --> J(路由器确定下一个服务器):::process J --> K(发送到服务器队列):::process K --> C ``` ### 2.2 TopX 引擎 TopX 引擎通过预计算和物化标签 - 术语对的连接，在与内容和结构相关的查询条件的组合倒排索引上运行。这个简单的预计算步骤使查询处理更具可扩展性，其索引结构的编码易于序列化，可以像任何倒排索引一样直接顺序存储在磁盘上，例如使用传统的 B + - 树索引或倒排文件。 在查询处理时，TopX 会交错扫描查询中每个标签 - 术语对的倒排列表，仅通过对这些列表的排序访问将大元素块提取到内存中，然后将这些块与同一文档在不同查询维度上之前看到的元素块进行迭代连接。使用 Pre - / Post - order 树编码来处理结构，To