Equivalence and Mapping of Database Schemes.

Alessandro D'Atri, Domenico Saccà: Equivalence and Mapping of Database Schemes. VLDB 1984: 187-195

@inproceedings{DBLP:conf/vldb/DAtriS84,
  author    = {Alessandro D'Atri and
               Domenico Sacc{\`a}},
  editor    = {Umeshwar Dayal and
               Gunter Schlageter and
               Lim Huat Seng},
  title     = {Equivalence and Mapping of Database Schemes},
  booktitle = {Tenth International Conference on Very Large Data Bases, August
               27-31, 1984, Singapore, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1984},
  isbn      = {0-934613-16-8},
  pages     = {187-195},
  ee        = {db/conf/vldb/DAtriS84.html},
  crossref  = {DBLP:conf/vldb/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the problem of database equivalence which arises in database design process. We introduce a graph formalism for the treatment of this problem. More precisely, we represent Entity-Relationship schemes by a special kind of graphs (called JFD-graphs) and we give a simple and efficient algorithm for testing the equivalence of two schemes. In addition, we present a set of elementary operators (preserving equivalence) for modifying an Entity-Relationship scheme and we prove that all equivalent schemes can be obtained by repeatedly applying such operators. Finally, we propose a methodology for mapping Entity-Relationship schemes into both relational and network schemes.

Copyright © 1984 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Gunter Schlageter, Lim Huat Seng (Eds.): Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings. Morgan Kaufmann 1984, ISBN 0-934613-16-8
Contents

References

[1]: Giorgio Ausiello, Alessandro D'Atri, Domenico Saccà: Graph Algorithms for Functional Dependency Manipulation. J. ACM 30(4): 752-766(1983)
[2]: ...
[3]: Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979)
[4]: Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981)
[5]: Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976)
[6]: ...
[7]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)
[8]: Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982)
[9]: ...
[10]: Sushil Jajodia, Peter A. Ng, Frederick N. Springsteel: The Problem of Equivalence for Entity-Relationship Diagrams. IEEE Trans. Software Eng. 9(5): 617-630(1983)
[11]: Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982)
[12]: Vincent Y. Lum, Sakti P. Ghosh, Mario Schkolnick, Robert W. Taylor, D. Jefferson, Stanley Y. W. Su, James P. Fry, Toby J. Teorey, B. Yao, D. S. Rund, B. Kahn, Shamkant B. Navathe, D. Smith, L. Aguilar, W. J. Barr, P. E. Jones: 1978 New Orleans Data Base Design Workshop Report. VLDB 1979: 328-339
[13]: Domenico Saccà: Closures of Database Hypergraphs. J. ACM 32(4): 774-803(1985)
[14]: ...
[15]: ...
[16]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[17]: Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94