TAX：用于XML的树代数全面解析

### TAX：用于 XML 的树代数全面解析 #### 1. 投影操作 对于树结构，投影可以看作是消除除指定节点之外的其他节点。在节点消除后得到的子结构中，我们期望保留输入集合中幸存节点之间原有的（部分）层次关系。 投影操作以集合 C 作为输入，同时以模式树 P 和投影列表 pl 作为参数。投影列表是模式 P 中出现的节点标签列表，可能会带有 * 符号。投影操作符的输出 πP,PL(C) 定义如下： - 输入集合 C 中的节点 n 属于输出，当且仅当存在一个嵌入 h : P → C，使得 n 与模式 P 中投影列表 pl 里出现标签的某个模式节点匹配，或者 n 是 C 中与某个模式节点 w 匹配的节点 m 的后代，并且 w 的标签在投影列表 pl 中带有 “*”。 - 当节点 n 和 m 属于输出，且在保留在输出中的节点里，n 是输入中 m 的最近祖先时，输出包含边 (n, m)。直观地说，输出树保留了输入数据树的结构，输出树中的每条边都对应于输入数据树中的一条祖先 - 后代路径。 - 输出中节点的相对顺序得以保留，即对于输出中的任意两个节点 n 和 m，若在 C 的前序枚举中 n 在 m 之前，那么在输出树的前序枚举中 n 也在 m 之前。 所有节点的内容，包括谱系，都从输入中保留下来。例如，使用图 1(b) 的模式树和投影列表 {$1,$2,$3}，对图 1(a) 的数据库进行投影操作，将得到图 2(b) 所示的结果。 单个输入树在投影操作中可能产生零个、一个或多个输出树。如果给定输入树中没有指定模式的见证，这个数量可能为零；如果从指定模式的见证中保留的某些节点之间没有祖先 - 后代关系，这个数量可能大于一。这种投影概念比关系投影更具一般性。若要确保每个输入树的投影结果不超过一个输出树，只需在模式树中添加一个标记为 $0 的新根节点，并将其与模式树的前一个根节点相连，同时将 $0 包含在投影列表 pl 中。 投影操作还可用于从输入集合中返回具有模式树嵌入的完整树。为此，同样在模式树中添加一个标记为 $0 的新根节点，将其与模式树的前一个根节点相连，并将 $0* 包含在投影列表 pl 中。 在关系代数中，处理的是“矩形”表，因此选择和投影是正交操作：一个选择行，另一个选择列。而对于树结构，数据没有相同的“矩形”结构，所以选择和投影并非那么明显地正交。不过，它们是非常不同且独立的操作，是各自关系对应操作的泛化。 下面是投影操作的流程说明： 1. 确定输入集合 C、模式树 P 和投影列表 pl。 2. 检查输入集合 C 中的每个节点，判断是否满足投影条件。 3. 根据满足条件的节点构建输出树，保留节点间的层次关系和相对顺序。 4. 若需要确保每个输入树投影结果不超过一个输出树，添加新根节点 $0 并更新投影列表。 5. 若要返回具有模式树嵌入的完整树，添加新根节点 $0 并将 $0* 加入投影列表。 #### 2. 乘积操作 乘积操作以一对集合 C 和 D 作为输入，生成一个输出集合，该集合对应于 C 和 D 中每对树的“并列”。具体来说，C × D 生成的输出集合如下： - 对于 C 中的每棵树 Ti 和 D 中的每棵树 Tj，C × D 包含一棵树，其根是一个新节点，标签名为 tax prod root，谱系为空，没有其他属性或内容；其左子节点是 Ti 的根，右子节点是 Tj 的根。 - 对于新根节点的左子树和右子树中的每个节点，所有属性值（包括谱系）都与输入集合中的相同。 新创建的根节点使用空谱系，反映了这些节点并非源自输入集合。由于数据树是有序的，C × D 和 D × C 并不相同。与关系代数不同，在关系代数中顺序对元组无关紧要，但对于对应于 XML 文档的数据树来说顺序很重要。和关系代数一样，连接操作可以表示为乘积操作后接选择操作。 乘积操作的流程说明： 1. 确定输入集合 C 和 D。 2. 遍历 C 中的每棵树 Ti 和 D 中的每棵树 Tj。 3. 为每对树 Ti 和 Tj 创建一个新的根节点，标签为 tax prod root，谱系为空。 4. 将 Ti 的根作为新根节点的左子节点，Tj 的根作为新根节点的右子节点。 5. 保留左