More Web Proxy on the site http://driver.im/

article

Free access

On the design of relational database schemata

Authors:

Miachel A. MeklanoffAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 6, Issue 1

Pages 1 - 47

https://doi.org/10.1145/319540.319542

Published: 01 March 1981 Publication History

Abstract

The purpose of this paper is to present a new approach to the conceptual design of relational databases based on the complete relatability conditions (CRCs).

It is shown that current database design methodology based upon the elimination of anomalies is not adequate. In contradistinction, the CRCs are shown to provide a powerful criticism for decomposition. A decomposition algorithm is presented which (1) permits decomposition of complex relations into simple, well-defined primitives, (2) preserves all the original information, and (3) minimizes redundancy.

The paper gives a complete derivation of the CRCs, beginning with a unified treatment of functional and multivalued dependencies, and introduces the concept of elementary functional dependencies and multiple elementary multivalued dependencies. Admissibility of covers and validation of results are also discussed, and it is shown how these concepts may be used to improve the design of 3NF schemata. Finally, a convenient graphical representation is proposed, and several examples are described in detail to illustrate the method.

References

[1]

ARMSTRONG, V~.W. Dependency structures of data base relationships. Information Processing, vol. 74. North-Holland, Amsterdam, I974, pp. 580-583.

[2]

BEERI, C., FAGIN, R., AND HOWARD, J.H. A complete axioinatization for functional and multivalued dependencies in database relations. Proc. ACM SIGMOD Int. Conf. Management of Data, Toronto, Canada, 1977, pp. 47-61.

Digital Library

[3]

BEERI, C. On the membership problem for multivalued dependencies in relational databases. TR-229, Princeton Univ., Princeton, N.J., Sept. 1977.

[4]

BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. Int. Conf. Very Large Data Bases, West Berlin, Germany, 1978, pp. 113-124.

[5]

BEERI, C., AND BERNSTEIN, P.A. Computational problems related to the design of normal form relational schemas. ACM Trans. Database Syst. 4, 1 (March 1979), 30-59.

Digital Library

[6]

BERNSTEIN, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. 1, 4 (Dec. 1976), 272-298.

Digital Library

[7]

BISKUP, J. On the complementation rule for multivalued dependencies on database relations. Acta Inf. 10, 3 (1978), 297-305.

Digital Library

[8]

CHEN, P.P. The entity-relationship model toward a unified view of data.ACM Trans. Database Syst. 1, 1 (March 1976), 9-36.

Digital Library

[9]

CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387.

Digital Library

[10]

CODD, E.F. Further normalization of the data base relational model. In Data Base Systems, Courant Computer Science Series, vol. 6, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.

[11]

CODD, E.F. Recent investigations in relational database systems. Information Processing, voh 74. North-Holland, Amsterdam, 1974, pp. 1017-1021.

[12]

DATE, C.J. An Introduction to Database Systems, 2nd ed. Addison-Wesley, Reading, Mass., 1977.

Digital Library

[13]

DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Dev. 17, 5 (Sept. 1972), 374-386.

[14]

DELOBEL, C., AND L~:ONARD, M. The decomposition process in a relational model. Proc. Int. Workshop on Data Structure Models for Information Systems, Namur, Belgium, May 1974, pp. 57-80.

[15]

FAGIN, R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 262-278.

Digital Library

[16]

FAGIN, R. The decomposition versus synthetic approach to relational database design. Proc. Third Int. Conf. Very Large Data Bases, Tokyo, Japan, Oct. 1977, pp. 441-446.

Digital Library

[17]

GAUL, Z. An almost linear time algorithm for computing a dependency basis in a relational database. IBM Res. Rep. RJ2656, IBM Research Labs., San Jose, Calif., Oct. 1979.

[18]

JOINT GUIDE AND SHARE DATABASE REQUIREMENT GROUP. Requirements for a Database Management System, November 1970. (Available from SHARE, Suite 750, 25 Broadway, New York, NY 10004.)

[19]

HAGIHARA, K., ITO, M., TANIGUCHI, K., AND KASAMI, T. Decision problems for multivalued dependencies in relational databases. SIAM J. Comput. 8, 2, 247-264.

[20]

MENDELZON, A.O. On axiomatizing multivalued dependencies in relational databases. J. ACM 26, 1 (Jan. 1979), 37-44.

Digital Library

[21]

MONAHAN, J., AND MELKANOFF, M.A. To be published.

[22]

RISSANEN, J. Independent components of relations. ACM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325.

Digital Library

[23]

SAGIV, Y. An algorithm for inferring multivalued dependencies that works also for a subclass of proportional logic. VIVCDCS-R-79-954, Dep. Computer Science, Univ. Illinois, Urbana, Jan. 1979.

[24]

SILVA, A.M. Derivation of relational dependencies through case-study analyses. M.S. Thesis, Computer Science Dep., Univ. California, Los Angeles, 1978.

