分布式反应式XML

理论计算机科学电子笔记150（2006）61-80www.elsevier.com/locate/entcs分布式响应式XMLThomas Hildebrandt Henning Niss Martin OlsenJacob W. Winther1{hilde，hniss，mol，jww}@ itu.dk丹麦哥本哈根IT大学摘要以XML为中心的计算模型已经被提出作为对协调模型中的互操作性、异构性和开放性的需求的回答。我们提出了一个原型实现的开放的以XML为中心的协调中间件，称为分布式反应XML。中间件的理论基础是一个受双图反应系统理论启发的通用分布式可扩展进程演算。演算是可扩展的，就像XML是可扩展的一样，因为它的签名和反应规则是不固定的。它通过允许进程的状态以及反应规则集在不同的客户端之间分布（或部分共享）来分布。 演算是通过将流程术语表示为存储在一个面向值的对等XML存储和反应规则，作为客户端执行的XML转换。形式主义并不要求只存储过程术语，也可以存储应用程序特定的数据。 XML Store提供透明共享所有参与对等体之间的过程术语。并发反应规则之间的冲突由乐观并发控制处理。因此，该实现提供了一个开放的基于XML的协调中间件，具有包含共享数据、过程和反应规则的正式基础。关键词：反应式系统，进程演算，双图，XML，协调中间件，并发控制1介绍XML作为半结构化数据交换和处理格式的普遍性自然导致了对XML与编程语言和全球普适计算模型之间相互作用的研究。这是1.作者名单。这项工作部分由丹麦研究机构资助（批准号：2059-03-0031）和哥本哈根IT大学（LaCoMoCo项目）。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.02462T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61早期观察到移动环境演算，嵌套移动计算代理的开创性演算，描述了半结构化数据的重新配置[4]。有人建议，这种关系可以允许在两个方向上的技术转让，例如，使用所谓的空间逻辑移动过程演算的原因XML数据和使用半结构化查询语言搜索嵌套网络结构。在这些想法的基础上，[5]提出了所谓的以XML为中心的计算模型和基于XML的中间件进行协调。在以XML为中心的计算模型中，计算的状态（或部分状态）由XML数据组成。对于协调语言，数据通常存储在共享（或部分共享）的分布式元组空间中。然后，计算或协调操作就用这个XML数据的转换来表示。上述XML的使用在某种程度上满足了协调语言和全球普适计算中的互操作性、异构性和开放性的需求[21]。然而，计算通常用通用和复杂的语言（如Java或Java）表示。这违背了获得一种理论的希望，这种理论有助于分析所实现系统的行为，正如英国全球普适计算科学大挑战所倡导的那样。另一方面，固定一套简单的计算或协调规则违背了开放性和灵活性的愿望。最近，双图反应系统[16，18]已经被引入作为具有半结构化状态的反应移动系统的Meta它是一个Meta模型，就像XML是一个元模型一样，因为它允许通过指定允许的语法以及反应规则来定义特定于领域的模型所有的双图模型都受益于为双图反应系统开发的一般理论，例如互模拟证明技术[12]和空间逻辑[7，8]，以及能够在不同的双图模型之间转换的能力在本文中，我们建议利用XML的相似之处和理论的双图实现一个开放的，分布式的基于XML的协调中间件的正式基础，包括共享的数据，过程和反应规则。具体地说，我们介绍了一个分布式可扩展进程演算（简称diX演算）。diX演算是基于一个简单的可扩展的反应式系统演算，它可以被视为XML上下文的符号。 它的灵感来自于[4]中观察到的移动性和半结构化数据的过程演算之间的相似性，并且来自于[16，19]中提出的双图反应系统的Meta理论特别是，T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6163为双图中的演算提供语义。[2]分布式演算的灵感来自于[5]中研究的基于XML的协调中间件，允许进程的状态以及反应规则集在不同的客户端之间分布（或部分共享）。我们提出了一个实现，称为分布式反应XML。这些过程以XML的形式存储在分布式XML存储中，因此可以供多个客户机访问。每个客户机都可以根据自己的一组反应规则对共享的XML文档执行转换。一个跨平台的技术贡献是并发控制的实现，处理并发反应之间的冲突通过分析并发反应何时与[15]中提出的XML文档基于锁的并发控制相反，使用乐观方法的原因是我们使用对等网络来分发XML文档。这种设置使得实现锁定机制变得非常复杂，因为我们需要确保所有对等点都同意锁定。使用实现的乐观并发控制，我们只需要确保对等点同意文档的最新版本我们使用所谓的面向值的对等分布式XML存储层来实现 这 种 乐观 并 发 控 制 ， 该 存 储 层在 ITU 和 DIKU 实 现 ， 称 为XMLStore[2，13，20]。在面向值的XML Store中，数据永远不会更新。相反，新的值被构造，在可能的情况下重用旧的值这允许用于检测冲突的更新的完整历史的廉价存储如果检测到冲突，此历史记录也可用于回溯，或者作为更通用的调试工具。最后，值得注意的是，形式主义并不要求只存储过程术语，也可以存储应用程序专用XML数据。因此，实现提供了一个简单的，开放的基于XML的协调中间件与正式的基础，encom-传递共享的XML数据，过程和反应规则。文件的结构：在SEC。2.提出了分布式可扩展进程演算（diX）。节中3.介绍了面向值的XML Store，并描述了基于XML Store的DiX演算的原型实现--分布式反应式XML。特别是，我们描述了我们如何实现并发控制。在整个文件中，我们使用一个基于位置的服务的例子.我们在Sec结束四是要做好相关工作和今后的工作。2后续论文将讨论双图语义和一般双图理论的可能应用。64T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）612分布式可扩展进程演算在本节中，我们提出了一个简单的分布式可扩展进程演算，简称diX-calculus，灵感来自[4]中观察到的移动性和半结构化数据的进程演算与[12，16，18，19]中提出的双图反应系统记法：我们让n，m，i，j在自然数范围内，I和J在自然数的有限集合范围内。我们经常会混淆自然数m≥ 0和集合（序数）{0，1，. m−1}。2.1过程表达式首先，我们定义了一个通用的签名概念，包括XML文档的签名和双图签名。这个术语是从双图签名中借用的。定义2.1签名是一个元组（n，N，Att，ar），其中n是一组控制，N是一组无限的名称，Att是一组有限的索引集，ar：→Att是为每个控件分配索引集的函数Q对于本应用程序，我们认为XML是一组XML元素名称，N是一组XML属性值，而Att是有限组XML属性名称。示例2.2[位置模型]在本文中，我们将通过一个基于位置的服务的示例来说明diX演算的协调方面，以及它为了使示例易于管理，它被简化了很多;人们可以很容易地想象更完整的位置建模。位置示例的当前状态称为位置状态。位置状态由建筑物组成。一座建筑物包含许多走廊，每个走廊又有许多房间。人们可以出现在建筑物中，在这种情况下，他们必须在某个房间中，或者不出现在位置状态中的任何建筑物中。因此，签名控制器需要包括控制建筑物、地板、房间和人员。我们用属性来修饰其中的一些控件，例如name。属性和控件之间的连接由ar捕获;例如ar（room）={name}。Q然后，我们引入过程表达式。它可以被看作是XML数据元组的一个简单的进程演算符号。定义2.3对于一个签名<$=（N，N，Att，ar），定义一个签名过程的表达式，T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6165按语法r：：= r||R|p|0宽过程p：：= κ{i：xi}i∈ar（κ）. p|p|p|1对于κ∈N和xi∈N.素过程Q[16]我们在这里引用|和||分别作为主要和广泛的部件组成。我们将1称为nil进程，将0称为null进程。我们假设进程表达式上的结构同余关系，使得素数并行合成是结合的和交换的，宽并行合成关联的，以及nil进程1和null进程0分别是素数和宽并行组合的身份。定义2.4结构全等是过程表达式上的最小全等，p1|（p 2）|p3）（p1|p2）|p3 p|1张图片1|ppp|克|p和R1||第3条规则）第1条规则||r3r||r r Q||r3r||0≡r0||r≡rQ素并行积的交换性意味着我们，像通常在进程演算中一样，认为素并行进程是无序的。由于我们稍后根据有序的XML值来实现演算，因此在处理这些值时需要小心地将它们视为无序的。结合性允许我们省去括号，用于素数和宽并行组合，分别写为：对于n时间随机分布和宽分布，我们分别给出了npi和nri，并设nri∈0pi=1和ndri∈0ri=0。通常情况下，我们通常会给出一个不确定的过程，即对于κ { i：xi} i ∈ a r（κ），写出κ{i：xi}i∈ar（κ）。1. 我们认为，如果r∈npi，其中n≥0，则r上的一个宽的正整数x_p_i的宽度为n，即. 他不过程r是n个素数的宽平行积。例2.5[CCS和Ambients]我们可以将（有限）CCS的子集表示为素数过程 ， 其 中 有 n ={act， coact}， Att={{ch}}和 ar （ act） =ar （ coact）={ch}。我们可以将（有限）移动环境的子集表示为素数过程，其中对于k∈k，k={amb，in，out，open}，Att={{name}}和ar（κ）={name}Q示例2.6继续我们的位置模型示例，我们可以使用流程表达式来描述位置状态。 例如，当前状态可以66T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61是：建筑{name：itu}。关闭{name：itu 3}。（房间{name：3A 07}。person{name：hniss}）| floor{name: itu4}.（r oo m{name：4A05}|（r oo m{name：4A09}。person{name：hilde}）），其中所有属性值都应该是常量。Q接下来我们定义进程上下文表达式。上下文表达式添加孔以及到过程表达式的链接映射（替换）定义2.7对于一个签名<$i =（N，N，Att，ar），由语法W：：= σ ||R语言-进程上下文R：：= R||R|P |0个宽流程上下文P：：=κ{i：xi}i∈ar（κ）. P|P|P|1|[]j素数存在于文本中，其中κ∈ N，xi∈N，j≥0，σ：N→N是有限替换，即. 的集合dom（σ）={x|（x） x是有限的。 上下文的结构一致性是定义为过程。Q我们引入了一个常数的概念，它对应于π-演算中发现的差异的概念.其思想是，即使将进程置于上下文中，也不能更改常量名称。然后，我们根据以下规则相对于一组常量CN键入流程上下文：C0：I→0C1：I→1C=0→1，j∈J，κ∈εC[]j：J→1Cκ{i：xi}i∈ar（κ）. P：I→1CP：I→1CPJ：J→1CP|PJ：IJ→ 1CR：I → nCRJ：J→mCR||RJ：I→n+ mCR：I→n，σ||R：I→n其中I和J是自然数的有限集合。 我们经常忽略C当C→W：I→J时，简单地写W：I →J。 我们还T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6167通常省略映射σ，如果它是N上的恒等式，并且在这种情况下，说上下文有一个平凡的链接映射。一个上下文W：I→n是线性的，如果每个索引j∈I在洞[ ]j处只出现一次。对于线性上下文W：m→n（其中m={0，.，m− 1}），也可以写为W：n，其中W：0 →Ln。特别地，一个宽过程表达式r：n被认为是一个具有平凡链接映射的基线性过程上下文表达式.线性上下文可以通过一组与上述规则相同的规则来正式定义，除了null和nil过程，漏洞和并行组合的规则被规则所C0：→L0C1：→L 1C[]j：{j} →L1和CP：I→L1CPJ：J→L1CR：I→LnCRJ：J→LmCP|PJ：I J→L1CR||RJ：I J→L、n+m在那里我 J是只对不交集I和J定义的并。在进程演算的语义中，允许反应的上下文通常被称为求值上下文。在双图反应系统的理论中，求值上下文被定义为线性上下文，其中所有孔都纯粹嵌套在来自活动前缀的子签名前缀的 这捕获了标准过程演算的评估上下文。 对于子签名，我们通过规则C，CW：I→LJ作为线性上下文的规则，除了前缀的规则被两个规则C，P：→L1，κ∈C∈R，<$κ{i：xi}i∈ar（κ）. P：P→L1C，P：I→L1，I/=且κ∈C∈R，<$κ{i：xi}i∈ar（κ）. P：I→L1上下文W：I→n可以被插入到上下文WJ：n→m中，从而导致在复合上下文中WJ=W：I→m。 在合成中，W的名称根据WJ的链接图被替换，并且两个链接图被合成，并且W的第i个I. 如果上下文WJ不是线性的，这可能意味着一些次素数的被复制，其他的被丢弃。 为了正式定义合成，令Rσ表示上下文R [σ（x1）/x1.σ（x k）/x k]，对于宽过程上下文R和置换σ，其中dom（σ）={x1，.，xk}。此外，对于广义的函数R，l∈R[j：Pj]j∈I表示Pj在R中所有具有j指标的洞中的i的作用.68T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61S，n定义2.8对于上下文CW：I→n和CWJ：n→m，定义复合词com positec omte xtCWJW：I→mbσJσ||当n d W j = σ j时，||Πj∈nPj,andWJ=σJ||RJ.Q2.2反应规则我们将反应规则正式定义如下定义2.9对于一个签名，定义一组参数化的反作用规则当PReact={（C，R，RJ，n，m）|CR：n→Lm，CRJ：n → m}.Q给定一组反应规则SPReact，其思想是，一个过程r可以反应并成为过程rJ，记为r→SrJ，如果存在规则（C，R，RJ，n，m）∈S，上下文C<$W和宽过程参数rJ：n使得r<$W<$R<$rJJ和rJ=W<$RJ<$rJJ。一般来说，我们不希望所有的上下文W都允许反应，所以我们定义相对于a的反应活动前缀的子签名前缀确定如上所定义的求值上下文。对于参数反应规则和子签名的集合S，通过下式定义基S的集合，React=.. L，W RJr |L W R r，（C，R，RJ，n，m）∈S，C， W：m→L mJ和r：我们说一个过程r可以对rJ起反应，记为r→S，相对于一组反应S，<$rJ，如果（r，rJ）∈ReactS，<$r。示例2.10位置模型中的房间可以被一个人预订用于某项活动，也可以取消预订（与房间是否被占用无关）。我们通过显式维护每个房间的状态标记来建模预订状态，并给出以下流程表达式：建筑{name：itu}。关闭{name：itu 3}。房间{name：3A 07}。（人{name：hniss}|状态{bookedby：hniss}）| floor{name: itu4}.房间{name：4A 05}。（状态{bookedby：none}）| room{name: 4A09}. （人{name：hilde}|状态{bookedby：none}）现在的意图是，一个人可以预订他所在的房间，如果它还没有被其他人预订。这个条件描述了协调T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6169J在模型中处理：r oo m{name：$r}。（person{name：$p}|status{booked by：none}|[]1）−→r oo m{name：$r}。（person{name：$p}|status{booked by：$p}|[]1）也就是说，当条件满足时（一个人在一个空闲的房间里），我们只需更改bookedby属性。由于房间里可能有不止一个人，我们必须确保其他人留在房间里;为此，我们使用洞（匹配房间里任何数量的其他人，甚至我们使用的惯例是常量名用打字机的字体书写，例如none，非常量名用$并且用斜体书写，例如$p。因此，对于该示例，常数集为C={itu4，itu3，3A07，4A05，4A09，none，hniss，hilde}。Q例2.11[CCS和Ambients]然后将通常的CCS反应规则写成单参数反应规则（我们使用名称$n表示变量而不是常数的约定）：（第二幕，第{ch：$a}幕。[ ] 1|coact{ch：$a}. [ ] 2、[ ] 1|[]第2、2、1段）或act{ch：$a}。[] 1|coact{ch：$a}. [] 2−→ [] 1|[] 2它没有常数，有两个洞，宽度为1。活动前缀的集合是空的，也就是说，=。通常的Ambient规则可以写为参数反应规则（R，R，RJ， 3，1），即R−→RJ，其中R = amb{name：$b}。（在{name：$a}中。[ ] 1|[] 2）|amb{name：$a}。[3]和J.ΣR= amb{name：$a}。 []第三章|amb{name：$b}。（[] 1|[]2）使用活动前缀={amb}。Q2.3分布式可扩展进程我们让一个DiX系统是一个（部分共享）宽的宽度为n的进程和一组对等体，每个对等体都有自己的签名，反应规则和评估上下文。定义2.12定义一个双X系统为一个对（r：n，P eers），其中r =npj是一个关于widthn的宽集合，Peers={peeri}i∈I是一个关于fpeeri=（ni，ni，Jin，Si）的集合，条件是ni∈I。 ►ΣiΠj∈Jipj. Reactionsofsystemsisdefinedbyy（j∈npj：n，Peers）→（j∈npJ：n，P eers）如果有存在sani∈Isuchthatj∈Jpj→S，j∈JpJ且pj= PJ.Qi i i ij j70T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61例2.13对于位置模型，形式主义的分布式本质允许每个人（可能每个人都携带自己的设备，可以访问当前位置状态）预订他们所在的房间，而无需咨询任何其他设备。目前，所有的peer共享一个prime进程。每个都有一个反应规则，如上所述，但个性化的人与同行，例如希尔德的同行将有规则r oo m{name：$r}。（person{name：hilde}|status{booked by：none}|[]1）−→r oo m{name ： $r} 。 （ person{name ： hilde}|status{booked by ：hilde}|[]1）这些设备通过确保一个房间不会被两个人同时预订（上述情况）来协调它们的动作。两个并发的反应都看到一个空闲的房间，然后更新位置状态的明显问题是由并发管理器处理的（第二节）。3.4）。Q例2.14与预订房间无关，我们可以想象一个位置服务器（实现使用Ekahau [9]）跟踪客户端设备的位置位置服务器定期测量客户端的位置，并为每次测量在XML文档中添加客户端、位置对这是通过带外手段完成的，即，而不是反应规则。因此，位置对可以被视为系统的输入。然后，我们通过如上所述的进程p 1和进程p 2使位置状态为位置测量：building{name：itu}....... （与以前一样）|| pos{name：hniss，where：4A09 }）|pos{name: hniss, where:4A09})使位置测量与人到房间的关联一致是为系统中的对等体之一（例如，位置服务器）配备用于移动人的广泛反应规则的问题：房间{name：$from}。（人{name：$p}|[] 2）||房间{name：$to}。[]第三章|| pos{name: $p,whe re: $to}|[]1−→r oo m{name：$f ro m}。[]2||r oo m{name:$to}. （person{name：$p}|[]3）|| 1 |[]1请注意，两个房间被一个宽的平行组合分开，允许房间在不同的地板上。通过将反应规则分发给不同的对等体，我们在应用程序中获得了一个最小的（尽管不是强制的）抽象概念。我们基本上有两个系统同时运行：一个是预订房间的系统，T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6171一种跟踪建筑物中人员位置的系统。 这两个系统是正交的，不需要知道彼此。此外，这还提供了开放性，因为对等体可以将其自己的反应规则和数据（只要它们不改变其他对等体的数据的表示Q2.4与Bigraphs的线性上下文W：m→Ln对应于[ 16 ]中定义的（纯）开双图，并且它们的合成与双图上的合成的定义一致。然而，双图是显式类型化的，在内部（域）和外部（余域）有有限的名称集。 这意味着一个上下文W：m→Ln将对应于双图[W]]：nm，Xn → n nn，Yn，对于有限集合X，YnN的选择使得dom（σ）nX和σ（X）nY，如果W = σ ||R. 显式类型化可以控制哪些名称不是在双图之间并行共享这对DNF公理化至关重要在[19]中提出的空间逻辑，以及在[8]中提出的双图的空间逻辑。本文中提出的过程演算适用于CNF公理化[19]，对于CNF公理化，可以不使用显式名称，而简单地假设所有名称都是共享的。后续论文将给出一个完全类型化的演算（也包括绑定名称）。3执行在本节中，我们将描述diX演算的实现，称为分布式响应式XML。该实现基于XML Store[2，13，20]，是[22]中提出的响应式XMLXML Store是一个通用的、对等的分布式持久存储管理器，用于树形结构数据（XML文档）。基于XML Store的实现给出了一个对等分布式实现，其中通过乐观方式处理并发控制是自然的。我们首先展示如何在XML中表示（主）流程表达式。定义3.1假设一个签名。Prime XML-进程通过以下方式映射到XML：[[κ{ai：xi}ai∈ar（κ）. p]]=<κa1=”x1“.. .aj=“xj“>[[p]]/κ>[[p|pJ]]=[[p]][[pJ]][[1]]=72T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61其中κ∈ α，ar（κ）={α1，.，a j}，xi∈N，并且n是空文档。Q示例3.2将位置模型过程呈现为XML（例如，2.6）给出：<建筑物名称=“itu”><楼层名称=“itu3”><房间名称=“3A07”><楼层名称=“itu4”><房间名称=“4A 05”/><房间名称=“4A09”>Q3.1系统架构XML Store是一个树形结构值（数据）的存储管理器，具体来说，就是XML文档。存储的值以后可以通过XML Store检索。接口只允许指定存储什么，而不是存储在哪里。因此，XML Store实现可以自由地移动存储的值。一旦存储，值就由位置无关的标识符（通常是值内容的加密散列尽管表示流程的XML值本身不必分布，但这样做是有意义的。XMLStore通过使用对等路由算法（当前的实现使用Kademlia [17]）来提供其存储的值的大规模分布。这个发行版内置在XML Store中，因此应用程序员不必实现自己的发行层。XML Store中的分布是透明的，因此应用程序无法观察值是存储在本地还是远程。分布式反应式XML的基本架构是一个分布在多个对等点上的XML存储，它为客户端提供对当前流程的访问。对于应用程序员来说，这似乎只是一个XML存储。客户端通过加入对等网络或作为传统客户端连接到这个XML存储。由于人们可以想象不同的情况下，他们每个人都将是一个优势，这是有意义的，有两个选项。例如，定期更新当前流程的位置服务器很可能会受益于成为网络的一部分，而不是每次更新时都连接到XML存储。另一方面，具有较少资源的客户端（例如PDA）可能没有可用于加入对等网络的资源，因此它们将作为客户端连接到XML StoreT. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6173、、、z、CCCC你好，p你好pzJ你好，你好ıııı、、、ıııı、、、c，C......、C图1显示了一个有四个客户机的设置。每个客户端都有自己的一套反应规则（第二节）。2.2）Ri和共享进程表达式p的句柄。Clien t1、、、XMLStoreClien t2R2CccR3R4客户机3客户机4Fig. 1. 分布式响应式XML设置。3.2实施反应为了简单起见，我们将只考虑素数反应规则，即反应规则（C，R，RJ，n，1）。这意味着我们只需要考虑具有一个洞的求值上下文，并且反应总是在同一个素数过程中执行。进行反应p→S，则等于发现反应rule（C，R，RJ，n，1）∈ S，一个求值上下文C <$$>，<$σ ||R E：1 →1和a宽过程的表达式nr=nj∈npjsuchatp=RE[R[j：pj]j∈nσ]（1）并计算出PJ=RE[Rj[j：pj]j∈nσ]。我们使用递归表达式来确定求值上下文。定义3.3对于一个素过程p和一个素表达式φ，令xpath（φ，[[p]）表示[p]中满足φ的子树的根的集合。Q对于子签名，则定义如下表达式φ=//*not（ancestor-or-self：：*R174T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61[name（）=' κ 1 ' or r name（）= ' κ 2 ' or r. . name（）=T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6175对于k\k ={k1，.，κ k}。 则xpath（φn，p）确定子树p的pJ，使得p=E<$pJ，并且E是评估上下文。我们不知道RE[R[j：pj]j∈nσ]=RE[Rσ[j：pjσ]j∈n]=RE<$R σ<$rσ。 对于任意过程RJ和σ，存在一个过程r使得RJ= rσ.因此，求解方程（1）相当于在p中找到一个完整的子树t R= Rσ <$rJ，对于某个rJ和替换σ，使得子树t R的根是xpath（φ<$，p）中节点的子节点。对于某个宽过程RJ和置换，求出p中的子树tR=Rσ<$RJ我们搜索上下文R直到可能的替换σ（计算为约束），并允许R中的洞匹配任何素数过程，甚至是空树（即，nil过程1）。如果对于某些替换σ，和与洞匹配的素过程pj找到上下文Rσ，则检查上下文Rσ的根是否属于表达式φ，φ j的解集。如果是这样，匹配算法报告回替换σ、上下文Rσ的根和（该）次素数过程pj与孔匹配。这是树的标准（有序）子树问题的推广。对于标准问题，通过每次匹配模式R中的一组孩子时使用二分匹配算法，将针对源树P中的一组子树。为了进行该反应，所需要的全部是用hRJσ[j：pj]j∈n来替换p中的S_b_t R。3.3XML Store存储在XML Store中的进程是值。这意味着一个进程一旦被存储，就不会改变;换句话说，它是不可变的。由于一个值永远不会更新，我们可以自由地将它缓存在（复制到）所有感兴趣的各方。这也意味着我们必须采取特别措施来执行相当于关于进程的更新。我们不是破坏性地更新值，而是使用对旧值未更改部分的引用来计算新值。换句话说，我们共享（部分）存储值。这种共享对应用程序员是透明的[2]。这样做的结果是XML Store实际上存储的是DAG而不是树。“最新”值（系统的当前状态）被绑定到一个可以更新的句柄（实际上是从这种(i) 通过查找所有的求值上下文来查找所有可能的赎回。对于我们的示例定位系统，我们允许对所有（子）过程进行反应，因此，定位求值上下文的表达式76T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61CC将简单地选择所有节点（//*）。在Ex中对进程执行此操作。3.2将返回一个包含所有节点的集合。(ii) 将每个可能的兑换与反应规则左侧的实例化孔和变量相匹配。将流程中的所有节点与“图书室”-反应规则的左侧进行匹配（例如：2.10），将导致之间反应规则的左手边和房间4A 09，变量$r实例化为4A 09，$p实例化为hilde，hole [ ]1映射为1。(iii) 如果存在任何匹配，则可以通过基于反应规则的右侧计算reactum并重构过程表达式来执行反应。由于XML Store中存储的所有数据都是不可变的，客户端不能简单地更改流程树中的匹配节点（redex）来响应更改。他们必须建造一棵新的树。图2说明了这种情况。在反应之前，过程如图2（a）所示。反应后，图。2（b），一个新的进程已经建立，但新的节点只从必须“更新”（reactum）的节点构建在路径上，未改变的节点被重用。模型Ctc建筑模型Ctc建筑模型、、、ZZ建筑得双曲余切值.、、、，z得双曲余切值.、、、，z、、、ZZ阿卢尔阿苏尔湾埃塞尔穆尔埃塞尔穆尔cc，cc，、、、JCC，ZZJCC，ZZ，zz房间房间房间房间room_。room房间cc，cc，、、、cc，zzJ，sJcc，zzJ，sJ，O，zz人地位地位人人地位地位人地位（bookedby：（bookedby：（bookedby：（bookedby：（bookedby：hniss）无）hniss）无）希尔德）(a)（b）第（1）款图二.重用未更改的节点（虚线箭头表示重用;粗体文本表示新构造的路径）。当前进程的句柄此时仍将引用旧的根节点p.为了让其他客户端知道新进程，客户端必须更新新根pJ的句柄。句柄的此类更新（XML Store唯一可能的更新）是 使用 原子 比较 和 交换 算法 完成 的 ， 该算 法保 证 在时 间t =[tread;tswap]内没有人更改该值。通过使用这个工具，我们能够获、、、、T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6177得客户端更新到流程的简单分布。因此，最终，这就是如何进行协调。78T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）613.4同步更新上面提到的简单形式的同步可以工作，但不支持多个客户端同时检查当前进程、查找可能的反应并构建新进程的情况。为了处理这个问题，我们将允许非冲突反应（直观地说，在过程的不同部分的反应）同时发生。我们使用术语冲突反应来表示这样的情况，即我们不能在不使过程处于不一致状态的情况下将两个（或更多）反应假设两个反应规则 R1和R2在同一进程上执行。反应同时进行，因此，它们将在完全相同的状态下检查过程我们现在可以陈述两种反应相互矛盾的情况(i) 这两种反应会覆盖对方的变化。由于它们都在改变相同的节点，我们不能将来自两个反应的改变融合到一个过程树中。(ii) 一个（或两个！）这两个反应中的一个改变了另一个反应的redex。由于只有当规则匹配redex时，反应才是可能的，因此这种情况删除了一个或两个反应的初始条件如第 3.2在进程p上执行一个反应，相当于在p中找到一个匹配的子树（一个redex）t R，并将其替换为RJσ [j：pj]j∈n。 假设p中没有一个子R1，则在p中存在一个子R1. Ad-对于R2，在p中找到一个子树tR2。我们知道，当R1的子树位于R 1的子树中时，所有节点都发生了变化，而当R2的子树位于R2的子树中时，所有节点都发生了变化。因此，一个conservative对非冲突反应的估计是：如果R1不改变tR2中的任何节点，并且LikeR2不改变 tR1中的任何节点，则两个反应将不具有任何重叠的改变。定义3.4设子树是从节点到节点集的函数，对于节点n，返回包含根为n的树中所有节点的集合。让此外，tR1是p上反应R1的还原剂，tR2是p上反应R2的还原剂。我们说两个反应R1和R2是共轭的i ≠subtree（tR1）≠ subtree（tR2）/=π。Q我们可以在开放式并发控制管理器中使用这些知识，允许客户端随时检查进程表达式。然后客户会发现可能的反应。当它准备好提交其中一个反应的结果时，我们验证该反应是否与客户端检查流程和尝试提交操作之间的时间内执行的其他反应相冲突。 如果发生任何反应，T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）6179然后，我们检查该反应的redex与我们将要提交的反应的redex没有任何共同的节点。如果没有冲突，我们可以将此反应的变化纳入共享过程。在冲突的情况下，我们简单地中止提交操作。为了能够进行这种验证，我们需要跟踪执行的每个反应以及作为反应条件的匹配子树（redex）。我们用所谓的版本来捕捉这些。一个版本由生成的进程树和一个变更表组成。变更记录将原始过程树（在反应发生之前）更改为存储在版本中的过程树。因此，一个变更树由redex、结果reactum和一个表示流程树的哪一部分被重写的reactum表达式组成。例3.5再次考虑希尔德成功预订4A09房间的反应。在这种情况下，版本包含图1所示的过程树。2（b）和一个变更。转换器包含Redex房间{name：4A 09}。（人{name：hilde}|状态{bookedby：none}），再现实房间{name：4A 09}。（人{name：hilde}|状态{bookedby：hilde}），和一个表示预订了哪个房间的表达式/child：：*[1]/child：：*[2]/child：：*[2]Q现在我们可以描述XML Store中真正存储的内容，即最新版本以及通向该版本的版本列表。XML Store中共享的聚合使用避免了一次又一次地重复存储相同（部分）进程树的明显问题作为存储变更集的一个副作用，我们能够跟踪所有的变更一个反应一个反应的基础上。这为我们调试ReactiveXML提供了一个很好的特性。3.5实现细节如上所述，分布式响应式XML已经使用XML Store提供的特性（在Java中）实现。该实现涵盖了完整的分布式、可扩展的流程演算;例如，我们正在运行的示例的流程表达式和反应规则都已使用该实现执行。为了在实践中发挥作用，我们将系统与定位服务器Ekahau [9]集成，该定位服务器定位无线LAN80T. 希尔德布兰特等人/理论计算机科学电子笔记150（2006）61客户.该集成允许位置服务器直接更新位置事件的队列，但是以安全的方式，使得更新包括适当的变更信息。因此，对于其他对等体来说，这看起来像是执行任何其他反应规则的结果。该 实 现 和 位 置 模 型 示 例 可 在 Web 上 获 得：http://www.itu.dk/research/theory/bpl/reactivexml/。4结论我们已经展示了如何利用XML和双图理论的相似性来实现一个开放的、分布式的基于XML的协调中间件，该中间件具有一个简单的分布式可扩展过程演算作为正式基础，该演算包括共享数据、过程和反应规则。该实现基于以前在ITU和DIKU实现的所谓面向价值的对等XML存储。我们演示了如何价值导向的方法促进了一个廉价的实现opti-可扩展并发控制，其中完整的历史进程存储。最后，我们通过一个基于位置的服务系统举例说明了协调中间件的使用，该系统已在国际电联实施并正在运行。4.1相关工作和今后的工作双图反应系统是一个元模型，其中可以定义π演算和Ambient演算等模型，基本语义理论被定义为化学抽象机（CHAM）风格的反应[3]。基于双图反应系统，dix演算因此与这些模型密切相关。我们目前正致力于将dix演算从纯的bigraphs扩展到绑定bigraphs。 π-演算是dix-演算的一个特例。在XML实现中，绑定名称和名称传递可能表示为属性的IDREF和ID我们还计划研究与响应CHAM [10]（以及Join演算）及其后继者的关系。[10]中创建新连接模式的能力似乎与使diX演算的反应规则成为状态的一部分密切相关，因此可能动态创建（然而，这也允许更改现有规则）。我们还考虑了如何扩展的dix演算，使对等点的连接成为动态的，在实现中通过支持移动对等点和断开连接的操作。我们计划研究一般偶图理论的应用，例如[7]的空间逻辑和互模拟的一般理论，