基于签名的高效XML数据集合关系搜索方法

### 基于签名的高效 XML 数据集合关系搜索方法 #### 1. 引言 XML 对象的典型特征是将数据值和其结构封装在一个单元中，这种数据与结构的封装便于数据交换。XML 正成为众多应用领域表示异构信息的首选格式，如电子数据交换、多媒体信息系统等。随着 XML 的广泛应用，对 XML 数据的存储和基于内容的检索提出了大量技术要求，许多问题仍待有效解决。 目前，XML 查询处理的主流研究集中在开发尊重结构的索引算法，结构或包含连接算法较为流行，它们都利用了基于区间的树编号方案。然而，搜索 XML 组件（节点和/或值）之间的关系仍是一个新的重要问题。用户可能对 XML 结构了解模糊，使用传统要求精确指定搜索路径的语言会导致搜索结果不准确和计算成本增加。 已有一些基于数据集合未知结构的搜索策略尝试。例如，[GS98] 提出了图结构数据中的邻近搜索算法，但性能是主要问题；[SKW01] 为 XML 数据集合定义了最近概念查询，使用 meet 运算符，但响应时间受节点实际距离影响大；[CMK+03] 提出了语义搜索引擎 XSEarch，基于简单查询语言，返回语义相关的文档片段。 本文的方法可视为 [SKW01] 和 [GS98] 的扩展或泛化，使用树签名概念实现高效的关系搜索，树签名已在传统 XML 搜索中取得良好效果。 #### 2. 树签名 树签名的目的是维护 XML 树结构的有效空间表示。将 XML 数据树 T 视为有序、有根、带标签的树，使用前序和后序排名进行编码。 - **基本（短）签名**：树 T 有 \(n\) 个节点的基本签名格式为 \(\text{sig}(T) = \langle (p_1, q_1, \text{name}_1), (p_2, q_2, \text{name}_2), \cdots, (p_n, q_n, \text{name}_n) \rangle\)，其中 \((p_i, q_i)\) 是节点的前序和后序排名，\(\text{name}_i\) 是节点名称。 - **扩展签名**：扩展签名是一个序列 \(\text{sig}_e(T) = \langle (p_1, q_1, \text{name}_1, f_1, a_1), (p_2, q_2, \text{name}_2, f_2, a_2), \cdots, (p_n, q_n, \text{name}_n, f_n, a_n) \rangle\)，其中 \(f_i\) 是指向第一个后续节点的指针（前序值），\(a_i\) 是指向第一个祖先（父节点）的指针。 给定一个节点 \(v\)，其他节点可分为四个不相交的子集：后代 D 节点、后续 F 节点、前导 P 节点和祖先 A 节点。树签名还能有效支持树操作，如叶子检测、路径切片、（子）树包含测试等。计算两个节点的最低共同祖先（l.c.a.）可通过递归跟随 \(fa\) 指针找到第一个满足条件的节点。 子签名是通过签名对 T 的一种专门（受限）视图，保留了 T 中节点的原始层次关系，但不一定形成树。 #### 3. 结构搜索查询 ##### 3.1 结构搜索查询模型 结构搜索查询 SS_Q 定义为节点指定表达式的合取范式：\(SS\_Q = \bigwedge_{i = 1}^{k} E_i\)，其中每个 \(E_i\) 是 XPath 表达式，确定作为关系发现起点的候选节点。查询结果是搜索数据树的一组树枝，不同合取项中符合条件的节点之间的结构关系在树枝中明确显示。 具体来说，查询答案是数据树的子树（树枝）集合。设 T 是数据树，SS_Q 是包含 \(k\) 个合取项的结构搜索查询。若存在节点模式 \(\mathcal{P} = \{v_1, v_2, \cdots, v_k\}\)，其中每个节点 \(v_i\) 在不同合取项中符合条件，且所有节点共享一个共同祖先，则合格树枝 \(\mathcal{T}\) 是 T 中由 \(\mathcal{P}\) 诱导的子树，可能包含额外的诱导节点，直到它们的 l.c.a.（树枝的根）。 例如，查询 \(\text{//person[@name = 'Ted']} \land (\text{//person[@name = 'John']} \lor \text{//person[@name = 'Jack']})\)，合格模式是成对的，结果树枝可能因具体节点对而异。 在某些情况下，可能需要进行级别受限的结构搜索，即找到根节点级别至少为某一值的树枝。例如，对于 DBLP XML 数据集，排除根元素 <dblp> 进行结构关系搜索更有意义，将这种查询表示为 \(SS\_Q_{l}\)，表示合格树枝的根节点级别应大于或等于 \(l\)。 ##### 3.2 查询评估原则 假设一个 XML 文档集合和一个 \(SS\_Q_{