The Theory of Joins in Relational Databases.

@article{DBLP:journals/tods/AhoBU79,
  author    = {Alfred V. Aho and
               Catriel Beeri and
               Jeffrey D. Ullman},
  title     = {The Theory of Joins in Relational Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {3},
  year      = {1979},
  pages     = {297-314},
  ee        = {http://doi.acm.org/10.1145/320083.320091, db/journals/tods/AhoBU79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1979 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

• 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/An3-1 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Corrigendum

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[2]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[3]

Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359 BibTeX

[4]

Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX

[5]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 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]

Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX

[9]

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

[10]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[11]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[12]

E. F. Codd: Recent Investigations in Relational Data Base Systems. IFIP Congress 1974: 1017-1021 BibTeX

[13]

...

[14]

...

[15]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[16]

...

[17]

David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. Advances in Data Base Theory 1979: 101-114 BibTeX

[18]

Glenn K. Manacher: On the Feasibility of Implementing a Large Relational Data Base with Optimal Performance on a Mini-Computer. VLDB 1975: 175-201 BibTeX

[19]

Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX

[20]

Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX

[21]

...

Referenced by

1. Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)
2. Alberto O. Mendelzon: Review - The Theory of Joins in Relational Databases. ACM SIGMOD Digital Review 1: (1999)
3. Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
4. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
5. Richard T. Snodgrass, Laura M. Haas, Alberto O. Mendelzon, Z. Meral Özsoyoglu, Jan Paredaens, Krithi Ramamritham, Nick Roussopoulos, Jennifer Widom, Philip S. Yu: Reminiscences on Influential Papers. SIGMOD Record 27(4): 81-85(1998)
6. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
7. Joachim Biskup, Andreas Kluck: A New Approach to Inferences of Semantic Constraints. ADBIS 1997: 72-79
8. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
9. Liwu Li: Fast In-Place Verification of Data Dependencies. IEEE Trans. Knowl. Data Eng. 5(2): 266-281(1993)
10. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
11. C. J. Date, Ronald Fagin: Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases. ACM Trans. Database Syst. 17(3): 465-476(1992)
12. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
13. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
14. Tok Wang Ling, Cheng Hian Goh: Logical Database Design with Inclusion Dependencies. ICDE 1992: 642-649
15. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
16. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
17. Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131
18. Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127
19. Edward A. Komissartschik: Restructuring and Dependencies in Databases. MFDBS 1989: 269-284
20. Jürgen M. Janas: Covers for Functional Independencies. MFDBS 1989: 254-268
21. Georg Gottlob, Michael Schrefl, Markus Stumptner: On the Interaction between Transitive Closure and Functional Dependencies. MFDBS 1989: 187-206
22. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
23. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988)
24. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
25. Stephen J. Hegner: Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction. PODS 1988: 174-183
26. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
27. Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
28. Edward P. F. Chan, Héctor J. Hernández: On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies. PODS 1987: 48-57
29. Henri Briand, C. Ducateau, Y. Hebrail, Danièle Hérin-Aime, Jacques Kouloumdjian: From Minimal Cover to Entity-Relationship Diagram. ER 1987: 287-304
30. Paolo Atzeni, Douglas Stott Parker Jr.: Algorithms for Set Containment Inference. DBPL 1987: 117-127
31. Marc Gyssens: On the Complexity of Join Dependencies. ACM Trans. Database Syst. 11(1): 81-108(1986)
32. Catriel Beeri, Michael Kifer: An Integrated Approach to Logical Design of Relational Database Schemes. ACM Trans. Database Syst. 11(2): 134-158(1986)
33. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
34. Peter Thanisch, George Loizou: A Polynomial-Time Join Dependency Implication Algorithm for Multi-Valued Dependencies. ICDT 1986: 397-408
35. Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396
36. Dirk Van Gucht: Interaction-Free Multivalued Dependency Sets. ICDT 1986: 409-420
37. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
38. K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies in Fuzzy Relations. ICDE 1986: 312-319
39. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
40. Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
41. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
42. Ashok Pahwa, Adarsh K. Arora: Automatic Database Navigation: Towards a High Level User Interface. ER 1985: 36-43
43. 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)
44. 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)
45. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
46. K. P. Tan: A Less Costly Constraints Checking for Join Dependency. VLDB 1984: 63-68
47. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
48. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
49. Tomasz Imielinski, Nicolas Spyratos: On Lossless Transformation of Database Schemes not Necessarily Satisfying Universal Instance Assumption. PODS 1984: 258-265
50. Marc Gyssens, Jan Paredaens: On the Decomposition of Join Dependencies. PODS 1984: 143-152
51. Jeffrey D. Ullman: On Kent's "Consequences of Assuming a Universal Relation". ACM Trans. Database Syst. 8(4): 637-643(1983)
52. Jeffrey D. Ullman: Corrigendum: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 8(2): 287(1983)
53. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
54. David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983)
55. William Kent: The Universal Relation Revisited. ACM Trans. Database Syst. 8(4): 644-648(1983)
56. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
57. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
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. Stephen J. Hegner: Algebraic Aspects of Relational Database Decomposition. PODS 1983: 400-413
62. Marc H. Graham: Path Expressions in Databases. PODS 1983: 366-378
63. Nathan Goodman, Oded Shmueli, Y. C. Tay: GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections. PODS 1983: 267-278
64. Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351
65. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
66. Carlo Zaniolo: A New Normal Form for the Design of Relational Database Schemata. ACM Trans. Database Syst. 7(3): 489-499(1982)
67. Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982)
68. 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)
69. Edward Babb: Joined Normal Form: A Storage Encoding for Relational Databases. ACM Trans. Database Syst. 7(4): 588-614(1982)
70. Tomasz Imielinski, Witold Lipski Jr.: A Technique for Translating States Between Database Schemata. SIGMOD Conference 1982: 61-68
71. Tomasz Imielinski, Witold Lipski Jr.: A Systematic Approach to Relational Database Theory. SIGMOD Conference 1982: 8-14
72. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
73. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
74. Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. PODS 1982: 199-204
75. Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. PODS 1982: 171-176
76. Marco A. Casanova: A Theory of Data Dependencies over Relational Expressions. PODS 1982: 189-198
77. Catriel Beeri, Henry F. Korth: Compatible Attributes in a Universal Relation. PODS 1982: 55-62
78. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9
79. 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)
80. Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981)
81. Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981)
82. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
83. Michel E. Adiba: Derived Relations: A Unified Mechanism for Views, Snapshots, and Distributed Data. VLDB 1981: 293-305
84. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120
85. Randy H. Katz, Nathan Goodman: View Processing in MULTIBASE, A Heterogeneous Database System. ER 1981: 257-277
86. Ilchoo Chung, Fumio Nakamura, Peter P. Chen: A Decomposition of Relations Using the Entity-Relationship Approach. ER 1981: 149-171
87. Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980)
88. Peter Honeyman: Extension Joins. VLDB 1980: 239-244
89. Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259
90. Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91
91. Fereidoon Sadri, Jeffrey D. Ullman: The Interaction between Functional Dependencies and Template Dependencies. SIGMOD Conference 1980: 45-51
92. Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979)
93. Michel A. Melkanoff, Carlo Zaniolo: Decomposition of Relations and Synthesis of Entity-Relationship Diagrams. ER 1979: 277-294