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

article

Free access

A formal approach to the definition and the design of conceptual schemata for databased systems

Editor: Robert W. Taylor Authors:

Michel A. MelkaoffAuthors Info & Claims

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

Pages 24 - 59

https://doi.org/10.1145/319682.319695

Published: 01 March 1982 Publication History

Abstract

A formal approach is proposed to the definition and the design of conceptual database diagrams to be used as conceptual schemata in a system featuring a multilevel schema architecture, and as an aid for the design of other forms of schemata. We consider E-R (entity-relationship) diagrams, and we introduce a new representation called CAZ-graphs. A rigorous connection is established between these diagrams and some formal constraints used to describe relationships in the framework of the relational data model. These include functional and multivalued dependencies of database relations. The basis for our schemata is a combined representation for two fundamental structures underlying every relation: the first defined by its minimal atomic decompositions, the second by its elementary functional dependencies.

The interaction between these two structures is explored, and we show that, jointly, they can represent a wide spectrum of database relationships, of which the well-known one-to-one, one-to-many, and many-to-many associations constitute only a small subset. It is suggested that a main objective in conceptual schema design is to ensure a complete representation of these two structures. A procedure is presented to design schemata which obtain this objective while eliminating redundancy. A simple correspondence between the topological properties of these schemata and the structure of multivalued dependencies of the original relation is established. Various applications are discussed and a number of illustrative examples are given.

References

[1]

AHO, A.V., BEERI, C., AND ULLMAN, J. The theory of joins in relational databases. In Proc. 18th Ann. Syrup. Foundations of Computer Science, Nov. 1977.

[2]

ARORA, A. K., AND CARLSON, C.R. The information preserving properties of relational database transformations. In Proc. 4th Int. Conf. Very Large Data Bases (West Berlin, Germany, Sept. 1978}, pp. 352-359.

[3]

BEER1, C. On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans. Database Syst. 5, 3 (Sept. 1980), 241-259.

Digital Library

[4]

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

Digital Library

[5]

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

[6]

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

Digital Library

[7]

BERGE, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.

Digital Library

[8]

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

Digital Library

[9]

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

[10]

CHEW, P.P. The entity-relationship model--A basis for the enterprise view of data. In Proc. 1977 Nat. Computer Conf. (Dallas, Tex., June 1977).

[11]

CODD, E.F. Further normalization of the database relational model. Database Systems, Courant Computer Science Series, vol. 6, Prentice-Hall, Englewood Cliffs, N.J., 1972.

[12]

CODD, E.F. Recent investigations in relational database systems. In IFIP Conference Proceedings, North-Holland, Amsterdam, 1974, pp. 1017-1021.

[13]

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

Digital Library

[14]

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

Digital Library

[15]

FAGIN, R. The decomposition versus the synthetic approach to relational database design. In Proc. 3rd Int. Conf. Very Large Data Bases (Tokyo, Japan, Oct. 1977), ACM, New York, 1977, pp. 441-446.

[16]

FALKENB~.RG, E. Concepts for modelling information. In Proc. IFIP TC-2, Working Conference on Modelling in Data Base Management Systems, G. Nijessen (Ed.) North-Holland, Amsterdam, 1976.

[17]

FLORY, A., AND KOULOUMIDJAN, J. A model and a method for logical database design. In Proc. 4th Conf. Very Large Data Bases (West Berlin, Germany, Sept. 1978), pp. 333-350.

[18]

HALL, P., OWLETT, d., AND TODD, S. Relations and entities. In Proc. IFIP TC-2, Working Conference on Modelling in Data Base Management Systems, G. Nijessen (Ed.), North-Holland, Amsterdam, 1976.

[19]

JOINT GUIDE AND SHARE DATABASE REQUIREMENT GROUP Requirements for a database management system. Nov. 1970. (Available from SHARE, Suite 750, 25 Broadway, New York, NY, 1O004.)

[20]

KATZ, R.H. Database design and translation for multiple data models. Ph.D. thesis, Univ. California, Berkeley, 1980.

Digital Library

[21]

Lm~, Y.E. On the semantics of the entity-relationship data model, in Entity-Relationship Approach to Systems Analysis and Design, P. Chen (Ed.). North-Holland, Amsterdam, 1980.

Digital Library

[22]

MWL~,NOFF, M.A., AND ZANIOLO, C. Decomposition of relations and synthesis of entity-relationship diagrams. In Entity-Relationship Approach to System Analysis and Design, P. Chen (Ed.). North-Holland, Amsterdam, 1980.

Digital Library

[23]

NXCHOLAS, J.M. Mutual dependencies and some results on undecomposable relations. In Proc. 4th Int. Conf. Very Large Data Bases {West Berlin, Germany, Sept. 1978), pp. 360-367.

[24]

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

Digital Library

[25]

RoussoPOULOS, S., AND MYLOPOULOS, J. Using semantic networks for database management. in Proc. Conf. Very Large Data Bases (Framingham, Mass., Sept. 1975), pp. 144-172.

[26]

SAKAY, H. On the optimization of the entity-relationship model. In Pr0c. 3rd USA-Japan Conf. (Oct. 1978), pp. 145-149.

[27]

SCHMID, H.A., AND SWENSON, J.R. On the semantics of the relational data model. In ACM SIGMOD Workshop Management of Data (San Jose, Calif., May I975), pp. 211-223.

Digital Library

[28]

