高志军（邢台金牛玻纤有限责任公司，河北 邢台 054000）

1 引言

随着XML应用领域的不断扩展，越来越多的数据使用XML进行表示和交换，如何实现XML查询的重写优化相应成为查询重写优化研究的一个热点。由于多数半结构化和XML查询语言，例如Lorel[1]、Quilt[2]、XML-QL[3]和XQuery[4]等都是基于正则路径表达式的，故对正则路径表达式的重写优化是实现XML查询重写优化的基础。

目前，XML查询重写取得了很大进展，对XML数据检索[5]和访问控制[6]中的查询重写以及在已知XML文档模式的情况下，如何使用XML查询回答技术进行信息搜索[7]等问题都有比较深入的研究。同时，针对XML文档在Oracle数据库中的存储和查询，也有了更为成熟的成果[8]。

但是就正则路径表达式的重写而言，多数研究工作仍局限于单个正则路径表达式的重写[10]。由于在实际应用中，存在大量正则路径视图，而且用户查询往往含有多个正则路径表达式，这就提出了一个如何使用正则路径视图重写含有多个正则路径表达式的XML查询问题。

2 基本概念

一篇XML文档可以用带有根节点的标签图表示，称为XML数据图，记为Gd。其中，XML文档的元素和数据值分别用Gd的非叶子节点和叶子节点表示，元素—子元素、元素—属性及引用关系用Gd中标有相同名字的边表示。图1给出了一个XML数据图实例。形式上，设O为Gd的节点对象ID集，C为Gd的标签常量集则有如下定义[9]：

定义1（正则路径表达式） 正则路径表达式（regular path expression）由语法递归定义构成。其中，r、r1和r2均为正则路径表达式，ε表示空串，a∈C表示标签常量，_表示任意一个标签。……