基于Schema路径约束的Twig模式最小化方法*

张　岩　廖湖声

(北京工业大学计算机学院　北京　100124)



基于Schema路径约束的Twig模式最小化方法*

张岩廖湖声

(北京工业大学计算机学院北京100124)

近年来,Twig查询是XML查询的核心操作。查询请求中的查询模式通常包含一些冗余的子查询,因此,Twig模式最小化成为了研究的热点。针对特定的Schema信息可能带来Twig模式优化的特征,在现有Twig模式最小化的基础上,提出了一种基于路径约束的Twig模式优化方法,归纳出一套的优化规则,不但可以优化Twig模式中冗余的叶节点,也可以优化冗余的中间节点。

树模式最小化; 模式约束

Class NumberTP391

1　引言

XML因其具有半结构化,灵活性强,跨平台等特点,已经成为了互联网数据存储与交换的标准,并广泛地应用到了XML数据库[1～2]以及流数据查询处理领域[3～5]。针对半结构化的XML数据查询,往往表现为一种树状的查询模式,被称为树模式[6],或Twig模式(小枝模式)。鉴于Twig模式匹配是XML查询的核心操作,出现了各种Twig模式查询优化方法。

树模式查询的目的就是找出所有XML文档中满足树模式结构关系的元素。一类研究致力于寻找高效的数据结构与匹配算法[14～19],从而提高Twig模式查询匹配的效率。由于Twig模式查询匹配的效率和Twig模式本身的复杂程度关系密切,而Twig模式往往存在一些冗余的子查询。因此,一类研究致力于找出并删除Twig模式中冗余的子查询,如Twig模式最小化。

鉴于有些冗余的子查询仅仅存在于特定类型的XML数据中,而这些类型信息可以从DTD[7]、XML Schema[8]等类型描述中提取,被称为模式约束。模式约束可以分为两类,一类是后向约束[9～11];另一类是前向约束[12～13]。前者包括必然孩子、必然子孙等约束,后者包括必然双亲、必然祖先、兄弟节点等约束。

图1　Twig模式举例

上述模式约束的共同特征就是考虑了节点之间结构连接关系,然而Twig模式树形结构中的路径信息对于Twig模式的优化也是有用的。例如:图1(c)中的Twig模式Q2是查找同时拥有子孙节点B和子孙节点F的A节点,且B节点拥有C子孙节点,这个C节点拥有H孩子节点。如果Q2查询的数据库具有这种约束条件:若所有的c元素具有必然孩子h元素。那么Q2中的H节点就可以判定为冗余的。优化结果如图1(d)所示。然而,使用路径约束:若约束条件为经历路径a、b到达的c元素,该c元素满足。同样可以判定Q2中的H节点为冗余节点,而这种基于路径的模式约束更加具体化,为Twig模式提供了更多的优化机会。

已有的工作中提出的Twig模式的优化算法,均只针对特定的模式约束,且均不包含基于路径的模式约束。为了解决上述问题,本文提出了: 1) 一套可用于Twig模式最小化的模式约束集合,其中包括基于路径的模式约束; 2) 一套面向Twig模式最小化的优化规则集合,它不但可以优化Twig模式中的叶节点,还可以优化中间节点; 3) 本文通过实验证明了规则的有效性。

2　Twig模式最小化

Twig模式是一个由若干个节点组成的树型模型。在节点集合Q中,用于指定查询结果的节点被称为返回节点;在Twig模式中,存在两种边:孩子边和子孙边。为了描述方便,本文使用δ(a)来表示a节点的类型,用opt(Q)表示查询Q的返回节点集合,用pc(u,v)表示节点u到v之间是父子关系的边,用ad(u,v)表示u到v之间是子孙关系的边。如图1所示,在Twig模式中,单线边代表父子关系,双线边代表子孙关系,用*标记的节点为返回节点。

Twig模式查询结果就是Twig模式查询Q与XML数据库D匹配的结果。它是Q中的节点与D中的元素之间的一个映射,表示为,PD,满足映射的结果满足两个条件:

1) 节点类型一致:对于任何节点,u和P(u)的类型一致;

2) 边的类型需一致:如果在Q中存在pc(u,v),那么,在D中P(v)是P(u)的孩子;如果Q中存在ad(u,v),那么,在D中P(v)是P(u)的子孙。

Twig查询Q的返回结果就是{P(r)|ropt(Q)}。

Twig模式查询匹配的开销由Twig模式本身的大小以及复杂程度决定。Twig模式最小化就是试图找出并删除Twig模式中冗余的子查询。Twig模式可能存在冗余的子查询,通常由于: 1) 查询本身存在冗余的分支; 2) 查询本身不存在冗余分支,但参照XML数据库的类型信息后,有些分支变得冗余。

