ACM SIGMOD Anthology TODS dblp.uni-trier.de

A Simplified Universal Relation Assumption and Its Properties.

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)
@article{DBLP:journals/tods/FaginMU82,
  author    = {Ronald Fagin and
               Alberto O. Mendelzon and
               Jeffrey D. Ullman},
  title     = {A Simplified Universal Relation Assumption and Its Properties},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {3},
  year      = {1982},
  pages     = {343-360},
  ee        = {http://doi.acm.org/10.1145/319732.319735, db/journals/tods/FaginMU82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

One problem concerning the universal relation assumption is the inability of known methods to obtain a database scheme design in the general case, where the real-world constraints are given by a set of dependencies that includes embedded multivalued dependencies. We propose a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency. The relationship between this method of defining the real world and the classical methods is exposed. We characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Also characterized in terms of hypergraphs are those join dependencies that are equivalent to a set of multivalued dependencies.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
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
[2]
...
[3]
Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX
[4]
...
[5]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[6]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[7]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[8]
Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX
[9]
Catriel Beeri, Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979: 25-71 BibTeX
[10]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[11]
...
[12]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[13]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[14]
Ronald Fagin: Normal Forms and Relational Database Operators. SIGMOD Conference 1979: 153-160 BibTeX
[15]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[16]
Y. Edmund Lien: On the Semantics of the Entity-Relationship Data Model. ER 1979: 155-168 BibTeX
[17]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[18]
David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39 BibTeX
[19]
David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) BibTeX
[20]
Alberto O. Mendelzon, David Maier: Generalized Mutual Dependencies and the Decomposition of Database Relations. VLDB 1979: 75-82 BibTeX
[21]
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX
[22]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[23]
...
[24]
Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 BibTeX
[25]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX
[26]
Moshe Y. Vardi: Inferring Multivalued Dependencies From Functional and Join Dependencies. Acta Inf. 19: 305-324(1983) BibTeX

Referenced by

  1. Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. PODS 1999: 21-32
  2. Anand Rajaraman, Jeffrey D. Ullman: Integrating Information by Outerjoins and Full Disjunctions. PODS 1996: 238-248
  3. Wai Yin Mok, David W. Embley: Transforming Conceptual Models to Object-Oriented Database Designs: Practicalities, Properties, and Peculiarities. ER 1996: 309-324
  4. J. Leon Zhao, Arie Segev, Abhirup Chatterjee: A Universal Relation Approach to Federated Database Management. ICDE 1995: 261-270
  5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  6. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
  7. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  8. Tzy-Hey Chang, Edward Sciore: A Universal Relation Data Model with Semantic Abstraction. IEEE Trans. Knowl. Data Eng. 4(1): 23-33(1992)
  9. Stephen J. Hegner: Pairwise-Definable Subdirect Decompositions of General Database Schemata. MFDBS 1991: 243-257
  10. Carl S. Hartzman, Carolyn R. Watters: A Relational Approach to Querying Streams. IEEE Trans. Knowl. Data Eng. 2(4): 401-409(1990)
  11. Gösta Grahne: Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases. PODS 1989: 75-82
  12. Lev A. Tenenbaum: Blocks and Projections' Synthesis in relational Databases. MFDBS 1989: 367-381
  13. Margareta Dina Draghici: An Extended View on Data Base Conceptual Design. MFDBS 1989: 148-171
  14. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  15. John H. Leuchner, Les Miller, Giora Slutzki: A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies. SIGMOD Conference 1988: 218-224
  16. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
  17. Roger Cavallo, Michael Pittarelli: The Theory of Probabilistic Databases. VLDB 1987: 71-81
  18. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  19. Marc Gyssens: On the Complexity of Join Dependencies. ACM Trans. Database Syst. 11(1): 81-108(1986)
  20. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
  21. Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
  22. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
  23. V. S. Lakshmanan: Split-Freedom and MVD-Intersection: A New Characterization of Multivalued Dependencies Having Conflict-Free Covers. ICDT 1986: 221-241
  24. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
  25. Lynette I. Brady, Christopher N. G. Dampney: The Semantics of Relational Database Functions. ER 1986: 287-302
  26. Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84
  27. Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
  28. Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215
  29. Joseph A. Wald, Paul G. Sorenson: Resolving the Query Inference Problem Using Steiner Trees. ACM Trans. Database Syst. 9(3): 348-368(1984)
  30. Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984)
  31. 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)
  32. 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)
  33. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  34. Alessandro D'Atri, Domenico Saccà: Equivalence and Mapping of Database Schemes. VLDB 1984: 187-195
  35. Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207
  36. Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255
  37. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
  38. Domenico Saccà, F. Manfredi, A. Mecchia: Properties of Database Schemata with Functional Dependencies. PODS 1984: 19-28
  39. Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152
  40. Gösta Grahne, Kari-Jouko Räihä: Dependency Characterizations for Acyclic Database Schemes. PODS 1984: 9-18
  41. Patrick C. Fischer, Dirk Van Gucht: Weak Multivalued Dependencies. PODS 1984: 266-274
  42. Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8
  43. Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200
  44. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
  45. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
  46. David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983)
  47. William Kent: The Universal Relation Revisited. ACM Trans. Database Syst. 8(4): 644-648(1983)
  48. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
  49. Joachim Biskup, Hans Hermann Brüggemann: Universal Relation Views: A Pragmatic Approach. VLDB 1983: 172-185
  50. Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
  51. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
  52. Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91
  53. Sharon McCure Kuck, Yehoshua Sagiv: Designing Globally Consistent Network Schemas. SIGMOD Conference 1983: 185-195
  54. Peter Honeyman, Edward Sciore: A New Characterization of Independence. SIGMOD Conference 1983: 92-96
  55. Alessandro D'Atri, Marina Moscarini, Nicolas Spyratos: Answering Queries in Relational Databases. SIGMOD Conference 1983: 173-177
  56. Edward Sciore: Improving Database Schemes by Adding Attributes. PODS 1983: 379-383
  57. Edward Sciore: Inclusion Dependencies and the Universal Instance. PODS 1983: 48-57
  58. Domenico Saccà: On the Recognition of Coverings of Acyclic Database Hypergraphs. PODS 1983: 297-304
  59. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287
  60. Tomasz Imielinski, Witold Lipski Jr.: Inverting Relational Expressions - A Uniform and Natural Technique for Various Database Problems. PODS 1983: 305-311
  61. Nathan Goodman, Oded Shmueli, Y. C. Tay: GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections. PODS 1983: 267-278
  62. Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296
  63. Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
  64. Serge Abiteboul: Disaggregations in Databases. PODS 1983: 384-388
  65. William Kent: Fact-Based Data Analysis and Design. ER 1983: 3-53
  66. Sushil Jajodia, Peter A. Ng, Frederick N. Springsteel: On Universal and Representative Instances for Inconsistent Databases. ER 1983: 279-295
  67. Sushil Jajodia, Peter A. Ng: On the Representation of Relational Structures by Entity-Relationship Diagrams. ER 1983: 249-263
  68. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  69. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
  70. David Maier, David Rozenshtein, Sharon C. Salveter, Jacob Stein, David Scott Warren: Toward Logical Data Independence: A Relational Query Language Without Relations. SIGMOD Conference 1982: 51-60
  71. Tomasz Imielinski, Witold Lipski Jr.: A Technique for Translating States Between Database Schemata. SIGMOD Conference 1982: 61-68
  72. Tomasz Imielinski, Witold Lipski Jr.: A Systematic Approach to Relational Database Theory. SIGMOD Conference 1982: 8-14
  73. Jirun Dong, Richard Hull: Applying Approximate Order Dependency to Reduce Indexing Space. SIGMOD Conference 1982: 119-127
  74. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
  75. David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39
  76. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
  77. Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
  78. Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54
  79. Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48
  80. Catriel Beeri, Henry F. Korth: Compatible Attributes in a Universal Relation. PODS 1982: 55-62
  81. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9
  82. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
  83. Katsumi Tanaka, Yahiko Kambayashi: Logical Integration of Locally Independent Relational Databases into a Distributed Database. VLDB 1981: 131-141
  84. Karen Chase: Join Graphs and Acyclic Database Schemes. VLDB 1981: 95-100
  85. Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132
  86. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:49 2008