ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/fb1171485.html,
Journal of Software, Vol.18, No.6, June 2007, pp.1400?1418 https://www.doczj.com/doc/fb1171485.html, DOI: 10.1360/jos181400 Tel/Fax: +86-10-62562563
? 2007 by Journal of Software. All rights reserved.
XML数据的查询技术?
孔令波1+, 唐世渭1,2, 杨冬青1, 王腾蛟1, 高军1
1(北京大学计算机科学技术系,北京 100871)
2(北京大学视觉与听觉信息处理国家重点实验室,北京 100871)
Querying Techniques for XML Data
KONG Ling-Bo1+, TANG Shi-Wei1,2, YANG Dong-Qing1, WANG Teng-Jiao1, GAO Jun1
1(Department of Computer Science and Technology, Peking University, Beijing 100871, China)
2(National Laboratory on Machine Perception, Peking University, Beijing 100871, China)
+ Corresponding author: Phn: +86-10-62755440, E-mail: lbkong@https://www.doczj.com/doc/fb1171485.html,, https://www.doczj.com/doc/fb1171485.html,/lbkong
Kong LB, Tang SW, Yang DQ, Wang TJ, Gao J. Querying techniques for XML data. Journal of Software,
2007,18(6):1400?1418. https://www.doczj.com/doc/fb1171485.html,/1000-9825/18/1400.htm
Abstract: XML has become the de facto standard for data representation and exchange for Web applications, such
as digital library, Web service, and electronic business. How to retrieve interesting information from the promising
XML data is an active research area. Among techniques in this area, the description of query patterns is a crucial
section. This paper reviews the actualities of recent researches on this topic. It classifies the query descriptors into
two categories, XML Query type and XML IR type (with three subcategories: XML IR/keyword, XML IR/fragment
and XML IR/query), and concludes three popular problems: Twig pattern processing, SLCA (smallest lowest
common ancestor) problem, and similarity measuring techniques for retrieved XML fragments. It analyzes the
virtue and deficiency of related techniques based on their convenience for common users. And hereby it proposes
four issues for further XML querying researches: structural keywords and corresponding structural similarity
measuring, wiping off the redundancy in XML data processing between XML Query (including XML IR/query) and
XML IR/keyword, theoretical discussion of XML Query and its realization, and the management of peculiar XML
data.
Key words: XML query; XML IR; XPath; XQuery; XML keyword search; XQuery FT; Twig; structural join;
SLCA(smallest lowest common ancestor); dewey encoding; similarity measuring; tree edit distance;
VSM; TF*IDF
摘要: XML规范已成为当前网络应用(包括数字图书馆、Web服务以及电子商务)中事实上的数据表达、交换
的标准.针对XML数据的查询在当前XML数据管理研究中占有重要的地位,也是当前XML数据处理研究领域的
热点方向,相关的研究文献有很多.根据查询模式描述的不同,将当前XML查询技术归入两大类:XML Query方式和
? Supported by the National Natural Science Foundation of China under Grant No.60503037 (国家自然科学基金); the National
High-Tech Research and Development Plan of China under Grant No.2005AA4Z3070 (国家高技术研究发展计划(863)); the Beijing
Natural Science Found of China under Grant No.4062018 (北京市自然科学基金)
Received 2006-04-25; Accepted 2007-01-23
孔令波等:XML数据的查询技术1401
XML IR方式.后者又进而可分以为3个子类:XML IR/keyword方式、XML IR/fragment和XML IR/query方式,并从中挑选出3个研究者关注的问题进行了简述,它们是:Twig查询模式的处理、SLCA(smallest lowest common ancestor)节点的获取以及对所获取的XML片段相似性的度量.以方便普通用户使用为准则探讨了相关XML查询技术的优、缺点,将如下4个问题作为需要进一步关注的研究内容:结构化关键字查询及相应的结构相似性度量方法,如何消除XML Query查询处理模式(包含XML IR/query)和XML IR/keyword查询处理模式间数据冗余的问题,XML Query 查询方式的理论探讨及其实现以及针对特定应用的XML数据的有效管理.
关键词: XML查询;XML IR查询;XPath;XQuery;XML关键字查询;XQuery FT;Twig查询模式;结构连接; SLCA节点;Dewey编码;相似性度量;树编辑距离;向量空间模型;TF*IDF
中图法分类号: TP311文献标识码: A
XML(extensible markup language)(最新的规范为2004年的XML1.1),即可扩展的标记语言,是一套定义语义标记的规范,其目标是能够定义计算机和人都方便识别的数据类型.随着网络应用的快速发展,符合XML规范的数据(称为XML数据)已大量存在于当前的信息社会,尤其是电子商务、Web服务、数字图书馆等应用理念的进一步发展,使得XML类型的数据成为当前主流的数据形式.对XML数据的有效管理也随之成为当前数据库领域研究的热点[1].
在规范了XML数据格式后,如何方便地从XML数据中提取用户感兴趣的信息就成为XML数据管理研究的重要主题,内容涉及查询请求模式的描述、查询语句的执行机制以及查询结果的显示.对这类问题的探讨已成为数据库研究领域的一个方向,到目前为止,在各高等级数据库会议上涌现出了数目繁多的研究论文(SIGMOD,VLDB,SIGIR,ICDE,ICDT等).本文的目的就是尝试对当前与该专题有关的研究成果进行汇总.
本文第1节在简单回顾XML数据的特点后,根据描述查询请求的不同将当前XML数据的查询技术分为两大类:XML Query方式和XML IR方式,并将后者进而分为3个子类:XML IR/query,XML IR/fragment和XML IR/keyword;之后进一步给出不同类别下查询模式的概括.第2节以Twig查询模式和XML关键字查询(SLCA(extensible markup language)问题)为线索,讲述XML查询语句执行的研究状况.第3节概括XML查询结果显示的问题,主要集中于满足给定关键字的XML片段的相似性度量问题.最后是总结和研究展望,根据是否便于普通用户使用的原则,提出舍弃标签信息但保留结构关系的新型查询模式描述的建议以及新型的XML片段结构相似性求解方法;并根据最近的研究文献归结出另外两个值得关注的研究方向,即XML Query查询方式的理论探讨及其实现,以及针对特定应用的XML数据的有效管理.
本文讨论的问题只是XML数据管理领域中的一部分,观点也可能存在偏颇之处,但我们希望通过本文的工作,能给数据库研究者,尤其是正在进入相关研究领域的人员一些启发和帮助.需要指出的是,若在一篇文章中将有关XML数据查询的研究内容,即从查询模式的分类到查询技术的实现全部覆盖是一件非常困难的事情,而且文献[2]概括的XML索引技术已经很好地概括了XML查询实现方面的研究内容.所以,本文在叙述上如下安排:内容着重于查询特征的概括,同时兼顾自文献[2]后出现的新的XML查询实现技术.例如,将XML查询根据其查询模式的不同分作两大类——XML Query和XML IR,然后概括叙述两种查询模式的研究点;在阐述研究点的过程中,对新出现的查询实现技术作简要的介绍.
1 XML查询模式分类
1.1 XML数据、模型及其结构信息
符合XML规范的数据称作XML数据.这类数据有两个基本特点:一是自描述,XML数据本身就已经包含了元数据——关于数据本身的信息,表现为不同语义的标记(例如元素、属性等等).在所有标记中,元素标记最为重要.一个元素标记由两个起、止标签构成,起止标签所含的文本就是对应的语义单元;二是半结构化,即不同于传统关系数据库(传统的数据库都有一定的数据模型,可以根据模型来具体描述特定的数据),XML数据的结构
1402 Journal of Software软件学报 V ol.18, No.6, June 2007
限制并不严格,表现为语义单元相互嵌套的层次关系.XML数据的基本形式为XML文档,如图1(a)所示即为一个实际的XML文档.在实际处理XML数据时,更为常见的是XML标签有向图模型,由XPath规范描述.通常简化为XML标签有向树模型,G=(V,E,r,A),其中的V表示G中所有节点的集合,E表示G中所有边的集合,r表示G的根节点,A是所有节点所带标签的集合.图1(b)即为满足XPath树模型定义的XML树,图中每个元素节点左侧的数字序列表示该节点的Dewey编码,右侧的数对则对应前、后序遍历生成的区间编码.有关两种编码的叙述参见文献[2].
??xml version=“1.0” encoding=“UTF-8”??
?proceedings?
?issue?
?articles?
?article?
?title? bibliography on data design ?/title?
?authors?
?author position=0? Karen Botnich ?/author?
?/authors?
?/article?
?article?
?title? face recognition ?/title?
?authors?
?author position=0? cola cohen ?/author?
?/authors?
?/article?
?/articles?
?publisher?
?year? 2003 ?/year?
?address?
?country? Germany ?/country?
?/address?
?/publisher?
?/issue?
?/proceedings?
(a) XML document instance
(a) XML文档示例
(b) XML tree instance
(b) 对应的XML树
Fig.1 XML document instance—Proceedings.xml, and its XML tree
图1 XML文档示例——Proceedings.xml及对应的XML树结构示例
孔令波等:XML数据的查询技术1403
XML数据包含的信息可分为两部分,一是内容(content),由XML数据中包含的text文本以及属性值组成; 另一部分为结构信息(structure),由XML数据的标签间的嵌套关系组成(通常不考虑由IDREF表示的关联关系),包括直接包含(direct containment)、紧包含(tight containment)和邻近关系(proximity property)等.这些结构关系与XML树模型下节点间的结构关系有着直接的对应,可由节点间的结构关系来描述.例如,紧包含关系对应树结构中的父亲-孩子(parent-child)结构关系,包含关系就对应祖先-子孙(ancestor-descendant)结构关系和父亲-孩子结构关系之和,而邻近关系则对应树结构中的兄弟(sibling)关系.由于XML标签有向树模型中的相关概念与数据结构中树结构的概念有着明显的对应关系,所以前面的叙述直接引用了相应的概念,没有作更多的叙述.这里介绍的有关XML数据的内容和结构信息不仅有助于把握XML数据的本质,而且也有助于更深刻地理解后续介绍的查询模式描述的内容:从XML数据中提取感兴趣的信息必然深受这两个特点的影响.
1.2 XML查询方式分类
作为日渐广泛采用的数据形式,从中提取有用的信息是一个不可回避的研究内容.为了从自描述的、半结构化的XML数据中抽取用户感兴趣的信息,研究人员开发了许多查询描述形式.根据查询请求描述特点的不同,可概括为两大类查询模式:XML Query查询模式和XML IR (information retrieval)查询模式.本节就对这一分类及其相关研究内容的概括.
1.2.1 XML Query查询模式
在从XML数据中获取感兴趣信息的处理过程中,有一类查询描述方式占有重要的地位,即XML Query查询模式:首先定义精致的查询模式描述语言,用户借助它来描述自己感兴趣的模式,将用户的模式交由实际的XML数据处理系统处理,返回与模式相匹配的结果.
1.2.1.1 XML Query查询模式概述
属于此类的查询语言有很多,包括Lorel[3],XML-QL[4],XML-GL[5],Quilt[6],Xpath[7],Xquery[8].其共同的特征是采用了正则路径表达式[9?11]的形式,其本质是捕捉XML数据单元间的结构关系和内容.XPath是实现XML 数据周游的基本语言,是XSLT,XQuery的基础.
根据前面的叙述,这类查询语言的缺陷也是明显的:首先,查询语言的使用者必须学习相关的语法机制,这一点本身就增加了普通用户使用它们的难度.而且用户即便是已经掌握了相关的查询描述机制,如果她/他不了解实际要查询的XML数据的组织情况(例如,数据中有哪些标签?感兴趣的标签间具有什么样的关系?),她/他同样不能完成查询语句的书写.在此,本文并不想通过概述相关查询语言的语法描述规则来说明这一点,而是采用实际例句的形式帮助读者意识到这一点.需要说明的是,这类查询语言发展到现在已出现了集中的趋势,其代表便就由W3C推出的XPath和XQuery查询语言.
图2给出的两个示例分别是XPath和XQuery的查询语句.图2(a)为XPath查询语句,表示从XML文档中提取所有作者名包含Botnich并且该作者位于文章首位的所有文章的名称.其中的“//”表示位于其前、后的标签(例如issue和articles)对应的节点应具有祖先-子孙的结构关系;图2(b)为XQuery查询语句,表示查询proceedings.xml将所有文章的题目全部列出来,其中除了前述XPath中有的“//”以外,FOR和RETURN则是新的内容.从两个实际的查询语句的例子中可以看出,除了需要掌握XPath中的技术外,用户还需要进一步理解FOR,LET,ORDER BY,WHERE和RETURN(即XQuery中最具代表性的FLOWR格式)等知识(实际上XQuery 还有其他内容).这对于普通用户而言不能不说具有相当的难度.有感于此,并且看到传统信息检索对用户使用友好的特点,促使部分研究者将信息检索特点引入XML数据处理的研究,即后面第1.2.2节要概括的内容.
如前所述,由于XPath查询语言是XSLT,XQuery的基础,所以,XPath描述的查询模式的不同形式也就代表了XML Query查询模式的主要内容,主要分为3个层次[12]:线性路径表达式、分支路径表达式和路径树.
定义1. 线性路径表达式.递归定义如下:
(1) 如果s是一个标签,例如issue,article,那么“/s”,“//s”都是线性路径表达式;
(2) 如果L是一个线性路径表达式,s是一个标签,那么“L/s”,“L//s”也是线性路径表达式.
当线性路径表达式中不存在“//”时,通常称为简单路径表达式.
1404
Journal of Software 软件学报 V ol.18, No.6, June 2007
定义2. 分支路径表达式.递归定义为: (1) 如果L 0,L 1是线性路径表达式,k 是一个整数,那么,L 0[L 1],L 0[k ]就是分支路径表达式;
(2) 如果B 是一个分支路径表达式,L 是一个线性路径表达式,那么,B [L ],B [k ]也都是分支路径表达式.
定义3. 路径树.路径树T (N ,E )(N 是节点集合,E 是边的集合)可递归定义如下:
(1) 以一个线性路径表达式为标签的单个节点就是一棵路径树;
(2) T 1(N 1,E 1),T 2(N 2,E 2)是两棵路径树,其中v 1∈N 1,v 2∈N 2,如果从v 1到v 2之间有一条边e ,那么,T (N 1∪N 2, E 1∪E 2∪{e })也是一棵路径树;
(3) T 1(N 1,E 1)是一棵路径树,v 1∈N 1,v 2是一个标签为k 的节点,e 是从v 1到v 2之间的一条边,那么,T (N 1∪{v 2}, E 1∪{e })也是一棵路径树;
(4) 路径树中的节点通常会与如下形式的谓词(predicate)关联:op value ,其中,op 为“=”或者“≠”;
(5) 路径树中的1个或多个节点可被设定为输出节点.
其中,路径树的定义包含了研究文章中常见的“小枝(twig)”的概念 [13?17]:专指具有多个叶节点的树结构形式的路径树查询形式.图2(a)中的XPath 语句就是Twig 查询模式的实例.针对Twig 查询模式的处理是XML Query 查询处理研究中的主要问题之一.相关工作的叙述参见第2.1节.
(a) XPath instance (b) XQuery instance
(a) XPath 查询语句示例 (b) XQuery 查询语句示例
Fig.2 XML Query instances
图2 XML Query 查询语句示例
1.2.1.2 XML Query 查询实现的要点及相关研究概括
通过上述XML Query 查询模式3种层次的描述可以看出,如何快速地确定任意两个元素间的结构关系(containment relationship)是实现此类查询模式的关键.为达到这一目标,相关的研究者提出了种类繁多的索引方法,可概括为两大类:一是节点记录类索引方法;二是结构摘要类索引方法.前者进而可分为3个小类:节点序号类索引方法、节点路径类索引方法以及混合类索引方法.有关内容已在文献[2]中作了较为详尽的叙述,所以在本文中对这方面的内容不再复述.文献[18]的阅读也会有助于读者进一步理解此处的内容.
需要说明的是,在浏览针对XML Query 查询处理的最新研究文献时还发现,尽管新出现的索引技术不能直接被文献[2]所覆盖,但是仍然可以很好地归入文献[2]中的划分类别.例如,在VLDB 2006文献[19]提出的FIX 索引方法,其基本内容为:在认识到对应于Twig 结构的矩阵的特征值向量可作为表征该Twig 结构的关键字的基础上,将XML 文档进行Twig 分解并根据特征向量构建索引结构,以满足XPath 的查询.虽然该方法不与文献[2]中提到的任何索引方法相同,但是按照该文的叙述,该方法是可以归入结构摘要类索引结构的.
另外,还有一些最新的研究文献中也与XML 数据及XML Query 查询有着紧密的联系,只是这类文章的切入点大多是着眼于获得同时包含其他信息的XML 结构片段.这类文章包括文献[20?22].文献[20]在XML 数据处理中引入元数据信息(meta-data,如数据的时新性、完整性以及敏感性),并提出了两个索引结构FMI(full meta-data index)和IMI(inheritance meta-data index)以支持对这类信息的管理;文献[21]则考察了XML 以及XPath 在语言数据(linguistic data)管理中的适用情况,进而给出了面向语言数据的查询语言——LPath;文献[22]尝试了如何管理XML 数据中的不确定信息的情况,例如,语义并不明确的Web 服务的信息,并提出了模糊树模LET $titles:=document (‘proceedings.xml’) //articles//title FOR $title in $titles RETURN ?titles ?
?title ?
?name ? $title ?/name ?
?/title ?
?/titles ? //issue//articles[.//author[text()=Botnich][@position=0]]//title
孔令波 等:XML 数据的查询技术 1405 型(fuzzy tree model)对这类信息进行管理.这类与XML Query 和XML IR 处理模式既有紧密联系同时又有所区别的思路,构成了XML 数据处理未来的研究方向之一.
1.2.2 XML IR 查询模式
如果说类似XPath 的查询处理是近期XML 数据处理的主要研究内容之一,那么,在XML 数据查询中吸收
传统信息检索[23]研究中的特点,如方便普通用户使用、
返回的结果能够体现与查询模式的相关程度等就成为当下XML 数据处理新的研究点.本文将针对向这一方向努力的查询方式记作XML IR 查询.
1.2.2.1 XML IR 查询模式概述
根据吸收信息检索特点方式的不同,XML IR 查询方式可以分为3个方面:扩展前述XML Query 查询语言(如XQuery)以吸收部分IR 特点的方式[24?29],本文称为XML IR/query 方式;另一种方式就是直接将对用户使用友好的关键字查询延伸至XML 数据[30?34],记为XML IR/keyword 方式;最后一种就是用户直接使用XML 片段来描述查询请求的方式[35],记作XML IR/fragment.图3(b)即为用XML 片段描述查询请求的示例.由于这种方式非常直接,而且有关的研究非常少,所以本文在此仅对XML IR/query 和XML IR/keyword 两种方式作简单的 概括.
(a) Xquery FT instance (b) XML IR/fragment instance
(a) XQuery FT 查询语句 (b) XML IR/fragment 查询语句
Fig.3 Query instances of XQuery FT and XML IR/fragment
图3 XQuery FT 和XML IR/fragment 查询语句
1.2.2.1.1 XML IR/query 模式
将IR 的特点吸收到XML Query 语言中,是XML IR 处理研究中的一个重要方面.早期的扩展多是针对IR 特性的某一方面进行的,例如,仅仅支持布尔查询的扩展,或者仅仅支持关键字相似性(keyword similarity)的扩展[36,37]以及针对邻近距离和相关性分级(proximity distance,relevance ranking)的扩展[24,29,30,38,39];而且,所扩展的XML Query 语言也是各种各样的,例如,2000年、2001年的XIRQL 扩展的便是XQL 查询语言.近期由于XQuery 在XML Query 查询处理中的突出地位,大多数的扩展还是基于XQuery 进行的.例如,2004年的TeXQuery [28]、FleXPath [29]和2005年的GalaTex [27].针对这一方向的研究,W3C 组织于2005年专门推出了覆盖全文检索特点的XQuery 扩展规范——XQuery FullText (XQuery FT),它在扩展的XQuery 中同时支持了经典全文检索所具有的一些主要特征,例如简单的关键字查询、布尔查询以及关键字-距离谓词(keyword-distance predicates).
在实际系统实现上,诸多原本针对IR 的搜索引擎也进行了扩展,以支持XML 数据上的搜索.为支持IR 的特点,这类引擎所支持的查询请求描述大多采用两类方法:一方面是引进文本和上下文相似性判断的操作来体现一定功能的结果分级机制;另一方面,大多数还是采取了在描述语言中引入XPath 部分功能的形式,并采取类似SQL 语句执行的方式,例如ELIXIR,XXL 以及XIRQL.
但是,从图3(a)给出的符合XQuery FT 规范的查询语句的实例可以看出,对普通的用户来说,想要掌握这类语句仍然具有相当的难度.
1.2.2.1.2 XML IR/keyword 模式
XML IR 查询的另一种重要方式就是直接将传统信息检索中的关键字查询方式应用到XML 数据中.主要有两种方式:一是直接将纯关键字方式不加修改地挪用到XML 数据的查询中;二是辅助信息限定关键字所在FOR $i IN document (“proceedings.xml”)//article WHERE $i //author contains ‘Cohen’
AND $i //title contains ‘Face’ AND $i //title contains ‘Recognition’ RETURN ?result ?
?author ? $i //author ?/author ? ?title ? $i //title ?/title ? ?/result ? ?article ? ?title ? Bibliography ?/title ? ?authors ? ?author ? Botnich ?/auhtor ? ?/authors ? ?/article ?
1406 Journal of Software 软件学报 V ol.18, No.6, June 2007 节点的范围,例如标签[26]或标签路径信息[40,41].Cohen Face Recognition 就是一个纯关键字的示例;后者的实际例子可以是Face+Recognition article: Author: Cohen,表示希望获取包含作者信息(Cohen)而且名称包含Face 和Recognition 的所有article 片段.由于后者引入的标签信息使得用户还要了解XML 数据的实际组织,增加了用户使用的复杂性,而且本质上讲,这种扩展关键字的方式只是增加了过滤关键字节点的作用,实际处理与纯关键字方式并无很大不同,所以,本节仅针对纯关键字形式的处理加以概括.虽然这种直接嫁接保留了原有的优点,但是由于前述XML 数据的独有特点,使得针对XML 数据的关键字处理具有了新的特征.例如,如何快速获得所有满足关键字组合语义的最紧致XML 片段的问题,实际研究中,研究者往往将这个问题转化为SLCA 问题[32].显然,它是XML 关键字查询处理的基本问题,有关它的讨论放到第2.2节;在获取了所有包含给定关键字的XML 片段后,另一个重要的问题就是XML 片段相似程度的计算(similarity measure).由于XML 片段具有结构信息,使得针对它的相似性计算在除了考虑传统的相似性以外,还需要考察结构的相似性.围绕这一问题的讨论内容较多,本文第3节对它进行了讨论.
1.2.2.2 XML IR 查询实现的要点
与传统的信息检索研究不同,针对XML 数据的IR 查询处理有着自己的特点,主要表现为两个方面:一是查询结果往往不是整个文档,而是XML 数据中的片段;二是针对所获XML 片段的相似性度量必须包含结构相似性的内容.这两个问题分别构成了XML IR 处理中的两个基本问题,对它们的叙述分别构成了第2.2节和第3节的内容.
1.3 XML 查询模式小结
图4显示了到2006年9月为止有关XML 数据查询研究的概括图.横轴对应于相关研究提出的时间,纵轴表示对应查询模式描述技术属于前述的3种查询模式XML Query,XML IR/query 和XML IR/keyword 中的哪 一种.
首先我们发现,对应XML Query 查询模式的研究目前已明显集中于W3C 组织推出的XPath 和XQuery 查询语言.其次,将信息检索中的技术特点吸收到XML 数据查询中体现了近几年XML 数据研究的一种趋势;在这一趋势中,扩展已有XML Query 查询的XML IR/query 方式处于主流地位,而且受XML Query 发展的影响,该方向的研究也越来越集中于W3C 的XQuery FT [42]查询语言的实现与扩充.至于吸收信息检索技术特点的XML IR/keyword 查询方式,其模式仍然是以关键字形式为主,并形成了两个研究的焦点:一个是SLCA 问题;另一个就是所获XML 片段的相似性计算问题.
Fig.4 Summary of query patterns for XML data by September, 2006
图4 XML 查询模式汇总图(截止到2006年9月)
199720002001199919982002
2003200420052006
孔令波等:XML数据的查询技术1407
2 XML查询处理
在大致了解了前述3种查询模式后,从当前研究专题中选取出如下两个问题作为本节的内容,它们是XML Query中的Twig问题以及XML IR/keyword中的SLCA问题.之所以选取这两个问题,是因为它们在各自的查询方式中所具有的突出地位,而且通过对这两个问题的讨论,可以帮助读者进一步了解查询处理的实现技术.例如,Twig查询模式是XML Query中较为复杂的查询形式,涵盖了XML Query查询方式的所有特点——结构包含、分支等;而SLCA对于XML IR/query和XML IR/keyword的意义可从第1.2.2节中得知.至于为什么没有将XML IR中的XML片段相似性度量的相关研究也放在这一节讲述,原因有二:一是该技术与查询实现相比相对独立;二是XML片段相似性度量技术研究本身内容丰富,可以单独作为一节进行讲述,即第3节的内容.
2.1 Twig查询模式的处理
2.1.1 问题描述
Twig是XML Query处理中一个重要的查询模式,其主旨就是搜索XML树得到满足树状结构的查询模式的结果.文献[12]给出的描述是当前该研究方向的参照,简要叙述如下:
首先是查询匹配问题.
给定具有n个节点的Twig查询模式Q和一个XML数据库G,Q在G中的一个匹配是指在Q的节点与G 的节点之间存在如下的映射关系:(i) 对应于查询节点的目标节点所含的数据必然满足查询节点上的谓词条件; (ii) 目标节点间的结构关系与查询节点组合间的结构关系必须一致,包括父亲-孩子关系和祖先-子孙关系.那么,具有n个节点Q模式的结果可表示为一个n元组的关系(d l,…,d n).
进而可定义Twig模式匹配问题为:给定Twig 查询模式Q和一个具有某种索引结构的XML数据库,所谓Twig模式匹配问题就是搜索XML数据库得到所有满足Q模式的XML数据片段,表示为n元组的形式.
2.1.2 研究概述
对Twig查询模式通行的求解算法大多采取如下步骤:
(1) 将Twig查询模式分解为二元结构关系(父亲-孩子,祖先-子孙);
(2) 利用结构连接的算法(即判断两元素满足结构关系的连接算法:Structural join algorithms)从XML数据库中寻找所有满足上述结构关系的节点集合;
(3) 将得到的中间结果合并为满足全部结构关系的最后结果.
直观地看,上述Twig查询模式求解方式中影响计算性能的因素主要有两个:一个是结构连接算法的效率;另一个就是将Twig模式分解的规模.显然,如果需要结构连接计算的数目少,整体的计算则必然会有较好的性能表现.在实际中,针对这一问题的求解除了前述两种思路外,还有一种为吸收流式处理方式的思路,分别叙述如下:
(1) 提高结构连接操作性能
采用这一思路的方式有两种:一是设计新的连接算法,如文献[43]中的MPMGJN(multi-predicate merge join)算法,其基本思路是,减少传统关系数据库中连接算法中构建全部连接记录之后过滤出所需结果的过程,采取按照所需进行连接的方式;第2种方式就是在结构连接中吸收XML索引结构信息,达到减少连接记录数目的目的[44,45],常用的XML索引形式为节点记录类编码中序号对索引形式的区间编码.这是因为对应节点的数值区间形式具有有效判断节点间结构关系的能力,从而达到筛选节点的目的.有关区间编码这一特点的更详细的叙述参见文献[2]的相关章节.
(2) 增大分解粒度
实际的算法包括文献[46?49].这类方法的基本思路就是采取增大Twig模式分解粒度以期达到减少结构判断操作的数目,从而提高整体计算的性能.需要指出的是,虽然文献[47]采取了FST(有限状态映射器finite state transducer)的机制,但是其求解Twig查询模式的基本方式促使我们将其归为这一类.其计算方式为:首先对Dewey编码进行扩展,使其能够蕴含对应节点标签路径的信息,在求解Twig查询模式时首先得到对应Twig查
1408 Journal of Software 软件学报 V ol.18, No.6, June 2007 询模式叶节点的所有扩展Dewey 编码,然后借助于FST 过滤出符合Twig 查询模式的节点集合.所以,本质上是将Twig 查询模式分解为路径之后求解的方式.
沿着这一思路,2006年,VLDB 中的文献[19]在吸收了XML 数据处理中结构索引(也称作结构摘要索引形式,参见文献[2]中的叙述)概念的基础上,进一步引入Twig 特征(twig feature)的技术.
(3) 流式处理
与前述两种方法不同,本节介绍的流式处理方式的基本思路为:首先依照Twig 查询模式设置相应的堆栈结构,每个堆栈对应Twig 查询模式中相应的节点,堆栈的排列次序与前序遍历Twig 查询模式时的节点次序相同;然后,顺序地扫描XML 数据,将扫描过程中遇到的对应于Twig 查询模式标签的节点顺序地压入对应的堆栈,当遇到对应于Twig 查询模式叶节点标签的节点时,回溯经过的相应堆栈,这样,符合Twig 查询模式结构关系的节点序列即为满足查询请求的结果[12,14,50,51].
该类方法的示意由图5给出[12],称为完整路径连接方式(holistic path join,简称HPJ).图中要注意的是,图5(c)中返回A 1B 2C 1路径结果的处理.当扫描图5(a)中的各节点遇到C 1时,HPJ 即着手根据堆栈中节点的情况构建相应的节点路径.首先看到S B 堆栈中最上一层的节点B 2,查看堆栈S A 中与它能够构成路径的节点只有A 2,所以返回A 2B 2C 1路径;进一步考察S A 中的A 1节点,由于它也与B 2相连接,所以,对应的A 1B 2C 1也是满足查询的节点路径.类似地,可以得到A 1B 1C 1.此时,S B 中已没有可用的节点,故可以将S C 中的C 1节点弹出.由于弹出C 1后S C 堆栈为空,这就意味着整个处理已结束.
(a) Data (b) Query (c) Stacks (d) Result
(a) 数据 (b) 查询 (c) 堆栈 (d) 结果
Fig.5 Holistic path join processing
图5 完整路径连接处理示意
根据上面对HPJ 处理的叙述,显然可以利用XML 数据编码信息帮助判断各节点的结构关系,这一思路正是后续3篇文献[14,50,51]的工作之一;除此之外,它们大多也考虑了更为复杂的Twig 查询模式的处理,如文献[14]提出了完整Twig 连接(holistic twig join,简称HTJ),文献[51]吸收了结构摘要的信息.但是,基本的处理还是延续了文献[12]的概念. 2.2 XML 关键字查询中的SLCA 问题
2.2.1 问题描述
对于XML 数据的关键字查询来说,基本操作就是找到包含给定关键字的XML 片段的根节点:SLCA 节点. 定义4. SLCA 问题:给定一棵标签有向树G =(V G ,E G ,r ,A )以及一组关键字W ={k 1,k 2,…,k k },那么,SLCA 问题就是确定满足给定关键字的最紧致XML 片段的根节点的问题.所谓最紧致XML 片段(XML 子树)S 是指S 具有如下特征:
(1) 全部关键字都出现于S 的叶节点中;
(2) S 中的任意子树都不可能包含全部关键字.
当前,针对SLCA 问题的求解方法多与Dewey 编码有着紧密的联系,主要原因就是因为Dewey 编码包含了该节点所在节点路径上所有节点的Dewey 码信息,而这些信息对于建立节点与路径的关联关系,也就是关键字所在节点间的结构关系,有着实际的便利.图1(b)即为包含Dewey 码的SLCA 问题示意:由实线围起来的XML 片段即为对应于关键字Cohen Face Recognition 的最紧致XML 片段,该片段根节点即为SLCA 节点.从中可以发现,对应SLCA 节点的Dewey 码和关键字所在节点的Dewey 码具有有趣的关联:作为SLCA 节点的article 节A 1
B 1
A 2
B 2
C 1A B C C B A A 1B 1C 1A 1B 2C 1A 2B 2C 1
孔令波 等:XML 数据的查询技术 1409 点的Dewey 码为0.0.0.1,关键字Face Recognition 所在节点的Dewey 码为0.0.0.1.0,另一个关键字Cohen 所在节点的Dewey 码为0.0.0.1.1.0,借助文献[2]中介绍的Dewey 编码知识可知,SLCA 节点的Dewey 码正是两个关键字所在节点Dewey 码的最长公共前缀.
需要指出的是,当一个XML 文档中包含有多个对应同一关键字的节点时,计算最合适的SLCA 节点并不能通过求解包含关键字的节点的Dewey 码的最长公共前缀简单地解决.
2.2.2 研究概述
针对SLCA 问题,文献[32]归纳出了3种算法:Indexed Lookup Eager (ILE)算法、Scan Eager (SE)算法和Stack 算法[33].鉴于Dewey 编码具有能够提供路径内部节点信息的能力,所以,这3种算法都是基于Dewey 编码的.文中声称ILE 算法具有较好的性能,其流程概述如下:
(1) 首先修改B+-索引树结构.
一是使它能够实现对(keyword,dewey)类型数据的支持,其中的keyword 表示感兴趣的关键字字符串,dewey 则表示Dewey 码.记修改后的B+-树结构为DBPT(dewey B-plus tree).显然,DBPT 必须支持Dewey 数据上的运算,包括Dewey 码的大小、包含、公共前缀(lca)以及求解两Dewey 码中的处于子孙位置的Dewey 码的descendant 运算.
此外,DBPT 还必须实现两个基本的运算,即lm(dewey, keyword)和rm(dewey, keyword),二者的目的分别是搜索DBPT 从所有关键字为给定keyword 的Dewey 码集合中得到小于/大于(smaller/greater than)给定dewey 码的最大/最小Dewey 码.
(2) 得到对应给定关键字组k 1,k 2,...,k k 的Dewey 码集合D 1,D 2,...,D k .
D i 是所有包含关键字k i 的Dewey 码集合,并按照每个集合包含的元素数目的多少(即集合“势”的概念)进行排序,其中,D 1对应于元素数目最少的Dewey 码集合.
(3) 那么,基于Dewey 码集合D 1,D 2,...,D k 求解SLCA 节点ILE(slca (D 1,...,D k ))算法可用如下的公式来表达:
????????=∈∪1
),...,},({),...,(21D v k k D D v slca stor removeAnce D D slca , 其中的slca ({v },D 1,…,D k )运算由如下公式确定:
slca ({v },D 2,...,D k )=slca (slca ({v },D 2,...,D k ?1),D k ),
而从一个Dewey 码集合D i 中寻找与一个Dewey 码v 匹配的最佳SLCA 节点的Dewey 码的计算,由如下公式确定:
slca ({v },D i )={descendant (lca (v ,lm (v ,D i )),lca (v ,rm (v ,D i )))}.
从这3个计算公式可以看出,对D 1中的任意个Dewey 码都要在DBPT 上执行(k ?1)次lm 和rm ;在得到对应lm 和rm 运算的两个Dewey 码后,ILE 还需要运行两次lca 运算以及一次descendant 运算才能从中计算得到一个准SLCA 节点Dewey 码.
进一步考虑实际实现:由于无法确定用户会输入哪些关键字,所以,ILE 必须依据全部的XML 节点构建DBPT 结构,如果XML 数据有N 个节点,并取B+树的分叉数为m ,根据数据结构的理论,BPT 的高度不会
小于??N m log ,那么,ILE 算法总共要进行??N m D k log ||)1(1××?次的rm 和lm 运算.如果考虑到对应关键字的节点数 目往往远远小于XML 数据中的节点数目N ,则以判断出由于ILE 必须依赖全部XML 节点求解SLCA,其计算效率并不高.所以,提高SLCA 节点的求解效率仍然是需要妥善解决的问题.
3 XML 片段的相似性度量
在获取了满足给定关键字的最紧致XML 片段后,XML IR/keyword 查询处理的另一个重要步骤就是如何计算XML 片段间相似程度的问题.由于这个问题的有关研究内容较多,所以专门在小节对该问题进行讲述,尽管它是XML IR/keyword 查询处理的重要环节.
在第1.1节中提到XML 数据的重要特点之一就是它的结构性,满足给定关键字的XML 片段同样具有这一
1410 Journal of Software 软件学报 V ol.18, No.6, June 2007 特点,所以,衡量XML 片段间相似程度的问题就不可能回避其结构信息.现有针对此问题的研究可分为两类:一类基于树结构编辑距离的方法;另一类统信息检索中TF*IDF 技术深刻影响的近似方法.
3.1 基于树编辑距离的相似性度量
这类方法的核心就是标签有向树结构编辑距离的概念[52,53].
定义5. 标签有向树结构编辑距离:基于标签有向树结构G =(V ,E ,r ,A ),可定义3种编辑操作:更名(rename,即将某一节点的标签修改为另一标签)、删除某节点(delete)和插入一节点操作(insert),并指定3种编辑操作的代价分别为C R ,C D 和C I .对应两个标签有向树T 1和T 2间的编辑脚本s ,是指在仅仅使用前述3种编辑操作的前提下将T 1转换为T 2的编辑操作的序列,其编辑代价记作γ(s ),表示s 中全部编辑操作代价之和.由于每个编辑操作都对应一个编辑代价,那么,所有将T 1转换为T 2的编辑脚本S 中代价最小的那个脚本就是最优编辑脚本(optimal edit script),其编辑代价值就是T 1和T 2之间的编辑距离.记作EDist (T 1,T 2),即)}({min ),(21s T T EDist S
s γ∈=. 虽然标签有向树结构的编辑距离有着清晰的表述形式,但是其实际计算往往过于复杂,从而研究者更多地关注于吸收传统信息检索TF*IDF 技术[23]的近似方法.
3.2 相似性度量近似方法
由于本节的近似方法与传统信息检索中的TF*IDF 技术有着紧密的联系,因此本节首先简要地回顾传统信息检索中TF*IDF 技术.然后将针对XML 片段相似性度量的近似方法分为4种类型:基于TF*IDF 的回归方法、结构化的TF*IDF 方法、MLP(叶节点路径最大值:maximum leaf path)方法和路径包模型(path bag model).
3.2.1 传统的TF*IDF 技术
传统信息检索处理有一个非常鲜明的特点,那就是查询处理返回的结果总是与用户提供的查询模式最为相关的部分结果.例如Top-k ,k -NN(k nearest neighbor)查询结果显示功能.为了实现这一功能,就需要信息检索处理具有衡量所获结果与给定查询模式的相似程度的能力,即 Ranking 机制或相似性度量机制(similarity measure).传统信息检索领域针对这一问题提出了许多解决办法,详细情况请参见文献[23],其中最具代表性的就是向量空间模型(vector space model,简称VSM)和TF*ID 计算方法.
向量空间模型是TF*IDF 技术的基础,其基本思路是:首先从查询目标文档(d 1,d 2,...,d N ,N 为文档的数目)中提取出感兴趣的文字单元(term unit),并利用文字单元组成的向量——(t 1,t 2,...,t m ),m 为文字单元的数目——作为近似文档内容的形式,那么,文档(d j )和关键字(q )都可看作是向量空间中的点,然后即可利用向量空间中点距离的知识来计算文档d j 与关键字q 之间的近似程度. 基于这一思路,TF*IDF 计算方法如下:首先确定对应关键字的统计向量),...,,(,,2,1q m q q w w w q = 与对应文档d j 的统计向量),...,,(,,2,1j m j j j w w w d = 表示.其中,统计信息w i ,j (1≤i ≤m )计算如下:首先确定文字单元t i 在文档d j 出现 的频率freq i ,j ,进而确定该文字单元在所有文档中出现频率的最大值max l freq l ,j ,并记n i 表示包含文字单元t i 的文档数目,那么,tf i ,j 和idf i 可根据如下公式计算(tf i ,q 的计算也类似):
j l l j i j i freq freq tf ,,,max =,i
i n N idf log =. 文字单元t i 在文档d j 的权重计算如公式:w i ,j =tf i ,j ×idf i .
而文字单元t i 在关键字模式q 中的权重信息w i ,q (1≤i ≤m )计算如下(在实际研究中还有其他计算形式):
w i ,q =(0.5+0.5tf i ,q )×idf i .
于是,基于向量空间的距离理论,文档d j 与关键字模式q 之间的距离可计算如下:
∑∑∑===××=×?=m i q
i m i j i m
i q i j i j j j w w w w q d q d q d sim 12,12,1,,||||),( .
可见,基于VSM 的TF*IDF 计算方法具有两个基本的技巧:首先是文字单元,即将查询目标与查询模式都看
孔令波 等:XML 数据的查询技术 1411 作是由文字单元为基本元素构成向量的思路;其次就是利用向量空间的距离理论计算近似的相似程度.XML 片段的相似性判断近似方法大多延续了TF*IDF 计算的技巧——抽取XML 数据中的部分信息作为“单元”(例如标签路径[54]、小枝[55]等),然后将查询模式和XML 片段都映射为“单元”向量空间中的点,然后利用向量空间的距离公式计算XML 片段的相似性.
为了便于读者直观地了解后续近似方法的讨论,在此给出3个XML 片段,如图6所示.其中,图6(b)和图6(c)都是通过交换图6(a)中的某两个节点得到的片段.直观地看,图6(a)和图6(c)仍具有相同的结构;而图6(a)和 图6(b)的结构则不相同.
(a) Source XML fragment (b) Exchanging k 1 and k 4 (c) Exchanging k 2 and k 3
(a) XML 源片段 (b) 交换k 1和k 4后的片段 (c) 交换k 2和k 3后的片段
Fig.6 Three XML fragments with same labels
图6 标签相同的3个XML 片段
3.2.2 基于TF*IDF 的回归方法[31,33,35,55?57]
本质上讲,这类方法可以看作是一种基于叶节点文本统计特性的多元回归问题,即首先直接利用TF*IDF 方法计算XML 片段中叶节点的统计值,之后利用XML 片段中叶节点到SLCA 节点间的相对位置信息为参数求解对应于SLCA 节点的影响因子.所以,这种方法并不能有效地捕捉XML 片段的结构特征,即这类方法通常不能区分图6(a)和图6(b)之间的结构差异,而是会将它们作为同一结构.
3.2.3 结构化的TF*IDF 方法[55,58?61]
这类方法同样吸收了TF*IDF 技术中“单元(term)”的概念,只是此时的“单元”变成了具有结构信息的“Twig 单元(twig unit)”.所以,这类方法的核心就是如何分解XML 数据,以便得到能够体现XML 数据结构特征的“Twig 单元”向量.实践证明,这种分化的计算是复杂的.文献[55]也承认了这一点,并在提出了较为严格的关于“Twig 单元”分解的计算方法后,将注意力转到了类似路径包模型的近似计算方法上.文献[58?60]中的工作与此类似.这类方法不仅计算复杂,而且对XML 数据的标签信息以及片段节点的相对位置信息是敏感的,对来自不同XML 模式的XML 片段的相似性判断也就无能为力.而从不同来源的XML 数据中搜寻符合某关键字的信息,是有着实际的意义的.
3.2.4 MLP (maximum leaf path)[62]
这里提出的计算方法与其他近似方法都不相同,它将XML 片段
的相似性度量的计算分成了两个部分.其中一部分为引入MLP 概念,
进而构建MLP 向量以捕捉XML 片段的结构特征.所谓MLP 就是指
某节点到以之为根的所有叶节点的最长距离,如图7所示.另一部分
是利用节点标签集合的覆盖程度来捕捉XML 片段的语义相似性.但
是,基于MLP 向量的方法在捕捉XML 片段的结构特征上并不理想.
例如,如果将图7中的根节点所含的空白叶节点移到其左侧灰节点,
则前后的结构是不同的,但MLP 向量还是相同的.所以,图6(a)和
图6(b)之间的结构差异也就不能分辨. Fig.7 Illustration of MLP concept 图7 MLP 示意图
1412
Journal of Software 软件学报 V ol.18, No.6, June 2007
3.2.5 路径包模型[54,63] 这类方法的核心思想是,采用XML 片段中标签路径的分布信息作为XML 片段结构特征的近似.由于它们没有考虑到节点间的关联结构,而且对节点标签也是敏感的,所以,这类方法就不能区分图6中3个XML 片段的结构差异,这是因为它们具有相同的标签路径.为了弥补这一缺陷,文献[63]进一步引入了节点位置信息,以区分不同的分叉.然而,这种扩展也引入了不利的因素,即对节点的相对位置信息敏感,从而会将结构相同的图6(a)和图6(c)区分为不同的结构.
3.3 XML 片段相似性度量方法小结
作为传统信息检索中重要的概念,查询结果的相似性比较同样在XML 关键字查询中具有重要的意义.相关研究算法的汇总由表1给出.从中可以看出,针对这一问题的研究方法主要分为两类:一类是基于数结构编辑距离的方法;另一类是延续TF*IDF 概念的近似方法.
由于前者实现的复杂性使得近期的研究更多地集中于近似方法上,可分为4种类型:基于TF*IDF 的回归方法、结构化的TF*IDF 方法、MLP 方法和路径包模型.但是,当集中考察各方法在捕捉XML 片段的结构特征上的表现后发现,这些近似方法存在如下不足:即不能很好地分辨XML 片段结构上的细微差异,而且部分算法也过多地依赖于XML 数据的标签或节点相对位置信息,从而不能满足XML 片段来自不同XML 数据源的情况.
总之,当前,针对XML 片段相似性度量的研究还有待进一步深入.其中,设计既能够有效地捕捉XML 片段结构上的细小差异,同时又不必过多地依赖于XML 片段中标签、节点相对位置信息的新方法,是一个值得关注的研究点.
Table 1 Summarization for similarity measures of XML fragments
表1 XML 片段相似性度量方法概述 Similarity measure Reference Year Class Subclass Description
Tree edit distance [52,53] 1992, 1997, 2005 Accurate method Tree edit distance ? Three edit operations: -Rename, delete, and insert ? Smallest edit cost ? Complicated to computing
Regression TF*IDF [31,33,35] [55?57] 2003~ 2005 Regression TF*IDF ? TF*IDF at leaf nodes
? Using hierarchical information as regression parameters ? Be insensitive to the structural
difference
UBDist [58] 2002
Structural terms [61] 2002 Twig units [55] 2005 Binary branch distance [59] 2005 pq -Grams [60] 2005 Structural TF*IDF ? Structural term is the kernel ? Structural term vector distance as the similarity measure ? Be dependent of labels or node positions ? Complicated to computing
Path bag model [54,63] 2002, 2003 Path bag model ? Label path vector is the kernel ? Similarity measure is the vector
distance ? Be dependent of labels or node positions
? Be insensitive to the structural
difference
MLP [62] 2004 Approximate methods MLP ? Two parts: Structural similarity
+ Semantic similarity
? MLP vector is the kernel for structural similarity measure
? Be insensitive to the structural
difference 4 总结与研究展望
4.1 XML 查询技术小结
XML 数据管理的研究已经受到数据库研究领域的广泛关注.其中,针对XML 数据的查询技术的研究有着
孔令波等:XML数据的查询技术1413
特殊的意义:首先,数据管理的最终目的还是需要用户使用,而查询方式则是与用户直接相关的第一层机制;其次,查询方式也深切地影响到XML数据处理实现的方方面面,例如,不同查询模式的处理就需要不同索引机制.所以,对当前有关XML数据查询的研究作汇总也就有着实际的意义.需要说明的是,虽然当前XML数据处理方式有两种——流式XML数据处理形式和传统XML数据处理形式,但在XML查询描述形式上,二者有着相同的形式.
在广泛调研的基础上,本文首先将相关的查询方式分为两大类,分别为XML Query查询方式和XML IR查询方式.其中,后者又可以分为3个小类,分别为XML IR/query方式、XML IR/keyword方式以及XML IR/fragment方式,并归结出3个受到广泛关注的研究问题,分别为XML Query中的Twig查询模式、XML IR中的XQuery FT的实现以及XML IR/keyword中的SLCA问题和XML片段相似性度量问题.
在本文的书写过程中,我们深切地感受到,尽管前期我们针对XML数据的索引技术作了汇总[2],但是要真正理解各种各样的索引技术背后的“所以然”,还是需要回到宏观的查询层上面.这也是让我们坚持完成本文,进而希望图帮助相关研究者对相关研究内容有所了解的原因.
4.2 研究展望
除了沿着传统的XML数据处理继续深入以外(例如查询优化、索引技术、Twig处理、XQuery FT实现[68]等),在通观现有相关研究的基础上,本文认为吸收传统信息检索特点的XML IR查询会是值得进一步深入探讨的方向,其中,方便普通用户使用的XML IR/keyword查询形式的处理尤其值得研究人员的关注.沿着这个方向进行思考,认为有两个问题值得进一步探讨:结构化关键字查询描述及结构相似性度量和XML数据处理系统的数据冗余,分别对应第 4.2.1节和第 4.2.2节.此外,根据2006年最新的研究文献,与XML Query(包括XML IR/query)有关的进一步研究可概括出两个值得关心的方向,分别为XML Query查询的理论研究及其实现(对应于第4.2.3节)和新应用背景下的XML数据的管理(对应于第4.2.4节).
4.2.1 结构化关键字查询描述及结构相似性度量
我们知道,结构信息对于XML数据而言有着突出的重要地位,但是,现有关键字的扩展方式在这一点上的表现差强人意——只是借助于标签或标签路径信息达到过滤关键字所在节点的目的,而不能提供更多的结构信息.因此,赋予XML IR/keyword查询以结构信息也就有着实际的研究价值:不仅有利于用户结构化组织感兴趣的关键字从而赋予查询模式更多的信息,而且也有利于减少查询过程中临时XML片段的数目.
这里要注意的是,新的机制虽然能够描述关键字间的结构信息,但却不应当以增加用户使用的难度为代价.例如,前述的关键字扩展形式就需要用户了解XML数据的组织信息.具有这两个特点的新型关键字查询模式由于没有标签信息的约束,基于它的查询就可以覆盖模式不同的XML数据,这一点是与纯关键字形式的查询能力相同的.
与之紧密相关的另一个问题就是研制结构与内容相分离的相似性度量技术.既然获得的XML片段可以来自不同的XML模式,那么,现有与标签信息有关的XML片段相似性度量方法也就无能为力,而且现有方法对结构差异不敏感的缺陷也需要研究人员提出新的方法.针对这一问题,MLP方法中将结构相似性和语义相关性度量相分离的方式是一个有益的启发.
4.2.2 XML数据处理系统的数据冗余
既然是针对XML数据查询的调研,过程中也就自然地考察了相关XML数据处理系统的实现情况.与前述XML数据查询的分类相吻合,有关的系统实现也能够很好地归入相关的类别中,这在一定程度上也说明了本文分类的合理性.在绘制完成查询模式汇总图的图4之后,我们意识到,当前XML数据处理系统中存在着数据冗余的现象,即支持XML Query查询的系统与支持XML IR/keyword查询的系统都必须各自维护一套XML数据的转换格式,即便查询的目标是同一个XML文档.这一点也可以通过当前XQuery/FT通行的实现架构得到验证:它们通常采取全文检索和XQuery处理松散结合的架构形式,而没有统一的索引结构[27?29].
文献[64]的基本索引结构形式为倒排索引与节点序号类索引混合的形式.但是,该文只是简单地延续了传统关键字查询中得到目标文档所含关键字位置信息的处理,而没有意识到XML数据上的关键字查询应以最紧
1414 Journal of Software软件学报 V ol.18, No.6, June 2007
致XML片段的求取为特征的,而根据第2.2节以及对XML索引机制的了解[2],不论是文中的倒排表还是节点序号类索引,是不能有效地完成这样的计算的.文献[65]提出了将节点序号对索引与结构摘要索引相结合的复合索引结构:在得到XML数据的1-Index结构摘要后,对结构摘要中的节点赋予唯一的标示,然后将其与扩展节点序号对索引相结合.借助于结构摘要的特性,该索引方式可以支持XML数据的结构查询;而借助于基于堆栈的算法[32,33],该索引结构也能够支持包含关键字的查询,但是,由于直接依赖于结构摘要索引结构,该方式就不能避免第1.2节中提到的不足,而且根据文献[32]中的结论,基于堆栈的SLCA问题求解方案,其性能也并不占优. 4.2.3 XML Query查询的理论研究及其实现
有感于关系代数对于关系数据管理的重要性,如何在理论上探讨XML数据管理,一直以来都是研究者关注的热点之一.由于描述这类数据的XML规范已经相对稳定,这类理论上的探讨也就更多地集中于XML数据的查询.文献[66,67]是针对这一方向的两个最新的研究成果.
此外,在XQuery FullText版本推出来之后,如何有效地实现XQuery/FT的查询机制,也就成为数据库研究人员需要着手解决的问题.到目前为止,支持大部分XQuery/FT特性的研究也只有文献[27]的GalaTex系统.该系统在原有实现XQuery查询的Galax系统上引入倒排表机制,以支持XQuery/FT中的与文本查询有关的特点,其实现的策略可以适用于其他基于XQuery查询引擎的XQuery/FT实现.尽管如此,XQuery/FT的复杂性决定了针对它的实现还是存在许多值得研究的问题.例如,如何更有效地实现支持全文本查询相关的算子以及如何设计更为合理的程序框架,包括其索引机制的设计、查询执行流程的优化、目标XML片段的相关性计算等等.2006年,SIGMOD的Complex FT[68]就是在这一方向的努力结果.
4.2.4 新应用背景下的XML数据的管理
正如第1.2.1.2节中提到的,将不同应用领域的数据以XML形式进行保存已日渐为研究者所采纳.虽然这类数据的管理可以自然地吸收现有XML数据管理研究的成果,但是,不同应用领域的不同特点也使得对这类XML数据的管理有了独特的要求.如何开发能够满足这类要求的技术,也就成为未来研究值得关注的又一个方向.
References:
[1] Meng XF, Zhou LX, Wang S. State of the art and trends in database research. Journal of Software, 2004,15(12):1822?1836 (in
Chinese with English abstract). https://www.doczj.com/doc/fb1171485.html,/1000-9825/15/1822.htm
[2] Kong LB, Tang SW, Yang DQ, Wang TJ, Gao J. XML indices. Journal of Software, 2005,16(12):2063?2079 (in Chinese with
English abstract). https://www.doczj.com/doc/fb1171485.html,/1000-9825/16/2063.htm
[3] Abiteboul S, Quass D, McHugh J, Widom J, Wiener J. The Lorel query language for semistructured data. Int’l Journal on Digital
Libraries, 1997,1(1):68?88.
[4] Deutsch A, Fernandez M, Florescu D, Levy A, Suciu D. A query language for XML. Computer Networks, 1999,31(11?16):
1155?1169.
[5] Ceri S, Comai S, Damiani E, Fraternali P, Paraboschi S, Tanca L. XML-GL: A graphical language for querying and restructuring
XML documents. Computer Networks, 1999, 31(11?16):1171?1187.
[6] Chamberlin D, Robie J, Florescu D. Quilt: An XML query language for heterogeneous data sources. In: Suciu D, Vossen G, eds.
Proc. of the Int’l Workshop on the Web and Databases (WebDB 2000). Dallas: Springer-Verlag, 2000.1?25.
[7] Clark J, DeRose S. XML Path Language (XPath) Version 1.0 W3C Recommendation. World Wide Web Consortium, 1999.
https://www.doczj.com/doc/fb1171485.html,/TR/xpath
[8] Chamberlin D. XQuery: A query language for XML W3C working draft. Technical Report, WD-xquery-20010215, World Wide
Web Consortium, 2001. https://www.doczj.com/doc/fb1171485.html,/TR/xquery/
[9] Li QZ, Moon B. Indexing and querying XML data for regular path expressions. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S,
Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int’l Conf. on Very Large Data Bases (VLDB). Rome: Morgan Kaufmann Publishers, 2001. 361?370.
孔令波等:XML数据的查询技术1415
[10] Cooper BF, Sample1 N, Franklin MJ, Hjaltason GR, Shadmon M. A fast index for semistructured data. In: Apers PMG, Atzeni P,
Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int’l Conf. on Very Large Data Bases (VLDB).
Rome: Morgan Kaufmann Publishers, 2001. 341?350.
[11] Zhang C. Relational databases for XML indexing [Ph.D. Thesis]. Wisconsin: University of Wisconsin-Madison, 2002.
[12] Bruno N, Koudas N, Srivastava D. Holistic twig joins: Optimal XML pattern matching. In: Franklin MJ, Moon B, Ailamaki A, eds.
Proc. of the 2002 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Madison: ACM Press, 2002. 310?321.
[13] Amer-Yahia S, Cho S, Lakshmanan LVS, Srivastava D. Minimization of tree pattern queries. In: Aref WG, ed. Proc. of the 2001
ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Santa Barbara: ACM Press, 2001. 497?508.
[14] Jiang HF, Wang W, Lu HJ, Yu JX. Holistic twig joins on Indexed XML documents. In: Freytag JC, Lockemann PC, Abiteboul S,
Carey MJ, Selinger PG, Heuer A, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases (VLDB). Berlin: Morgan Kaufmann Publishers, 2003. 273?284.
[15] Chen ZY, Jagadish HV, Korn F, Koudas N. Counting twig matches in a tree. In: Young DC, ed. Proc. of the 17th Int’l Conf. on
Data Engineering (ICDE). Heidelberg: IEEE Computer Society, 2001. 595?604.
[16] Lee DW, Srivastava D. Counting relaxed twig matches in a tree. In: Lee YJ, Li JZ, Whang KY, Lee DH, eds. Proc. of the 9th Int’l
Conf. on Database Systems for Advances Applications (DASFAA). LNCS 2973, Springer-Verlag, 2004. 88?99.
[17] Jagadish HV, Al-Khalifa S. TIMBER: A native XML database. The VLDB Journal, 2002,11(4):274?291.
[18] Meng XF, Wang Y, Wang XF. Research on XML query optimization. Journal of Software, 2006,17(10):2069?2086 (in Chinese
with English abstract). http://www.jos. https://www.doczj.com/doc/fb1171485.html,/1000-9825/17/2069.htm
[19] Zhang N, ?zsu MT, Ilyas IF, Aboulnaga A. FIX: Feature-Based indexing technique for XML documents. In: Dayal U, Whang KY,
Lomet DB, et al., eds. Proc. of the 32nd Int’l Conf. on Very Large Data Bases (VLDB). Seoul: ACM Press, 2006. 259?270.
[20] Cho SR, Koudas N, Srivastava D. Meta-Data indexing for XPath location steps. In: Chaudhuri S, Hristidis V, Polyzotis N, eds. Proc.
of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Chicago: ACM Press, 2006. 455?466.
[21] Bird S, Chen Y, Davidson SB, Lee HJ, Zheng YF. Designing and evaluating an XPath dialect for linguistic queries. In: Liu L,
Reuter A, Whang KY, et al., eds. Proc. of the 22nd Int’l Conf. on Data Engineering (ICDE). Atlanta: IEEE Computer Society, 2006.
52.
[22] Abiteboul S, Senellart P. Querying and updating probabilistic information in XML. In: Ioannidis YE, Scholl MH, eds. Advances in
Database Technology, Proc. of the 10th Int’l Conf. on Extending Database Technology (EDBT 2006). Munich: Springer-Verlag, 2006. 1059?1068.
[23] Baeza-Yates R, Ribeiro-Neto B, et al. Modern Information Retrieval. Pearson Education Limited, 1999.
[24] Fuhr N, Groβjohann K. XIRQL: A query language for information retrieval in XML documents. In: Croft WB, Harper DJ, Kraft
DH, Zobel J, eds. Proc. of the 24th Annual Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval (SIGIR).
New Orleans: ACM Press, 2001. 172?180.
[25] Barg M, Wong RK. Structural proximity searching for large collections semi-structured data. In: Paques H, Liu L, Grossman D, eds.
Proc. of the ACM Conf. on Information and Knowledge Management (CIKM). Atlanta: ACM Press, 2001. 175?182.
[26] Cohen S, Mamou J, Kanza Y, Sagiv Y. XSearch: A semantic search engine for XML. In: Freytag JC, Lockemann PC, Abiteboul S,
Carey MJ, Selinger PG, Heuer A, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases (VLDB). Berlin: Morgan Kaufmann Publishers, 2003. 45?56.
[27] Curtmola E, Amer-Yahia S, Brown P, Fernàndez M. GalaTex: A conformant implementation of the XQuery FullText language. In:
Florescu D, Pirahesh H, eds. Proc. of the 2nd Int’l Workshop on XQuery Implementation, Experience, and Perspectives (XIME-P).
Baltimore: ACM Press, 2005. 1024?1025.
[28] Amer-Yahia S, Botev C, Shanmugasundaram J. TeXQuery: A FullText search extension to XQuery. In: Feldman SI, Uretsky M,
Najork M, Wills CE, eds. Proc. of the 13th Conf. on World Wide Web (WWW). Manhattan: ACM Press, 2004. 583?594.
[29] Amer-Yahia S, Lakshmanan LV, Pandit S. FleXPath: Flexible structure and full-text querying for XML. In: Weikum G, K?nig AC,
Deβloch S, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Paris: ACM Press, 2004. 83?94.
1416 Journal of Software软件学报 V ol.18, No.6, June 2007
[30] Balmin A, Papakonstantinou Y, Hristidis V. A system for keyword proximity search on XML databases. In: Freytag JC,
Lockemann PC, Abiteboul S, Carey MJ, Selinger PG, Heuer A, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases (VLDB). Berlin: Morgan Kaufmann Publishers, 2003. 1069?1072.
[31] Weigel F, Meuss H, Schulz KU, Bry F. Content and structure in indexing and ranking XML. In: Amer-Yahia S, Gravano L, eds.
Proc. of the 7th Int’l Workshop on the Web and Databases (WebDB). Maison de la Chimie: ACM Press, 2004. 67?72.
[32] Xu Y, Papakonstantinou Y. Efficient keyword search for smallest LCAs in XML databases. In: Ozcan F, ed. Proc. of the ACM
SIGMOD Int’l Conf. on Management of Data (SIGMOD). Baltimore: ACM Press, 2005. 537?538.
[33] Guo L, Shao F, Botev C, Shanmugasundaram J. XRANK: Ranked keyword search over XML documents. In: Halevy AY, Ives ZG,
Doan A, eds. Proc. of the 2003 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). San Diego: ACM Press, 2003.
16?27.
[34] Florescu D, Kossmann D, Manolescu I. Integrating keyword search into XML query processing. https://www.doczj.com/doc/fb1171485.html,/w9cdrom/
index.html
[35] Carmel D, Maarek YS, Mandelbrod M, Mass Y, Soffer A. Searching XML documents via XML fragments. In: Proc. of the 26th
Annual Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval (SIGIR). Toronto: ACM Press, 2003.
151?158.
[36] Chinenyanga T, Kushmerick N. Expressive and efficient ranked querying of XML data. In: Mecca G, Siméon J, eds. Proc. of the
4th Int’l Workshop on the Web and Databases (WebDB 2001). Santa Barbara: ACM Press, 2001. 1?6.
[37] Theobald A, Weikum G. The index-based XXL search engine for querying XML data with relevance ranking. In: Jensen CS,
Jeffery KG, Pokorny J, eds. Proc. of the 8th Conf. on Extending Database Technology (EDBT). Prague: Springer-Verlag, 2002.
477?495.
[38] Bremer JM, Gertz M. XQuery/IR: Integrating XML document and data retrieval. In:Fernandez MF, Papakonstantinou Y, eds. Proc.
of the 5th Int’l Workshop on the Web and Databases (WebDB). Madison: ACM Press, 2002. 1?6.
[39] Hayashi Y, Tomita J, Kikui G. Searching text-rich XML documents with relevance ranking. In: Proc. of the SIGIR Workshop on
XML and Information Retrieval.2000. https://www.doczj.com/doc/fb1171485.html,/sigir00-xml/final-papers/Hayashi/hayashi.html
[40] Schmidt A, Kersten LM, Windhouwer M. Querying XML documents made easy: Nearest concept queries. In: Young DC, ed. Proc.
of the 17th Int’l Conf. on Data Engineering (ICDE). Heidelberg: IEEE Computer Society, 2001. 595?604.
[41] Graupmann J, Schenkel R, Weikum G. The SphereSearch engine for unified ranked retrieval of heterogeneous XML and Web
documents. In: B?hm K, Jensen CS, Haas LM, et al., eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB).
Trondheim: ACM Press, 2005. 529?540.
[42] XQuery 1.0 and Xpath 2.0 fulltext. W3C Working Draft 1, 2006. https://www.doczj.com/doc/fb1171485.html,/TR/xquery-full-text/
[43] Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database management systems.
In: Aref WG, ed. Proc. of the 2001 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Santa Barbara: ACM Press, 2001. 425?436.
[44] Wang J, Meng XF, Wang S. Structural join of XML based on range partitioning. Journal of Software, 2004,15(5):720?729 (in
Chinese with English abstract). https://www.doczj.com/doc/fb1171485.html,/1000-9825/15/720.htm
[45] Wan CX, Liu YS, Xu SH, Liu XP, Lin DH. Indexing XML data based on region coding for efficient processing of structural joins.
Chinese Journal of Computers, 2005,28(1):113?127 (in Chinese with English abstract). https://www.doczj.com/doc/fb1171485.html,/qwjs/view.asp?id=1746 [46] Wang J, Meng XF, Wang Y, Wang S. Target node aimed path expression processing for XML data. Journal of Software, 2005,
16(5):827?837 (in Chinese with English abstract). https://www.doczj.com/doc/fb1171485.html,/1000-9825/16/827.htm
[47] Lu JH, Ling TW, Chan CY, Chen T. From region encoding to extended Dewey: On efficient processing of XML twig pattern
matching. In: B?hm K, Jensen CS, Haas LM, Kersten ML, Larson P, Ooi BC, eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB). Trondheim: ACM Press, 2005. 193?204.
[48] Chen Y, Davidson SB, Zheng YF. BLAS: An efficient XPath processing system. In: Weikum G, K?nig AC, De?loch S, eds. Proc.
of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Paris: ACM Press, 2004. 47?58.
孔令波等:XML数据的查询技术1417
[49] Wang W, Wang HZ, Lu HJ, Jiang HF, Lin XM, Li JZ. Efficient processing of XML path queries using the disk-based F&B index.
In: B?hm K, Jensen CS, Haas LM, et al., eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB). Trondheim: ACM Press, 2005. 145?156.
[50] Jiang HF, Lu HJ, Wang W. Efficient processing of XML twig queries with OR-predicates. In: Weikum G, K?nig AC, De?loch S,
eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Paris: ACM Press, 2004. 59?70.
[51] Chen T, Lu JH, Ling TW. On boosting holism in XML twig pattern matching using structural indexing techniques. In: Ozcan F, ed.
Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Baltimore: ACM Press, 2005. 455?466.
[52] Shasha D, Zhang K. Approximate tree pattern matching. In: Apostolico A, Galil Z, ed. In: Proc. of the Pattern Matching Algorithms.
Oxford University, 1997.
[53] Bille P. A survey on tree edit distance and related problems. Theoretical Computer Science, 2005,337(1-3):217?239.
[54] Joshi S, Agrawal N, Krishnapuram R, Negi S. A bag of paths model for measuring structural similarity in Web documents. In:
Getoor L, Senator TE, Domingos P, et al., eds. Proc. of the 9th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (SIGKDD). Washington: ACM Press, 2003. 577?582.
[55] Amer-Yahia S, Koudas N, Marian A, Srivastava D, Toman D. Structure and content scoring for XML. In: B?hm K, Jensen CS,
Haas LM, Kersten ML, Larson P, Ooi BC, eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB). Trondheim: ACM Press, 2005. 361?372.
[56] Arvola P, Junkkari M, Kek?l?inen J. Generalized contextualization method for XML information retrieval. In: Herzog O, Schek H,
Fuhr N, et al., eds. Proc. of the 2005 ACM CIKM Int’l Conf. on Information and Knowledge Management (CIKM). Bremen: ACM Press, 2005. 20?27.
[57] Wolff JE, Fl?rke H, Cremers AB. Searching and browsing collections of structural information. In: Proc. of the IEEE Advances in
Digital Libraries (ADL 2000). Washington: ACM Press, 2000. 141?150.
[58] Guha S, Jagadish HV, Koudas N, Srivastava D, Yu T. Approximate XML joins. In: Franklin MJ, Moon B, Ailamaki A, eds. Proc.
of the 2002 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Madison: ACM Press, 2002. 287?298.
[59] Yang R, Kalnis P, Tung AK. Similarity evaluation on tree-structured data. In: Ozcan F, ed. Proc. of the ACM SIGMOD Int’l Conf.
on Management of Data (SIGMOD). Baltimore: ACM Press, 2005. 754?765.
[60] Augsten N, B?hlen MH, Gamper J. Approximate matching of hierarchical data using pq-grams. In: B?hm K, Jensen CS, Haas LM,
Kersten ML, Larson P, Ooi BC, eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB). Trondheim: ACM Press, 2005.
301?312.
[61] Schlieder T, Meuss H. Querying and ranking XML documents. Journal of the American Society for Information Science and
Technology, 2002,53(6):489?503.
[62] Kailing K, Kriegel H, Sch?nauer S, Seidl T. Efficient similarity search for hierarchical data in large databases. In: Bertino E,
Christodoulakis S, Plexousakis D, et al., eds. Advances in Database Technology-EDBT 2004, Proc. of the 9th Int’l Conf. on Extending Database Technology (EDBT). Greece: Springer-Verlag, 2004. 676?693.
[63] Kotsakis E. Structured information retrieval in XML documents. In: Proc. of the 2002 ACM Symp. on Applied Computing (SAC).
Madrid: ACM Press, 2002. 663?667.
[64] Wan CX, Liu YS. Efficient supporting XML query and keyword search in relational database systems. In: Meng XF, Su JW, Wang
YJ, eds. Advances in Web-Age Information Management, Proc. of the 3rd Int’l Conf. (WAIM). LNCS 2419, Beijing: Springer-Verlag, 2002. 1?12.
[65] Hristidis V, Papakonstantinou Y, Balmin A. Keyword proximity search on XML graphs. In: Dayal U, Ramamritham K,
Vijayaraman TM, eds. Proc. of the 19th Int’l Conf. on Data Engineering (ICDE). Bangalore: IEEE Computer Society, 2003.
367?378.
[66] Ré C, Siméon J, Fernández MF. A complete and efficient algebraic compiler for XQuery. In: Liu L, Reuter A, Whang KY, et al.,
eds. Proc. of the 22nd Int’l Conf. on Data Engineering (ICDE). Atlanta: IEEE Computer Society, 2006. 14.
[67] Zhang SH, Dyreson C. Symmetrically exploiting XML. In: Carr L, Roure DD, IyengarA, et al., eds. Proc. of the 15th Int’l Conf. on
World Wide Web (WWW). Edinburgh: ACM Press, 2006. 103?111.
1418 Journal of Software软件学报 V ol.18, No.6, June 2007
[68] Amer-Yahia S, Curtmola E, Deutsch A. Flexible and efficient XML search with complex full-text predicates. In: Proc. of the ACM
SIGMOD Int’l Conf. on Management of Data (SIGMOD). Chicago: ACM Press, 2006. 575?586.
附中文参考文献:
[1] 孟小峰,周龙骥,王珊.数据库技术发展趋.软件学报,2004,15(12):1822?1836. https://www.doczj.com/doc/fb1171485.html,/1000-9825/15/1822.htm
[2] 孔令波,唐世渭,杨冬青,王腾蛟,高军.XML数据索引技术.软件学报,2005,16(12):2063?2079. https://www.doczj.com/doc/fb1171485.html,/1000-9825/16/
2063.htm
[18] 孟小峰,王宇,王小锋.XML查询优化研究.软件学报,2006,17(10):2069?2086. https://www.doczj.com/doc/fb1171485.html,/1000-9825/17/2069.htm
[44] 王静,孟小峰,王珊.基于区域划分的XML结构连接.软件学报,2004,15(5):720?729. https://www.doczj.com/doc/fb1171485.html,/1000-9825/15/720.htm
[45] 万常选,刘云生,徐升华,刘喜平,林大海.基于区间编码的XML索引结构的有效结构连接.计算机学报,2005,28(1):113?127.
https://www.doczj.com/doc/fb1171485.html,/qwjs/view.asp?id=1746
[46] 王静,孟小峰,王宇,王珊.以目标节点为导向的XML路径查询处理.软件学报,2005,16(5):827?837. https://www.doczj.com/doc/fb1171485.html,/1000-
9825/16/827.htm
孔令波(1974－),男,博士生,山东日照人,主要研究领域为关系数据库实现技术, XML数据处理技术,数据挖掘.
王腾蛟(1973－),男,博士,副教授,CCF高级会员,主要研究领域为数据库,数据仓库,Web数据集成,数据挖掘
.
唐世渭(1939－),男,教授,博士生导师,CCF
高级会员,主要研究领域为数据库,半结构
化数据,Web数据集成,数据挖掘.
高军(1975－),男,博士,副教授,CCF高级
会员,主要研究领域为数据库,数据仓库,
半结构化数据,Web数据集成,移动数据
挖掘.
杨冬青(1945－),女,教授,博士生导师,CCF
高级会员,主要研究领域为数据库,数据仓
库,Web数据集成,移动数据挖掘.
分布式数据库的索引技术研究 摘要:索引是分布式数据库中的一个重要对象。通过对分布式数据库中的索引管理技术的分析,论述了分布式数据库中索引的概念、特点、分类及使用原则等。分析了分布式数据库设计中的统一索引服务。在文章的最后部分给出了创建合理索引的一些建议。 关键词:分布式数据库索引检索 1索引的概念 索引是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标志这些值的数据页的逻辑指针清单。表的存储由两部分组成,一部分用来存放数据页面,另一部分存放索引页面。 2索引的创建 2.1 索引的创建 创建索引有多种方法,这些方法包括直接创建索引的方法和间接创建索引的方法。直接创建索引,例如使用CREATE INDEX语句或者使用创建索引向导,间接创建索引,例如在表中定义主键约束或者唯一性键约束时,同时也创建了索引。虽然,这两种方法都可以创建索引,但是,它们创建索引的具体内容是有区别的。 使用CREATE INDEX语句或者使用创建索引向导来创建索引,这是最基本的索引创建方式,并且可以定制创建出符合自己需要的索引。在使用这种方式创建索引时,可以使用许多选项,例如指定数据页的充满度、进行排序、整理统计信息等,这样可以优化索引。使用这种方法,可以指定索引的类型、唯一性和复合性,也就是说,既可以创建聚簇索引,也可以创建非聚簇索引,既可以在一个列上创建索引,也可以在两个或者两个以上的列上创建索引。 通过定义主键约束或者唯一性键约束,也可以间接创建索引。主键约束是一种保持数据完整性的逻辑,它限制表中的记录有相同的主键记录。在创建主键约束时,系统自动创建了一个唯一性的聚簇索引。虽然,在逻辑上,主键约束是一种重要的结构,但是,在物理结构上与主键约束相对应的结构是唯一性的聚簇索引。换句话说,在物理实现上,不存在主键约束,而只存在唯一性的聚簇索引。同样,在创建唯一性键约束时,也同时创建了索引,这种索引则是唯一性的非聚簇索引。因此当使用约束创建索引时,索引的类型和特征基本上都已经确定了,由用户定制的余地比较小。 3分布式数据库设计中的统一索引服务
龙源期刊网 https://www.doczj.com/doc/fb1171485.html, XML与SQL数据库 作者：刘立平 来源：《数字技术与应用》2015年第07期 摘要：XML的核心是描述数据的组织结构，它可以作为数据交换的标准格式。SQL数据库在数据查询、修改、保存、安全等方面具有其他数据处理手段无法替代的地位。一个系统获得一个XML文件后，可能需要将XML中的某些标记包含的文本内容转化为数据库中表的一条记录；另一方面，一个应用系统可能需要将数据库表中的某些记录转化为一个XML文件，以便与其他系统交互数据，发挥XML文件在数据交换上的优势。 关键词：XML SQL数据库数据交换 中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2015）07-0000-00 1 XML XML（eXtensible Markup Language）是可扩展标记语言，XML是由万维网联盟定义的一种语言，是表示结构化数据的行业标准。它使得Internet上的数据相互交流更加方便，让文件的内容更加显而易懂。XML不仅提供了直接在数据上工作的通用方法，还可以将用户界面和结构化数据相分离，允许不同来源的数据的无缝集成和对同一数据的多种处理。XML包括一系列相关技术，其中主要内容有：规范的XML、有效的XML文件、XML与CSS、XML与XSL、基于DOM的解析器、XML Schema模式、XML与数据库等等知识。 2数据库 数据库（DataBase，简称DB）是存放数据的仓库，是为了满足某一部门中多个用户的多种应用的需要，安装一定的数据模型在计算机中组织、存储和使用的相互联系的数据集合。数据库系统就是管理大量的、持久的、可靠的和共享的数据的工具。 数据库管理系统软件的种类有很多，但常用的也就那么三五种：ORACLE、My SQL、ACCESS、MS SQL Server这些是不同领域常用的数据库管理系统软件。其中ORACLE和MS SQL Server最为常见，这里以MS SQL Server为例， SQL server数据库是美国微软公司发布的一款RMDBS数据库，也就是关系型数据库系统。SQL server的优点为： （1）真正的客户服务器体系结构。 （2）图形化用户界面，更加直观、简单。 （3）丰富的编程接口工具，为用户进行程序设计提供更多选择余地。
3D GIS空间索引技术 3DGIS是新一代GIS技术的重要分支，是进行全方位、多层次、多要素时空分析的基础，开发结构简单、功能完善的真3DGIS软件是当前GIS研究人员的重要目标。3DGIS需要管理大量的三维空间对象，且常常需要根据空间位置对这些对象进行查询、检索和显示操作。为了处理这类空间操作，传统的关系数据库搜索方法需要花费大量的磁盘访问时间和空间运算时间。为了提高检索效率，传统的关系数据库一般都建立一系列的索引机制，如B+树等。目前常用的索引机制多是一维索引，无法有效处理3DGIS空间数据库中的三维空间地理实体。因此，必须为3DGIS空间数据库建立专门的索引机制——空间索引。 空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按照一定规律排列的数据结构，它介于空间操作算法和空间对象之间，筛选、排除与特定的空间操作无关的空间对象。空间索引机制是快速、高效地查询、检索和显示地理空间数据的基础，其性能优劣直接影响GIS空间数据库的性能，关系到3DGIS软件系统的整体运行状况。 一、三维空间索引简介 3DGIS是2DGIS在三维空间内的延展，是布满整个三维空间内的GIS，它与2DGIS的差异主要体现在空间位置的确定、空间拓扑关系的描述与空间分析的延展方向上。3DGIS将三维空间坐标（x，y，z）作为独立的参数来构建空间实体对象模型，能够实现空间实体的真三维可视化，以立体造型来展现空间地理现象，它不仅能够表达空间实体之间的平面关系，还能够表达其垂向关系，在此基础上进行复杂的三维空间分析与操作。 在GIS由二维扩充到三维后，其处理的空间对象也由二维空间中的“点、线、面”扩充到三维空间中的“点、线、面、体”。2DGIS对平面空间的“有限-互斥-完整”剖分是基于面的划分，而3DGIS对三维空间的“有限-互斥-完整”剖分则是基于体的划分。在3DGIS 空间数据库中，空间实体的表达形式复杂，各种空间操作不仅计算量大，而且多具有面向邻域的特点。因此，在3DGIS中，由于空间维数的增加和空间实体关系复杂度的提高而导致三维空间数据的海量性。海量数据的存储与管理需要更加高效的空间数据结构和空间索引机制。目前成熟的空间索引算法多集中在二维空间索引上，如网格索引、四叉树索引等，而对3DGIS的空间索引问题研究较少。对低维空间数据而言，二维空间索引的索引效率较高，并且多数可以进行扩展以支持高维数据集。但应用实践显示，仅仅简单地将二维空间索引维数增加到三维，其效率并不高，且很多索引结构都是针对特定空间查询操作而设计的，不具有通用性。因此，需要研究3DGIS所使用的空间索引技术。 设计3DGIS空间索引面临的主要困难是：三维空间实体的空间关系比较复杂，有时甚至呈一种相对无序的状态。从本质上看，3DGIS对空间索引的要求与2DGIS基本类似，但在数据采集、数据库维护、数据操作、界面设计等方面要比2DGIS复杂得多。目前的三维空间索引大多是从二维空间索引的基础上发展而来的。与二维空间索引相似，三维空间索引方法也是基于空间数据的层次化聚类原则，结构上类似于早期用于数据检索的B+树：数据矢量存储在数据节点，空间位置邻近的矢量尽可能存储于同一节点。数据节点之间以层次化目录结构来组织，每一个目录节点都指向下一级的一个子树。 目前，索引结构大都采用平衡树的概念，即从根节点到所有数据节点的访问长度（索引高度）相同（但在插入和删除操作后可能会有改变），在树的形状上表现为高度一致性。从任意节点到数据节点的访问长度称为节点的级，数据节点对应第0级。 二、空间索引结构分类 根据空间索引结构的演化过程，空间索引方法可分为4大类，即基于二叉树的索引技术、基于B树的索引技术、基于Hashing的格网技术和空间目标排序法。
XML与关系数据库 前面我们讲到了XML的数据存取机制，从一个较高的层面上分析了数据存取的多种方式。作为其中的一种，数据库的数据存取机制似乎倍受青睐，但我们并未对此作比较深入的探讨，这一节里我们对XML与数据库的关系进行更进一步的详细分析。 我们知道，关系数据库提供了对于大批量数据的有效存储管理和快速信息检索、查询的功能。从体系结构上看，数据库技术的发展历经了网络型数据库、层次型数据库、关系数据库、面向对象数据库。虽然面向对象数据库融入了面向对象技术，但是到目前为止，在各个领域使用最广的还是关系数据库。关系数据库管理系统（RDBMS）采用二维表格作为存储数据的模型，如下图10-1所示， 字段字段字段 行 行 行 行 图10-1 关系数据库二维表 表格由行和列组成，一般情况下，列被称作“字段”，用于表示组成数据有效信息的属性，而行则用于指示一条完整的数据记录。由于数据间的相关性可以通过表与表之间关键字（外键）来关联，由此产生了“关系”类型数据库的由来。 关系数据库有自己的查询语言——结构化查询语言（Structured Query Languag e，SQL）。SQL最初由IBM提出，后经不断发展，已于1986年成为业界标准并被广泛采用。SQL 是非过程性的。当SQL语句传送到数据库服务器后，服务器返回满足条件的结果或结果集（视具体查询项目而定）。一般情况下，大多数支持SQL 的服务器系统均采用客户/服务器架构，现在又发展到更为先进的分布式处理架构。这样一来，SQL服务器既可以接收客户应用程序发送的查询请求，也可以接收其他服务器的查询请求，这些服务器可能是其他SQL服务器，也可以是XML服务器。 就数据存储而言，关系型数据库已经是相当成熟的应用，从80年代商用产品出现至今，早已深入企业储存及数据应用的核心。相较之下，XML部分技术尚且在发展阶段。关系型数据库是透过详细定义和控制结构化数据的方式，达到数据增、删、查询的目的。因此它是以字段数据型态的精确定义，将数据以列的方式一笔笔储存，再透过数据表之间的互相关联，建构出数据和数据结合后的复杂结果，因此
Geomatics Square NO.6 2011 (Total 113) 科技交流 基于空间数据库的几种常用空间索引技术研究 白航 （广东省国土资源测绘院，广州510500） 摘要:空间数据库是地理信息系统(GIS)的基础和核心，空间索引技术通过对存储介质上数据位置信息的描述来提高数据查询、检索及获取效率；其好坏直接影响空间数据库系统的可用性和可扩展性。本文介绍了几种常见的空间数据库索引技术：简单格网空间索引、K-D 树空间索引、R 树空间索引、四叉树空间索引等；系统总结了空间数据库索引技术的研究进展，探讨了其发展前景和存在问题。 关键词:空间数据库；空间索引；GIS 1.引言 空间数据库技术是随着GIS (地理信息系统)的发展而兴起的一门新技术，复杂的地理环境和海量、多维、结构复杂的空间数据导致了基于空间数据库查询、检索及空间计算的开销一般要比关系数据库大的多，特别是查询语句中条件谓词包含一些对空间数据操作或连接的一些函数，这些函数的计算开销远比数值计算或字符串比较等要大。若使用传统的关系型数据库管理系统(DBMS)来管理空间数据，其存在固有缺陷，用顺序扫描的方法查询的效率非常低。因此为了提高查询效率，采用空间索引技术十分必要。 2.空间数据库索引技术 空间数据用来表示空间物体的位置、形状、大小和分布特征等方面信息，适用于描述二维、三维或多维分布的区域现象。空间数据库是计算机物理存储介质上存储的地理空间数据的总和。数据库的索引机制可以用来快速访问某条特定查询所请求的数据，而无需遍历整个数据库。传统的关系数据库为了提高检索效率，一般都会建立一系列的索引机制，如B 树等，但这些都是一维索引，无法处理空间数据库中的二维和多维的 空间数据。 空间数据库索引技术是通过对存储在介质上的数据位置信息的描述，来提高空间数据库的查询性能和数据获取效率，索引技术的好坏直接影响到空间数据库系统的成败。空间数据索引作为一种辅助性的空间数据结构，介于空间操作算法和地理对象之间，通过筛选、排除大量与特定空间操作无关的地理对象，缩小了空间数据的操作范围，从而提高空间操作的速度和效率。 3.几种常见的空间索引技术 3.1简单格网空间索引 格网空间索引的原理简单，即把目标空间实体集合所在的空间范围划分成一系列大小相同的格。如图3-1所示，每一个格相当于一个桶（bucket ），记录落入该格内的空间实体的编号。基于格网索引的查找思路也较简单，在数据分布较均匀的情况下，查询效率较高。但格网的大小直接影响了索引表的大小，格网太小，索引表会急剧膨胀，维护索引表本身的花费增加，查询效率随之下降；反之，落在一个格内的空间实体可能会过多；因此格的大小严重制约着查询效率的提高。 8
1.1．索引作用 2.在索引列上，除了上面提到的有序查找之外，数据库利用各种各样的 快速定位技术，能够大大提高查询效率。特别是当数据量非常大，查询涉及多个表时，使用索引往往能使查询速度加快成千上万倍。 3. 4.例如，有3个未索引的表t1、t2、t3，分别只包含列c1、c2、c3，每 个表分别含有1000行数据组成，指为1～1000的数值，查找对应值相等行的查询如下所示。 5. 6.SELECT c1,c2,c3 FROM t1,t2,t3 WHERE c1=c2 AND c1=c3 7. 8.此查询结果应该为1000行，每行包含3个相等的值。在无索引的情况 下处理此查询，必须寻找3个表所有的组合，以便得出与WHERE子句相配的那些行。而可能的组合数目为1000×1000×1000（十亿），显然查询将会非常慢。 9. 10. 如果对每个表进行索引，就能极大地加速查询进程。利用索引的查询 处理如下。 11. 12.（1）从表t1中选择第一行，查看此行所包含的数据。 13. 14.（2）使用表t2上的索引，直接定位t2中与t1的值匹配的行。类似，利 用表t3上的索引，直接定位t3中与来自t1的值匹配的行。 15. 16.（3）扫描表t1的下一行并重复前面的过程，直到遍历t1中所有的行。 17. 18. 在此情形下，仍然对表t1执行了一个完全扫描，但能够在表t2和t3 上进行索引查找直接取出这些表中的行，比未用索引时要快一百万倍。 19. 20. 利用索引，MySQL加速了WHERE子句满足条件行的搜索，而在多表连 接查询时，在执行连接时加快了与其他表中的行匹配的速度。 21. 22.2. 创建索引 23.在执行CREATE TABLE语句时可以创建索引，也可以单独用CREATE INDEX 或ALTER TABLE来为表增加索引。 24. 25.1．ALTER TABLE 26.ALTER TABLE用来创建普通索引、UNIQUE索引或PRIMARY KEY索引。 27. 28. 29. 30.ALTER TABLE table_name ADD INDEX index_name (column_list) 31. 32.ALTER TABLE table_name ADD UNIQUE (column_list)
常见数据库加密技术对比 作者：安华金和孙峥 数据库加密作为近年来兴起的数据库安防技术，已经被越来越多的人所重视。这种基于存储层加密的防护方式，不仅可以有效解决数据库明文存储引起的泄密风险，也可以防止来自内部或者外部的入侵及越权访问行为。 从技术手段上来看，现今数据库加密技术主要有三大类，分别是前置代理及加密网关方式、应用层加密方式以及后置代理方式。这三类技术各自的特点如何，彼此之间孰优孰劣，下文详尽介绍。 一. 前置代理及加密网关数据库加密技术 该数据库加密技术思路是在数据库之前增加一道安全代理服务，对数据库访问的用户必须经过该安全代理服务，在此服务中实现如数据加解密、存取控制等安全策略；然后安全代理服务通过数据库的访问接口实现数据在库中的加密存储。安全代理服务存在于客户端应用与数据库存储引擎之间，负责完成库中数据的加解密工作，加密数据存储在安全代理服务中。 这种数据库加密技术也会存在一些问题和限制： 1）由于在安全增强代理中需要存储加密数据，因此要解决与数据库存储数据的一致性问题，这基本不可实现。 2）数据的联合检索问题：由于在数据库内外都存在数据，这些数据的联合检索将变得很困难；SQL语法的完全兼容也非常困难。 3）开发无法透明问题：数据库协议虽然存在标准，但事实上每个不同的数据库版本都会进行若干变更、扩展和增强，使用了这些特性的用户必须进行改造。同时在安全代理中对数据库通讯协议的模拟非常困难。 4)数据库的优化处理、事务处理、并发处理等特性都无法使用：查询分析、优化处理、事务处理、并发处理工作都需要在安全增强器中完成，无法使用数据库在并发处理和查询优化上的优势，系统的性能和稳定性更多地依赖于安全代理； 5) 此种数据库加密技术对于对存储过程、触发器、函数等存储程序的实现支持也非常困难。
《空间数据组织与分析》 结课论文 题目：多级空间索引算法分析 学院：研究生学院 专业：大地测量学与测量工程 班级：硕研12级3班 姓名：张鼎凯 学号：2012020344 日期：2012年12月05日
摘要：空间数据库的索引是提高空间数据库存储效率和空间检索性能的关键技术。介绍了空间数据库中建立索引的常用技术，给出了一种多级空间索引，详细讨论了该索引的建立算法以及应用该索引的检索算法，并进行了算法分析。 关键词：计算机软件；间数据库；空间索引；空间检索；算法分析 1 空间索引技术简介 空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间数据一般是是多维的，在此主要介绍二维空间数据的索引。近年来，国外学者提出应用空间基数分区对空间数据进行管理，已得出了几种空间数据索引结构。例如Robinson提出的K-D-B 树[2]，Guttman 提出R 树结构[3]，Freeston 提出的BANG 文件[4]，Beckmann 提出的R*树结构[5]等。国内则学者提出了QR-树[6]，网格索引[7][8]等索引结构，并进行了有关索引结构的性能分析和查询优化研究[8][9]。众多的索引结构可以说各有优缺点。总的来说，可分为以四叉树为代表的网格文件结构和以R 树及其变种为代表的动态索引技术。 1.1四叉树结构 四叉树索引是栅格文件索引技术的代表。栅格文件索引技术的基本思想是将一张地图规则地划分成多个互不相交的栅格，且要求所有栅格覆盖全地图，然后再利用栅格对地图上的空间对象进行索引。如K-D树、K-D-B 树、四叉树、八叉树等均基于此思想。我们在此主要介绍一下四叉树空间索引技术。四叉树空间索引是将一张地图逐步四等分，且依次编号，如图1（a）所示，其层次由用户依需要而定。划分的结果可生成如图1（b）的四叉树结构。从此结构中可确定被索引类中每个对象实例的被索引属性值属于那一个最小范围块，并将其ID 加到该最小范围块所带的链表中。查询时根据用户关心的区域，选中区域所在最小范围块中的对象。四叉树的查询在最坏情况下效率较低，而且四叉树的动态性较差。建立索引后，如果又扩大地图范围增加新对象时，必须重新建立四叉树索引，因而缺乏灵活性。
一、引言 对数据库索引的关注从未淡出我的们的讨论，那么数据库索引是什么样的？聚集索引与非聚集索引有什么不同？希望本文对各位同仁有一定的帮助。有不少存疑的地方，诚心希望各位不吝赐教指正，共同进步。[最近首页之争沸沸扬扬，也不知道这个放在这合适么，苦劳？功劳？……] 二、B-Tree 我们常见的数据库系统，其索引使用的数据结构多是B-Tree或者B+Tree。例如，MsSql使用的是B+Tree，Oracle及Sysbase使用的是B-Tree。所以在最开始，简单地介绍一下B-Tree。 B-Tree不同于Binary Tree（二叉树，最多有两个子树），一棵M阶的B-Tree满足以下条件：1）每个结点至多有M个孩子； 2）除根结点和叶结点外，其它每个结点至少有M/2个孩子； 3）根结点至少有两个孩子（除非该树仅包含一个结点）； 4）所有叶结点在同一层，叶结点不包含任何关键字信息； 5）有K个关键字的非叶结点恰好包含K+1个孩子； 另外，对于一个结点，其内部的关键字是从小到大排序的。以下是B-Tree（M=4）的样例： 对于每个结点，主要包含一个关键字数组Key[]，一个指针数组（指向儿子）Son[]。在B-Tree 内，查找的流程是：使用顺序查找（数组长度较短时）或折半查找方法查找Key[]数组，若找到关键字K，则返回该结点的地址及K在Key[]中的位置；否则，可确定K在某个Key[i]和Key[i+1]之间，则从Son[i]所指的子结点继续查找，直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。 接着，我们使用以下图片演示如何生成B-Tree（M=4，依次插入1~6）： 从图可见，当我们插入关键字4时，由于原结点已经满了，故进行分裂，基本按一半的原则进行分裂，然后取出中间的关键字2，升级（这里是成为根结点）。其它的依类推，就是这样一个大概的过程。
实验三：XML 与数据库的数据转换 1实验学时 2 学时 2实验目的 理解 XML 与数据库之间的转换方式 在项目实践中综合各种知识的运用 3实验内容 采用 Eclipse IDE(或 MyEclipse) 建立一个 Java 项目 利用 MySQL 及其图形界面工具建立一个数据库 利用 JDBC 建立其和数据库的连接 编写 XML 文件和处理类以完成 XML 文件和数据库之间的 数据转换 4实验代码 import javax.xml.transform.*; import javax.xml.transform.stream.*; import javax.xml.transform.dom.*; import org.w3c.dom.*; import javax.xml.parsers.*; import java.io.*; import java.sql.*; public class DatabaseToXML { // MySQL的JDBC连接jar包位置是D:\mysql-connector-java-5.1.19-bin.jar // 数据库名称为：xmllab // 表名是：person，表中的字段及属性请查阅ppt文档 // 用户名是：root // 密码是：root public static void main(String args[]) { Connection con; Statement sql; ResultSet rs; // 为ppt文档中的图示中的表增加一个字段id，用于MySQL自增量计算 Integer[] id = {}; String[] number = { "" }; String[] name = { "" }; String[] date = { "" }; String[] salary = { "" }; try { Class.forName("com.mysql.jdbc.Driver"); } catch (ClassNotFoundException e) {
摘要： 随着XML数据的日益增多，XML已经成为了互联网上数据表示和数据交换的标准格式。同时也涌现出大量的XML数据存储方法，比较有代表性的有XML专用数据库存储、面向对象数据库存储、关系数据库存储等。由于关系数据库的大力发展、广泛应用和其成熟的技术，在存储管理XML的各种可能的方式中，基于关系数据库的XML数据存储成为一种可行而有前景的方式，受到了广泛的关注。 由于关系数据库的二维平面关系表结构与XML的层次结构有很大差异，怎样在关系数据库中有效地存储XML文档，同时又能保持其结构信息和文档信息成为一个难题。为了解决这一难题，使得XML模式与关系模式之间的映射问题，成为XML 文档的关系化存储技术的核心问题。 本文主要探讨了XML与数据库映射的方法。
目录 第一章前言 (1) 第二章XML技术 (3) .2.1XML的特点 (3) .2.2XML的应用分析 (4) 2.3.1DTD (5) 2.3.2XML Schema (6) 2.4XML解析技术 (7) 2.4.1 SAX (8) 2.4.2．DOM (8) 2.4.3．DOM与SAX比较 (9) 第三章XML与数据库技术 (10) 3.1 XML是数据库吗？ (10) 3.2 数据和文档的对比 (10) 3.2.1 以数据为中心的文件 (11) 3.2.2 以文档为中心的文件 (11) 3.2.3 数据、文档和数据库 (11) 第四章XML与关系数据库的转换 (13) 4.1边模型映射法 (13) 4.2结点模型映射法 (16) 第五章结束语 (19) 第六章致谢 (20)
第一章前言 近年来，互联网得到了迅猛发展，它提供了全球范围的网络互联与通信功能，其丰富的信息资源给人们的学习和生活带来了极大的便利。作为互联网最主要应用的Web实际上已成为最大的信息资源库。电子商务、电子出版、远程教育等基于Web 的新兴领域的全面兴起使得传统的Web资源更加复杂化和多样化。人们对Web服务功能的需求也达到更高的标准，如用户需要对Web进行智能化的语义搜索和对数据按照不同的需求进行多样化显示等个性化服务；公司和企业要为客户创建和分发大量有价值的文档信息，以及对不同平台、不同格式的数据源进行有效的数据交换和集成等等。在这种大环境下，以简单易学、灵活通用著称的HTML，随着网络应用的日益广泛，局限性逐渐明显，越来越不能适应作为Intemet上信息交换和表示的工具了。 XML(eXtensible Markup Language)作为SGML(Standard Generalized MarkupLanguage)的一个优化子集，它不像HTML那样事先定义好一组标签，而是提供了一个标准，只要遵循这个标准，你可以灵活的定义自己的标记。XML不仅能够存储数据，而且能够存储结构和语义信息，具有通用的数据表示能力，能表示结构化、半结构化及元结构化数据，可以描述不同种类应用软件中的数据，这使其在数据交互和信息共享方面拥有天然的优势，成为Web上数据表示与交换的通用标准。 XML与HTML相比主要有以下几点优势： (1)XML简单，具有自我描述能力。通过语义标记来说明数据的语义，容易理解且易于解析。这使得XML具有机器可读性，具体应用可以按照各种方式解析、过滤及重构XML文档。 (2)XML具有灵活性。HTML的标记是预定义的，具有固定的名称及语义，不能扩展，而XML的标记可由用户定义，可以被任意的扩展。XML的嵌套结构可以表示各种复杂的数据结构，各种格式的数据都可以较容易的转换为XML数据，这使得XML非常适合于Web信息的发布和集成。 (3)XML具有平台独立性。XML可用于不同类型、系统间的交换格式的传送，从而简化了从一个应用程序到另一个应用程序之间传递信息的工作。 (4)XML实现了结构、内容和显示相分离。文档类型定义(DTD)或XML模式(XMLschema)描述了XML文档的结构，即元素间的嵌套关系。XML文档实例只描述数据，使得数据具有独立性，而XML文档的显示具有多样性，XML文档的显示是由XML文档配合XSL(eXtensible Style Language)来完成的，对同一个XML文档可以
实验报告封面 课程名称： XML企业应用开发课程代码： SN3005 任课老师：江立实验指导老师: 江立 实验报告名称：作业二 学生姓名：马增群 学号： 1340112124 教学班： GX01 递交日期： 2015年12月15日 签收人： 我申明，本报告内的实验已按要求完成，报告完全是由我个人完成，并没有抄袭行为。我已经保留了这份实验报告的副本。 申明人(签名):马增群实验报告评语与评分： 评阅老师签名：
一、实验名称：xml与数据库中数据的导入导出 二、实验日期：2015年12月15日 三、实验目的： 四、实验用的软件： XMLSpy2013 五、实验的步骤和方法： 实验前准备: 新建一个Java工程，工程名称为xmlDemo,文件目录如图所示：
src frame包：存放java的界面类。IndexFrame是索引界面类，ImportFrame是导入界面类，ExportFrame是导出界面类； service包：存放java的Service类。DBService是实现数据库操作的Service类，DBToXmlService是实现从数据库导出xml文件的Service类，XmlToDBService是实现从xml文件导入数据库的Service类； utils包：存放java的工具类。DBConnectionUtil是数据库连接的工具类； libs dom4j-1.6.1.jar：实现XML读取相关操作的价包； mysql-connector-5.1.8.jar：实现连接MySql数据库的价包； (1)数据库设计
实现了xml文件导出、xml文件导入功能。点击文件菜单可以看到两个选项
2010年2月第2期 电子测试 ELECTRONIC TEST Feb.2010 No.2 数据库索引研究 于绍娜1，李霞丽1，胥桂仙1，杨智君2 (1. 中央民族大学，北京 100081；2. 中国计量科学研究院，北京 100013) 摘要：在数据库系统应用中，要进行频繁的数据查询操作。索引是与表或视图关联的磁盘上结构，有效的使用索引，可以快速找到表或视图中特定信息，减少系统的响应时间。本文介绍了索引的概念、分类、使用和维护，并就MS SQL SERVER索引进行了一些分析和实践。 关键词：聚集索引；非聚集索引；筛选索引；B树 中图分类号：TP311 文献标识码：A Study on database index Yu Shaona1, Li Xiali1, Xu Guixian1, Yang Zhijun2 (1. Minzu University of China, Beijing 100081;2. National Institute of Metrology P.R.China, Beijing 100013) Abstract: In the application of database system, data query is done frequently. Index is a disk structure associating with table or view. Using index in database effectively, it’s good for finding information fast in the table or view and reducing system’s answering time. In this paper, we introduce classify, using and maintenance of index. In addition, we analysis and practice the index in MS SQL SERVER. Keywords: clustered index；nonclustered index；Filtered Indexes；B tree 0 引言 索引中保存着表或视图中排序的索引列，并且纪录了索引列在数据库表中的物理存储位置。通过索引查询，可以减少为返回查询结果集而必须读取的数据量。索引还可以强制表中的行具有唯一性，从而确保表数据的数据完整性。创建设计良好的索引以支持查询，可以显著提高数据库查询和应用程序的性能。但是，索引并不总是提高系统的性能，表中建有大量索引会影响增、删、改语句的性能，因为当表中的数据更改时，所有索引都须进行适当的调整。因此，合理的设计索引对于提高数据库的性能具有重要意义。 1 索引的概念 索引包含由表或视图中的一列或多列生成的键。键存储在一个B树结构中，使SQL Server可以快速有效地查找与键值关联的行。 MS SQL SERVER中数据存储的基本单位是页(Page)，磁盘I/O操作在页级执行。SQL Server 数据页和索引页都是8K字节大。这意味着与8KB数据页相比，索引页可以有效地将与更多行相关的信息压缩到一个8KB页。当SQL查询要求某个表中