基于语义的XML关键字查询

贾 颖

（山东工商学院计算机基础教学部，山东 烟台 264005）

基于语义的XML查询

贾 颖

（山东工商学院计算机基础教学部，山东 烟台 264005）

针对XML数据的

查询问题，考查了已有的查询技术的优势和不足，提出了基于语义的XML

检索算法。对用户输入的

进行分类，分为条件

和结果

。条件

只用于限定查询范围，不出现在结果集中。给出了语义相关节点对的概念和判定方法，并提出了基于

分类和语义相关节点对的XML数据查询算法。

XML

查询；

分类；语义相关节点对

XML数据一种介于HTML网页数据和传统关系数据库数据之前的一种形式，它是在Web数据激增的背景下产生的一种新的数据描述形式。XML能有效地存储和管理Web上的数据(文档)，使其既能被高效地操作和维护，又能在 Internet平台上方便地表示和交换。它比HTML网页上的数据多了语义信息。HTML标签是用来描述数据显示格式的，数据的语义信息靠数据自身表达；而XML数据用自定义的标签标明了数据的语义。XML是纯文本数据，不受操作系统和软件平台的限制，比关系数据库又多了灵活性，所以非常适合于电子数据交换、电子商务等Web领域。

随着互联网上XML数据的增多，XML数据检索问题一直是一个研究热点，其中XML数据检索又是其中的一个重要的研究方向。它与传统的HTML

检索有所不同，HTML

检索要经历如下过程：爬网，通过网页中包含的超链接搜集网页；从搜集到的网页中提取

，建立词典；建立单词到文档映射关系的倒排索引；根据某种检索模型来计算用户查询与网页内容的相关性（相似性），例如向量空间模型；对检索结果进行排序，返回最相关的Top-K个结果。XML

查询是一种介于HTML

查询和数据库结构化查询之间的一种查询形式。因为 XML是一种半结构化、自描述的数据，它定义的标签包含了语义信息，它的树形结构提供了结构信息。所以对于XML数据的查询比HTML查询更为快速，结果也更精确。

1 研究现状

XRank搜索引擎：XRank[1]是Connell大学的的研究者提出的XML搜索引擎。XRank的缺点是对用户输入关键字的格式没有要求，是单纯的文本格式关键字，也不要求返回类型，虽然可以兼容HTML检索，但也造成查询准确度不高[4]。并且，XRank返回以结果集中节点为根节点的整个子树，里面包换了大量对用户无用的信息。优点是Xrank利用Dewey编码的特性，提出了改进版的倒排索引DIL、RDIL和HDIL，存储空间大大节省。Xrank借鉴了PageRank算法的思想提出了用于计算元素重要性的ElemRank算法，该算法考虑了沿包含边的正向传播、反向传播以及元素间引用的影响。

XSEarch[2]搜索引擎是支持语义的XML搜索引擎，它要求用户输入的包含返回结果的标签。XSEarch试图从语义的角度去解决查询结果中存在无效结果的问题。它通过判断两个元素是否关联来解决无效结果问题。判断元素是否关联的标准是，如果两个节点的最小公共子树除了这两个节点之外，不包含其他同名节点，那么认为这两个节点是关联的。

Xseek[3]最主要的贡献是将用户输入的分类，分为谓词回结果为以SLCA为根节点的子树。SLCA（Smallest Lowest Common Ancestor）是指包含所有

的节点集，而且这个节点集中的任一节点的子孙节点都不能再包含所有查询

。Xseek从一定程度上限制了结果集的大小，但因为返回的结果集中每一个逻辑单元都包含全部的

，同样会造成返回结果集不必要的增大。

和结果

，并提出了分类的规则：如果一个输入

和一个名称节点相匹配，并且不存在一个输入

和这个名称节点的子孙值节点相配，那么这个输入

就是结果

，其余的

是谓词

。Xseek的返

文献[4]提出了借鉴Xseek中把查询分类的思想，把查询

分为谓词

和结果

；定义了相似节点对（SNP）的概念，提出了发现SNP的算法和有效相似节点对(MSNP)的判定方法，用于寻找

的匹配节点；提出了构建名称节点、值节点和主Dewey码节点的索引结构，以加快节点和其Dewey码之间的相互查找。

2 基于语义的XML查询

将输入分类，是提高检索精度的最经济和高效的途径。借鉴数据库结构化查询的方法，把查询

分为结果

和条件

。然后在XML数据集的索引中找到所有与结果

的匹配节点。通过条件

的限定，筛选出满足条件的节点，得到一个节点集。返回以节点集中的每一个节点为根节点的子树作为结果树。

2.1 数据描述

图1是一个包含节点Dewey编码的XML文档片段，Q1,Q2是查询示例，见图2。

图1 XML文档片段图

图2 查询示例

2.2 查询表达式描述

首先，借鉴XSeek对查询进行分类的思想。文献[4]提出让用户在输入时指明

