对于一个XML文档中的每一个元素e,假设我们将一个三元组与之

对于一个XML文档中的每一个元素e,假设我们将一个三元组与之关联< begin,end,levl>,其中 begin表示e在文档中的开始位置,用其在文件中的字节偏移量来表示,end表示元素的结束位置,而 level表示e的嵌套层数,其中根节点的层数为0。
(1)用这个三元组的形式来表达当元素el分别为①e2的祖先;②e2的双亲的条件。
(2)假设每一个元素都有一个系统生成的内部id,并且对于每一个标签1我们存储了个id列表记录所有标签1的元素,即,对于每个标签的id倒排列表。我们将三元组和元素id存储在一起,并且将id列表按照元素的开始位置排序。现在,假设我们想对路径表达式a//b求值。连接的输出形式必须是<id,id>对,其中id和id分别为标签名为a的元素e的id,和为标签名为b的元素e的id。结果必须按照复合码<e的开始位置
(3)假设我们有k个整数的有序列表,其中k是一个常数。并假设其中没有重复,即,每一个值只在一个列表中出现一次。设计一个算法来合并这些列表,其中的比较次数应该和输出列表的大小成线性关系
(4)接下来,假设我们要对连接a//a2//…//a求值(k为常数)。连接的输出必须是k元列表<idn,id,…id>,其中i为标签名为a的元素e的id,并且e是e+1的祖先(1<=i<=k-1),列表必须按照复合码<e的开始位置,…,e的开始位置>排序。扩展你在第2和第3题中设计的算法来计算这个连接。算法中的比较次数要与输入和输出数据量成线性关系