王晓燕

（太原大学，山西太原 030009）

XML己经成为Internet上数据的表示标准和交换工具，然而XML数据的一个明显特征是数据冗余较大，冗余既造成了存储空间的浪费，又增加了查询处理的时间，降低了效率。目前，减小XML文档大小的一种有效的方法就是压缩，但是压缩后的XML文档需要解压后才能对其进行验证、查询等操作。

众所周知，XML获得广泛应用的关键是XML数据资源的查询与检索。所以，研究XML数据的检索和查询自然就成了世界性的热门课题。

1 索引模块的设计

搜索引擎的索引部分是整个搜索引擎最关键的部分，衡量索引的好坏主要看它本身占据多少额外的磁盘空间和查询时的检索速度。在对XML文档数据建立索引时，根据需要，设计一个索引模块，并给出一种新的倒排索引方法。

XML文档包括结构信息和内容信息，这些都要编入索引，把XML文档看成一棵树，树中的节点作为一个基本的存储单元，每个节点有一个唯一的标识符，这个标识符是由解析模块中的节点编码器分配的，将其简记为Id，其标识符为一个编码，形式为（start，end）。

XML文档经过节点编码器后生成DOM（文档对象模型）树，再经过节点结构构造器后产生的节点结构仍是一颗树，树的最下一层是叶子节点，即文本部分，其余都是中间节点，即结构部分。

索引采用倒排表的方式来实现，本文共设计了三种索引表。

1.1 文档结构表

一篇读入的XML文档，经过节点结构构造器后，解析为一个树状结构，索引器首先建立这样一个表，即文档结构表，用来存放每篇文档的结构。

文档Id即该文档的编码，由文档加入数据库的次序决定，从零开始编码，表中每个节点的数据结构为节点结构结构器已经构造的节点结构。以先序遍历的顺序存储文档树，遇到Id编码的两个值相等的情况不予存储，即不存储叶子节点。

1.2 文档信息表

文档的结构索引是用来提高查准率，体现面向XML文档索引的优势的，还应该有一个表，记录文档的一些基本信息，如地址、主题等。

1.3 关键词索引表

用户查询一般情况下都是输入关键词，所以关键词索引表是非常重要的，这部分属于内容索引。将叶子节点处的文本内容进行处理，去掉无意义的词，提取关键词。对文档空间中的所有关键词，在关键词索引表中都建立一条相应的记录。这些词按字母顺序存放，可加快查找速度。在关键词索引表中，每个文档按与关键词的相关度排序记录，每插入一个新的文档，也要计算其与关键词的相关度，并插入到相应的位置。相关度按照一定的算法算出。

2 利用高频路径产生索引机制

高频路径的所有子连续路径也是高频路径，所以要对算法得到的高频路径扩展（找出所有高频路径的子连续路径）以得到全部的高频路径。

对文档库用路径查找算法得到的高频路径的集合为:

再经过扩展得到的所有高频路径的集合为:

然后将这些路径视为一个regular set，通过自动机的转换，产生最小化有限状态机（MFA），作为索引构造的条件。

3 关系型数据和XML结构转换

XML是层次结构的，它可以对非关系型的数据进行编码。但是，目前服务器上维护的数据来自关系型数据库，关系数据库的基本组成单位是表，这里定义一个映射实现表和XML数据文档之间的转换。

我们可以建立数据库模式（database schema）和XML数据模式（xml schema）之间的映射关系，实现信息的转化。需要注意的是当XML文档不是由数据库中导出，而是由应用程序来指定XML文档的数据结构时，从XML数据模式映射到数据库模式时存在一些问题:首先是映射到表的时候需要将字段的数据类型设定，DTD文档无法准确定义元素的数据类型，在引入schema之后可以解决此问题。其次在XML文档中，大小写是区分的，而在数据库中大小写是不区分的，假如在XML文档中存在两个PCDATA的元素，它们的名称除了大小写不同外都一样，则转换程序会将其转换成两个字段，这会导致在数据库中错误的发生;另外XML数据是有顺序的，而数据库中的数据是无序结构表达的，办法之一是添加一个sort字段。

消除查询表达式中出现的#。一般地，正则表达式E1#E2匹配从E1开始，经一条或多条边到达E2的所有路径。消除#需遍历整个映射图，将映射图中以E1为起点，E2为终点的子图转化为与之等价的正则表达式。将一个图转化为正则表达式的问题是一个已知问题，采用适当的算法我们可以将表达式中的#部分转化为与之匹配的映射子图对应的正则表达式，从而消除#。

将XML查询转换为关系系统中的查询过程为:首先将XML查询中的变量消去，把正则路径表达式重写为简单路径表达式，再将SPE表达式的查询转化SQL查询。

4 XML数据库事务处理和版本控制

XML数据库一般提供事务处理功能，包括提交、撤回和日志文件，也包含对XML文档的版本控制功能。

事务为数据库的一组操作，这些操作组成一个逻辑单元。事务遵循的ACID性质（原子性、一致性、独立性和持久性），通过提供事务日志机制，纪录系统执行的每个事务的详细情况，保证事务处理稳定地运行和系统出现问题后完全恢复。

处于版本控制之下的文档都有自己的历史信息，纪录修改文档的作者以及时间等，使用者可以根据文档或用户或日期来查看整个的版本历史信息。XML数据库版本控制，允许用户通过查询更新原信息，用户应用程序可以检入 或检出XML文档，利用版本号、日期或者标签获得以前版本的文档，以及显示XML文档的版本历史信息。版本控制允许用户查询更新原信息，通过更新引擎注释、修改和精炼信息。内置的版本系统跟踪信息的变化，提供这些变化的历史信息。

5 基于XML的路径查找算法

在XML文档中，所有的信息都存储在叶子节点处。信息的存取是由根节点沿着某路径（path）到叶子节点完成的。可以把XML文档看作成树状结构，节点间存在一种次序（order）关系。用搜索连续路径的方法，快速检索出文件中重要的连续路径。

XML的路径查找算法，使用二维Hash table存储事务，一边是含有事务节点名称的hash array，可加快路径搜索的速度;另一边是含有事务长度的length list所构成的array，以便在查找时找到当前的最长路径。

［1］吴敏，徐德智，N Damas.基于离散模式的XML数据查询的 CSP 实现［J］.计算机应用，2011，23（4）:31-34.

［2］徐德智，H.Sidi..基于树模型的XML查询［J］.企业技术开发，2009（4）:7-8.

［3］吕建华，王国仁，于戈.XML数据的路径表达式查询优化技术［J］.软件学报，2010，14（9）:1615-1620.

［4］吴敏，徐德智，陈学工.XML模式蕴含及查询优化研究［J］.计算机应用，2011，11（8）:7-30.

［5］万常选，刘云生，徐升华，等.基于区间编码的XML索引结构的有效结构［J］.计算机学报，2005（1）:113-127.