leff@smu.UUCP (Laurence Leff) (02/10/88)
From uunet!R20.UTEXAS.EDU!CS.TECH Thu Feb 4 23:29:54 1988
Received: by smu (5.51/4.7)
id AA08599; Thu, 4 Feb 88 21:29:45 CST
From: uunet!R20.UTEXAS.EDU!CS.TECH
Received: from R20.UTEXAS.EDU by uunet.UU.NET (5.54/1.14)
id AA10008; Thu, 4 Feb 88 14:14:23 EST
Date: Thu 4 Feb 88 13:14:01-CST
Subject: UT-CS TRS
To: trlist-request@smu.edu
Message-Id: <12372096163.47.CS.TECH@R20.UTEXAS.EDU>
Status: R
DEPARTMENT OF COMPUTER SCIENCES
TECHNICAL REPORT CENTER
TAYLOR HALL 2.124
THE UNIVERSITY OF TEXAS AT AUSTIN
AUSTIN, TEXAS 78712-1188
(512) 471-9595
ARPANET ADDRESS: CS.TECH@UTEXAS-20
TECHNICAL REPORTS, SEPTEMBER 1987 - DECEMBER 1987
PREPAYMENT IS REQUIRED.
Please make U.S. bank checks or international money orders payable to
"The University of Texas."
[ ] TR-87-34 $1.50 [ ] TR-87-41 $1.50
[ ] TR-87-35 $3.00 [ ] TR-87-42 $5.00
[ ] TR-87-36 $5.00 [ ] TR-87-43 $2.00
[ ] TR-87-37 $1.50 [ ] TR-87-44 $1.50
[ ] TR-87-38 $1.50 [ ] TR-87-45 $1.50
[ ] TR-87-39 $2.50 [ ] TR-87-46 $1.50
[ ] TR-87-40 $1.50 [ ] TR-87-47 $1.50
------------------------------------------------------------------------------
TR-87-34 VERTEX DECOMPOSITIONS OF PLANAR GRAPHS
Donald Fussell and Ramakrishna Thurimella
September 1987
16 pages
ABSTRACT: Vertex decompositions of graphs are useful in designing
fast parallel algorithms for vertex coloring. Vertex arboricity of
a graph is the minimum number of sets into which a vertex set can
be partitioned such that the subgraph induced by each set is an
acyclic graph (a forest). It is well known that the vertex
arboricity of planar graphs is 3 and that of outerplanar graphs is
2, from a result due to Chatrand and Kronk [CK 69]. In this paper,
it is shown that outerplanar graphs can be vertex partitioned into
two sets, one inducing a forest and the other an independent set.
As a result it can be concluded that all 4-connected planar graphs
can be vertex partitioned into three sets such that two of them
induce forests and the third is an independent set.
TR-87-35 INTRODUCTION TO LOGIC PROGRAMMING
Krzysztof R. Apt
September 1987
55 pages
ABSTRACT: We provide a systematic and self-contained introduction
to the theory of logic programming.
TR-87-36 DESIGN OF THE CADM BASED SORT/SEARCH/SET ENGINE
Vivekanand Bhat
September 1987
171 pages
ABSTRACT: Managing large databases involves time consuming and
computationally intensive operations such as sorting, searching and
various relational algebraic operations. These are traditionally
performed on general purpose computers. Special hardware can be
used to achieve higher speed in implementing these operations. The
design of one such system for performing sort, search and set
operations such as union, intersection and set difference, is
described. The performance of this system is compared with the
performance of general purpose computers for performing the above
operations, and it is shown that our system performs considerably
better. Implementation of a prototype is described.
TR-87-37 A DATA-DEPENDENCY BASED INTELLIGENT BACKTRACKING SCHEME FOR PROLOG
Vipin Kumar and Yow-Jian Lin
September 1987
22 pages
ABSTRACT: This paper presents a scheme for intelligent backtracking
in Prolog programs. Rather than doing the analysis of unification
failures, this scheme chooses backtrack points by doing the
analysis of data dependency between literals. The other
data-dependency based methods previously developed can not be
easily incorporated in the Warren's abstract machine, and are not
able to perform across-the-clause backtracking intelligently. Our
scheme overcomes all these problems. For many problems this scheme
is just as effective as intelligent backtracking schemes based upon
(more accurate) analysis of unification failure, and yet incurs
small space and time overhead. To demonstrate the usefulness of our
scheme, we have modified a Warren's abstract machine simulator to
incorporate our intelligent backtracking scheme, and have evaluated
its performance on a number of problems.
TR-87-38 ON IMPLEMENTING A COST-EFFECTIVE HYPERTEXT SYSTEM
Khe-Sing The
September 1987
9 pages
ABSTRACT: The current state of technology is still insufficient to
support the ideal futuristic hypermedium. It can, however, support
a hypertext for some specific applications, provided that the
system is carefully designed to fit into the technological
advantages and usability considerations. In this paper we first
discuss the requirements for a simple and yet practically usable
hypertext system, then we identify some feasible applications of
the simple system in the current practices of software development.
A feasible prototype is proposed as an example to illustrate the
technical aspects of our hypertext specification.
TR-87-39 BALANCED PROTOCOLS FOR SEQUENCING DISTRIBUTED COMPUTATIONS
Yeturu Aahlad and J. C. Browne
October 1987
50 pages
ABSTRACT: A fundamental issue in the design of distributed
sequencing protocols which greatly impacts performance is the level
of optimism at which they operate. "Optimistic" and "pessimistic"
protocols such as those proposed by [Jefferson] and [Schneider]
respectively, represent end-points of a spectrum of protocols which
we call "balanced." We illustrate with an example that the optimal
balance between the extremes of optimism and pessimism may lie
anywhere in this spectrum. We then lay the ground-work for a study
dealing with the selection of an appropriate protocol from this
spectrum and the impact of such a choice upon performance. Towards
this end, a general purpose protocol capable of executing any given
distributed program at any specified level of optimism is
presented.
TR-87-40 DISTRIBUTED PROCESSING OF LOGIC PROGRAMS
Ouri Wolfson and Avi Silberschatz
October 1987
14 pages
ABSTRACT: This paper is concerned with the issue of parallel
evaluation of logic programs. To address this issue we define a
new concept of predicate decomposability. If a predicate is
decomposable, it means that:
- its evaluation can be conducted in parallel by several
processors, without communication among them.
- the computation-time by k processors is roughly equal to
1/k of the time required by one processor.
On both accounts decomposability is a stronger notion of
amenability to parallel evaluation than the widely accepted
membership-in-the-NC-complexity-class. The reason is that the
latter notion may necessitate communication among the processors,
and may not reduce computation time as drastically.
We completely characterize three classes of single rule programs
(sirups) with respect to decomposability: nonrecursive, linear, and
simple chain programs. All three classes were studied previously in
various contexts. We establish that nonrecursive programs are
decomposable, whereas for the other two classes we determine which
ones are, and which ones are not decomposable. We also establish
two sufficient conditions for sirup decomposability.
TR-87-41 MANAGEMENT OF STRATIFIED DATABASES
Krzysztof R. Apt and Jean-Marc Pugin
November 1987
25 pages
ABSTRACT: We propose here a knowledge based management system
supporting immediate visualization and simulation facilities in
presence of non-monotonic reasoning. It is based on a special class
of indefinite deductive databases, called stratified databases,
introduced in APT, BLAIR and WALKER [ABW] and VAN GELDER [VG], in
which recursion "through" negation is disallowed.
A stratified database has a natural model associated with it which
is selected as its intended meaning. The main technical problem
addressed here is the task of maintaining this model. To solve it
we refine the ideas present in the works of DOYLE [D] and DE KLEER
[dK] on belief revision systems. We also discuss the implementation
issues and the trade-offs involved.
TR-87-42 TECHNIQUES AND DATA STRUCTURES FOR PARALLEL RESOURCE MANAGEMENT
Jit Biswas
November 1987
200 pages
ABSTRACT: The problem of managing the resources of a highly
parallel system is viewed as the problem of simultaneously updating
data structures that hold system state. We approach this problem in
an abstract data type framework. Simultaneous update may be
attained in two ways: by decomposing abstract states into
components and allowing operations to concurrently transform the
state of these components in a controlled manner, and by weakening
the specification of abstract data types in ways that are
acceptable to entities using instances of abstract data types.
This thesis contributes to parallel resource management in both
ways. First, we have considered management of system state for
computation structures consisting of arrays of computations that
differ only in indexing parameters. We have proposed simple
decompositions of the externally visible state into simultaneously
updatable components. Second, we have considered the management of
system state for weakened priority queues. The two priority
structures proposed in this thesis, a concurrent heap and a
software banyan, have been found to be efficient and effective.
We have, in addition, contributed in the area of language tools for
computations that utilize predefined abstract data type
implementations. A mechanism for abstract data type definition is
presented. To promote simultaneity of update we have defined a
significant extension of the linguistic construct of path
expressions and used it as a basis for defining implementation of
sequencing within abstract data types. The main advantage of using
extended path expressions is that in addition to synchronization
requirements, binding of activities to object decompositions may be
specified, along with runtime consistency checking, while leaving
the object implementation to the underlying system. We have
developed algorithms for the automatic synthesis of sequencing and
synchronization code.
A task level data flow language designed and implemented by us has
provided a context and a testbed for ideas presented in this
thesis.
TR-87-43 PSYCHO: A GRAPHICAL LANGUAGE FOR SUPPORTING SCHEMA EVOLUTION IN
OBJECT-ORIENTED DATABASES
Hyoung-Joo Kim and Henry F. Korth
November 1987
34 pages
ABSTRACT: One of the important requirements of non-conventional
applications such as CAD/CAM, AI, and OIS (office information
systems) with multimedia documents is schema evolution, that is,
the ability to make a wide variety of changes to the database
schema dynamically. We provided a framework of schema evolution in
[BKKK86,BKKK87] and the framework was realized in an object-
oriented database system, ORION at MCC. Schema modifications using
line-oriented interaction are difficult for the user to manage if
class lattices are complicated. The difficulty is even greater
because there are a large number of types of schema modifications.
We have designed and implemented a graphical language PSYCHO
(Pictorial Schema-editor Yielding Class Hierarchies and Objects)
for supporting user friendly and powerful schema modification in
object-oriented databases. In this paper, following a brief
overview of our schema evolution framework, we present the detailed
exploration of PSYCHO.
TR-87-44 TDFL: A TASK-LEVEL DATA FLOW LANGUAGE
Paul A. Suhler, Jit Biswas, and Kim M. Korner
November 1987
18 pages
ABSTRACT: The Task-Level Data Flow Language (TDFL) is a graphical
programming language intended for the writing of new programs and
the adaptation of existing ones. A computation is represented as a
directed graph. As each node contains a subroutine-sized task,
this is considered to be coarse-grained parallelism. The task
functions are written in standard sequential high-level languages.
Two versions have been implemented, one supporting static and one
supporting dynamic computation graphs. This paper discusses
previous data flow languages, presents the definition of TDFL,
describes its implementations on the Sequent Balance shared-memory
multiprocessors, and presents several programs and their
performance figures.
TR-87-45 QUERY LANGUAGES FOR NESTED RELATIONAL DATABASES
Henry F. Korth and Mark A. Roth
December 1987
16 pages
ABSTRACT: The nested relational model has proven useful in modeling
databases of complex objects. In this paper we consider query
languages designed specifically to exploit the power of this model.
First, formal query languages are considered: a relational calculus
defining the desired power of nested relational languages, and a
relational algebra that provides a procedural language suitable for
query optimization. Next, two higher-level languages are discussed
and compared, SQL/NF, and Heidelberg Data Base Language (HDBL). Two
extensions of these languages are considered. X-SQL/NF is a
role-join extended version of SQL/NF that incorporates an ISA
hierarchy into the semantics of the language. A recursive version
of HDBL allows the definition of a transitive closure operation on
nested relations.
TR-87-46 A PROTOTYPE VIEW UPDATE TRANSLATION FACILITY
Arthur M. Keller and Laurel Harvey
December 1987
11 pages
ABSTRACT: We describe a prototype implementation of a view update
translation facility. This facility consists of two programs: one
for defining the view and specifying the view update semantics and
the other for translating view updates into database updates based
on these semantics. The first program is run once at view
definition time and obtains the necessary semantics by asking the
view definer a sequence of questions in an interactive dialog. The
second program takes any valid requests to insert, delete, or
replace a single view tuple and performs the necessary operations,
if permitted, on the database to accomplish the view update request
without any disambiguating dialog. Prototype implementation was
simplified by not actually using a relational database system but
rather all interaction normally with the database instead is with
the person running the program. This has the advantages of clearly
showing all database operations and it eliminates the need to set
up a database with desired test or demonstration cases. The
database operations for performing a view update are those that are
necessary for validating the request and changing the database in
accordance with the specified semantics so that the view changes as
requested. Unnecessary database operations have not been observed
in this prototype system. The class of views that can be updated
using this prototype system is a large class of selection,
projection, and join views.
TR-87-47 FORMAL MODEL OF CORRECTNESS WITHOUT SERIALIZABILITY
Henry F. Korth and Gregory Speegle
December 1987
20 pages
ABSTRACT: In the classical approach to transaction processing, a
concurrent execution is considered to be correct if it is
equivalent to a non-concurrent schedule. This notion of correctness
is called serializability. Serializability has proven to be a
highly useful concept for transaction systems for data-processing
style applications. Recent interest in applying database concepts
to applications in computer-aided design, office information
systems, etc. has resulted in transactions of relatively long
duration. For such transactions, there are serious consequences to
requiring serializability as the notion of correctness.
Specifically, such systems either impose long-duration waits or
require the abortion of long transactions. In this paper, we define
a transaction model that allows for several alternative notions of
correctness without the requirement of serializability. After
introducing the model, we investigate classes of schedules for
transactions in the model. We show that these classes are richer
than analogous classes under the classical model. Finally, we show
the potential practicality of our model by describing protocols
that permit a transaction manager to allow non-serializable
executions that are correct under our model.
-------