基于bloom+filter的路径表达式查询处理

《基于bloom+filter的路径表达式查询处理》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y9555皇O槿旦大学博士学位论文学校代码学号基于BloomFilter的路径表达式查询处理1024602t021088BloomFilter——basedPathExpressionQueryProcessing院系：信息科学与工程学院专业：姓名：指导教师：完成日期：计算机软件与理论宫学庆周傲英教授2006年4月15日中文摘要近年来，XML语言已经成为了互联网上数据表示和交换事实上的标准。随着Web服务和个性化信息订阅等应用的蓬勃发展，越来越多的信息以XML的格式通过网络被发布和交换。在这些应用中，XML数据

2、以数据流的形式不断地快速到达，而针对XML数据的查询是大量的路径表达式，传统的查询处理技术在性能上已经不能够满足应用的需求。在XML数据流上对大量的路径表达式进行查询处理是科研技术人员所面临的一个新的挑战。本文围绕XML数据流的查询处理问题展开研究工作，分别探讨了针对简单路径表达式和复杂路径表达式的查询处理技术，提出了新的处理方法，并通过实验验证了所提出方法的有效性和高效性。同时，本文就XML数据流处理引擎的设计进行了探讨，并实现了一个原型系统。论文的主要贡献可以总结为如下几点：·本文首先提出了将BloomFi

3、lter结构应用于解决XML数据流过滤问题的方法，该方法可以有效地支持对简单路径表达式中的通配符””号和后代轴“／／”的处理。同时本文设计了前缀过滤的方法，用于减少解析过程中所生成候选路径的数量，提高过滤处理的性能。详尽的对比实验表明，本文提出的方法在创建路由表时的性能和所创建路由表的大小两个方面明显优于已有的处理方法。同时，在查询集很大并且XML文档深度相对较小的情况下，本文提出的方法在过滤性能上也要优于已有的方法。·本文提出了将包含有分支结构的复杂路径表达式分解成一组简单路径表达式，在对简单路径表达式进行过

4、滤处理的基础上，实现对复杂路径表达式进行查询处理的方法。与已有的方法不同，本文所提出的方法以简单路径过滤引擎输出的查询字符串流作为输入，可以支持对元素内容约束的处理，同时可以以连续查询(ContinuousQueries)的方式实现对复杂路径表达式的查询处理。本文通过实验将所提出的处理方法与已有方法进行了对比，证明该方法在对复杂路径表达式的查询处理上具有较好的性能。·本文在简单路径表达式和复杂路径表达式查询处理技术的研究基础之上，设计和实现了一个XML数据流处理引擎一一XSTRfXMLSTReamProcess

5、ingEngine)原型系统，并对该系统的实现进行了介绍。XSTR系统可以被作为中间件应用于针对XML数据流进行处理的应用系统中。综上所述，本文就XML数据流的查询处理技术进行了深入的探讨和研究，提出了不同于已有方法的新的技术和方法，并通过实验对所提方法的有效性进行了验证。本文的研究工作，促进了XML查询处理技术的发展，具有现实的应用价值。关键词：XML数据流、路径表达式、查询处理、连续查询分类号：TP31111AbstractInthepastseveralyears，XMLhasbeenthede如ctos

6、tandardfordatarepre-sentationandexchangeOiltheweb．Itiswidelyappliedintheemergingapplicationsystems．such柏Webservicesandpersonalizedcontentdelivery．Intheseapplica，-tions，plentyofpathexpressionsareprocessedagainstXMLdocumentsthatarriverapidlyinstreamform．Effici

7、entqueryprocessingonXMLstreamhasbeenaveryimportantresearchchallenge．Inthisdissertation．wefocusontheresearchrelatedtoqueryprocessingonXMLstream．Somenovelmethodsareproposedfortheprocessingofsimplepathexpressionsandbranchedpathexpressionsrespectively．Theperform

8、anceofthesemethodsareevaluatedaccordingtoexperiments．Inparticular，weimplementaXMLstreamprocessingprototypesystem．Thenoveltyandcontributionsofthisdissertationcallbesummarizedasfollowing：·Wepropos