原生XML数据库动态结点编码方案分析与应用的研究

【作者】 吕向风；

【导师】 李兰友；

【作者基本信息】 天津工业大学 ， 计算机应用技术， 2008， 硕士

【摘要】 随着XML相关标准的制定,Internet上出现了大量的XML文档,如何有效地管理和查询这些文档成为一个亟待解决的问题,这一问题的出现极大地促进了XML数据库技术的研究。原生XML数据库(NXD)是专为存储和管理XML文档而提出的,在NXD中的XML文档查询主要包括值查询和结构查询,其中的结构查询是XML查询的一个重要内容。判断结点之间的结构关系的主要思想是将一个复杂的查询模式分解成为若干个二元基本结构关系的集合,首先计算二元基本结构关系,然后将基本的匹配结果组合起来。在这种处理策略下,基本结构关系(包括父子关系和祖先-后代关系)的计算成为查询处理的关键操作,这种操作被称为结构连接(或包含连接)。各种索引的建立可以提高结构连接算法的效率,而XML结点编码可以方便地建立各种索引,所以XML文档结点编码方案的研究引人注目。本文在对原生XML数据库中动态结点编码方案及其应用进行透彻剖析的基础上,重点对三种动态结点编码方案,即ORDPATH编码、DeweyIDs编码及DLN编码进行了研究,并用C#开发了三种编码方案的软件。然后,用十个标准的XML文档测试集对三种编码方案进行测试,根据测试结果对三种动态编码的确定性、动态性和压缩性进行了分析与比较:在此基础上,从理论上进一步对XML动态编码的性能进行了分析比较,着重分析了动态编码的压缩性。对动态编码压缩性理论分析所采用的标准是:编码K个层标识占用的存储空间S,分别对用固定长度、长度域、前缀编码及控制标记等四种方式编码K个层标识占用的存储空间S进行统计,最终归纳出关于S与K的通式。通过一系列研究,进一步验证了动态结点编码在编码时间和空间效率的高效性。最后,对动态编码方案在查询计划和查询处理模型中的应用进行了探讨。更多还原

【Abstract】 With the development of related standard on xml, a great deal of XML documents appeared on internet, how to effectively manage and query these files become an urgent problem,what will greatly promote research on XML database technology. Native XML Database (NXD) is designed to store and manage the XML files whose queries include value inquiries and structure inquiries in NXD. The main ideas to judge structure relationship between nodes is to decompose a complex inquiry mode into several sets of dual basic structure relations. First calculate the basic structure of binary relations, and then match the basic combined. In such strategy, to caculate the basic structure relations (including parent-child and ancestor-descendent relations) become the key operations of query processing, and the operations is defied structure connecting (or contains connections). The establishment of various indexing can improve structure linking algorithm’s efficiency, various indexes can be easily set up by XML nodes coding. Therefore, a large number of scientific research workers concentrate on XML document node coding studies.In this paper, analyze dynamic nodes coding scheme in original XML database and its application for a thoroughly,on the basis of that emphasize on the research of three dynamic coding schemes, that is ORDPATH coding, coding and DLN DeweyIDs coding and develop a software about three codding shema with c sharp. Use ten standard XML documents test sets to exam further, what will come out some test results by which I analyze and compare of the three codings’ accuracy, dynamic and compression; Next, I analyze the dynamic coding scheme’s performance on theory. In its all performance, I emphasize on compression whose standard is compute the storage space that coding K layer totem. Use the fixed length, the length domain, prefix code and control token to encod K layers logo and statistic the storage space occupied by S respectively, and ultimately achive about S and K’s general formula.At last, discuss the application of dynamic node code schema in query plan and query processing model.更多还原