Abstracts:

Silvio Salza and Massimiliano Renzetti
Dipartimento di Informatica e Sistemistica,Universita di Roma "La Sapienza", Roma, Italy; salza@dis.uniroma1.lst

The paper investigates the main issues in performance analysis and tuning of parallel database applications. More specifically we present a modelling methodology that was developed for an important class of parallel relational systems, and is devised for a strict integration with the design procedure. Our approach is meant to provide the designer with a valuable feedback since the early stages of a project, i.e. before the system is even implemented. Developing the model has required to deal with several interesting problems,and has led to some original contributions especially for the bufferpool model and the evaluation of transaction response times.(pp. 127-139)

Keywords:parallel architectures, performance evaluation, workload modelling

Ye-In Chang, Bor-miin Liu and Cheng-Huang Liao
Department of Applied Mathematics, National Sun Yat-Sen University, Kaohsiung, Taiwan, R.O.C. changyi@math.nsysu.edu.tw

Semijoins have traditionally been applied for reducing the communication cost required for distributed query processing. Semijoins whose execution will reduce the amount of data transmission required to perform a join sequence are termed beneficial semijoins for that join sequence. Beneficial semijoins include conventional profitable semijoins and gainful semijoins that are not profitable themselves but become beneficial due to the inclusion of join reducers. In this paper, based on the values of dynamic cumulative benefit (DCB), we propose an efficient algorithm for finding beneficial semijoins, i.e.,to interleave a sequence of join operations with semijoins to reduce the data transmission cost. In this algorithm, a dynamic weighted graph is constructed based on the correlated relationship among semijoins where two semijoins are said to be correlated with each other if the condition for one to be beneficial depends on execution of the other. Then, we compute the dynamic profit for each subgraph, which is recursively constructed. when there are N vertexes in the initial dynamic weighted graph, where each vertex represents a semijoin, our algorithm needs to expand (N + 1) graphs to find a solution in the best case. From our simulation study, we show that our strategy can efficiently find beneficial semijoins and requires a lower data transmission cost than does the profitable semijoin approach. (pp. 141-151)

Keywords: distributed databases, query optimization, relational databases, semijoins

Thomas Zurek
University of Edinburgh, United Kingdom

In this paper we present a framework for parallel temporal joins. The temporal join is a key operator for temporal processing. Efficient implementations are required in order to make temporal database features attractive and applicable for the many applications that are amenable. We focus on the temporal intesection as the supertype of temporal joins. A basic algorithm is presented that is based on partitioning the temporal data over its interval timestamps. It consists of a partition, a join and a merge stage. The partition stage has to replicat tuples that intersect with more than one partition range. Any sequential join technique can be used in the join stage. Two possible optimisations for reducing the overhead imposed by replication are discussed. The algorithm and its optimisations are evaluated on top of a performance model. We describe the model and give details in the appendix. The evaluation shows that both optimisations together decrease the basic costs significantly. Furthermore we can give an idea of the quantitative impact of replication overhead in parallel temporal join processing. A modest worklaoad caused a share of around 70% of the total costs; higher values can be expected in reality. (pp. 153-166)

Keywords: temporal join, parallel join, temporal databases, partitioning

Ono Kinji
Professor and Director of R&D at National Center for Science Information Systems, Japan ono@rd.nacsis.ac.jp

This paper presents the architecture of Phasme-a high performance application-oriented database system manager providing key facilities for the fast development of object-oriented, relational-based or other kinds of applications. Differing from conventional database systems, application-oriented servers are independent of a particular data model but cooperate with any, offer facilies to exploit new hardware architecture trend, are fully general to support efficiently wide range of heterogeneous objicts, and offer facilities to enforce applications consistency of related objects. Phasme, a Parallel Application-Oriented Database System (AODMS) has been designed to meet the new information systems' requirements and to use the power and the trends of the new generation of hardware. The major contributions of Phasme are the application-oriented architecture, the data storage manager, the dynamic optimization of both inter and intra-operation parallelism, and the exploitation of operating system services such as multi-threading or memory mapping for efficient executions. (pp.167-177)

Keywords: Application-oriented DBMS, Parallelism, Performance Evaluation

Wei-Pang Yang
Dept. of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C

