xml关键字查询中最紧致片段问题的研究

《xml关键字查询中最紧致片段问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文XML关键字查询中最紧致片段问题的研究姓名：张雷申请学位级别：硕士专业：计算机软件与理论指导教师：洪晓光20090405山东大学硕士学位论文摘要XML(eXtensibleMarkupLanguage)在Web服务、电子商务、数字图书馆等诸多网络相关应用领域已经成为描述数据的事实上的标准。为了方便用户从海量的XML数据中提取他们所需要的信息，许多XML数据查询算法应运而生，使得XML数据查询成为XML数据管理领域的一个热点。本文将这些XML数据查询算法按照查询模式描述的不同分为两类，即舳结构查询和XML关键字查询。

2、前者多采用了正则表达式的描述方法，偏向于传统的结构化的查询方式，能够清楚的表述用户的查询意图；后者融入了信息检索领域常用的查询思想和方法，允许用户仅仅输入关键字就能够进行查询。XML结构查询算法根据精确的查询条件，能够输出理想的查询结果。然而，该算法对进行查询的用户也提出了更高的要求，即不仅要熟悉结构查询算法所采用的查询语言，而且还要了解待查询的XML文档树结构。以上要求对于绝大多数用户而言是不切实际的，所以从用户的角度出发，XML关键字查询是一种能够被广泛使用的查询方法。XML关键字查询方式中最关键的问题是如何求解包含所有关键字的最

3、紧致片段，即SLCA(SmallestLowestCommonAncestors)I'口-]题。目前已有许多求解算法，包括Stack、ILE、SE、USA和LISAⅡ等。ILE和SE在与Stack的实验对比中表现得效率更高，适合需要频繁I／o操作的海量XML查询，他们仅需要顺序读取XML数据一遍；相比ILE和SE，LISA和LISA1I在轻量级XML查询中，无论是在理论分析上还是试验对比中都表现出了更好的性能。然而，LISA不仅需要频繁扫描节点，而且需要引入集合交操作，耗费了大量CPU周期。LISAlI虽然在避免不必要扫描方面改进了L

4、ISA算法，但却使用了自己独有的编码，不仅引入了编码映射，而且也使得该算法的通用性大大削弱。这两种算法即便作为一种仅在内存中执行的算法，以上缺点也影响了查询速度。为此，本文提出一种轻量级的、使用XML关键字查询通用的Dewey编码的新算法，NDT(N-Di、，idedTravelAlgorithm)，即求解最紧致片段问题的N分遍山东大学硕士学位论文历算法。该算法不仅消除了集合交操作，而且仅仅扫描所有节点至多一遍。NDT无论在理论分析上还是试验对比中，都表现出了较好的性能，是一种可行的最紧致片段求解算法。作为一种新的XtVI]．,关键字

5、查询算法，NDT具有查询简便快捷、普通用户使用门槛较低、用户友好等的特点，但是也会存在查准率相对于XMI．,结构查询算法较低的XML关键字查询的先天缺陷。关键词：XML关键宇查询；Dewey；SLOe,；NDTII山东大学硕士学位论文ABSTRACTX池(eXtensibleMarkupLanguage)hasbecamethefactstandardfordescribingdatainthefieldofWebService，ElectronicCommerceetc．Inordertohelpuserstoretrieveinf

6、ormationmeyneedfromovedargeamountofXMLdocuments，manyalgorithmshavebeenraised．ResearchonXMLquerymakessensefromthatpointofVIeV忆Accordingtoretrievalbasisofthosemethods，thispaperdividesXMLretrievalalgorithmsintotwocategories，XMLStructm'alRetrievalandXMLKeywordRetrieval．Thef

7、ormeronetakesadvantageofregularexpressionsastraditionalqueriesandcouldexposeusers’Sneedeasily．ThelatteroneismorelikeInformationRetrievalandtheonlyinputsneededfromthensersarekeywords．XMLStructuralRetrievalreturnsaccu_rateresultsjustaccordingtoexpressionsinput．However,ita

8、lsoqualifiestheusersnotonlyonthequerylanguagebutalsoonthestructureofXMLdocuments．Thosequalificationsareimpossi