足球比分直播

图模型XML数据上查询处理方法的分析.pdf

返回
图模型XML数据上查询处理方法的分析.pdf_第1页
第1页 / 共51页
图模型XML数据上查询处理方法的分析.pdf_第2页
第2页 / 共51页
图模型XML数据上查询处理方法的分析.pdf_第3页
第3页 / 共51页
图模型XML数据上查询处理方法的分析.pdf_第4页
第4页 / 共51页
图模型XML数据上查询处理方法的分析.pdf_第5页
第5页 / 共51页
点击查看更多>>
资源描述:
哈尔滨工业大学工学硕士学位论文 - IV - 摘 要 由于图结构具有强大的表示能力,它 在许多方面有着广泛的应用。随着计算机技术和国际互联网络 技术的迅速发展,图模型数 据上的管理和查询操作领域受到了越来越多的重视。 XML 可以方便地表示复杂的图模型数据规范并已成为通用信息交换标 准之一,从数据库的角度对 其进行研究,最主要的研究问题是如何有效 地存储和查询大规模的 XML 数据。图模型 XML 数据上的可达查询是其中 一类重要的查询。 为高效地回答查询,基于可达编码的 方法被提出,并加入索引和其它辅助结构以提高效率,然而由 于图上编码的时间复杂度太 大,并且会过多地占用搜索和存储空间,现有基 于编码的算法对大量数据上 进行的可达查询并不适用。基于路径匹配的方法 通常将一个查询分解为一组 路径,然后连接原来分支连接处的节点,然而该 类型的结构连接方法通常导 致庞大的中间结果,从而将严重影响查询处理效率。 本文提出了图模型 XML 数据上的一种存储策略, 该存储模型由基于正向,反向两棵生成树的可达 编码和一种高效的可达索引 组成,利用它可以在很短的时间内判断图中任两 点的可达关系。实验表明, 在实际图模型数据上所占存储空间与图的节 点数接近线形关系。 基于此存储策略,本文提出一种针对 图状查询的全局的查询处理方法,通过按照不同的拓扑序两趟 遍历查询图的所有节点,而 得到查询结果。该查询结果以查询结果节点集合 的形式表示,占用很小的存 储空间,但省略了结果中边的信息。本文还提出 查询结果转换算法,在需要 时,可以将结果节点集合转换为查询结果图。理 论和实验证明,该查询处理 方法的时间复杂度接近数据图节点数的线形关系 ,处理查询时中间结果和查 询结果所占空间均很小。 本文给出了图模型 XML 数据上可达查询,查询结 果等的严格定义,还证明了存储策略和查询 处理方法的正确性。 关键词 XML;图模型;可达查询;查 询处理;存储模型 哈尔滨工业大学工学硕士学位论文 - V - Abstract Because graph structure has powerful ability of data representation, it has been widely used in many aspects. With the development of computer science and web technology, the area of management and query over graph-structured data attracts more and more attention. XML can represent complex graph-structured data and has been one of data exchange standard. And the most important problem is how to efficiently store and query large XML data in database research area. The reachability query is an important kind query on XML data, for which some query s based on reachability code and s with index and other structures are proposed to improve query efficiency. Because the time spent on coding a graph is usually high, and these s require large storage on disk, however, these s are not able to deal with reachability query on large amount of data well. The path-based approaches break down a query into a set of paths, and join the original joint nodes, but this type of s usually produce large middle result, therefore seriously reduce query efficiency. In this paper, a storage strategy and a query process are presented, with the s to represent and convert the query result. The storage model, which is composed of the reachability code of the two spanning trees and an efficient reachability index, can be used to determine the reachable relation between any two nodes in nearly constant time. Experiment shows the storage size is nearly linear to the number of nodes in the graph. The query processing is holistic and for graph-structured query, the basic idea of which is to get the query result by traversing all the nodes of the query graph twice in different topologic order. Query result is represented by sets of result nodes, whose advantage lies in small storage space without any edge ination of the result. If necessary, the sets of result nodes can be reconstructed to the sets of result graphs. Considering this, we proposed a result converting . The analysis and experiment prove the time spent on query processing is nearly linear to the number of nodes in the graph, and the extra storage space used by query processing and the result storage space is low. This paper also gives the strict definition of reachability query and query 哈尔滨工业大学工学硕士学位论文 - VI - result of the graph-structured XML data, and the proof of the correctness of the storage strategy and the query processing . Keywords XML; Graph; Reachability Query; Query Processing; Storage Model 哈尔滨工业大学工学硕士学位论文 - VII - 目录 摘要 ...............................................................................................................................I Abstract ....................................................................................................................... V 第 1 章 绪论 ................................................................................................................ 1 1.1 研究的目的和意义 ........................................................................................... 1 1.2 国内外研究现状 ............................................................................................... 2 1.2.1 DBMS 支持复杂对象的研究 .................................................................... 2 1.2.2 图模型数据库的研究现状 ........................................................................ 3 1.3 本文研究的内容 ............................................................................................... 6 1.4 本章小结 ........................................................................................................... 7 第 2 章 预备知识 ........................................................................................................ 8 2.1 XML 数据 .......................................................................................................... 8 2.2 图模型 XML 数据上的查询 ............................................................................ 9 2.3 XML 数据上的可达编码 ................................................................................ 11 2.4 本章小结 ......................................................................................................... 12 第 3 章 图模型 XML 数据的编码与存储 ............................................................... 13 3.1 图模型 XML 数据的可达化简 ...................................................................... 13 3.2 双生成树 ......................................................................................................... 15 3.3 X-Index ............................................................................................................ 19 3.3.1 X-Index 的建立 ........................................................................................ 19 3.3.2 X-Index 的存储和查找 ............................................................................ 21 3.4 本章小结 ......................................................................................................... 23 第 4 章 查询处理 ...................................................................................................... 24 4.1 查询处理中的概念与定义 ............................................................................. 24 4.2 X-Scan 算法 ..................................................................................................... 26 4.2.1 两个节点集合间的节点筛选 .................................................................. 27 4.2.2 两趟遍历 .................................................................................................. 30 4.3 结果转换 ......................................................................................................... 32 4.4 本章小结 ......................................................................................................... 33 第 5 章 实验 .............................................................................................................. 34 5.1 存储空间 ......................................................................................................... 35 哈尔滨工业大学工学硕士学位论文 - VIII - 5.2 索引建立 ......................................................................................................... 37 5.3 查询效率 ......................................................................................................... 39 5.4 影响系统的参数 ............................................................................................. 40 结论 ............................................................................................................................ 42 参考文献 .................................................................................................................... 43 攻读学位期间发表的学术论文 ................................................................................ 46 哈尔滨工业大学硕士学位论文原创性声明 ............................................................ 47 哈尔滨工业大学硕士学位论文使用授权书 ............................................................ 48 哈尔滨工业大学硕士学位涉密论文管理 ................................................................ 49 致谢 ............................................................................................................................ 50 哈尔滨工业大学工学硕士学位论文 - 1 - 第 1章 绪论 1.1 研究的目的和意义 XML 是互联网联合组织 W3C创建的一组规范,以便于软件开发人员和内容创作者在网页上组织信息,其目的不仅 在于满足不断增长的网络应用需求,同时还希望借此能够确保在通过网络进行 交互合作时,具有良好的可靠性与互操作性。良好的数据存储格式、可扩展性、高度结构化、便于网络传输是XML 主要的四大特点,决定了其卓越的性能表现。由于 XML 能针对特定的应用定义自己的标记语言,这一特征使得 XML 可以在电子商务、数字图书馆、远程教育已经信息集成等各种 EDI 应用领域中一展身手。 XML 技术出现至今,受到了业界的广泛 关注。在工业界,微软、 IBM、Oracle 等参加了 XML 各项标准的制定, XML1.0 标准刚一出台,便开始了相应商品的开发。其中,微软的 Office、 Windows 都将完全采用 XML 格式,而IE4.0、 IE5.0 则早已实现了对 XML 的支持; IBM、 Oracle 等在各自的数据库商品中提供了对 XML 的支持。商业公司如此,国外的研究机构更加钟情有甚,从 1998 年至今,很多颇具影响的机构和大学一直在研究如何管理 Web 上已出现和即将出现的大量 XML 数据,致力于 XML 数据使用性能的提高。 XML 数据管理技术的研究对提高我国的社会信息化水平,促进我国的科技、经济和国防军事的发展,提高我国综 合实力,具有重要的意义,因此其研究工作也引起了国内学术界的重视。复旦 大学、人民大学、东北大学、哈尔滨工业大学等高等院校已相继开始了 XML 数据管理与处理的基础研究。 从数据库的角度对 XML 进行研究,最主要的研究问题是如何有效地存储和查询大规模的 XML 数据。目前,面向 XML 数据的存储和查询已经有大量的技术提出,但是这些技术并不能够满足高效 XML 数据处理的需要,其中一个重要的问题就是目前大多数的 XML 文档的存储和查询技术都是基于树模型,即将 XML 文档抽象为一棵树,而 XML 本身已经可以通过 idref 属性支持图模型的表达。图模型将 XML 数据看作一个复杂的有向图结构, XML 数据上元素之间、元素和属性之间的联系在图模型中被抽象成有向边;树模型将XML 数据看作一棵有向的标签树, XML 数据上元素之间、元素和属性之间的联系被抽象成树上的有向边。毫无疑问,图模型的 XML 文档具有更强大的表哈尔滨工业大学工学硕士学位论文 - 2 - 达数据的能力。 图查询的核心问题是图的匹配问题,由于 图结构强大的表示能力,图上的查询在许多方面有着广泛的应用,例 如,交通运输网络,作业调度,家族关系,化学信息学,生物信息学, XML 文档 包含了 DTD 以及 ID/IDREF,语义网络 RDF, OWL,网络通信和机器视觉等等。 有向图上两点间的可达查询即是给定两个节点 u,v,判断图中是否存在从 u到 v 的有向路径。而对于查询图 Q 而非两点间的可达查询,需要在数据图中找出所有满足 Q 的子图,其节点间应该满足 Q 中规定的可达关系。 XML 规范将数据以有向图的形式组织,随着 XML 的广泛应用,有向图上的可达查询变得日益重要。 1.2 国内外研究现状 本节首先回顾让数据库管理系统 DBMS支持复杂对象的相关研究,然后总结近年来各种图模型数据库的研究现状,最后对图模型 XML 数据技术带来的新的挑战和现有的查询处理方法的不足作出分析。 1.2.1 DBMS 支持复杂对象的研究 早在 1976 年, MIT 的 Peter P. Chen 就首先提出了实体 -关系模型 Entity-Relationship Model[1],而后,文献 [2]和 [3]分别指出,关系和 ER 图都可以被看作是建立于更高层次上的实体,这使 得在设计查询计划时可以支持结构化行为。 70 年代的研究成果之一是 System-R,它是由 IBM 的 San Jose 研究中心开发的数据库系统。在 System-R 中, SQL 语言被提出。同时, Lorie 和 Plouffe 提出加入隐藏指针,用于支持树结构的 schema。在 1983 年, System-R 开始支持复杂对象[4],这标志着在关系数据库系统中开始加入新的结构。 1989 年,面向对象的数据库系统概念被提出[5],接着在 1990 年提出了第三代数据库系统的概念[6]。 1995 年,由 Dallan Quass 等人首次提出查询半结构化信息的方法[7],在1998 年以后, XML 查询处理成为了一个研究热点。 哈尔滨工业大学工学硕士学位论文 - 3 - 1.2.2 图模型数据库的研究现状 1.2.2.1 图模型数据库的相关研究 1990 年, Marc Gyssens 等人在文献 [8]中提出作为图模型的数据库的概念 1.模式和对象 实例 都可以被看成图。 2.对数据进行操作即是图的转化。 文献 [8]提出了 4 种操作节点 /边的插入 /删除,以及一个抽象操作符,适用于具有同一个性质集合的抽象对象。关系可以被这 4 种操作实现,而且可以用 4 种操作符加抽象操作符模拟嵌套的关系代数。 1987 年, Isabel F. Cruz 等人提出了一种查询语言 G,用于带标签的图上的数据查询,这种查询语言的表达能力被证明可以与关系的查询语言相当[9]。 1989 年,在图数据库中找出正则的简单路径的问题被提出[10]给定一个带标签的有向图 G,以及一个正则表达式 R,找到所有的由简单路径表示的节点对 路径的起点和终点 ,使得沿着路径的标签的串联组合满足 R,正则简单路径问题是 NPC 问题。那么,在图 G 中是否存在有向简单路径 p 满足 R,使得组成 p 的边的标签的串联在 R 指明的语言中然而可以证明,经过节点的路径问题也是 NP 完全的。 1987 年, Rakesh Agrawal 提出定义一个 alpha 操作符,允许用户表示一大类递归查询,而且可以被高效地实现[11]。 alpha 操作符可以被自由地混杂在其它操作符中。而且该操作符在代数层次 而非语言层次上被支持,它的表达能力至少与线性递归一样强。 Ralf H. Guting 等人实现了明确支持图结构的关系数据库 GraphDB[12]。 图的视图的概念于 1994 年被 Alejandro Gutiérrez 等人提出[13],并将视图建立在 DBMS 上 包括 RDBMS 和 OODBMS。图的视图上的操作有并union ,交 intersection ,节点差异 node difference ,边的差异 edge difference,选择 selection和投影 projection。 1993 年, Mark H. Nodine 等提出了一种外存上的图搜索策略[14],即当图太大,以至于不能放入内存时,在外存上搜索该图。 Sriram Raghavan 等于 2003 年提出了一种网络上的图的存储方法[15]。他们认为,网络中的图 WG 是巨大的。该方法提供了外部接口给搜索引擎,内部接口用于网络数据仓库,以及批量的数据获 取。在这个方法中,构造了具有两个层次的图。 哈尔滨工业大学工学硕士学位论文 - 4 - Milo 和 Suciu 提出了以 backward simulation 和 backward bisimulation 为基础的一系列的索引结构( 1/2/T-index) 。针对 1-index 可能过大的情况 ,文献[16,17,18]分别提出了 Ak-index, Dk-index 和 Mk-index 利用 k-simulation 对1-index 进行近似匹配。 文献 [19]提出了利用 bisimulation 建立 FB-index,用于处理带有 branch的查询。已经证明, FB-index 是最小的可以回答 XML 上所有 branch 查询的索引。但是当 XML 结构不规整的时候, FB-index 的体积仍然可能过大,甚至超过内存大小,文献 [20]研究了把 FB-index 组织到磁盘上的策略。文献 [21]和 [22]研究了对 1-index 和 FB-index 进行更新的方法。 1.2.2.2 图模型 XML 数据上的查询处理方法 通常可以将图模型 XML 数据上的查询处理看作在图 G 中找出匹配图 Q 的子图,即是一种图的匹配算法。通常的图匹配问题是 NP 完全的[2],然而对于一些特殊情况可以会有高效的算法。例如对于无环图,文献 [3,4]提出了关于图的大小是多项式时间复杂度的算法。因为 有向图中含有环对于查询没有意义,所以目前研究关注的均为有向无环图 DAG。本文所指的图均为有向无环图。 当前对 XML 数据操作的实现主要集中在可达查询操作和 twig 操作的实现。在文献 [23]所做出的调查和总结中,在图上的模式匹配算法被分为精确匹配和不精确匹配两种。 精确匹配需要查询节点到数据节点的一个完全 的映射,例如,所有的查询节点与它们相应的数据节点精确对应,而 且所有父子关系的查询边映射为数据图中的边,祖先与后代关系的查询边映射为数据图中的路径。 不精确匹配允许近似,即或者通过一个由查询 节点到数据节点的部分映射,或者通过转换数据节点来建立一个完全的映射。 本文只将研究限定在精确匹配上。精确的图匹配问题是一个 NP 完全问题[24]。然而,对于一些特殊的情况,高效的算 法仍然存在。例如,如果数据图是无环的,那么就会有关于数据图的大小的多项式算法存在。 最近的一项研究[25]提出了一个关于数据图的大小的近似 2 次方的算法,它在精确匹配的概念上针对在 DAG 上的树状和 DAG 模式的查询,正如文献 [23]总结到的那样,很多图搜索系统利用一个 在执行图匹配算法以前的预先过滤的步骤 为了减小搜索空间,而基于定制的传统意义上的索引和评估方法 。 应用中最普遍的索引方法是带固定 或者参数化的长度的路径索引[26,27,23]。对于包含有祖先 -子孙边的查询,为匹配这样的 边而建立路径索引相当于在每一个节点上统计它到它所有子孙节点的边,即众所周知的图上的传递闭包。 哈尔滨工业大学工学硕士学位论文 - 5 - 在空间和时间的权衡 tradeoff上,大多数已有的图匹配方 法假定数据图是静态的,因此,倾向于预先算出传递闭包 ,或者建立可改变长度的路径索引来为高效的模式匹配换取空间。 Floyd-Warshall 算法计算传递闭包时的时间复杂度是 On3,结果存储空间是 On2。此外,为了在数据更新的时候维持实例化的传递闭包,还需要多项式时间的代价。 在文献 [28]中,为了在树状数据中搜索只含“ /”的树枝,对选择性估计问题进行了研究。当应用到含有“ //”边的树枝时, [28]所提出的选择性估计方法很可能效率低下或者不严密。 匹配的实现在 [23]中被总结为两类根据传统 子 图到图的匹配技术实现,或者根据结构连接方法实现。结构连 接方法将一个查询分解为一组路径,然后连接原来分支连接处的节点[29,30,31]。尽管如此,这样的结构连接方法通常导致庞大的中间结果,这将严重地影响查询效率。 基于可达编码的方法是树状 XML 数据查询处理中使用最广的方法之一,其基本思想是为图中的每个节点 /边赋予特定信息,使得任两个节点通过彼此的信息就可在常数时间内判断可达关系。针对树状数据的 Interval 编码是其中一种常用的可达编码,在这种编码中,每个节点 v 具有一个正整数区间 a,b。对于图中任意两个节点 u 和 v,如果 u 的区间包含 v 的区间,那么 u 可达 v,反之不可达。 虽然 Interval 编码已经被引入到图状 XML 数据的可达查询处理中,但是由于图的边可能会非常多,完全采用编码 的方法将会占用大量的搜索和存储空间,因此是不适用的。 对于两点间可达关系的判断,经典的 Floyd-Warshall 算法[33]可以在 On3时间内求出图中所有点的传递闭包,所占空间为 On2,其中 n 为图中顶点数。对于图上点 u 是否可达点 v 的问题,可以通过判断 v 是否在 u 的传递闭包中的方法解决,时间复杂度为 On。然而这对于较大规模数据 比如拥有百万级节点的图 并不适用,因为这需要占用大 量的空间存储传递闭包,并且会花费大量的磁盘 I/O 操作。 [23]指出,很多图匹配算法都预先对路径 进行索引,同时固定索引的路径的长度并将其参数化以减小搜索空间,并且估计结果大小以减小中间结果[26,27,23]。文献 [32] 将 Interval 编码扩展到 DAG 上,每一个节点 u 都对应一组互不重叠的 Interval,称为 Lu;从 u 可达节点 v,当且仅当 Lv中所有的Interval 均被 Lu中的某些 Interval 包含。然而对于较大规模的图, Lu会很大,并且过于零散的 Interval 会影响存储和查询效率。 [35]提出了 DagStackD
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播