没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记151(2006)107-124www.elsevier.com/locate/entcs基于Object-Z的Twig XML数据库求值算法设计杨柳1和孙俊2新加坡国立大学新加坡摘要基于XML的Web技术,例如语义Web和Web服务,促进了Web自动化和普遍访问内容。基于XML的技术成功的关键因素之一是为基于XML的数据模型找到有效的查询评估算法。 XML小枝查询是对带标签的XML文档的结构和内容的复杂选择谓词。近年来,一些新的小枝查询评价算法被提出。然而,这些算法是难以理解的,因此,由于高复杂性实现。 在这项工作中,我们提出了一个算法设计的XML查询评估系统使用Object-Z。一个Object-Z规范的开发,给出了一个简洁和逻辑的XML数据模型和小枝查询的描述。它使得小枝查询的计算简单明了,并允许不同的计算算法可以容易地、独立地构造。关键词:XML,Twig查询求值,Object-Z,规范1介绍XML正在成为Internet上信息交换的事实标准.基于XML的本体语言,如RDF,DMAL+OIL/OWL [3]是语义Web [23]的基石,因为它们为数据标记提供了基本词汇:本体。因此,有效地处理XML文档的能力对于1电子邮件:liuyang@comp.nus.edu.sg2电子邮件:sunj@comp.nus.edu.sg1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.07.039108Y. 刘,J.Sun/Electronic Notes in Theoretical Computer Science 151(2006)107软件感知的应用程序,因为软件代理将执行由XML文档标记的数据的自主发现、查询和处理。尽管XML文档可能具有相当复杂的内部结构,但它们通常可以建模为有序树。XML查询语言中的选择通常指定多个元素上的选择谓词的模式[4,5])。例如,要检索嵌套在节内并且至少有一个图和一个表的所有段落,可以表示为:Q1=//section//paragraph[图AND表]这样的查询可以表示为节点标记的小枝模式(或小树),其中元素和字符串值作为节点标签[6]。 查找所有出现的twig模式是XML查询处理中的核心操作[14,21,19,22]。目前,最有效的算法之一是整体分支连接算法TSGeneric[16]。它使用堆栈来缓存XML元素,并使用游标接口来提供标准方法来返回可能匹配的元素。随着光标接口[15]的不同实现,已经开发了有效的算法[16]来基于可用的访问方法处理小枝连接然而,由于整体方法的高度复杂性,很难理解并实施评价过程。像Object-Z这样的形式化规范语言是精确的和高度可重用的,它可以对问题进行明确的规范,从而允许高效的算法设计。本文使用Object-Z [13]给出了树结构XML数据模型和小枝查询结构的面向对象规范特别是,泛型类与类继承相结合来构造规范,这导致了一个高度可扩展的规范和一个清晰的结构,这对XML查询评估的高效算法设计非常有用我们表明,各种评价算法可以直接使用我们的结构形式化。总的来说,我们相信我们的方法是适用于其他情况下,密集的算法设计的基础上复杂的数据结构是必需的,例如。任务调度、安全协议等。我们的工作是有关研究应用形式化方法的XML相关方面的Web域。在文献[25]中,Object-Z中给出了一个形式化的面向对象的语义模型,它提供了对语言的形式化理解,并有助于Object-Z的标准化分类。在[26]中,Object-Z规范被用来对XSLT 2.0、XPath 2.0和XQuery 1.0的公共语义结构进行建模。目的是重用这些语义结构来指定XML家族语言的语义,并理解它们之间的共性和差异我们的工作重点是算法Y. 刘,J.Sun/Electronic Notes in Theoretical Computer Science 151(2006)107109使用Object-Z设计XML查询评估。我们表明,我们的Object-Z规范简化了树枝查询评估问题的复杂算法的设计我们相信,我们的方法是适用于复杂的算法设计的基础上复杂的数据结构是必需的系统。我们的工作也与将形式化方法应用于其他Web技术的工作有关,其中一些在[20,12,28,17,7,11]中得到了证明另一个远程相关的工作是Martin和Simpson关于Z模式和关系数据库之间的连接的工作[18]。本文的其余部分组织如下:第2节简要介绍Object-Z规范语言。第3节描述了XML数据模型的位置表示及其Object-Z规范。第4节描述了XML小枝查询和相关的数据结构。第五部分介绍了XML小枝查询评估的整个系统第6节展示了规范如何促进不同评估算法的设计第七节是论文的结论。2Object-ZZ [24]是一种基于状态的形式化规范语言,基于集合论和一阶逻辑的数学。它已被用于指定广泛的系统,包括事务处理系统和通信协议。Z中的规范通常由许多状态和操作模式组成。状态模式将变量组合在一起,并定义它们的值之间的关系操作模式定义了一个或多个状态模式的“之前”和“之后”赋值之间的关系Object-Z [13]是Z语言的面向对象扩展。它通过增强的结构化。Object-Z的主要结构是类定义,它捕获一个类的面向对象的概念,通过封装一个单一的状态模式与所有的操作,可能是一个封闭的变量。Object-Z类在语法上表示为具有零个或多个泛型参数的命名框可能有局部类型和常量定义,最多一个状态模式和一个关联的初始状态模式以及零个或多个操作。状态模式的声明称为状态变量,谓词称为类不变式。类不变式限制了状态变量的可能赋值。初始模式标识状态模式的可能初始值。操作可以是操作模式,也可以是涉及现有类操作和模式运算符的模式表达式表示一个对象(物理上)包含在另一个类中,而不是110Y. 刘,J.Sun/Electronic Notes in Theoretical Computer Science 151(2006)1070级1234Fig. 1. 示例XML文档而不是仅仅被它引用,它的类型是用系统的日志注释的[9]。例如,declara:A在classsB中指示classsB的对象具有对classA的对象的引用a,并且该对象被classB的对象包含。单个对象不能(直接)被多个对象包含类可以使用继承递增地指定一类它继承了另一个,可以用新的状态变量、新的不变量和初始约束以及新的操作来扩展它的定义。它还可能给现有的业务增加新的限制。在包含一个或多个继承层次结构的规范中,变量可以多态地声明为具有层次结构中任何类的类型3XML数据模型在本节中,我们将探讨在小枝查询计算中常用的XML数据表示这种表示给出了XML元素之间一些有趣的在本节的最后给出了使用Object-Z类定义的XML文档的形式化大多数现有的XML查询处理算法依赖于XML元素的位置表示[27,2,8,15],其中XML文档被建模为有序树,每个树节点(XML元素)被表示为一个图。格式为:(docID,start,end,level)。docID是XML数据库中XML文档的标识符。start(end)指的是从文档的根r到元素的start(end)按前序遍历的元素的数量。level表示元素的嵌套深度图1显示了一个包含根r和元素a、b和c的示例XML文档。从根r开始执行前序遍历。一旦一个元素被访问,它的开始值被设置为当前计数器。当一个元素第二次被访问时,它的结束值被设置为当前计数器。r(1100)a(2,17)c(20,35)a(36,45)a(47,90)a(3,8)c(9,15)b(21,25)b(26,32)a(37,42)c(49,67)c(71,88)c(4,7)c(10,13)c(23,24)b(27,30)c(38,39)b(50,65)b(73,85)a(5,6)a(11,12)c(28,29)c(52,54)c(57,60)c(76,80)Y. 刘,J.Sun/Electronic Notes in Theoretical Computer Science 151(2006)107111元件T(docID,start,end,level,tag)docID,start,end,level:Ntag:TAG起始端电平起始端为了在Object-Z中完整地表示XML文档元素,首先我们使用自由类型Char定义了XML元素标记名集TAG。Char包含标记名称的所有有效字符。TAG是所有可能的XML元素节点标记名称的集合,即以字母或两个特殊字符开头的有效字符序列。这一定义严格遵循万维网联盟的定义。详细定义见[1]。[Letter,Digit,CombiningChar,Extender]Char::= letter Letter|数字转换器数字转换器|“的。“的|“--”|“的一声|“:”|comChar组合Char|扩展器扩展器扩展器TAG=={t:seq Char |head(t)∈字母(head(t)=''t. head(t)=':')}XML元素的Object-Z建模定义如下元素类,其中定义了两个简单的类不变量利用位置表示,树节点之间的结构关系可以容易地确定为:(1)祖先-后代(A-D)关系:元素v是元素u的后代当且仅当u。开始<; 开始<联合end;(2)父子(P-C)关系:元素v是元素你我都在。开始<; 开始<吧。结束和U。水平= v. -1级 两个关系Isparentof和IsparentorOf的定义如下:IsparentstorOf:ElementParticipElementIsParentOf:ElementParticipElementx,y:元素·xIsabolistorOf y惠x. 开始<吧。开始吧。启动 y.endx.start > y.startx.end y.endy.end < x.start段XYXYXYYX树Y根Y根xY根XY根X图二. 任意两个XML元素对于XML文档中的任意两个元素x和y,它们之间有四种可能的位置关系,如图2所示。图2中的情况2和情况3由前面的关系IsobstorOf捕获。需要一个新的关系来描述情况1和情况4:x。结束
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功