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     

Designing and prototyping data-intensive applications in the Logresand Algres programming environment

The authors present an environment and a methodology for the design and rapid prototyping of data-intensive software applications, i.e., applications which perform substantial retrieval and update activity on persistent data. In the approach, the application is formally specified using Logres, a database language which combines object-oriented data modeling and rule-based programming. These specifications are translated into Algres, an extended relational algebra, thus yielding a rapid executable prototype. Algres programs embedded into a conventional programming language interface may be converted to conventional programs operating on a commercial relational system. This methodology helps automate the conversion from declarative requirements to imperative code, performing several tasks fully automatically and reducing the probability of human errors, while integrity constraints and application specifications are expressed in a declarative language, at a very high level of abstraction     

A normal mode expansion for piezoelectric plates and certain of its applications

The equations of motion of an arbitrary piezoelectric plate are represented by a set of second-order differential equations involving only the transverse spatial coordinates. This is achieved by expanding the thickness dependence in a set of basis functions derived from the solutions to the plate problem at cutoff. Techniques are presented for constructing approximate plate equations using only chosen mode amplitudes; such equations predict the true cutoff frequencies and give dispersion curves which are rigorously correct up to terms of order k(2). The coefficients in these equations can be computed analytically, and techniques for doing this are presented. Comparisons with dispersion curves calculated by partial wave analysis are given both for quartz and for lithium niobate. The theory provides a quite general basis for modeling devices such as trapped energy resonators.     

Providing Flexible Process Support to Project-Centered Learning

While business process definition is becoming more and more popular as an instrument for describing human activities, there is a growing need for software tools supporting business process abstractions to help users organize and monitor their desktop work. Tools are most effective when they embed some knowledge about the process, e.g., in terms of the typical activities required by the process, so that users can execute the activities without having to define them. Tools must be lightweight and flexible, so as to enable users to create or change the process as soon as there is a new need. In this article, we first describe an application-independent approach to flexible process support by discussing the abstractions required for modeling, creating, enacting, and modifying flexible processes. Then, we show our approach at work in the context of project-centered learning. In this application, learners are challenged to perform concrete tasks in order to master specific subjects; in doing so, they have to conduct significant projects and cope with realistic (or even real-life) working conditions and scenarios. Often, students are geographically dispersed or under severe timing constraints, because these activities intertwine with their normal university activity. As a result, they need communication technology in order to interact and workflow technology in order to organize their work. The developed platform provides a comprehensible, e-learning-specific set of activities and process templates, which can be combined through a simple Web interface into project-centered collaboration processes. We discuss how the general paradigm of flexible processes was adapted to the learning concept, implemented, and experienced by students.     

Support environment for active rule design

The lack of tools for rule generation, analysis, and run-time monitoring appears one of the main obstacles to the widespreading of active database applications. This paper describes a complete tool environment for assisting the design of active rules applications; the tools were developed at Politecnico di Milano in the context of the IDEA Project, a 4-years Esprit project sponsored by the European Commission which was launched in June 1992. We describe tools for active rule generation, analysis, debugging, and browsing; rules are defined in Chimera, a conceptual design model and language for the specification of active rules applications. We also introduce a tool for mapping from Chimera into Oracle, a relational product supporting triggers.Most of the tools described in this paper are fully implemented and currently in operation (beta-testing) within the companies participating to the IDEA Project, with the exception of two of them (called Argonaut-V and Pandora), which will be completed by the end of 1996.Research presented in this paper is supported by Esprit project P6333 IDEA, and by ENEL contract VDS 1/94: Integrity Constraint Management     

Approximate green?s function representations for the analysis of SAW and leaky wave devices

The Green?s function or boundary element method (BEM) is the preferred technique for rigorous SAW device analysis. However, because of its computational cost, its principal application is the analysis of mode propagation in periodic structures to determine parameters that can then be used in simplified coupling of modes (COM) or P-matrix models. In this paper, rigorous representations are derived that express the Green?s function in terms of a continuous superposition of modes. The derivations include detailed analysis of the Green?s function properties as a function of both frequency and wavenumber, and representations are obtained for both the slowness and spatial domains. Approximate forms are then generated by replacing the continuous mode superposition by a discrete one. The Green?s function can be approximated to any required degree of accuracy, and the resulting approximations are applicable to any type of wave on any type of substrate. The long-range spatial components in the approximate forms are represented by exponential terms. The separable properties of these terms allow this class of approximation to be applied to general SAW and leaky wave device analysis in such a way that the computational effort increases only linearly with device size.     

Spectroscopic studies of the biosorption of gold(III) by dealginated seaweed waste

Gold biosorption by dealginated seaweed waste has been studied to elucidate the mechanisms of metal uptake from solution. Dealginated seaweed was able to retain up to 1 mmol g(-1) of Au from solution at pH 3. FT-IR showed the presence of carboxylate groups on the surface of the biosorbent; however, the changes observed for the Au-bound samples suggested very little sorption to the carboxyl moieties. Colloidal Au formed on the surface of dealginated seaweed by reduction of Au(III) to Au(0) was observed using ESEM and four different types of particles were clearly identified. The Au distribution matched closely that obtained for S atoms indicating a possible link between these elements. EXAFS measurements showed that colloidal Au is present on the surface of the biosorbent. Evidence of gold reduction from Au(III) to Au(I) and Au(0) was also confirmed by the measured bond distances characteristic of the metal. The coordination number obtained by EXAFS indicated that approximately 75% of the Au on the sample was present in the colloidal form and the remaining Au was bound to S as nearest neighbor. The proposed mechanisms for Au removal from solution are reduction of Au species by components on the surface of the biosorbent to form colloidal metal followed by retention of the ionic Au(I) species at the sulfur containing sites. The results show that dealginated seaweed can be used for the cleanup of gold-containing effluents.     

What you always wanted to know about Datalog (and never dared toask)

Datalog, a database query language based on the logic programming paradigm, is described. The syntax and semantics of Datalog and its use for querying a relational database are presented. Optimization methods for achieving efficient evaluations of Datalog queries are classified, and the most relevant methods are presented. Various improvements of Datalog currently under study are discussed, and what is still needed in order to extend Datalog's applicability to the solution of real-life problems is indicated