基于模型检查的XML Schema特征提取

XQuery用于查询XML文档,对XQuery查询优化有助于提高查询效率,有重要的研究意义。树模式把XQuery表示成树结构的查询,如何基于XML Schema对树模式进行优化是当前的研究热点,需要利用XML Schema的一些特征进行树模式优化,因此如何自动提取XML Schema的特征是需要解决的问题。提出基于模型检查的XML Schema特征提取方法。首先把XML Schema转换成Schema图,进而转换成模型检查器NuSMV的输入模型,从而可以对时态逻辑公式表示的XML Schema特征进行检查,提取的孩子关系以及子孙关系特征可以用于树模式优化。

XML Schema特征提取算法

Twig模式最小化作为XML查询优化的一个重要方面,由于在进行最小化的过程中通常要利用XML Schema中的约束信息,因此被称为Schema特征。为了简化运用传统方法提取Schema特征的过程,以及确保提取过程的正确性,提出了一种自动提取Schema特征的模型检查算法。在Schema的形式模型的基础上,利用扩展的CTL公式表示Schema特征,提出算法以检查Schema模型是否满足要求的特征。由于扩展了CTL公式,所提算法不但可以检查孩子、子孙等前向的Schema特征,而且可以检查双亲、祖先等后向特征。最后,实现了支持该算法的模型检查器。