1000-9825/2005/16(12)2063
?2005 Journal of Software 软 件 学 报
Vol.16, No.12
XML 数据索引技术
1 2
?
孔令波 1+, 唐世渭 1,2, 杨冬青 1, 王腾蛟 1, 高 军 1
(北京大学 计算机科学技术系,北京 100871) 100871) (北京大学 视觉与听觉信息处理国家重点实验室,北京
XML Indices
KONG Ling-Bo1+,
1 2
TANG Shi-Wei1,2,
YANG Dong-Qing1,
WANG Teng-Jiao1,
GAO Jun1
(Department of Computer Science and Technology, Peking University, Beijing 100871, China) (National Laboratory on Machine Perception, Peking University, Beijing 100871, China)
+ Corresponding author: Phn: +86-10-62755440, E-mail: lbkong@https://www.doczj.com/doc/7c2720695.html,, https://www.doczj.com/doc/7c2720695.html,
Received 2004-12-07; Accepted 2005-08-24 Kong LB, Tang SW, Yang DQ, Wang TJ, Gao J. XML indices. Journal of Software, 2005,16(12):2063?2079. DOI: 10.1360/jos162063 Abstract: XML has become the de facto standards for data representation and exchange on Web applications,
such as digital library, Web service, and electronic business, etc. Indexing technique is still significant for efficient XML data processing. This paper discusses the actualities of the recent researches on XML indexing. It classifies the techniques into two categories, node-record-style index with three subcategories, and structural-summary-style index. It analyzes the virtue and deficiency of the related schemes based on the considerations for query processing efficiency and data modification supporting. And hereby it proposes three issues for future XML indexing researches, including internal structure retrieval, multi-dimensional processing on node paths, efficient modification-validating support and the index amalgamation for satisfying both querying and IR on XML data. Key words: XML index; interval encoding; B-E-L model; node numbering; bisimilarity; k-bisimilarity; structural summary; update XML; incremental validation; XML information retrieval 摘 要: 对 XML 数据建立有效的索引,是左右 XML 数据处理性能的重要因素.深入地讨论了目前 XML 索引
技术的研究现状,将 XML 索引技术分为两大类:节点记录类索引(本身还可以分为 3 个小的类型)和结构摘要类 索引.根据 XML 数据查询处理效率以及 XML 数据修改对 XML 索引的要求,讨论了相关 XML 索引方法的优点 和不足,并归结出 XML 索引后续研究的 3 个方向:XML 结构信息的获取,路径信息的多维处理,数据修改合法性 的有效支持,以及涉及能够同时有效满足 XML 查询和信息获取的索引.
? Supported by the National High-Tech Research and Development Plan of China under Grant Nos.2002AA4Z3440, 2005AA4Z3070
(国家高技术研究发展计划(863)) 作者简介: 孔令波(1974－),男,山东日照人,博士生,主要研究领域为关系数据库实现技术,XML 数据处理技术,数据挖掘; 唐世渭(1939－),男,教授,博士生导师,CCF 高级会员,主要研究领域为数据库,半结构化数据,Web 数据集成,数据挖掘;杨冬青(1945－), 女,教授,博士生导师,CCF 高级会员,主要研究领域为数据库,数据仓库,Web 数据集成,移动数据挖掘;王腾蛟(1973－),男,博士,副教 授,CCF 高级会员,主要研究领域为数据库,数据仓库,Web 数据集成,数据挖掘;高军(1975－),男,博士,副教授,主要研究领域为数据库, 数据仓库,半结构化数据,Web 数据集成,移动数据挖掘.
2064 关键词:
Journal of Software
软件学报
2005,16(12)
XML 索引;区间编码;B-E-L 模型;节点赋数;双似;k 阶双似;结构摘要;XML 数据修改;增量式验证; XML 信 息获取 文献标识码: A
中图法分类号: TP311
XML(最新的规范为 2004 年的 XML1.1)(extensible markup language),即可扩展的标记语言,是一套定义语 义标记的规范,其目标是能够定义计算机和人都能方便识别的数据类型.随着网络应用的快速发展,尤其是电子 商务、Web 服务等应用理念的进一步发展,使得 XML 类型的数据成为当前主流的数据形式.对 XML 数据的管 理也成为研究的热点[1]. XML 数据的基本形式是 XML 文档.对 XML 数据的处理分为两种不同的方式,一类是 XML 流处理,另一类 为静态数据处理方式,即传统的数据管理形式.在后一种处理方式中,类似于索引在关系数据管理系统中的地 位,XML 索引技术仍然是研究人员考虑的主要内容,也是本文关注的内容. 本文首先概述了基于静态 XML 文档数据之上的查询处理的情况,针对查询中的不足,将当前研究文献中出 现的 XML 索引分为两大类别,并简要叙述了 XML 索引设计中应该考虑的主要因素;之后对当前 XML 索引的 研究,分别从结构关系表示、结构关系的获取以及如何提供数据修改支持 3 个方面进行了阐述.最后是总结和 研究展望.本文讨论的问题只是数据库研究领域中的一部分,观点也可能存在偏颇之处,但我们希望通过本文的 工作,能给数据库研究者,尤其是正在进入相关研究领域的人员一些启发和帮助.
1
XML 索引及其分类
1.1 XML数据及XPath查询处理
??xml version=“1.0” encoding=“UTF-8”?? ?!DOCTYPE root SYSTEM “sample2.dtd”? ?root? ?a?a1 ?b?b1 ?c?c1?/c? ?/b? ?/a? ?a?a2 ?b?b2 ?c?c2?/c? ?/b? ?/a? ?a?a3 ?b?b3 ?c?c3 c4 c5 c6?/c? ?/b? ?/a? ?/root? (a) Sample.xml ??xml version=“1.0” encoding=“UTF-8”?? ?!ELEMENT root (a+)? ?!ELEMENT a (#PCDATA | b)*? ?!ELEMENT b (#PCDATA | c)*? ?!ELEMENT c (#PCDATA)? (b) Sample.dtd
XML 规范规定了 XML 数据必须满足的条件,其基本的形式 是 XML 文档.从逻辑上讲,一个 XML 文档通常由 5 部分组成:声明、 元素、注释、字符引用和处理指令,为叙述方便,统称为 XML 数据 单元.XML 数据内容的限制通常由 XML 模式(包括 DTD 和 XML Schema)来描述.图 1 为 sample.xml 文档及其 DTD 的示意.图中 root 为 sample.xml 的根,它具有 3 个标签为 a 的区段,而每一个 a 区段 都嵌套一个以 b 标签为标志的区段.当给定 XML 文档时,该文档也 就 隐 含 地确定了其中所含的标记单元的顺序,称为 XML 顺序 (XML ordering),这一概念在 XML 查询处理时是需要考虑的,即查 询结果中的标记单元应当具有类似的顺序特征. 为了从 XML 以及半结构化数据中获取所需要的信息,研究人 员 开 发 了 许 多 查 询 语 言 , 包 括 Lorel,XML-QL,XML-GL,Quilt, XPath,XQuery.它们共同的特征为:采用了正则路径表达式 [2?4]的形 式,其本质是捕捉 XML 数据单元间的结构关系和内容.XPath 是实 现 XML 数据周游的基本语言,是 XSLT,XQuery 的基础.它首先定 义了 XML 数据的树形模型.图 2 即为图 1 的满足 XPath 数模型定 义的 XML 树.图 2 中每个元素节点左侧的数字表示该节点在前序 遍历 XML 树形成的节点标签序列中的序号;右侧的数字表示该节 点在后序遍历 XML 树形成的节点标签序列中的序号.由 XPath 的 定义可以构建很复杂的查询语句,主要分为 3 个层次 [5]:线性路径 表达式、分支路径表达式和路径树.其中,路径树的定义包含了研
Fig.1 图1
sample.xml and its DTD file sample.xml 和 sample.dtd 示例
究文章中常见的小枝概念:Twig[6?10]. 当在 XML 文档类数据之上处理 XPath 查询时,借助于 W3C 定义的 XML 数据处理的两种接口规
孔令波 等:XML 数据索引技术
2065
范,DOM(document object model)和 SAX(simple API for XML),处理方式可概括为:顺序读取 XML 文档中的节 点;如果该节点的路径满足 XPath 中定义的条件(包括结构关系、测试条件和谓词关系),那么该节点即为 XPath 查询语句的一个输出.这种基本的线性表达式查询语 句的处理方式存在如下两个缺陷: (1) 只能采取周游的方式在 XML 文档中寻找满 足查询语句结构关系的数据单元,即为了获取满足查 询路径的结果,必须周游所有可能的数据单元的标签 路径,效率不高. 以图 2 为例,要想得到文本包含“c3 c4 c5 c6”的“c” 节点,那么必须从根节点开始沿着 root→a→b→c 的路 径到达.如果采取某种索引结构,可以直接定位到目标 节点,将会大大提高查询的效率. (2) 对 XML 中标签路径相同的节点,仍然需要重 新遍历它们的路径.这个问题直接来自于(1). 同样以图 2 为例,如果目标节点是 c,文档中存在 3 条相同标签路径的节点路径,而根据上述基本处理方 式,为了搜索所有的 c 节点,必须对同样的路径都要遍
c1
b1
Root Element Text String value
1
a
9 0 root
Level 0
2
4
a
5
7
8
a
Level 1
2
a1
1
b
5
a2
4
b
8
a3
7
b
Level 2
3
c
0
b2
6
c
3
b3
9
c
6
Level 3
c2
c3 c4 c5 c6
Fig.2 图2
XML tree of sample.xml sample.xml 对应的 XML 树
历.那么,将同样路径的节点汇集到同一节点中,就可以提高搜索的效率. 由此在实际研究中引申出两类 XML 索引形式:节点记录类索引和结构摘要类索引.
1.2 XML索引分类 1.2.1 节点记录类索引 本质上讲,第 1 类缺陷是由于查询处理必须通过标签路径查找节点这一限制造成的,即要想最终得到满足 查询路径的节点,必须顺序地依次访问标签路径对应的节点路径才行.那么,如果能够改变 XML 数据管理的方 式,使得可以避免必须通过路径找节点的限制,进而变为在某种辅助信息的帮助下,直接针对节点集合的划分得 到最后结果的方式,这就形成了节点记录类 XML 索引的基本思想. 类似于树结构的保存,基于实际的处理要求,将 XML 数据单元(标签名称、属性名称、属性的值、文本,甚 至是文本中的字符串等)作为记录保存;同时在数据单元的记录中保存有助于确定节点间结构关系的位置信息, 模式为(数据单元标识,数据单元在 XML 中的位置信息).位置信息通常分为两类,一类是节点在某种遍历方法所 得字符序列中的序号,另一类是节点在 XML 文档中的路径信息. 实际索引数据的保存可以采用不同的形式 [11,12],如保存为文本(native storage)、关系数据形式和面向对象 数据形式.其中最常见的就是将索引记录保存为关系的方式.本文主要针对这种方式展开叙述,其中涉及到的相 关概念对其他方式的理解也是具有借鉴意义的. 1.2.2 结构摘要类索引 结构摘要是针对 XML 查询处理基本方式中的第 2 个缺陷而来的:既然是相同路径重复遍历的问题,那么, 将 XML 数据按照路径进行约简,要求这种约简中只保存 XML 数据中不同的路径,将具有相同路径的节点集合 作为约简中该路径的末端节点的内容,那么,在 XML 数据上的路径查询处理,也就能够在约简结构中得到相同 的结果节点集合.
2
XML 索引应考虑的因素
2.1 XML查询的要求 不拘 XML 索引是何种形式,其实际设计与实现都必须考虑 XML 查询的基本特征——结构关系的保存以 及基于结构信息快速计算节点间结构关系这两个因素.这实际上就是要求相关的技术能够满足高效处理 XML
2066
Journal of Software
软件学报
2005,16(12)
查询的请求.实际研究中,XML 查询是一个范围很大的方面,内容很多.本文仅就 XML 索引为满足查询而应当具 备的两个基本方面展开讨论,包括: 2.1.1 结构关系的获取 虽然传统的索引技术经过长期的积累已经相对成熟,但是,这类索引技术针对的主要是根据值(而不是具有 某种关系的模式)定位数据记录的功能,不太关注数据记录间的逻辑关系;而 XML 数据查询的基本特征就是根 据模式特征(正则路径表达式形式描述的结构关系)的输入提取符合该模式的数据,所以,XML 索引的主要内容 就是设计适用于模式匹配的技术.自然,针对正则路径表达式的相关设计也就成为考虑的重点. XML 查询中模式匹配的问题,如前面所述,主要就是对 XML 数据中结构关系的表达,以及如何利用已有的 索引技术为高效获取符合结构关系[13](见前面所述的包含关系定义)的数据集提供支持的问题. 2.1.2 保 序 根据前面的叙述可知,元素在具体的 XML 文档中是有一定的次序限制的,该次序称为 XML 文档的次序. 各元素在次序中出现的顺序取决于对 XML 树的先序遍历.当查询关系存储的 XML 分解数据时,由于关系模式 不存在次序的概念,为此,就必须在分解 XML 的过程中考虑如何确保查询的结果仍然符合结果元素集在原 XML 数据中的次序关系,与这些元素在原 XML 文档先序遍历次序间有一一对应的关系,而且元素间的结构关 系也必须一致. 2.2 XML数据修改的要求 2.2.1 修改有效性 要想真正实现对 XML 数据的管理,对 XML 数据进行修改是必不可少的功能.但是,到目前为止,关于 XML 数据修改问题还没有形成统一的标准.文献[14]对此作了探讨:给出了一些 XML 数据修改操作的定义,并就如何 在 XQuery 之上进行数据修改功能的扩展做了有益的尝试. XML 数据通常都会有相应的类型限制:当没有 XML 模式存在时,XML 必须是格式良好的;当存在一个相关 联的 XML 模式时,XML 数据就必须满足模式规定的数据生成规则.所以,既然修改存在改变 XML 数据结构的 可能性,那么,如何保证在修改之前确认这种修改不会触犯 XML 模式规定的规则,就成为 XML 数据管理研究的 主要问题. 由于在 XML 处理中,XML 索引结构完全能够代替 XML 源数据,即 XML 索引结构完全能够满足查询操作 的要求.所以,XML 索引结构同样应该支持这类限制.文献[15?17]给出了 XML 数据修改有效性的探讨,但是,文 章主要是基于 XML 树以及结构摘要上的工作,并没有涉及对关系化存储的 XML 数据的修改、验证的问题. 与之相象但有本质不同的一个概念是 XML 类型检查问题(XML type checking problem).简单地说,类型检 查是看一个 XML 数据是否符合 XML 模式的要求;而修改有效性则是判断一个 XML 数据生成过程是否能够保 证生成满足 XML 模式的数据. 2.2.2 数据与索引结构的一致性 由 XML 数据修改操作引起的另外一个问题就是如何维护 XML 数据与 XML 索引间的一致性,即保证 XML 索引能够动态反映 XML 数据上的修改.而且,当存在 XML 的二级索引时,修改引起的连锁反应也必须在二级索 引中体现.有关的概念在关系数据库研究中都有很好的阐述,在此不一一叙述.但是,由于 XML 数据保有结构信 息的原因,这类一致性问题也体现出新的特点[18,19]. 2.3 两点说明 2.3.1 节点记录索引的关系保存与 XML-关系映射存储的区分 在实际文献中,将 XML 数据管理与关系数据库管理系统结合,除了上述将节点记录索引保存为关系的方式 以外,还有一类基于 XML 模式分解的 XML 数据关系保存方式[20?25].其基本思想就是根据 XML 模式中蕴含的 限定 XML 数据结构的规则,将结对出现概率大的元素作为 RDBMS 中的关系(在有关的文献中称这种技术为内 联(inlining)),从而实现了对 XML 模式的分解,并作为关系模式;之后,将 XML 数据分解保存到相应的关系表中. 虽然都是借助于关系数据库管理系统,但是二者的本质区别在于:节点记录索引的关系存储是针对结构查
孔令波 等:XML 数据索引技术
2067
询操作而来,每条索引记录都包含有便于结构查询的辅助信息——位置信息;而模式映射的关系存储方式是尽 可能地将 XML 数据转换为符合关系规则的形式,不便于结构查询的处理. 2.3.2 XML 索引的结构层次 在分析 XML 索引研究内容时,比较混乱的 是 XML 索引的界定问题.尤其是将 XML 数据 交由关系数据库管理系统(RDBMS)管理时,原 有 RDBMS 中开发的索引与 XML 索引间的关
Post-traversal order
8
b3
10
root
Pre/Post plane - sample.xml
a3
系,现有研究文献都没有进行讲解.本文建议将 前面叙述的索引看作是 XML 索引结构中的第 1 层次,而原有数据管理系统的索引(甚至一些 针对 XML 数据处理特点新研发的部分结构)都 可 看 作 是 XML 索 引 结 构 中 的 二 级 索 引 (secondary index),这样一来,有关 XML 索引的 整体研究就有了清晰的把握.例如,文献[26]中 的 Xp-tree 索引就是在区间编码的基础上引入 空间数据访问的索引结构,即可看作 XML 二级 索引的一种形式.比较常用的有经典的 B-tree, B+-tree 索引、哈希索引、R-tree 索引,以及延自 于它们的各种演化形式索引.
c3
6
a2
b2
4
c2
a1
2
b1
c1
0
0
2
4
6
8
10
Pre-traversal order
Fig.3 图3
The node distribution of sample.xml on pre-post plane sample.xml 中元素节点在 pre-post 平面上的分布
3
节点记录类 XML 索引
节点记录类索引本质上即是将 XML 数据分解为数据单元的记录集合,同时在记录中保存该单元在 XML
数据中的位置信息.主要有两种获取位置信息的方法,一种是节点序号方法(node numbering method,有时也称为 节点标签方法,node labeling method),另一种是节点路径方法(node path method).对它们的研究占了 XML 数据 处理研究文献中相当大的部分.根据路径信息表现形式的不同,节点记录类索引分为 3 大类:基于节点序号的索 引、基于节点路径信息的索引和二者相结合的混合索引. 3.1 节点序号类索引 3.1.1 基本思想 这类索引中的位置信息是节点在某种遍历序列中的序号.对于一个 XML 文档,设计遍历 XML 文档的策略, 遍历的最终结果表现为一个由节点组成的序列;相应地,节点的标签在序列中就有一个序号,该序号表明了节点 间的次序关系,也能够反映节点间的结构关系,进而,就可以基于该序号信息捕获节点间的结构关系. 节点序号类 XML 索引的基本思想是:基于 XML 文档设计某种遍历策略,得到由元素组成的序列,节点的标 签在序列中就具有唯一的次序,将序列与某指标集(最常用的就是自然数)建立一一映射的关系,对应序列中某 个标签就有唯一的序号;对任意两个具有节点序号信息的节点,可以构建某种运算,该运算的结果可以表征节点 间的结构关系,即{(独立单元属性,位置信息)}→{结构关系}映射. 根据标签序列生成方式的不同,目前研究文献中序号类索引可分为两种:基于标签有向树的遍历(如先序遍 历和后序遍历)和基于字符流模型的顺序处理.根据映射指标集的不同,可分为赋以自然数[27?30]、赋以局部编码
[31?35]
和赋以素数 [36] 的方式.在序列生成和节点序号赋值的基础上,可以构建不同形式的位置信息,进而形成不 相关概念:位置信息的不同形式 序号对形式
同的节点记录索引形式. 3.1.2 3.1.2.1
位置信息中最为常见的是所谓的区间编码 [27,29](interval encoding)为序号对的形式.其基本思想是:将节点
2068
Journal of Software
软件学报
2005,16(12)
在先序遍历序列和后序遍历序列中的序号对组成的区间(pre,post)作为该节点的位置信息.图 3 即为 sample.xml 中元素节点对应的序号对在 pre/post 平面上的分布.为了能够区分相同标签的节点,图中将 a,b 和 c 标签包含的 文本信息作为该节点在图中的标签示意.图中以 b2 点为中心,作平行于 X 轴和 Y 轴的直线,就会将 Pre/post 平面 分成 4 个区域,各区域的节点恰好是以 b2 为上下文节点满足如下 4 个轴关系节点的集合:b2 的祖先节点、b2 之后的节点、 之前的节点和 b2 的子孙.基于区间编码的基本索引记录形式为(s,pre,post),其中 s 为 XML 树中 b2 节点的标签属性.有如下的结论: 命题 1. 给定一棵 XML 树,XT,能够建立一组满足三元关系 R?String×Nat×Nat(Nat 为自然数)的实例 Rn,Rn 中的每一个元组(s,start,end)都满足如下条件: 1) s 是 XT 中节点的标签; 2) 对所有(s,start,end)∈Rn,start＜end; 3) 如果节点 s1 和 s2 在 XT 中呈祖先-子孙关系(s1 是 s2 的祖先节点),那么相应的元组(s1,start1,end1)∈Rn 和 (s2,start2,end2)∈Rn 必然满足 start1
孔令波 等:XML 数据索引技术 编码的索引展开叙述.
2069
较早尝试将 XML 数据纳入 RDBMS 管理的方法是文献[41]中提出的 Edge 方法.该方法采用的数据模型近 似 OEM,这一点与后续的基于 XML 树的相关方法不同.它的设计介于面向 XML 数据的映射和模式指导下关系 映射之间:既延续了第 2.3.1 节中的模式映射的特点——需要构造复杂的关系模式来支持 XML 数据的查询;又 吸收了树结构分解的方式.虽然文中讨论了对数据修改的支持,但是却没有深入探讨数据修改合法性的控制问 题.文献[20]也具有类似的特点.文献[43]延续了 Edge 的形式,通过引入无损和有效两个概念从理论上系统地讨 论了 XML 数据保存为关系表的有效性问题.可惜的是没有深入探讨基于 Edge++之上的查询、修改等问题. 文献[22]给出了基于区间编码的 XML 索引方法.该方法基于 XPath 中给出的 XML 树模型.相关概念已在 第 3.1.2 节给出.需要指出的是,基于这种模式实现路径模式的查询的基本方式只能是将路径分解为基于区间编 码的比较.这一特点造成基于该方法的 XPath 处理性能不理想,尽管文中点明基于区间编码的 XPath 处理性能 较 Edge 提高了 5 倍.为了解决这个问题,文献[31]给出了采用时空数据管理中开发的多维索引区间编码的组织 索引记录,如 R-tree 和 RI-tree,但还是没有摆脱分段求解带来的问题. 与之相似的另一个广为应用的序号对编码方式,B-E-L,同样具有类似区间编码的缺陷.为了解决该问题,研 究人员除了采用类似于区间编码中的解决办法——设计新的多维索引以外,如文献[44]的 RI-tree,文献[45]的 XR-tree,主要采取了优化连接操作的手段;文献[46]给出了多谓词合并连接(multi-predicate merge join,简称 MPMGJN)的算法,文献[40]给出了位置统计图连接(pH-join:position histogram join)算法,文献[47]给出了基于 B+-tree 的结构连接方法,文献[48]则分别讨论了区间模型(interval model)和位置模型(position model)上的结果 集合估计算法以帮助选择较优的连接次序,以及文献[49]的基于划分的连接算法.但是,这些改进都没有摆脱结 构操作是最小二元关系的本质,所以,其 XPath 处理的实际性能不能达到最优.鉴于 RDBMS 中 LIKE 语句的潜 力,许多研究尝试了将二者混合的方式. 3.1.4 3.1.4.1 节点序号类索引分 XPath 查询处理 与结构摘要类索引不同,节点记录类索引打破了必须通过标签路径查找节点这一限制,将 XML 数据分解成 规范形式的节点记录.由于保存了节点的位置信息,而且能够很好地结合到成熟的关系数据库管理系统中.基于 节点序号类索引的查询路径处理,根据编码的不同分为 3 类. 序号对编码的查询处理通常分成两个阶段:第 1 个阶段是将查询语句分解为基本的二元结构关系运算形 式,即只利用索引记录中的位置信息处理两节点间的结构关系判断;第 2 个阶段是将第 1 阶段的中间结果进行 合并.实际处理中多采用树形结构组织查询的处理.虽然任何查询语句都可以基于这类索引记录得到准确的结 果,但是,正如前面的概述所述,基于这类索引的查询处理往往导致较多的连接操作,无法达到较高的性能.这在 进行复杂语句的处理时更为突出. 基于局部编码的查询处理,由于无法摆脱耗时的数字序列模式匹配操作,基于它们处理 XPath 的研究相对 要少得多,但是,由于这类编码隐含地保存了路径与内部节点间的关系,反而在新发展的 XML 信息获取处理中 找到了进一步研究的价值(参见第 5.2.1 节).文献[50]在引入 FST(finite state transducer)模块后探讨了 Dewey 编 码在 Twig 处理上的优势,并进一步将序号对编码引入到处理机制中,以减少结构关系计算的代价. 至于素数编码,相关的文献只有文献[36].虽然这种编码在结构关系的表达上具有简洁的数学上的映射,但 是,当数据规模较大时,就需要系统提供很大的素数,这在实际使用时是不方便的:一是需要较大的保存空间,二 是素数的关系运算也会有较大的开销. 这类索引都能够支持 XML 查询对保序的要求. 3.1.4.2 数据修改的支持 针对第 2.2 节中给出的 XML 数据修改支持的要求,在现有节点序号类索引中,文献[32]给出了将实数作为 序号的指标集的思路:利用实数可表示无穷精度的特点满足插入数据带来的节点序号的扩张.但是,由实数计算 带来的结构关系计算的代价是提高查询处理性能所不容忽视的.文献[33]的扩展方式类似于哈希桶的成倍分裂 方式,但是,当 XML 树的扇出很大时,标签的标示会变得很大,带来了冗余.文献[3,43,51]给出了预留空间的处理
2070
Journal of Software
软件学报
2005,16(12)
方法.文献[36]通过维护同余表(SC table:simultaneous congruence table)实现了对保序和数据更新的支持,但是, 当新节点插入时,重新计算同余表的代价也是不容忽视的.文献[52]采取了动态编码的技术,引入了 W-BOX 和 B-BOX,具有较好的理论分析和实验的结果. 至于对修改合法性检验的支持,在这类索引中还没有开展相关的研究.但是,从数据管理的角度对这类形式 的 XML 数据的修改的支持是非常必要的. 3.2 节点路径类索引 3.2.1 基本思想 节点的路径信息同样蕴含节点在 XML 数据中结构的信息:如果给定两节点的路径信息,同时预知两节点存 在结构关系的情况下,就必然可以获知它们之间的结构关系.即节点 A 的标签路径包含节点 B 的标签路径,那么, 在 XML 树中 A 和 B 之间一定具有祖先-子孙的结构关系,且 B 是 A 的祖先.所以,基于路径信息来获取节点的 结构关系就成为另一组 XML 数据处理技术的思路来源,并演化出基于节点路径的 XML 索引[53?58].这类索引的 核心技 术 是 字 符 串 的 模 式 匹 配.因 而,这 类 索 引 记 录 数据的管理方法,有许多是来自于信息获取领域的.例 如,Trie,Patricia trie 以及 Suffix tree,甚至 Suffix array 等结构.索引记录的基本模式为(数据单元标识,路径信息). 由于这类索引的大部分处理模式与传统的模式匹配有很深的关系,在此不再展开叙述.仅对基于路径的多维索 引的概念进行简单的叙述. 3.2.2 相关概念:路径多维索引-UB-tree 在路径索引记录数据的管理中,文献[53]突破了路径匹配只能基于字符串匹配的限制,借助于 Z-地址和 Z区间的概念,通过对路径的转换,引入了 UB-tree 结构,实现了借助于转换对路径的多维管理. 定义 1. Z-地址. 设 ?表示 n 维空间,?空间中每条记录的第 i 个属性 Ai 具有 s 个可能的取值,表示为 Ai=Ai,s?1,Ai,s?2∧Ai,0,那么, 对?空间中的任一记录 O∈?,都有一个唯一的 Z-地址函数 Z(O)与之对应:
Z (Ο ) = ∑ ∑ Ai , j 2 jn + i ?1 .
j = 0 i =1
s ?1 n
利用 Z-地址,可以构建一个从 n 维空间到 1 维 Z-地址空间的映射.n 维空间中的每一点都对应 Z 地址空间 的一个区间? α,β?,称为 Z-区间(Z-region).以 B+-tree 对 Z-区间集合中的数据做索引,就成为 UB-Tree 的基本思想. 当将 XML 路径集合看作是某个 n 维空间 (取 XML 数据中最长路径的长度作为维度 n 的值 )中的一个实例时, 就可以实现将 XML 路径到 Z-地址空间的转换,进而可以实现用 UB-tree 来对 XML 路径信息进行索引的目的. 虽然这种基于转换的多维管理结构在转换代价和路径转换空间冗余两个方面存在不足 ,但是 ,由于多维索 引的概念能够突破对字符串只能进行连续模式匹配的方式 , 所以 , 在这个方向上作进一步的研究具有实际的 意义.
3.2.3
节点路径类索引概述 文献[57]直接保存了节点标签路径的字符串,并利用了 SQL LIKE 的模式匹配实现对路径查询的处理.文献
[56]则利用了可将 XML 文档的节点路径标签字符串和查询路径字符串都分解为后缀片断的特性:将文档的后
缀片断用树结构组织 , 之后将查询路径对应的片断在文档树上匹配从而得到最后的结果 . 文献 [54] 的思路与之 类似,只是将后缀换成了 Prüfer 编码.
3.2.4 3.2.4.1
节点路径类索引概述分析
XPath 查询处理
基于节点路径信息的查询处理 ,与节点序号类索引的查询处理是类似的 , 只是其中的结构关系操作换作路 径字符串集合中对查询路径的匹配 :将节点路径记录交由关系数据库管理系统管理时 ,通过巧妙的设计 ,直接利 用 SQL 中 的 模 式 匹 配 功 能 (LIKE ‘%’) 实 现 查 询 路 径 中 的 祖 先 - 子 孙 关 系 , 如 文 献 [57] 中 将 path 写 成
“a1#/a2#/a3#/a4#/a5”的形式.这样,所有满足 “//a3//a5”结构的节点的 SQL 语句都可以写成 “LIKE ‘#%/a3#%/a5’”
的形式.尽管路径标签字符串能够满足 XPath 路径模式的匹配,但缺乏保序支持的能力,所以,在实际中多采取与
孔令波 等:XML 数据索引技术 序号相结合的混合方式.
2071
至于新颖的多维路径索引—— UB-tree, 在面向实际应用时还存在如下的缺陷 : 在处理查询时 , 必须经过字 符串到 Z 地址空间的转换,其代价是不容忽略的;实际存储中,必须预先给定标签路径长度的最大值,这就造成存 储的冗余 ,也为 Z- 地址的计算增加了不必要的工作 .尽管如此 , 作为新的处理方式 ,标签路径的多维索引方式仍 然是颇具吸引力的方式.
3.2.4.2
数据更新支持
在这类索引的文献中,未见支持 XML 数据修改的探讨. 3.3 混合索引 同时保留节点的序号信息以及节点的路径作为索引记录的位置信息,就构成了此处的混合索引[38,59,60]. 这类索引记录的模式多为多个模式的组合,基本的模式为(数据单元的标识,路径 ID,序号位置信息)和 (路径
ID, 标签路径 ) 的组合 . 例如 , 文献 [38,59]都采用了标签路径与序号对结合的方式 . 与之不同的是 , 文献 [60] 采取了
将后缀树[56]与序号对结合的方式. 混合索引吸收了节点记录索引和路径索引的优点 :既具有路径模式匹配是不必分解为最小片断的要求 ,同 时还能够保证得到的结果符合保序的要求.但是,在支持 XML 数据修改问题上鲜见有益的探讨.
4
结构摘要类 XML 索引
4.1 基本思想 以 XML 树结构中节点的路径信息为基础 ,采取某种约简方式 ,使得约简后的树结构只维护不同的路径信 息 , 而不会存在具有相同路径的两个节点 . 这里 , 结构摘要索引仍然采取标签有向图的结构 . 当基于结构摘要进 行 XML 查询处理时,就可以避免第 1 节所述的基本 XML 查询处理的另一个缺陷. 4.2 相关概念 定义 2. 结构摘要. 给定标签有向图 G=(VG,EG,rootG,ΣG),G 的结构摘要是基于定义在 VG 上的一个等价关系上的标签有向图
IG=(VI(G),EI(G),rootI(G),ΣG).其中 VI(G)的节点 n 称作索引节点,对应于 VG 中满足等价关系的节点集合,即 n.extent;
并且,EI(G)中存在一条边(ui,vi),当且仅当对应于 EG 中存在一条边(ud,vd),并且 ud∈ui.extent,vd∈vi.extent. 在这类结构摘要索引中,为了达到简化 XML 树的目的,最初多采用自动机理论中的 NFA 到 DFA 转化的思 路 [62].在文献 [63]中引入了双拟和双似的概念以后 ,由于双似概念能够准确地表述结构摘要问题 ,所以 ,后续的这 类索引多基于这个概念[64?69]. 定义 3. 双拟关系(Bisimulation). 给定一棵有向树 G,G=(V,E),其中 V 是 G 中节点的集合,E 是 G 中边的集合;对 G 进行转换,可以得到另外一 种表达形式 G′(V′,E′),它与原来的 G 应具有如下的关系:G′的点元素集合 V′与 G 中的 V 是一样的,同时 G′元素 间的关系 E′与 G 中的 E 是一致的,但是二者的表现形式是不同的;否则,G′=G.基于 G 和 G′可以定义一个二元关 系 R,它是 G 中节点 V 和 G′的节点 V′的笛卡尔积:R={(p,q)|p∈V,并且 q∈V′}.如果 R 满足如下条件,则称 R 是 G 和 G′的一个双拟关系:
1. 如果在 G 中存在一个节点 p′,它与 p 具有关系 p → p ′ .
即,在 G 中有边α将 p 和 p′连结,那么,在 G′中必也存在一个元素 q′,它与 G′的元素 q 存在关系.
α
2. 类似地可以定义 G′中元素关系到 G 中节点间关系的映射:
如果在 G′中存在一个节点 q′,使得从 q 到 q′经过元素间关系α,即 q → q ′ ,那么,在 G 中必然也有一个节点 p′, 使得从某一节点 p 到 p′也有α关系,即 p → p ′ . 定义 4. 双似关系(bisimilarity).
α α
2072
Journal of Software 软件学报 2005,16(12)
如果 G 和 G′的两个节点 p,q 间存在双拟关系,那么称
root
0
Level 0
Root Element Text String value
p 和 q 是双似的(bisimilar),记作 p≈bq.由前面双拟的定义
可知 ,两个元素双似是等价的关系 .显然 ,两个节点满足双 拟的关系,那么它们必然具有相同的标签路径.
a
Level 1
图 4 即为 sample.xml 文档的基于双似等价概念的结 构摘要结构 . 从图中可以看出 , 结构摘要只保留了唯一的 路径 , 具有相同路径的文本数据都集中在该路径的节点
Level 2
a1 a2 a3
b
之中 . 显然 , 只搜索一条路径就可以获取具有相同路径的 所有节点. 考察到 XML 查询语句中更多出现的是结构片段查
Level 3
b1 b2 b3
c
询 , 而不是整个从根节点开始的简单路径 , 所以 , 文献 [62] 放松了双似的限制,引入 k 阶双似的概念,捕捉 XML 数据 中路径的局部特征以满足结构片段查询的特点. 定义 5. K 阶双似(K-similarity).
c1 c2
c3 c4 c5 c6
Fig.4
图4
Structural summary of sample.xml by bisimilarity equivalence relation
1) 对标签有向图 G 中的任意两个节点 u 和 v,如果
它们具有 u≈0v,当且仅当 u 和 v 具有相同的标签.
sample.xml 的基于双似等价关系的结构摘要
2) 对标签有向图 G 中的任意两个节点 u 和 v,如果
它们具有 u≈kv,当且仅当 u 和 v 的父亲节点 u′和 v′具有
u≈k?1v. K 可以看作是控制整个索引结构的分辨率参数.
在实际应用中,如何在 G 中寻找节点的最大 K 阶相似性,即如何以尽可能大的相似性划分 G 的节点集合, 成为这类索引的核心技术. 4.3 结构摘要索引概述
Stanford 大学的 Lore 项目中的 DataGuide[61]是结构摘要的最初形式,其基本思想是基于将 NFA 转换为 DFA
的形式对 XML 数据中的相同路径进行约简.这种基于处理的阐述缺乏形式的描述,不能很好地描述结构摘要的 本质特征.1-index[62]引入了双似等价关系的概念,从而对结构摘要找到了形式化描述的理论基础.
DataGuide 和 1-index 能够很好地满足简单路径查询的要求,但在实现性能上稍显不足.为此,APEX[64]引入
了依赖于 XML 数据查询分布的信息:将经常出现的 XML 查询语句对应的标签节点预先保存在一个哈希结构 中.它的作用类似于 Cache 的功能:当有新的查询要求处理时,首先在哈希表中搜索是否有满足的节点集合. 为了增加对结构摘要树便利的灵活性,文献[65]进一步提出了 F&B 索引,并声称 F&B 索引是同类索引中回 答 Twig 查询存储空间最小的数据结构,它可以满足全部分支路径查询的要求.但是,由于 F&B 索引在实现上必 须依赖内存,而且在基于它处理查询的优化上还存在进一步的空间,这些因素都限制了 F&B 索引在实际中的应 用 . 针对这个问题 , 演化出两类解决方案 , 一是所谓近似结构摘要索引 , 如 Xsketch,A(K)-index,D(K)-index, 以及
M(K)-index;另一个就是文献[69]提出的基于磁盘存储的并引入序号对的 F&B 索引.
在 K 阶双似概念的基础上,类似于 DataGuides,可以创建相应阶的 XML 索引.A(K)-index[63]索引的创建过程 是一个逐渐细化的过程:K 阶索引的建立是在(k?1)阶索引的基础上实现的.在 1-index[62]和 A(K)-index 的基础 上,D(K)-index[67]吸收了 APEX 中动态反映查询分布的优点,将二者进行了结合,并具有如下的特征:对任意两个 节点 u 和 v,如果 u 和 v 之间存在一条边,那么,K(u)≥K(v)?1.其中,K(u)和 K(v)分别表示节点 u 和 v 的局部相似性
(local similarity),即父节点的 K 值不应小于孩子节点的 K 值 ?1.M(K)-index[69]的索引结构与 D(K)-index 类似,在
实际应用时 ,同时尝试随查询语句动态调整的方式 .但是 ,这种类近似结构摘要索引只是部分减轻了索引空间以 及查询处理效率的问题. 文献[69]中的 F&B 索引一方面实现了将结构摘要树保存于磁盘,而且,为了提高数据访问的效率,另一方面,
孔令波 等:XML 数据索引技术
2073
还深入探讨了在保存中引入聚集机制的方法,以及将编码机制(文中采用的是 B-E-L)结合进 F&B 索引的方案. 但是,由于没有超越通过摘要树遍历得到查询结果的处理方式,其实际应用中的性能仍需要实践的结果来证明. Table 1 Summarization for XML indices 表 1 XML 索引综合概述表格
Scheme name DataGuides 1/T-index A(K)-index APEX F&B index XSketch D(K)-index M(K)-index Disk-Based F&B Edge Interval encoding Order-Size B-E-L Edge Prime Dewey ORDPATH PSL Extended Dewey UB-Trees XParent ViST PRIX XRel Extended inverted index BLAS
++
Ref.
Year
Class
Subclass
Subsubclass
Query processing Basic computation Ordering support
Modification/Validation support Modification Incremental maintenance No discussing Validation
[61] [62] [63] [64] [65] [66] [67] [68] [69] [41] [27]
1997 1999 2002 2002 Structural summary 2002 style index 2002 2003 2004 2005 1999 2002 Sequence number pair Node numbering index Unequal join & Mediate result merge ? ? Navigation on summary tree No
Incremental maintenance No discussing Yes
No discussing
Yes
No discussing Straightforward SQL series Extended preorder and range
[21,52] 2003 1999~ [37? 2003 42,45] [52] 2005 [36] 2004 [32] 2002 [31] 2004 [33] 2004 [50] [53] [56] [55] [54] [59] [38] [60] 2005 Node 2001 record ~2002 style index 2002 2003 2004 2001 2003 2004
Node path index
Yes No discussing Prime modulo SC table Number No discussing sequence Local matching ρ-tight subtree No encoding FST No discussing discussing transducing TransforNo mation Multi-dim & Range discussing No discussing computation Path string Yes matching Dynamic scope Suffix tree No Label path allocation scan Prüfer Yes No discussing sequence matching Prime Path string matching Suffix tree scan No discussing
Hybrid
?
Yes
No discussing
4.4 结构摘要索引分析
4.4.1
XPath 查询处理
基于结构摘要的 XML 查询语句处理,与第 1.1 节中所述的在 XML 文档之上的 XPath 查询处理是相同的:
扫描路径获取满足查询路径的节点集合 .由于结构摘要已经尽可能地合并了相同标签路径的节点 ,所以 ,周游一 条路径即可得到该标签路径下的所有节点,避免了相同标签路径的重复访问的缺陷,与直接基于 XML 原始数据 匹配查询路径模式相比 , 性能有了大幅度的提高 . 而且 , 由于它维护了整体的信息 , 基于该结构就可以比较容易 地实现对 XML 数据修改的支持. 但是 ,结构摘要虽然约简了路径信息 ,对查询路径的匹配本质上仍然是周游的方式 ,这就需要维护整体的数
2074
Journal of Software 软件学报 2005,16(12)
据结构,难以适用于大规模数据;而且,由于只是保存约简后的树结构,对保序的支持就难以实现.
4.4.2
对数据修改的支持 针对数据修改的问题 ,结构摘要类索引中有文献 [61?63],它们都试图寻找一个结构摘要类索引通用的增量
式修改方法 , 基本思路可概括为 : 在发生数据修改的部分 , 根据修改的类型不同插入新数据 , 或删除某个节点 , 对 涉及的节点分别进行分割 (split) 或合并 (merge) 处理 . 本质上 , 这种修改的支持还只是数据与索引间的一致性 问题.
5
XML 索引技术总结及研究展望
5.1 XML索引技术总结 对 XML 数据管理的研究,是当前诸多领域的热点.有鉴于索引技术在数据管理中的突出地位,众多的 XML 文献也将研究集中到了 XML 索引的技术.如何捕获 XML 数据中的结构特征,并高效地支持路径(结构)查询的 处理,是其中的核心.在给出 XML 索引应考虑的限制后,本文对当前分布于众多研究文献中的 XML 索引进行了 汇总,按照解决现有基于 XML 文档进行 XML 查询存在的两类缺陷的方式的不同,将繁多的 XML 索引归入两 大类:结构摘要类索引和节点记录类索引.并通过 XML 数据结构信息的捕获、如何高效处理结构关系的查询, 以及索引对 XML 数据修改的支持 3 个方面进行了阐述.表 1 是全文内容的总结,包括索引的类别、查询性能以 及对 XML 数据修改的支持. 5.2 研究展望 如果说 XML 数据可以看作由结构部分(即元素见结构关系的集合)和内容部分(包括元素属性的值和元素 中所含文本的集合)组成,那么 ,当前有关 XML 数据处理的研究基本上属于这样一种模式:给定表征结构关系的 查询路径,搜索 XML 数据空间寻找匹配结构模式的内容集合.也就是说,指到目前为止,经典的 XML 查询都是基 于用户已经了解 XML 数据的组织结构为前提的.显然,这一要求大大提高了对普通用户搜索 XML 信息的要求, 更不用说要求用户掌握查询语言的语法规则 . 为此 , 可以采取两种思路 : 一种是设计辅助功能 , 方便地帮助用户 了解 XML 数据的组织结构;另一种是 XML 的信息获取.除此之外,XML 数据修改合法性验证是另一个必须关 注的方向.
5.2.1
同时满足 XML Query 和 XML IR 效率要求的索引 如果说类似于 XPath 的查询处理,即首先精心定义满足 XML 内容和结构要求的查询语言,之后搜索 XML
数据、匹配满足使用查询语言描述的模式从而得到最后的结果,是近期 XML 数据处理的主要研究内容,那么, 将传统信息获取中的优点纳入 XML 数据的处理——希望提供给用户一种友好的使用形式,成为当下 XML 数 据处理的新的研究点 .近期的研究可分为两个方面 :一方面是扩展前述面向模式匹配的查询语言 (如 XQuery)以 支持部分 XML IR 中的特点[70?75];另一方面是将对用户使用友好的关键字查询延伸至 XML 数据[39,76?79].其中, 由于第 1 种结合不能摆脱原有查询语言的基本要求——仍然要求用户必须知晓 XML 数据的结构模式以及掌 握复杂的语法,所以,本质上不符合 XML IR 的要求.而对 XML 数据的关键字查询,其基本的操作就是找到满足 关键字的 SLCA 节点(smallest lowest common ancestor)[78],针对这一问题多采用 Dewey 编码.而我们知道,Dewey 编码对 XML Query 处理的性能是不足的,另外,基于 Dewey 求解 SLCA 节点的基本操作主要是数字序列的模式 匹配,效率堪忧,所以,设计既能够保证 XML Query 查询的性能,又能够确保 XML IR 处理效率的索引,就成为值 得深入探讨的另一个方向.
5.2.2
内部结构信息的获取 与 XML 信息获取思路不同,将 XML 数据查询引向 XML 数据的另一部分——结构特征,就会得到具有实
际意义的处理方式 :给定 XML 数据片断 (可以是元素文本内容中的一个字符 ,也可以是一段简单的路径信息 ), 搜索 XML 数据的结构部分,寻找所有指向给定片段的路径集合.显然,这种处理方式对于引导那些不知道 XML 结构信息的用户进一步寻找更为详尽的目标是很有帮助的 .粗看起来 ,似乎前面所述的基于节点路径信息的索 引方式完全能够胜任 ,但是 ,由于上述结构中的路径是完整的字符串形式 ,不能够方便地提供路径内部的统计信
孔令波 等:XML 数据索引技术
2075
息,因而无法胜任诸如 “以给定片断为核心,半径为 3 个字符的路径集合”类的查询.从这一角度来说,从信息获取 领域引入到 XML 数据处理范畴的关键字查询[39,78]也是不敷使用的.而另外一大类节点记录索引则由于没有保 存路径有关的信息 , 虽然能够满足传统给定查询路径寻找内容集合的方式 , 但不适于这里提到的逆向查询的 处理.
5.2.3
节点记录索引对数据修改合法性的支持 仅仅是最近几年,尤其是 2003 年,2004 年,对 XML 数据修改合法性层次的支持才在几个会议中有了相关的
讨论[15?17,80,81].与以前的 XML 文档有效性验证(validation of XML documents)[82]不同,这些文章大多采用增量有 效性验证的概念(incremental validation of XML documents): 给定 XML 模式(DTD 或 XML Schema 的形式)τ,一个满足τ所规定的限制条件的 XML 树 T,T∈sat(τ)(表示 T 满足τ的限制 ),以及将 T 转换为 T ′的修改的操作序列 S,增量验证的问题就是如何设计一个检验机制 M,它能够 有效检验 T ′∈sat(τ).通常所指的修改操作包括如下类型:
(1) 替换指定节点的标签; (2) 在指定节点后插入新的叶节点; (3) 在指定节点中插入一个节点作为该节点的第 1 个孩子; (4) 删除指定的叶节点.
显然,上述的修改操作没有涉及递归删除、插入等形式.为解决这个问题,上述文章采取了不同的方法,除了 文献 [80] 采取了在修改语句中增加条件函数以外 , 其他解决方法都有一个共同点 , 就是借助于不同形式的自动 机对字符串的接收、拒绝判断的能力 . 但是 , 所有这些修改合法性验证的方法都不能自然的扩展到节点记录类 索引方式.如何设计针对节点记录类索引形式的 XML 数据修改合法性验证机制,因而具有实际的意义. References:
[1] [2] [3] 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/7c2720695.html,/1000-9825/12/1822.htm Barashev D, Novikov B. Indexing XML to support path expressions. In: Manolopoulos Y, Návrat P, eds. Proc. of the 6th East European Conf. on Advances in Databases and Information Systems (ADBIS). Bratislava: Springer-Verlag, 2002. 1?10. 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). Roma: Morgan Kaufmann Publishers, 2001. 361?370. [4] 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). Roma:Morgan Kaufmann Publishers, 2001. 341?350. [5] [6] [7] [8] Zhang C. Relational databases for XML indexing [Ph.D. Thesis]. Wisconsin: University of Wisconsin-Madison, 2002. 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. 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. 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. [9] [10] [11] [12] 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. 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. Jagadish HV, Al-Khalifa S. TIMBER: A native XML database. The VLDB Journal, 2002,11(4):274?291. Fiebig T, Helmer S, Kanne CC. Anatomy of a native XML base management system. The VLDB Journal, 2002,11(4):292?314.
2076
[13] [14] [15] [16] [17]
Journal of Software 软件学报 2005,16(12)
Miklau G, Siciu D. Containment and equivalence for a fragment of XPath. Journal of the ACM, 2004,51(1):2?45. Tatarinov I, Ives ZG, Halevy AY, Weld DS. Updating XML. In: Aref WG, ed. Proc. of the 2001 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Santa Barbara: ACM Press, 2001. 413?424. Papakonstantinou Y, Vianu V. Incremental validation of XML documents. In: Calvanese D, Lenzerini M, Motwani R, eds. Proc. of the 9th Int’l Conf. (ICDT). LNCS 2572, Siena: Springer-Verlag, 2003. 47?63. Barbosa D, Mendelzon AO, Libkin L, Mignet L. Efficient incremental validation of XML documents. In: Titsworth F, ed. Proc. of the 20th Int’l Conf. on Database Engineering (ICDE). Boston: IEEE Computer Society, 2004. 671?682. Abrao MA, Bouchou B, Ferrari MH. Incremental constraint checking for XML documents. In: Bellahsene Z, Milo T, Rys M, Suciu D, Unland R, eds. Proc. of the 2nd Int’l XML Database Symp. (Xsym), Database and XML Technologies. LNCS 3186, Springer-Verlag, 2004. 112?127.
[18]
Kaushik R, Bohannon P, Naughton JF, Shenoy P. Updates for structure indexes. In: Bressan S, Chaudhri AB, Lee ML, Yu JX, Lacroix Z, eds. Proc. of the 28th Int’l Conf. on Very Large Data Bases (VLDB). LNCS 2590, Hong Kong: Morgan Kaufmann Publishers, 2002. 239?250.
[19] [20] [21]
Yi K, He H, Stanoi I, Yang J. Incremental maintenance of XML structural indexes. 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. 491?502. Deutsch A, Fernandez M, Suciu D. Storing semistructured data with STORED. In: Haas LM, Tiwary A, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD’99). Philadelphia: ACM Press, 1999. 431?442. Shanmugasundaram J, Tufte K, He G. Relational databases for querying XML documents: Limitations and opportunities. In: Atkinson MP, Orlowska ME, Valduriez P, Zdonik SB, Brodie ML, eds. Proc. of the 25th Int’l Conf. on Very Large Data Bases (VLDB). Edinburgh: Morgan Kaufmann Publishers, 1999. 302?314.
[22] [23]
Kanne CC, Moerkotte G. Efficient storage of XML data. In: Young DC, ed. Proc. of the 16th Int’l Conf. on Data Engineering (ICDE). San Diego: IEEE Computer Society, 2000. 198. Klettke M, Meyer H. XML and object-relational database systems-enhancing structural mappings based on statistics. In: Suciu D, Vossen G, eds. Proc. of the Int’l Workshop on the Web and Databases (WebDB). LNCS 1997, Dallas: Springer-Verlag, 2000. 151?170.
[24]
Schmidt AR, Kersten ML, Windhouwer M, Wass F. Efficient relational storage and retrieval of XML documents. In: Suciu D, Vossen G, eds. Proc. of the Int’l Workshop on the Web and Databases (WWW). LNCS 1997, Amsterdam: Springer-Verlag, 2000. 137?150.
[25]
Bohannon P, Freire J, Roy P, Siméon J. From XML schema to relations: A cost-based approach to XML storage. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int’l Conf. on Data Engineering (ICDE). San Jose: IEEE Computer Society, 2002. 64?92.
[26]
Hwang JH, Nguyen VT, Ryu KH. A new indexing structure to speed up processing XPath queries. In: Zhou LZ, Ooi BC, Meng XF, eds. Proc. of the 10th Int’l Conf. on Database Systems for Advanced Applications (DASFAA). LNCS 3453, Trondheim: Springer-Verlag, 2005. 900?906.
[27] [28]
Grust T. Accelerating XPath location steps. 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. 109?120. DeHaan D, Toman D, Consens MP. A comprehensive XQuery to SQL translation using dynamic interval encoding. In: Halevy AY, Ives ZG, Doan A, eds. Proc. of the 2003 ACM SIGMOD Intl. Conf. on Management of Data (SIGMOD). San Diego: ACM Press, 2003. 623?634.
[29] [30]
Grust T, Teubner J. Accelerating XPath evaluation in any RDBMS. ACM Trans. on Database Systems, 2004,29(1):91?131. Amagasa T, Yoshikawa M, Uemura S. QRS: A robust numbering scheme for XML documents. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the 19th Int’l Conf. on Data Engineering (ICDE). Bangalore: IEEE Computer Society, 2003. 705?707.
[31] [32]
O’Neil P, O’Neil E, Pal S, Cseri I, Schaller G. ORDPATHs: Insert-Friendly XML node labels. 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. 903?908. Tatarinov I, Viglas SD. Storing and querying ordered XML using a relational database system. 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. 204?215.
孔令波 等:XML 数据索引技术
[33] [34] [35] [36] [37] [38] [39] [40]
2077
Cohen E, Kaplan H, Milo T. Labeling dynamic XML trees. In: Popa L, ed. Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS). Madison: ACM Press, 2002. 271?281. Han ZM, Fu NY. Efficiently coding and querying XML document. In: Bhalla S, ed. Proc. of the 4th Int’l Workshop on Databases in Networked Information Systems (DNIS). LNCS 3433, Springer-Verlag, 2005. 54?69. Han ZM, Xi CT, Le JJ. Efficiently coding and indexing XML document. In: Zhou LZ, Ooi BC, Meng XF, eds. Proc. of the 10th Int’l Conf. on Database Systems for Advanced Applications (DASFAA). LNCS 3453, Beijing: Springer-Verlag, 2005. 138?150. Wu XD, Lee ML, Hsu W. A prime number labeling scheme for dynamic ordered XML trees. In: Proc. of the 20th Int’l Conf. on Database Engineering (ICDE). Boston: IEEE Computer Society, 2004. 66?78. Runapongsa K. Methods for efficient storage and indexing in XML databases [Ph.D. Thesis]. Michigan: University of Michigan, 2003. Seo CY, Lee SW, Kim HJ. An efficient inverted index technique for XML documents using RDBMS. Information and Software Technology, 2003,45(1):11?22. Florescu D, Kossmann D, Manolescu I. Integrating keyword search into XML query processing. https://www.doczj.com/doc/7c2720695.html,/w9cdrom/ index.html Wu YQ, Patel JM, Jagadish HV. Estimating answer sizes for XML queries. In: Jensen CS, Jeffery KG, Pokorny J, Saltenis S, Bertino E, B?hm K, Jarke M, eds. Proc. of the 8th Int’l Conf. on Extending Database Technology (EDBT 2002). Prague: Springer-Verlag, 2002. 590?608.
[41] [42]
Florescu D, Kossman D. A performance evaluation of alterative mapping schemes for storing XML in a relational database. Technical Report, No. 3680, INRIA, France, 1999. Al-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu Y. Structural joins: A primitive for efficient XML query pattern matching. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int’l Conf. on Data Engineering (ICDE). San Jose: IEEE Computer Society, 2002. 141?152
[43]
Barbosa D, Freire J, Mendelzon AO. Designing information-preserving mapping schemes 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. 109?120.
[44]
Kriegel HP, PStke M, Seidl T. Managing intervals efficiently in object-relational databases. In: Abbadi AE, Brodie ML, Chakravarthy S, Dayal U, Kamel N, Schlageter G, Whang KY, eds. Proc. of the 26th Int’l Conf. on Very Large Data Bases (VLDB). Cairo: Morgan Kaufmann, 2000. 407?418.
[45]
Jiang HF, Lu HJ, Wang W, Ooi BC. XR-Tree: Indexing XML data for efficient structural joins. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the 19th Int’l Conf. on Data Engineering (ICDE). Bangalore: IEEE Computer Society, 2003. 253?264.
[46]
Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database management systems. In: Aref WG, ed. Proceedings of the 2001 ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Santa Barbara: ACM Press, 2001. 425?436.
[47]
Chien SY, Vagena Z, Zhang D, Tsotras VJ, Zaniolo C. Efficient Structural Joins on Indexed XML Documents. In: Bressan S, Chaudhri AB, Lee ML, Yu JX, Lacroix Z, eds. Proc. of the 28th Int’l Conf. on Very Large Data Bases (VLDB). LNCS 2590, Hong Kong: Morgan Kaufmann, 2002. 263?274.
[48] [49] [50]
Wang W, Jiang HF, Lu HJ, Yu JX. Containment join size estimation: Models and methods. 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. 145?156. Wang J, Meng XF, Wang S. Structural ioin of XML based on range partitioning. Journal of Software, 2004,15(5):720?729 (in Chinese with English). https://www.doczj.com/doc/7c2720695.html,/1000-9825/15/720.htm 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.
[51]
Harding PJ, Li QZ, Moon B. XISS/R: XML indexing and storage system using RDBMS. 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. 1073?1076.
2078
[52] [53] [54] [55]
Journal of Software 软件学报 2005,16(12)
Silberstein A, He H, Yi K, Yang J. BOXes: Efficient maintenance of order-based labeling for dynamic XML data. In: Stephanie Kawada, ed. Proc. of the 21st Int’l Conf. on Data Engineering (ICDE). Tokyo: IEEE Computer Society, 2005. 285?296. Kratky M, Pokorny J, Snasel V. Indexing XML data with UB-trees. In: Manolopoulos Y, Návrat P, eds. Proc. of the 6th East European Conf. on Databases and Information Systems (ADBIS). Bratislava: Springer-Verlag, 2002. 155?164. Rao P, Moon B. PRIX: Indexing and querying XML using prüfer sequence. In: Titsworth F, ed. Proc. of the 20th Int’l Conf. on Database Engineering (ICDE). Boston: IEEE Computer Society, 2004. 288?300. Wang HX, Park S, Fan W, Yu PS. ViST: A dynamic index method for querying XML data by tree structure. In: Halevy AY, Ives ZG, Doan A, eds. Proc. of the 2003 ACM SIGMOD Intl. Conf. on Management of Data (SIGMOD). San Diego: ACM Press, 2003. 110?121.
[56] [57]
Bayer R. XML Databases: Modeling and multidimensional indexing. Invited talk at DEXA Conf. München, 2001. http://link.springer.de/link/service/series/0558/bibs/2113/21130001.htm Jiang HF, Lu HJ, Wang W, Yu JX. Path materialization revisited: An efficient storage model for XML data. In: Zhou XF, ed. Proc. of the 13th Australasian Database Conf. on Database Technologies 2002 (ADC). Melbourne: Australian Computer Society, 2002. 85?94.
[58] [59] [60] [61]
Wang HX, Meng XF. On the sequencing of tree structures for XML indexing. In: Stephanie Kawada, ed. Proc. of the 21st Int’l Conf. on Data Engineering (ICDE). Tokyo: IEEE Computer Society, 2005. 372?383. Yoshikawa M, Amagasa T. XRel: A path-based approach to storage and retrieval of XML documents using relational databases. ACM Trans. on Internet Technology, 2001,1(1):110?141. 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. Goldman R, Widom J. Dataguides: Enabling query formulation and optimization in semistructured databases. In: Jarke M, Carey MJ, Dittrich KR, Lochovsky FH, Loucopoulos P, Jeusfeld MA, eds. Proc. of the 23rd Int’l Conf. on Very Large Data Bases (VLDB). Athens: Morgan Kaufmann, 1997. 436?445.
[62] [63]
Milo T, Suciu D. Index structures for path expressions. In: Beeri C, Buneman P, eds. Proc. of the 1999 Int’l Conf. on Database Theory (ICDT). LNCS 1540, Jerusalem: Springer-Verlag, 1999. 277?295. Kaushik R, Sheony P, Bohannon P, Gudes E. Exploiting local similarity for efficient indexing of paths in graph structured data. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int’l Conf. on Data Engineering (ICDE). San Jose: IEEE Computer Society, 2002. 129?140.
[64] [65] [66] [67] [68] [69]
Chung C, Min J, Shim K. APEX: An adaptive path index for XML data. 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. 121?132. Kaushik R, Bohannon P, Naughton JF, Korth HF. Covering indexes for branching path queries. 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. 133?144. Polyzotis N, Garofalakis M. Statistical synopses for graph-structured XML databases. 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. 358?369. Chen Q, Lim A, Ong KW. D(k)-index: An adaptive structural summary for graph-structured data. 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. 134?144. He H, Yang J. Multiresolution indexing of XML for frequent queries. In: Titsworth F, ed. Proc. of the 20th Int’l Conf. on Data Engineering (ICDE). Boston: IEEE Computer Society, 2004. 683?694. 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, Kersten ML, Larson P, Ooi BC. eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases (VLDB). Trondheim: ACM Press, 2005. 145?156.
[70] [71]
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 2001). Atlanta: ACM Press, 2001. 175?182. 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.
孔令波 等:XML 数据索引技术
[72]
2079
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.
[73] [74] [75]
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. 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. 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.
[76]
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.
[77] [78] [79]
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. Xu Y, Papakonstantinou Y. Efficient keyword search for smallest LCAs in XML databases. In: Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). Baltimore: ACM Press, 2005. 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.
[80]
Kane B, Su H, Rundensteiner EA. Consistently updating XML documents using incremental constraint check queries. In: Chiang RHL, Lim EP, eds. Proc. of the 4th ACM CIKM Int’l Workshop on Web Information and Data Management (WIDM). McLean: ACM Press, 2002. 1?8.
[81] [82]
Bouchou B, Halfeld M, Alves F. Updates and incremental validation of XML documents. In: Lausen G, Suciu D, eds. Proc. of the 9th Int’l Conf. on Data Base Programming Languages (DBLP). LNCS 2921, Potsdam: Springer-Verlag, 2003. 216?232. Thompson H. xsv: Schema validator. 2002. https://www.doczj.com/doc/7c2720695.html,/2001/03/webdata/xsv
附中文参考文献:
[1] [49] 孟小峰,周龙骥,王珊.数据库技术发展趋势.软件学报,2004,15(12):1822?1836. https://www.doczj.com/doc/7c2720695.html,/1000-9825/15/1822.htm 王静,孟小峰,王珊.基于区域划分的 XML 结构连接.软件学报,2004,15(5):720?729. https://www.doczj.com/doc/7c2720695.html,/1000-9825/15/720.htm
索引的是一种功能 索引是个既稳定又开放的信息结构，它有十一种功能。 1 分解功能 把文献中的资料单元(如篇名、机构、短语、概念、物名、地名、书名、人名、字词、符号等)一一分解，这就是索引的分解功能。它是索引工作的起跑线和索引编纂的基础，没有对文献内容的这种分解功能，就没有索引。 过去有些反对索引的人说，索引是把古人的著书“凌迟碎割”。他们对索引法的反对，实出于对流传已久的那种落后的皓首穷经的陋习的偏爱和对新的治学方法的无知，洪业曾鄙视他们为卧于涸辙的鲋鱼，以升斗之水济命，而不知西江水之可羡。虽然如此，但他们所谓的索引是把古人著书“凌迟碎割”的形象说法，却从反面十分正确地道破了索引的分解功能。 分解功能是索引作用于文献的特殊功能，是它和其他检索工作不同之处。 2 梳理功能 每种文献都包容着许多不同性质的资料单元，它们在文献中基本呈无序的状态。把这些无序状态的资料单元按外表特征或内容性质进行各归其类的整理，这就是索引的梳理功能。章学诚早就发现了这种功能，他在给《族孙守一论史表》信中要求其在治二十四史年表时一并把廿二史列传中的人名编成索引，两者互为经纬，这样便可使考古之士，于纷如乱丝之资料中，忽得梳通栉理。 梳理功能是索引分解的后继。如果只有分解功能而没有梳理的功能，那么分解功能就没有价值。 梳理是对资料单元的初分。如是字序，只要按笔划或音序归类即可；如是类序只要按大类归纳即可。就像小姑娘梳头，先把长发梳顺，而编什么辫子或梳什么发型则是下一步的要求了。 3 组合功能 把梳理后的资料单元按照分类的要求，严密地组织它们的类别层次以及类目下的专题和同类目下款目的序列关系；或按字序的要求，严密地把标目的结构正装或倒装、考虑限定词对标目的限定和修饰的级数、或考虑字序和类序相结合的可能。此外，不论是类序或字序都要考虑参照系统的建立方案，使相关款目形成网络，使用户检索的眼界得以拓宽。这些，都是索引的组合功能。 过去，国外的同行曾把圣经的页边索引以“串珠”命名；我国有人曾把本草的方剂编成索引，以“针线”命名，“串珠”和“针线”是索引组合功能很形象的描绘。它使文献资料单元成为一串串的明珠，成为被针线贯穿起来的资料单元的珍品。 4 结网功能 对某个领域的文献进行有计划的索引编纂，利用类型的结构从各种不同的角度和层次对这些文献的内容进行纵横交错和多维的揭示和组合，使之形成一个检索这些文献中的各种不同性质的资料单元的网络。这就是索引的结网功能。 由“主表”和“词族索引”、“范畴索引”、“英汉对照索引”等所组成的《汉语主题词表》是由几种不同性质的索引构建的一个主题词间的联系、辨析主题词词义和被标引的文献主题概念是否精确的一个隐含的语义网络，它对文献中的资料单元产生族性检索和扩大检索途径的作用。这个网络的结构和作用就是运用索引结网功能的一个范例。
分布式数据库的索引技术研究 摘要:索引是分布式数据库中的一个重要对象。通过对分布式数据库中的索引管理技术的分析,论述了分布式数据库中索引的概念、特点、分类及使用原则等。分析了分布式数据库设计中的统一索引服务。在文章的最后部分给出了创建合理索引的一些建议。 关键词:分布式数据库索引检索 1索引的概念 索引是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标志这些值的数据页的逻辑指针清单。表的存储由两部分组成,一部分用来存放数据页面,另一部分存放索引页面。 2索引的创建 2.1 索引的创建 创建索引有多种方法,这些方法包括直接创建索引的方法和间接创建索引的方法。直接创建索引,例如使用CREATE INDEX语句或者使用创建索引向导,间接创建索引,例如在表中定义主键约束或者唯一性键约束时,同时也创建了索引。虽然,这两种方法都可以创建索引,但是,它们创建索引的具体内容是有区别的。 使用CREATE INDEX语句或者使用创建索引向导来创建索引,这是最基本的索引创建方式,并且可以定制创建出符合自己需要的索引。在使用这种方式创建索引时,可以使用许多选项,例如指定数据页的充满度、进行排序、整理统计信息等,这样可以优化索引。使用这种方法,可以指定索引的类型、唯一性和复合性,也就是说,既可以创建聚簇索引,也可以创建非聚簇索引,既可以在一个列上创建索引,也可以在两个或者两个以上的列上创建索引。 通过定义主键约束或者唯一性键约束,也可以间接创建索引。主键约束是一种保持数据完整性的逻辑,它限制表中的记录有相同的主键记录。在创建主键约束时,系统自动创建了一个唯一性的聚簇索引。虽然,在逻辑上,主键约束是一种重要的结构,但是,在物理结构上与主键约束相对应的结构是唯一性的聚簇索引。换句话说,在物理实现上,不存在主键约束,而只存在唯一性的聚簇索引。同样,在创建唯一性键约束时,也同时创建了索引,这种索引则是唯一性的非聚簇索引。因此当使用约束创建索引时,索引的类型和特征基本上都已经确定了,由用户定制的余地比较小。 3分布式数据库设计中的统一索引服务
龙源期刊网 https://www.doczj.com/doc/7c2720695.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）丰富的编程接口工具，为用户进行程序设计提供更多选择余地。
本文介绍了数据库索引，及其优、缺点。针对MySQL索引的特点、应用进行了详细的描述。分析了如何避免MySQL无法使用，如何使用EXPLAIN分析查询语句，如何优化MySQL索引的应用。 索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它 们包含着对数据表里所有记录的引用指针。 注：[1]索引不是万能的！索引可以加快数据检索操作，但会使数据修改操作变慢。每修改数据记录，索引就必须刷新一次。为了在某种程序上弥补这一缺陷，许多SQL命令都有一个DELAY_KEY_WRITE项。这个选项的作用是暂时制止MySQL 在该命令每插入一条新记录和每修改一条现有之后立刻对索引进行刷新，对索引的刷新将等到全部记录插入/修改完毕之后再进行。在需要把许多新记录插入某个数据表的场合，DELAY_KEY_WRITE 选项的作用将非常明显。[2]另外，索引还会在硬盘上占用相当大的空间。因此应该只为最经常查询和最经常排序的数据列建立索引。注意，如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。 从理论上讲，完全可以为数据表里的每个字段分别建一个索引，但MySQL把同一个数据表里的索引总数限制为16个。 1. InnoDB数据表的索引 与MyISAM数据表相比，索引对InnoDB数据的重要性要大得多。在InnoDB数据表上，索引对InnoDB数据表的重要性要在得多。在InnoDB数据表上，索引不仅会在搜索数据记录时发挥作用，还是数据行级锁定机制的苊、基础。"数据行级锁定"的意思是指在事务操作的执行过程中锁定正在被处理的个别记录，不让其他用户进行访问。这种锁定将影响到(但不限于)SELECT...LOCK IN SHARE MODE、SELECT...FOR UPDATE命令以及INSERT、UPDATE和DELETE命令。 出于效率方面的考虑，InnoDB数据表的数据行级锁定实际发生在它们的索引上，而不是数据表自身上。显然，数据行级锁定机制只有在有关的数据表有一个合适的索引可供锁定的时候才能发挥效力。 2. 限制 如果WEHERE子句的查询条件里有不等号(WHERE coloum != ...)，MySQL将无法使用索引。 类似地，如果WHERE子句的查询条件里使用了函数(WHERE DAY(column) = ...)，MySQL也将无法使用索引。 在JOIN操作中(需要从多个数据表提取数据时)，MySQL只有在主键和外键的数 据类型相同时才能使用索引。
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的格网技术和空间目标排序法。
索引方法： 网格索引——点要素（图元），线、面要素，有冗余 四叉树索引——线、面要素，有冗余 改进的四叉树索引——线、面要素 R树——空间重叠 一、网格索引，四叉树索引 在介绍空间索引之前,先谈谈什么叫“索引“。对一个数据集做”索引“,是为了提高对这个数据集检索的效率。书的”目录“就是这本书内容的”索引“,当我们拿到一本新书,想查看感兴趣内容的时候,我们会先查看目录,确定感兴趣的内容会在哪些页里,直接翻到那些页,就OK了,而不是从第一章节开始翻,一个字一个字地找我们感兴趣的内容,直到找到为止,这种检索内容的效率也太低了,如果一本书没有目录,可以想象有多么不方便…可见书的目录有多重要,索引有多重要啊！ 现在大家对索引有了感性认识,那什么是“空间索引“呢？”空间索引“也是”索引“,是对空间图形集合做的一个”目录“,提高在这个图形集合中查找某个图形对象的效率。比如说,我们在一个地图图层上进行矩形选择,确定这个图层上哪些图元被这个矩形所完全包含呢,在没有”空间索引“的情况下,我们会把这个图层上的所有图元,一一拿来与这个矩形进行几何上的包含判断,以确定到底哪些图元被完全包含在这个矩形内。您是不是觉得这样做很合理呢？其实不然,我们先看一个网格索引的例子：
我们对这个点图层作了网格索引,判断哪些点在这个矩形选择框内,是不需要把这个图层里所有的点都要与矩形进行几何包含运算的,只对 a,b,c,d,e,f,g这七个点做了运算。可以推想一下,如果一个点图层有十万个点,不建立空间索引,任何地图操作都将对整个图层的所有图元遍历一次,也就是要For循环10万次；建立索引将使得For循环的次数下降很多很多,效率自然提高很多！ 呵呵…想必大家都知道空间索引的好处了,也不知不觉向大家介绍了点图层的网格索引,还有哪些常用的空间索引呢？这些空间索引又该如何实现呢？带着这样的问题,下面介绍几种常用的空间索引。 网格索引 网格索引就是在一个地图图层上,按每个小网格宽△w,高△h打上均匀的格网,计算每个图元所占据的网格或者所经过的网格单元集合,
实验三：索引的创建与使用 一、实验目的： 1、理解索引的概念和索引的作用。 2、掌握创建索引的方法。 3、学会使用索引。 4、了解聚簇索引和非聚簇索引。 二、实验要求：（必做） 硬件：Intel Pentium 120或以上级别的CPU，大于16MB的内存。 软件：Windows 95/98/2000操作系统，关系数据库管理系统SQL SERVER 2000。 学时：2学时 三、实验内容： 1、用create index在学生表student的学号sno上建立聚簇索引。 2、在学生表student中，为姓名sname建立非聚簇索引。 3、在课程表的课程号Cno上建立唯一索引。 4、在选课表的学号sno、成绩Grade上建立复合索引，要求学号为升序，学号相同时 成绩为降序。 5、用drop删除学生表student的索引。 数据库设计与管理实验报告
实验名称评分 实验日期年月日指导教师 姓名专业班级学号 一、实验目的 二、实验步骤及结果 1、用create index在学生表student的学号sno上建立聚簇索引。 create clustered index stusno on student(sno); 2、在学生表student中，为姓名sname建立非聚簇索引。 create index stusname on student(sname); 3、在课程表的课程号Cno上建立唯一索引。 create unique index coucno on course(cno); 4、在选课表的学号sno、成绩Grade上建立复合索引，要求学号为升序，学号相同时成绩为降序。
GIS空间数据库文献综述 姓名：张磊 摘要：通过分析地理信息系统建设过程中空间数据库的建设内容1 综述空间数据块的划分、图层的分层设计方法、专题图层划分和数据集设计、分析空间数据库的结构,讨论了空间数据库系统建设的方法和需解决的关键技术问题。 关键字：GIS；空间数据库 引言：地理信息系统是集计算机科学、空间科学、信息科学、测绘遥感科学、环境科学等学科于一体的新兴边缘科学1GIS 从20 世纪60 年代出现以来,至今只有短短的40 多年时间,但已成为已成为多学科集成并应用于各领域的基础平台,成为地学空间信息分析的基本手段和工具。目前,地理信息系统不仅发展成为一门较为成熟的技术科学,而且已成为一门新兴产业,在测绘、地质、水利、环境检测、土地管理、城市规划、国防建设等领域发挥越来越重要的作用。目前，国际上在此领域进行深入研究并形成软件产品的有目前，国际上在该领域进行过深入研究并形成软件产品的有：ESRIArcSDE1,MapInfo Spatial Ware2以及Oracle Spatial 3,DB2 Spatial Extender4和Informix Spatial Data Blade 等。 1 . 空间数据库的设计 1.1空间数据库的设计思路 空间数据库由图形数据库和属性数据库两部分组成, 运用地理信息系统技术分别建好图形数据库和属性数据库后, 通过统一的编码来实现滑坡的图形数据库与属性数据库的无缝连接, 最终形成完整的空间数据库5。 1.2 间数据库的主要内容 每个GIS 数据集都提供了对世界某一方面的空间表达,包括: 基于矢量的要素(点、线和多边形) 的有序集合; 诸如数字高程模型和影像的栅格数据集; 网络; 地形和其他地表; 测量数据集; 其他类型数据,诸如地址、地名和制图信息; 描述性的属性。 除了地理表现形式以外,地理数据集还包括传统的描述地理对象的属性表1 许多表和空间对象之间可以通过它们所共有的字段(也常称为“关键字”) 相互关联1 就像它们在传统数据库应用中一样,这些以表的形式存在的信息集和信息关系在GIS 数据模型中扮演着非常关键的角色。 1.3 空间数据表现形式 1.3.1空间关系:拓扑和网络 空间关系,比如拓扑和网络,也是一个GIS 数据库的重要部分1 使用拓扑是为了管理要素间的共同边界、定义和维护数据的一致性法则,以及支持拓扑查询和漫游 1胡金星.空间数据库实现及其集成技术研究[J].计算机应用研究,2003,3:12-15． 2Andrew S Tanenbaum,Albert S.Woodhull :Operating SystemDesign and Implementation[Z]. 3Forta B, Fonte P, Brewer G.Windows2000 开发人员指南[M].杜大鹏,译.北京: 中国水利水电出版 社,2001.144 ,428. 4David J Kruglinski.Visual C++6. 0 技术内幕[M].4 版.希望图书创作室.北京:北京希望电子出版 社.209-426. 5 兰恒星,吴法权,周成虎,等.基于GIS 的滑坡空间数据库研究以云南小江流域为例[ J].中国地质灾害与防治学报, 2002, 13( 4):10-16.
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
一、深入浅出理解索引结构 实际上，您可以把索引理解为一种特殊的目录。微软的sql server提供了两种索引：聚集索引（c lustered index，也称聚类索引、簇集索引）和非聚集索引（nonclustered index，也称非聚类索引、非簇集索引）。下面，我们举例来说明一下聚集索引和非聚集索引的区别： 其实，我们的汉语字典的正文本身就是一个聚集索引。比如，我们要查“安”字，就会很自然地翻开字典的前几页，因为“安”的拼音是“an”，而按照拼音排序汉字的字典是以英文字母“a”开头并以“z”结尾的，那么“安”字就自然地排在字典的前部。如果您翻完了所有以“a”开头的部分仍然找不到这个字，那么就说明您的字典中没有这个字；同样的，如果查“张”字，那您也会将您的字典翻到最后部分，因为“张”的拼音是“zhang”。也就是说，字典的正文部分本身就是一个目录，您不需要再去查其他目录来找到您需要找的内容。我们把这种正文内容本身就是一种按照一定规则排列的目录称为“聚集索引”。 如果您认识某个字，您可以快速地从自动中查到这个字。但您也可能会遇到您不认识的字，不知道它的发音，这时候，您就不能按照刚才的方法找到您要查的字，而需要去根据“偏旁部首”查到您要找的字，然后根据这个字后的页码直接翻到某页来找到您要找的字。但您结合“部首目录”和“检字表”而查到的字的排序并不是真正的正文的排序方法，比如您查“张”字，我们可以看到在查部首之后的检字表中“张”的页码是672页，检字表中“张”的上面是“驰”字，但页码却是63页，“张”的下面是“弩”字，页面是390页。很显然，这些字并不是真正的分别位于“张”字的上下方，现在您看到的连续的“驰、张、弩”三字实际上就是他们在非聚集索引中的排序，是字典正文中的字在非聚集索引中的映射。我们可以通过这种方式来找到您所需要的字，但它需要两个过程，先找到目录中的结果，然后再翻到您所需要的页码。我们把这种目录纯粹是目录，正文纯粹是正文的排序方式称为“非聚集索引”。 通过以上例子，我们可以理解到什么是“聚集索引”和“非聚集索引”。进一步引申一下，我们可以很容易的理解：每个表只能有一个聚集索引，因为目录只能按照一种方法进行排序。 二、何时使用聚集索引或非聚集索引 下面的表总结了何时使用聚集索引或非聚集索引（很重要）：
《空间数据库索引建立》实验报告 张占阳 （长安大学地测学院地理信息系统，陕西西安710054） 一、实验课时和类型： 学时：8 实验类型：综合性 二、实验目的： 1．认识空间数据库中数据的存放方式或存储结构； 2．掌握空间数据库的格网索引、标题索引的建立方法； 3．理解空间索引的功能和意义； 4．加强学生面向对象程序设计的能力。 三、适用专业： 地理信息系统专业 四、采用教材： 教材：《计算机地图制图》艾自兴，龙毅编著武汉大学出版社参考书：《地图学》祝国瑞编著武汉大学出版社五、仪器与工具： P3以上配置计算机； VC++工具软件； 实验地图数据。 六、实验原理与内容： 本次实验为综合性实验，涉及《数字地图制图原理》、《计算机地图制图原理》、《地图数据库》等几门课程中所讲的内容。
七、实验数据说明 1、地图区域：武汉市 文件名：武汉实习数据.usr 2、分类代码： 代码名称 30000 控制点 10000 图廓点 10001 铁路 10003 汽渡虚线 10004 主要道路 20001 码头 20002 铁路中转站 20003 河流、湖泊 20004 居民地 3、代码说明： 分类代码第一个字符为1，表示线目标；分类代码第二个字符为2，表示面目标。 4、控制点顺序： 第一点：左上角第二点：右上角 第三点：右下角第四点：左下角 控制点的理论值（人为规定x,y）： 第一点：12.50 37.40
第二点：62.50 37.40 第三点：62.50 82.40 采用仿射变换方法。 主要实验内容： 1．读取数据 2．仿射变换 3．绘图显示 4．建立定位索引——格网索引 5．建立定性索引——标题索引 6．将已建立的格网索引用于目标拾取功能的实现 7．运用已建立的标题索引实现对象的属性查询 八、实验步骤： 第一；建立一个MapOfWuhan （MFC）工程，参数缺省。 第二；建立地图三要素：点、线、面。点类包括对应点的X，Y坐标；线类包括线号（Xcode），线分类代码（Xflcode）以及组成线的点号数组（m_array）；面类包括面号（Mcode），面分类代码（Mflcode）以及组成面的点号数组（m_array）。 第三；在读取数据时，要设计存储结构。在Doc中要建立点类数组Array_dian，线类数组Array_xian，面类数组Array_mian，分别存放对应的点线面类目标。一共有655组数据，读取的时候每组中的X，Y 坐标存放到预先定义的点类对象中，若每组的分类代码为线类目标的分类代码，则把相应的线的分类代码存放到事先定义的线类对象的
《空间数据组织与分析》 结课论文 题目：多级空间索引算法分析 学院：研究生学院 专业：大地测量学与测量工程 班级：硕研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 加到该最小范围块所带的链表中。查询时根据用户关心的区域，选中区域所在最小范围块中的对象。四叉树的查询在最坏情况下效率较低，而且四叉树的动态性较差。建立索引后，如果又扩大地图范围增加新对象时，必须重新建立四叉树索引，因而缺乏灵活性。
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) 此种数据库加密技术对于对存储过程、触发器、函数等存储程序的实现支持也非常困难。
一、引言 对数据库索引的关注从未淡出我的们的讨论，那么数据库索引是什么样的？聚集索引与非聚集索引有什么不同？希望本文对各位同仁有一定的帮助。有不少存疑的地方，诚心希望各位不吝赐教指正，共同进步。[最近首页之争沸沸扬扬，也不知道这个放在这合适么，苦劳？功劳？……] 二、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，升级（这里是成为根结点）。其它的依类推，就是这样一个大概的过程。
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 34.ALTER TABLE table_name ADD PRIMARY KEY (column_list 35.
几种空间数据库系统的空间查询模块功能浅析 摘要：本文针对市场流行数据库Oracle和MySQL以及地理信息系统ArcGIS的空间查询模块功能进行了调研，通过研究具体功能函数，分析总结各自的优缺点并尝试性提出了其适合的应用方向及范围。 关键词：空间查询Oracle MySQL ArcGIS 引言 空间数据库是地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的。空间数据库的研究始于20 世纪70年代的地图制图与遥感图像处理领域,其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷，从而形成了空间数据库这一数据库研究领域。而传统数据库系统只针对简单对象，无法有效的支持复杂对象（如图形、图像）。随着空间数据库的诞生，空间数据查询功能应运而生。各数据库开发商针对空间数据库的特殊性，结合在实际应用中对空间数据关系的分析技术，基于数据库语言开发出了一套具备空间数据查询功能的模块。本文分别对Oracle、MySQL和ArcGIS三个产品的空间数据查询服务进行了一些调研，分析其处理函数功能与实现方法，评价其功能的优缺点，探讨了产品的应用范围与使用方法。 1Oracle数据库 Oracle数据库系统是美国ORACLE公司（甲骨文）提供的以分布式数据库为核心的一组软件产品，是目前最流行的客户/服务器(CLIENT/SERVER)或B/S体系结构的数据库之一。该数据库是目前世界上使用最为广泛的数据库管理系统，作为一个通用的数据库系统，它具有完整的数据管理功能；作为一个关系数据库，它是一个完备关系的产品；作为分布式数据库它实现了分布式处理功能。但它的所有知识，只要在一种机型上学习了Oracle知识，便能在各种类型的机器上使用它。 1.1Oracle Spatial概述 Oracle Spatial 是Oracle数据库强大的核心特性，它将所有的地理空间数据类型（矢量、栅格、网格、影像、网络、拓扑）统一在单一、开放的、基于标准的数据管理环境中，这就减少了管理单独、分离的专用系统的成本、复杂性和开销。Oracle Spatial使得我们能够在一个多用户环境中部署地理信息系统（GIS），并且与其它企业数据有机结合起来，统一部署电子商务、政务。其功能由于传统的GIS 技术已达到其本身可伸缩性的极限，用户越来越多地转向以数据库为中心的空间计算。Oracle Spatial将空间过程和操作直接转移到数据库内核中，从而提高了性能和安全性。Oracle Spatial从1995年Oracle7.1.6开始发展到2003年的10G版本，空间数据处理能力越来越强大。其在MDSYS方案下有大量的自定义数据类型，经常使用的是SDO_GEOMETRY类型,见图1。该类型表示一个几何对象，可以是点、线、