提升XPath查询性能与XML数据存储的高效方案

### 提升XPath查询性能与XML数据存储的高效方案 #### 1. 利用Oracle仓库加速XPath查询 在处理XPath查询时，为了提高查询效率，我们采用了一种基于语义仓库的方法。具体步骤如下： - **计算匹配数量**：利用语义仓库计算低选择性查询的匹配数量。 - **拆分查询**：如果匹配数量超过设定的阈值（当前实验设置为50,000），查询路由器（QR）会将低选择性查询拆分为若干子查询，子查询的数量等于（匹配数量 / 阈值） + 1。这些子查询与原低选择性查询等价。 此外，eXist处理器在处理搜索范围大或数据库非常大的通配符查询（Q2）时存在问题。如果节点测试或谓词子句中存在通配符，QR会在PreLevel索引处处理通配符选项来移除通配符，但目前这一功能尚未完全成熟，仅能在某些查询中移除通配符。 #### 2. 提升XPath查询性能的整体方案 为了提升XPath查询的性能，我们构建了FAST语义仓库，其中包含基于先前XPath性能的层级索引工作的索引结构。当前工作中，我们使用Oracle 10g部署了扩展索引结构，并利用Oracle的一些特性确保索引的快速重建。通过查询路由器，我们可以通过以下两种模式利用索引结构： - **完全解析查询**：使用索引方法完全解析查询。 - **生成结果集**：结合Base或Primary Index Table与eXist XQuery处理器生成结果集。 查询路由器接受XPath表达式作为输入，并在必要时为eXist数据库创建XQuery表达式。 我们还进行了一系列实验，以证明使用我们的索引结构可以优化XPath表达式。结合索引的快速重建，这种方法不仅支持快速的XPath查询，还为更新操作提供了坚实的基础。大型索引的构建时间在60到260秒之间，这允许在一天内多次重建索引，为可更新索引的追加和定期全量重建提供了基础。目前，我们的研究重点是管理更新查询，同时也在研究PIT构建成本与查询性能提升之间的关系，以对索引进行微调。未来，FAST原型的下一个版本应包含XPath和XQuery表达式的接口。 #### 3. 相关工作回顾 在存储和查询XML数据方面，有多种RDBMS（关系型数据库管理系统）相关的技术，下面为你介绍几种常见的模型： | 模型名称 | 存储方式 | 优点 | 缺点 | | --- | --- | --- | --- | | 邻接列表模型 | 存储当前节点键和父节点键 | 易于从任意节点搜索父节点 | 查找子节点、祖先节点和后代节点效率低 | | 物化路径模型 | 存储每个节点从根节点的完整路径 | 仅通过路径值即可确定当前节点位置 | - | | 嵌套集模型 | 使用左（lft）和右（rgt）列对每个节点进行索引 | 易于查询节点关系 | 插入、更新或删除新节点时需重新索引所有节点 | | XPath加速器 | 将节点索引为前序值和后序值 | 可在前后序平面中查找祖先、跟随、前导和后代节点 | 存储的XML数据有任何更改时，需重新索引所有节点 | 以下是这些模型的关系流程图： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(邻接列表模型):::process -->|存储节点键| B(存储树结构数据):::process C(物化路径模型):::process -->|存储节点路径| B D(嵌套集模型):::process -->|索引节点| B E(XPath加速器):::process -->|索引节点值| B ``` #### 4. 嵌套区间树编码与连分数 为了更高效地存储和更新树结构的XML数据，我们引入了嵌套区间树编码与连分数的方法。 - **基本结构**：嵌套区间的基本结构与嵌套集类似，但嵌套区间使用有理数表示节点。如果父节点为（p_lft, p_rgt），子节点为（c_lft, c_rgt），则满足p_lft <= c_lft且c_rgt >= p_rgt，便于查找节点关系。嵌套区间模型使用有理数集，因为整数集无法表示lft和rgt值之间的无限数量。例如，在父区间（plft, prgt）内找到一个未占用的段（lft1, rgt1），并插入子节点（(2 * lft1 + rgt) / 3, (lft1 + 2 * rgt1) / 3），插入后仍有两个未占用的段可添加更多子节点。 - **嵌套区间树编码与连分数**：基本的嵌套区间方案存在二进制编码数据大小在广度和深度上呈指数增长的问题，甚至可能导致数值溢出。为解决这一问题，我们采用了嵌套区间树编码与连分数的方法。 - **编码**：嵌套区间用有理数a/b标记树节点，其中a ≥ b ≥ 1且GCD(a, b) = 1（GCD为最大公约数）。例如，节点a = 181，b = 34可通过欧几里得算法转换为物化路径‘5.3.11’： - 181 = 34 * 5 + 11 - 34 = 11 * 3 +