Assumptions in Relational Database Theory.

@inproceedings{DBLP:conf/pods/AtzeniP82,
  author    = {Paolo Atzeni and
               Douglas Stott Parker Jr.},
  title     = {Assumptions in Relational Database Theory},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {1-9},
  ee        = {http://doi.acm.org/10.1145/588111.588113, db/conf/pods/AtzeniP82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Many results in relational database theory on the structure of dependencies, query languages, and databases in general have now been established. However, neither (a) the reliance of these results on various assumptions, nor (b) the desirability or reasonableness of these assumptions themselves have been closely examined. These assumptions are nontrivial: examples include the universal relation assumption and the lossless join assumption.

The purpose of the present paper is to clarify many of the existing assumptions, and point out weaknesses. This is desirable both to harden the statements of previous results, and to evaluate recent suggestions that certain assumptions (such as the acyclic JD assumption) may be useful for modeling "real world" databases. Specifically, studies are made of assumptions made for (1) universal relations, (2) functional dependency inference, and (3) decomposition theory. We show that:

• Some assumptions (such as uniqueness of relationships among attributes) can be more powerful than they appear;
• common treatment of FDs is sometimes inappropriate, and for example FD inferences such as {A->,B, B->C} |= A->C can be incorrect;
• the 'decomposition' approach to design may be hard to justify in real terms; and
• Acyclic JDs may have drawbacks in eliminating ambiguity in queries and in modeling real enterprises.

Copyright © 1982 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ANSI]

...

[ABU]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX

[AABM]

...

[AP]

...

[BDM]

...

[BFMMUY]

Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX

[BFMY]

Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX

[B]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[BG]

Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX

[CK]

C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154 BibTeX

[C]

...

[F1]

Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX

[F2]

Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160 BibTeX

[FMU]

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) BibTeX

[Go]

Billie S. Goldstein: Constraints on Null Values in Relational Databases. VLDB 1981: 101-110 BibTeX

[Gr]

Marc H. Graham: Functions in Databases. ACM Trans. Database Syst. 8(1): 81-109(1983) BibTeX

[HK]

...

[H]

Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX

[HLY]

Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) BibTeX

[IL]

Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397 BibTeX

[K1]

William Kent: The Entity Join. VLDB 1979: 232-238 BibTeX

[K2]

William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981) BibTeX

[LP]

...

[L1]

Y. Edmund Lien: On the Semantics of the Entity-Relationship Data Model. ER 1979: 155-168 BibTeX

[L2]

Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981) BibTeX

[LT]

...

[Lipski]

Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX

[LPO]

Ewing L. Lusk, Gene Petrie, Ross A. Overbeek: Item Tracking Entity-Relationship Models. ER 1981: 213-233 BibTeX

[Mc]

...

[MU]

David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) BibTeX

[Me]

Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX

[O]

Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60 BibTeX

[R]

Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX

[Sa1]

Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX

[Sa2]

Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX

[Sc]

...

[SS]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977) BibTeX

[U1]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[U2]

Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX

[V]

...

Referenced by

1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
2. Renée J. Miller, Yannis E. Ioannidis, Raghu Ramakrishnan: The Use of Information Capacity in Schema Integration and Translation. VLDB 1993: 120-133
3. 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)
4. Stefan W. Joseph, Romas Aleliunas: A Knowledge-Based Subsystem for a Natural Language Interface to a Database that Predicts and Explains Query Failures. ICDE 1991: 80-87
5. Edward Sciore: Abbreviation Techniques in Entity-Relationship Query Languages. ER 1991: 129-145
6. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
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. Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343
9. Victor M. Markowitz, Arie Shoshani: Name Assignment Techniques for Relational Schemas Representing Extended Entity-Relationship Schemas. ER 1989: 75-93
10. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
11. Alessandro D'Atri, Fabrizio L. Ricci: Interpretation of Statistical Queries to Relational Databases. SSDBM 1988: 246-258
12. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
13. Alessandro D'Atri, Paolino Di Felice, Marina Moscarini: Dynamic Query Interpretation in Relational Databases. PODS 1987: 70-78
14. Alessandro D'Atri, Paolino Di Felice, V. S. Lakshmanan, Marina Moscarini: On Global Context Dependencies and their Properties. MFDBS 1987: 71-79
15. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
16. Joachim Biskup, Hans Hermann Brüggemann: Data Manipulation Languages for the Universal Relation View DURST. MFDBS 1987: 20-41
17. W. S. Luk, Steve Kloster: ELFS: English Language From SQL. ACM Trans. Database Syst. 11(4): 447-472(1986)
18. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
19. Joachim Biskup, Hans Hermann Brüggemann, L. Schnetgöke, M. Kramer: One Flavor Assumption and Gamma-Acyclicity for Universal Relation Views. PODS 1986: 148-159
20. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
21. Tok Wang Ling: A Normal Form For Entity-Relationship Diagrams. ER 1985: 24-35
22. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984)
23. Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen Van Gelder, Jeffrey D. Ullman: System/U: A Database System Based on the Universal Relation Assumption. ACM Trans. Database Syst. 9(3): 331-347(1984)
24. Arthur M. Keller, Marianne Winslett: Approaches for Updating Databases With Incomplete Information and Nulls. ICDE 1984: 332-340
25. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
26. David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983)
27. William Kent: The Universal Relation Revisited. ACM Trans. Database Syst. 8(4): 644-648(1983)
28. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
29. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
30. Joachim Biskup, Hans Hermann Brüggemann: Universal Relation Views: A Pragmatic Approach. VLDB 1983: 172-185
31. Alessandro D'Atri, Marina Moscarini, Nicolas Spyratos: Answering Queries in Relational Databases. SIGMOD Conference 1983: 173-177
32. Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57
33. Sushil Jajodia, Peter A. Ng, Frederick N. Springsteel: On Universal and Representative Instances for Inconsistent Databases. ER 1983: 279-295
34. Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141
35. Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160