一种快速执行可扩展样式表单语言转换的方法

技术领域

本发明属数据库技术领域，具体涉及一种新颖的快速执行可扩展样式表单语言转换(XSLT)的方法。采用该方法，可以快速、高效地将XML文件转换成为文本文件、HTML文件或者其它格式的XML文件。

背景技术

XML(可扩展标记语言)是一种元语言，也是一种基于文本的标记语言。它是标准通用标记语言的一个子集。XML包含一组基本规则，任何人都可以利用这种规则创建针对特定应用领域的标记语言，这些标记并不描述信息的显示方式，而是信息本身。它允许标记元素类型、元素嵌套、以及元素之间的引用等。XML标准的制定大大促进了Web(互联网)的发展，它将成为下一代Web的基础。

随着越来越多的公司在他们的数据管理和数据交换策略中采用XML作为数据表示和交换的标准，在很多操作系统平台上都开始提供能够处理XML数据的工具。XSLT(可扩展样式表单语言转换)作为W3C组织制定的一个标准，已经得到了很多的软件工具支持。XSLT是一种用来进行转换的语言，使用起来非常方便，所以很多开发人员非常乐意采用它来处理XML数据。目前已经有了一些可以单独运行的XSLT转换引擎，比如SAXON，XALAN，还有微软公司的MS XML等。开发人员使用这些工具，可以将XML数据转换为HTML(超文本标记语言)文件或者其它格式。

在生物信息等应用领域中，人们常常采用XML来表示大规模数据。这样得到的XML数据文件往往非常大。目前已有的XSLT引擎只能处理小的XML文档，当文档较大时，它们的执行性能下降得非常快。这些XSLT引擎内部几乎没有采用任何优化技术，在执行转换之前，它们需要将整个XML源文档读取到内存当中。内存中的数据结构是一个树型结构，因为需要记录节点之间的指针等附加信息，所以其大小是源文档的好几倍。在处理很大的XML文档时，需要消耗非常多的内存。当物理内存不够使用时，系统就要大量使用虚拟内存。对虚拟内存的过度使用是导致系统性能下降的最关键原因。

发明内容

本发明的目的在于提出一种执行XSLT转换的高效方法。该方法保证在使用较少内存的情况下，能够处理非常大的XML文档。

本发明提出的快速执行XSLT转换方法，是通过一个流处理模型来执行XSLT转换。扫描MML源文档，通过该流处理模型，XML源文档的结构信息已知(用文档类型定义DTD来表示)，一个XSLT转换程序被转化成为很多个事件处理器。在从头到尾读取XML源文档的过程中会触发很多事件，对每一类事件，都有一个对应的输出片断；最开始的时候，结果文档为空，随着对源文档的扫描过程的进行，相应事件的输出片断被逐渐添加到已产生的结果文档的后面；在扫描过程结束后，用户马上就可以得到最终完整的结果文档。在所述流处理转换模型中，每一类事件的输出片断可能是一个常数字符串，当前叶子节点的PCDATA值，或者是二者的串接。所以，在转换的过程中，并不需要额外的缓存区来存放中间结果。

1.与本发明有关的一些基本概念

文档类型定义DTD：

XML文档的结构可以用DTD(文档类型定义)来表示，而DTD可以表示为一棵有序树的形式，称为DTD树。如图1所示，树根表示XML文档的根元素，其他节点分别对应于DTD中的一个元素类型，节点间的父子关系对应于DTD元素间的嵌套关系。一个节点的所有孩子节点从左到右排序。

XSLT转换程序：

一个XSLT程序L包含很多模板规则，每条模板规则由模式和模板两个部分组成，其中模式表示该规则的匹配模式，而模板表示该规则对应事件的输出模板。输出模板是一个序列，每个序列元素或者是常数字符串，或者是调用其他模板规则的应用模板命令。假定已经将相邻接的常数字符串串接，因此在输出模板中，不会再出现连续两个常数串的情况。一个XSLT转换程序(示例1)如下：