的类型，也就是按照Result_keywords_expression，predicate_kewords_expression的语法格式输入,其中 Result_keywords_expression的形式为“[keywords.{[keywords]}”；predicate_kewords_expression的形式为“[keywords].or &{[keywords]}”；其中keywords的形式为“keyword ‘keyword’”，前面是标签名称，后面是对应的值。按照上面的格式，语句Q1、Q2应改写为：

Q1 [position]，[name ‘Yao Ming’]

Q2 [name]，[position ‘guard’] & [nationality ‘U.S.’]

应该说这种方法是可行的，因为 XML虽然是自描述语言，但它的标签命名规则已经有了很多行业标准[5]，例如对数学符号进行编码的MahtML、化学领域的标记语言CML、W3C推荐的用于描述二维图形的标记语言 SVG、金融领域的XBRL（可扩展商业报告语言）等。对于熟悉本领域知识的人，给出符合规范的查询条件是可以做到的，而这样做的好处是大大提高了查询精度。

2.3 创建高效索引

为XML数据建立高效的索引，是影响XML数据查询速度的重要因素。我们用哈希表来为XML数据的名称节点和值节点分别建立索引，链地址法处理冲突，记录每个标签和值出现在哪些节点和这些节点的Dewey码。笔者通过查找哈希表，可以得到与关键字匹配的节点的dewey码集合。

另外为了能快速进行Dewey码到的反推，笔者建立主Dewey码索引，将XML文档中所有的节点以Dewey码为主键存储到B+树中，存储的形式是（Dewey，keyword）。

2.4 查找语义相关节点对（SRNP）

判断两个节点语义相关的方法有：MLCA[6]认为，XML文档中的节点只与某个节点集合中与其最近的节点语义相关。而XSEarch提出了Interconnection的概念，指出对于XML文档中的两个节点，若在连接这两个节点的路径上没有出现相同标签的节点，则认为它们语义相关的。文献[4]提出了基于Dewey码的相似节点对（SNP）的概念，是通过比较两个

集合S1，S2中的任意两个节点ni，nj的公共最长前缀predewey来的到SNP。

定义1 两个节点ni和nj，ni∈S1 ，nj∈S2，它们的最长公共前缀记为predewey，其中由点号分隔的整数个数为ni和nj的相似度，记为S(ni，nj)。

定义2 节点集S1和S2中节点个数分别为m、n，∀ni∈S1，∃nj∈S2满足条件：

S(ni,nj)≥S(ni,nk) nk∈S，k=0,1,…j-1,J+1,…,n-1，那么称ni、nj为节点集S1、S2的一对SNP。

这里的SNP就是语义相关的节点对SRNP。针对图1所示的XMl文档，以Q2为例，演示基于语义相关节点对的查询算法，如图3所示：

图3 基于语义相关节点对的查询算法

2.5 返回结果集

最后，返回以结果集（0.2.1.1.0，0.30.1.0.0）中每个节点为根节点的子树，即

可以看到，基于分类和语义相关节点对查找的算法可以得到用户关心的最小XML片段。

3 结束语

在考查了目前主要的XML查询技术的基础上，提出了基于

分类和语义相关节点对（SRNP）的查询算法。该算法对用户输入

的模式进行了限定，并将查询

划分为条件

和结果

。条件

只用于限定查询范围，而不出现在结果集中。定义了语义相关节点对的概念和发现方法。通过在

对应的节点集中查找语义相关节点对，最后得到结果集。返回以结果集中节点为根节点的子树，即为查询结果。实践证明，该算法在查询速度和精度方面都有较好的表现，但在查询语法的扩展，索引结构的优化，查询处理的优化方面还需要进一步的提高。

[1] L.Guo,F.Shao,C.Botev,J.Shanmugasundaram. XRank: Ranked keyword search over xml documents[C].Proceeding of the ACM SIGMOD International Conference on Management of Data,2003:16-27.

[2] S.Cohen,J.Mamou,Y.Kanza and Y.Sagiv. XSEarch:.semantic search engine for XML[C].Proceedings of International Conference on Very Large DataBases, 2003: 45-56.

[3] C.Botev,J.Shanmugasundaram.Context-Sensitive Keyword search and ranking for XML[C].Proceeding Of the International Workshop on the Web and Database,2005: 115-120.

[4] 孔令磊.面向 XML文档的查询研究[D].北京:北京交通大学,2006.

[5] 周军峰,孟小峰.XML查询处理研究[J].计算机学报,2012,35(12):2459-2479.

[6] Y.Li,C.Yu,H.VJagadish.Schema-free XQuery[C].Proceeding of the International Conference on Very Large Data Bases, 2004:72-83.

XML keyword query based on semantic relevancy

Concerning the keyword search on XML Data, analyzed the advantages and the shortage of the keyword search method and put forward.new algorithm for keyword search on XML data. We classified keywords into conditional keyword and result keyword. Conditional keyword is used to restrict the range of querying and will not appear in the results sets. Defined the Semantics relevant Node pair (SRNP) and brought forward the SRNP finding method. And then gave the XML Data keyword search algorithm based keywords classify and SRNP.

XML keyword query; keyword classify; SRNP

TP311.13..

A....

1008-1151(2015)08-0005-03

2015-07-10

山东省科技发展计划项目（2014GGX101044）；山东工商学院青年基金项目（2013QN093）。

贾颖(1979－)，女，山东工商学院计算机基础教学部讲师，硕士，研究方向为网络安全与数据检索。