SILVA, M.A., AND MELKANOFF, M.A. Decomposition of universal relation schemas allowing interrelational dependencies. (Manuscript submitted for publication.)

[29]

SMITH, J.M., AND SMITH, D.C.P. Database abstractions: Aggregation. Commun. ACM 20, 6 (June 1977), 405-413.

Digital Library

[30]

SPYRATOS, N., AND BANCILHON, F. Name independence and database abstraction in the relational model. In Proc. MFCS 78 Syrup. (Zakopane, Poland, Sept. 1978).

[31]

TSICHRITZIS, D., AND KLUG, A. (Eds.) The ANSI/X3/SPARC DBMS framework report of the study group on database management systems. Inf. Syst. 3, 3 (1978).

[32]

ZANIOLO, C. Analysis and design of relational schemata for database systems. Ph.D. thesis, Computer Sci. Dep. Rep. UCLA-ENG-7669, UCLA, Los Angeles, Calif., July 1976.

Digital Library

[33]

ZANIOLO, C., AND MELKANOFF, M.A. On the design of relational database schemata. A CM Trans. Database Syst. 6, 1 (March 1981), 1-47.

Digital Library

Cited By

Woitsch R(2015)Hybrid ModelingStandards and Standardization10.4018/978-1-4666-8111-8.ch019(387-408)Online publication date: 2015
https://doi.org/10.4018/978-1-4666-8111-8.ch019
Woitsch R(2014)Hybrid ModelingRevolutionizing Enterprise Interoperability through Scientific Foundations10.4018/978-1-4666-5142-5.ch005(97-118)Online publication date: 2014
https://doi.org/10.4018/978-1-4666-5142-5.ch005
Waseem AHussain SShaikh ZCosta CAparicio M(2013)An extended synthesis algorithm for relational database schema designProceedings of the 2013 International Conference on Information Systems and Design of Communication10.1145/2503859.2503874(94-100)Online publication date: 11-Jul-2013
https://dl.acm.org/doi/10.1145/2503859.2503874
Show More Cited By

Index Terms

A formal approach to the definition and the design of conceptual schemata for databased systems
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Data model extensions
    2. Database management system engines

Recommendations

Conceptual xml for systems analysis
A Formal Object Approach to the Design of ZML

This paper addresses two issues: how formal object modeling techniques facilitate the XML application development and how XML technology helps formal/graphical software design process. In particular, the paper presents a XML/XSL approach to the ...
XML Schema Re-Engineering Using a Conceptual Schema Approach
ITCC '05: Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume I - Volume 01

At present, the eXtensible Markup Language (XML) is popular for both data presentation and data transfer activities. XML Documents follow XML Schemas. It is possible to use them as database schemas and databases. An XML Schema can be hierarchical or ...

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 7, Issue 1

March 1982

123 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/319682

Editor:
Robert W. Taylor
IBM Research Lab, San Jose, CA

Issue’s Table of Contents

Copyright © 1982 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1982

Published in TODS Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
786
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)19

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Woitsch R(2015)Hybrid ModelingStandards and Standardization10.4018/978-1-4666-8111-8.ch019(387-408)Online publication date: 2015
https://doi.org/10.4018/978-1-4666-8111-8.ch019
Woitsch R(2014)Hybrid ModelingRevolutionizing Enterprise Interoperability through Scientific Foundations10.4018/978-1-4666-5142-5.ch005(97-118)Online publication date: 2014
https://doi.org/10.4018/978-1-4666-5142-5.ch005
Waseem AHussain SShaikh ZCosta CAparicio M(2013)An extended synthesis algorithm for relational database schema designProceedings of the 2013 International Conference on Information Systems and Design of Communication10.1145/2503859.2503874(94-100)Online publication date: 11-Jul-2013
https://dl.acm.org/doi/10.1145/2503859.2503874
Karagiannis DHöfferer P(2008)Metamodeling as an Integration ConceptSoftware and Data Technologies10.1007/978-3-540-70621-2_4(37-50)Online publication date: 2008
https://doi.org/10.1007/978-3-540-70621-2_4
Boyd MMcBrien P(2005)Comparing and transforming between data models via an intermediate hypergraph data modelJournal on Data Semantics IV10.5555/2137771.2137774(69-109)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/2137771.2137774
Draghici M(2005)An extended view on data base conceptual designMFDBS 8910.1007/3-540-51251-9_11(148-171)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-51251-9_11
Boyd MMcBrien P(2005)Comparing and Transforming Between Data Models Via an Intermediate Hypergraph Data ModelJournal on Data Semantics IV10.1007/11603412_3(69-109)Online publication date: 2005
https://doi.org/10.1007/11603412_3
Rizopoulos NMçbrien P(2005)A general approach to the generation of conceptual model transformationsProceedings of the 17th international conference on Advanced Information Systems Engineering10.1007/11431855_23(326-341)Online publication date: 17-Jun-2005
https://dl.acm.org/doi/10.1007/11431855_23
Ram S(1995)Deriving functional dependencies from the entity-relationship modelCommunications of the ACM10.1145/223248.22327738:9(95-111)Online publication date: 1-Sep-1995
https://dl.acm.org/doi/10.1145/223248.223277
Ram SCurran S(1990)The synthesis approach for relational database design: an expanded perspectiveInformation Sciences: an International Journal10.1016/0020-0255(90)90035-952:1(53-73)Online publication date: 1-Oct-1990
https://dl.acm.org/doi/10.1016/0020-0255%2890%2990035-9
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