Join processing in relational databases

ABSTRACT

The join operation is one of the fundamental relational database query operations. It facilitates the retrieval of information from two different relations based on a Cartesian product of the two relations. The join is one of the most diffidult operations to implement efficiently, as no predefined links between relations are required to exist (as they are with network and hierarchical systems). The join is the only relational algebra operation that allows the combining of related tuples from relations on different attribute schemes. Since it is executed frequently and is expensive, much research effort has been applied to the optimization of join processing. In this paper, the different kinds of joins and the various implementation techniques are surveyed. These different methods are classified based on how they partition tuples from different relations. Some require that all tuples from one be compared to all tuples from another; other algorithms only compare some tuples from each. In addition, some techniques perform an explicit partitioning, whereas others are implicit.

REFERENCES

• 1: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Composition of Database Relations, Proceedings of the Fifth International Conference on Data Engineering, p.102-108, February 06-10, 1989
• 2: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 3: ATKINSON, M., BANCILHON, F., DEWITT, D., DITTRICH, K., MAIER, D., AND ZDOlXIIK, S. 1989 The object-oriented database system manifesto. In Proceedings of the Deductive an d Object Oriented Database8 Conference.
• 4: BABA, T., SAITO, H., AND YAO, S. B. 1987. A network algorithm for relational database operations. In International Workshop on Database Machines, pp. 257-270.
• 5: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 6: BANCILHON, F., RICHARD, P., AND SCHOLL, M 1983. VERSO: The relational database machine. In Advanced Database Machine Architecture, D. Hsiao, Ed., Prentice-Hall, Englewood Cliffs, N.J.
• 7: S. Bandyopadhyay , A. Sengupta, A robust protocol for parallel join operation in distributed data bases, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.97-106, December 05-07, 1988, Austin, Texas, United States
• 8: Jay Banerjee , Won Kim , Kyung-Chang Kim, Queries in Object-Oriented Databases, Proceedings of the Fourth International Conference on Data Engineering, p.31-38, February 01-05, 1988
• 9: C. K. Baru , O. Frieder, Database Operations in a Cube-Connected Multicomputer System, IEEE Transactions on Computers, v.38 n.6, p.920-927, June 1989 [doi>10.1109/12.24307]
• 10: BARU, C. K, FRIEDER, 0., DANDLUR, D., AND SEGAL, M. 1987. Join on a cube: Analysis, simulation and implementation. In Proceedings of International Workshop on Database Machines (Dec.), pp. 74-87.
• 11: BEEm, C., AND VARDI, M. Y. 1981. On the properties of join dependencies. In Advances zn Database Theory, vol. 1. Plenum Publishing, New York, pp. 25-72.
• 12: David A. Bell , D. H. O. Ling , Sally I. McClean, Pragmatic Estimation of Join Sizes and Attribute Correlations, Proceedings of the Fifth International Conference on Data Engineering, p.76-84, February 06-10, 1989
• 13: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 14: BENTLEY, J. L. 1979. Multidimensional binary search trees in database applications. IEEE Trans. Softw. Eng. SE-5, 4 (July).
• 15: BENTLEY, J. L., AND KUNG, H. T. 1979. A tree machine for searching problems. IEEE Conference on Parallel Processing, pp. 257-266.
• 16: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 17: BERNSTmN, P. A., A~D GOODMAN, N. 1979a The theory of semijoins. Computer Corporation of America Rep. 79-27, Cambridge, Mass.
• 18: BERNSTmN, P. A., AND GOODMAN, N. 1979b. Inequality semijoins. Computer Corporation of America Rep. 79-28, Cambridge, Mass.
• 19: BERNSTEIN, P A, AND GOODMAN, N. 1980. The power of inequality semijolns Aiken Computa~ tion Lab Rep. 12-80, Harvard Umv., Cambridge, Mass.
• 20: E. Bertino , W. Kim, Indexing Techniques for Queries on Nested Objects, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.196-214, June 1989 [doi>10.1109/69.87960]
• 21: Dina Bitton , Maria Hanrahan , Carolyn Turbyfill, Performance of Complex Queries in Main Memory Database Systems, Proceedings of the Third International Conference on Data Engineering, p.72-81, February 03-05, 1987
• 22: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• 23: BLASGEN, M. W., AND ESWARAN, K. P. 1977. Storage and access in relational databases. IBM Syst. J. 16, 4, 363-377
• 24: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 25: Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
• 26: BmTTON LEE, INC. 1981. IDM 500: Intelligent Database Machine Product Description.
• 27: Stephanie Cammarata , Prasadram Ramachandra , Darrell Shane, Extending a relational database with deferred referential integrity checking and intelligent joins, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.88-97, June 1989, Portland, Oregon, United States
• 28: Michael Carey , George Lapis , Eugene Shekita , Bruce Lindsay , John McPherson, An incremental join attachment for Starburst, Proceedings of the sixteenth international conference on Very large databases, p.662-673, September 1990, Brisbane, Australia
• 29: S Ceri , G Gottlob , G Pelagatti, Taxonomy and formal properties of distributed joins, Information Systems, v.11 n.1, p.25-40, 1986 [doi>10.1016/0306-4379(86)90021-9]
• 30: J. M. Chang , K. S. Fu, A dynamic clustering technique for physical database design, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582280]
• 31: Jean-Pierre Cheiney , Pascal Faudemay , Rodolphe Michael, An Extension of Access Paths to Improve Joins and Selections, Proceedings of the Second International Conference on Data Engineering, p.270-280, February 05-07, 1986
• 32: Jason S. J. Chen , Victor O. K. Li, Optimizing Joins in Fragmented Database Systems on a Broadcast Local Network, IEEE Transactions on Software Engineering, v.15 n.1, p.26-38, January 1989 [doi>10.1109/32.21723]
• 33: C~mSTODUL^KIS, S. 1985 Estimating block transfer and join sizes In Proceedings of SIGMOD CODASYL, 1971. Data Base Task Group Report.
• 34: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 35: ConD, E. F. 1972. Relational completeness of data base sublanguages. In Data Base Systems. Prentice-Hall, Englewood Cliffs, N.J., pp. 65-98.
• 36: Douglas W. Cornell , Philip S. Yu, Site Assignment for Relations and Join Operations in the Distributed Transaction Processing Environment, Proceedings of the Fourth International Conference on Data Engineering, p.100-108, February 01-05, 1988
• 37: Alfred G. Dale , Furman F. Haddix , Roy M. Jenevein , Christopher B. Walton, Scalability of Parallel Joins on High Performance Multicomputers, University of Texas at Austin, Austin, TX, 1989
• 38: DATE, C. J. 1983. The outer join. In Proceedings of International Conference on Databases (Cambridge, England), pp. 76-106.
• 39: DAYAL, U. 1985. Query processing in a multidatabase system. In Query Processzng in Database Systems, W. Kim, D. S. Reiner, and D. S. Batory, Eds. Springer-Verlag, New York, pp. 81-108.
• 40: Bipen C. Desai, Performance of a Composite Attribute and Join Index, IEEE Transactions on Software Engineering, v.15 n.2, p.142-152, February 1989 [doi>10.1109/32.21741]
• 41: Bipin C. Desai, An introduction to database systems, West Publishing Co., St. Paul, MN, 1990
• 42: DESHPANDE, V., LARSON, P.-A., AND MARTIN, T. P. 1990. Parallel join algorithms for nested relations on shared-memory multiprocessors. IEEE Symposium on Parallel and Distributed Processing, pp. 344-351.
• 43: DEWITT, D., AND GERBER, R. J. 1985. Multiprocessor hash-based join algorithms. In Proceedings of Conference on Very Large Data Bases, pp. 151-164.
• 44: David J. DeWitt , Jim Gray, Parallel database systems: the future of database processing or a passing fad?, ACM SIGMOD Record, v.19 n.4, p.104-112, Dec. 1990 [doi>10.1145/122058.122071]
• 45: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 46: Alan F. Dutka , Howard H. Hansen, Fundamentals of data normalization, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 47: EHRENSBERGER, M. J. 1984. The DBC/1012 database computer's systems-architecture, components, and performance. In Minnowbrook Workshop on Database Machines.
• 48: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
• 49: Ramez Elmasri , Gene T. J. Wuu , Yeong-Joon Kim, The time index—an access structure for temporal data, Proceedings of the sixteenth international conference on Very large databases, p.1-12, September 1990, Brisbane, Australia
• 50: EPSTEIN, R., AND STONEBRAKER, M. 1980. Analysis of distributed database processing strategies. In Proceedings of Conference on Very Large Data Bases, pp. 92-101.
• 51: EPSTEIN, R. 1982. Query Processing Techniques for Distributed, Relational Database Systems. University Microfilms International, Ann Arbor, Mich.
• 52: Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
• 53: F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989 [doi>10.1109/69.87978]
• 54: Shinya Fushimi , Masaru Kitsuregawa , Masaya Nakayama , Hidehiko Tanaka , Tohru Moto-oka, Algorithm and performance evaluation of adaptive multidimensional clustering technique, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.308-318, May 1985, Austin, Texas, United States
• 55: Georges Gardarin , Patrick Valduriez, Relational databases and knowledge bases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 56: GERBER, R. J. 1986. Datafiow query processing using multiprocessor hash-partitioned algorithms. Computer Sciences Tech. Rep. No. 672, Computer Sciences Dept., Univ. of Wisconsin, Madison, Wisc.
• 57: Shahram Ghandeharizadeh , David J. DeWitt, Hybrid-range partitioning strategy: a new declustering strategy for multiprocessor databases machines, Proceedings of the sixteenth international conference on Very large databases, p.481-492, September 1990, Brisbane, Australia
• 58: GOODMAN, J. R. 1981. An investigation of multiprocessor structures and algorithms for database management. Tech. Rep. UCB/ERL, M81/33, Univ. oF California, Berkeley.
• 59: Mohamed G. Gouda , Umeshwar Dayal, Optimal semijoin schedules for query processing in local distributed database systems, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582344]
• 60: P. Goyal , H. F. Li , E. Regener , F. Sadri, Scheduling of Page Fetches in Join Operations Using Bc-Trees, Proceedings of the Fourth International Conference on Data Engineering, p.304-310, February 01-05, 1988
• 61: Goetz Graefe, Relational Division: Four Algorithms and Their Performance, Proceedings of the Fifth International Conference on Data Engineering, p.94-101, February 06-10, 1989
• 62: Marc Gyssens, On the complexity of join dependencies, ACM Transactions on Database Systems (TODS), v.11 n.1, p.81-108, March 1986 [doi>10.1145/5236.5237]
• 63: Robert B. Hagmann, An Observation on Database Buffering Performance Metrics, Proceedings of the 12th International Conference on Very Large Data Bases, p.289-293, August 25-28, 1986
• 64: Lilian Harada , Miyuki Nakano , Masaru Kitsuregawa , Mikio Takagi, Query processing method for multi-attribute clustered relations, Proceedings of the sixteenth international conference on Very large databases, p.59-70, September 1990, Brisbane, Australia
• 65: Thomas R. Harbron, File systems: structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 66: James P. Held , John V. Carlis, MATCH—a new high-level relational operator for pattern matching, Communications of the ACM, v.30 n.1, p.62-75, Jan. 1987 [doi>10.1145/7885.7889]
• 67: HS~AO, D. K. (ED.) 1980. Collected Readings on a Database Computer (DBC). The Ohio State University, Columbus, Ohio
• 68: Kien A. Hua , Chiang Lee, An adaptive data placement scheme for parallel database computer systems, Proceedings of the sixteenth international conference on Very large databases, p.493-506, September 1990, Brisbane, Australia
• 69: HURSC~, J. L. 1989. Relational joins: More than meets the eye. Database Program. Design 2, 12 (Dec.), 64-70.
• 70: HURSON, A. R. 1981. An associative backend for data base management. IEEE Workshop on Computer Architecture for Pattern Analysis and Image Data Base Management, pp. 225-230.
• 71: HURSON, A. R. 1986. VLSI time/space complexity of an associative parallel join module. In International Conference on Parallel Processing, pp. 379-386.
• 72: A. R. Hurson , L. L. Miller , B Shirazi , S. H. Pakzad, Performance evaluation of an associative parallel join module, Computer Systems Science and Engineering, v.4 n.3, p.131-146, July 1989
• 73: IBM 1978. IMS/VS General Information Manual GH20-1260. White Plains, New York
• 74: INTEL CORPORATION. iDBP DBMS Reference Manual, Order No. 222100.
• 75: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• 76: KAMBAYASm, Y 1985 Processing cyclic queries. In Query Processing in Database Systems, W. Kim, D. S. Reiner, and D. S. Batory, Eds. Sprmger-Verlag, New York, pp. 62-78.
• 77: Hyunchul Kang , Nick Roussopoulos, Using 2-way Semijoins in Distributed Query Processing, Proceedings of the Third International Conference on Data Engineering, p.644-651, February 03-05, 1987
• 78: KANG, H., AND ROUSSOPULOS, N. 1987b. On the cost-effectiveness of a semijoin in query processing. In COMPSAC, pp. 531-537.
• 79: William Kent, A simple guide to five normal forms in relational database theory, Communications of the ACM, v.26 n.2, p.120-125, Feb. 1983 [doi>10.1145/358024.358054]
• 80: Won Kim, A new way to compute the product and join of relations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582278]
• 81: W. Kim, A model of queries for object-oriented databases, Proceedings of the 15th international conference on Very large data bases, p.423-432, July 1989, Amsterdam, The Netherlands
• 82: Won Kim , D. S. Reiner , D. S. Batory, Query Processing in Database Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• 83: KITSUREGAWA, M., TANAKA, H., AND MOTO-OKA, T. 1983. Application of hash to database machine and its architecture. New Generation Com~ut. 1, }.
• 84: Masaru Kitsuregawa , Miyuki Nakano , Mikio Takagi, Query Execution for Large Relations on Functional Disk Systems, Proceedings of the Fifth International Conference on Data Engineering, p.159-167, February 06-10, 1989
• 85: Masaru Kitsuregawa , Lilian Harada , Mikio Takagi, Join Strategies on KB-Tree Indexed Relations, Proceedings of the Fifth International Conference on Data Engineering, p.85-93, February 06-10, 1989
• 86: M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
• 87: Masaru Kitsuregawa , Yasushi Ogawa, Bucket spreading parallel hash: a new, robust, parallel hash join method for data skew in the super database computer (SDC), Proceedings of the sixteenth international conference on Very large databases, p.210-221, September 1990, Brisbane, Australia
• 88: Akhil Kumar , Michael Stonebraker, The effect of join selectives on optimal nesting order, ACM SIGMOD Record, v.16 n.1, p.28-41, March 1987 [doi>10.1145/24820.24822]
• 89: H. T. Kung , Philip L. Lehman, Systolic (VLSI) arrays for relational database operations, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582267]
• 90: M. Seetha Lakshmi , P. S. Yu, Effect of skew on join performance in parallel architectures, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.107-120, December 05-07, 1988, Austin, Texas, United States
• 91: M. Seetha Lakshmi , Philip S. Yu, Limiting Factors of Join Performance on Parallel Processors, Proceedings of the Fifth International Conference on Data Engineering, p.488-496, February 06-10, 1989
• 92: M. S. Lakshmi , P. S. Yu, Effectiveness of Parallel Joins, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.410-424, December 1990 [doi>10.1109/69.63253]
• 93: Tobin J. Lehman , Michael J. Carey, Query processing in main memory database management systems, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.239-250, May 28-30, 1986, Washington, D.C., United States
• 94: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 95: Lu, H , AND CAREY, M. 1985. Some experimental results on distributed join algorithms in a local network. In Proceedings of Conference on Very Large Databases, pp 292-304.
• 96: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 97: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 98: S. Masuyama , T. Ibaraki , S. Nishio , T. Hasegawa, Shortest semijoin schedule for a local area distributed database system, IEEE Transactions on Software Engineering, v.13 n.5, p.602-606, May 1987 [doi>10.1109/TSE.1987.233465]
• 99: MENEZES, B. L., THADANI, K., DALE, A. G., AND JENEVmN, R 1987. Design of a HyperKYK- LOS-based multiprocessor architecture for high-performance join operations. In International Workshop on Database Machines, pp. 74-87.
• 100: K. P. Mikkilineni , S. Y. W. Su, An Evaluation of Relational Join Algorithms in a Pipelined Query Processing Environment, IEEE Transactions on Software Engineering, v.14 n.6, p.838-848, June 1988 [doi>10.1109/32.6162]
• 101: J. K. Mullin, Optimal Semijoins for Distributed Database Systems, IEEE Transactions on Software Engineering, v.16 n.5, p.558-560, May 1990 [doi>10.1109/32.52778]
• 102: M. C. Murphy , D. Rotem, Effective resource utilization for multiprocessor join execution, Proceedings of the 15th international conference on Very large data bases, p.67-76, July 1989, Amsterdam, The Netherlands
• 103: Marguerite C. Murphy , Doron Rotem, Processor Scheduling for Multiprocessor Joins, Proceedings of the Fifth International Conference on Data Engineering, p.140-148, February 06-10, 1989
• 104: T. Nakayama , Masahito Hirakawa , Tadao Ichikawa, Architecture and Algorithm for Parallel Execution of a Join Operation, Proceedings of the First International Conference on Data Engineering, p.160-166, April 24-27, 1984
• 105: Masaya Nakayama , Masaru Kitsuregawa , Mikio Takagi, Hash-Partitioned Join Method Using Dynamic Destaging Strategy, Proceedings of the 14th International Conference on Very Large Data Bases, p.468-478, August 29-September 01, 1988
• 106: Edward R. Omiecinski, Heuristics for Join Processing Using Nonclustered Indexes, IEEE Transactions on Software Engineering, v.15 n.1, p.18-25, January 1989 [doi>10.1109/32.21722]
• 107: 0MIECINSKI, E., AND SHONKWILER, R. 1990. Parallel join processing using nonclustered indexes for a shared memory environment. In IEEE Symposium on Parallel and Distributed Processing, pp. 144-159.
• 108: Sylvia L. Osborn , T. E. Heaven, The design of a relational database system with abstract data types for domains, ACM Transactions on Database Systems (TODS), v.11 n.3, p.357-373, Sept. 1986 [doi>10.1145/6314.6461]
• 109: Esen Ozkarahan, Database machines and database management, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 110: E. A. Ozkarahan , C. H. Bozsahin, Join strategies using data space partitioning, New Generation Computing, v.6 n.1, p.19-39, 1988 [doi>10.1007/BF03037503]
• 111: Gultekin Özsoyoğlu , Victor Matos , Meral Özsoyoğlu, Query processing techniques in the summary-table-by-example database query language, ACM Transactions on Database Systems (TODS), v.14 n.4, p.526-573, Dec. 1989 [doi>10.1145/76902.76906]
• 112: W. Perrizo , J. Y. Y. Lin , W. Hoffman, Algorithms for Distributed Query Processing in Broadcast Local Area Networks, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.215-225, June 1989 [doi>10.1109/69.87961]
• 113: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 114: S Pramanik, Performance analysis of a database filter search hardware, IEEE Transactions on Computers, v.35 n.12, p.1077-1082, Dec. 1986 [doi>10.1109/TC.1986.1676716]
• 115: PRAMANIK, S., AND FOTOUHI, F. 1985. An index database machine: An efficient m-way join processor. In Proceedings of Hawaii International Conference on System Sciences, vol. 1, pp. 330-338.
• 116: Sakti Pramanik , David Ittner, Use of graph-theoretic models for optimal relational database accesses to perform join, ACM Transactions on Database Systems (TODS), v.10 n.1, p.57-74, March 1985 [doi>10.1145/3148.3325]
• 117: S. Pramanik , D. Vineyard, Optimizing Join Queries in Distributed Databases, IEEE Transactions on Software Engineering, v.14 n.9, p.1319-1326, September 1988 [doi>10.1109/32.6175]
• 118: Philippe Pucheral , Jean-Marie Thévenin , P. Valduriez, Efficient main memory data management using the DBgraph storage model, Proceedings of the sixteenth international conference on Very large databases, p.683-695, September 1990, Brisbane, Australia
• 119: L Raschid , T Fei , H Lam , S Y W Su, A special-function unit for sorting and sort-based database operations, IEEE Transactions on Computers, v.35 n.12, p.1071-1077, Dec. 1986 [doi>10.1109/TC.1986.1676715]
• 120: James P. Richardson , Hongjun Lu , Krishna Mikkilineni, Design and evaluation of parallel pipelined join algorithms, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.399-409, May 27-29, 1987, San Francisco, California, United States
• 121: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 122: Arnon Rosenthal , Cesar Galindo-Legaria, Query graphs, implementing trees, and freely-reorderable outerjoins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.291-299, May 23-26, 1990, Atlantic City, New Jersey, United States
• 123: Arnon Rosenthal , David S. Reiner, Extending the Algebraic Framework of Query Processing to Handle Outerjoins, Proceedings of the 10th International Conference on Very Large Data Bases, p.334-343, August 27-31, 1984
• 124: RUDOLPH, J. A. 1972a. A production implementation of an associative array processor. In Proceedings of Fall ,)o~nt Computer Conference, pp. 229-241.
• 125: Giovanni Maria Sacco, Distributed Query Evaluation in Local Area Networks, Proceedings of the First International Conference on Data Engineering, p.510-516, April 24-27, 1984
• 126: Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986 [doi>10.1145/7239.7336]
• 127: SAKAI, H., IWATA, K., KAMIYA, S., ABE, M., TANAKA, A., SHIBAYAMA, S., AND MURAKAMI, K. 1984. Design and implementation of the relational database engine. In Proceedings of Conference on Fifth Generation Computer Systems, pp. 419-435.
• 128: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States
• 129: Arie Segev, Optimization of join operations in horizontally partitioned database systems, ACM Transactions on Database Systems (TODS), v.11 n.1, p.48-80, March 1986 [doi>10.1145/5236.5241]
• 130: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 131: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 132: Eugene J. Shekita , Michael J. Carey, A performance evaluation of pointer-based joins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.300-311, May 23-26, 1990, Atlantic City, New Jersey, United States
• 133: Michael Stonebraker , Lawrence A. Rowe, The POSTGRES Papers, University of California at Berkeley, Berkeley, CA, 1987
• 134: Stanley Y. W. Su, Database computers: principle, architectures & techniques, McGraw-Hill, Inc., New York, NY, 1988
• 135: Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
• 136: Tandem Database Group - NonStop SQL: A Distributed, High-Performance, High-Availability Implementation of SQL, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.60-104, September 28-30, 1987
• 137: TONG, F., AND YAO, S. B., 1982. Performance analysis of database join processors In National Computer Conference, pp. 627-637.
• 138: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 139: VALDURmZ, P. 1982. Semijoin algorithms for distributed databases. In 3rd International Symposium o7~ Distributed Databases.
• 140: VALDUmEZ, P 1986 Optimization of complex database queries using join indices. Database Eng. 9, 4 (Dec.), 10-16.
• 141: Patrick Valduriez, Join indices, ACM Transactions on Database Systems (TODS), v.12 n.2, p.218-246, June 1987 [doi>10.1145/22952.22955]
• 142: VALDURmZ, P., AND BORAL, H. 1986. Evaluation of recurmve queries using join indices. In Proceedings of Conference on Expert Database Systems.
• 143: V^LDURIEZ, P, AND GARDAmN, G. 1982. Multiprocessor join algorithms of relations In Improving Usability and Responsiveness. Academic Press, New York, pp. 219-237
• 144: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• 145: Patrick Valduriez , Yann Viemont, A multikey hashing scheme using predicate trees, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 146: Patrick Valduriez , Setrag Khoshafian , George P. Copeland, Implementation Techniques of Complex Objects, Proceedings of the 12th International Conference on Very Large Data Bases, p.101-110, August 25-28, 1986
• 147: Christopher B. Walton, Investigating Skew and Scalability in Parallel Joins, University of Texas at Austin, Austin, TX, 1989
• 148: X. Wang , W. S. Luk, Parallel join algorithms on a network of workstations, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.87-96, December 05-07, 1988, Austin, Texas, United States
• 149: WHANG, K.-Y., WIEDERHOLD, G., AND SAGALOWICZ, D. 1985. The property of separability and its application to physical database design. In Query Processing *n Database Systems, W Kim, D. S Reiner, and D S. Batory, Eds. Springer- Verlag, New York, pp. 297-317.
• 150: YAO, S B., TONa, F., ANn SHENG Y. Z. 1981 The system architecture of a data base machine (DBM). IEEE Database Eng. Bull. 4 2, 53-62.
• 151: H. Yoo , S. Lafortune, An Intelligent Search Method for Query Optimization by Semijoins, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.226-237, June 1989 [doi>10.1109/69.87962]
• 152: Masatoshi Yoshikawa , Yahiko Kambayashi, Processing Inequality Queries Based on Generalized Semi-Joins, Proceedings of the 10th International Conference on Very Large Data Bases, p.416-428, August 27-31, 1984
• 153: Clement T. Yu , C. C. Chang , Marjorie Templeton , David Brill , Eric Lund, Query processing in a fragmented relational distributed system: Mermaid, IEEE Transactions on Software Engineering, v.11 n.8, p.795-810, Aug. 1985 [doi>10.1109/TSE.1985.232528]
• 154: C. T. Yu , K.-C. Guh , W. Zhang , M. Templeton , D. Brill , A.L.P. Chen, Algorithms to process distributed queries in fast local networks, IEEE Transactions on Computers, v.36 n.10, p.1153-1164, Oct. 1987 [doi>10.1109/TC.1987.1676856]
• 155: Hansjorrg Zeller , Jim Gray, An adaptive hash join algorithm for multiuser environments, Proceedings of the sixteenth international conference on Very large databases, p.186-197, September 1990, Brisbane, Australia
• 156: François Bancilhon , Micheł Scholl, Design of a backend processor for a data base machine, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582265]
• 157: Jayanta Banerjee , David K. Hsiao , Richard I. Baum, Concepts and capabilities of a database computer\, ACM Transactions on Database Systems (TODS), v.3 n.4, p.347-384, Dec. 1978 [doi>10.1145/320289.320292]
• 158: Joseph D. Brownsmith, A simulation model of the MICRONET computer system during join processing, Proceedings of the 14th annual symposium on Simulation, p.1-16, March 17-20, 1981, Tampa, Florida, United States
• 159: BROWNSMITH, J D., AND SU, S. Y. W. 1980. Performance analysis of the equijoin operation m the MICRONET computer system In Proceedrags oflCC, pp. 264 268.
• 160: CHASE, K. 1981. Join graphs and acyclic database schemes. In Proceedings of Conference on Very Large Data Bases, pp 95-100
• 161: D. M. Chiu , Y. C. Ho, A methodology for interpreting tree queries into optimal semi-join expressions, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582277]
• 162: Paolo Ciaccia , Maria Rita Scalas, Optimization Strategies for Relational Queries, IEEE Transactions on Software Engineering, v.15 n.10, p.1217-1235, October 1989 [doi>10.1109/TSE.1989.559773]
• 163: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 164: DEW,T% D. J. 1979. DIRECT: A multiprocessor organization for supporting relational database management systems. IEEE Trans. Comput. C-28, 6, 395-406.
• 165: DEWITT, D. J., NAUGHTON, J. F., AND SCHNEIDER, D. A. 1991. An evaluation of non-equijoin algorithms. Tech. Rep. 1011, Univ. of Wisconsin-Madison, Madison, Wlsc.
• 166: Danièle Grady , Claude Puech, On the effect of join operations on relation sizes, ACM Transactions on Database Systems (TODS), v.14 n.4, p.574-603, Dec. 1989 [doi>10.1145/76902.76907]
• 167: Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500089]
• 168: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 169: Goetz Graefe, Heap-Filter Merge Join: A New Algorithm for Joining Medium-Size Inputs, IEEE Transactions on Software Engineering, v.17 n.9, p.979-982, September 1991 [doi>10.1109/32.92919]
• 170: HONEYMAN, P. 1980. Extension joins. In Proceedings of Conferences on Very Large Data Bases, pp. 239-244.
• 171: Yang-Chang Hong, A Pipeline and Parallel Architecture for Supporting Database Management Systems, Proceedings of the First International Conference on Data Engineering, p.152-159, April 24-27, 1984
• 172: KAMIBAYASHI, N, AND SEO, K. 1982. SPIRIT-III: An advanced relational database machine introducing a novel data staging architecture with tuple stream filters to preprocess relational algebra. In National Computer Conference Proceedings, pp. 605-616.
• 173: Arthur M. Keller, Algorithms for translating view updates to database updates for views involving selections, projections, and joins, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.154-163, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325423]
• 174: K~NT, W. 1979. The entity join. In Proceedings of Conference on Very large Data Bases, pp. 232 -238.
• 175: M. Lacroix , A. Pirotte, Generalized joins, ACM SIGMOD Record, v.8 n.3, p.14-15, September 1976 [doi>10.1145/984378.984379]
• 176: Hongjun Lu , Kian-Lee Tan , Ming-Chien Sahn, Hash-based join algorithms for multiprocessor computers with shared memory, Proceedings of the sixteenth international conference on Very large databases, p.198-209, September 1990, Brisbane, Australia
• 177: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 178: MENON, M. J. AND HSIAO, D. K. 1983. Design and analysis of join operations of database machines. In Advanced Database Machine Architecture, D. K. Hsiao, Ed. Prentice-Hall, Englewood Cliffs, N.J., pp. 203-255.
• 179: T. H. Merrett, Why sort-merge gives the best implementation of the natural join, ACM SIGMOD Record, v.13 n.2, p.39-51, January 1983 [doi>10.1145/984523.984526]
• 180: T. H. Merrett, Practical hardware for linear execution of relational database operations, ACM SIGMOD Record, v.14 n.1, p.39-44, 1983 [doi>10.1145/984540.984543]
• 181: MERRETT, T, H., KAMBAYASm, Y., AND YASUURA, H. 1981. Scheduling of page fetches in join operations. In Proceedings of Conference on Very Large Data Bases, pp. 488-497.
• 182: E. R. Omiecinski , E. T. Lin, Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.329-343, September 1989 [doi>10.1109/69.87979]
• 183: Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
• 184: QADAH, G. Z. 1984. Evaluation of performance of the equi-join operation on the Michigan relational database machine. In Proceedings of Conference on Parallel Processing, pp. 260-265.
• 185: QADAH, G. Z. 1985. The equijoin operation on a multiprocessor database machine. In Proceed~ ings of Interna~ional Workshop on Database Machines, Spriager-Verlag, New York, pp. 35-67.
• 186: Ghassan Z. Qadah , K. B. Irani, A database machine for very large relational databases, IEEE Transactions on Computers, v.34 n.11, p.1015-1025, Nov. 1985 [doi>10.1109/TC.1985.1676534]
• 187: G. Z. Qadah , K. B. Irani, The Join Algorithms on a Shared-Memory Multiprocessor Database Machine, IEEE Transactions on Software Engineering, v.14 n.11, p.1668-1683, November 1988 [doi>10.1109/32.9054]
• 188: RISSANEN, J. 1979. Theory of joins for relational databases: A tutorial survey. In Proceedings of Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 64 Springer-Verlag, New York, pp. 537-551.
• 189: Arnon S. Rosenthal, Note on the expected size of a join, ACM SIGMOD Record, v.11 n.4, p.19-25, July 1981 [doi>10.1145/984488.984491]
• 190: Donovan A. Schneider , David J. DeWitt, Tradeoffs in processing complex join queries via hashing in multiprocessor database machines, Proceedings of the sixteenth international conference on Very large databases, p.469-480, September 1990, Brisbane, Australia
• 191: SCHUSTER, S. A., }~GUYEN, H. B., OZKARAHAN, E. A., AND SMITH, K. C. 1979. RAP.2: An associative processor for databases and its applications. {EEE Trans. Comput. C-28, 6, 446-458.
• 192: Edward Sciore, A Complete Axiomatization of Full Join Dependencies, Journal of the ACM (JACM), v.29 n.2, p.373-393, April 1982 [doi>10.1145/322307.322313]
• 193: SHAW, D. E. ET AL. 1981. The NON-VON database machine: A brief overview. Database Eng. 4, 2
• 194: Roger Shultz , Ila Miller, Tree Structured Multiple Processor Join Methods, Proceedings of the Third International Conference on Data Engineering, p.190-199, February 03-05, 1987
• 195: Su, S. Y. W., NGUYEN, L. H., EMAN, A., AND LIPOVSKI, G. J. 1979. The architectural features and implementation techniques of multicell CASSM. L~EE Trans. Comput. C-28, 6 (June), 430-445.
• 196: James A. Thom , Kotagiri Ramamohanarao , Lee Naish, A Superjoin Algorithm for Deductive Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.189-196, August 25-28, 1986
• 197: VARm, M. Y. 1980. Axiomatization of functional and join dependencies in the relational model. Weizman InstiLute M.Sc. thesis, Rehovot, Israel.
• 198: VARDI, M. Y. 1983. Inferring multivalued dependencies from functional and join dependencies. Acta Inf. 19, 2, 305-324.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
database machines, distributed processing, join, parallel processing, relational algebra