简介:关于索引查询方面的论文题目、论文提纲、索引查询论文开题报告、文献综述、参考文献的相关大学硕士和本科毕业论文。
摘 要：压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法.针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引.当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组.而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点.新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题.
关键词：压缩树索引 正排索引 倒排索引值谓词Ctree
1. 引言
XML作为论文范文的网络数据形式,受到了人们的普遍关注.如何实现对大规模XML数据的有效管理和利用,如何在XML数据源中对大量的信息进行有效地查询,成为了备受关注的研究热点.XML数据作为一种半结构化性质的数据形式,它的查询需要一种更灵活的查询机制.
以往对XML数据的查询主要有两种方法.一种方法是建立XML文档树的路径索引,并通过路径索引加速XML查询的计算.另一种方法是对XML文档树中的结点（或边）进行编码,通过编码直接判断结点之间的结构关系或元素内容.对XML索引的研究主要基于路径记录和结构索引、树节点编码的思想.但是现有的索引技术都存在着或多或少的不足.例如：DataGuaide[l索引可以在与路径长度成比例的时间中求出该路径到达所有对象的集合,但它只适用于简单的自根开始的路径连接,对于从任意节点开始的查询效果不是很好.Index Fabric[2]索引存储了XML数据的层次结构信息,统一处理了有模式和无模式信息情况下的XML数据的检索,并且因为其结构是平衡的,因而不同的访问所需的查询代价几乎相同,这样就使得对XML数据的查询和更新所需要的时间与层次相关而不是与索引关键字的长度相关.但因为它只保留了有文本值的元素节点的信息从而丢失了元素节点间的结构关系.APEX[3]能够有效地处理某些相对路径查询,它的索引是基于查询频度的,对频繁使用路径创建索引.当查询频度有变化时,APEX索引可以进行有效地更新以适应查询频度的变化.但它对于带有元素值或属性值的查询表达式的处理效率较低.XISS索引通过将原始查询语句分解为子表达式,然后分别针对这些子表达式实现查询,最后对这些中间结果进行联结获得查询结果集.从而能较好地支持含通配符的查询语句.但是,它是对每一个中间结果进行联结后得到最终查询结果.虽然这样一种方法的确能够解决通配符问题,可是,这种中间结果的联结很有可能是非常耗时的,特别是对于长路径的简单表达式.
Ctree树索引是一种新的压缩树(Compact Tree),它是一个包含组级和元素级的两级双向树.它的两级双层结构能够在搜索的时候极大的减少搜索空间的范围.同时,由于组值的类型是一致的,可以进行值索引,谓词过滤时能达到很高的效率.但是,查询出路过程中向上匹配与向下匹配仍然不是很理想.
2.相关知识
(1)正排索引.正排索引入口为文档编号,给出文档编号通过正排索引可以找到该文档所包含的所有词项term及词项的出现频率t.
(2)倒排索引.倒排索引入口为词项term,通过倒排索引可以找到包含每个词项term的文档集合,称为记录表( posting list),posting list中包含文档号及term在该文档中出现的频率和位置.
(3)压缩树.压缩树(Ctree[5])包含组级和元素级两层结构.组级提供了一个简洁的结构概要.元素级则保存了孩子父亲连接的详细信息.而每个组的孩子到父亲的映射用一个数组实现.
压缩树Ctree是一棵有根树,树中的每一个节点g成为一个组,每个组包含一个元素数组记为g．pid[],详细描述如下：
(1)每个组都有一个标识符、一个名字,分别表示为g．id和g．name.
(2)边的方向是从根到叶子,如果从gl到92有一条边,则91是g2的父亲,92是91的孩子,如果从91到g3有一条路径,则91是g3的祖先,93是91的后代.
(3)每个组包含一个元素数组g．pid[],g．pid[]的数组索引k表示g中的一个元素,表示为g：k.g．pid[k]的值指向g的父亲gp中的一个元素,并且gp：g. pid[k]是g:k的父亲元素.
索引:删除索引界面方式创建和索引对[www.taohv.cn]查询的影响027
(4)任何两个元素g:kl、g:k2,如果kl<,k2,那么g．pid[ kl]≤g. pid[ k2].
3. 索引的改进过程
图l是一个XML数据树T[6].T中每一个结点通过id、label和value来表示标识、标签名和元素值,其中value是可选的,为了区分其与子节点,value用点线相连.
为了构造T的压缩索引树,我们首先生成T的有序路径摘 要.对于一棵数据树,路径摘 要上的每一个结点都称为一个组,每个组都确定地对应树中的一条标签路径.组包含了所有树中具有相同路径的结点,当组按它们的先序遍历序号有序时称之为有序路径摘 要.树T的有序路径摘 要如图2(a)所示,点框表示一个组,框中的数字表示具有相同路径的结点.路径摘 要可看作是对数据树约简的过程,但它并没有记录单个节点之间的关系,因此不能处理多分枝查询,所以在此基础上增加元素级关系.
获得数据树的有效路径摘 要后,由前面所介绍的压缩树的结构,构造数据树T的压缩索引树如图2(b)所示,树中每个组有一个数组,数组值用逗号隔开显示在框内,数组索引标号是值的位置,从0开始.
改进的索引需要先对正排索引和倒排索引做一些修改：正排索引中的入口由文档编号改为压缩树中的组节点( group),词项改为该组节点的子节点,给出组标识通过正排索引查找该组的子节点；同样的方法,倒排索引的入口为压缩树的元素,通过倒排索引可以查找包含每个元素的组.
在改进的倒排索引中,将原来所存放的文档号、term在文档中出现的频率和位置相应的改为存放：元素在所在组的数组中的位置,元素所在组的父节点,元素的value值（如果存在的话）.
针对数据树T构造的正排索引和倒排索引如图3所示.
4.基于Ctree树索引的查询处理
首先,我们把对XML的查询Q表示成查询树模型,树中节点表示Q中的标签,单箭头的边表示指向孩子,双箭头的边表示指向子孙.起过滤作用的值谓词描述在对应节点上.假设每一个查询只返回一种节点,即目标节点,将其目标节点用方框标示出来.以查询“/dblp/article[ contains(//au-thor,“John”)and year>, 94 ]/title”为例,其查询树Q如图4所示,图中点线箭头表示结果匹配的方向.
一个查询转换成查询树Q之后,使用Ctree索引数据来解析查询Q可以通过以下三个步骤：
(l)定位与查询相关的组,即在Ctree索引树T的组级中寻找满足查询结构的组.如查询Q相关的组有( dblp,article,author,year,title),对应的gid集为(O,1,3,4,2).因此,便减少了查询空间,尤其关注一下组author,其对应的gid为3,“//author”本身具有不确定性,而至此已经锁定至第3组,所以不再需要考虑搜索其他子孙节点,从而提高了效率.
(2)对于每一个相关组,根据值谓词找出符合条件的元素.当获得值谓词的值value和相关组的gid后,调用search( value,gid)方法找出所需元素.例如,在查询Q中的两个值谓词：author等于“John”和year>, 94.对于第一个谓词,通过第一步查询节点author映射到组3,调用search(“John”,3).返回元素3:0和3:1（即图1中的节点4和节点15）.同理,对于第二个谓词返回元素4:0（即节点5）.
(3)根据第二步选出的符合值谓词的元素,使用改进的正排索引和倒排索引进行匹配并返回查询结果.如查询Q在找出“author等于‘John”’与“year>, 94”的元素之后．使用倒排索引找出其父节点.根据所得的父节点使用正排索引,返回该父节点所有的title子元素.
查询处理的算法：输入：T为值索引的Ctree树,Q为查询树；输出：T中满足Q的元素集.
算法为
(1)使用GroupFinder获取T组级中与Q相关的组集合.
(2)对获得的每个组,执行操作：①根据所给的值谓词,调用search( value,gid)选出符合条件的元素；②调用正排索引和倒排索引对已经获得的目标组和元素进行匹配；③输出元素集.
5. 索引性能评估
为了证实改进的Ctree索引XML数据的有效性,我们利用DBLP数据集进行测试,比较改进的Ctree和原Ctree索引及路径索引（Index Fabric）.我们用C++实现相应的方法,测试的路径表达式如表1所示.
三种索引的实验结果在图5中显示,Ql是一个没有谓词的简单查询.对于Q1,三种方法有相同的性能.
对于其他查询,Ctree明显比路径索引有效.其中一个原因就是以上三个查询都有值谓词“D论文范文id”,这就降低了路径索引的速度.因为路径索引需要对元素author和包含“D论文范文id”的元素进行连接操作.而改进的Ctree通过引入正派索引和倒排索引可以在查找包含“D论文范文id”的元素时,减少所需的时间,提高查询效率.
6.结束语
本文针对Ctree索引在查询过程中向上匹配与向下匹配操作过程不理想,耗时较多的问题,引入正排索引和倒排索引,提出了改进的方案.改进的索引方法不仅很好的解决了匹配问题,而且保留了Ctree索引的优点.不足之处在于,虽然该方法处理简单路径查询时效率较高,但是对于复杂路径查询处理结果不够理想,需要进一步改进.
总结：本论文主要论述了索引查询论文范文相关的参考文献,对您的论文写作有参考作用。
索引引用文献:
[1] 容易写的工程索引工程论文选题 工程索引工程毕业论文题目怎样定
[2] 工程索引相关论文题目 工程索引论文题目哪个好
[3] 工程索引学位论文参考文献 工程索引期刊参考文献哪里找
