《基于slca语义的不确定xml关键字查询技术研究》由会员分享，可在线阅读，更多相关《基于slca语义的不确定xml关键字查询技术研究（61页珍藏版）》请在金锄头文库上搜索。
1、分类号：TP392密级：公开UDC：学校代码：10127硕士学位论文论文题目：基于 SLCA 语义的不确定 XML 关键字查询技术研究英文题目：Research on Uncertain XML Keyword Search Basedon the Semantic of SLCA学位类别：工学硕士研究生姓名：苏龙超学号：201102188学科(领域)名称：计算机应用技术指导教师：协助指导教师：张晓琳职称：教授职称：2014年 6月 6日独创性说明本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表
2、或撰写的研究成果，也不包含为获得内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。签名：_日期：_关于论文使用授权的说明本人完全了解内蒙古科技大学有关保留、使用学位论文（纸质版和电子版）的规定，即：本人唯一指定研究生院有权保留送交学位论文在学校相关部门存档，允许论文在校内被查阅和借阅，可以采用影印、缩印或其他复制手段保存论文。在论文作者同意的情况下，研究生院可以转授权第三方使用查阅该论文。（保密的论文在解密后应遵循此规定）签名：_导师签名：_日期：_内蒙古科技大学硕士学位论文摘要近年来，XML数据的查询技术已
3、经成为研究的热点。根据查询模式的不同，XML数据查询分为 XML结构查询和 XML关键字查询，但是对比 XML结构查询，更多的用户习惯于不需要专业领域知识的 XML关键字查询。随着数据采集和处理技术的进步，真实世界中的大部分数据都是不确定的。不确定 XML数据是近年来研究者们提出的一种新的不确定数据的表示形式，不确定 XML数据已经大量应用到金融、电信、军事等领域。目前对于不确定 XML的关键字查询的研究很少，并且由于不确定 XML关键字查询的每一个结果都对应一个概率值，所以用户通常希望得到前 k个概率值最大的结果。不确定 XML的 Top-k关键字查询算法得到了广泛的关注。首先，已有的不确定
4、 XML关键字查询都是基于栈结构实现的，需要频繁的进栈、出栈操作以及频繁的字符串比较，时间效率低下。为了解决这一问题，本文提出一种基于动态 Keyword数据仓的不确定 XML关键字查询算法 PrList。算法首先初始化动态 Keyword数据仓，然后自底向上、自左向右遍历 Keyword数据仓中的节点求解 SLCA节点，不需要进出栈和字符串的比较。其次，目前不确定 XML的 Top-k关键字查询仅返回概率值排在前 k的根节点，需要进一步的处理才能构建满足特定条件下的子树，时间效率低下。为了解决这一问题，本文定义了一种新的基于最小相关联通子树的 Top-k查询语义 SRCT-Top-k，SRC
5、T-Top-k查询返回概率值排在前 k的最小相关联通子树。为了便于处理 SRCT-Top-k查询，对动态 Keyword数据仓进行了扩展，形成扩展动态 Keyword数据仓，然后基于扩展动态 Keyword数据仓提出了 PrListTop-k算法来处理 SRCT-Top-k查询。PrListTop-k算法仅扫描一次扩展动态 Keyword数据仓就能构建满足特定条件下的子树，并且制定的过滤策略可以大量地减少中间结果。本文进行了大量的对比实验。通过设定不同的查询条件，将提出的 PrList算法与 PrStack算法进行对比，并将提出的 PrListTop-k算法与没有过滤策略的PrListTop-
6、k-N算法进行对比。对最终的实验结果进行了详细的分析，证明了所提出的两种算法具有高效性。关键词：不确定 XML；关键字查询；Top-k查询；动态 Keyword数据仓I内蒙古科技大学硕士学位论文AbstractIn recent years, the querying technology of XML has became a hot spot in theresearch. According to the different query mode, the XML data query can be dividedinto XML structural query and XML key
7、word query, but comparing to the XMLstructural query, users accustome to the XML keyword query which does not need thespecial field of knowledge. With the progress of the technology for data acquisitionand progressing, most of the data in the real world are uncertain. The uncertain XMLproposed by re
8、searchers is a new representation method of uncertain data, and theuncertain XML data have been widely used in field of economic, telecommunicationsand the military. Currently, the research on the uncertain XML keyword query isseldom. Because the uncertain XML keyword query will return results with
9、anadditional probability value, users are usually interested in the results with the khighest property. The research on top-k keyword query algorithm over uncertainXML has been widely noted by researchers.Firstly, Existing algorithms of keyword search over uncertain XML are based onstack, which need
10、 to put the nodes into the stack, get the nodes out the stack and comparethe strings frequently, leading to a waste of time easily. To solve this problem, this paperproposes a new keyword search algorithm named PrList based on the dynamic keyworddata repository. This algorithm firstly initializes th
11、e dynamic keyword data repository, thentraverses the items of the keyword data repository from bottom to top, left to right to getthe SLCA nodes, and it does not need to put the nodes into the stack, get the nodes out thestack and compare the strings. Secondly, Exiting algorithms of Top-k keyword se
12、archover uncertain xml just return root nodes with the k highest probabilistic existence,and they have to construct subtree results that meet some certain conditions, which areinefficient in practice. To solve this problem, this paper defines a novel Top-k querysemantics over uncertain xml named SRC
13、T-Top-k based on smallest relatedconnected subtree, which returnes the smallest related connected subtree with the khighest probabilistic existence. In order to process the SRCT-Top-k search easily, thispaper extends the dynamic keyword data repository which becomes extended dynamicII内蒙古科技大学硕士学位论文ke
14、yword data repository, and then proposes an algorithm named PrListTop-k based onthe extended dynamic keyword data repository. PrListTop-k finds the subtree resultsmeeting some certain conditions by scanning the dynamic keyword data repositoryonly once, and developes filtering strategies to reduce the number of in
