文档数据库中的查询评估：基于有序树嵌入的策略

### 文档数据库中的查询评估：基于有序树嵌入的策略 #### 1. 引言 在文档数据库的查询评估中，树模式查询（TPQ）的嵌入是一个重要问题。例如，当查询一个包含特定类型和文本内容的节点时，需要准确判断查询树能否嵌入到文档树中。对于TPQ P嵌入文档T的情况，其嵌入规则如下： - 对于P中的每个节点v，v和f(v)类型相同，且f(v)满足与v相关的所有当前谓词。 - 若在P中v → u，则在T中f(u)是f(v)的子节点，且f(u)满足与v相关的所有c - 谓词；若在P中v ⇒ u，则在T中f(u)是f(v)的后代节点，且f(u)满足与v相关的所有d - 谓词。 近年来，针对此类XML查询评估开展了大量研究，以下是几种相关方法及其特点： | 方法 | 时间复杂度 | 特点 | | ---- | ---- | ---- | | 基于元素和单词的反转 [8] | 最坏情况O(nm) | n和m分别是T和P中的节点数 | | 基于路径和单词的反转 [5] | 最坏情况O((n⋅h)k) | 引入路径索引，h是文档树的平均高度，k是连接次数 | | 转换为字符串匹配问题 [6, 7] | O(n⋅m⋅h) | 通过对查询树的兄弟节点排序实现多项式时间复杂度，但可能因查询树和文档树排序不同找不到嵌入，结果可能不正确 | | 表示为解析树并自底向上或自顶向下评估 [1] | 自底向上策略需O(n5⋅m2)时间和O(n4⋅m2)空间，自顶向下算法相同 | 同一作者的另一篇论文 [2] 称该问题是NP - 完全的，存在争议 | 本文提出了一种基于有序树嵌入的新算法，其时间复杂度为O(n⋅m)。 #### 2. 基于有序树嵌入的策略 ##### 2.1 基本概念 为了方便处理，引入森林的概念。森林是不相交的有限树的有限有序序列。树T由根节点root(T)和森林 <T1, ..., Tk> 组成，T1, ..., Tk是T的子树，k是根节点的出度。树可表示为 <t; T1, ..., Tk>，T1, ..., Tk的根节点是t的子节点且互为兄弟节点。 树和森林的遍历有前序和后序两种方式，节点的前序和后序编号分别用pre(v)和post(v)表示。通过前序和后序编号可以判断节点的祖先关系和左右顺序： - 引理1：设v和u是森林F中的节点，v是u的祖先当且仅当pre(v) < pre(u)且post(u) < post(v)。 - 引理2：设v和u是森林F中的节点，v在u的左侧当且仅当pre(v) < pre(u)且post(v) < post(u)。 有序树嵌入的定义如下： - 定义1：设P和T是有根标记树，有序嵌入 (f, P, T) 是一个单射映射f: V(P) → V(T)，满足： - 标签保存条件：label(v) = label(f(v))。 - 子节点条件：若 (v, u) 是c - 边，则f(v)是f(u)的父节点。 - 祖先条件：若 (v, u) 是d - 边，则f(v)是f(u)的祖先。 - 兄弟节点条件：v在u的左侧当且仅当f(v)在f(u)的左侧。 - 定义2：设P和T是树，P在T中的根保留嵌入是一个嵌入f，使得f(root(P)) = root(T)。若存在根保留嵌入，则称T的根是P的一个出现。 以下是有序树嵌入的流程mermaid图： ```mermaid graph LR A[开始] --> B[判断节点v和u的标签是否匹配] B -- 是 --> C[判断边类型] C -- c - 边 --> D[检查f(v)是否是f(u)的父节点] C -- d - 边 --> E[检查f(v)是否是f(u)的祖先] D -- 是 --> F[继续检查其他节点] E -- 是 --> F B -- 否 ```