To efficiently support continuous display for continuous media, many approaches based on the striping strategy that is implemented on a multi-disk drive have been proposed. However, the striping strategy can only support simultaneous display of continuous media which are predetermined before they are stored in the multi-disk drive. For an interactive display application, a system must support users to make any choice of objects for display even when display has started. Although Shahabi et. al. have proposed the replication and prefetching strategies for interactive display of continuous media, the combination of objects for display and the branch points for choices both have to be predetermined. Based on their strategies, they have to consider all the possible cases according to the given the combination of objects and the branch points of choices; it will require a lot of additional overhead of space and time. To reduce the overhead, in this paper, we will propose a sliding window approach to supporting interactive display for continuous media, in which we only record a little necessary information of retrieval of the following subobjects for display in a sliding window . For the way of interactive display described above, in which the combination of objects for display and the branch points for choices are predetermined, we call it off-line interactive display. As opposed to off-line, and on-line interactive display is the one, in which the combination of objects for display and the branch points for choices are dynamically determined. To support on-line interactive display, we will extend the sliding window approach to the dynamic sliding window approach. In this dynamic sliding window approach, the size of the sliding window can be changed according to the future requirements of data for display. (pp. 179-193)

Keywords: data placement strategies, digital continuous media, interactive display, multi-disk drive, real-time database systems, striping

Abdelsalam Helal
MCC,Austin, Texas 78759 helal@mcc.com

Parallel database systems are gaining popularity as a solution that provides high performance and scalability in large and growing databases. A parallel database system exploits multiprocessing to improve performance. Parallel database architectures can be broadly classified into three categories: shared memory, shared disk, and shared nothing. An important question, however, is which architecture should be used for a specific database application. Each architecture has its strengths and weaknesses. In this paper, simulation models for the three main architectures are presented. Using these models, a number of experiments were conducted to compare the system performance of these architectures under different workloads and transaction models. The goal of this work is to aid the decision making process of which architecture is better satisfying the requirements of a given database application. (pp. 195-205)

Keywords:parallel architectures:

Marko Bohanec
Jozef Stefan Institute, Jamova 39, Ljubljana, Slovenia marko.bohanec@ijs.si

Decision table decomposition is a machine learning approach that decomposes a given decision table into an equivalent hierarchy of decision tables. The approach aims to discover decision tables that are overall less complex than the initial one, potentially easier to interpret, and introduce new and meaningful intermediate concepts. Since an exhaustive search for an optimal hierarchy of decision tables is prohibitively complex, the decomposition uses a suboptimal iterative algorithm that requires the so-called partition selection criterion to decide among possible candidates for decomposition. This article introduces two such criteria and experimentally compares their performance with a criterion originally used for the decomposition of Boolean functions. The experiments highlight the differences between the criteria, but also show that in all three cases the decomposition may discover meaningful intermediate concepts and relatively compact decision tables. (pp. 207-217)

Keywords:decision table decomposition, partition selection criteria, intermediate concepts, concept hierarchy, knowledge discovery

Eugenio Zimeo
Universita di Napoli "Federico II", Napoli,Italy

Object-based parallel programming allows for the expression of ideal programs, which do not specify the mapping of objects to machine nodes. A prallel machine can efficiently execute ideal programs only if a runtime tool dynamically takes the appropriate placement decisions. This paper presents a new distributed adaptive load balancing algorithm, called PWF(Probabilistic Wave Front). It uses simple heuristics that guide the dynamic allocation of objects on the nodes of a parallel machine and their migration among the nodes. Experimental results show that PWF constantly outperforms both the random algorithm and the ACWN (Adaptive Contracting Within Neighborhood) one and therefore succeeds in accurately placing objects on the nodes of a parallel system. (pp. 219-230)

Keywords:load balancing, object-oriented programming, parallelism, actors, Trandputers

Wim Mees and Christiaan Perneel
Royal Military Academy -- Signal & Image Center, Renaissancelaan 30, B-1000 Brussels (Belgium) wim@elec.rma.ac.be

In this paper we present a semi-automatic aerial image interpretation system. The knowledge, to be incorporated into the system in order to identify the best solution for the otherwise under-constrained problem of image interpretation, is structured in a logical way and distributed over a set of knowledge sources in a blackboard system. Each knowledge source applies the knowledge representation method which is best suited for its type of knowledge. In the instances where the knowledge represented in the system is insufficient, the system will suffer from an optical illusion and the human supervisor will have to correct the solution stored on the blackboard. The main goal of the system is to free the human image interpreter from the routine object vectorization part of the work and allow him/her to focus on the interpretation of the presence of specific objects at certain positions. (pp.231-243)

Keywords:scene analysis, artificial intelligence, fuzzy expert system, blackboard system