论文部分内容阅读
摘 要 本文基于Native XML数据库的特性，提出了一种自适应的优化索引方法，该方法能够根据XML数据文件的特点，结合ISP原理实现自动优化的KeyX索引。实验结果表明，它能有效地实时优化索引，保证XML数据库持续高效运行。
关键词 Native XML数据库 KeyX索引 ISP原理
中图分类号：TP311.131 文献标识码：A
Optimization of the XML Database Based on Index
TU Haiyan, ZOU Yunsong, LAI Xiang
(Military and Economics College, Wuhan, Hubei 430035)
Abstract Based on the characteristics of Native XML Database, an adaptive optimal indexing methods, the method according to the characteristics of XML data files, combined with the the ISP principle of automatic optimization KeyX index. The experimental results show that it can effectively real-time optimization of the index, to ensure that the XML database continued efficient operation.
Key words Native XML database; KeyX index; ISP principle
0 引言
Native XML数据库（Native Xml Database）是为XML数据量身定做的数据库，能在XML数据爆炸式增长时，对数据有效存储、查询和管理。Native XML数据库充分考虑到XML数据的特点，以一种自然的方式来处理XML数据，能够从各个方面很好的支持XML的存储和查询。它是现在唯一的纯XML数据库，应用十分广泛。
当XML数据比较庞大时，查询变得相当耗时，因此使用索引来加速查询十分必要。一般的Native XML数据库主要使用值索引、节点名索引、边或路径索引，其中值索引应用最为广泛。本文使用的KeyX索引是最新提出的值索引类型，它能提供通配符、多路径、范围查找等其它值索引类型所不具备的功能，该索引已开始逐步引入实际应用，并在不断地完善之中。通常情况下，数据库的索引是在开发阶段设计完成的，不能满足此后数据库的扩展需求，在XML数据库中尤为突出，所以对索引进行优化是非常有必要的。本文使用ISP（Index Selection Problem）原理对索引进行实时自动优化，保证XML数据库持续高效运行。
1 Native Xml数据库索引KeyX
KeyX是一种为Native XML 数据库量身订做的XML索引结构，KeyX还能够提供通配符、多路径、范围查找等其它值索引结构所不具备的功能。对一组频繁使用的查询表达式，从其查询的原XML数据中提取相关关键词，并将其存储在一个经过优化的搜索结构中，以便于以后能对关键词进行高效的检索，这些搜索结构包括哈希表、Tries、B+Tree等。
创建索引的过程如下。XPath表达式： = // [ = ]，将所有author的内容与对比，并将所有在路径///中的author元素作为关键词从XML数据中提取出来。每一个关键词都和XML数据中的一个或多个节点（元素或属性）有关。实验结果表明，KeyX将XML数据查询速度提高了105~106倍，并且随着XML数据量的增大，加速能力将更强。
2 利用ISP原理优化Native Xml数据库索引
定义合适的索引对优化数据库非常必要。为使索引能满足日后数据库扩展的需要，本文使用了ISP原理进行优化。所有的数据库操作都将以包的形式记录下来，即工作量workload，记为，每次对XML数据库的操作（operation, = ）所使用的路径表达式，被查询优化器定义为一组“备选索引”，这些“备选索引”能够有效地加速对数据库的操作。
与一般索引结构不同的是，“备选索引”不是由编码而来的，它是由查询优化器提取出来。表达式具有三种类型：第一种由关键词和路径组成，记为，如//，这种类型使用最多；第二种是带通配符的路径，记为，如//*；第三种由纯路径组成，记为，如//。在使用中根据实际需要选取提取方法。
由于工作量是由索引决定的，所以我们在考察时，只需分析所有的索引即可，记（Total Index Candidate） = ，由所有和工作量相关的索引组成。
当对数据库进行操作时，中的特定索引被激活，称此动作为索引配置（index configuration），记为，记所有可能的索引配置集合为。每次激活索引，累积组合将导致新的索引配置，根据ISP复杂度定义可得，|| = 2||。
由ISP原理：
(1)（下转第139页）（上接第122页）
其中为经ISP优化的索引配置，为每次进行操作所需的时间，为进行操作所需的存储空间（包括内存）。
并非所有索引配置都直接在数据库管理系统中创建，查询优化器需要根据XML数据中的相关关键词来预估时间和空间的需求，再由ISP在数据库管理系统中创建索引。
3 Native XML数据库索引优化实验结果及分析
本文建立的操作模型如图1所示。其中XDBMS使用Native XDBMS Infoyte DB V3，用来存储XML数据，Infoyte DB 内嵌了一个XPath查询引擎，通过查询优化器调用。当一个操作需求到来后，查询优化器对此操作进行处理，预估查询表达式并在KeyX索引存储器中检查是否有合适的索引，如果存在，就根据索引来加速查询；如果不存在，则转到XPath引擎处理。在实验中我们使用B+树作为KeyX索引存储器里的搜索树。索引选择工具（Index Selection Tool, ISP Tool）在数据库操作期间会被周期性的触发，然后根据操作需求找到一个尽可能好的索引配置。计算此操作的工作量并交由ISP Tool和查询优化器建立通信，由两者共同决定查询表达式以及假设的索引配置。经过此计算和优化过程后，查询优化器将此索引存储到KeyX索引存储器中。
图1 Native XML数据库索引优化实验模型
实验中，我们使用的XML文档大小为26M，包含58万个节点，实验用计算机配置：CPU C4 2.4G/内存512M/硬盘80G。软件平台：Visual C#， Native XDBMS Infoyte DB V3。建立了27个不同的基于XPath的数据库操作，为每一个表达式提供了一个备选索引，在初始化阶段，我们随机选择其中25个数据库操作。通常情况下，有些操作可能会被多次选中，有的则可能一次都未被选中。另外，每一个操作可能会通过预先定义的优化比进行修改。为进一步测试该系统的自适应优化特性，在程序持续运行当中，我们通过一个delta算法创建一个XPath查询，并将其与原27个操作的其中一个进行替换，保持27个操作总数不变。delta算法进行的操作能保证整个工作量较小地、随机地变化，这个算法能对现实数据库操作进行模拟。由于每次工作量变化微小，我们每进行30次数据库操作后调用一次ISP Tool。在实际应用中可根据需要将参数ispFrequency进行调整。
实验结果证明本文提出的方法能有效地自适应优化XML数据查询，不再需要人工定义和维护索引，在设计XML文档时也不需要使用DTD或XML Schema定义格式，而是通过系统的自适应、自优化功能完成索引的维护。应用于Native XML数据库索引类型较多，尽管本文仅对提出的KeyX索引进行了优化研究，但本文的方法也可推广到其它类型索引的优化之中。
参考文献
[1] B. C. Hammerschmidt, M. Kempa, and V. Linnermann. A selective key-oriented xml index for the index selection problem in xdbms. Proceedings of the 15th International Conference on Database and Expert Systems Applications - DEXA ’04. 2005
[2] IBM Corporation. IBM DB2 XML Extender. URL: http://www-3.ibm.com/software/data/db2/extenders/xmlext/.
[3] Infonyte GmbH. InfoNyte DB. URL: http://www.infonyte.com.
[4] 万常选.XML数据库技术.北京:清华大学出版社,2005.
[5] 向科峰,郑晓莉.基于TPR树的索引技术研究.电脑知识与技术,2005(36).
[6] 陈婕.基于XML的数据库统一的研究.硅谷,2008(11).
[7] 袁正午,程淼.时空数据库查询研究（英文）.重庆邮电学院学报(自然科学版),2006(4).
关键词 Native XML数据库 KeyX索引 ISP原理
中图分类号：TP311.131 文献标识码：A
Optimization of the XML Database Based on Index
TU Haiyan, ZOU Yunsong, LAI Xiang
(Military and Economics College, Wuhan, Hubei 430035)
Abstract Based on the characteristics of Native XML Database, an adaptive optimal indexing methods, the method according to the characteristics of XML data files, combined with the the ISP principle of automatic optimization KeyX index. The experimental results show that it can effectively real-time optimization of the index, to ensure that the XML database continued efficient operation.
Key words Native XML database; KeyX index; ISP principle
0 引言
Native XML数据库（Native Xml Database）是为XML数据量身定做的数据库，能在XML数据爆炸式增长时，对数据有效存储、查询和管理。Native XML数据库充分考虑到XML数据的特点，以一种自然的方式来处理XML数据，能够从各个方面很好的支持XML的存储和查询。它是现在唯一的纯XML数据库，应用十分广泛。
当XML数据比较庞大时，查询变得相当耗时，因此使用索引来加速查询十分必要。一般的Native XML数据库主要使用值索引、节点名索引、边或路径索引，其中值索引应用最为广泛。本文使用的KeyX索引是最新提出的值索引类型，它能提供通配符、多路径、范围查找等其它值索引类型所不具备的功能，该索引已开始逐步引入实际应用，并在不断地完善之中。通常情况下，数据库的索引是在开发阶段设计完成的，不能满足此后数据库的扩展需求，在XML数据库中尤为突出，所以对索引进行优化是非常有必要的。本文使用ISP（Index Selection Problem）原理对索引进行实时自动优化，保证XML数据库持续高效运行。
1 Native Xml数据库索引KeyX
KeyX是一种为Native XML 数据库量身订做的XML索引结构，KeyX还能够提供通配符、多路径、范围查找等其它值索引结构所不具备的功能。对一组频繁使用的查询表达式，从其查询的原XML数据中提取相关关键词，并将其存储在一个经过优化的搜索结构中，以便于以后能对关键词进行高效的检索，这些搜索结构包括哈希表、Tries、B+Tree等。
创建索引的过程如下。XPath表达式： = // [ = ]，将所有author的内容与对比，并将所有在路径///中的author元素作为关键词从XML数据中提取出来。每一个关键词都和XML数据中的一个或多个节点（元素或属性）有关。实验结果表明，KeyX将XML数据查询速度提高了105~106倍，并且随着XML数据量的增大，加速能力将更强。
2 利用ISP原理优化Native Xml数据库索引
定义合适的索引对优化数据库非常必要。为使索引能满足日后数据库扩展的需要，本文使用了ISP原理进行优化。所有的数据库操作都将以包的形式记录下来，即工作量workload，记为，每次对XML数据库的操作（operation, = ）所使用的路径表达式，被查询优化器定义为一组“备选索引”，这些“备选索引”能够有效地加速对数据库的操作。
与一般索引结构不同的是，“备选索引”不是由编码而来的，它是由查询优化器提取出来。表达式具有三种类型：第一种由关键词和路径组成，记为，如//，这种类型使用最多；第二种是带通配符的路径，记为，如//*；第三种由纯路径组成，记为，如//。在使用中根据实际需要选取提取方法。
由于工作量是由索引决定的，所以我们在考察时，只需分析所有的索引即可，记（Total Index Candidate） = ，由所有和工作量相关的索引组成。
当对数据库进行操作时，中的特定索引被激活，称此动作为索引配置（index configuration），记为，记所有可能的索引配置集合为。每次激活索引，累积组合将导致新的索引配置，根据ISP复杂度定义可得，|| = 2||。
由ISP原理：
(1)（下转第139页）（上接第122页）
其中为经ISP优化的索引配置，为每次进行操作所需的时间，为进行操作所需的存储空间（包括内存）。
并非所有索引配置都直接在数据库管理系统中创建，查询优化器需要根据XML数据中的相关关键词来预估时间和空间的需求，再由ISP在数据库管理系统中创建索引。
3 Native XML数据库索引优化实验结果及分析
本文建立的操作模型如图1所示。其中XDBMS使用Native XDBMS Infoyte DB V3，用来存储XML数据，Infoyte DB 内嵌了一个XPath查询引擎，通过查询优化器调用。当一个操作需求到来后，查询优化器对此操作进行处理，预估查询表达式并在KeyX索引存储器中检查是否有合适的索引，如果存在，就根据索引来加速查询；如果不存在，则转到XPath引擎处理。在实验中我们使用B+树作为KeyX索引存储器里的搜索树。索引选择工具（Index Selection Tool, ISP Tool）在数据库操作期间会被周期性的触发，然后根据操作需求找到一个尽可能好的索引配置。计算此操作的工作量并交由ISP Tool和查询优化器建立通信，由两者共同决定查询表达式以及假设的索引配置。经过此计算和优化过程后，查询优化器将此索引存储到KeyX索引存储器中。
图1 Native XML数据库索引优化实验模型
实验中，我们使用的XML文档大小为26M，包含58万个节点，实验用计算机配置：CPU C4 2.4G/内存512M/硬盘80G。软件平台：Visual C#， Native XDBMS Infoyte DB V3。建立了27个不同的基于XPath的数据库操作，为每一个表达式提供了一个备选索引，在初始化阶段，我们随机选择其中25个数据库操作。通常情况下，有些操作可能会被多次选中，有的则可能一次都未被选中。另外，每一个操作可能会通过预先定义的优化比进行修改。为进一步测试该系统的自适应优化特性，在程序持续运行当中，我们通过一个delta算法创建一个XPath查询，并将其与原27个操作的其中一个进行替换，保持27个操作总数不变。delta算法进行的操作能保证整个工作量较小地、随机地变化，这个算法能对现实数据库操作进行模拟。由于每次工作量变化微小，我们每进行30次数据库操作后调用一次ISP Tool。在实际应用中可根据需要将参数ispFrequency进行调整。
实验结果证明本文提出的方法能有效地自适应优化XML数据查询，不再需要人工定义和维护索引，在设计XML文档时也不需要使用DTD或XML Schema定义格式，而是通过系统的自适应、自优化功能完成索引的维护。应用于Native XML数据库索引类型较多，尽管本文仅对提出的KeyX索引进行了优化研究，但本文的方法也可推广到其它类型索引的优化之中。
参考文献
[1] B. C. Hammerschmidt, M. Kempa, and V. Linnermann. A selective key-oriented xml index for the index selection problem in xdbms. Proceedings of the 15th International Conference on Database and Expert Systems Applications - DEXA ’04. 2005
[2] IBM Corporation. IBM DB2 XML Extender. URL: http://www-3.ibm.com/software/data/db2/extenders/xmlext/.
[3] Infonyte GmbH. InfoNyte DB. URL: http://www.infonyte.com.
[4] 万常选.XML数据库技术.北京:清华大学出版社,2005.
[5] 向科峰,郑晓莉.基于TPR树的索引技术研究.电脑知识与技术,2005(36).
[6] 陈婕.基于XML的数据库统一的研究.硅谷,2008(11).
[7] 袁正午,程淼.时空数据库查询研究（英文）.重庆邮电学院学报(自然科学版),2006(4).