wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (12/01/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA BASES SEMINAR
-Thursday, December 7, 1989
Professor Opher Etzion, Temple University, will speak
on ``PARDES - An Enhanced Active Database System.''
TIME: 3:30 p.m.
ROOM: DC 1302
ABSTRACT
Traditional databases are passive. They do only what is
explicitly requested in the user's query or update
operation.The active database paradigm states that a
database may react in an intelligent way to an external
input by creating and executing database operations,
which, though not explicitly requested in the input,are
required to preserve invariants associated to the data
base.
This paradigm replaces many operations traditionally
implemented by application programs with descriptive
definitions that are part of the data model.
There are some implementations of this paradigm. The
most notable are POSTGRES, HiPAC, SAPIENS. Most of the
implementations are TRIGGER- ORIENTED. While triggers
are flexible, it is very difficult to control
interrelationship between triggers. Our model employs a
different app- roach which extends the current
implementations in the following ways:
1. It increases the expressive-power of the language
used to define the database schema by allowing the
specification of a richer class of invariants
(stated as equations) than is currently
supported. Example:[SALARY := BASE-SALARY + BONUS +
1000* count(SUBORDINATES)] The proposed language is
compact yet powerful. It reduces the cost of
development and maintenance of database update
applications and reduces the problems of validation
November 30, 1989
- 2 -
and verification thus improving reliability.
2. It provides an efficient algorithm for generating
the auxiliary operations required to preserve the
invariants after an update [In other models
these operations have to be explicitly coded,
either in the application program or in the
database schema.]
3. It provides a control algorithm that guarantees
minimum updates in the database per transaction
as well as a deterministic update sem- antics.
4. Existing models handle exceptions either by
disallowing them, or by requiring the user to
specify exception-handling routines for any
exception. Our model introduces the notion of
Exception-Handling Mode, proposes a number of such
modes, and specifies how modes can be defined in
the data base schema. [ An exception handling
mode represents a general method for handling a
class of exceptions. ] The modes we propose
eliminate a large portion of the exception-
handling code that currently exists in application
programs.
In the talk I will briefly survey the motivations
behind the active databases discipline, and refer to
some related work. The properties of the PARDES model
mentioned above will be presented using examples.
November 30, 1989wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (01/13/90)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA BASES SEMINAR
-Monday, January 15, 1990
Professor Liwu Li, Dept. of Computer Science,
University of Waterloo will speak on ``Fast In-Place
Verification of Data Dependencies.''
TIME: 3:30-4:30 p.m.
ROOM: DC 1304
ABSTRACT
Several fast and space-optimal sequential and parallel
algorithms for solving the satisfaction problem of
functional and multivalued dependencies (FDs and MVDs)
are presented in this talk. We propose two frameworks
to verify an MVD for a relation, and implement them by
exploiting the existing fast space-optimal sorting
techniques. The space-optimality means that we need
only a constant amount of extra memory for the
sequential implementations, and O(M) amount of extra
memory for parallel algorithms that use M processors.
This feature makes the algorithms particularly
attractive whenever space is a critical resource and
I/O transfers should be reduced to the minimal, this is
often the case for relational database systems. With N
denoting the number of tuples in a relation, we show
that the FD and MVD verification can be done in-place
in a time of O(N log N) for M=1, and in a time of
O((N/M+log N)log N) for M <= N, which implies a time of
O((Nlog N)/M) for M <= N/log N. We also discuss the
effect of relation modification on FD and MVD
verification.