ABSTRACT PARALLEL MACHINES
J. O'Donnell, G. Rünger
Abstract.
Any
parallel programming language provides a model of parallelism, which is accepted
implicitly when programming directly in the language.
We propose a more flexible approach to models of parallelism: in our
methodology, the program is derived in a sequence of steps, where the algorithm
version in each step incorporates just one decision and is based on a specific
model of parallelism called an abstract parallel machine chosen to be suitable
for that step. Each version of the algorithm is proved equivalent to the
previous one. An abstract parallel machine is described by a set of
parallel operations describing its behavior, and is related to similar abstract
parallel machines by transformation theorems.
In this paper we present the formalism for abstract parallel
machines and illustrate the derivation process with two case studies.
MULTIVALUED DEPENDENCIES AS INFERENCE RULES ON A
DEDUCTIVE PROCESS UNDER A RELATIONAL DATA MODEL SET-THEORY APPROACH
M. Millán,
M. C. Fernández-Baizán, E.
Menasalvas Ruiz, R. Portaencasa Baeza
Abstract.
A
set-theoretic interpretation of the relational model was proposed by Spyratos
and Lecluse [17]. It is also contended [16] that multivalued dependencies (mvd)
can be treated as inference rules. In this paper multivalued dependencies
are treated as inference rules rather than as integrity constraints, and
an Extended Query Model for deductive query answering is given. The Extended
Query Model is considered as an extension of the Query Model [18] because it
also includes multivalued dependencies treated as inference rules. The old query
model considers only functional dependencies. They are analyzed to establish how
they affect query processing in relational databases.
SOME ESSENTIAL SIDE-EFFECTS OF PROLOG ON A
DISTRIBUTED IMPLEMENTATION
L. Araujo
Abstract.
This
work describes an implementation of some essential side-effects of Prolog:
cut, findall, and
input/output, on a distributed memory system. The techniques designed are
advantageous when applied to parallel systems based on recomputation, such as
PDP (Prolog Distributed Processor), a model for Independent_AND/OR parallel execution of Prolog.
Nevertheless, they are also valid for any distributed memory system. The
implementation of the cut predicate exploits as much parallelism as possible,
including the parallel computation of branches of the search tree which depend
on a cut. However, the computation of a branch which does not depend on a cut is
never delayed to control computations depending on a cut. The model proposed for
the findall predicate reduces the
communication as much as possible by distributing the control of the execution
of findall, and takes advantage of the success paths used in the recomputation
to perform the sorting of the solutions. The PDP model for the exploitation of
combined parallelism has allowed a straightforward introduction of the
input/output predicates. Results obtained with an implementation of the models
on a network of workstations by means of the PVM (Parallel Virtual Machine)
software package are presented.
THE
IRRELEVANT VALUES PROBLEM IN THE ID3 TREE
D. Chiang, W. Chen, Y.-F. Wang, C.-F. Hsu:
Abstract.
When
a decision tree is represented by a collection of rules, the antecedents of
individual rules may contain irrelevant conditions. To avoid generating rules
with irrelevant conditions, we propose a new algorithm to remove irrelevant
conditions of rules in the process of converting the decision tree to rules
according to information on the decision tree. Since irrelevant conditions are
removed from the resultant rules, the resultant rules are more
general than those represented by the decision tree. As a side effect, the
resultant rules are less likely to suffer from missing branches.
SCHEMA
EVOLUTION IN SOFTWARE ENGINEERING
DATABASES --- A NEW APPROACH IN ADELE
ENVIRONMENT
M. Ahmed-Nacer, J. Estublier:
Abstract. This paper discusses schema evolution in software engineering databases. After a study of existing approaches, we show that these approaches do not satisfy software engineering requirements. Then, we present our model, which supports multiple schema compositions and multiple evolution policies, each application being free to define its evolution strategy. Management of our system is based on class versioning. The consistency of the database and the various evolution policies are controlled by consistency constraints. The schema composition uses software configuration techniques and evolution policy definition uses the capability of the active database of the Adele system.