（计算机软件与理论专业论文）实时数据库中基于图的主动规则系统.pdf

华中科技大学博士学位论文 摘要 实时数据库的事务和数据具有显式的定时限制，系统的正确性既要满足逻辑约束又要满 足日i 间约束。实时应j l j 环境还具有嵌入式和反应式的特征，在实时数据库中完善集成主动规 则机制，用于实时数据库的反应式行为，是主动实时数据库系统研究中的重要方面。 主动实时数据库系统中的主动规则不仅可应州于实时系统的反应式行为，还可以支持其 它重要的实时应_ 1 1 j ，例如实时事务的接纳( a d m i s s i o n ) 控制、系统资源管理、实时事务的预 分析预处理、以及用于不能满足截止期的实时事务的替代策略或应急措施( c o n t i n g e n c yp t a n ) 等等。现有研究中，主动规则的研究是系统的薄弱点，使用的规则模型一般局限于e c a 模型， 该规则源于人工智能的产生式规则，直接将e c a 规则模型用于数据库系统存在一定的局限性 与不足。另外，主动实时数据库系统中存在一个不可回避的矛盾：一方面，实时系统是反应 式系统，需要主动规则系统的支持；另一方面，用于反应式行为的主动规则的触发执行，将 影响实时事务的完成时间。现有的研究对上述矛盾通常采用回避或使用简化的解决方法。 f 鉴于以上背景我们提山“实时数据库中基于图的主动规则系统”这一课题，l 旨在全面 、 深入地研究实时数据库中的主动规则系统。在分析现有规则模型的基础上，提出一种基于图 的规m n 模型e - r g 。并全方位地研究该规则模型的应用优势以及该规则系统的理论基础，内容 包括规则系统的形式定义。规则触发执行的耦合方式、规则执行模型、规则系统的形式语义 等。 在主动实时数据系统的实现研究中，许多研究结果与原型系统实现是基于非实时的通用 操作系统平台。为此，本论文研究的后一部分，基于支持主动实时数据库的实时操作系统 a r t s - o s ，充分应用实时操作系统支持实时应用的技术特点，在本论文前一部分的理论研究 基础上研究主动实时数据库系统a r t s r o 的实现技术。 ， ( 基于图的主动规则模型可描述为包含“事件”、“规则图”、以及“耦合方式”的三元组， “规则图”由c a 规则集以及它们之间的控制结构组成，控制结构包含三类“规则关系”，即 “依次关系s ”、“同步关系r ”与“并发关系p ”，规则图是一种有向的有限无环图。“耦合方 式”包含了规则系统触发执行的处理语义，影响规则系统的表达能力与实现策略。 本论文形式、准确地定义了基于图的规则模型e r g 的语法，同时给出由c a 规则间的 时序关系构造三类规则关系s 、p 、y 的转换算法，保证规则图的l e 确形成，并讨论了e - r g 华中科技大学博士学位论文 规则的行为特征及其所具有的应_ i j 优势。在此基础上，研究规则执行语义所包含的规则触发 耦合方式，该问题的研究一直未得到应有的重视，我们严格地分类耦合方式为“同步类”和 “异步类”，并准确地定义“同步立即”、“异步立即”、“推迟”、“同步分离”以及“异步分离” 耦合方式等，同时对比了“同步类”和“异步类”触发耦合在实现上的差异。耦舍方式的严 格分类消除了“相同的耦合方式在不同的系统中却具有不同的语义”的混乱现象，也为规则 系统的正确实现奠定了基础。 基于图的规则系统e r g 的执行使用了一类主动嵌套事务模型，本文通过一阶逻辑形式 框架对其进行结构化定义描述，同时研究了e - r g 语言的正确性标准、并发控制锁协议与正 确实现规则图执行的调度算法。由于现有的主动规则系统没有统一的规则机制，对规则系统 的一般性描述造成规则语言理解和使用的困难为此，我们进一步研究了e - r g 规则语言的 形式语义，描述了e r g 规则指称语义的语义域、支撑函数、以及语义函数并根据幂域理 论，使用泛函的最小不动点准确地描述了e r g 规则的“规则间并发性”和“规则内并发性” 对规则系统本质刻画的形式语义是正确实现和理解规则语言的关键，由于其重要性。规则语 言的形式语义研究已成为数据库领域的一个热点，但是，由于规则系统形式语义的描述具有 较大的难度。所以在现有众多的规则系统中，仅有极个别的系统描述了规则的形式语义 在上述理论研究的基础上，基于实时操作系统a r t s - o s ，进一步研究了a r t s - r g 系统 的实现。实现研究包括系统的体系结构、模块功能和策略以及实现方法，并在试验系统上实 验考察了主动规则的执行对实时事务的影响、以及不同的实时调度和并发控制策略对实时事 务的影响 本文的研究还提供了另一种途径去解决前述的主动与实时之间存在的一个不可回避的矛 盾，即“实时系统具有反应式行为需要主动规则系统的支持，另外主动规则的触发执行不利 于实时事务及时完成”。基于图抽象的规则能够充分地发挥现代并行计算环境系统的优势，以 高性能处理器或多处理器或分布式处理环境为基础，能够有效地增强基于图的实时主动规则 系统对实时事务处理的可预测性。另外基于图的主动规则的执行使用主动嵌套事务局部化 a b o r t 或r o l l b a c k 对整个事务的影响，便于实现为满足硬实时事务的时间约束使用的可控制的 不精确性计算策略产7 关键词：主动实时数据库，主动规则，并发性。嵌套事务模型，指称语义，耦合方式， 实时操作系统。 n 华中科技大学博士学位论文 a b s t r a c t r e a l t i m ed a t a b a s es y s t e m sn e e dt of a c et h ec h a l l e n g eo fs i m u l t a n e o u s l ys a t i s f y i n gd a t a c o n s i s t e n c ya n dr e a l - t i m er e q u i r e m e n t s t h et r a n s a c t i o n sa n dd a t ai n r e a l - t i m ed a t a b a s es y s t e m s h a v ee x p l i c i tt i m ec o n s t r a i n t s t h ec o r c c c tc r i t e r i ao f t r a n s a c t i o ne x e c u t i o n sm u s ts a r i s f yb o mt i m i n g a n d l o g i c a lc o n s t r a i n t s i na d d i t i o n a l ，f o rm a n y r e a l - t i m ea p p l i c a t i o n s ，s u c h i nc o n t r o ls y s t e m s ，a r 船l - t i m ec o n s t r a i n ti si m p o s e do nat r a n s a c t i o nt og u a r a n t e et h a tt h es y s t e mw i l lh a v ear e s p o n s et o at r i g g e ri nt i m e a n dt h i sk i n do ft r i g g e r su s u a l l yd e p e n d so ns t a t e so ft h ed a m b a s e ，a n dt h u st h e d a t a b a s es y s t e m sa r ec h a r a c t e r i z e db yb o t hr e a l t i m ea n da c t i v e n e s s s i n c er e a l - t i m es y s t e m sa r e i n h e r e n t l yr e a c t i v ea n di t s h o u l dr e s p o n di nt i m et oe x t e r u a ie v e n t so c c u r r i n gi nt h ee x t e r n a l e n v i r o n m e n ta n di n t e r n a le v e n t s ，i ti s n e c e s s a r yt os e a m l e s s l yc o m p o s ea c t i v e r u l es y s t e m so f r e a c t i v em o d e l si n t or e a l t i m ed a t a b a s es y s t e m s r e c e n tr e s e a r c hw o r kh a sb e e nc a r r i e do u ti nh o wt l l ee v e n t - c o n d i t i o n - a c t i o nf e c a ) r u l e s c a nb ee x t e n d e dt oi n c l u d et i m ec o n s t r a i n t sa n dh o w p r e d i c t a b l eb e h a v i o rc a nb ee n s u r e d ，b u tm o r e r e s e a r c h e sh a v et ob ed o n e t h e c o n c e p t o fa c t i v er u l eo r i g i n a t e sf r o mt h ep r o d u c t i o nr u l ep a r a d i g m i na r t i f i c i a li n t e l l i g e n c e ，i tc a nh ea p p l i e di ni n t e g r i t yc o n s t r a i n ta n dt h eo t h e ra p p l i c a t i o n si n d a t a b a s es y s t e m s ，s u c ha s ，a d m i s s i o no fr e a l t i m et r a n s a c t i o n st op r e v e n ts y s t e m so v e r l o a d ，t h e m a n a g e m e n to ft h es y s t e mr e s o u r c e s ，p r e - a n a l y z ea n dp r e - p r o c e s s i n go fr e a l t i m et r a n s a c t i o n e x e c u t i o n s 。c o n t i n g e n c yp l a n s o ra l t e r n a t i o n sf o re x p o r e dd e a d l i n et r a n s a c t i o n sa n ds oo n h o w e v e r , t h ep r o b l e mt ob ea d d r e s s e di sn o ts i m p l yo n eo fi n t r o d u c i n gr e a c t i v em e c h a n i s m si n t oar e a l - t i m e d a t a b a s e o nah a n d ，t h e r ea r ed i s a d v a n t a g e st h a tt h ee c ar u l em o d e li s a p p l i e di nr e a l - f i m e d a t a b a s es y s t e m o nt h eo t h e rh a n d ，p r e d i c t a b i l i t yi so fp a r a m o u n ti m p o r t a n c ef o rar e a l - t i m e d a t a b a s e ，b u tr e a c t i v em e c h a n i s m sw i l l e n h a n c eu n p r e d i c t a b i l i t y w h e nar u l ei s t r i g g e r e d i n i m m e d i a t e ，d e f e r r e d ，d e t a c h e dc o u p l i n gm o d e so rc a s c a d et r i g g e r i n gm o d e ，t h ee x e c u t i o nt i m eo f t h et r i g g e r i n gt r a n s a c t i o nw i l li n c r e a s e i no r d e rt os o l v et h ep r o b l e m sm e n t i o n e da b o v e r e s e a r c hp r o j e c t ”g r a p h b a s e da c t i v er u l e s y s t e m s i nr e a l - t i m ed a t a b a s es y s t e m s ”i sp r o p o s e d t oo v e r c o m es o m es h o r t c o m i n g so f t h ei c a r u l em o d e l ，w e p r e s e n t s ag r a p h - b a s e dr u l e m o d e l ，a p p l i c a t i o na d v a n t a g e a n d p r i n c i p l e o n g 豫p l 卜b a s e d a c t i v er u l ei nr e a l - t i m ed a t a b a s e s y s t e m sd e e p l y s t u d i e di nt h i sd i s s e r t a t i o n r e s e a r c h i n ga s p e c t s i n c l u d e st h ef o r m a ld e f i n i t i o no ft h e g r a p h - b a s a dr u l e ，c o u p l i n gm o d e s 。 e x e c u t i o nm o d e la n df o r m a ls e m a n t i c so f t h er u l es y s t e m 华中科技大学博士学位论文 t h eo t h e rp a r to ft h i sd i s s e r t a t i o ns t u d yi m p l e m e n t a t i o no f t h eg r a p h b a s e dr u l es y s t e mi n r e a l t i m eo p e r a t i n gs y s t e m i td o n tb eb e l i e v a b l et h a tt h ep o w e r f u lr o b u s ta c t i v 。r e 8 i t j “。d a r a b a s 。 s y s t e mw i l lb eb u i l t o nt h eg e n e r a ln o nr e a l - t i m eo sp l a t f o r m ，s ow ei m p l e m e n t at e s t - b e ds y s t e mo f f e a i t i m ea c t i v er u l eb a s e do nar e a l - t i m ea t r s - o sb yu s i n ge x c e l l e n tr e a l - t i m ef e a t u r eo ft h e r e a l t i m e0 s g r a p h b a s e dr u l em o d e le r gc a nb ed e s c r i b e di n3 - t u p l e t h er u l e e r a p hi s d e f i n e da san e t w o r ko fc ar u l e sa n dt h e i rc o n t r o la s s o c i a t i o n s t h er u l ea s s o c i a t i o n sa r e c l a s s i f i e di n t os e q u e n c e ( s ) ，s y n c h r o n i z a t i o n 4 ( y ) a n dp a r a l l e l ( p ) a s s o c i a t i o n s ，a c c o r d i n ga st e m p o r a l s e m a n t i cr e l a t i o n sa m o n gc ar u l e s ，a n dt h er u l eg r a p hi sf i n i t ed i r e c t i v eg r a p hs t r u c t u r ew i t h i nn o l o o pp a t h c o u p l i n gm o d e s c a ns p e c i f yt h et r a n s a c t i o n a lr e l a t i o n s h i pb e t w e e nar u l et r i g g e r i n ge v e n t a n dt h ee x e c u t i o no fr u l ee r a p h ，a n dc o u p l i n gm o d e sa l s od e n o t e de x e c u t i o ns e m a n t i c so fr u l e s y s t e m 。e x p r e s s i o n a lc a p a b i l i 吼a n da r c h i t e c t u r eo f r u l es y s t e m i nt h ed i s s e r t a t i o n ，w ef i r s t l yd e s c r i b e dt h ef o r m a ld e f i n i t i o na n ds y n t a xo ft h eg r a p h - b a s e d r u l em o d e l ，a n dg i v e nat r a n s l a t i o na l g o r i t h mw h i c hc a r lt r a n s l a t et e m p o r a la s s o c i a t ew i t h i ns i m p l e c ar u l ei n t or u l er e l a t i o ns ，y ，p t h et r a n s l a t ea l g o r i t h mg u a r a n t e et h a tt h er u l eg r a p hc a nc o r r e c t l y b ec a n s t r u c t e d i na d d i t i o n ，t h e a p p l i c a t i o na d v a n t a g e s o fg r a p h - b a s e dr u l em o d e lh a db e e n d e s c r i b e d s e c o n d l y , w ef o c u so nt h ec o u p l i n gm o d e sf o rc o n c u r r e n ta c t i v er u l e sa n df u r t h e rc l a s s i f yi t i n t os y n - c o u p l i n ga n da s y n - c o u p l i n g ，a c c o r d i n gt ot h ek e yi s s u e ，s y n c h r o n ya n da s y n c h m n y , i n p a r a l l dp r o g r a m m i n gl a n g u a g e b yt h i sm e t h o d ，w e c a ne s c a p ef r o mt h ec o n f l i c ti nw h i c h m e a n i n g s o ft h ef m i n ec o u p l i n gm o d ea f ed i s s i m i l a ri nv a r i o u sa c t i v ed a t a b a s es y s t e m s w ea l s os h o wt h e v a r i o u ss t m t a g i e st oc o n s t r u c tt h es y n - c o u p l i n ga n da s y n - c o u p l i n gm o d e si ne r gr u l es y s t e m ， b a s e do ns e m a n t i c sf o rc o u p l i n gm o d e s n e x t , w ed e s c r i b e dt h ee x e c u t i o nm o d e lo fg r a p h b a s e dr u l es y s t e mt h a ti sak i n do fa c t i v e n e s t e dt r a n s a c t i o nm o d e l t h ee x e c u t i o nm o d e lh a db e e nf o r m a l l yd e f i n e db yaf i r s to r d e rl o g i c f o r m a lf r a m e w o r ks y s t e m w ep e r f e c t l yd e s c r i b et h ec o r r e c tc r i t e r i a , c o n c u r r e n tc o n t r o ll o c k p r o t o c o l s ，a n ds c h e d u l em a c h i n e t og u a r a n t e ec o r r e c ts e m a n t i c so f r u l eg r a p h a l t h ee n d 。t h ed e n o m t i o n a ls e m a n t i c so f e r a p h b a s e dr u l em o d e la r ed e s c r i b e d w h i c hb e n e f i t s t ot h ea c t i v ed a t a b a s es y s t e m sf o rt w om a j o r r e a s o n s f i r s t l y , t h ef o r m a l i z i n gs e m a n t i c so f t h ea c t i v e r u l ee s 饿q j e sf r o mt h ea m b i g u i t yt ou n d e r s t a n di n f o r m a ls e m a n t i c so ft h ea c t i v er u l e s e c o n d l y ，t h e f o r m a l i l m t i o np r o v i d e st h eb a s i st o c o r r e c t l yi m p l e m e n tt h ea c t i v e r u l es y s t e m s s i n c ea b o v e b e n e f i t s , t h ef o r m a ls e m a n t i c sf o rr u l e l a n g u a g eh a db e e nr e s e a r c h e di n t e r e s t i n g l y i nv a r i o u s s y s t e m s n e v e r t h e l e s s ，t h ew e l l k n o w nd i f f i c u l tt os p e c i f yf o r m a ls e m a n t i c so fr u l el a n g u a g eh a d 华中科技大学博士学位论文 r e s u i ti nt h a tt h ef o r m a ls e m a n t i c sh a db e e ng i v e n i nr a r e l yr u l es y s t e m s d e n o t a t i o n a is e m a n t i c so f e r ga r e d e s c r i b e dw i t hs e m a n t i cd o m a i n sa p p r o p r i a t et ot h ee _ r g r u l el a n g u a g ef i r s t l y i s s p e c i f i e d ，a n da u x i l i a r y f u n c t i o n so v e rt h e s ed o m a i n st om o d e lr e l a t i v e o d e r a t i o n so nt h e s ec o m p o n e n t sa r ed e f i n e d h a v i n gs p e c i f i e dt h es e m a n t i cd o m a i n sa n da u x i l i a r y f u n c t i o n s s e m a n t i cf u n c t i o n s a r e s p e c i f i e d e - r gr u l e s ”i n t e r - r u l e ”a n d ”i n t r a - r u l e ”p a r a l l e l e x e c u t i o ns e m a n t i c sa r ed e f i n e d a st h el e a s tf i x e dp o i n to ff u n c t i o n s b a s e do na b o v et h e o r yf r u i t s ，w ei m p l e m e n tat e s t - b e ds y s t e mo fa c t i v er e a l - t i m ed a t a b a s e a r t s r gi nt h er e a l - t i m ea r t s - o sp l a t f o r m i nt h ep a p e r , t h ea r c h i t e c t u r e o ft e s t 。b e ds y s t e m ， f u n c t i o nm o d u l e s ，a n di m p l e m e n t a t i o ns t r a t e g yh a db e e nd e s c r i b e d i na d d i t i o n ，w ee x p e r i m e n ti n t e s t - b e dh o wt h ee x e c u t i o no fa c t i v er u l ec a u s er e a t - t i m et r a n s a c t i o n st om i s si t sd e a d l i n e ，a n dh o w t h ev a r i o u ss c h e d u l ea n dc o n c u r r e n tc o n f f o im e t h o d sa f f e c tt h er e a l - t i m et r a n s a c t i o nt om i s si t s d e a d l i n e b yt h ew a y , t h eg r a p h - b a s e dr u l em o d e li nt h ed i s s e r t a t i o ng i v e sa n o t h e rw a yt os o l v et h e c o n f l i c tb e t w e e nr e a c t i v em a c h i n e sa n di t d e l a y i n g t h er e a l - t i m e ”a n s a c f i o ne x e c u t i o n t h e g r a p h - b a s e d r u l em o d e l a d a p t s t h em o d e r n p a r a l l e lc o m p u t e ra r c h i t e c t u r e ，s o t h er e a l t i m e t r a n s a c t i o ne x e c u t i o nc a nb ep r e d i c t a b l eb yu s i n ga c t i v er u l e sd i s t r i b u t i o no rp a r a l l e lc o m p u t e d i n a d d i t i o n ，t h en e s t e dt r a n s a c t i o n e x e c u t i o nm o d e lo fe - r gr u l ec a nl o c a lt h e s c o p eo ft h e s n b - t r a n s a c t i o n sa b o r to rr o l l b a c ki nt h ep a r e n tt r a n s a c t i o n ，s ot h ee - r gr u l ec a nb eu s e dt o i m p l e m e n ti m p r e c i s ec o m p u t em e t h o d s o f h a r dr e a l - t i m es y s t e mw i t ht e m p o r a lc o n s t r a i n t s k e yw o r d s ：a c t i v er e a l - t i m ed a t a b a s es y s t e m ，a c t i v er u l e ，p a r a l l e l ，n e s t e dt r a n s a c t i o n m o d e l ，d e n o t a t i o n a ls e m a n t i c s ，c o u p l i n gm o d e s ，r e a l - t i m eo s v 华中科技大学博士学位论文 1 绪论 1 1 问题与动机 现代应用例如自动化生产、控制和通信系统、电力或数据网管理、证券交易等，一方 面要维护大量的共享数据和控制知识；另一方面其数据及应用活动有很强的时间性，要求及 时癌应当前外部环境、按彼此之间的联系存取已获得的数据和处理采集的数据、再及时作出 响应；第三，要求能自动监视特定的情形和活动，当指定的情形出现时，能自动采取相应的 行动，而这些都无需人工干预。现代应用的需求使得实时主动数据库的研究成为数据库研究 领域的重要热点。 实时数据库有别于传统数据库i l i ，其事务和数据具有显式的定时限制，系统的正确性不 仅要满足逻辑约束。而且还要满足时间约束。实时数据库系统的资源分配策略与任务调度机 制要有利于保证紧急任务的及时完成，并追求事务定时限制的满足，以及满足定时限制事务 的比率最大的目标。 实时数据库类似于实时系统，需要满足各种定时限制，但实时数据库也有别于实时系统， 它要维护数据一致性，具有数据库系统能力，且实时数据库事务的执行存在许多不可预测因 素( 如i 0 的延时、系统的负载程度、系统资源的共享冲突等) ，甚至存在不可调和的时间约 束与逻辑约束的冲突，而实时系统没有这些要求，它通常工作于可预测的资源需求以及数据 需求环境，系统致力于所有任务不违背时间约束口j 。 实时系统一般都是反应式系统，实时监控的传感器收集实时数据，触发驱动实时监控系 统上作运行。因而作为实时系统的实时数据库要完善集成主动规则机制，用于实时数据库 的反应式行为，形成主动实时数据库系统，这是实时数据库系统发展的必然结果【” 集成于实时数据库中的主动规则，一般使用e c a ( e v e n t c o n d i t i o n - a c t i o n ) 规则模型， 同时对规则模型增加时间约束的表达和处理能力，并规定主动规则触发执行的优先级，保证 规则执行的可终止性和结果的确定性1 4 j 【“。然而主动实时数据库中存在一个不可回避的矛盾： 一方面，实时系统是反应武系统，需要主动规则系统的支持；另一方面，用于反应式行为的 主动规则的触发执行，将影响实时事务的完成时间，无论是立即、推迟、分离的执行耦合方 式，以及允许规则的串联( c a s c a d e ) 触发均增加了实时事务执行的不可预测性因为立即、 华中科技大学博士学位论文 推迟触发方式直接增加了实时事务的执行时间，而分离触发的规则执行虽然没有直接增加实 时事务的时间，但增加了系统的负载，也间接地增加了实时事务的执行时间当然，如果仅 使用分离的触发耦合方式以及限制串联触发的层次数将部分地减少主动规则的执行对实时事 务的不利影响解决上述矛盾的基础必须对主动规则系统本身作出更广泛深入的研究，这是 本文研究的动机之一。 主动规则源于a l 知识表示的产生式系统，将其引入数据库系统，不仅增加了数据库的知 识表示和推理能力，也改变了数据库的响应执行方式。主动规则在实时数据库系统中的重要 应用还包括：实时系统的资源管理、实时事务的接纳控制( a d m i s s i o nc o n t r 0 1 ) 以及实时事务的 应急措施等( c o n t i n g e n c yp l a n ) 1 6 1 1 ”、实时事务的预分析预处理i 】1 9 j 等等。完善地构造上述基于 主动规则的重要应用也直接依赖于对规则系统的能力、执行模型的特性以及规则系统与实 时数据库管理系统的集成方式作出全面深入的理解和掌握 在主动实时数据库研究领域，对规则系统的研究显得较为薄弱规则系统一般局限于 e c a 规则模型。鉴于此，我们提出“实时数据库中基于图的主动规则系统”这一研究课题， 在全面深入地分析现有规则模型的基础上。提h 1 1 - - 种基于图的规则模型e r g ，并研究基于图 的规则模型的系统理论基础，包括规则系统的形式定义、规则触发执行的耦合方式、规则执 行模蠹、规则系统的形式语义、以及规则系统的实现策略。 任何理论都应该和实践紧密结合。在理论研究的基础上，开发了“实时主动规则系统试 验平台”，并且不同于已有的平台，该试验平台的实现基于我们开发的支持主动实时数据库系 统的实时操作系统a r t s - o s 它对实时系统的资源管理、实时调度、接入控制和可预测性研 究等柙具有重要的作用。 1 2 实时主动数据库的研究 1 2 1 实时数据库的研究热点 数据库系统中对时间的处理有两方面：。实时和时态1 1 0 1 。时态数据库就是在数据 库中引入“时问”维，丽实时数据库乃指事务和数据都可具有显式的定时限制，系统的正确 执行既器满足逻辑约束又要满足时间约束1 1 1 1 1 ”j i l 3 l 。同时满足这两种一致性要求的实时数据库 事务的处理与传统的数据库相比具有更大的困难。事务处理中的众多不可预测因数的存在， 以及时间约束与逻辑约束的并存导致实时事务的调度策略和并发控制技术成为研究热点。 华中科技大学博士学位论文 1 2 1 1 实时并发控制 传统的并发控制的目的是保证数据的逻辑一致性，要求事务是平坦的，具有a c i d 特性 对其结构复杂且既要有逻辑一致性又要有时间一致性的实时事务，并发控制的策略则一般致 力于：放松逻辑一致性要求以满足或兼顾时间一致性要求。一般作法是在传统的乐观或悲观 并发控制基础上，加以改造以适应实时并发控制需要【1 4 j f 1 8 】。典型的方法有： e 一可串行化并发控制 e 一可串行化( e p s i l o n s e r i a l i z a b i l i t y ) 是事务处理中的一种正确性标准，它是一种更一 般的误差受限的串行化。它允许不一致性数据被读取，并控制不一致性的程度，使误差量限 制在一个指定范围，而使数据最终能达到一个一致性状态。e 一可串行化需要数据库的数据 空间是一可度量空间，文i ”使_ l je 一可串行化放松逻辑致性要求以期满足时间一致性要求 1 2 0 i ”1 。 一可串行性并发控制 一可串行性是基于“相似性”概念的止规可串行性的扩展。相似性概念是指在时间和 精确性上有微略差别的数据可以彼此替换地作为事务的读数据。相似是内在地依赖于应用 的概念，不同的事务对同样的数据对象可以有不同的相似性要求，两个值有多大的“微细差 别”才能算相似，应依特定的应用而定。相似是一种二元关系，它是自反的、对称的，但 不一定是可传递的i ”i 。 基于语义豹并发控制 可串行化不是维护逻辑一致性的唯一方法，还可以依据事务在数据库中的操作语义将事 务分类。使用兼容集而非可串行化作为正确性标准。在r h o d ei s l a n d 大学开发的r t s o r a c ( r e a l t i m es e m a n t i co b j e c t sa n dc o n s t r a i n t sm o d e l ) 系统中使用了基于语义的并发控制技术 1 1 9 i p 3 1 其它还有许多并发控制技术1 2 5 j 。如不同于乐观或悲观并发控制技术的优先级驱动的 实时并发控制协议【2 7 l 【2 8 1 1 2 9 l 、基于多版本两段锁的并发控制协议【”i 、混合乐观和时标的并发控 制协议等。 1 2 1 1 实时事务的调度算法 简单地讲，调度就是给出事务或任务执行的一个排序( 偏序) ，不同的系统目标，有不同 的调度算法。传统数据库追求的目标是系统吞吐量及平均响应时间，而实时数据库追求的目 华中科技大学博士学位论文 标是单个事务定时限制的满足及全系统满足定时限制事务的比率最大( 3 2 】1 3 3 】事务的调度是 一个n p 难度问题，依据实时事务的特点，研究人员提出各具特色的调度策略，代表性的有： 最早放行最优先( e r f - - e a r l i e s tr e l e a s e f i r s t ) 该策略将最高优先级指派给具有最早“放行”( r e l e a s e ) 时间的事务。所谓放行时间就是 事务可以开始执行的最早时间，e r f 策略的主要优点是简单而主要缺点是它根本不管事务 的截止期。 截止期最早最优先( e d f - - e a r l i e s td e a d l i n ef i r s t ) 即具最早截止期者优先级最高。这是一种获得广泛应用的调度策略，其主要缺点是它让 已过或几乎要过截止期者将获得最高优先级，而这种事务无论如何不能满足其截止期。这显 然不合适。 可达截止期最早最优先( e a r l i e s tf e a s i b l ed e a d l i n ef i r s t ) 具有最早的可选截止期者优先级最高所谓一个事务t 的截止期是当前时间“可达到” 的乃指t + ( e p ) d 。这里t 为当前时间e 、p 分别为事务t 的执行时间估算和已执行时 间，d 为其截止期。 空余时间最短最优先( l s f - l e a s ts l a c kf i r s t ) 事务t 的空余时间s = d - - ( x - t - e - - p ) ，即推迟t 的执行而仍然能满足其截止期的可推迟时 间量估算。 价值鼍高最优先( h v f - - h i g h t e s tv a l u ef i r s t ) 每一事务有一价值函数，其值最大者最优先，问题是如何合理地构造价值函数。 价值密度最大最优先( h v d f - - h i g h e s t v a l u ed e n s i t yf i r s t ) 价值密度( v a l u ed e n s i t y ) 意为事务完成时的期望价值与实现该价值所需计算量的比最 大者优先级最高这里也有如何设计价值