Browse Prior Art Database

RELATIONAL SCHEMA GRAPHS FROM MULTIVALUED DEPENDENCIES WITH LOSSLESS JOINS

IP.com Disclosure Number: IPCOM000148969D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12

Publishing Venue

Software Patent Institute

Related People

Forsyth, J.J.: AUTHOR [+3]

Abstract

RELATIONAL SCHEMA GRAPHS FROM MULTIVALUED DEPENDENCIES WITH LOSSLESS JOINS J. J. Forsyth and L. E. Charnock Department of Computer Science Michigan State University

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 20

RELATIONAL SCHEMA GRAPHS FROM MULTIVALUED DEPENDENCIES
WITH LOSSLESS JOINS
J. J. Forsyth and L. E. Charnock
Department of Computer Science

 Michigan State University
East Lansing, Mic:higan 48824

                  ABSTRACT
This paper presents a new algorithm for using multivalued
dependencies to design relational schema for relational
databases. The restricted dependency basis establishes an
ordering between the relations which in turn generates a
graph structure. It is shown that paths in the graph
correspond to lossless joins. This method generates fewer
relations than other hierarchical methods. Examples of the
algorithm are presented.

    The relational model of data provides that relations can be
decomposed into normal forms that facilitate the maintenance of
integrity constraints specified by functional dependencies [7,8,16].
The consequences of this feature halve generated substantial research I

into methods of designing relational database schema subject to
various specifications of integrity constraints. Functional

dependencies, multivalued dependencies and join dependencies have been
identified as models of integrity constraints which produce effective
schema design procedures [4,9]. This paper introduces a method for

1

[This page contains 1 picture or other non-text object]

Page 2 of 20

designing relational schema subject to both functional and multivalued
dependencies such that hierarchical relationships between relations
provide effective guides toward forming lossless joins.

    Bernstein developed a method which used functional dependencies
to synthesize relation schema in which all relations satisfy the third
normal form 161. That method allowed arbitrary choices of
dependencies at certain stages, so more than one schema could be
synthesized from a given set of dependencies. The method did not
fully predict which pairs of relations in the scheme could be joined
losslessly, so one requires a test for lossless joins [3,4].

    Fagin extended the schema design concepts to include multivalued
dependencies, and he defined a new normal form, fourth normal form, to
capture the conditions which would avoid update anomalies under
multivalued dependencies [9]. This approach also makes a flattened
view of the database, without indicating some of the legitimate
interrelation-ships that can be generated through lossless joins.

    Tanaka and Tsuda took a hierarchical approach to schema synthesis
using functional dependencies 1151, They based their ordering on the
partial ordering of the closures of the functional determinants. They
"pruned" the partial order graph to a tree in an effort to provide the
ability to recover information through lossless joins while storing
each attribute in a minimum number of relations. A list of "residual
semantic constraints" indicated those functional dependencies which

[This page contains 1 picture or other non-text object]

Page 3 of 20

were n...