Fragmentation: a technique for efficient query processing

ABSTRACT

A “divide and conquer” strategy to compute natural joins by sequential scans on unordered relations is described. This strategy is shown to always he better than merging SCBIIS when both relations must he sorted before joining, and generally better in practical cases when only the largest relation mutt be sorted.

REFERENCES

• 1: 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]
• 2: BLASGEN, E. W., AND ESWARAN, K.P. Storage and access in a relational database. IBM Syst. J. 16, 4 (1977), 363-377.
• 3: BR^DLE~, J.V. Distribution-Free Statistical Tests. Prentice-Hall, Englewood Cliffs, N.J., 1968.
• 4: 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]
• 5: CODD, E. F. Relational completeness of database sublanguages. In Data Base Systems, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, 65-98.
• 6: CObb, E.F. Further normalization of the database relational model. In Data Base Systems, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, 33-64.
• 7: 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
• 8: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• 9: HEISIN6, W.P. Note on random addressing techniques. IBM Syst. J. 2 (1963), 114-115.
• 10: 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]
• 11: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: 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]
• 14: 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]
• 15: 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]
• 16: 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]
• 17: Domenico Sacca , Gio Wiederhold, Database partitioning in a cluster of processors, ACM Transactions on Database Systems (TODS), v.10 n.1, p.29-56, March 1985 [doi>10.1145/3148.3161]
• 18: SACCO, G.M. Fragmentation: A technique for efficient query processing. TR 20/11/82, Univ. di Torino, Dip. di Informatica (revised: 26/8/83).
• 19: Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
• 20: 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]
• 21: 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]
• 22: David Elliot Shaw, A relational database machine architecture, Proceedings of the fifth workshop on Computer architecture for non-numeric processing, p.84-95, March 11-14, 1980, Pacific Grove, California, United States
• 23: SHAW, D. E., ET AL. The NON-VON database machine: A brief overview. IEEE Database Eng. Buff. (Dec. 1981), 43-54.
• 24: Dan E Willard, Efficient processing of relational calculus expressions using range query theory, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 25: E. Wong , R. H. Katz, Distributing a database for parallelism, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 26: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 27: S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979 [doi>10.1145/320071.320072]
• 28: ZwF, G. K. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley, Reading, Mass., 1949.

INDEX TERMS

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

General Terms:
Algorithms, Economics, Performance