DOC PREVIEW
SJSU CS 157A - Multivalued Dependencies

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Multivalued Dependencies and a New Normal Form for Relatknal Databases RONALD FAGIN IBM Research laboratory A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is strictly stronger than Codd’s “im- proved third normal form” (or “Boyce-Codd normal form”). It is shown that, every relation schema can be decomposed into a family of relation schemata in fourth normal form without loss of information (that is, the original relation can be obtained from the new relations by taking joins). Key words and phrases: database design, multivalued dependency, functional dependency, fourth normal form, 4NF, third normal form, 3NF, Boyce-Codd normal form, normalization, decomposition, relational database CR Categories: 3.59, 4.33, 6.1 1. INTRODUCTION The concept of “functional dependencies” [l, 3-6, 8, 10, 111 has proved to be useful in the design and analysis of relational databases. In fact in one approach [3, 41 to the logical design of relational databases, functional dependencies are essentially the only input. We introduce “multivalued dependencies,” which are a generaliza- tion of functional dependencies. We believe that multivalued dependencies sig- nificantly extend the understanding of logical database design. Multivalued de- pendencies lead to a new (“fourth”) normal form for relational databases. Roughly speaking, we say that a relation schema is in fourth normal form if all dependencies (functional and multivalued) are the result of keys. We now introduce multivalued dependencies and compare them with functional dependencies, by wry of example. A precise definition appears in Section 2. Let S(EMPLOYEE,SALARY,CHILD) be the relation that appears in Table I. Following Codd [6], we say that the relation S obeys the functional dependency EMPLOYEE-tSALARY. Intuitively this means that each employee has exactly one salary. The precise meaning is that if two tuples (that is, rows) of S agree in the EMPLOYEE column, then they agree in the SALARY column. When we say that a functional dependency (or a multivalued dependency) holds for a relation Copyright @ 1977, Association for Computing Machinery, Inc. General permission to repub- lish, but not for profit, all or part of this material is granted provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. Authors’ address: IBM Research Laboratory K53/282, 5600 Cottle Road, San Jose, CA 95193. ACM Transactions on Database Systems, Vol. 2, No. 3, September 1977, Pages 262-278.A New Normal Form for Relational Databases l 263 Table I Table II EMPLOYEE SALARY CHILD EMPLOYEE CHILD SALARY YEAR Hilbert Gauss Gauss Pythagoras $40K @OK @OK $20K Hubert Gwendolyn Greta Peter Hilbert Hilbert Gauss Gauss Gauss Gauss Pythagoras Pythagoras Hubert $35K 1976 Hubert $40K 1976 Gwendolyn $40K 1975 Gwendolyn $5OK 1976 Greta $40K 1975 Greta $5OK 1976 Peter $15K 1975 Peter $20K 1976 schema S”, we mean that every relation S that is an instance (“snapshot”) of the schema S* is constrained to obey the dependency. (For our purposes, a relation schema is simply a set of column names, along with a set of dependencies, which can be thought of as “integrity constraints.” See Cadiou [5] for a careful, thorough discussion of relation schemata.) The relation schema S*(EMPLOYEE,SALARY, CHILD), of which the relation S of Table I is an instance, “obeys” (that is, has as a part of its definition) the functional dependency EMPLOYEE+SALARY. So every instance must obey this functional dependency. What are the multivalued dependencies? First, the multivalued dependency EMPL~YEE++SALARY (which can be read “EMPLOYEE multidetermines SALARY”) holds for S*, since functional dependencies (in which the left- and right-hand sides are disjoint) turn out to be special cases of multivalued depen- dencies. Furthermore the multivalued dependency EMPLOYEE++CHILD holds for S* because intuitively, an employee’s set of children is completely deter- mined by the employee and is “orthogonal” to the salary. In this case multivalued dependencies remedy one of Schmid and Swenson’s [12] objections to functional dependencies, that an employee “has” a set of children just as he “has” a salary and there should be no arbitrary distinction. Thus both of the multivalued de- pendencies EMPLOYEE++SALARY and EMPLOYEE++CHILD hold for this schema. As another example, let T*(EMPLOYEE,CHILD,SALARY,YEAR) be a re- lation schema that specifies the children and salary history of each employee. An instance T of T* appears in Table II. A tuple, such as (Pythagoras,Peter,$20K, 1976)) appears in relation T i$ ( 1) Pythagoras is an employee, (2) one of his children is named Peter, and (3) during at least part of 1976, his salary was $20K. Although T* has no functional dependencies, it does have the multivalued dependencies EMPLOYEE++CHILD (as in the previous example), and also EM- PLOYEF J++( SALARY,YEAR}, because intuitively, an employee’s salary history is completely determined by the employee and is orthogonal to his set of children. Caution: As we shall see, it does not follow from EMPLOYEE-+-+(SALARY, YEAR] that either EMPLOYEE-t-SALARY or EMPLOYEE-++YEAR. The pair { SALARY,YEAR) is in some sense a “cluster.” Multivalued dependencies provide a necessary and sufficient condition for a relation to be decomposable into two of its projections without loss of information ACM Transactions on Database Systems, Vol. 2, No. 3, September 1977.264 l Ronald Fagin (in the usual sense


View Full Document

SJSU CS 157A - Multivalued Dependencies

Documents in this Course
SQL

SQL

18 pages

Lecture

Lecture

44 pages

Chapter 1

Chapter 1

56 pages

E-R Model

E-R Model

16 pages

Lecture

Lecture

48 pages

SQL

SQL

15 pages

SQL

SQL

26 pages

Lossless

Lossless

26 pages

SQL

SQL

16 pages

Final 3

Final 3

90 pages

Lecture 3

Lecture 3

22 pages

SQL

SQL

25 pages

Load more
Download Multivalued Dependencies
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Multivalued Dependencies and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Multivalued Dependencies 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?