XML关键词搜索的替代查询生成及其优化

### XML关键词搜索的替代查询生成及其优化 #### 1. 引言 XML已成为半结构化文档广泛接受的标准，被用作数据描述框架。支持用户从大量XML数据中检索有用信息是很有意义的。如果支持如Web搜索中的关键词搜索这种用户友好的方式，用户就可以向XML数据库提交查询并获取各种信息。 虽然已有大量关于XML关键词搜索的研究致力于从大量XML数据中高效检索结果，但到目前为止，提升结果质量的支持方法尚未得到充分探索。用户通常很难在一次尝试中就获得符合其搜索意图的结果。在这种情况下，他们不得不多次优化查询并进行搜索，直到获得他们想要的结果。因此，在XML关键词搜索中，不仅支持高效的搜索方法，还支持能优化用户查询和/或帮助他们更全面理解结果的方法是很有必要的。 理解XML搜索结果的相关研究包括提取XML子树的摘要以及XML子树的一组区分特征。在关系数据库领域，也提出了几种不同的方法，如数据库结构挖掘、意向查询回答和频繁共现术语的发现等。 在XML关键词搜索中，存在一个已知问题，即一些输入关键词会匹配到用户未预期的节点，从而导致检索出的结果与用户的搜索意图不匹配。这涉及两个因素：一是关键词既可以作为XML元素名称出现，也可以作为其他节点的文本值出现；二是关键词可以作为不同元素节点的文本值出现并具有不同的含义。 为了解决这些问题，主要有以下四个方面的贡献： 1. 考虑关键词的歧义性，定义了XML关键词搜索中生成替代查询的问题。 2. 定义了近似替代查询以及两个评估近似替代查询的指标。 3. 实现了朴素和优化两种方法来获取近似替代查询，实验表明优化方法更有效。 #### 2. 相关工作 在XML关键词搜索领域，为了找到XML数据中的最小子结构，已经进行了大量研究。例如，最低公共祖先（LCA）及其相关变体，如最小LCA（SLCA）、排他LCA（ELCA）和有意义LCA（MLCA）等都得到了研究。不过，这些工作大多没有考虑关键词作为元素名称和文本值出现的两种歧义性。 XReal系统采用了一种信息检索（IR）风格的方法来解决这些歧义，但很难确定用户的搜索意图，除非它们被唯一标识。因此，将结果按解释分类并提供给用户是更好的选择。 此外，还有一些其他相关的研究： - Huang等人提出了XML片段作为XML子树的摘要，以帮助理解XML搜索结果。 - Liu等人提出了区分特征集（DFSs），用于反映搜索结果中最重要的特征，帮助用户进行比较。 - 数据库结构挖掘旨在发现数据库表中的结构关系。 - 意向查询回答通过添加额外信息来增强查询结果，帮助用户理解。 - Tao等人提出发现频繁共现术语，以使用这些术语优化输入查询。 - 查询输出（QBO）是一种数据驱动的方法，用于从关系模型的结果中获取实例等价查询（IEQs），但难以应用于XML关键词搜索中的IEQ发现任务。 近似替代查询可以看作是获取近似查询的任务。信息检索领域的查询扩展方法旨在通过放宽给定的输入关键词来获取更多相关信息，但由于不考虑结构信息，无法应用于XML关键词搜索的近似替代查询生成。XML搜索中使用路径查询的松弛方法通过放宽结构条件来获取精确和近似结果，但我们的目标是通过挖掘XML子树并考虑XML树中的信息结构来生成近似查询。 #### 3. 预备知识 将XML树建模为有序且带标签的树。除叶子节点外，XML树的每个节点v对应一个XML元素节点，并带有标签λ(v)。为简单起见，将属性节点视为元素节点。每个节点v都有一个唯一的ID，使用Dewey顺序作为节点ID，因为它在栈算法中表现良好。节点v的Dewey顺序表示为dewey(v)，以v为根的子树表示为st(v)或st(dewey(v))。 利用倒排列表来生成替代查询。单词k的倒排列表通常是直接包含k的节点列表。Dewey倒排列表（DILs）是带有Dewey顺序标签的XML树的倒排列表。创建扩展的DILs，每个条目包含： 1. 文本值包含k的节点的Dewey顺序和元素名称。 2. 元素名称为k的节点的Dewey顺序。 将关键词及其父元素名称的对表示为带标签的关键词。倒排列表中的每个条目s对应一个节点，称为条目节点s。 给定XML