论文部分内容阅读
Active XML(Active eXtensible Markup Language)的提出,能够有效的解决当前分布式数据管理中存在的数据源异构性、交互性及自主性问题,为分布式Web数据管理提供了新的发展方向。AXML文档是一部分数据直接给出,另一部分数据以Web服务调用方式隐含给出的XML文档,通过触发这这些服务调用,可以获得其包含的隐含信息来扩充文档内容。AXML模式定义了符合约束条件的AXML文档集合。AXML数据管理需要考虑如下基础问题:(1)AXML数据交换是AXML的主要应用方式,而数据交换之前必须判定给定AXML文档通过触发其包含的服务调用是否能够转换成为符合目标模式要求的文档实例,从而引出了文档重写问题;(2)在某些情况下,还要考虑符合给定源模式的全部文档是否能够重写为目标模式实例,这就需要考虑模式之间的兼容性,该问题为模式重写问题;(3)AXML数据交换过程中,通常以查询方式来实现数据请求,而查询可满足性判定是执行给定查询的前提条件,通过判定给定查询的可满足性,可以过滤掉一部分不可满足查询,从而提高查询的执行效率;(4)保证AXML文档为有效文档是AXML数据管理的关键,也是AXML数据交换、文档查询的先决条件。本文基于树自动机理论,对AXML数据交换中存在的AXML文档重写和模式重写、AXML文档查询可满足性、AXML文档有效性检验问题进行了深入研究,目的是对上述问题提出有效的解决方法,从而让AXML能够更好的服务于分布式数据管理。第一,研究了AXML文档重写和模式重写问题。AXML文档重写问题是指判定给定文档通过触发其包含的服务调用是否能够将其转换成为符合目标模式的文档实例。AXML文档重写问题分为可能重写和安全重写,AXML文档可能重写是判定给定文档是否能够重写为目标模式的某一文档实例;AXML文档安全重写是判定给定文档的全部可生成文档是否能够重写为符合目标模式的文档实例。AXML模式重写问题是指判定符合给定源模式的全部文档是否能够重写为目标模式实例。首先,基于传统树自动机理论,定义了用于抽象描述AXML文档树的ADTA机(AXML DocumentTree Automata),基于ADTA机,给出了多项式时间复杂度的AXML文档可能重写判定算法,给出了算法的正确性证明;在ADTA机的基础上,定义了ADTA机补自动机,提出了多项式时间复杂度的AXML文档安全重写判定算法,给出了算法的正确性证明;然后,定义了用于描述AXML模式的ASTAr机(AXML Schema Tree Automata for Rewriting),给出了ASTAr机构造算法,ASTAr机定义了所有符合给定AXML模式约束的AXML文档集合;最后,通过分析AXML模式包含与模式重写的关系,基于ASTAr机,提出了多项式时间复杂度的AXML模式重写判定算法,分析了算法的正确性和有效性。第二,研究了模式约束下的AXML文档树模式查询可满足性问题。AXML文档查询可满足性问题是指判定符合给定模式约束的AXML文档是否满足给定查询表达式。首先,给出了AXML文档查询可满足性的形式化定义;然后,定义了用于抽象AXML模式的ASTAq机(AXML SchemaTree Automata for Queries),用于描述符合给定AXML模式约束的文档集合,定义了抽象树模式查询的TPQA机(Tree Pattern Query Automata),TPQA机描述了包含满足给定树模式查询表达式路径的文档集合;最后,基于ASTAq机和TPQA机,针对XPath树模式查询片段{“/,//,[ ]”},提出了一种多项式时间的AXML文档查询可满足性检验算法,分析了算法的正确性和有效性。第三,研究了AXML文档有效性检验问题。AXML文档有效性检验问题是指给定AXML文档及其服务调用规范,检验文档是否符合目标模式。定义了用于抽象AXML模式的ASTAv机(AXML Schema Tree Automata forValidation),该树自动机描述符合目标模式约束的文档集合,能够完成对给定文档当前状态的有效性检验;基于ASTAv机,通过分析服务规范与目标模式之间的关系,提出了一种多项式时间的AXML文档有效性检验算法,分析了算法的正确性和有效性。