Xref: utzoo ont.events:1429 uw.talks:116 uw.cs.grad:103
Path: utzoo!utgpu!watserv1!watmath!maytag!water!wlrush
From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: DATA BASES SEMINAR
Keywords: Prof. Liwu Li, Dept. of Comp. Sci., Univ. of Waterloo
Message-ID: <2895@water.waterloo.edu>
Date: 12 Jan 90 18:16:13 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 40


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.