ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Relative Information Capacity of Simple Relational Database Schemata.

Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109
@inproceedings{DBLP:conf/pods/Hull84,
  author    = {Richard Hull},
  title     = {Relative Information Capacity of Simple Relational Database Schemata},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {97-109},
  ee        = {http://doi.acm.org/10.1145/588011.588027, db/conf/pods/Hull84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Fundamental notions of relative information capacity between database structures are studied in the context of the relational model. Four progressively less restrictive formal definitions of "dominance" between pairs of relational database schemata are given. Each of these is shown to capture intuitively appealing, semantically meaningful properties which are natural for measures of relative information capacity between schemata. Relational schemata, both with and without key dependencies, are studied using these notions. A significant intuitive conclusion concerns the informal notion of relative information capacity often suggested in the conceptual database literature, which is based on accessability of data via queries. Results here indicate that this notion is too general to accurately measure whether an underlying semantic connection exists between database schemata. Another important result of the paper shows that under any natural notion of information capacity equivalence, two relational schemata (with no dependencies) are equivalent if and only if they are identical (up to re-ordering of the attributes and relations). The approach and definitions used here can form part of the foundation for a rigorous investigation of a variety of important database problems involving data relativism, including those of schema integration and schema translation.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[2]
Paolo Atzeni, Giorgio Ausiello, Carlo Batini, Marina Moscarini: Inclusion and Equivalence between Relational Database Schemata. Theor. Comput. Sci. 19: 267-285(1982) BibTeX
[3]
Giorgio Ausiello, Carlo Batini, Marina Moscarini: On the Equivalence among Data Base Schemata. ICOD 1980: 34-46 BibTeX
[4]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[5]
Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
[6]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[7]
...
[8]
Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218 BibTeX
[9]
Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47 BibTeX
[10]
...
[11]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[12]
Wesley W. Chu, V. T. To: A Hierarchical Conceptual Data Model Data Translation in a Heterogeneous Database System. ER 1979: 575-576 BibTeX
[13]
...
[14]
...
[15]
...
[16]
Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) BibTeX
[17]
Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX
[18]
...
[19]
...
[20]
Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984) BibTeX
[21]
...
[22]
Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX
[23]
...
[24]
Roger King, Dennis McLeod: The Event Database Specifications Model. JCDKB 1982: 299-322 BibTeX
[25]
Anthony C. Klug: Entity-Relationship Views over Uninterpreted Enterprise Schemas. ER 1979: 39-60 BibTeX
[26]
Y. Edmund Lien: On the Semantics of the Entity-Relationship Data Model. ER 1979: 155-168 BibTeX
[27]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[28]
Tok Wang Ling, Frank Wm. Tompa, Tiko Kameda: An Improved Third Normal Form for Relational Databases. ACM Trans. Database Syst. 6(2): 329-346(1981) BibTeX
[29]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[30]
David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. J. Comput. Syst. Sci. 21(3): 368-379(1980) BibTeX
[31]
...
[32]
Amihai Motro, Peter Buneman: Constructing Superviews. SIGMOD Conference 1981: 56-64 BibTeX
[33]
John Mylopoulos, Philip A. Bernstein, Harry K. T. Wong: A Language Facility for Designing Database-Intensive Applications. ACM Trans. Database Syst. 5(2): 185-207(1980) BibTeX
[34]
Colm Ó'Dúnlaing, Chee-Keng Yap: Generic Transformation of Data Structures. FOCS 1982: 186-195 BibTeX
[35]
Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX
[36]
...
[37]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[38]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[39]
S. Bing Yao, Vance E. Waddle, Barron C. Housel: View Modeling and Integration Using the Functional Data Model. IEEE Trans. Software Eng. 8(6): 544-553(1982) BibTeX
[40]
Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982) BibTeX

Referenced by

  1. Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan: Conjunctive Query Equivalence of Keyed Relational Schemas. PODS 1997: 44-50
  2. John L. Knapp: Uniqueness Conditions for ER Representations. OOER 1995: 296-307
  3. Arnon Rosenthal, David S. Reiner: Tools and Transformations - Rigorous and Otherwise - for Practical Database Design. ACM Trans. Database Syst. 19(2): 167-211(1994)
  4. Victor M. Markowitz, Arie Shoshani: Representing Extended Entity-Relationship Structures in Relational Databases: A Modular Approach. ACM Trans. Database Syst. 17(3): 423-464(1992)
  5. Wonhee Sull, Rangasami L. Kashyap: A Self-Organizing Knowledge Representation Scheme for Extensible Heterogenous Information Environment. IEEE Trans. Knowl. Data Eng. 4(2): 185-191(1992)
  6. Victor M. Markowitz: A Relation Merging Technique for Relational Databases. ICDE 1992: 428-437
  7. Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439
  8. Arnon Rosenthal, David S. Reiner: Database Design Tools: Combining Theory, Guesswork, and User Interaction. ER 1989: 187-201
  9. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
  10. Joachim Biskup, Bernhard Convent: A Formal View Integration Method. SIGMOD Conference 1986: 398-407
  11. Gabriel M. Kuper, Moshe Y. Vardi: On the Expressive Power of the Logical Data Model (Preliminary Report). SIGMOD Conference 1985: 180-187
  12. Tim Connors: Equivalence of Views by Query Capacity. PODS 1985: 143-148
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:44 2009