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合金中离子键的存在使其非晶形成能力增强。非晶与晶态合金的总结构能差越小的过渡元素使其形成非晶的驱动力越强，对非晶形成越有利，由此得出的规律与上述共价键的作用规律一致。     

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

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

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.     

蛇形益智魔方的三维路径求解算法

蛇形益智魔方是智力魔方的一种,由27个两两相连的小正方体组成。文章通过计算机图形学的概念建立空间三维坐标模型,对模型中关键点进行分析归类,对空间中每个方块体可能的坐标点进行了递归公式推导,最后利用三维空间坐标的遍历算法来寻找蛇形魔方所有可能的解,指出了模型的使用前景。     

一类递归编程的特殊方法探讨

介绍了递归模型的一般形式、递归程序的执行过程及递归程序设计.重点从数学公式的角度探讨了复杂递归问题的一类特殊编程方法及其应用.     

LU分解递归算法的研究

将递归方法引入稠密线性代数的计算，能产生自动的矩阵分块，使算法适合于当今分级存储高性能计算机的结构，提高运算速度。文中对解线性代数方程组的LU分解递归算法进行了研究，给出了算法的详细推导过程。