　　＜xsl：template match＝″/″＞　　 ＜html＞＜head＞＜title＞Books Information＜/title＞＜/head＞　　＜body＞＜table＞　　 ＜xsl：apply-templates select＝″publication/book″/＞　　＜/table＞＜/body＞　　 ＜/html＞　　＜/xsl：template＞　　＜xsl：template match＝″book″＞　　 ＜tr＞＜td＞＜xsl：apply-templates select＝″title″/＞＜/td＞　　＜td＞＜table＞　　＜xsl：apply-templates select＝″author″/＞　　＜/table＞＜/td＞　　 ＜/tr＞　　＜/xsl：template＞　　＜xsl：template match＝″author″＞　　 ＜tr＞＜td＞＜xsl：apply-templates select＝″name″/＞＜/td＞＜/tr＞　　＜/xsl：template＞　　＜xsl：template match＝″title″＞　　 ＜xsl：value-of select＝″.″/＞　　＜/xsl：template＞　　＜xsl：template match＝″name″＞　　 ＜xsl：value-of select＝″.″/＞　　＜/xsl：template＞

SAX编程接口：

当使用XML解析器来解析XML文档时，它将触发一系列事件以驱动应用程序。基于事件的SAX接口(针对XML的简单编程接口)通过回调方法向应用程序报告XML文档解析过程中的事件，比如一个元素的开始或者结束等。用户程序要具体实现这些回调函数来处理不同的事件。本发明将把XSLT转换程序转化成一系列事件处理器。

2.转换树及其构造

在XSLT转换程序中，每一条模板规则或者应用模板命令将匹配源XML文档中的一个节点或者一组兄弟节点，所以它们对应于DTD树中的唯一一个节点。为了将XML文档的结构信息和XSLT转换要求结合在一起来考虑，本发明提出了转换树的概念。本质上，转换树是经过扩展了的DTD树。图2是转换树的一个例子，它结合了图1中的DTD和上述XSLT转换程序(示例1)的信息。在转换树中，圆形节点表示一个元素类型，而矩形节点表示来自于XSLT转换程序中的一个常数字符串，虚线表示调用某一应用模板命令，实线表示元素之间的父子关系。下面对转换树进行具体定义。

给定待转换文档的DTD和一个XSLT转换程序，对应的转换树是一棵有序树。该有序树包含两类节点，元素节点和常数字符串节点。在转换树中，存在三类边。第一类边表示元素之间的父子关系，由实线来表示；第二类边连接元素节点和常数字符串节点，由点划线表示；第三类边表示调用和被调用关系，用虚线表示。前面两类边是根据DTD中的信息构造出来，而第三类边是根据XSLT转换程序得到。

为了方便下文讲述构造转换树的步骤，首先给出几个术语的定义。XSLT转换程序中的每一条模板规则r_i将匹配DTD树中的一个节点，称该节点为r_i的匹配节点，记为mnode(r_i)。r_i的输出模板是一个序列(o_i1，o_i2，...，o_it)，如果o_ij是应用模板命令，它也会选中DTD树中的唯一一个节点，称其为o_ij的选中节点，记为selnode(o_ij)。

构造转换树的步骤如下：首先构造XML文档类型定义的DTD树T；考察XSLT转换程序L的每一条转换规则r，在T中找到r的匹配节点n；继续考察r的输出模板序列中的每一个元素o，如果o是一个常数字符串，为树T创建一个叶子节点n’，添加一条从n到n’的边；如果o是调用模板命令，从树T中找到o的选中节点n’，同样添加一条从n到n’的边。

3.流处理模型及其建立

下面介绍流处理模型(SPM)。对每一个事件e，不管它是元素标签开始事件，还是元素标签结束事件，都有一个输出片断和e对应。对于每一个元素开始事件，其输出片断start(e)是一个常数串。对非叶子节点的元素结束事件，其输出片断end(e)也是一个常数串。但是，叶子节点的元素结束事件和上面的情况不一样。对于每一个这类事件，其输出片段是一个三元组(c₁，pcdata，c₂)，其中c₁和c₂是常数串，pcdata表示当前叶子节点的PCDATA值，可能为空。

