基于事前约束的XML关键字查询处理技术

Keyword search is one of the hot research issues for XML data management. As existing keyword search systems only support simple keywords, the deviation between query semantics and users' query intention is observed frequently in practice, resulting in huge burden on users to identify desired information from large volumes of returned results, which we call as post-processing. Different from this processing strategy, we study to enhance a keyword query's power in describing users'query intention by applying constraints on input keywords before query processing, and solve the hard problems appeared in this situation, including (1) query hinting in real time, such that to provide users relevant constraints, and help them to formulate queries that reflects their query intentions; (2) efficient labeling schemes, indexes and parallel execution strategies for supporting different query semantics and their relationships; (3) effective result clustering and ranking strategy; (4) result subtree constructing strategy based on various requirements from different users. By solving the above problems, we will implement a prototype system, which can describe users' query intentions accurately, while at the same time, can give quick feedback to users, such that to verify the correct of the proposed theories and approaches, and finally, implement the ultimate goal of significantly reducing users' post-processing cost and accelerating the process for users to get desired information.

关键字查询处理是XML数据管理领域研究的热点问题之一。由于现有关键字查询接口仅支持简单的关键字，因此实际中常出现查询语义和查询意图偏离的情况，导致用户在查询处理后从大量返回结果中费时费力的甄别符合自身查询意图的信息（事后处理方式）。与此不同，本项目研究通过事前约束（指在查询算法执行前指定约束信息）来增强关键字的查询意图表达能力，以及解决由此带来的技术难题，包括（1）实时查询提示策略，为用户实时展示相关的约束条件，协助其输入满足查询意图的查询；（2）支持多种语义及其关系求解的高效编码、索引及并行执行策略；（3）有效的结果分组和排序策略；（4）基于用户需求多样化的结果子树构建策略。通过解决由于引入事前约束而带来的以上技术问题，搭建查询意图表达能力强、响应机动快速的XML 关键字查询处理系统，对课题所提出的理论和方法进行验证，最终实现缩减用户事后处理代价，加速用户获取所需信息的目标。

本项目通过四年的研究工作，完成了项目设定的研究目标。在关键字查询处理方面，提出一种通用的自顶向下关键字查询处理策略及相应的TDxLCA算法。TDxLCA以自顶向下的方式依次检测所有的公共祖先结点，避免了公共祖先重复处理问题；对于检测到的每个公共祖先结点，TDxLCA算法通过该结点的孩子而不是后代判断其满足性，避免了访问无用结点问题。TDxLCA算法的通用性体现在编码独立性和语义独立性两个方面。编码独立性指基于任意一种现存的路径编码，TDxLCA算法均以相同的时间和空间复杂度处理给定的查询；语义独立性指针对给定的查询，TDxLCA算法可用于处理任意一种语义。在关键字查询结果的子树构建方面，提出了RKN的形式化定义及相应的算法。该算法采用从上到下，广度优先的策略，一边求解RKN结点一边剪枝并构建结果子树，将原本构建结果子树所需的三步操作压缩为两步，获得了最小的时间和空间复杂度。提出了相应的并行处理策略以进一步提升查询处理的效率。在数据图的压缩方面，首先证明了在传递归约的基础上，等价归约可以快速求解，因而可以扩展到大图的处理上。然而，传递归约本身并不容易，已有的传递归约方法同样不能扩展到大图，为此我们提出了高效的传递规约算法，并进一步提出了线性时间的等价规约算法。实验结果显示，所提出的方法比传统方法平均处理速度快10倍以上，显著提升了算法在时间和空间方面的扩展性，可以处理大规模数据图。在可达性查询处理方面，提出了基于有向无环图压缩图，利用内嵌子树加速可达查询处理的高效算法。同时提出了利用最优生成树加速可达查询处理的算法，以及通过改进2hop标签来加速可达查询处理的算法。在k-步可达查询处理方面，提出一种双向搜索算法来加速查询处理。