基于触发路径的主动规则集终止性分析

为满足用户对网络服务的个性化、定制化和主动化需求,主动规则成为解决这些问题的关键技术.研究了在网络环境下基于规则的复杂应用中,大量规则集同时触发所带来的规则终止性问题,提出的分析方法确保主动规则能够有效运行,以提供更加灵活的主动服务.讨论了以静态分析方法为主的主动规则终止性分析相关工作,随后给出问题描述和相关形式化定义.分析了基于关联图的终止性分析方法的保守性,引入触发路径和有限触发环概念,提出了基于触发路径的两种终止情形分析方法,提高了规则集终止性分析的准确性,采用两阶段分析算法保证了分析效率.与相关分析方法的实验比较说明,文中方法能够更准确高效地检测主动规则集的终止性,并适应基于主动规则的其它应用.     

关联图与主动规则集的终止性分析

终止性反映了主动数据库系统良好的行为特性.目前有关主动规则集终止性分析的主要依据是触发图和活化图,其分析结果是保守的.为表达一个规则的动作可能使另一规则的条件为假的事实,引入了惰化图(deactivationgraph),并与触发图和活化图相结合,定义了更为一般的关联图(relationshipgraph).同时,给出了基于关联图的主动规则集终止性静态分析算法,提高了终止性判定的准确性.     

含环触发图对应的主动规则集可终止性分析

主动规则集的可终止性是主动数据库规则集的三大重要特征之一.主动规则集可否保证终止将直接影响到系统的应用.由于主动规则间存在依赖关系,通过对依赖关系的分析,给出了规则的触发传递闭包、依赖传递闭包等概念.以此为基础,提出了用规则触发－依赖图(T-DG)方法来分析主动规则集的终止性.特别讨论了判定含环的触发图(TG)对应的主动规则集是否保证终止的方法,给出了相应的判定算法、算法证明及分析.     

Towards a Systematic Method for Proving Termination of Graph Transformation Systems

We describe a method for proving the termination of graph transformation systems. The method is based on the fact that infinite reductions must include infinite ‘creation chains’, that is chains of edges in different graphs of the reduction sequence, such that each edge is involved in creating the next edge. In our approach, the length of such creation chains is recorded by associating with each edge label a creation depth, which denotes the minimal length of a creation chain from an edge in the initial graph to that edge. We develop an algorithm which can prove the absence of such infinite chains (and therefore termination), analyse problems of the approach and propose possible solutions.     

Abstract Interpretation for Termination Analysis in Functional Active Databases

An active database consists of a traditional database supplemented by a set of Event-Condition-Action (ECA) rules. One of the key questions for active database designers is that of termination of the ECA rules. The behaviour of the ECA rules may be obscure and their semantics is often not specified formally. Consequently, developing termination analysis algorithms and proving their correctness is a challenging task. In this paper we address this problem for functional active databases by adopting an abstract interpretation approach. By functional active databases we mean active databases whose transaction execution semantics have been expressed in a purely functional language. Although we demonstrate our techniques for a specific active DBMS which supports a functional database programming language interface, these techniques are directly applicable to other active DBMSs whose execution semantics have been specified using a functional or a denotational approach.     

基于约束的主动规则终止性分析

终止性是主动规则所需的最重要的一个性质,但规则的终止性检查通常是不可判定的.已有的静态分析方法非常保守,SQL3标准也没有提供保证终止的机制,所以商业数据库限制规则级联触发的最大次数确保终止.由于规则可看成数据库状态转换器,而约束能够表示所有可能的数据库状态,基于约束表示的数据库状态及约束求解,模拟规则处理,可得到更精确的终止性结论.     

基于活化路径和条件公式的主动规则集可终止性判定方法

支持主动规则机制已经成为现代数据库系统的一个重要特征.主动规则集的可终止性判定是主动数据库中一个核心问题之一,利用触发图和活化图的方法来判定可终止性都存在不同的保守性.为此,提出了为有效活化路径建立条件公式的思想,在此基础上给出了一个新的判定主动规则集可终止性的方法.分析的结果表明,提出的方法较现有方法可以发现更多的可终止性情形,最后给出了相应的算法及其可终止性、正确性证明.     

PEARD: A Prototype Environment for Active Rule Debugging

This research has investigated dynamic, execution-based rule analysis through the development of a Prototype Environment for Active Rule Debugging, called PEARD. PEARD simulates the execution of active database rules, supporting the Event-Condition-Action rule paradigm. Rule definition is flexible, where changes to rules can be applied immediately during a debugging session without recompiling the system. A breakpoint debugging tool allows breakpoints to be set so that the state of variables may be inspected and changed anytime a breakpoint is reached during rule execution. A rule visualization tool displays the rule triggering process in graph form, supporting different visualization granularities to help the user to understand rule execution. Color coding is also used as part of the visualization tool to help the user see where the different parts of an ECA rule are executed due to deferred coupling modes. Users can examine different parts of the rule graph display to inspect the state of a transaction at different rule execution points. Other debugging features include a means for detecting potential cycles in rule execution and a utility to examine different rule execution paths from the same point in the rule triggering process. Our experience with PEARD has helped to identify some of the useful functional components of an active rule debugging tool and to identify research directions for future active rule development environments.This research was partially supported by NSF Grant No. IRI-9410993.     