在将源XML文档用XSLT程序转换的过程中，会产生一个事件序列。所有这些事件的输出片断按照先后顺序串接起来，也就是转换后的结果文档。在扫描源文档的过程中，新产生的输出结果将被逐渐添加到先前产生结果的尾部。所以，在得到完整的结果文档之前，处理引擎可以先输出前面的一部分结果。

从转换树得到流处理模型的步骤如下所示：建立流处理模型是一个递归的过程，对转换树的任一节点n，end(n)，start(n)初始值为空串；如果n是叶子节点，则令end(n)：＝pcdata+end(n)；以c₁，c₂，...，c_p表示节点n下面所有来自于DTD树的孩子节点，p为该孩子节点个数，以d₁，d₂，...，d_q表示节点n下面所有来自于XSLT转换程序的孩子节点，q为该孩子节点数，如果d₁是一个常数字符串节点，则令start(n)：＝start(n)+d₁，并且设置计数器i为2，否则，设置计数器i为1；当i不大于q的时候，重复以下步骤：假设c是位于从节点n到节点d_i这条路径上的n的孩子节点，如果从n到c的边没有被星号标记，并且d_i+1是常数串节点，则令end(c)：＝end(c)+d_i+1和i：＝i+2，否则令i：＝i+1；如果d_i+1是常数串节点，假设c′是位于从节点n到节点d_i+2这条路径上的n的孩子节点，则令start(c′)：＝d_i+1+start(c′)和i：＝i+2，否则令i：＝i+1；对每一个孩子节点d_j，递归调用以上过程。

看一个具体的例子，图2中的转换树对应的流处理模型示例如下所示：

start(publication)＝″<html>...<table>″

end(publication)＝″</table>...</html>″

start(book)＝″<tr><td>″

end(book)＝″</table></td></tr>″

end(title)＝concat(PCDATA value of title，″</td><td><table>″)

begin(author)＝″<tr><td>″

end(name)＝concat(PCDATA value of name，″</td></tr>″)

综上所述，本发明提出的快速执行XSLT转换的方法，是通过一个流处理模来执行XSLT转换，具体步骤如下：

(1)首先通过构造转换树，将XML源文档的结构信息和XSLT转换要求结合起来；

(2)从转换树建立流处理模型，它是一个递归过程；

(3)扫描XLM源文档，通过流处理模型，在从头到尾读取XML源文档的过程中会触发很多事件，对每一类事件，都有一个对应的输出片断；最开始的时候，结果文档为空，随着对源文档的扫描过程的进行，相应事件的输出片断被逐渐添加到已产生的结果文档的后面；在扫描过程结束后，用户马上就可以得到最终完整的结果文档。

在本发明中提出的流处理模型中，每一个元素开始和结束事件都有一个输出片断对应。在扫描源文档的过程中，将会产生很多输出片断。在转换源文档的过程中，没有额外的缓存开销。在源数据还没有完全读完之前，就可以输出结果文档的开始部分。所以，即使给定一个非常大的XML数据实例，本发明方法也能通过一趟扫描完成转换过程。本发明方法中的流处理模型完全避免了现有转换引擎需要预先将整个源文档载入内存的缺陷，减少了内存消耗，极大地提高了执行效率。同时，流处理模型具有很好的可扩展性，在配置有256M内存的普通个人电脑上，能够处理500M以上甚至几个G的XML数据。

例如，对于上述流处理模型，在扫描源XML文档并利用SAX接口来解析的过程中，每次遇到publication元素的开始，将输出<html>...<table>；每次遇到book元素的开始，将输出<tr><td>；每次遇到title元素的结束，将首先输出该title元素的叶子值，然后输出</td><td><table>；...。所有这些单个事件的输出串接起来，即为最终的结果文档。

附图说明

图1为一棵DTD树。

图2是结合图1中的DTD和示例1中的XSLT转换程序的转换树。