XML数据索引技术论文（共7篇）
XML数据索引技术论文 篇1
0 引 言
由于XML数据的灵活性,自描述性好及可扩展性高,成为当前主流的数据形式,并成为Internet中进行数据交换和表示的标准。 由于客观世界的复杂性,不确定性是数据常见的内在属性,因此不确定的信息是普遍存在的。通常不确定信息以概率值的形式在XML文件中表示。如何在连续不确定XML中建立索引实现快速高效的查询成为了当务之急。
索引是提高查询效率的有效途径,DataGuides[1]、1-index[2]、A(k)-index[3]、D(k)-index[4],都是其中典型的代表。但是这些索引结构有个共同的特点就是仅支持简单路径查询,不支持分支路径查询。文献[5]提出一种扁平结构索引F-index,能够快速过滤所有与查询无关的索引结点,进而过滤掉与查询无关的元素序列。在处理深度嵌套的复杂结构XML文档时具有很大的优势,但是这种索引结构仅适用于普通XML文档中的查询。文献[6]提到一种处理连续不确定数据的索引方法,这种方法通过对节点提前计算一些附加信息,在查询时通过这些信息过滤与查询无关的节点,最小化概率阈值查询中概率计算的次数。但是这种索引只适用连续不确定数据的查询处理,对于连续不确定XML文档没有实际应用。
在连续不确定XML中进行的查询,多数只需要知道取得某个值的概率是否超过了一个给定的阈值,即概率阈值查询。提出CPTI索引技术。首先扩展了结构索引F-index,建立了概率XML数据的扁平结构链表,此链表在原有的普通XML数据扁平结构链表的基础上又添加了结点状态(普通结点和分布式结点)和相应的概率信息,查询可直接在链表里进行,这种结构可快速的返回twig小枝的查询结果,并且可以确定节点的路径概率值(即从根节点到本节点的路径概率);其次建立了值索引,此索引在服从连续分布的叶子结点,记录了结点概率信息,查询时先根据此概率信息过滤掉一些与查询无关的叶子节点,减少叶子节点概率的计算。
1 CPTI索引
1.1 建立模型
一个PXML文档可表示成一棵树,记作T=(Vp,rp,Ep,tag)。其中:(1) Vp是结点的集合。(2) rp⊆Vp是树的根结点。(3) Ep是边的集合。(4) tag:VA→<name,value,valuetype>,给每个结点赋予一个三元字符串组,分别表示该结点的节点名、值和值的类型,如图1所示是包含mux和cont类节点的P-文档[7]。
1.2 CPTI结构索引
CPTI结构索引是一个链表,记录一个节点A和它的所有tag为B的后代节点的情况,链表结构如图2所示。图2(a)是链表表头,其中PC表示父子关系,AD表示祖先子孙关系,图2(b)为链表元素,此链表是在结构索引F-index链表元素的基础上增加了三个元素,Flag表示后代结点的类型,包含F、Fi、和Fm,F表示普通节点,Fi表示独立节点,Fm表示互斥节点;P表示后代节点的路径概率值,即从根节点到该节点的路径概率;CurrentNode表示对应的后代结点。
记录图1中所有非叶节点和它后代的可达性信息,建立了如图3所示的CPTI结构索引。其中Mo表示monitoring、Si表示sensori、Ms表示measures、Ti表示tempi。
1.3 CPTI值索引
1.3.1 正态分布的概念及特征
若连续型随机变量X的概率密度为
1.3.2 值索引
值索引是一个二维表结构,记录cont类节点概率值和对应区间关系的信息表,值索引结构如图5所示,P表示用户给定的概率值,0<P<1;|x2-x1|表示图4中关于X=μ对称的、概率为P的最短区间长度;xL、xR含义与图4中xL和xR含义相同。查询时,可根据此表信息过滤与查询无关的元素以减少处理元素的数目。
图1中叶子结点T服从正态分布N(μ,δ2),根据T的实际分布情况,计算得到一些信息,构成一个信息表,例如T2结点,设初值0.1,步长0.1,确定P值,并计算得到图6所示值索引。
图6 CPTI值索引实例
2 基于CPTI索引的查询处理过程
例如查询图1中温度在(28,31)范围内的概率P大于0.6的传感器s,如图7所示。使用CPTI结构索引查询图7中的Twig,利用CPTI值索引过滤不满足Temp在(28,31)的概率大于0.6这一条件的Twig。
2.1 CPTI结构索引查询Twig
CPTI结构索引查询步骤:
(1) 通过CPTI结构索引找到S-id的PC指针和S-T的AD指针,两指针同时推进,比较两个指针所指链表中AncestorNode是否相同,如果相同,则找到符合条件的小枝。如果不同,则继续推进,直到PC或AD为空。
(2) 根据链表元素P确定T的节点类型和路径概率。如果T的路径概率低于查询概率阈值将被过滤掉,否则保留。
根据以上策略,最终找到如图8所示三个小枝。
2.2 CPTI值索引过滤Twig
CPTI值索引过滤步骤:
(1) (a,b)是概率阈值查询的查询区间,P,x1,x2,xL,xR含义和图4中表示的含义相同,查询的概率为Pi=阈值概率/路径概率。本例中a=28,b=31,Pt=0.6/(T的路径概率)。
(2) 当
(3) 当
(4) 其余情况均利用pdf进行计算。
根据以上过滤策略,只有T4符合条件。所以符合图7查询的只有S3[/id3]//T4。
3 实验分析
3.1 实验环境和数据集
本实验是在Dell Optiplex 380(2.93GHz),RAM 2GB,300G硬盘上运行,OS是Windows XP Professional SP-3。实验测试采用人工合成数据集。
3.2 测试及结果分析
本实验进行了两组测试。第一组测试中,数据集如表1所示,P文档逐渐增大,分别测试了没有索引存在、只有结构索引存在、结构索引和值索引都存在时的运行时间。结果如图9所示,从图中可以看出通过索引进行查询,查询时间大幅度地减少,并且发现,通过CPTI结构索引处理查询时,P文档越大,时间变化幅度越小,效率越高。
第二组测试中,P文档不变,44MB,只改变查询的概率值(P1～P9分别是0.1～0.9,步长0.1),测试了运行时间,如图10所示,从图中可以看出,概率值越大,运行时间越短,即概率值越大,通过CPTI索引查询的效率越高。
4 结 语
本文在已有XML索引方法的基础上提出了CPTI索引结构,可以实现连续不确定XML的概率阈值查询,使用CPTI结构索引加速了Twig查询,通过CPTI值索引过滤Twig,进一步减少了查询时间。实验表明,效率较高。进一步的工作是对叶子节点服从任意分布的情况进行研究。
参考文献
[1]Goldman R,Widom J.DataGuides:Enabling query formulation andop-timization in semistructured databases[C]//Proc.of the 23rdInt'1Conf.on Very Large Data Bases(VLDB),Athens:Morgan Kaufman-nPublishers,1997:436-445.
[2]Milo T,Suciu D.Index structures for path expressions[C]//Proc.ofthe 7th Int'1 Conf.on Database Theory(ICDT),LNCS 1540,Jerusa-lem:Springer-Verlag,1999:277-295.
[3]Kaushik R,Sheony P,Bohannon P,et al.Exploiting localsimilarity forefficient indexing of paths in graph structured data[C]//Proc.of the18th Int'1Conf.on Data Engineering(ICDE),San Jose:IEEE Comput-er Society,2002:129-140.
[4]Chen Q,Lim A,Ong K W.D(k)-index:An adaptive structuralsummaryfor graph-structured data[C]//Proc.of the 2003 ACMSIGMOD Int'1Confon Management of Data(SIGMOD),San Diego:ACM Press,2003:134-144.
[5]He H,Yang J.Multiresolution indexing of XML for frequentqueries[C]//Proc.of the 20th Int'1 Conf.on Data engineering(ICDE),Bos-ton,IEEE Computer Society,2004:683-694.
[6]周军锋,孟小峰,蒋瑜,等.F-index:一种加速Twig查询处理的扁平结构索引[J].软件学报,2007,18(6):1429-1442.
[7]Kimelfeld B,Sagiv Y.Matching twigs in probabilistic XML[C]//VLDB'07,Vienna,Austria,2007.
XML数据索引技术论文 篇2
就是这么一个结构极其简单的表，200万数量级的复杂查询将会变的非常缓慢，比如执行下面的SQL语句。
SELECT a.id,FROM_UNIXTIME(a.time)
FROM article AS a
WHERE a.title=‘PHP笔试题和答案――基础语言方面’
查询时间基本上需要50-100秒，这个是非常恐怖的，如果加上联合查询和其他一些约束条件，数据库会疯狂的消耗内存。
如果这时候数据库里面针对title字段建立了索引，查询效率将会大幅度提升，如下图所示。可见对于大型数据库，建立索引是非常非常重要的一个优化手段(当然还会有很多其他优化这样的数据库的方法，但是本文主题所限，暂不讨论。)，废话了这么多，以下开始总结MySQL中索引的使用方法和性能优化以及一些注意事项。
索引的概念
索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。上述SQL语句，在没有索引的情况下，数据库会遍历全部200条数据后选择符合条件的;而有了相应的索引之后，数据库会直接在索引中查找符合条件的选项。如果我们把SQL语句换成“SELECT * FROM article WHERE id=000”，那么你是希望数据库按照顺序读取完200万行数据以后给你结果还是直接在索引中定位呢?上面的两个图片鲜明的用时对比已经给出了答案(注：一般数据库默认都会为主键生成索引)。
索引分为聚簇索引和非聚簇索引两种，聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了;聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快。
索引的类型
1. 普通索引
这是最基本的索引，它没有任何限制，比如上文中为title字段创建的索引就是一个普通索引。
C直接创建索引
CREATE INDEX indexName ON table(column(length))
C修改表结构的方式添加索引
ALTER tableADD INDEX indexName ON (column(length))
C创建表的时候同时创建索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` 255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL ,
`content` text CHARACTER SET utf8 COLLATE utf8_general_ci NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
INDEX indexName (title(length))
)
C删除索引
DROP INDEX indexName ON table
2. 唯一索引
与普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值(注意和主键不同)。如果是组合索引，则列值的组合必须唯一，创建方法和普通索引类似。
C创建唯一索引
CREATE UNIQUE INDEX indexName ON table(column(length))
C修改表结构
ALTER table ADD UNIQUE indexName ON (column(length))
C创建表的时候直接指定
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` 255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL ,
`content` text CHARACTER SET utf8 COLLATE utf8_general_ci NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
UNIQUE indexName (title(length))
);
3. 全文索引(FULLTEXT)
MySQL从3.23.23版开始支持全文索引和全文检索，FULLTEXT索引仅可用于 MyISAM 表;他们可以从CHAR、VARCHAR或TEXT列中作为CREATE TABLE语句的一部分被创建，或是随后使用ALTER TABLE 或CREATE INDEX被添加。////对于较大的数据集，将你的资料输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把资料输入现有FULLTEXT索引的速度更为快。不过切记对于大容量的数据表，生成全文索引是一个非常消耗时间非常消耗硬盘空间的做法。
C创建表的适合添加全文索引
CREATE TABLE `table` (
`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` 255) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL ,
`content` text CHARACTER SET utf8 COLLATE utf8_general_ci NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
FULLTEXT (content)
);
C修改表结构添加全文索引
ALTER TABLE article ADD FULLTEXT index_content(content)
C直接创建索引
CREATE FULLTEXT INDEX index_content ON article(content)
4. 单列索引、多列索引
多个单列索引与单个多列索引的查询效果不同，因为执行查询时，MySQL只能使用一个索引，会从多个索引中选择一个限制最为严格的索引。
5. 组合索引(最左前缀)
平时用的SQL查询语句一般都有比较多的限制条件，所以为了进一步榨取MySQL的效率，就要考虑建立组合索引。例如上表中针对title和time建立一个组合索引：ALTER TABLE article ADD INDEX index_titme_time (title(50),time(10))。建立这样的组合索引，其实是相当于分别建立了下面两组组合索引：
Ctitle,time
Ctitle
为什么没有time这样的组合索引呢?这是因为MySQL组合索引“最左前缀”的结果。简单的理解就是只从最左面的开始组合。并不是只要包含这两列的查询都会用到该组合索引，如下面的几个SQL所示：
C使用到上面的索引
SELECT * FROM article WHREE title=“PHP程序员” AND time=1234567890
SELECT * FROM article WHREE utitle=“PHP程序员”
C不使用上面的索引
SELECT * FROM article WHREE time=1234567890
MySQL索引的优化
上面都在说使用索引的好处，但过多的使用索引将会造成滥用。因此索引也会有它的缺点：虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件。建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重，但如果你在一个大表上创建了多种组合索引，索引文件的会膨胀很快。索引只是提高效率的一个因素，如果你的MySQL有大数据量的表，就需要花时间研究建立最优秀的索引，或优化查询语句。下面是一些总结以及收藏的MySQL索引的注意事项和优化方法。
1. 何时使用聚集索引或非聚集索引?
动作描述 使用聚集索引 使用非聚集索引 列经常被分组排序 使用 使用 返回某范围内的数据 使用 不使用 一个或极少不同值 不使用 不使用 小数目的不同值 使用 不使用 大数目的不同值 不使用 使用 频繁更新的列 不使用 使用 外键列 使用 使用 主键列 使用 使用 频繁修改索引列 不使用 使用
事实上，我们可以通过前面聚集索引和非聚集索引的定义的例子来理解上表。如：返回某范围内的数据一项。比如您的某个表有一个时间列，恰好您把聚合索引建立在了该列，这时您查询1月1日至月1日之间的全部数据时，这个速度就将是很快的，因为您的这本字典正文是按日期进行排序的，聚类索引只需要找到要检索的所有数据中的开头和结尾数据即可;而不像非聚集索引，必须先查到目录中查到每一项数据对应的页码，然后再根据页码查到具体内容。其实这个具体用法我还不是很理解，只能等待后期的项目开发中慢慢学学了。
2. 索引不会包含有NULL值的列
只要列中包含有NULL值都将不会被包含在索引中，复合索引中只要有一列含有NULL值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为NULL。
3. 使用短索引
对串列进行索引，如果可能应该指定一个前缀长度。例如，如果有一个CHAR(255)的列，如果在前10个或20个字符内，多数值是惟一的，那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。
4. 索引列排序
MySQL查询只使用一个索引，因此如果where子句中已经使用了索引的话，那么order by中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作;尽量不要包含多个列的排序，如果需要最好给这些列创建复合索引。
5. like语句操作
一般情况下不鼓励使用like操作，如果非使用不可，如何使用也是一个问题。like “%aaa%” 不会使用索引而like “aaa%”可以使用索引。
6. 不要在列上进行运算
例如：select * from users where YEAR(adddate)<，将在每个行上进行运算，这将导致索引失效而进行全表扫描，因此我们可以改成：select * from users where adddate<’2007-01-01′。关于这一点可以围观：一个单引号引发的MYSQL性能损失。
最后总结一下，MySQL只对一下操作符才使用索引：<,<=,=,>,>=,between,in,以及某些时候的like(不以通配符%或_开头的情形)。而理论上每张表里面最多可创建16个索引，不过除非是数据量真的很多，否则过多的使用索引也不是那么好玩的，比如我刚才针对text类型的字段创建索引的时候，系统差点就卡死了。
最后的最后PS：现在更新个技术文章真难，还得做大量实验…
XML数据索引技术论文 篇3
随着互联网的迅速发展,可扩展标记语言XML由于其良好的数据格式、丰富的数据表示能力及验证机制,已经成为Web中数据表示和交换的标准。XML在Web中广泛应用使得XML文档的结构变得越来越复杂和数据量越来越大,导航式的遍历显然已经不能满足查询所需的要求,对XML文档节点编码并建立索引可以快速有效地定位出需要访问的节点[1],提高XML数据访问的查询效率。因此对XML数据建立索引是一个必要的手段,也成为了当前XML查询中研究的热点问题。
对XML文档建立索引,就是将具有相同标签的XML节点划分在同属一个索引节点类中[2]。目前,国内外对XML建立索引技术的研究取得了丰富的研究成果。例如,最早提出对XML文档建立索引的思想来源于文献[3]提出的基于结构概要的Data Guide索引方法,它的本质是一个确定自动机,能够根据绝对路径很好地给出响应查询,但却不能提供相对路径的查询。文献[4]提出带有分支路径查询的F&B索引,它可以快速地查询出带有分支路径的查询,但是F&B在构建索引时消耗的内存资源过大。文献[5,6]提出的基于元素、属性和结构的XISS索引,它将一个复杂的路径表达式分解成若干个简单路径,通过对XISS索引的访问来处理每个简单路径的查询处理得到满足结构关系的中间结果,最后对这些中间结果依次进行结构连接得到查询的最终的结果。但该方法对具有N个元素或者属性组成的路径查询表达式,XISS索引需要从XML文档中访问N组节点,并且至少需要N - 1 次结果的结构连接,因此会增加结构连接运算的时间。文献[7 - 9]都是基于DTD的XML索引方法DBXI,该方法能够很好地将DTD的结构信息保存到XML文档中元素和属性中,并且能够快速地访问到结果集。但该方法对XML文档使用区间编码的方法,这种编码对于分解后的简单路径查询存在着很多不相关的结果和结构连接运算相对复杂,并且对于DTD自身也存在着很多的缺陷性。文献[10,11]提出了基于Schema的SBXI索引方法,但这些方法中对XML文档也是使用区间编码的方法。
为了避免上述方法中存在的缺点,本文提出了一种基于XML Schema混合编码的索引方法SBXHCI,其优点在于: 通过使用Schema,避免了DTD本身的多种缺陷; 把Schema中的信息存入相应的XML文档中,可以快速地去除了不相关节点的访问,有效地减少结构连接次数,并能确保所有待查询节点都能被访问; 根据前缀编码和区间编码各自的优点,对XML文档采用混合编码建立索引结构,这种编码方法可以快速地查询出待查询的节点和加快了结构连接的速度,从而提高查询效率和准确率。
1 XML文档和模式
1. 1 XML文档模型
定义1 XML文档树: 一个XML文档T可以表示成一颗带有标签的有序树( V,E,Label,Root) 。其中V表示文档中节点的有限集合,V = element∪attribut,element和attribute分别代表文档中的元素节点和属性节点; Root是文档树T中的根节点Root∈V; E = V × V是文档中有向边的集合; Label是文档中V到V的集合,既文档树中每个节点分别指明一个标签作为节点标识。下面给出了一个关于书架的XML文档简略片段,图1 给出了对应的文档树的模型,其中椭圆形代表节点,三角形代表属性,矩形代表文本。
从图1 中可以看出文档的根节点为bookshelf,它的子节点是由book元素组成,每个book节点都有一个属性id; 节点集合及其边对应的关系都可以很容易从文档书中看出。
1. 2 XML模式
模式定义语言使XML文档遵循一定规则,可以有效地描述和确定出文档的特性,从而得到一个良构的XML文档。它不仅规定了XML文档中可以使用的元素和元素的数据类型,而且还定义了文档中元素出现的顺序和次数以及其节点的嵌套关系等。目前比较广泛使用的是DTD和XML Schema模型。
DTD使用一种特殊的语法来表示XML文档中的元素和属性,如< ! ELEMENT bookshelf ( book + ) > 表示bookshelf元素包含一个或者多个book元素,< ! ATTLIST book id ID #REQUIRED > 表示book元素的属性id是必须且只能出现一次。而Schema使用一种与XML文档相同的语法来定义XML文档的元素,如使用< element name = ″bookshelf″ > 和< attribute name= ″id″ type = ″string″ use = ″required″ / > 来表示元素和属性。因此使用DTD模式比使用Schema模式来判断一个XML文档是否有效,必然会增加解析的时间开销。并且DTD相对于Schema还有着其他的缺点: DTD只提供字符串类型的数据,而Schema中提供了丰富的数据类型并且可以自定义数据类型,具有很好的可扩展性; DTD提供的约束限制仅有? ( 零或一个) 、* ( 零或多个) 和+ ( 一个或多个) 三种,而Schema还可以提供范围限制等。因此本文采用Schema模式限制约束XML文档并对XML建立索引。
定义2 Schema摘要树: 对于一个Schema文档可以映射成一个文档摘要树( V,children) ( 本文不考虑Schema结构中存在环的情况) ,其中V表示文档中标签生成的节点集合,children表示一个元素映射到子元素上的映射集合。
2 基于Schema索引的关键技术
2. 1 文档编码和索引结构
目前对XML文档常用的编码方法有基于区间编码[12,13]和基于前缀编码[14]: 区间编码是对XML文档中的每个节点赋予一对整数值,父节点的编码区间包含其子节点和后代的编码区间; 前缀编码是保存了XML文档节点的路径信息,任何父节点的编码都是其子节点和后代节点编码的前缀。本文充分利用两种编码的特点,分别对XML文档和Schema文档分别进行编码。
Schema编码: 把Schema映射成一个摘要树,节点n的编码用( Code( n ) ,Level( n ) ,E/A) 标识,其中Code( n) 表示节点n的前缀编码,Level( n) 表示节点n在摘要树中的层数,E/A表示节点是元素节点还是属性节点。
定理1 给定一个有效的XML文档树T采用区间编码,则对T中任意两个节点m和n,若m是n的祖先节点的充分必要条件为Precode( m ) ·Order( m ) 是Precode( n ) ·Order( n ) 的一个前缀,其中Precode ( m) 表示节点m的前缀编码,Oeder( m) 表示节点m的顺序码。
通过对Schema编码采用倒排索引建立一个Schema索引结构,在倒排索引中把关键词存储在一个索引文件中,使用指针链表指向关键词相关的文档,从而有效的完成倒排索引列表。如图2 所示,本文把具有相同元素/属性的节点归并到一个索引中,这样可以通过在Schema索引中快速的访问指定元素/属性节点。
XML编码: XML文档采用混合编码,每个节点的编码都包含前缀编码和区间编码信息。节点n编码为( Start( n ) ,End( n ) ,S_Code( n ) ) 。其中Start( n ) 和End( n ) 分别表示节点n的前序遍历和后续遍历值,S_Code( n ) 是节点n所对应的元素或者属性在Schema文档树中具有相同路径相同位置的节点前缀编码Code( n ) ,Level( n) 表示节点n在XML文档树中的层数。因此,XML文档将Schema的前缀编码信息存入节点,通过使用S_Code( n ) 使得每个节点都包含了相应的Schema中的结构信息,这使得在SBXHCI可以直接判断出无效的路径表达式中,并且在结构连接运算中提供精确的定位和减少结构连接的次数。
定理2 给定一个有效的XML文档树T采用区间编码,则对T中任意两个节点m和n,若m是n的祖先节点的充分必要条件为Start( m ) < Start( n ) 且End( n ) < End( m ) 。若m是n的父节点充分必要条件是m是n的祖先节点且Level( m ) + 1 =Level( n ) 。
根据Schema索引可以建立一个XML文档索引结构,如图3所示。首先根据Schema摘要树先序遍历的节点建立一个目录,然后把XML文档中具有相同前缀编码的元素归并到一起,这样可以快速地定位某个节点的祖先节点,最后根据B + 树将XML文档中具有相同元素/属性的节点归并到一个索引中。从XML编码可以看出,任意一个节点的前缀编码都包含了从根节点到该节点的简单路径信息。
一般实际的应用中,Schema文档和XML文档之间是多对多的关系。本文为了方便测试SBXHCI方法的效率,提出的索引技术是基于一个Schema文档对应一个XML文档的,因此在实际开发中,我们只需要在schema文档和XML文档编码过程中分别加入Schema_ID( n ) 和XML_ID( n ) 即可。
2. 2 路径查询语言
XML查询语言共同的特点是使用路径表达式在XML文档中导航到待查询节点并返回指定路径的节点集合,目前最常用的XML查询语言是XPath。XPath使用路径表达式来查找XML文档中的节点、节点集合、原子值等,节点是沿着路径选取的,它的基本语法为Step1 /Step2 /…/Step N,其中Step = Axis: : Node_test[Predicate* ]。轴Axis实际上是指一个方向,即查询是沿着选着的轴的方向移动,节点测试Node_test是指选着的节点类型或者是节点名,谓词Predicate对定位步选择的节点作更进一步的筛选。
一般情况下路径表达式为复杂路径,即表达式会存在多个谓词使得查询过程中存在多个分支几点。本文处理复杂路径的基本思想是路径分解的方法,即将复杂路径查询分解成若干个简单路径表达式,对每个简单路径查询的结果集进行连接得到需要查询的结果集。
2. 3 算法分析
SBXHCI查询文档分为四个步骤: 建立索引,路径分解,与Schema索引匹配,与XML文档匹配。SBXHCI查询算法流程图如图4 所示,具体算下如下:
( 1) 建立索引。分别对Schema和XML文档建立索引,具体步骤可参见2. 1 节中的说明。为了减小索引空间,本文改进了Schema摘要树中前缀编码的方法,根据摘要树层次中最大的兄弟节点个数( 记作b Node ) 来决定编码的长度1 = [log2max( b Node ) ],既每层的编码长度,从而减小了Schema编码中前序编码的Code( n ) 的长度。如图1 中第三层节点中最大的兄弟节点为5,则可以用3 位来表示每个节点的编号。
( 2) 路径分解。在进行路径表达式查询过程中将复杂路径分解为若干个简单路径的子查询,对于分解后含有目标节点的简单路径称为目标匹配路径,只含有一个谓词约束的简单路径称为条件匹配路径。例如一个复杂路径表达式a/b[c > d]/e/f[g = h]/i,可以分解为条件匹配路径a/b[c > d],b/e/f[g = h]和目标匹配路径f/i。
( 3) 与Schema索引匹配。对分解后的子查询在Schema索引中进行有效性的验证,可以通过定理1 来判断一个简单路径是否合法。如果子查询中存在Schema索引文档中无相匹配结构的路径信息,则说明待查询的路径表达式不合法,返回无查询结果。因为Schema中定义了XML文档遵循的规则,即XML文档中可以使用的元素和元素的数据类型,而且还定义了文档中元素出现的顺序和次数及其嵌套关系等,如果在Schema中查询不到相应的路径信息,则在相应的XML文档中也不会存在此路径表达式的查询结果集。因为Schema文档的大小比XML文档的小的多,所以加快了对无效路径的查询效率。如果在Schema索引中有相应匹配的路径信息,则说明待查询的路径是一个合法的表达式。
( 4) 与XML文档匹配可以根据待查询的路径表达式的复杂度分为两种情况:
a) 如果查询路径为简单路径,即查询路径为目标路径,则可以直接根据路径的目标节点在Schema摘要树中找到对应的S_Code( n ) 值,从而在XML文档的索引中直接获取到待求的XML节点;
b) 如果查询路径为复杂路径,可以将查询路径分解为若干个分支路径集合{ b Path} 和一个包含目标节点的目标路径TPath。如果{ b Path} 包含两条及两条以上的路径集合,首先从{ b Paht } 依次取出两条路径找出叶子节点的前缀编码S_Code( i) ,并找出对应的Schema摘要树中的相同的前缀编码Code( i) ,使用“与”操作计算出相邻路径中节点的最长的前缀编码,循环操作{ b Path} 既可以得到分支路径结果集bResult; 如果{ b Path} 只包含一条路径,则直接可以求出bResult。最后使用同样的方法对bResult和t Path进行连接,得到待求的XML节点。具体算法如下所示:
输入:分支路径集合{b Paht},目标路径t Path
输出:待求的XML节点集Result
3 实验及其分析
为了测试和评估本文提出SBXHCI查询系统中的混合索引方法性能和查询效率,本文使用了Java语言实现SBXHCI查询系统。实验运行在一台CPU主频为2. 3 GHz双核,内存大小为4 GB,操作系统为Windows 7 电脑上。实验采用的数据有两种:第一种是广泛应用于XML测试的DBLP数据,它的特点是结构简单,树的深度不高; 第二种是XML基准数据库XMark,它包含了复杂的树形记录结构。本文实验中忽略了XML数据中的空格,并且所有的实验都是经过多次实验所取得稳定的平均结果值。表1 表示两种不同数据及的特征。
根据实验的可行性和可获得性,本文选取文献[6]中的XISS方法、文献[8]中DBXI方法、文献[11]中SBXI方法三种具有代表性的方法和本文提出的SBXHCI方法进行分析和比较测试。
3. 1 构建索引的时间和空间比较
衡量一种索引机制的性能可以从以下三个方面来考察: ①创建索引所花费的时间; ② 存储索引所需的空间; ③ 查询响应消耗的时间。创建索引所花费的时间越短,消耗的存储空间越少,查询响应的时间越短,则说明索引的性能越好。图5 分别表示不同方构建索引的时间和空间比较。
从图5( a) 中可以看出,不管是结构相对简单的DBLP文档,还是相对复杂的XMark文档,SBXHCI方法建立索引所需的时间都是最小的。原因是解析Schema与解析XML文档使用相同的解析器,相对于解析DTD时减小了消耗的时间,加快了索引的构建,因此使用Schema构建索引的方法SBXHCI和SBXI所消耗的时间小于使用DTD构建索引的方法DBXI。
从图5( b) 中可以看出,XISS构建索引消耗的空间最小,原因是XISS在构建索引的过程中只对XML文档中每个节点赋予一个二元组( pre,post) 编码,并没有包含模式信息,因此构建索引使用的空间最小; 对于结构相对简单的DBLP文档,SBXHCI方法建立索引所需空间则比DBXI和SBXI要小,而对于结构相对复杂的XMark文档,SBXHCI方法建立索引所需空间则比DBXI和SBXI要大,虽然本文优化了前缀编码标识节点的位数,但在构建索引的过程中比区间编码使用了更多的存储空间,因此SBXHCI方法在构建XMark索引过程中比DBXI方法使用了更多的存储空间。
3. 2 查询响应时间的比较
为了测试文档索引的查询响应时间,本文针对表1 中数据2-DBLP和数据4-XMark两种数据集,分别给出了4 种具有代表性的路径表达式查询语句,如表2 所示。其中D1 - D5 是关于DBLP的查询表达式,X1 - X4 是关于XMark的查询表达式,D1和X1 是不包含谓词的简单路径查询,D2 和X2 是含有谓词的简单路径查询,D3 和X3 是含有谓词的复杂路径查询,D4、D5和X4 是错误路径查询。查询响应时间实验结果如图6 所示。
从图6 中可以看出,对于无效路径的查询,DBXI、SBXI和SBXHCI三种方法都可以快速的判断出无查询结果。在XML文档建立索引中有效的利用了模式信息,都是先从相应的模式信息中进行匹配,无需查询XML文档,可以直接判断出无效查询,因此大大降低无效路径的查询响应时间。
对于有效路径的查询,SBXHCI方法相对于其他三种方法明显的降低了查询响应时间。对于XISS查询具有N个元素组成的路径查询时,需要N - 1 次的结果结构连接,因此查询响应消耗的时间最大; DBXI和SBXI方法都是采用区间编码建立索引,在结构连接算法的性能低于采用前缀编码的索引; 而SBXHCI采用混合编码索引的机制,在结构连接中去除了不相关节点的连接操作,减少了结构连接次数,加快了结构的连接运算,这使得查询效率得到更进一步的提高,优于其他三种方法。
4 结语
XML数据索引技术论文 篇4
现在传统的方式是使用DOM或SAX协议对XML文档进行操作, DOM是建立文档树来访问XML数据, 建立树的过程会花费很大的系统开销, 对于较大的XML文档, 这种方式会很大程度上降低系统的性能, 即使使用SAX协议访问, 也是顺序方式查找XML文档, 还是很难满足日益发展的Web服务的要求。当数据量很大时必须找到一种新的方式来提高查询的效率, 人们已经开始着手研究Native XML数据库 (NXD) 并取得了一定的成就, Native XML数据库是一种新的数据库技术, 是一个完整的数据库系统, 有着传统数据库的各种功能和组件, 如今NXD的技术还在研究中, 一些机制还不是很完善。该文利用NXD的思想, 保持XML文档的原格式, 并建立索引来提高查询效率, 针对一种特定情形下的数据查询基于XML文档的存储结构建立索引机制, 这里要处理的是图书查询系统的图书信息, 针对常见的查询建立索引, 使用关系数据库来保存索引, 加快查询效率的提高。
1 图书查询系统应用分析
首先, 分析一下图书查询系统常用的查询有哪些种类, 针对这些应用来建立索引。
1) 用户要求返回具有某种属性的书目列表。这是最常用的查询方式, 几乎绝大部分查询都是这种类型的查询, 如题名检索、作者检索、主题词检索、出版社检索等, 我们为题名检索和出版社检索为例。
问题一:查询书名为“我的童年”的书目列表。
问题二:查询“清华大学出版社”出版的书目列表。
2) 返回一类书目的列表。这里可能是某一类书中的一个子类, 如一个网页设计的入门者, 他只是想浏览网页设计方面的书籍, 并不是确定要找哪一本书。
问题三:查询类别名为“网页制作”的书目列表。
3) 返回具有某一属性的书本的其他属性列表。这种应用很少, 但也存在, 如想要查找在清华大学出版社出书的作者列表。
问题四:查询出版社为“清华大学出版社”的书目作者列表。
2 建立索引
根据实际的应用给要查询的文档建立索引, 一个书店或者图书馆里的书目是众多的, 所以我们的XML文档也是非常庞大的, 因此已经不可能用DOM或SAX来访问了, 我们也不使用XED (XML-Enabled DBMS) 的方式, 把数据都存储在关系数据库中, 然后转换成XML格式。我们采用了一种折中的方法, 依然使用原始的XML文档方式来存储数据, 但把检索中会用到的数据另外存储到关系数据库中, 这样在查询的过程中使用的是关系数据库系统, 效率比较好, 而最终读取的结果又会依赖XML文档。将XML文档中的一部分内容读取出来, 这样我们查询得到的结果依然是XML格式, XML的优势同样能够得到发挥。其具体结构如图1:
从关系数据库到XML文档, 其实是一个定位过程, 如果不通过关系数据库建立索引, 我们可能是顺序方式查找需要的信息, 现在把查询过程中用到的信息存储在关系数据库中的表中了, 我们需要将这些表 (可能不止一个表) 关联到XML文档中的某个特定的位置, 这样才能减轻查询的负担, 常用的做法是利用XML文档的行号来实现。我们通过例子来看, 附表是一个图书信息文档, 其书目分为两大类, 文学类和计算机类, 在计算机类中又有子类网页制作, 从结构上来说已经是有点复杂了, 存在一个子类结构, 我们看一下《亲密接触ASP.Net》这本书, 这本书的信息是从
现在来建立下一个表, 考虑到第一类应用, 也是几乎绝大部分的查询方式, 这一类查询强调某本书的一个子元素或属性, 而这些元素或属性正好是XML文档里的路径。由此引入路径表:path_list, 见表2。把XML文档中出现的所有路径存储到表中, 这样我们要查询时可能从该表中选择正确的路径进行查询, 例如要查询书名时, 可以在path属性里匹配字符串“/catalog (/category) +/book/name”即可, 这里的字符串是用正则表达式表示的, 其中“/category”在path里可以出现多次, 但至少出现一次。
表2只是存储了XML文档中的所有路径, 至于路径下的内容才是查询时用到的主要信息。单有这个路径是不行的, 必须再引入一个表来存储XML文档中每个元素或属性的值, 即value_list表, 见表3。value_list表存储了路径和值, 在查询的时候可以依照路径查询, 而最终得到的结果是某本书或某些书的列表, 而这些信息可以通过book_list来获得, 这要求在value_list表中再存储一个book_id来定位到某一本书,
对于第一类的书目, 包括子类别, 需要单独存储出来, 以保证分类查询时的效率, 因此再加入一个表:category_list, 见表4, 这个表能确保分类查询时快速返回结果。
value_list、category_list两个表这里没有设主键, 实际应用时应添加主键。
3 执行查询
通过上面的四个表, 我们建成了图书目录XML文档的索引, 这里并不是把信息存储在一个表中, 而是分开建立索引, 以利于询和实现XML优势, 现在来执行前面提到的三类应用。第一类应用中, 对问题一, 首先从path_list表中查询合适的路径, 也就是配前面说到的字符串, 得到1和13两个path_id符合, 然后从value_list表中查询这两个path_id且value字段为用户给定的“我的年” (或者以“我的童年”为子串的字符串) 的记录, 返回book_id值, 最后从book_list表中得到其内容在XML文档中的位置, 定位XML文档中返回最终结果。主要用到以下的SQL语句:
SELECT start_pos, end_pos FROM book_list WHERE book_id IN (SELECT book_idFROM value_listWHER (path_id=‘1‘ORpath_id=‘13‘) AND value LIKE‘我的童年‘)
第二类问题通过category_list表就可以解决, 书目种类毕竟是少数, 数据量不会很大, 在这个表中查询要找的信息应该很方便问题三执行的SQL语句:
SELECT start_pos, end_pos FROM category_list where category_name=‘网页制作’
第三类应用比较少, 这种查询不需要返回书本信息, 需要操作的是value_list和path_list两个表, 重复查询value_list就可以得结果。这里我们为了简单起见, 只查询没有子类结构的情形。问题四的查询SQL语句为:
SELECT value
FROM value_list
WHERE path_id=’14’AND book_id IN
(SELECT book_idFROM value_listWHERE path_id=‘15‘AND value=‘清华大学出版社‘)
4 结束语
本文简单介绍了图书查询系统XML文档的一种索引建立方法, 它是针对查询这种特殊的应用设计实现的, 利用关系数据库来建立索引, 但最终的数据还是保存在XML文档中, 索引中建立了路径表, 能够支持XPath查询的实现。这种索引机制适用网上书店系统, 图书馆检索系统等, 只提供给用户查询, 不提供修改, 执行修改和更新的是图书管理员, 而且面向单一应用, 用特定的表实现, 效率较高。在有新的应用时, 我们可以建新的表机制来实现需求。这种索引能大大提高查询效率, 但存在一些不足, 由于是对查询建立的索引机制, 在多用户频繁更新数据的情形下, 系统需要重建索引, 会大大提高系统需求。
摘要：该文针对XML, DOM和SAX协议操作大文档的缺陷, 将技术成熟的关系数据库索引机制应用于图书书目查询系统, 从而实现对XML文档的快速查询。
关键词：XML,关系数据库,索引
参考文献
[1]Arzucan Ozgur, Taflan I Gundem.Efficient Indexing Technique for XML-based Electronic Product Catalogs[J].Electronic Commerce Re search and Applications, 2006 (5) :66-77.
[2]王宏宇.基于Native—XML数据库倒排索引算法研究[J].情报科学, 2006, 24 (7) :84-88.
[3]李素清, 陶世群.一种基于关键词的XML文档查询算法[J].计算机工程与应用, 2012, 48 (5) :138-142.
[4]赵雄峰.一种高效检索XML文档的倒排索引技术[J].电脑知识与技术, 2010, 6 (30) :8429-8431.
时空数据库索引技术研究 篇5
关键词：时空数据库,移动对象轨迹,索引
因为出现许多需要有效对移动对象管理的应用,STDB受到很多关注。这些应用需要在不同的时间戳记录对象的地理位置(有时也记录对象的形状),而且支持对它们历史的和将来预期的特征进行查询。
STDB的目的是根据数据的时间属性作历史性和预言性的检索。具体地说,给定对象集合o1,o2,…,oN(N是基数),对于每个对象oi(1≤i≤N),历史性STDB会存储oi在历史的所有时间戳t的有效范围oi.E(t)。根据空间数据库的原理,oi.E(t)能够表示为一个描述对象在时刻t的真实形状。尤其是,如果其形状不是重要属性,oi.E(t)则以一个点代替以表示oi在时刻t的位置。实际上,在连续时间戳,同一对象的有效范围可以用不同的方法压缩(例如:如果对象在几个连续时间戳保持静止,则它的有效范围在该时间内只需存储一次)。
另一方面,对每个对象oi,预期性STDB会存储它的最新更新的位置oi.L(tupd)(tupd:对象最新更新的时间)和用于描述它当前移动特性时间函数。最适合的时间函数是线性函数,因为1)线性函数能够近似描述任何运动轨迹,2)线性函数要求的参数个数最少。具体来说,除了oi.L(tupd),系统只需记录对象的速度oi.vel,就可以计算出在将来任何时刻t>tupd对象的位置:
oi.L(t)=oi.L(tupd)+oi.vel(t-tupd)
用这种模型只需在对象的时间函数的参数(如:速度)发生变化时采取更新数据库。
人们已经对作为支持时空查询的辅助结构的时空索引方法做了很多研究。时空存取方法主要集中在两个正交方向:1)对对象过去位置的索引,2)对现在的位置和将来预期位置的索引。
1 移动对象历史数据的时空索引
考虑到移动对象连续不断发送它们的位置,保持所有的更新几乎是不可能的。有两种方法可用来减少历史数据:1)采样,对数据流在某一时刻进行采样。可以采用线性插值计算出相邻采样点间的线性轨迹。2)仅在变化时更新,移动对象仅当它们的数据属性(速度或方向)发生变化时才发送数据。我们把对历史数据的时空索引机制分为三类。
第一类是在现存的空间索引方法加入时间属性。这类时空索引方法主要是处理空间维,时间维是第二要素。
RT-tree[1]结合了作为空间存取方法的R树和作为时间存取方法的TSB树。在RT树中,时间和空间信息是分开维护的。不管是叶结点还是非叶结点,每个索引项都包含(S,T,P)形式。S是空间信息,T是时态信息(时间间隔),P是指向子树或对象的指针。随着时间变化,如果对象空间位置不变,则它的空间信息S不变,仅对时态信息进行更新。如果对象空间位置发生变化,则需要创建一个新的索引项插入RT树。这种方法有许多局限性,一方面,如果变化对象的数量很大,许多索引项被创建,RT树会迅速膨胀;另一方面,当结点溢出时,怎样分裂结点还没有很好的解决办法。
3D R-tree[2]把时间看作除了空间维以外的另一维。主要思想是为了避开时间和空间查询之间的区别。3D R-tree可以直接利用现有的R树算法来处理空间及时态查询而无需修改,其前提是必须知道移动对象历史轨迹存在的有效时间范围,如果移动对象轨迹结束时刻不确定,那么3D R-tree将无法有效工作。比如若移动对象运动轨迹从某个历史时刻开始一直延伸到当前时刻,显然包围移动对象轨迹的3D MBR将会非常巨大且造成空间区域的大量重叠,直接导致3D R-tree的查询搜索性能下降。因此,在应用中要求移动对象轨迹是封闭的(closed),即移动对象历史轨迹必须在某个过去时刻终止而不能延伸到当前时刻。由于3D R-tree将时间维与空间维等同索引,时间片查询则必须扫描整个3D R-tree而非在此时间片下的有效子树,因此性能非常低下。
第二类是同时把空间和时间加入某一结构中,但它们是各自独立的。这是为了使在某一时刻所有有效的空间数据同时在一个索引结构(R-tree)中。最高目标使为每一时间项都建立一个单独的R-tree。这种方法需要很大的存储量。
MR-tree[3]采用了在R-tree的背景下可重叠B-tree的思想。主要思想是避免每个时间戳都有单独的R-tree而引起的存储量过大。通过在连续的R-tree中不存储相同的对象实现减少存储量。作为替代,以不同根结点的链接指向同一结点,而所有的结点项都保存着它们在不同时间戳的值。这种思想对时间片查询来说是完美的。搜索被指向适合的根结点,然后利用R-tree进行空间搜索。然而,它对时间窗口查询的执行是无效的。而且,一个主要的缺陷是存在许多重复项。考虑到这样的情况,在连续两个时间戳仅有一个结点项发生变化,而在这连续两个R-tree的所有其它结点也必须重新复制。
HR-tree与[4]MR-tree非常相似。HR-tree是一种采用重叠技术、将单一版本的结构转换为部分固定结构的高效时空索引结构。该结构为两级索引机制,分别对时空对象的时间信息和空间信息进行索引:1)HR-tree是对事务时间进行索引,它按时间递增顺序将时空对象的时间信息组织为有序表,并将时空对象不发生空间变化的那个时间片作为时空对象的时间信息值;2)用R-tree索引结构为每个时间片的空间对象建立索引,并将R-tree的存储信息(根结点存储地址)保存到对应时间片的时间索引结点中。为了节省空间,相邻时间片的R-tree可能会重叠,即若相邻时间片的R-tree有共同的分枝,则只保存该分枝的一个版本。
第三类是主要考虑时间维索引,其次考虑空间维。第三类方法主要集中在面向轨迹的查询。在此类中处理空间查询处于次要位置。
Trajectory-bundle(TB-tree)[5]是完全保持轨迹的类似R-tree结构。一个叶子结点仅能包含属于同一轨迹的线段。存在一个缺陷:在空间上比较靠近的不同轨迹的线段将被存储在不同的结点上。构建TB-tree是从左到右的原则。也就是说。最左边的结点是最先插入的结点,最右边的结点是最后插入的结点。
Scalable and Efficient Trajectory Index(SETI)[6]将空间区域分割成静态且不重叠的分区,在每个分区下对移动对象的轨迹线段利用R树进行索引。其考虑是,相对于无限连续变化的时间维而言,移动对象轨迹受空间范围所限,那么可以把受限的空间区域利用某种规则静态划分以分而治之。良好的划分函数应尽量把同一移动对象不同轨迹线段聚类在同一个分区中。若一条轨迹线段穿过多个分区,那么必须将此线段裁剪并分别存储在不同分区R树中,这样会导致查询结果的重复,在查询处理后必须进行重复结果的剔出。相应地,时态查询则被转换为对折线段集合的空间窗口查询,利用几何计算方法可以得到空间窗口内的折线段集合,其对应的移动对象集合即是时态查询结果。
2 移动对象当前位置轨迹索引
在现实应用中许多要求能够有效地对移动对象当前位置进行管理和查询。相对来说,检索移动对象当前位置更具有挑战性,其关键在于如何提高传统空间索引的频繁更新动态性能以满足动态环境下的应用要求。标准R树更新算法采用删除-重插机制来实现移动对象位置更新,频繁更新会导致R树性能急剧下降。为了支持R树的频繁更新操作,近年来提出的方法包括LUR树(Lazy Update R-tree)、自底向上更新策略(Bottomup Update)、哈希方法(Hash)等。LUR[7]提出了一种延迟更新(Lazy Update)策略,即若移动对象位置未超出当前节点MBR,算法仅仅更新移动对象所在的数据页面并维持索引页面不变;对于移出MBR之外的移动对象,根据其超出MBR程度大小,判断是否将MBR进行有限扩展以包含移动对象新位置;或者利用标准R树更新算法进行更新以尽量减少位置更新所带来的索引树更新操作。Bottom-up Updates的自底向上法扩展了LUR-tree思想。自底向上法比较适合处理移动对象的连续更新。例如:扩展MBR以包含新的值和移动当前对象到兄弟结点。
Song等人利用空间划分的思想来索引移动对象当前位置,首先静态地把空间划分为可以相互重叠的区域,然后根据当前位置将移动对象哈希映射到不同区域中去。只有当移动对象位置超出了当前区域才会更新此对象的索引记录,数据库中保存了移动对象位置近似视图。
3 当前和将来轨迹查询索引
在移动计算、位置服务等新兴应用中,需要对移动对象当前及未来位置预测以提供相关服务,针对移动对象当前和未来轨迹的索引方法是目前研究的热点。为了能够预测移动对象未来轨迹,需要存储一些额外的信息(如移动对象当前速度和目的地等)。然后根据移动对象当前的运动特性对未来轨迹进行预测,目前通常使用线性方程来描述移动对象的运动特性。在D维空间下,移动对象运动特性可以使用参考时间tref时位置xref=(x1,x2,…,xd)以及速度矢量v=(v1,v2,…,vd)来描述。移动对象在任何时间点t(t≥tref)的位置可利用公式xt=xref+v(t-tref)计算得出。主要的索引方法有:FT-Quadtree、PMR-Quadtree、STRIPE索引、TPR-tree、TPR*-tree等。
FT-Quadtree[8]使用的是Quad-tree索引结构,最大的特点是使用了轨迹共享技术来最大限度地减少数据的存储数量,提高索引的更新效率。在这种树中的叶子节点结构表示为(oid,轨迹的数量,起始坐标,结束坐标,起始时间,结束时间,其他信息)。对于在同一时间内的节点而言,如果它们的坐标位置相同或者接近,那么就可以采取共享策略把若干个节点的内容放入一个公共的节点内,这样就可以明显地减少存储的空间。
使用PMR-quadtree[9]作为索引将来轨迹的基本空间存取方法,关键的一点是当移动对象发生更新时,整个索引结构被破坏,然后根据新的信息重建索引结构。为了避免过多的更新操作,索引每ΔT时间单元重建。在理论上,无限的时间维可以分割为大小为ΔT的相等的时间片。对于每一时间片,会构建一个新的基于运动方程的PMR-tree。然而,由于存储设备的有限性,只有当前的PMR-tree会被存储。
TPR-tree[10]使用时间参数化包围框来包含移动对象,其索引结构与R树类似。但TPR-tree采用谨慎的BR策略,在某些时刻(如构建时刻)包围框是最小的,但在其后的时间内往往不是。从一维角度考虑,MBR最(大)小边界速度为其范围内所有点的最(大)小速度,从而保证所有点始终包含在同一个MBR中。TPR-tree索引节点记录不仅存储了移动对象(子树)MBR,而且包含了移动对象(子树)MBR速度矢量。由于节点MBR呈现出一种随时间变化的动态性,随着时间延伸包围框会越来越大,导致空间区域的大量重叠从而使得性能下降。因此,必须在适当时候对TPR-tree进行重构以提高查询性能。
TPR*-tree[11]修改了TPR-tree的动态操作算法。通过维护一个代价下降优先队列保证插入路径选择的全局最优,保持TPR-tree MBR的紧致性以提高查询性能。对于上溢节点的分裂算法,TPR*-tree只是在必要的时候才对节点分裂并重插。以二维空间移动对象为例,节点首先在所有可能的8个方向(4×d)上进行排序,并从中选择一种最好的分裂方式,实际上此时节点并不分裂,而是把节点中30%的记录删除后重插。如果在重插过程中发生上溢,那么就直接进行节点分裂以避免传递操作。TPR*-tree是目前最好的参数化空间访问方法。
4 结束语
该文总结了移动对象轨迹索引的各种技术,并对它们进行了比较详细的分类,对每种方法均找出了多个比较典型的模型进行介绍。近年来对移动对象历史轨迹、当前位置与未来趋势预测的索引方法研究较多,在如何同时解决上述三种查询的索引方法上研究仍然欠缺。多种索引结构的结合是时空数据库系统实际设计的主要趋势,选择哪几种索引结构以及如何把它们有机地结合起来将是系统设计所面临的主要难题。
参考文献
[1]Xu X,Han J,Lu W.RT-Tree:An Improved R-Tree Indexing Structure for Temporal Spatial Databases.In Proc.of the Intl.Symp.on Spatial Data Handling,SDH,pages1040-1049,July1990.
[2]Basch J,Guibas L J,Hershberger J.Data structures for mobile data.In Proc.of the ACM-SIAM symposium on Discrete algorithms,SODA,pages747-756,1997.
[3]Xu X,Han J,Lu W.RT-Tree:An Improved R-Tree Indexing Structure for Temporal Spatial Databases.In Proc.of the Intl.Symp.on Spatial Data Handling,SDH,pages1040-1049,July1990.
[4]Nascimento M A,Silva J R O.Towards historical R-trees.In Proc.of the ACM Symp.on Applied Computing,SAC,pages235-240,Feb1998.
[5]Pfoser D,Jensen C S,Theodoridis Y.Novel Approaches in Query Processing for Moving Object Trajectories.In Proc.of the Intl.Conf.on Very Large Data Bases,VLDB,pages395-406,Sept.2000.
[6]Chakka V P,Everspaugh A,Patel J M.Indexing Large Trajectory Data Sets with SETI.In Proc.of the Conf.on Innovative Data Sys-tems Research,CIDR,Asilomar,CA,Jan.2003.
[7]Kwon D,Lee S,Lee S.Indexing the Current Positions of Moving Objects Using the Lazy Update R-t ree[C]//In:Proc.of MDM,2002.
[8]Ding R,Meng X F,Bai Y.Efficient Index Maintenance for Moving Objects with Future Trajectories[C]//Kyoto:The8th International Conference on Database Systems for Advanced Applications(DASFAA),2003.183.
[9]Tayeb J,Ulusoy O,Wolfson O.A Quadtree-Based Dynamic Attribute Indexing Method.The Computer Journal,41(3):185-200,1998.
[10]Saltenis S,J ensen C S,Leutenegger S T,et al.Indexing the Positions of Continuously Moving Objects[C]//In:Proc.of ACM SIG-MOD,2000.
XML数据索引技术论文 篇6
XML文档版本管理的目的是不仅可以让使用者操作最新版本的XML文档,还可以快速获取旧版本的XML文档,对XML文档版本发展过程进行追踪。目前已提出的XML文档版本管理技术有Diff-based[1]、Timestamps-based[2]等方法。
Diff-based方法的主要概念都是利用edit-script语法(insert, delete, update,move)来记录同一份XML文档不同版本之间的变化。不管Diff-based方法经过怎样的发展,仍然无法突破直接任意地获取XML文档版本的限制。
文献[2]以Timestamps-based方法为基础,提出了以时间戳与数值范围为XML文档版本中每个结点进行编码。但没有讨论如何明确定义结点数值范围中的间距值range,也没有说明当新的XML文档版本加入时,例如新增、删除和修改XML文档,原来XML文档结点的数值范围应该如何调整。
1多版本XML文档及编码方法
文献[3]提出了多版本XML文档的概念。多版本XML文档是将原始版本及其后续版本的差异整合成一个XML 文档,并且设计出新的numbering schema,给予XML树状结构的每个结点两种范围的编码:空间上的数值范围(startpos :endpos)和时间上的生存周期(vstart :vend)。图1是一个多版本XML文档的例子(版本1-3),图中标出了每个结点的编码。
版本1只有books结点和左分支的book结点,这些结点一直到版本3依然保留,因此每个节点的(vstart :vend)都是(1 :3),版本2增加了右边的book结点及4个子结点,因此这些结点的vstart是2,这些结点在第三个版本中继续保留,唯独删除了book结点的第三个子结点author,因此该author结点的vend是2,其他结点的vend均为3 。
新的numbering schema实际上是区间编码的一种扩展,存在如下关系:
(1) 可利用时间范围(vstart :vend)来撷取满足特定版本的结点。如要撷取版本v的结点a,只需满足a.vstart<v<a.vend条件即可。
(2) 可利用数值范围判断两个结点之间的结构关系。如给定的两结点u,v,如果u是v的祖先,当且仅当u.startpos<v.startpos<u.endpos。
2编码的维护
首先给出插入子树的四种情形,如图3所示。三角形代表要插入的子树。根据插入子树在原文档中有无左右子树,可以划分为四种情形。 我们注意到,当在文挡中插入内容,原文挡的所有结点的数值范围需重置,进而会导致索引文件内容以及结构的调整,这样的效能无疑是低下的,下面讨论插入一个子树时结点编码更改最小化的方法。
举例说明:如图4(a)所示,在结点<2,4>和<5,7>之间插入一子树(结构如图4 (b) 所示),这属于情形一:插入的子树有左右兄弟子树。此时插入子树的根结点的startpos值应该满足在区间[Left.endPos,right.startPos]内,即[[4],5]内,才能保证结点之间的结构关系,而此区间的间距仅为1,因此有些文献提出在编码时给所有结点的区间编码都乘以一个系数,从而预留出一定的空间,但问题是,对插入子树的规模我们无法预测,如果插入子树过大,即使预留空间也没有用,我们采用浮点数给子树编码,具体方法是:先给子树相对编码,相对编码结果如图4 (b)所示,然后再将子树中所有结点的编码都乘以一个系数,我们称之为相对因子,相对因子取0.1,0.01,0.001等这样的小数。取值时必须满足其与插入子树的根结点的endpos值的乘积小于1,此例中,子树的根结点的endpos值为4,因此相对因子的值为0.1,最后再将子树中所有结点的编码加上左区间的值,此例中左区间的值为4,从而完成对子树的编码,如图4(c)。这样可以保证原来的文档中所有结点编码的数值部分不需要重置。情形二:插入子树的根结点的startpos值应该满足在区间[Left.endPos,P.endPos]内。情形三:插入子数的根结点的startpos值应该满足在区间[P.startPos,right.startPos]内。情形四:插入子树的根结点的startpos值应该满足在区间[P.startPos,P.endPos]内。情形二、三、四给子树编码的方法与情形一相同,只是其中的一个参数(左区间的取值)不同。
3新的索引机制
我们将从索引文件内容和索引文件结构两方面来讨论新的索引机制。
文献[3]用关系数据库来存储多版本文件至少有两个缺点:(1)无法利用XML数据自身的特点,如结构化、自描述性等,在处理XML数据时需经过多级复杂的转换;(2)对结构查询不具有优势,对如图5这样存在祖先、子孙复杂嵌套的多版本文件,无法避免冗余连接。(篇幅所限,图5中我们只标记出结点的(vstart :vend),而数值范围由线段的长短标记,如果有结点没有标出时间生存周期,表示该结点继承其祖先的生存周期)。
本文提出的新的索引机制能较好地解决上述两个问题。新的索引机制可以用在纯XML数据库中,同时能支持多版本XML文档的结构查询。索引文件的内容是将文档中具有相同名称的结点存储在一起形成一个列表,列表保存每个结点的四元组编码。以图5为例,该文档索引文件内容如下:
A:<1,21,1,10>,<2,4,2,8>,<5,9,1,7>,<6,8,1,7>,<7,7,1,7>,<10,15,1,8>,<11,13,1,8>,<12,12,1,8>,<14,14,1,8>,<16,20,1,9>,<17,19,1,9>,<18,18,1,9>,<35,37,1,9>
D:<3,3,2,7>,<22,24,1,10>,<23,25,1,10>,<24,24, 1,10>,<26,30, 1,10>,<27,29,1,10><28,28,1,10>, <31,33,1,10>,<32,32,1,10>,<36,36,1,9>
通过b+树来组织每个名称列表。根据b+树的插入算法,将每个list中的结点按照startpos值由小到大插入一棵b+树,这种索引结构将加速查询。
本文提出的索引机制和XISS有些相似,但也有本质的不同。XISS用<order,size>来标记每一个结点,仅仅能够判断结点之间的结构关系,但是不支持多版本文档,我们沿用XISS最根本的思想,但用新的numbering schema来代替<order,size>的结点编码机制,就可以在不恢复版本的前提下,利用索引直接快速地撷取特定版本的结点,为多版本XML文档的结构连接奠定了基础。
4查询
结构连接是XML查询的核心操作,受到了专家和学者的关注。目前提出的许多结构连接算法都不支持多版本的XML文档。文献[4]叙述的anc_desc_b+算法效率比较高,该算法对alist和dlist列表分别顺序扫描一次就可以完成连接。下面我们来扩展该算法,使其支持多版本XML文档的查询,通过算法分析看出,该算法在处理祖先—后代复杂嵌套的情况时能利用索引的B+树结构跳过并不参与连接的结点,避免了许多冗余的连接步骤。
4.1算法
自定义的两个过程version_of_demand(a)和nextnode(a)是算法扩展的基础。version_of_demand(a)能返回a结点是否是符合版本的结点;而nextnode(a)过程返回a列表中下一个符合版本条件的a结点。扩展后的Anc_Desc_B+_MV算法如下:
Anc_Desc_B+_MV(alist,dlist,v)
输入:两个参与连接的列表Alist和Dlist,要获取的XML文档的版本整数V
输出:按后代有序的连接结果output
1. Let a,d be the first elements of alist and dlist;
2. While (not at the end of alist or dlist) do
3. If (a is an ancestor of d) then
4. Locate all elements in alist that are ancestors of d and version_of_demand(a) and push them into stack;
5. Let a be the last element pushed;
6. output d as a descendant of all elements in stack;
7. D=nextnode(d)
8. Else if (a.end<d.begin) then
9. If (ancestor stack is not empty) then
10. Pop all stack elements which are before d;
11. Let 1 be the last element popped;
12. Else 1=a;
13. Let a be the element in alist having the smallest begin that is larger than 1.end and version_of_demand(a); /*利用B+树定位/
14. Else
15. Output d as a descendant of all elements in stack;
16. If (ancestor stack is empty ) then
17. Let d be the element in dlist having the smallest begin that is larger than a.begin and version_of_demand(d)
18. Else
19. D=nextnode(d)
20. Endif
21. Endif
22. endwhile
4.2查询
简要说明算法的执行过程,以图5为例,如果查询版本2的a//d,则执行过程如图7所示。可以看出,参加连接的祖先结点仅为<a1,a2,a13>,后代结点仅为<d1,d10>,利用新的索引机制,避免了连接中的冗余操作。上述查询还隐藏着另一层意义,一般的XML文档版本管理问题中,若要查询某个版本的内容,需先恢复版本。而本文所述方法不需要恢复版本就能直接进行查询,原因是(startpos :endpos)和(Vstart:Vend)具有时间和空间的概念。
Step1:压a1进栈 Step2:压a2进栈Step3:输出(a1,d1)(a2,d1) Step4:弹a1出栈,弹a2出栈Step5:a13进栈 Step6:输出(a13,d10)Step7:弹a13出栈
5总结
多版本XML文档的研究是XML研究领域相对独立的一个研究方向,目前主要由加州大学洛杉矶分校和台湾嘉义大学从事这方面的研究,国内此项研究尚处于起步阶段。不同于以往研究,在改进编码方式的基础上,本文针对多版本XML文档提出了一种新的索引机制,在文档频繁更改的时候,多版本文档结点的数值编码不需要重置,索引文件内容和索引文件结构的更新也是局部而有限的。更为重要的是,该索引机制的提出对多版本XML文档的存储和查询提供了新的思路:文档的存储不再需要依托关系型数据库;在不需要恢复版本的情况下,扩展后的结构连接算法也能够对任意版本的文档作高效的结构查询。
摘要：首先对XML文档的编码方式作了改进,提出了用浮点数对插入子树进行编码的方法,新的编码方法能较好地支持XML文档的插入更新,在此基础上提出了支持多版本XML文档的新的索引机制,最后扩展了一个经典的结构化连接算法使之不仅能支持多版本XML文档的查询,而且还能较好地避免连接过程中的冗余操作。对XML的版本管理,尤其是在索引和查询优化方面提供了一些新的思路。
关键词：XML,索引,多版本XML,结构化连接
参考文献
[1]Marian Abiteboul S,Cobena G,Mignet L.Change-centric management of versions in an XMLwarehouse.Proc.of the27th VLDB,Rome,Ita-ly,2001,9.
[2]Chien S Y,Tsotras VJ,Zaniolo C,Zhang D.Storing and Querying Mul-tiversion XML Documents using Durable Node Numbers.Proc.of WISE,2001.
[3]蔡政霖.XML文档版本管理.http://datf.iis.sinica.edu.tw/Pa-pers/2003datfpapers.
初探面向对象数据库及其索引技术 篇7
一、面向对象数据库
什么是面向对象数据库?至今众说不一, 不同的人有不同的回答。对下一代数据库的发展方向主要有这样三种观点, 它们都与面向对象数据库相关。第一种观点认为如果一个数据库具有诸如复杂对象、对象标识、对象封装、类型和类及类层次、重载与动态捆绑、可扩充的预定义类型、持久性和二级存储管理等这些不可缺少的规则, 那么它就是一个面向对象数据库。这些规则主要强调了面向对象的特性, 而关系数据库只能应用于简单的商务处理, 不适应新的复杂应用。第二种观点则是针对第一种观点的反面观点, 它给出了一组自己新定义的规则并强调关系数据库引入了两个主要开发方法即非过程访问和数据独立性, 在以后的系统中放弃它们是愚蠢的。在数据库中, S Q L作为“星际数据语言”, 必须被支持。第三种观点则比前两种更加形式化和技术化, 它主要基于关系数据模型给出了一个系统。持这种观点的学者认为第一种观点忽略了关系数据模型是错误的, 而第二种观点强调SOL语言也是错误的, 因为他们认为SQL语言是关系模型的误用。他们提出的系统是在关系模型上的扩充, 允许定义新的数据类型。
二、面向对象数据库的主要特点
面向对象数据库将面向对象的能力赋予了数据库设计人员和数据库应用开发人员, 从而扩展了数据库系统的应用领域, 并能提高开发人员的工作效率和应用系统的质量。面向对象数据库具备如下特点:
首先, 它是一个数据库管理系统, 具有数据库管理系统的基本功能。一是永久性, 数据库中的数据是永久保存;二是存储管理, 包括索引管理、数据聚集、数据缓冲、存取路径选择、查询优化等;三是能够并发控制, 提供高于当前已有数据库管理系统同样级别的、对多个用户并发操作的支持;四是故障恢复能力, 提供不低于当前已有数据库管理系统同样级别的、将数据库从故障后的错误状态中恢复到某个正确状态的功能;五是交互式查询功能, 且是非过程化的、高效的、独立于应用的。
其次, 它是一个面向对象的系统。具有支持面向对象数据库模型, 支持复杂对象, 具有运用各种构造机制从简单对象组成复杂对象的能力。复杂对象构造能力加强了对客观现实世界的模拟能力, 且方法自然、易理解;具有对象标识, 对象标识独立于其值而存在的特性可以极大地加快查询速度;具有封装性, 对象既封装了数据, 又实现了信息隐藏, 使用户不必知道操作的实现细节, 只需利用设计者提供的消息即可访问对象;具备类型/类, 类型层次/类层次能力, 因而支持继承性这一强有力的建模工具;具有可扩充性等优良特性。
三、面向对象数据库的索引技术
索引在面向对象数据库中是一种重要的技术, 它具有加速查询求值的功能。在传统的关系数据库中, 索引是在一个属性或一组属性上建立的, 而在面向对象的数据库中, 索引的建立有所不同, 它引入了3类新的索引:继承类层次索引、嵌套属性索引和复杂的二维索引。
1. 类层次索引
类C的属性A的类层次索引, 是以该类为根的类层次上所有类的属性A的一个单一索引。索引属性是建立在其上的属性, 而索引类是索引建立在这些类属性上的类层次的根。
对一个类的查询目标有两种解释:一种是类, 而另一种是以该类为根的类层次, 即该类及其所有直接和间接的子类。如果一个类层次索引不用于一个类层次中, 那么可以依照传统方法对类层次的每一个类分别在共同属性上建立单一类索引。一般说来, 如果继承层次中有两个以上的类, 则类层次索引优于单类索引。对于类层次索引和单一类索引的实现一般采用B+树。
一个嵌套属性索引建立在一个聚集类层次上, 可分为嵌套索引、路径索引和多重索引。
2. 嵌套索引
在面向对象数据模型中, 允许一个对象的属性值是一个对象或一组对象, 构成嵌套对象。尽管一个查询返回一个目标类的实例对象集合, 但查找谓词可以指定在该类的任意嵌套属性上。一个类的嵌套属性上的索引称为嵌套属性索引 (Nested-Attribute Index, 简称为NX) 。在类的嵌套属性索引中, 对属性的索引是间接的, 是针对类的嵌套属性的。换句话说, 对属性的索引并不针对索引类的属性。通常情况下, 采用B+树组织嵌套索引。嵌套索引维护较困难, 但检索性能最好, 适用于对象的反向引用存在的情况。
3. 路径索引
在嵌套索引中, 如果给定一个关键字, 叶结点只记录了关联此关键字路径中起始对象的对象标识。我们研究路径索引 (Path Index, 简称为PX) , 以记录所有以该关键字结束的路径。通常同样采用B+树组织路径索引。路径索引不需要反向游历, 实现起来较方便, 检索性能次之。
4. 多重索引
如果将一条路径分裂成若干条子路径, 并在每一条路径上建立嵌套索引, 可以在一定程度上降低修改索引所带来的开销。通常采用B+树组织多重索引。多重索引结构简单, 维护最方便, 但检索性能不理想。
二维索引即为一个嵌套属性索引, 再加上索引类与索引属性实际所属类之间所有类的一个类层次索引。嵌套继承索引就是综合考虑了聚集和继承两方面的一种二维索引。
总之, 无论使用哪种索引技术, 在选用时都需要对索引性能、维护代价和实现技术复杂度等方面综合权衡, 来达到最好的效果。
四、面向对对象数据库技术的发展
面向对象数据库技术的发展不是取代关系数据库系统, 但能够成为继关系数据库技术之后的新一代数据库管理技术。尽管目前已有大量的研究开发工作, 已有一些可运行的面向对象数据库系统, 但面向对象数据库的成熟仍有赖于许多关键问题的解决。
1. 标准化和形式化是面向对象数据库系统研究和发展的一个重要方向。几年来, 人们对面向对象数据库概念和技术已基本达成了共识, 但在面向对象数据模型的其它方面, 如体系结构、编程接口语言的理解等不是很统一, 还需要在系统研制和应用过程中进行标准化。
2.面向对象数据库系统的性能改善是必须加强的。面向对象数据库系统作为CAD/CAM/CASE应用环境的开发平台, 这些应用往往需要对大量互相关联的对象进行计算。传统数据库系统的计算模式是每次为用户提供一个对象, 与这种应用不匹配, 所以有必要研究面向对象数据库系统的计算模式。面向对象系统中有大量频繁使用的操作, 如给对象发送消息、根据对象标识决定物理位置等, 识别这些操作, 再进行优化实现对面向对象数据库系统性能的改善有重要意义。
3. 在发展一项新技术的同时, 必须面向对象数据库系统作为CAD/CAM/CASE应用环境的开发平台, 这些应用往往需要对大量互相关联的对象进行计算。传统数据库系统的计算模式是每次为用户提供一个对象, 与这种应用不匹配, 所以有必要研究面向对象数据库系统的计算模式。面向对象系统中有大量频繁使用的操作, 如给对象发送消息、根据对象标识决定物理位置等, 识别这些操作, 再进行优化实现对面向对象数据库系统性能的改善有重要意义。考虑新、旧技术的接轨问题, 面向对象数据库技术也不例外。异构数据库系统是面向对象数据库和传统数据库接轨的重要途径, 任的关键技术。也是面向对象数据库系统站稳脚跟所必需的。面向对象数据库应具有很强的建模能力, 可以在单一共同模型下支持网状、层次、关系等数据模型, 面向对象设计和编程则应提供可扩充性, 用来设计和实现能接纳新型数据库的异构数据库管理系统。
4. 要大力加强面向对象数据库的应用开发工具的研制和推广。面向对象数据库模型丰富的建模能力, 一方面能使用户建模容易, 另一方面也使面向对象数据库模式复杂, 所以, 对面向对象数据库系统来说, 仅有编程接口是不够的, 还需要有更高级的数据库工具。
5. 视图、演绎能力、语义建模和事务也是未来面向对象数据库系统应该具备的数据库特征。在关系数据库中, 视图可作为外部模式, 用于数据保护和简单查询;出于类似的理由, 面向对象数据库也需要支持视图的概念。说明性查询语言是关系数据库成功的关键因素之一, 所以具有演绎能力的面向对象数据库查询语言是一个重要的研究方面, 也是集成面向对象数据库和知识库技术的一个重要途径。许多语义建模概念, 如版本、复合对象等的语义会影响面向对象数据库的体系结构, 包括查询计值、存储结构、并发控制因而必须对面向对象教据库的核心模型进行扩充。
6. 加强面向对象数据库技术与关系数据库技术相结合的研究。面向对象数据库系统未来的发展趋势不是取代关系数据库系统, 而是与关系数据库技术相结合。新一代数据库系统应是包括面向对象特性的、与关系数据库系统兼容的成熟的数据库管理系统。
五、结束语
面向对象技术是近20年来计算机技术界和工业界研究的一大热点。面向对象方法与先进的数据库技术相结合已成为当今数据库领域研究和发展的主要方向之一。将面向对象技术应用到数据库系统中, 使数据库管理系统能够支持面向对象数据模型的数据库模式, 对提高数据库系统模拟和操纵客观世界的能力, 扩大数据库应用领域具有重要的意义;将面向对象技术应用到数据库的集成开发环境中, 使数据库应用开发工具能够支持面向对象的开发方法并提高相应的开发手段, 对提高应用软件的开发质量和软件的生产能力是十分重要的。从根本上讲, 面向对象数据库技术对复杂对象既要有极强的表达和建模能力, 又要有很强的存储和管理能力, 这正是传统数据库技术面向复杂工程数据所难以胜任的关键技术。
参考文献
[1] 李昭原, 邓佚.面向对象数据库技术及其最新动态.PC世界 . 1996.4
[2] 陈仲民, 王雪.面向对象数据库的索引技术.计算机工程与科学.2000年22卷6期
[3] 廖春维, 施伯乐.面向对象数据库系统的索引技术.计算机科学.24卷第6期