没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记174(2007)17-34www.elsevier.com/locate/entcs耦合软件转换Alcino Cunha1,3Joost Visser2,3DI-CCTC,Universidade do Minho,葡萄牙摘要耦合转换发生在软件演化中,当多个工件必须以彼此保持一致的方式进行修改时。 一个重要的例子涉及到数据类型、其实例以及使用或产生它的程序的耦合转换。在前面,我们已经提供了前两个转换的形式化处理:数据类型和实例。治疗涉及类型安全,类型改变战略重写系统的建设。在本文中,我们将我们的处理扩展到相应的数据处理程序的转换。扩 展 背 后 的 关 键 见解 是 , 数 据 迁 移 功 能 和 数 据 处 理 器 都 可以类 型 安 全 地 表 示 为广 义 抽 象 数 据 类 型(GADT)。然后,这些表示受到程序计算规则的约束,并在类型安全、类型保持的策略重写系统中加以利用。为了便于计算,我们使用无点表示和相应的计算规则。因此,耦合变换分两步进行。首先,将类型改变重写系统应用于源类型以获得目标类型以及源和目标之间的迁移函数(的表示)。然后,将类型保持重写系统应用于迁移函数和源(或目标)类型上的数据处理器的合成,以获得目标(或目标)类型上的数据处理器源)类型。所有重写都是类型安全的。关键词:程序转换,术语重写,策略编程,广义抽象数据库,数据精化。1介绍耦合转换发生在软件演化中,当多个工件必须以相同的方式被修改时,其中yre_m_i_n_c_n_n_s与a_h_h。Laémmel[14]确定了耦合变换的类别,并讨论了它们在问题领域中的广泛出现,例如协同编辑,软件建模,模型转换和重新/逆向工程。耦合转换的一个特别具有挑战性的实例涉及数据类型、其实例和使用或1电子邮件地址:alcino@di.uminho.pt2 电子邮件:joost. di.uminho.pt3WorkfunderdbyFundaPundaPunda1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.10.01918A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17S、、、、,,pJp,,到,数据类型转换的数据类型a,aJ分别是A和AJ的实例。p生产者,生成类型A q查询的数据,消费类型AJ,zza:A,,TzaJ:AJA型到Aj型的T从qQJ从Aj→A型迁移函数到Aj→AJJ,Yp转化生产者qJ转换查询Fig. 1.数据类型A、数据实例a、数据生产者p和数据查询q的耦合转换。挑战在于通过将组合物融合为αp和αq来计算pJ和qj,使得它们直接作用于AJ而不是通过A。在软件更新的背景下,例如当需要调整数据库的模式时,然后,数据库模式的适配必须与数据库实例的迁移以及连接到这些数据库实例的程序的一个重要的研究挑战仍然是为耦合变换提供一个通用的、抽象的概念框架[15]。此前,我们已经采取了第一步来提供这样一个框架。特别地,我们已经提供了两级数据转换的形式化处理,即数据类型和实例的耦合转换[6]。在本文中,我们扩展我们以前的治疗,包括数据处理器的转换。图1给出了我们对耦合转换问题的观点的全局概述。源类型A到目标类型AJ的类型级变换T由相关联的实例迁移函数来证明。在第5节中,我们概括了如何将这种类型级和值级转换耦合到一个两级数据转换系统中,该系统被建模为强类型、类型更改、战略重写系统。消费类型A的值的查询q和生成这样的值的生产者p是数据处理程序的示例。为了获得转换后的类型AJ上的查询和生产者,我们可以简单地将q和p与迁移函数from和to组合在一起。这相当于程序迁移的包装方法,其中原始类型和原始处理器仍然显式存在。在本文中,我们所面临的挑战是从这些包装器组合中计算处理器qJ和pJ,使得它们不再涉及原始类型和处理器。在第4节中,我们解释了如何在一个额外的类型保持策略重写系统中利用这种程序计算来对所关键思想是使用融合或森林砍伐技术[24]来消除中间数据类型A。在第2节中,我们提出了一个具体的例子来激励我们的方法耦合转换。在第6节中,我们展示了如何使用类型保持重写系统,XA. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1719程序计算(第4节)和用于两级数据转换的类型改变重写系统(第5节)可以结合起来执行耦合转换。这两个重写系统都在值级别使用了强类型的表示,在第3节中进行了概括。第7节讨论相关工作,第8节结束。2启发性的例子:查询进化假设有关音乐专辑的信息保存在XML文件中,这些文件符合以下Haskell类型捕获的文档模式:typeAlbums= [Album]typeAlbum=(ASIN,(Title,Artist))typeASIN=StringtypeTitle=StringtypeArtist=String对该格式的查询将是如下函数getArtists::相册→[Artist]getArtists = List. 地图(snd)音乐专辑集合的实例如下所示:收藏=[(“B000002UB2”,(“修道院路”,“披头士”)),(“B000002HCO”,(“Debut”,“Bjork”))]在实际情况中,对于给定的格式,可能会有许多查询和生成器,并且可能有许多大型实例。假设相册格式通过两个步骤更改为新格式。首先,将轨道信息添加到每个专辑。这涉及到引入一个新的字段,它包含一个嵌套的曲目标题列表typeAlbumJ=(ASIN,(Title,(Artist,Tracks)typeTracks= [标题]随后,为了将专辑集合存储在关系数据库中,格式被转换为基于有限映射的表示:typeDB=(Map Int Album,Map(Int,Int)Title)第一张地图表示专辑表。第二个映射是一个带有复合键的表,用于保存曲目标题。第一步是格式演变的一个例子。第二种是层次关系数据映射.当然,这两个转换步骤会使所有现有的数据实例和处理器失效。在本文中,我们将表明,现有的数据和查询,实际上可以自动迁移到新的格式的程序转换耦合到格式转换。例如,在第一步之后,查询可以是20A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17迁移至:getArtistsJ= List. map(fstsndsnd)在第二步之后,查询将迁移到:getArtistsDB= elems对象映射。map(snd)地图在这里,elems是map上的一个标准函数,它返回map的范围,一个列表(按键的升序排列)和Map。map将其参数函数应用于每个范围元素。请注意,迁移的查询不涉及作为中间格式的原始相册类型,也不根据迁移函数包装的原始查询进行定义。3类型的表示在我们将要定义的两个重写系统中,我们都需要访问值级别上的类型表示。无点表达式的类型保持重写系统需要它们用于类型导向的重写决策,而类型改变重写系统对类型本身执行重写。为了确保两个重写系统的类型安全,类型的通用表示并不存在。使用广义代数数据类型(GADT)[22],Haskell类型系统的最新扩展,可以声明一个参数化数据类型Type a,其居民必须是类型a的表示[12]:dataType awhereInt::Type IntString::TypeString One::Type()Either::Type a→Type b→Type(Either a b)Prod::Type a→Type b→Type(a,b)功能::类型a→类型b→类型(a→b)列表::类型a→类型[a]Map::Type a→Type b→Type(Map ab)Tag ::String→Type a→Type a注意,在这个声明中,参数化Type a的Typea在每个构造函数中受到不同的限制这正是GADT和常规参数化数据类型之间的区别,在常规参数化数据类型中例如,类型构造函数Int的类型为Type Int,而List Int的类型为Type[Int]。因此,GADTType a的参数a允许我们携带必要的类型信息以确保类型安全。类型a允许表示一些基本类型,和,产品,函数,列表和有限映射-对于本文的目的来说足够了,但如果需要,可以扩展到更多类型。Tag构造函数允许我们用名称标记类型。例如,Albums的类型表示可以定义如下。类别:类别:音乐A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1721albums=List(Tag“Album”(Prod String(Prod StringString)标签的使用将在后面说明。给定一个基类型a,可以使用Haskell类型系统来推断它的表示。我们定义了一个类Typeable a,它有一个返回表示的方法typeof:classType awheretype::Type ainstanceTypeable Int其中typeof=IntinstanceTypeable a实例Typeable[a]其中typeof=List typeof中存在的其余类型必须定义Typeable的普通实例类型. 现在,可以与解释器进行以下交互:> typeof::Type[(Int,Char)](List(Prod IntChar))这依赖于类型a的Show类的一个简单实例。4无点程序演算在本节中,我们将解释如何定义类型安全、类型保持的策略重写系统,以将程序计算规则应用于迁移函数和数据处理器。特别是,我们的目标是应用融合法,以简化包装处理器的原始数据到处理器,直接对新的数据,从而避免建立原始类型的中间数据结构。如果融合成功,则可以获得显著的效率增益我们的函数将使用所谓的无点编程风格来表示,在这种风格中,函数是使用一小组组合子和原始函数从简单的函数构建的事实上,getArtists查询就是以这种风格定义的。无点组合子满足一组强大的方程定律,用于通过计算推理函数程序[11],并且由于没有变量和λ-抽象,实现重写系统来自动化此类计算是简单的。无点组合子及其定律无点编程中最基本的组合子是函数复合和恒等函数。(· ·):(b→c)→(a→b)→a→c(· λ·)=λfgx. f(gx)识别码: a→aid = λx。X这些组合子共同享有以下定律,这些定律是如此基本,以至于它们通常在程序计算中隐式使用。f(gh)=(fg)hComp-Asynidf=fid=fId-Nat为了处理乘积,我们有分裂组合子(o),它将22A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17将两个函数应用于相同的值,以及投影:(·o·):(a→b)→(a→c)→a→(b×c)(·o·)=λfgx. (fx,gx)fst:(a×b)→afst = λ(x,y)。 Xsnd:(a×b)→bsnd = λ(x,y). y关于这些,我们有以下定律和导出的乘积组合子:fstosnd=id-Re exfst(fog)=f snd(fog)=g-取消(fog)h=fhogh-融合f×g=ffstogsnd-Def我们也有原始函数bang:a→1,给定任何值都返回类型1的单个居民。它满足以下定律。f =爆炸我的f:a→1Bang-Eta类似的组合子和定律存在于和函数中,但它们在本文中没有列表和映射的组合子和定律将在后面介绍函数的类型安全表示对于无点函数的类型安全表示,我们再次求助于GADT:数据PF f,其中Id::PF(a→a)Comp::Type b→PF(b→c)→PF(a→b)→PF(a→c)Fst::PF((a,b)→a)Snd::PF((a,b)→b)·Δ·:PF(a→b)→PF(a→c)→PF(a→(b,c))·×·*PF (a→b)→PF(c→d)→PF((a,c)→(b,d))Bang::PF(a→1)Fun::String→(a→b)→PF(a→b)PF(a→b)型居民是a→b型函数的无点表示。中间类型表示在组合中的存在构造函数将在后面解释。Fun构造函数允许我们在无点表达式中包含逐点函数,而不必将它们转换为无点形状;它可以用于没有特定推理的函数。通过使用GADT来表示无点表达式,我们获得了类型-免费检查:不可能编写一个不可能的函数,如fstbangbang或将不正确的类型赋给表达式。无点表达式的这种抽象语法可以通过以下求值函数转换为具体的函数:eval::PF a→aeval Id=λx→xeval(Comp f g)=λx→(eval f)(eval g x)eval Fst=λ(x,y)→xA. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1723eval Snd=λ(x,y)→yeval(fΔg)=λx→(eval f x,eval g x)eval(f×g)=λ(x,y)→(eval f x,eval g y)eval Bang= λ →()eval(Fun n f)=f例如:> letassocr=(Comp(Prod Int String)Fst Fst)Δ(Snd×Id)> eval assocr((1,“foo”),True)(1,(“foo”,True))重写无点表达式为了简化无点表达式,我们实现了一个保持类型的策略重写系统,其中规则以及由它们组成的策略具有以下类型:typeRule= Rulea。类型a→PF a→重写M(PF a)在这里,RewriteM是一个单子。因此,重写规则基本上是无点表示上的一元函数,另外用类型表示进行参数化。RewriteMmonad是MonadPlus类的一个实例:classMonadmMonadPlus m其中mzero::m amplus::m a→m a→m aMonadPlus 类 的 一 个 著 名 实 例 是 类 型 数 据 Maybe a = Just a| 没 什 么 我 们 的RewriteMmonad扩展了这一点,能够在重写过程中产生证明跟踪,其中包括中间结果和应用规则的名称,但这与本文的目的无关rules的附加参数用于类型定向重写。类型导向的重写是必不可少的,因为有些定律需要类型信息:仅仅使用语法是不可能决定定律是否可以应用的。 例如,Bang-Eta定律指出,任何类型a→1的函数都可以转化为不管它的定义是什么。也考虑到当被用作一个扩展(从右到左)。它不能应用于任何恒等函数,而只能应用于a×b→a×b类型的恒等函数。使用这种类型定向的扩展是变得非常相关;它们是基本的,例如,在简单类型的λ-演算中建立等式的可判定性[8,9]。作为编码类型导向规则的示例,考虑Bang-Eta(从左到右):bang eta::Rulebang eta Bang=mzerobang eta(函数一)=return bang eta=mzero为了避免非终止性,规则在Bang本身上失败(mzero)。其他类型a→()的表达式被重写为Bang。否则规则失效。类型定向重写不需要我们注释所有的无点组合,24A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17具有类型表示的变量在大多数情况下,子表达式的类型可以从封闭表达式的类型除非一个类型变量在构造函数的类型中存在量化,就像Comp的情况一样。这就解释了为什么我们必须用它的中间类型的表示来参数化Comp。 作为因此,当指定涉及组 合 的 规 则 时 , 用 户 必 须 明 确 地 推 理 类 型 。 一 个 例 子 是 从 左 到 右 的Comp-Asynchronouscompassocr::Rule组合物(组合物a(组合物b f g)h)=return(Comp b f(Comp a gh))comp assocr=mzero请注意如何使用输入类型指定新的中间类型。处理组合的结合性当为无点表达式实现重写系统时,必须特别注意组合的结合性。当手工计算时,通过省略组合组合子周围的括号来隐式地假设该规则。这种策略已经被硬连接到一些重写系统中,例如Bird我们采用了不同的方法。在应用任何有关产品的规则之前,我们将详尽地应用compassocr,以保证所有成分都与权利相关联。当右参数不是任意的时,必须对具有最外成分的定律进行某种完备化。例如,考虑编码取消:prod cancel::Ruleprod cancel(Comp Fst(fΔg))=return fprod cancel(Comp Snd(fΔg))=return gprod cancel(Comp Fst(Comp a(fΔg)h))=return(Comp a fh)prod cancel(Comp Snd(Comp a(fΔg)h))=return(Compa g h)prod cancel=mzero附加的第三和第四方程允许在右相关组合物序列中的任何位置应用该规则。我们定义了典型的策略重写组合子:nop::Rulenop t=return*规则→规则→规则(fDg)tx=ftx>>=gt()::规则→规则→规则(fg)t x=f t xmany::规则→规则many r=(rDmany r)nopmany1::Rule→Rulemany1 r=rDmany rtry::Rule→Rule尝试x=xnopDcombinator按顺序应用两个规则(第二个规则仅在第一个规则成功时应用)。第二种选择是一种左倾选择,它试图应用第一条规则,如果失败,它会尝试第二条规则。manycombinator反复尝试应用一个规则,直到失败。many1类似,但必须至少成功一次。try尝试应用规则,A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1725如果失败,则返回原始表达式,而nop是一个总是成功的规则我们还定义了标准的遍历组合子,我们省略了它们的定义once::Rule→Rule everywhere::Rule→Rule这些组合子采用单个规则作为参数,并分别应用一次。every- where,在表达式的自顶向下遍历期间。重写系统的构成有了基本的规则和组合子,就可以定义重写系统,例如:简化涉及产品的表述prods::Ruleprods=many1(多次(一次比较)Donce(bangetaprodcancelprod reex. ))虽然简单,但它处理了一类有趣而有用的简化。为了方便起见,我们定义了一个函数来将重写系统应用于无点表达式:rewrite::Typeable a可输入规则→PF a→IO(PF a)在内部,它处理派生受重写影响的表达式的类型表示以及成功和失败的报告。5两级数据转换耦合转换解决方案的第二个组成部分是允许两级数据转换的类型更改重写系统。我们依赖于我们在以前的工作中提出的重写系统[6],并进行了一个简单的基本修改:而不是值级转换(或迁移函数)本身,我们将使用它们的无点表示,然后可以随后进行上一节的类型保持重写系统。二级转换步骤通过数据集之间的不等式和以下形式的伴随函数到A,, ≤从个zlb这里,不等式A≤B模拟了一个类型级别的转换,其中数据类型A被转换成数据类型B,并证明了这样一个事实,即存在一个到(表示关系)的单射、全关系和一个来自(抽象关系)的满射、可能是部分函数,使得从A到=idA,其中idA是数据类型A上的恒等函数。 虽然一般来说可以是一个关系,它通常是一个函数。因此,类型级转换产生于值级转换的存在,值级转换的属性防止数据混淆。当从左到右应用时,不等式A≤B将保持或丰富信息内容,而从右到左应用时,它将保持或限制信息内容。封装类型更改重写我们的mod26A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17Haskell中的两级数据转换是以下类型声明:dataRep a b = Rep{to::PF(a→b),from::PF(b→a)}data View a其中View::Rep a b → Type b →View(Type a)typeRULE= RISKa. 类型a→可能(视图(类型a))View构造函数表示类型a可以表示为类型b,如果有函数to::a→b和from::b→a允许数据在两者之间转换。请注意,只有源类型a从View构造函数中逃逸,而目标类型b仍然是封装的-它是隐式存在量化的。 RULE类型表示,当重写类型表示时,我们不替换它,而是用目标类型对其进行扩充以及一对允许在源和目标类型之间进行转换的值级别函数。对于保持类型的策略重写系统,我们为两级转换规则的身份、顺序组合、左偏选择、重复和结构组合nop::RULEnop x=Just(View(Rep Id Id)x)(D)::RULE→RULE→RULE(fDg)a=do视图(Rep t1 f1)b←f a视图(Rep t2 f2)c←g breturn(View(Rep(Comp b t2 t1)(Comp b f1f2))c)(视图)::规则→规则→规则many::Rule→Ruleonce::Rule→Rule为了简洁起见,我们只给出前两个的定义。这些组合子允许我们将局部的单步转换组合成一个全局转换。示例两级重写规则根据要解决的场景,上述策略组合器可以与不同的单步重写规则集组合,以获得适当的重写系统。在其他地方,我们提供了格式演化和层次关系数据映射的规则集[6]。的以下格式演变规则与我们的示例相关inside::String→RULE→RULEinside n r(Tag m a)|nm = doView rep b←r areturn(View rep(Tag mb))inside=无类型Query b= Querya。类型a→PF(a→ b)addfield::Type b→Query b→RULEaddfieldb f a=Just(View(Rep(IdΔ(f a))Fst)(Prod ab))assocr::RULEassocr(Prod(Prod a b)c)=return$View rep(Prod a(Prod b c))A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1727zz[String],,Albums添加Tracks AlBumsJgetArtists,,,、从月1toDBtoo1从2toDB至2中国cJzJDBDB图二. Albums格式在添加曲目信息的演变步骤之前和之后都映射到关系数据库。其中rep=Rep((Comp(Prod a b)Fst Fst)Δ(Snd×Id))((Id×Fst)Δ(比较(生产b c)Snd Snd))assocr=mzero内部组合子在给定标记下应用其参数规则。addfieldcombinator添加一个新的field,其值通过查询现有数据获得。assocr规则将嵌套产品关联到右侧。下面我们将在必要时介绍进一步的规则。分阶段访问数据迁移功能封装在视图中的数据迁移功能可以使用简单的分阶段方法进行访问,为此我们可以定义以下两个功能:showType::View(Type a)→StringunView::View(Type a)→Type b→Maybe(PF(a→b),PF(b→a))请注意,目标类型表示必须提供给unView,但一般来说,这种类型只能在计算之后动态可用。在第一阶段,我们应用转换以动态地获得b,使用showType,以其字符串表示的形式在第二阶段,字符串表示被合并到我们的源代码中,并被解析和编译,最终成为静态可用的。下面我们将演示在口译会话中使用这种分阶段方法。注意,这种分阶段的方法并不是我们使用动态计算的结果类型和迁移函数的唯一选择。相反,我们可以明智地使用存在和通用量化类型来以类型安全的方式对动态类型和动态类型化的值和函数进行建模[1]。有了这些,迁移函数可以计算和使用在一个单一的阶段。6耦合变换现在,我们将演示上一节中介绍的重写系统如何允许我们处理第2节中描述的耦合转换的激励示例。图2中显示了所涉及的转换的概述。相册的例子涉及列表和有限的地图。我们需要扩展无点表达式的类型,在这些数据类型上使用原语操作数据PF a其中28A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17...列表映射::PF(a→b)→PF([a]→[b])映射::PF(b→c)→PF(映射a b→映射a c)元素::PF(映射a b→[b])Fromlist::PF([a]→Map Int a)Fromlist通过给列表中的元素分配递增的整数键,从列表中构建一个映射。我们没有展示eval对这些原语的直接扩展。当然,这些函数可以用更基本的列表和映射函数来写,比如折叠,但这会不必要地使计算复杂化。在为特定的应用场景选择原语集时,在表达性和易于计算之间取得适当的折衷是给定这些原语,我们可以用抽象语法编写getArtists查询getArtists::PF(Albums→[Artist])getArtists=Listmap(Comptypeof Snd Snd)为了允许简化涉及列表和映射的函数表示,我们还必须向无点重写系统添加新的简化规则。关于这些原语的一些相关定律是:listmapflistmapg=listmap(fg)Listmap-Fusionmapmapfmapmapg=mapmap(fg)Mapmap-Fusionlistmapfelems=elemsmapmapfElems-Mapelemsfromlist=idElems-Fromlist将这些定律编码为重写规则是简单的。例如,Listmap-Fusion编码如下(再次假设组合的右关联listmap fusion::Rule列表映射融合(Comp(列表a)(列表f)(列表g))=return(Listmap(Comp a f g))列表映射融合(Comp(列表a)(列表f)(Comp b(列表g)h))=return(Compb(Listmap(Compa fg))h)listmap fusion =mzero与prods一起,这些定律被纳入重写系统优化,简化了涉及产品,列表和有限地图的无点表达式。使用上一节中定义的组合子,我们可以定义一个规则addTracks通过添加曲目信息来改进专辑addTracks=once addInsideDmany(once assocr)whereaddInside=inside“Album”(addfield(List String)getTracks)getTracks::Query[String]getTracks(Prod String)=Comp String(Fun“Note”Note)Fst注意,使用inside将addfield的应用限制为表示A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1729标签为“Album”注释函数(其定义被省略)使用ASIN字段在某些外部数据源(如互联网)中查找曲目标题。在字段添加之后,assocr规则被彻底应用,以将得到的嵌套元组转换为所需的右关联形式。第一个转换步骤有了这些定义,我们可以根据第一个转换步骤执行查询的迁移,如下面的解释器交互所示。首先,我们将addTracks应用于专辑的类型表示以获得预期的视图:> letJust vw1=addTracks专辑> 01-02Prod String(Prod String(Prod String(ListString)使用新的类型表示,现在可以获得迁移函数,并通过组合getArtists和from来构建新的查询。> letalbumsJ= List(Tag“Album”(Prod. (ListString)> letJust(to,from)=unView vw1相册J> letgetArtistsJ=Comp albums getArtists from> getArtistsJ名单map(snd)地图名单地图预览名单map((id × fst)Δ(snd <$snd))<$名单map(id ×((id × fst)Δ(snd snd)))id在这个组合查询中,我们可以识别出原始查询(第一行),跟踪信息的删除(第二行),以及嵌套元组右关联的反转(最后两行)。这个组合查询的简化使用了Listmap-Fusion和各种关于产品的定律来获得:> 重写优化getArtistsJList。地图(fst snd snd)这个简单的查询直接从每个专辑中选择艺术家字段。第二个转换步骤第二个转换步骤涉及一个称为toDB的策略,用于层次关系映射[6]。与本例相关的成分规则之一是使用Fromlist函数将列表细化为映射listmap::Rulelistmap(List a)=Just(View(Rep Fromlist Elems)(MapInt a))listmap=mzero按照与上面类似的步骤,我们首先获得专辑J的数据库细化的类型表示。> letJust vw2=toDB albumsJ> showType vw2Prod(Map Int(Prod String(Prod StringString)30A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17(Map(Prod Int Int)String)然后使用迁移函数来组成一个新的查询(参见图2)。> letdbJ= Prod(Map Int. )(Map(Prod Int Int)String)> letJust(to2,from)=unView vw2 dbJJ> letgetArtistsDB=Comp albums getArtists(Comp albums> getArtistsDB从2)名 单 map ( snd snd ) List. mapfst List. map ( ( id ×fst ) Δ ( sndsnd))List. map(id ×((id ×fst)Δ(snd snd)id List. mapid idelems Map. map(id×(id×(id×elems)idid地图map((fst fst)Δ(snd × id))Map. map((fst fst)Δ(snd × id))idljoin(id×njoin)ididididid(地图。map((id × fst)Δ(snd snd))× id)id由于toDB策略的复杂性,这个查询非常长,而且是不连贯的。 它基本上将两个表转换回相册列表(在map上使用一些基本的连接操作),然后才应用原始查询。经过简化,我们得到了预期的结果。> 重写优化getArtistsDB元素映射。map(snd)地图这个优化的查询忽略了第二个包含曲目信息的表,并直接从第一个表中获取艺术家列表我们已经展示了我们的耦合转换方法如何允许将对数据类型的查询迁移到对该数据类型的细化的查询。但是我们引入的支持耦合转换的重写系统允许我们处理许多其他场景。要了解这些可能性,请考虑一个场景,其中Albums在添加曲目信息的演化步骤之前和之后都映射到关系数据库(参见图2)。请记住,需要细化步骤来满足以下等式:ID. 在许多有趣的情况下,这个定律可以自动地通过计算得到证明使用我们的重写系统。例如,要证明将Albums转换为DBJ的精化的正确性,必须证明以下等式:从0到2从0到2从0到=id我们的重写系统成功地将这个等式的左边重写为id,从而证明了这个等式。从1到2的组合迁移没有跟踪信息的数据库,保存单个唱片表的数据库,该数据库保存具有音轨信息的附加表如果按此方式使用,此迁移函数首先将原始数据库转换这是非常不合理的,因为在新数据库中,第一个表只是现有表的副本。只有第二个包含磁道信息的表必须从头开始创建。 通过自动简化这种组合,可以计算出更直接的偏移,它绕过了2A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)1731中间列表格式:(list2mapelems)Δ(unnjoin列表2map元素列表2map. map(list2map Note fst))请注意,这个表达式包含两个表达式list2map元素,它基本上通过将新的序列键分配给其范围值来重建映射。然而,如果原始数据库是通过专辑列表的迁移获得的,则其键必须已经是顺序的,并且该表达式将不会创建不同的映射。事实上,每个细化都将不变量引入到目标类型上的nifrom=id假设其数据是由原始类型的迁移产生的。 的情况下这样的不变量的第一个表正好是list2map表元素=id,因此上面的表达式可以进一步简化为下面的表达式。idΔ(unnjoin)map(list2map Note fst))正如预期的那样,数据库迁移可以归结为添加一个新表(使用函数FUNCTIONOTE和映射上的嵌套连接操作),并保持现有表不变。本质上,我们已经计算了从文档迁移到的数据库迁移。7相关工作涉及格式和实例转换而不是程序转换的耦合转换的相关工作在[6]中提供,仅简要概括。我们专注于相关的方法,(也)考虑到程序转换。两级转换格式演化和数据映射是数据格式和实例耦合转换的重要示例,由Laémmeletal[16,17]确定。我们的一个程序是基于数据精化理论[20,21]来实现对数据([6],第5节)的低水平协同转换Cleve等人使用术语他们的方法涉及生成和转换技术来转换遗留信息系统的数据操作语句,但仅限于过程语句上的信息保留转换(基本上是:插入,删除,更新)。该方法抽象了各种语言(Cobol,Codasyl,SQL),但缺乏形式化和泛化。据报道,转化不涉及融合。计算形式的程序转换已经开发了几个系统,用于使用融合律执行计算形式的程序转换其中,MAG [19]和Yicho [13]是突出的,但两者都针对以逐点风格编写的Haskell程序为了处理通用递归模式的融合规律,两者都采用了高级高阶匹配算法。我们不需要这样的技术,因为我们的递归函数仅限于非常特定的模式,例如地图,融合更容易编码。32A. Cunha,J.Visser/Electronic Notes in Theoretical Computer Science 174(2007)17MAG系统的一个缺点是它使用固定的策略来应用转换规则,而Yicho提供了一些基本的策略组合子。在以前的工作[7]中,第一作者提出了一个用于简化无点表达式的重写系统第4节中介绍的系统的主要改进是类型化:我们现在可以使用类型表示来指导重写过程,并且重写规则保证是类型安全的。在他的Haskell编程入门书中,Bird提出了一个函数计算器,也可以用来简化无点表达式。不幸的是,表达式没有类型,与MAG一样,它使用固定的重写策略,这使得它很难应用于我们的场景。GADT的替代方案我们的解决方案在很大程度上依赖于GADT,无论是对于类型表示还是对于类型导向和类型安全的无点重写
下载后可阅读完整内容,剩余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直接复制
信息提交成功