对于参照模式约束的Twig模式最小化问题,文献[9]给出了如下的描述:C是一个模式约束的集合,集合中包含三种约束,分别为必然孩子约束,必然子孙约束以及子类型约束。对于查询Q1和Q2,如果所有满足约束C的数据库D,有Q1(D)⊆Q2(D),那么将其表示为Q1(D)⊆CQ2(D)。如果Q1(d)⊆cQ2(D)并且Q2(D)⊆CQ1(D),那么说Q1和Q2在约束C下等价,表示为Q1(D)=CQ2(D)。判断在约束C下,查询Q是否是最小化的,就归结为查找是否还有更小规模的Q1,使得Q1(D)=CQ(D),如果没有,那么Q是最小化的,即不存在冗余分支。查询Q的规模定义为Q中节点的数量。

3　模式约束集合

基于Twig模式最小化的需求,在相关工作的基础上[9～13],定义了五种模式约束,如下:

必然孩子约束(表示为:a→b):每个a类型元素都必然有b类型的孩子元素。

必然子孙约束(表示为:a⟹b):每个a类型元素都必然有b类型的子孙元素。

必然父亲约束(表示为:a←b):每个b类型元素都必然有a类型的父亲元素。

必然祖先约束(表示为:a⟹b):每个b类型元素都必然有a类型的祖先元素。

必然兄弟约束(表示为:a→cb):每个具有b类型孩子元素的a类型的元素,都必然有c类型的孩子元素。