[25]

TANAKA, K., KAMBAYSHI, Y., AND YAJIMA, S. On the representability of decompositional schema design with multivalued dependencies. Rep. ER79-01, Dep. Information Science, Kyoto Univ., Japan, Jan. 1979.

[26]

WANG, C.P., AND WEDEKIND, H.H. Segment synthesis in logical data base design. IBM J. Res. Dev. 19, 1 (Jan. 1975), 71-77.

Digital Library

[27]

ZANIOLO, C. Analysis and design of relational schemata for database systems. Rep. UCLA-ENG- 7669, Computer Science Dep., Univ. California, Los Angeles, July 1976.

[28]

ZANIOLO, C., AND MELKANOFF, M.A. A formal approach to the definition and the design of conceptual schemata for database systems. To appear in ACM Trans. Database Syst.

Digital Library

Cited By

Storey VLukyanenko RCastellanos A(2023)Conceptual Modeling: Topics, Themes, and Technology TrendsACM Computing Surveys10.1145/358933855:14s(1-38)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1145/3589338
Mancas C(2015)The Quest for Data Independence, Minimal Plausibility, and Formalization: The Relational Data Model (RDM)Conceptual Data Modeling and Database Design: A Fully Algorithmic Approach, Volume 110.1201/b19279-4(115-340)Online publication date: 29-Sep-2015
https://doi.org/10.1201/b19279-4
Biskup JLink S(2011)Appropriate inferences of data dependencies in relational databasesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-012-9275-063:3-4(213-255)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s10472-012-9275-0
Show More Cited By

Index Terms

On the design of relational database schemata
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Data model extensions
      2. Relational database model
    2. Query languages
      1. Relational database query languages

Recommendations

Controlling FD and MVD Inferences in Multilevel Relational Database Systems

The authors investigate the inference problems due to functional dependencies (FD) and multivalued dependencies (MVD) in a multilevel relational database (MDB) with attribute and record classification schemes, respectively. The set of functional ...
Testing implications of data dependencies

Presented is a computation method—the chase—for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as ...
Language and program design for functional dependencies
HASKELL '08

Eight years ago, functional dependencies, a concept from the theory of relational databases, were proposed as a mechanism for avoiding common problems with multiple parameter type classes in Haskell. In this context, functional dependencies give ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 6, Issue 1

March 1981

211 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/319540

Editor:
David K. Hsiao
Ohio State Univ., Columbus

Issue’s Table of Contents

Copyright © 1981 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1981

Published in TODS Volume 6, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
1,171
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)27

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Storey VLukyanenko RCastellanos A(2023)Conceptual Modeling: Topics, Themes, and Technology TrendsACM Computing Surveys10.1145/358933855:14s(1-38)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1145/3589338
Mancas C(2015)The Quest for Data Independence, Minimal Plausibility, and Formalization: The Relational Data Model (RDM)Conceptual Data Modeling and Database Design: A Fully Algorithmic Approach, Volume 110.1201/b19279-4(115-340)Online publication date: 29-Sep-2015
https://doi.org/10.1201/b19279-4
Biskup JLink S(2011)Appropriate inferences of data dependencies in relational databasesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-012-9275-063:3-4(213-255)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s10472-012-9275-0
Taneja KZhang YXie TPecheur CAndrews JDi Nitto E(2010)MODAProceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering10.1145/1858996.1859053(289-292)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.1145/1858996.1859053
Hartmann SLink S(2009)On Inferences ofWeak Multivalued DependenciesFundamenta Informaticae10.5555/2362701.236270692:1-2(83-102)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/2362701.2362706
Hartmann SLink S(2009)On Inferences ofWeak Multivalued DependenciesFundamenta Informaticae10.5555/1551891.155189692:1-2(83-102)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1551891.1551896
Biskup JLink S(2008)Appropriate reasoning about data dependencies in fixed and undetermined universesProceedings of the 5th international conference on Foundations of information and knowledge systems10.5555/1786094.1786103(58-77)Online publication date: 11-Feb-2008
https://dl.acm.org/doi/10.5555/1786094.1786103
Biskup JLink S(2008)Appropriate Reasoning about Data Dependencies in Fixed and Undetermined UniversesFoundations of Information and Knowledge Systems10.1007/978-3-540-77684-0_7(58-77)Online publication date: 2008
https://doi.org/10.1007/978-3-540-77684-0_7
Baixeries JBalcázar J(2005)Characterization and armstrong relations for degenerate multivalued dependencies using formal concept analysisProceedings of the Third international conference on Formal Concept Analysis10.1007/978-3-540-32262-7_11(162-175)Online publication date: 14-Feb-2005
https://dl.acm.org/doi/10.1007/978-3-540-32262-7_11
Thallheim B(2005)The higher-order entity-relationship model and (DB)MFDBS 8910.1007/3-540-51251-9_25(382-397)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-51251-9_25
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents