The Theory of Joins in Relational Databases.

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979)
  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        = {, db/journals/tods/AhoBU79.html},
  bibsource = {DBLP,}


Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is lossless) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

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

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


Jeffrey D. Ullman: Corrigendum: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 8(2): 287(1983) BibTeX


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359 BibTeX
Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
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
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
E. F. Codd: Recent Investigations in Relational Data Base Systems. IFIP Congress 1974: 1017-1021 BibTeX
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
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
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
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX

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
  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
  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
  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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:40 2008