基于变宽邻域图割和活动轮廓的目标分割方法

基于图割的活动轮廓算法是一个结合图割优化工具和活动轮廓模型迭代变形思想的目标分割算法。针对算法在迭代过程中对已达目标边界的活动轮廓线所在邻域重复切割的不足,将活动轮廓线分为已达目标曲线段和未达目标曲线段,仅对未达目标曲线段进行膨胀得到可变宽度轮廓线邻域,从而减少了对邻域的切割时间。实验表明,改进算法效率提高为原来的2~3倍。     

图数据库中基于GPU的图分析计算方法

现有的图数据库对于在线分析操作大多采用基于CPU的分布式图计算引擎(如GraphX),但CPU核心数量有限的不足会导致计算效率低下,同时集群间的同步也会产生额外的通信开销.通过使用图形处理单元(GPU)对图计算进行加速,设计并实现图处理系统RockGraph.该系统能够根据用户需求从图数据库中提取出包含核心信息的子图,...     

一种基于图卷积神经网络和依存分析的财经新闻情感分析方法

财经新闻的情感分析有助于企业和投资者确定投资风险和提高经济效益,具有较高的应用价值。针对财经新闻文本,提出一种在图卷积神经网络中使用依存句法分析（Dependency Analysis-based Graph Convolutional Network,DA-GCN）的情感分析方法。该方法通过分析文档中词语的依存关系,获取句子的语序信息和文档中重要的句子成分,再通过词语在文档中的共现信息实现信息传递和对图的参数更新。在财经新闻数据集上进行的实验表明,本文提出的方法与传统深度学习方法相比,在各项评价指标上都取得显著提升。     

有界闭连通域上的非线性循环终止性分析

运用计算机代数中的Groebner基理论,对有界闭连通域上的单重非线性循环程序的终止性问题进行研究,建立了可计算的终止性判定算法. 该算法将这类循环的终止性判定问题归约为有无不动点的判定问题.     

利用移动终端和上网卡实现智能演示系统

蓝牙技术适用于短距离无线数据传输,而USB适用于和PC机之间的数据传输.本文介绍了通过移动终端和上网卡的蓝牙与上网卡的USB来实现一种新型的智能演示系统的方法.该系统拓宽了移动终端和上网卡的用途,同时使演讲者可以在演讲场所自由走动.     

基于有向带权图迭代的面向对象系统分解方法

针对如何从现存的系统中提取构件的问题,提出了一种基于有向带权图迭代分析的面向对象系统分解方法.它将面向对象系统抽象为一个有向带权图,使用迭代算法考察不同粒度的子图的独立性,并选择独立性高的作为候选构件.实验结果表明,该方法是一种有效的系统分解方法,在准确性上比现有系统分解方法有所提高.     

认证协议的有向图模型及其安全性分析

认证协议的形式化描述及其安全性分析是安全协议形式化分析的关键问题之一.为了解决以往分析方法中协议规范形式化描述存在的问题,提出了一种协议规范有向图描述方法,并在此基础上提出了协议消息构造的逆向搜索算法.用该算法分析Woo-Lam认证协议,找到了该协议一种新的攻击方法及其攻击路径.     

一种基于与或图表示的多风格肖像画自动生成方法

提出了一种基于与或图表示的多风格肖像画自动生成方法.与或图表示是一种分层次的产生式模型,能够分离肖像画的结构和风格并解释其多样性.采用这种模型,该方法能够从一幅正面的人脸图像自动地产生出一系列不同风格的肖像画.该方法将肖像画分解成各个部分,每一部分都对应许多子模板,这些子模板作为肖像画与或图中的叶子结点.而肖像画与或图就像一个"母模板"能够产生出大量的由子模板组合而成有效的新肖像画.该方法受益于多个不同风格的模板库,改变模板库的风格就能方便地更改生成肖像画的风格.文中所提供的例子表明了该方法的有效性.     

GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.     

OT系统的可复用站场图的设计与实现

目前,操作员终端(OT)系统需要根据特定的站场图去开发特定的系统。为解决上述问题,根据OT系统的开发需求,本文介绍了一种可复用的OT系统站场图的实现方法。该方法基于XML技术和组件化程序思想,能有效的缩短了OT仿真系统的开发周期,简化开发过程。采用这种方法的操作员终端系统无需重新编译就可以自动适应不同的线路情况。     

ORDBMS中主动性规则的研究与实现

归纳了ORDBMS(object-relationaldatabasemanagementsystem)主动性规则的一般描述形式,对规则各种语义、规则继承、规则操作、多规则触发以及规则的级联触发进行了全面的探讨.提出并实现了一种适用于ANGEL系统的简化E-C-A(event-condition-action)模型.该模型提供了对"更新/更新”、"查询/更新”、"更新/查询”和"查询/查询”这4类规则的支持、对C-A分离耦合模式以及对冲突执行触发器的优先级定义手段,并通过在触发约束表示中将NEW与OLD扩展为一种路径量词而提供了对集合约束的表示和实施能力.另外,还讨论了该模型中基于事务的规则行为分析方法.