基于以上的五种约束,本文定义了包含简单XPath表达式的路径约束。XPath简单表达式是没有谓词的XPath表达式,它仅包含节点检测,孩子轴(‘/’)和子孙轴(‘//’)。

路径必然孩子约束(表示为:path/bind):其中,path是简单XPath表达式,bind是下面的模式约束之一:a→b、a⟹b、a←b和a⟸b。即path到达的子树中,孩子元素a和子孙元素b满足约束bind。

路径必然子孙约束(表示为:path//bind):其中,path是简单XPath表达式,bind是下面的模式约束之一:a→b、a⟹b、a←b和a⟸b。即path到达的子树中,子孙元素a和子孙元素b满足约束bind。

路径必然孩子兄弟约束(表示为:path/a→ⓒb):其中,path是简单XPath表达式。即path到达的子树中,孩子元素a,子孙元素b、c,它们三者满足约束a→cb。

路径必然子孙兄弟约束(表示为:path//a→cb):其中,path是简单XPath表达式。即path到达的子树中,子孙元素a、b、c,它们三者满足约束a→cb。

4　Twig模式冗余节点识别规则

上述模式约束特征集合用于Twig模式最小化中,本节提出一套判断冗余节点的规则,用于判断Twig模式中的冗余节点。假定Q是Twig模式,D是XML数据库,有以下规则成立:

规则1对于Q中的中间节点A和叶节点B,如果存在pc(A,B)边,且D满足δ(A)←δ(B),或者存在ad(A,B)边,且D满足δ(A)⟹δ(B);那么B节点只要不是返回节点就是冗余节点。

规则2对于Q中的节点S、A、B,如果节点A只有一个子孙节点,该节点为B,若A不是返回节点,若表1中的四种情况之一成立,则A为冗余节点。

表1　规则2成立条件

规则3对于Q中的节点A、B和叶节点C,如果存在pc(A,B)边和pc(A,C)边,并且D满足δ(A)→δ(C)δ(B),那么C节点只要不是返回节点就是冗余节点。

规则4如果一个简单XPath表达式path与Q中某个分支匹配,并且路径中最后一个节点为δ(A)类型,若Q中存在pc(A,B)边,且D满足path→δ(B),那么B节点只要不是返回节点就是冗余节点。

规则5如果一个简单XPath表达式path与Q中某个分支匹配,并且路径的最后一个节点为δ(A)类型。若Q中存在ad(A,B)边,且D满足path⟹δ(b)B,那么节点只要不是返回节点就是冗余节点。

规则6如果一个简单XPath表达式path与Q中某个分支匹配,节点A仅有一个后代节点,为A节点,若表2中的四种情况下之一成立,则A节点只要不是返回节点就是冗余节点。

表2　规则6成立条件

规则7如果XPath表达式path与Q中某个分支匹配,并且路径path的最后一个节点为δ(A)类型。如果Q中存在pc(A,B)边和pc(A,C)边,且D满足path→δ(C)δ(B),那么C节点只要不是返回节点就是冗余节点。

5　实验

本文做了一系列的实验,通过不同的测试案例来验证第4章规则的有效性。实验环境为一台配有Intel Core i7-2600 CPU和8G内存的工作站,其上运行Windows 10操作系统。本文根据不同场景,编写了不同的XML Schema测试集合。该测试集合包含7个文件(表3中的“s1.xsd - s7.xsd”)。针对不同的schema文件,使用不同结构的Twig模式进行测试(为了方便表示,使用XPath语言表示Twig模式)。另外,使用优化的TwigList算法,测试了Twig模式在优化之前和之后的查询时间对比。

表4展示了优化前后的Twig模式,通过观察可以发现,我们的优化规则不但可以优化Twig模式中的叶节点,同时可以优化中间节点。表4中名为“Twig模式规模”的列,展示了优化前后,Twig模式中节点个数的对比,可以看到,Twig模式被优化后,节点规模成下降趋势。表4中,名为“查询时间”的列给出了Twig模式在被优化前后,执行的具体时间。名为“加速比”的列给出了优化前后,查询执行时间的加速比。通过对比,发现优化的Twig模式可以提高Twig模式查询效率。

表3　测试案例

表4　测试结果

6　结语

基于现有的参照模式约束的Twig模式最小化的工作中两类基本的模式约束集合,本文通过扩展这两类基本的特征约束,提出了基于路径的特征约束集合,为Twig模式最小化带来了更多的优化机会。基于各种Schema特征,本文提出了一套面向Twig模式最小化的优化规则,不但可以优化Twig模式中冗余的叶节点,而且可以优化中间节点。一系列实验已经验证了这些优化规则的有效性。

[1] 万长选,刘喜平.XmL数据库技术[M].北京:清华大学出版社,2008.

WAN Changxi, LIU XiPing. XmL Database Technology[M]. Beijing: Tsinghua University Press,2008.

[2] 小峰.XML数据管理:概念与技术[M].北京:清华大学出版社,2009.

XIAO Feng. XML Database Management[M]. Beijing: Tsinghua University Press,2009.

[3] E. Wu, Y. Diao, S. Rizvi. High-performance complex event processing over streams[C]//Proceedings of the 2006 ACM SIGMOD international conference on Management of data,2006:407-418.

[4] Hakuta S, Maneth S, Nakano K, et al. XQuery streaming by forest transducers[C]//Data Engineering (ICDE), 2014 IEEE 30th International Conference on. IEEE,2014:952-963.

[5] Chakravarthy S, Adaikkalavan R. Events and streams: harnessing and unleashing their synergy![C]//Proceedings of the second international conference on Distributed event-based systems. ACM,2008:1-12.

[6] Hachicha M, Darmont J. A survey of XML tree patterns[J]. Knowledge and Data Engineering, IEEE Transactions on,2013,25(1):29-46.

[7] Bex G J, Neven F, Schwentick T, et al. Inference of concise DTDs from XML data[C]//Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment,2006:115-126.

[8] Fallside D C, Walmsley P. XML schema part 0: primer second edition[J]. W3C recommendation,2004,16.

[9] Amer-Yahia S, Cho S R, Lakshmanan L V S, et al. Minimization of tree pattern queries[C]//ACM SIGMOD Record. ACM,2001,30(2):497-508.

[10] Ramanan P. Efficient algorithms for minimizing tree pattern queries[C]//Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM,2002:299-309.

[11] 李慧.基于XMLSchema的Twig查询模式最小化[D].北京:北京工业大学,2013.

LI Hui. Optimizing Twig Query Pattern Based on Xml Schema[D]. Beijing: Beijing University of Technology,2013.

[12] 王宇,孟小峰,王珊.基于模式的Pattern Tree语义优化[C]//第二十一届中国数据库学术会议论文集(研究报告篇),2004.

WANG Yu, MENG Xiaofeng, WANG Shan. semantic optimization Based on Pattern Tree[C]//The 21st China Database Conference Proceedings(Research Report chapter),2004.

[13] Chen D, Chan C Y. Minimization of tree pattern queries with constraints[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM,2008:609-622.

[14] Lakshmanan L V S, Ramesh G, Wang H, et al. On testing satisfiability of tree pattern queries[C]//Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment,2004:120-131.

[15] Tahraoui M A, Pinel-Sauvagnat K, Laitang C, et al. A survey on tree matching and XML retrieval[J]. Computer Science Review,2013,8:1-23.

[16] Bacˇa R, Krátky M, Ling T W, et al. Optimal and efficient generalized twig pattern processing: a combination of preorder and postorder filterings[J]. The VLDB Journal,2013,22(3):369-393.

[17] Bruno N, Koudas N, Srivastava D. Holistic twig joins: optimal XML pattern matching[C]//Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM,2002:310-321.

[18] Zhou J, Xie M, Meng X. TwigStack+: Holistic twig join pruning using extended solution extension[J]. Wuhan University Journal of Natural Sciences,2007,12(5):855-860.

[19] Qin L, Yu J X, Ding B. TwigList: make twig pattern matching fast: Advances in Databases: Concepts, Systems and Applications[M]. Heidelberg: Springer Berlin,2007:850-862.

Twig Pattern Minimization Based on Path Constraints in XML Type Information

ZHANG YanLIAO Husheng

(College of Computer Science, Beijing University of Technology, Beijing100124)

Twig Pattern Query is the core operation of XML query. Since the query patterns in query requests always include some redundant sub-queries, twig pattern minimization has been a hot research in this field. Some specific schema information can be used to perform twig pattern minimization. This paper proposes a new approach for twig pattern minimization which includes a set of rules based on path constraints in XML type information for removing not only redundant leaf nodes, but also the middle ones.

twig minimization, schema constraints

2016年3月10日,

2016年4月24日

北京市自然科学基金项目(编号:4122011)资助。

张岩,男,硕士研究生,研究方向:软件XML数据库技术。廖湖声,男,博士,教授,研究方向:软件自动化方法,编译技术,XML数据处理,程序分析与程序变换。

TP391DOI:10.3969/j.issn.1672-9722.2016.09.030