基于最小相关实体子树的XML关键字查询算法.doc

--------------------------校验:_____________-----------------------日期:_____________基于最小相关实体子树的XML关键字查询算法基于最小相关实体子树的XML关键字查询算法摘要:针对目前xml关键字查询结果中包含了许多无意义的节点的问题,提出了一种语义相关的查询算法。由于xml文档具有半结构化和自描述的特点,通过充分利用节点间的语义相关性,提出了最小最低实体子树(slest)的概念,在这个概念中,关键字之间仅存在物理连接关系;为了捕获关键字之间的idref引用关系,提出基于最小相关实体子树(siest)的算法,并利用最小最低实体子树和最小相关实体子树代替最小最低公共祖先(slca)作为查询结果。实验结果表明,提出的算法能有效提高xml关键字查询结果的查准率。关键词:最小最低实体子树;最小相关实体子树;xml关键字查询;xml数据库;语义相关性*puterscienceandengineering,xi’anuniversityoftechnology,xi’0引言的普及,对xml数据的查询迅速增多。因此,如何能够简单并有效地查询xml文档成为一个研究的热点。目前,在xml数据检索方面的研究集中到xml结构化查询和xml关键字查询两个方面。用户使用结构化查询的门槛较高,除了要了解xml文档结构,还要掌握相应的查询语言,例如,xpath或xquery。用户需要利用这些精确的查询语言来描述自己需要的查询模式,查询系统则会根据用户描述的查询模式返回相应的查询结果。如图1,如果用户想要找到名为“java”的书的信息,相应的查询路径表达式为“//books/book[title=“java”]”。由于大部分互联网用户并不懂得相应的查询语言和xml文档结构,所以xml关键字查询更适合于普通用户。xml关键字查询由于其简单易用而受到普通用户欢迎,用户只需要提供有关的查询关键字就可以实现查询。目前,xml关键字查询大多数是以最低公共祖先(monancestor,lca)概念的改进作为查询结果,比如elca(exclusivelca)、slca(smallestlca)和mlca(meaningfullca),这类方法执行效率较高,但由于没有捕获xml文档中不同节点之间的类似于idref引用关系,导致查询的准确率较低。1相关研究xrank[2]是最早考虑到xml文档的分层和超链接结构及关键词二维接近概念的xml检索系统。xrank是以elca作为返回结果,elca节点是满足以下条件的节点集:删除了以该节点为根的子树中包含了全部关键字的更小子树后,原子树仍包含全部关键字。xrank提出一种基于栈的算法,通过elemrank来衡量xml元素的重要性,但xrank不区分标签和关键字,没有考虑到关键字之间可能存在的语义信息,使得该系统会返回大量无意义的结果。文献[2-3]中介绍了以slca作为返回结果的三种主流算法indexedlookupeagar(ile)、scaneagar(se)和s