Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!wasatch!cs.utexas.edu!tut.cis.ohio-state.edu!bloom-beacon!bu-cs!purdue!decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!cernvax!ethz!marti
From: marti@ethz.UUCP (Robert Marti)
Newsgroups: comp.databases
Subject: Re: WANTED: normalization software
Summary: Ceri & Gottlob, CACM Vol.29, Nr.6
Message-ID: <775@ethz.UUCP>
Date: 8 Feb 89 16:46:53 GMT
References: <1723@tank.uchicago.edu>
Organization: ETH Zuerich
Lines: 25
Cc: keith@cerberus.uchicago.edu, finkel%pobox.dec@decuac.dec.com

In article <1723@tank.uchicago.edu>, keith@cerberus.uchicago.edu (Keith Waclena) writes:
>         Has anyone seen or heard of a program that will assist in the
>         normalization of a relational database.  I believe I saw one
>         that was written in PROLOG but cannot remember the citation.

Stefano Ceri and Goerg Gottlob: Normalization of Relations and Prolog.
Communications of the ACM, Vol. 29, Nr. 6, June 1986, pp.524-544.

As Diederich and Milton of UC Davis found out, the Prolog implementation
described in the paper is   S L O W   !  They were able to get speed-ups
of up to a factor of 80 using Smalltalk on a Tektronix.  I did an
implementation in Modula-2 on Sun-3's (using dynamic bit vectors for
sets of attributes and dynamic arrays for sets of FDs) which was 10-50
times faster than the numbers published in the Diederich and Milton paper.
(Jim Diederich and Jack Milton: New Methods and Fast Algorithms for
Database Normalization.  ACM Transactions on Database Systems, Vol. 13
Nr. 3, September 1988, pp. 339-365).

--Bob

-- 
Robert Marti                      Phone:      +41 1 256 52 36
Institut fur Informationssysteme
ETH-Zentrum                       CSNET/ARPA: marti%inf.ethz.ch@relay.cs.net
CH-8092 Zurich, Switzerland       UUCP:       ...uunet!mcvax!ethz!marti