A survey of parallel execution strategies for transitive closure and logic programs

An important feature of database technology of the nineties is the use of parallelism for speeding up the execution of complex queries. This technology is being tested in several experimental database architectures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribute data to disks under the control of different processors in order to perform selections and joins in parallel. With the development of new query languages, and in particular with the definition of transitive closure queries and of more general logic programming queries, the new dimension of recursion has been added to query processing. Recursive queries are complex; at the same time, their regular structure is particularly suited for parallel execution, and parallelism may give a high efficiency gain. We survey the approaches to parallel execution of recursive queries that have been presented in the recent literature. We observe that research on parallel execution of recursive queries is separated into two distinct subareas, one focused on the transitive closure of Relational Algebra expressions, the other one focused on optimization of more general Datalog queries. Though the subareas seem radically different because of the approach and formalism used, they have many common features. This is not surprising, because most typical Datalog queries can be solved by means of the transitive closure of simple algebraic expressions. We first analyze the relationship between the transitive closure of expressions in Relational Algebra and Datalog programs. We then review sequential methods for evaluating transitive closure, distinguishing iterative and direct methods. We address the parallelization of these methods, by discussing various forms of parallelization. Data fragmentation plays an important role in obtaining parallel execution; we describe hash-based and semantic fragmentation. Finally, we consider Datalog queries, and present general methods for parallel rule execution; we recognize the similarities between these methods and the methods reviewed previously, when the former are applied to linear Datalog queries. We also provide a quantitative analysis that shows the impact of the initial data distribution on the performance of methods. Recommended by: Patrick Valduriez     

钻石型分形晶格上BEG模型的临界行为

应用实空间重整化群方法研究了分形结构 -钻石型分级晶格上BEG(Blume Emery Griffith)模型的相变和临界现象 ,得到了重整化变换的递推关系 ,确定了重整化变换的不动点 ,并且计算了临界点附近关联长度的临界指数 发现钻石型分级晶格上BEG模型的相变温度为无穷大 ,这表明系统永远处于有序态     

军械调运方案优化算法的设计与仿真

军械调运问题的数学模型和手工算法过去已有研究,但是当问题较为复杂时,手工算法就要花费大量时间而且准确性也难以保证。针对这一缺陷,本文在已有的数学模型和手工算法的基础上,设计了一种可以用计算机实现的基于递归的算法来寻求军械紧急调运问题的最优方案,并使用面向对象的java语言将算法实现。     

一种简化的三维模糊制器

针对三维模糊控制器规则多,结构复杂,难以实现的问题,提出了一种简化的三维模糊控制器。该方法是把三个输入量分别为偏差、偏差变化、偏差的偏差变化的一维模糊控制器加权融合实现简化的三维模糊控制器。并提出了根据不同类型的被控对象设置三个加权系数。加权系数具有粗调、细调和微调的作用,类似于传统PID调节器的比例、积分和微分,实现对系统静差的消除。     

合金化对非晶形成能力影响的电子理论计算

根据分子动力学理论建立了非晶Ni64Pd16Al20的结构模型，利用Recursion方法计算了Ni64X17Al20系非晶及相应晶态的电子结构。结果表明，Ni64X16Al20合金的非晶形成能力与过渡元素局域电子态密度的双峰位置、电子得失形成的离子键及非晶与晶态合金的总结构能差有关。局域电子态密度的结果表明，A1与过渡元素间存在电子耦合一共价相互作用，合金元素使Ni64X16Al2合金非晶形成能力从强到弱的顺序是：Ir，Pt，Rh，Pd，Au，Ag，Cu；Ni64X16Al20合金中离子键的存在使其非晶形成能力增强。非晶与晶态合金的总结构能差越小的过渡元素使其形成非晶的驱动力越强，对非晶形成越有利，由此得出的规律与上述共价键的作用规律一致。     

递归程序设计方法的分析探讨

递归是设计程序的一种重要方法,文中对递归的定义及递归的基本条件进行了分析,给出了递归程序设计的基本方法,并结合数据结构中二叉树遍历和单链表结点输出的实例进行了验证,最后对递归程序进行了深度分析,说明了递归是一种有效的程序设计方法。     

高阶累积量计算优化的仿真研究

高阶累积量由于计算量大而未得到广泛的应用,所以对其进行计算优化以及算法的简化能更好的发挥其优越性,根据推导的非平稳随机过程四阶累积量精确递推估计公式,从减少四阶累积量估计的计算量,增强四阶累积量的工程实用性出发,给出了四阶累积量近似递推估计定理.只要四阶累积鼍的更新因子满足定理的条件,就能减少计算量,并且使估计的四阶累积量保持抑制高斯噪声的性能,并且根据四阶累积量的优化给出了五阶累计量的优化和仿真.从时域和频域进行了优化仿真,仿真结果证实了估计的有效性.     

基于分形参数的可控木纹纹理仿真

自然景物的模拟是计算机图形学中具有挑战性的研究方向之一.木纹纹理仿真是自然环境模拟中不可缺少的重要组成部分,但由于木纹纹理生成的复杂性和随机性,使得对其进行逼真仿真十分困难.在分析分形布朗运动以及随机中点位移法的基础上,讨论了中点位移法中各参数对分形曲线的影响,提出了一种非常简单的、基于参数可控的木纹纹理生成算法.仿真结果表明,方法具有快速、简单、高效,可控的特点,通过改变参数能较好地实现真实木纹纹理的仿真.     

一种模式匹配快速算法

在定义模式串的特征值之后,给出了判断两等长串匹配的必要条件以及两相邻子串的特征值之间的递推关系.在此基础上,提供一种模式匹配快速算法,其时间复杂度可达O(n).该算法彻底避免了回溯现象,执行效率要比RK算法高.     

The renaming problem in shared memory systems: An introduction

Exploring the power of shared memory communication objects and models, and the limits of distributed computability are among the most exciting research areas of distributed computing. In that spirit, this paper focuses on a problem that has received considerable interest since its introduction in 1987, namely the renaming problem. It was the first non-trivial problem known to be solvable in an asynchronous distributed system despite process failures. Many algorithms for renaming and variants of renaming have been proposed, and sophisticated lower bounds have been proved, that have been a source of new ideas of general interest to distributed computing. It has consequently acquired a paradigm status in distributed fault-tolerant computing.In the renaming problem, processes start with unique initial names taken from a large name space, then deciding new names such that no two processes decide the same new name and the new names are from a name space that is as small as possible.This paper presents an introduction to the renaming problem in shared memory systems, for non-expert readers. It describes both algorithms and lower bounds. Also, it discusses strong connections relating renaming and other important distributed problems such as set agreement and symmetry breaking.